Multilevel Coarse-to-Fine PCFG Parsing

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 168–175, New York, June 2006. c⃝2006 Association for Computational Linguistics Multilevel Coarse-to-fine PCFG Parsing Eugene Charniak, Mark Johnson, Micha Elsner, Joseph Austerweil, David Ellis, Isaac Haxton, Catherine Hill, R. Shrivaths, Jeremy Moore, Michael Pozar, and Theresa Vu Brown Laboratory for Linguistic Information Processing (BLLIP) Brown University Providence, RI 02912 ec@cs.brown.edu Abstract We present a PCFG parsing algorithm that uses a multilevel coarse-to-fine (mlctf) scheme to improve the effi- ciency of search for the best parse. Our approach requires the user to spec- ify a sequence of nested partitions or equivalence classes of the PCFG non- terminals. We define a sequence of PCFGs corresponding to each parti- tion, where the nonterminals of each PCFG are clusters of nonterminals of the original source PCFG. We use the results of parsing at a coarser level (i.e., grammar defined in terms of a coarser partition) to prune the next finer level. We present experiments showing that with our algorithm the work load (as measured by the total number of constituents processed) is decreased by a factor of ten with no de- crease in parsing accuracy compared to standard CKY parsing with the origi- nal PCFG. We suggest that the search space over mlctf algorithms is almost totally unexplored so that future work should be able to improve significantly on these results. 1 Introduction Reasonably accurate constituent-based parsing is fairly quick these days, if fairly quick means about a second per sentence. Unfortunately, this is still too slow for many applications. In some cases researchers need large quantities of parsed data and do not have the hundreds of machines necessary to parse gigaword corpora in a week or two. More pressingly, in real-time applica- tions such as speech recognition, a parser would be only a part of a much larger system, and the system builders are not keen on giving the parser one of the ten seconds available to pro- cess, say, a thirty-word sentence. Even worse, some applications require the parsing of multi- ple candidate strings per sentence (Johnson and Charniak, 2004) or parsing from a lattice (Hall and Johnson, 2004), and in these applications parsing efficiency is even more important. We present here a multilevel coarse-to-fine (mlctf) PCFG parsing algorithm that reduces the complexity of the search involved in find- ing the best parse. It defines a sequence of in- creasingly more complex PCFGs, and uses the parse forest produced by one PCFG to prune the search of the next more complex PCFG. We currently use four levels of grammars in our mlctf algorithm. The simplest PCFG, which we call the level-0 grammar, contains only one non- trivial nonterminal and is so simple that min- imal time is needed to parse a sentence using it. Nonetheless, we demonstrate that it identi- fies the locations of correct constituents of the parse tree (the “gold constituents”) with high recall. Our level-1 grammar distinguishes only argument from modifier phrases (i.e., …

Content truncated to 500 words