Inducing History Representations for Broad Coverage Statistical Parsing

Inducing History Representations for Broad Coverage Statistical Parsing James Henderson Department of Computer Science, University of Geneva, Gen`eve, Switzerland James.Henderson@cui.unige.ch Abstract We present a neural network method for induc- ing representations of parse histories and us- ing these history representations to estimate the probabilities needed by a statistical left-corner parser. The resulting statistical parser achieves performance (89.1% F-measure) on the Penn Treebank which is only 0.6% below the best current parser for this task, despite using a smaller vocabulary size and less prior linguistic knowledge. Crucial to this success is the use of structurally determined soft biases in inducing the representation of the parse history, and no use of hard independence assumptions. 1 Introduction Unlike most problems addressed with machine learning, parsing natural language sentences requires choosing be- tween an unbounded (or even infinite) number of possi- ble phrase structure trees. The standard approach to this problem is to decompose this choice into an unbounded sequence of choices between a finite number of possible parser actions. This sequence is the parse for the phrase structure tree. We can then define a probabilistic model of phrase structure trees by defining a probabilistic model of each parser action in its parse context, and apply machine learning techniques to learn this model of parser actions. Many statistical parsers (Ratnaparkhi, 1999; Collins, 1999; Charniak, 2000) are based on a history-based model of parser actions. In these models, the probabil- ity of each parser action is conditioned on the history of previous actions in the parse. But here again we are faced with an unusual situation for machine learning problems, conditioning on an unbounded amount of information. A major challenge in designing a history-based statisti- cal parser is choosing a finite representation of the un- bounded parse history from which the probability of the next parser action can be accurately estimated. Previ- ous approaches have used a hand-crafted finite set of fea- tures to represent the parse history (Ratnaparkhi, 1999; Collins, 1999; Charniak, 2000). In the work presented here, we automatically induce a finite set of real valued features to represent the parse history. We perform the induction of a history representation using an artificial neural network architecture, called Simple Synchrony Networks (SSNs) (Lane and Hen- derson, 2001; Henderson, 2000). This machine learn- ing method is specifically designed for processing un- bounded structures. It allows us to avoid making a priori independence assumptions, unlike with hand-crafted his- tory features. But it also allows us to make use of our a priori knowledge by imposing structurally specified and linguistically appropriate biases on the search for a good history representation. The combination of automatic feature induction and linguistically appropriate biases results in a history-based parser with state-of-the-art performance. When trained on just part-of-speech tags, the resulting parser achieves the best current performance of a non-lexicalized parser on the Penn Treebank. When a relatively small vocab- ulary of words is used, performance is only marginally below the best current parser accuracy. If either the bi- ases are reduced …

Content truncated to 500 words