Probabilistic Prediction and Picky Chart Parsing

Probabilistic Prediction and Picky Chart Parsing* David M. Magerman Stanford University magerman@cs.stanford.edu Carl Weir Paramax Systems weir@prc.unisys.com ABSTRACT This paper describes Picky, a probabilistic agenda-based chart parsing algorithm which uses a technique called prob- abilistic prediction to predict which grammar rules are likely to lead to an acceptable parse of the input. In tests on ran- domly selected test data, "Picky generates fewer edges on av- erage than other CKY-like algorithms, while achieving 89~ first parse accuracy and also enabling the parser to process sentences with false starts and other minor disfluencies. Fur- ther, sentences which are parsed completely by the proba- bilistic prediction technique have a 97~0 first parse accuracy. 1. Introduction Two important concerns in natural language parsing which encourage the use of probabilistic analysis are ef- ficiency and accuracy. An accurate parser which has a domain or language model so detailed that it takes hours to process a single sentence, while perhaps interesting, is no more useful than a simple instantaneous parser which is always wrong. Probabilistic modelling of the grammar of a language has been proposed as a potential solution to the accuracy problem, disambiguating grammatical parses generated by an ambiguous grammar. However, little attention has been paid to the repercussions of probabilistic parsing on the computational complexity and average-case performance of existing parsing algo- rithms. Effective probabilistic models of grammar which take into account contextual information (e. g. [10] [2]) cannot take advantage of the O(n 3) behavior of CKY-like parsing algorithms. If they are to use existing grammat- ical formalisms, these models must use algorithms that are worst-case exponential. When natural language parsers are incorporated into natural language understanding systems, another sig- nificant issue arises: robustness. As a component of a language processing system, a parser's task is to an- alyze correctly all inputs which can be understood by the system, not just those which are precisely grammat- ical. Or, one might say, the grammar of natural lan- *Special thanks to Jerry Hobbs and Bob Moore at SRI for providing access to their computers, and to Salim Roukos, Pe- ter Brown, and Vincent and Steven Della Pietra at IBM for their instructive lessons on probabillstic modelling of natural language. guage includes fragments, run-ons, split infinitives, and other disfluencies which would receive red marks on a high school English paper. At the same time, meaning- less sequences of words and other uninterpretable inputs should nol be analyzed as though they are acceptable. Robust processing of natural language is an ideal appli- cation of probabilistic methods, since probability theory provides a well-behaved measure of expectation within a given language. This paper proposes an agenda-based probabilistic chart parsing algorithm which is both robust and efficient. The algorithm, Picky 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 …

Content truncated to 500 words