Earlier quoted context omitted.
I have the impression that the average sentence length is more on the order of 15 words per sentence, but I might be wrong. The cubic time complexity is for exhaustively finding the best parse. In practice you can use various approximation techniques, such as coarse-to-fine parsing used by the Charniak & Berkeley parsers. I believe these two are faster than the Stanford Parser, and the parameters of the approximation…
Thanks! Here is a study on average sentence length showing it at 24 words per sentence: http://ds.nahoo.net/Academic/Maths/Sentence.html In my own study, I performed analysis on a corpus of a few hundred million sentences of written text and found it at 31 words per sentence. It would be great if you can point to the use of GPU for parsing. I had never heard of the bitpar parser, will look into it.
An Efficient Way to Extract the Main Topics from a Sentence
31–40 of 78 posts
Re: An Efficient Way to Extract the Main Topics from a Sentence
#32The sentence subject is one thing, the sentence topic 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.
The 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.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#33Earlier quoted context omitted.
The 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…
Accuracy is state-of-the-art -- 92-93% depending on the beam width and the evaluation set (Stanford or MALT dependencies). I assume that this is for English? A former colleague of mine compared two statistical dependency parsers (Malt and MST) to a rule-based dependency parser with a maxent disambiguation model, for Dutch. The rule-based system outperforms the statistical dependency parsers by a wide margin, both in-…
Yes, for English. There's a standard multi-lingual evaluation for statistical dependency parsers (the CoNLL 2007 data), but none for constituency parsers.
I had a look at that paper, but didn't read it carefully. All I can really say is that there's a real evaluation problem between rule-based and statistical parsers. Rule-based parsers recover richer representations, but tend to have lower coverage over arbitrary data --- they normally can't guarantee that a parse is returned; they may deem the sentence ungrammatical.
In that paper, the parsers were evaluated on "home ground" for the rule-based parser, as they used the treebank created for it. Having worked on the CCG formalism through my PhD, I can say that even small differences in annotation scheme can make a big difference in which parsers come out ahead.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#34Nice 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…
Re: your first point.
In English, the first noun is almost always the actor of the verb, with subsequent nouns being acted upon. This isn't true for other languages though.
(I'm sure someone will come up with an exception to that rule but for 90% of the cases this is true).
Re: An Efficient Way to Extract the Main Topics from a Sentence
#35Without 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 Maybe later I'll give it a crack :)
Wordnet & the Brill Pos tagged corpus do the trick, more or less
Re: An Efficient Way to Extract the Main Topics from a Sentence
#36Nice 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…
Re: your first point. In English, the first noun is almost always the actor of the verb, with subsequent nouns being acted upon. This isn't true for other languages though. (I'm sure someone will come up with an exception to that rule but for 90% of the cases this is true).
Except in passive constructions, but maybe that's an easy case to detect.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#37https://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...
Re: An Efficient Way to Extract the Main Topics from a Sentence
#38The sentence subject is one thing, the sentence topic 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.
Ask anyone under ~30, they won't know what you're talking about.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#39This 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.
This 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.
But 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]
Re: An Efficient Way to Extract the Main Topics from a Sentence
#40Earlier quoted context omitted.
My 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…
The 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…
The Stanford parser is particularly slow --- it's in java, and it's written for research more than anything.
The choice of language is not what causes the slowness of the Stanford parser. It's the choice of search strategy, which trades-off speed for accuracy.
Shift-reduce dependency parsers are linear time, and are giving state-of-the-art results.
No, this is incorrect.
The choice of parsing logic (shift-reduce, dependency) and the search strategy (greedy, sometimes erroneously called "deterministic") are orthogonal. It's the greedy search strategy that leads to linear time performance.
The choice of logic determines the lower-bound (best-case) on parsing complexity. If you do exhaustive search for the exact solution of a shift-reduce dependency parser, it is worst-case exponential. In practice, you don't do exact search, and by using a beam search approximation you can get observed linear-time performance.
[edit: You can read my thesis if you are not familiar with what a parsing logic is.]
I am not aware of state-of-the-art results from greedy shift-reduce parsers. Do you mind sharing?