A Linear Observed Time Statistical Parser Based on Maximum Entropy Models

A. Linear Observed Time Statistical Parser Based on Maximum Entropy Models Adwait Ratnaparkhi* Dept. of Computer and Information Science University of Pennsylvania 200 South 33rd Street Philadelphia, PA 19104-6389 adwait~unagi, cis. upenn, edu Abstract This paper presents a statistical parser for natural language that obtains a parsing accuracy--roughly 87% precision and 86% recall--which surpasses the best previously published results on the Wall St. Journal domain. The parser itself requires very lit- tle human intervention, since the informa- tion it uses to make parsing decisions is specified in a concise and simple manner, and is combined in a fully automatic way under the maximum entropy framework. The observed running time of the parser on a test sentence is linear with respect to the sentence length. Furthermore, the parser returns several scored parses for a sentence, and this paper shows that a scheme to pick the best parse from the 20 highest scoring parses could yield a dramatically higher ac- curacy of 93% precision and recall. 1 Introduction This paper presents a statistical parser for natural language that finds one or more scored syntactic parse trees for a given input sentence. The parsing accuracy--roughly 87% precision and 86% recall-- surpasses the best previously published results on the Wall St. Journal domain. The parser consists of the following three conceptually distinct parts: 1. h set of procedures that use certain actions to incrementally construct parse trees. 2. A set of maximum entropy models that com- pute probabilities of the above actions, and ef- fectively "score" parse trees. * The author acknowledges the support of AI:tPA grant N66001-94C-6043. 3. A search heuristic which attempts to find the highest scoring parse tree for a given input sen- tence. The maximum entropy models used here are simi- lar in form to those in (Ratnaparkhi, 1996; Berger, Della Pietra, and Della Pietra, 1996; Lau, Rosen- feld, and Roukos, 1993). The models compute the probabilities of actions based on certain syntactic characteristics, or features, of the current context. The features used here are defined in a concise and simple manner, and their relative importance is de- termined automatically by applying a training pro- cedure on a corpus of syntactically annotated sen- tences, such as the Penn Treebank (Marcus, San- torini, and Marcinkiewicz, 1994). Although creat- ing the annotated corpus requires much linguistic expertise, creating the feature set for the parser it- self requires very little linguistic effort. Also, the search heuristic is very simple, and its observed running time on a test sentence is linear with respect to the sentence length. Furthermore, the search heuristic returns several scored parses for -a sentence, and this paper shows that a scheme to pick the best parse from the 20 highest scoring parses could yield a dramatically higher accuracy of 93% precision and recall. Sections 2, 3, and 4 describe the tree-building procedures, the maximum entropy models, and the search heuristic, respectively. Section 5 describes experiments with the Penn Treebank and section 6 compares this paper with previously published works. 2 …

Content truncated to 500 words