An Efficient Way to Extract the Main Topics from a Sentence • Hacker News Board

Re: An Efficient Way to Extract the Main Topics from a Sentence

#21

Post by alok-g » Thu, May 09, 2013, 4:20 PM UTC

andreasvc wrote: post #17

alok-g wrote: post #13

Earlier 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…

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.

Re: An Efficient Way to Extract the Main Topics from a Sentence

#22

Post by microtonal » Thu, May 09, 2013, 4:20 PM UTC

andreasvc wrote: post #17

alok-g wrote: post #13

Earlier 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…

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…

I have the impression that the average sentence length is more on the order of 15 words per sentence, but I might be wrong.

It highly depends on the nature of the material. But, e.g. in Dutch based on samples of newspapers I found that the average is between 16 and 20 tokens.

The grandparent mentions sentences of 100 word (I take that he means tokens). I'd guess that such sentences usually contain one or more dependent clauses, that can be parsed separately if necessary.

In practice you can use various approximation techniques, such as coarse-to-fine parsing used by the Charniak & Berkeley parsers.

Indeed, there are many possible optimizations. Such as: restricting the number of lexical analyses using a part-of-speech tagger (particularly useful in highly lexicalized grammars), guided parsing (e.g. by filtering partial left-corner splines that never lead to a good parse), and beam search.

Dependency parsers are indeed faster

Purely statistical dependency parsers are faster. There are also dependency parsers that use (rule-based) unification grammars. Such parsers can produce dependency structure as a side-effect or even post-processing step and rely on relatively expensive unification of attribute-value structures.

Re: An Efficient Way to Extract the Main Topics from a Sentence

#23

Post by teeja » Thu, May 09, 2013, 4:26 PM UTC

The 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.

Re: An Efficient Way to Extract the Main Topics from a Sentence

#24

Post by mindcrime » Thu, May 09, 2013, 4:27 PM UTC

MojoJolo wrote: post #8

For some NLP, I really suggest using OpenNLP ( 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!

I'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

[2]: http://osintegrators.com/opensoftwareintegrators|howyoucanbe...

[3]: http://fogbeam.blogspot.com/2013/05/prolog-im-going-to-learn...

Re: An Efficient Way to Extract the Main Topics from a Sentence

#25

Post by microtonal » Thu, May 09, 2013, 4:30 PM UTC

syllogism wrote: post #16

alok-g wrote: post #13

Earlier 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…

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-domain and out-of-domain:

http://dl.acm.org/citation.cfm?id=1870171

Nonetheless, I find work on statistical dependency parsing to be very exiting, since it is fast and requires far less human effort :).

https://github.com/syllog1sm/redshift/ . You'll want the develop branch. It's GPL licensed.

Very nice work!

Re: An Efficient Way to Extract the Main Topics from a Sentence

#26

Post by alok-g » Thu, May 09, 2013, 4:32 PM UTC

microtonal wrote: post #22

andreasvc wrote: post #17

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…

I have the impression that the average sentence length is more on the order of 15 words per sentence, but I might be wrong. It highly depends on the nature of the material. But, e.g. in Dutch based on samples of newspapers I found that the average is between 16 and 20 tokens. The grandparent mentions sentences of 100 word (I take that he means tokens). I'd guess that such sentences usually contain one or more depende…

>> The grandparent mentions sentences of 100 word (I take that he means tokens).

Correct. Though I have seen valid (readily human-readable) sentences even longer at 140 tokens, so the number of words too can reach or exceed 100 more frequently than commonly assumed.

>> I'd guess that such sentences usually contain one or more dependent clauses, that can be parsed separately if necessary.

Absolutely. Often more than one independent clause and several dependent clauses. But I am not aware how to identify these and parse them separately. Can you please shed some light? Are there for example some simpler grammars available that do not need to do the full parse to identify these clauses?

Re: An Efficient Way to Extract the Main Topics from a Sentence

#27

Post by microtonal » Thu, May 09, 2013, 4:34 PM UTC

mindcrime wrote: post #24

MojoJolo wrote: post #8

For some NLP, I really suggest using OpenNLP ( 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!

I'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…

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 find application in the NLP world

You missed the nicest and most satisfying book ;):

http://www.mtome.com/Publications/PNLA/pnla-digital.html

It is simultaneously an introduction to Prolog and natural language parsing using Prolog.

Re: An Efficient Way to Extract the Main Topics from a Sentence

#28

Post by mindcrime » Thu, May 09, 2013, 4:41 PM UTC

microtonal wrote: post #27

mindcrime wrote: post #24

Earlier quoted context omitted.

I'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…

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 find application in the NLP world You missed the nicest and most satisfying book ;): http://www.mtome.com/Publications/PNLA/pnla-digital.html It is simultaneously an introduction to Prolog and natural language parsing using Prolog.

Very 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!

Re: An Efficient Way to Extract the Main Topics from a Sentence

#29

Post by microtonal » Thu, May 09, 2013, 4:44 PM UTC

alok-g wrote: post #26

microtonal wrote: post #22

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. It highly depends on the nature of the material. But, e.g. in Dutch based on samples of newspapers I found that the average is between 16 and 20 tokens. The grandparent mentions sentences of 100 word (I take that he means tokens). I'd guess that such sentences usually contain one or more depende…

>> The grandparent mentions sentences of 100 word (I take that he means tokens). Correct. Though I have seen valid (readily human-readable) sentences even longer at 140 tokens, so the number of words too can reach or exceed 100 more frequently than commonly assumed. >> I'd guess that such sentences usually contain one or more dependent clauses, that can be parsed separately if necessary. Absolutely. Often more than o…

I haven't tried such a thing (yet), but there is some work in that area. Advaith Siddhartan's thesis may be a good start:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.8...

Re: An Efficient Way to Extract the Main Topics from a Sentence

#30

Post by mindcrime » Thu, May 09, 2013, 4:47 PM UTC

tannerc wrote: post #19

Arjuna wrote: post #9

This 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…

Why 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.

What'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.