Statistical Decision-Tree Models for Parsing

Statistical Decision-Tree Models for Parsing* David M. Magerman Bolt Beranek and Newman Inc. 70 Fawcett Street, Room 15/148 Cambridge, MA 02138, USA magerman@bbn, com Abstract Syntactic natural language parsers have shown themselves to be inadequate for pro- cessing highly-ambiguous large-vocabulary text, as is evidenced by their poor per- formance on domains like the Wall Street Journal, and by the movement away from parsing-based approaches to text- processing in general. In this paper, I de- scribe SPATTER, a statistical parser based on decision-tree learning techniques which constructs a complete parse for every sen- tence and achieves accuracy rates far bet- ter than any published result. This work is based on the following premises: (1) grammars are too complex and detailed to develop manually for most interesting do- mains; (2) parsing models must rely heav- ily on lexical and contextual information to analyze sentences accurately; and (3) existing n-gram modeling techniques are inadequate for parsing models. In exper- iments comparing SPATTER with IBM's computer manuals parser, SPATTER sig- nificantly outperforms the grammar-based parser. Evaluating SPATTER against the Penn Treebank Wall Street Journal corpus using the PARSEVAL measures, SPAT- TER achieves 86% precision, 86% recall, and 1.3 crossing brackets per sentence for sentences of 40 words or less, and 91% pre- cision, 90% recall, and 0.5 crossing brackets for sentences between 10 and 20 words in length. This work was sponsored by the Advanced Research Projects Agency, contract DABT63-94-C-0062. It does not reflect the position or the policy of the U.S. Gov- ernment, and no official endorsement should be inferred. Thanks to the members of the IBM Speech Recognition Group for their significant contributions to this work. 1 Introduction Parsing a natural language sentence can be viewed as making a sequence of disambiguation decisions: de- termining the part-of-speech of the words, choosing between possible constituent structures, and select- ing labels for the constituents. Traditionally, disam- biguation problems in parsing have been addressed by enumerating possibilities and explicitly declaring knowledge which might aid the disambiguation pro- cess. However, these approaches have proved too brittle for most interesting natural language prob- lems. This work addresses the problem of automatically discovering the disambiguation criteria for all of the decisions made during the parsing process, given the set of possible features which can act as disambigua- tors. The candidate disambiguators are the words in the sentence, relationships among the words, and re- lationships among constituents already constructed in the parsing process. Since most natural language rules are not abso- lute, the disambiguation criteria discovered in this work are never applied deterministically. Instead, all decisions are pursued non-deterministically accord- ing to the probability of each choice. These proba- bilities are estimated using statistical decision tree models. The probability of a complete parse tree (T) of a sentence (S) is the product of each decision (dl) conditioned on all previous decisions: P(T[S) = H P(dildi-ldi-2""dlS)" diET Each decision sequence constructs a unique parse, and the parser selects the parse whose decision se- quence yields the highest cumulative probability. By …

Content truncated to 500 words