Efficiency, Robustness and Accuracy in picky Chart Parsing

Efficiency, Robustness and Accuracy in Picky Chart David M. Magerman Stanford University Stanford, CA 94305 magerman@cs.st anford.edu Parsing* Carl Weir Paramax Systems Paoli, PA 19301 weir@prc.unisys.com ABSTRACT This paper describes Picky, a probabilistic agenda-based chart parsing algorithm which uses a technique called p~'ob- abilistic prediction to predict which grammar rules are likely to lead to an acceptable parse of the input. Using a subopti- mal search method, "Picky significantly reduces the number of edges produced by CKY-like chart parsing algorithms, while maintaining the robustness of pure bottom-up parsers and the accuracy of existing probabilistic parsers. Experiments using Picky demonstrate how probabilistic modelling can im- pact upon the efficiency, robustness and accuracy of a parser. 1. Introduction This paper addresses the question: Why should we use probabilistic models in natural language understanding? There are many answers to this question, only a few of which are regularly addressed in the literature. The first and most common answer concerns ambigu~ ity resolution. A probabilistic model provides a clearly defined preference nile for selecting among grammati- cal alternatives (i.e. the highest probability interpreta- tion is selected). However, this use of probabilistic mod- els assumes that we already have efficient methods for generating the alternatives in the first place. While we have O(n 3) algorithms for determining the grammatical- ity of a sentence, parsing, as a component of a natural language understanding tool, involves more than simply determining all of the grammatical interpretations of an input. Ill order for a natural language system to process input efficiently and robustly, it must process all intelligi- ble sentences, grammatical or not, while not significantly reducing the system's efficiency. This observ~ttiou suggests two other answers to the cen- tral question of this paper. Probabilistic models offer a convenient scoring method for partial interpretations in a well-formed substring table. High probability con- stituents in the parser's chart call be used to interpret ungrammat.ical sentences. Probabilistic models can also *Special I.hanks to Jerry Hobbs and F3ob Moo*re at S[II for providing access to their colllptllel's, and to Salim ]-/oukos, Pe- l:er Brown, and Vincent and Steven Della Piel.ra ,-xt IF3M for their inst.ructive lessons on probabi|isti,: modelling of natural I:mguage. be used for efficiency by providing a best-first search heuristic to order the parsing agenda. This paper proposes an agenda-based probabilistic chart parsing algorithm which is both robust and efficient. The algorithm, 7)icky 1, is considered robust because it will potentially generate all constituents produced by a pure bottom-up parser and rank these constituents by likeli- hood. The efficiency of the algorithm is achieved through a technique called probabilistic prediction, which helps the algorithm avoid worst-case behavior. Probabilistic prediction is a trainable technique for modelling where edges are likely to occur in the chart-parsing process. 2 Once the predicted edges are added to the chart using probabilistic prediction, they are processed in a style similar to agenda-based chart parsing algorithms. By limiting the edges in the chart to those which are pre- dicted by this model, the parser can process …

Content truncated to 500 words