A* Parsing: Fast Exact Viterbi Parse Selection

A* Parsing: Fast Exact Viterbi Parse Selection Dan Klein Computer Science Department Stanford University Stanford, CA 94305-9040 klein@cs.stanford.edu Christopher D. Manning Computer Science Department Stanford University Stanford, CA 94305-9040 manning@cs.stanford.edu Abstract We present an extension of the classic A* search procedure to tabular PCFG parsing. The use of A* search can dramatically reduce the time required to find a best parse by conservatively estimating the probabilities of parse completions. We discuss vari- ous estimates and give efficient algorithms for com- puting them. On average-length Penn treebank sen- tences, our most detailed estimate reduces the to- tal number of edges processed to less than 3% of that required by exhaustive parsing, and a simpler estimate, which requires less than a minute of pre- computation, reduces the work to less than 5%. Un- like best-first and finite-beam methods for achieving this kind of speed-up, an A* method is guaranteed to find the most likely parse, not just an approximation. Our parser, which is simpler to implement than an upward-propagating best-first parser, is correct for a wide range of parser control strategies and maintains worst-case cubic time. 1 Introduction PCFG parsing algorithms with worst-case cubic-time bounds are well-known. However, when dealing with wide-coverage grammars and long sentences, even cu- bic algorithms can be far too expensive in practice. Two primary types of methods for accelerating parse selec- tion have been proposed. Roark (2001) and Ratnaparkhi (1999) use a beam-search strategy, in which only the best n parses are tracked at any moment. Parsing time is lin- ear and can be made arbitrarily fast by reducing n. This is a greedy strategy, and the actual Viterbi (highest proba- bility) parse can be pruned from the beam because, while it is globally optimal, it may not be locally optimal at ev- ery parse stage. Chitrao and Grishman (1990), Caraballo and Charniak (1998), Charniak et al. (1998), and Collins (1999) describe best-first parsing, which is intended for a tabular item-based framework. In best-first parsing, one builds a figure-of-merit (FOM) over parser items, and uses the FOM to decide the order in which agenda items should be processed. This approach also dramat- ically reduces the work done during parsing, though it, too, gives no guarantee that the first parse returned is the actual Viterbi parse (nor does it maintain a worst-case cu- bic time bound). We discuss best-first parsing further in section 3.3. Both of these speed-up techniques are based on greedy models of parser actions. The beam search greedily prunes partial parses at each beam stage, and a best-first FOM greedily orders parse item exploration. If we wish to maintain optimality in a search procedure, the obvious thing to try is A* methods (see for example Russell and Norvig, 1995). We apply A* search to a tabular item- based parser, ordering the parse items based on a com- bination of their known internal cost of construction and a conservative estimate of their cost of completion (see figure 1). A* search has been proposed and used for …

Content truncated to 500 words