Statistical parsing

Statistical parsing is a group of parsing methods within natural language processing. The methods have in common that they associate grammar rules with a probability. Grammar rules are traditionally viewed in computational linguistics as defining the valid sentences in a language. Within this mindset, the idea of associating each rule with a probability then provides the relative frequency of any given grammar rule and, by deduction, the probability of a complete parse for a sentence. (The probability associated with a grammar rule may be induced, but the application of that grammar rule within a parse tree and the computation of the probability of the parse tree based on its component rules is a form of deduction.) Using this concept, statistical parsers make use of a procedure to search over a space of all candidate parses, and the computation of each candidate's probability, to derive the most probable parse of a sentence. The expectation maximization algorithm is one popular method of searching for the most probable parse.

"Search" in this context is an application of the very useful search algorithm in artificial intelligence.

By way of example, think about the sentence "The can can hold water." A reader would instantly see that there is an object called "The can" and that this object is performing the action 'can' (i.e. is able to); and the thing the object is able to do is "hold"; and the thing the object is able to hold is "water". Using more linguistic terminology, "The can" is a noun phrase composed of a determiner followed by a noun, and "can hold water" is a verb phrase which is itself composed of a verb followed by a verb phrase. But is this the only interpretation of the sentence? Certainly "The can can" is a perfectly valid noun-phrase referring to a type of dance, and "hold water" is also a valid verb-phrase, although the coerced meaning of the combined sentence is non-obvious. This lack of meaning is not seen as a problem by most linguists (for a discussion on this point, see Colorless green ideas sleep furiously) but from a pragmatic point of view it is desirable to obtain the first interpretation rather than the second and statistical parsers achieve this by ranking the interpretations based on their probability.

(In this example I have made various assumptions about the grammar, such as a simple left-to-right derivation rather than head-driven, its use of noun-phrases rather than the currently fashionable determiner-phrases, and no type-check preventing a concrete noun being combined with an abstract verb phrase. None of these assumptions affect the thesis of my argument and a comparable argument can be made using any other grammatical formalism.)

There are a number of methods that statistical parsing algorithms frequently use. While few algorithms will use all of these they give a good overview of the general field. Most statistical parsing algorithms are based on a modified form of chart parsing. The modifications are necessary to support an extremely large number of grammatical rules and therefore search space, and essentially involve applying classical artificial intelligence algorithms to the traditionally exhaustive search. Some examples of the optimisations are only searching a likely subset of the search space (stack search), for optimising the search probability (Baum-Welch algorithm) and for discarding parses that are too similar to be treated separately (Viterbi algorithm).

Notable people in statistical parsing

* Eugene Charniak Author of Statistical techniques for natural language parsing [http://www.cs.brown.edu/people/ec/home.html] amongst many other contributions
* Fred Jelinek Applied and developed numerous techniques from Information Theory to build the field [http://www.clsp.jhu.edu/people/jelinek/]
* David Magerman Major contributor to turning the field from theoretical to practical by managing data [http://www-cs-students.stanford.edu/~magerman/]
* James Curran Applying the MaxEnt alogrithm, word representation, and other contributions [http://www.it.usyd.edu.au/about/people/staff/james.shtml]
* Michael Collins (computational linguist) First very high performance statistical parser [http://people.csail.mit.edu/mcollins/]
* Joshua Goodman Hypergraphs, and other generalizations between different methods [http://research.microsoft.com/~joshuago/]

ee also

*Stochastic context-free grammar