UMIACS Computational Linguistics Colloquium

April 29, 1998, 4pm, AVW Room 4406

We consider the use of context-free grammars (CFGs) for parsing (assigning syntactic structure to) English sentences. There are well-known CFG parsing algorithms that can parse in n-cubed time, where n is the length of the sentence. Unfortunately, this is not nearly efficient enough when dealing with large grammars and longish sentences. In this talk we describe some new techniques devised by a group of us at Brown for dramatically reducing the amount of work necessary to find a parse for a sentence using a probabilistic CFG (a CFG in which each rule is assigned a probability). The key idea is to use the probabilistic information to order the parsing steps so as to guide the parser toward a parse without most of the usual hunting and pecking. We describe three such parsers, each using more information and achieving correspondingly better results than the last.

For the colloquium series schedule, see the UMD Computational Linguistics Colloquium Series web page at http://umiacs.umd.edu/~resnik/cl_colloquium/. If you are interested in meeting with the speaker, please contact Mari Broman Olsen (molsen@umiacs.umd.edu) or Philip Resnik (resnik@umiacs.umd.edu).