25 ms·
An Efficient Way to Extract the Main Topics from a Sentence
- languagehacker 13y agoCool idea, but basically reinvents chunking, which NLTK already has (http://nltk.org/api/nltk.chunk.html http://nltk.org/api/nltk.chunk.html). Keep up the writing and NLP research though :)
- DanBC 13y agoThis is neat! The article gives an example which I find a bit confusing. >I ran it on this sentence - > “Swayy is a beautiful new dashboard for discovering and curating online content.” >And got this result - > This sentence is about: Swayy, beautiful new dashboard, online content That misses "discovering" and "curating", which I think are the most important parts of that sentence.
- deleted 13y ago[deleted]
- arrrg 13y agoNah, it filtered out the meaningless buzzwords. It's a dashboard for online content. That pretty much implies the picking and finding of said online content to be displayed on the dashboard.
- danso 13y agoHuh? "Curating" and "discovering" may be overused tech verbs, but they are vital in describing what the "dashboard" does. For example, you would never describe the Google Analytics dashboard as something that curates or discovers. And far worse than buzzwords are adjectives. Does "beautiful" add anything to that sentence?
- arrrg 13y agoGoogle Analytics has nothing whatsoever to do with online content.
- danso 13y agoYou're missing the point. The OP is talking about a system for interpreting sentences in bulk and extracting useful keywords. "beautiful new" are not useful, and arguably, "dashboard" is not particularly useful. "Curating" and "discovering", while grating to our ears, are definitely descriptive words of purpose...because there are "dashboards" that have nothing to do with "curating"...so ostensibly, "curating" has some use as a keyword
- stonemetal 13y agoI disagree. Dashboards curate by definition. Some car dashboards display have a tachometer, some don't it depends on the car's focus. Google Analytics similarly doesn't display all available information, just that which will be useful. Dashboards always display a limited subset of available information that makes sense to the current context aka curated. Discovering is also vacuous. The whole point of a dashboard is to convey information. Do I discover how fast I am going by looking at my car's dashboard? Do I discover my website's traffic by going to Google analytics? Sure, I wouldn't use them if I didn't get the information I need from them. So using an online content dashboard that doesn't deliver online content of some sort would be a waste of time. Beautiful adds something because not all dashboards are beautiful.
- yolesaber 13y agoThis is because he is only extracting the noun phrases from the sentence. If you adapted his code to tag verb phrases as well (by modifying the semi-CFG and the normalize_tags method) then you could also extract "discovering" and "curating" as well.
- RBerenguel 13y agoBut this would miss the "main topics," since when you have both the vp's and the np's you have everything :/ Here is the resulting tree (it's unformatted, sorry, I tweaked an old Prolog grammar I had for analysing search keywords and tweets): [[[[Swayy,snp],np],[is,[a,[[beautiful,new,dashboard,snp],np],np_],vp],simple_s],for,[[discovering,simple_s],and,[[curating,[[online,content,snp],np],vp],simple_s],s],s]
- jweese 13y agoNice writeup. A few comments: So you're just identifying NPs and VPs in a sentence? So lets say I run your program, and I get NPs "Instagram" and "Facebook", and the VP "acquired." The question is, who did what to whom? Did Facebook acquire Instagram, or did Instagram acquire Facebook? Second, I think you're way over-emphasizing the supposed slowness of CFG parsing. Yes, the complexity is O(n^3) in the length of the sentence, but in practice, n is usually small. Modern statistical PCFG parsers are fast.
- alok-g 13y agoMy understanding is different, so please correct me / supply missing information. From what I understand, the average length of a typical written sentence is n = ~27. OK, this is small by itself, but Stanford Parser (lexicalized PCFG) I am using needs about 1 second to parse a sentence of this size. Imagine how slow that is on a computer time-scale by comparing it to string-length operation on the same sentence. I do encounter many sentences that are as much as 100 words long (and reading them myself, find nothing wrong with them). At about four times the length, these take about a minute to parse! I am trying to find information about speeds of other PCFG parsers, including Collins, Charniak, Berkeley, etc. I understand dependency parsers are faster but also generally lag in accuracy.
- syllogism 13y agoThe Stanford parser is particularly slow --- it's in java, and it's written for research more than anything. The C&C CCG parser runs at about 60-80 sentences a second, although it gives either CCG constituents or dependencies -- so the output may take some interpretation. Shift-reduce dependency parsers are linear time, and are giving state-of-the-art results. My parser's currently a pain in the ass to install, as it hasn't really been released yet, but it does hundreds of sentences a second. Accuracy is state-of-the-art -- 92-93% depending on the beam width and the evaluation set (Stanford or MALT dependencies). https://github.com/syllog1sm/redshift/ https://github.com/syllog1sm/redshift/ . You'll want the develop branch. It's GPL licensed. It's implemented in Cython (i.e., almost all the code is Cython --- I'm not using it just for the speed critical bits), which would make it easy to work with if you're using Python. But, as I said...I don't claim it's currently fit for human consumption. A C++ implementation of the same algorithm is here: http://www.sutd.edu.sg/yuezhang.aspx http://www.sutd.edu.sg/yuezhang.aspx . Note his papers too -- he did some of the important work on this line of research. The last few years of work in shift-reduce dependency parsing have been a bit of a break-through in parsing, imo.
- thejosh 13y agoI was interested in this to parse some user entered data extracted from Facebook, and found Text Razor[1] to be pretty good at this. Natural Language is a beautiful thing. [1] http://www.textrazor.com/ http://www.textrazor.com/
- MojoJolo 13y agoFor some NLP, I really suggest using OpenNLP (http://opennlp.apache.org/ http://opennlp.apache.org/) from Apache. It has libraries that can be trained to do different NLP tasks like sentence splitting, tokenizers, POS tagging, and document classification. I still didn't manage to use all of them but in my experience, it's very easy to use. Documentation is good too!
- mindcrime 13y agoI'm a fan of OpenNLP as well, although I haven't done a lot of performance evaluation around it yet. Apache Stanbol[1] is also a very interesting project, which leverages OpenNLP (among other things) for doing semantic entity extraction from text. Also, FWIW, I wrote an article[2] a while back, focusing on Open Source NLP tools. It was aimed slightly more at business users than developers, so it doesn't dig real deep on the tech side, but there is a list of popular OSS NLP tools that people interested in this topic might find useful. And if I can throw in another shameless plug (only because I think it will genuinely be of interest, of course), I'll point out this post[3] on Prolog resources, since Prolog often finds application in the NLP world. [1]: http://stanbol.apache.org http://stanbol.apache.org [2]: http://osintegrators.com/opensoftwareintegrators|howyoucanbenefitfromopensourcenaturallanguageprocessing http://osintegrators.com/opensoftwareintegrators|howyoucanbe... [3]: http://fogbeam.blogspot.com/2013/05/prolog-im-going-to-learn-prolog.html http://fogbeam.blogspot.com/2013/05/prolog-im-going-to-learn...
- danieldk 13y agoAnd if I can throw in another shameless plug (only because I think it will genuinely be of interest, of course), I'll point out this post[3] on Prolog resources, since Prolog often find application in the NLP world You missed the nicest and most satisfying book ;): http://www.mtome.com/Publications/PNLA/pnla-digital.html http://www.mtome.com/Publications/PNLA/pnla-digital.html It is simultaneously an introduction to Prolog and natural language parsing using Prolog.
- mindcrime 13y agoVery cool. That post was originally written quite some time ago, and it was never meant to be an exhaustive list. That said, I'll add this to the list as well. Thanks for the pointer!
- Arjuna 13y agoThis is neat. Shlomib, you might be interested in SHRDLU [1][2] if you are not aware of it. It was developed by Terry Winograd [3] for his dissertation [4] at MIT. It is a natural language understanding [5] parser that allows you to interact with a small world of 3D solids. I think you will find the paper interesting, because it goes into detail on sentence structure and associated parsing. Here is a sample dialogue with the program, taken from Wikipedia: Person: Pick up a big red block. Computer: OK. Person: Grasp the pyramid. Computer: I don't understand which pyramid you mean. Person (changing their mind): Find a block which is taller than the one you are holding and put it into the box. Computer: By "it", I assume you mean the block which is taller than the one I am holding. Computer: OK. Person: What does the box contain? Computer: The blue pyramid and the blue block. Person: What is the pyramid supported by? Computer: The box. Person: How many blocks are not in the box? Computer: Four of them. Person: Is at least one of them narrower than the one which I told you to pick up? Computer: Yes, the red cube. [1] https://en.wikipedia.org/wiki/SHRDLU https://en.wikipedia.org/wiki/SHRDLU [2] http://hci.stanford.edu/winograd/shrdlu/ http://hci.stanford.edu/winograd/shrdlu/ [3] https://en.wikipedia.org/wiki/Terry_Winograd https://en.wikipedia.org/wiki/Terry_Winograd [4] http://hci.stanford.edu/winograd/shrdlu/AITR-235.pdf http://hci.stanford.edu/winograd/shrdlu/AITR-235.pdf [5] https://en.wikipedia.org/wiki/Natural_language_understanding https://en.wikipedia.org/wiki/Natural_language_understanding
- tannerc 13y agoWhy does this seem so scary/amazing? It's basically taking what computers already do really well today and adding a language "mask" onto it. Yet it still blows me away.
- mindcrime 13y agoWhat's really amazing is how old SHRDLU is. It was developed back in the late 60's, early 70's. Although... I guess you could look at it two ways: Be amazed at what SHRDLU could do in 1970, or be disappointed that, given that we had that in 1970, we don't have the "Star Trek Computer" yet in 2013.
- jbrooksuk 13y agoWithout having Brown and NLTK in Node.js, I'm not sure how well I can add this to my port of shlomibs original code. For those who haven't seen yet, I wrote a port of the first part of this here https://github.com/jbrooksuk/node-summary https://github.com/jbrooksuk/node-summary Maybe later I'll give it a crack :)
- RBerenguel 13y agoWordnet & the Brill Pos tagged corpus do the trick, more or less
- edtechdev 13y agohttps://github.com/NaturalNode/natural https://github.com/NaturalNode/natural
- jbrooksuk 13y agoHeh, I raised an issue on my GitHub page https://github.com/jbrooksuk/node-summary/issues/2 https://github.com/jbrooksuk/node-summary/issues/2 and found natural shortly after.
- marknutter 13y agoI smell a $30 million acquisition in the near future..
- danieldk 13y agoBy those standards, many companies will be worth billions ;). (Chunking is not exactly new and PCFG parsing is pretty fast these days.)
- shmageggy 13y agoI think this was a sarcastic commentary on the Summly acquisition.
- marknutter 13y agobingo :)
- teeja 13y agoThe sentence subject is one thing, the sentence <i>topic</i> might be quite another. Consider sentences like: "He joined the not-yet-famous Liverpool band in early 1958." To many human beings the topic is quickly obvious. Parsing won't do the trick.
- run4yourlives 13y agoThe only reason that sentence is "obvious" to many people is because we have a reference to a famous band from Liverpool that got its start in the late 50's/early 60's that is already embedded in our brain's library of facts. Removed from that context human beings see that sentence as equally meaningless as a parser, because it is. I'd imagine many young people (who don't have the "correct" reference points) wouldn't have a clue that the sentence is about George Harrison. In order to properly handle this sentence one would need the same external reference that your brain has. Without the reference the sentence can be discarded as incomplete, since that's what a human would do too.
- yolesaber 13y agoThis is why systems such as MIT's ConceptNet exist. NLTK and other NLP systems can provide the grammatical breakdown and ConceptNet can fill in the semantic / contextual gaps.
- unhammer 13y agoYou don't necessarily need knowledge to distinguish a topic from a subject though. It's a grammatical distinction. See http://en.wikipedia.org/wiki/Topic%E2%80%93comment#Definitions http://en.wikipedia.org/wiki/Topic%E2%80%93comment#Definitio... e.g. in the sentence (3) As for the little girl, the dog bit her "the dog" is the subject NP, "the little girl" is the topic. That toy example is perfectly parsable without semantics or even probabilities (though take any real-world sentence and I'm betting you'll need more than just grammar).
- teeja 13y agoThank you for elaborating my point. But a machine don't need an enormous library of facts to find the topic, just a small one. The words 'he', 'band', 'Liverpool' and '1958' are enough to get very precise ... but not because of their grammatical position.
- taf2 13y agohttps://github.com/taf2/rb-brill-tagger https://github.com/taf2/rb-brill-tagger. For anyone usin ruby can do something very similar much of the code is c++ with smaller ruby API ... It's pretty good bug reports welcome...
- drakaal 13y agoOr you could just drop stop words and gerunds. This is another post from "TheTokenizer" that over simplifies a complex problem and creates devistatingly bad results. The method described doesn't tell you what the sentence is about it tells you which things aren't verbs and articles and does a poor job of it. Granted single sentence keyword extraction is not easy, but this is an awful approach. You'd be much better using Word Frequency analysis to determine the rarest words in the sentence.
- swah 13y agoWhat happens when you apply it repeatedly? Does the text keep shrinking?
- visarga 13y agoJust apply TFIDF to text and it extracts the most interesting words out of the phrase - it's dead simple. You just count words and do a little scoring and sorting. Example applied to tweets. Check out how the least significant words come out last. Some words have been dropped (those with frequency less than 5 in a corpus of a few million phrases). ------ - "math final today 6-17-09 piece of cake hopefully i should do well since i m a math nerd amp english amp social" - math, nerd, studies, piece, cake, english, amp, final, hopefully, social, since, should, well, today, do, of, ------ - "anyone want an incredibly designed unique limited edition tee for the summer check out www artcotic com" - tee, designed, incredibly, unique, edition, limited, summer, anyone, check, www, want, com, an, out, for, the,
- pilooch 13y agoGood job. But I need to make the note that the title is confusing to NLP/ML practitioners. 'topics' usually refer to clusters as captured by so-called 'topic models' [1], the output of an unsupervised learning method, usually a variant of LDA. [1] http://en.wikipedia.org/wiki/Topic_model http://en.wikipedia.org/wiki/Topic_model
- kylebgorman 13y agoAs a working computational linguist I shiver anytime human language technology is discussed on HN. Smart developers (who don't work on human language) are shockingly ignorant about natural language processing. For instance, this article reinvents "chunking". People who are interested in these problems are advised to read the entire NLTK book and Jurafsky & Martin textbook before reinventing square wheels. </$.02>