I smell a $30 million acquisition in the near future..
An Efficient Way to Extract the Main Topics from a Sentence
11–20 of 78 posts
Re: An Efficient Way to Extract the Main Topics from a Sentence
#12I smell a $30 million acquisition in the near future..
By those standards, many companies will be worth billions ;).
(Chunking is not exactly new and PCFG parsing is pretty fast these days.)
Re: An Efficient Way to Extract the Main Topics from a Sentence
#13Nice 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…
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 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.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#14This 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.
Nah, 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.
Huh? "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?
Re: An Efficient Way to Extract the Main Topics from a Sentence
#15Earlier quoted context omitted.
Nah, 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.
Huh? "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?
Google Analytics has nothing whatsoever to do with online content.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#16Nice 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…
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 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/ . 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 . 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.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#17Nice 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…
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 can be tuned to have faster parsing at the expense of accuracy. You could probably get a reasonable parse tree for a sentence in one second. The fastest PCFG parser which does not do such approximations is bitpar. Another avenue is to try to use the GPU; there has been some research into this.
Dependency parsers are indeed faster but in general their accuracy cannot be compared to constituency parsers, because the information in the output is of a different nature.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#18Earlier quoted context omitted.
Huh? "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?
Google Analytics has nothing whatsoever to do with online content.
You'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
Re: An Efficient Way to Extract the Main Topics from a Sentence
#19This 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.
Re: An Efficient Way to Extract the Main Topics from a Sentence
#20This 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.