3 ms·
The off the shelf natural language parsing algorithms are polynomial time (generally n^3 or so). http://en.wikipedia.org/wiki/List_of_algorithms#Parsing http:/
by jimbokun 18y ago
The off the shelf natural language parsing algorithms are polynomial time (generally n^3 or so).
http://en.wikipedia.org/wiki/List_of_algorithms#Parsing http://en.wikipedia.org/wiki/List_of_algorithms#Parsing
In that list CYK, Earley, GLR, and Inside-Outside are taught as suitable for parsing natural languages (oversimplifying, the dividing line between parsers for computer languages and human language is that the former are deterministic and the latter spectacularly ambiguous).
So, you want to process a bunch of text, with time to parse each sentence increasing as a polynomial of the length of a sentence...I think you see where I'm going with this. Obviously, lots of people are looking for shortcuts here, but that probably means sacrificing something in accuracy, at which point you need to question whether you really want to be parsing, anyways. Last I checked, state of the art parsing accuracy is low 90s, and that's if all your sentences come from the Penn Treebank corpus.
So, when saying NLP is hard, NLP probably means parsing. You can probably describe applied NLP research as finding clever ways to answer the question you want to answer without actually parsing. Or parsing just a little bit, but not everything, you get the idea.
An interesting side question is just how do people parse natural language in real time so accurately. Or do people really parse at all, in the algorithmic sense?
- dmoney 18y ago> An interesting side question is just how do people parse natural language in real time so accurately. We have hardware support for massive neural nets:) I would guess that as we read/listen we speculatively build several different parse trees that could represent the sentence, eliminating each one when its probability (based on the implied semantics) falls too low.