TAG, Dynamic Programming, and the Perceptron for Efficient, Feature-Rich Parsing

CoNLL 2008: Proceedings of the 12th Conference on Computational Natural Language Learning, pages 9–16 Manchester, August 2008 TAG, Dynamic Programming, and the Perceptron for Efficient, Feature-rich Parsing Xavier Carreras Michael Collins Terry Koo MIT CSAIL, Cambridge, MA 02139, USA {carreras,mcollins,maestro}@csail.mit.edu Abstract We describe a parsing approach that makes use of the perceptron algorithm, in conjunction with dynamic programming methods, to recover full constituent-based parse trees. The formalism allows a rich set of parse-tree features, including PCFG- based features, bigram and trigram dependency fea- tures, and surface features. A severe challenge in applying such an approach to full syntactic pars- ing is the efficiency of the parsing algorithms in- volved. We show that efficient training is feasi- ble, using a Tree Adjoining Grammar (TAG) based parsing formalism. A lower-order dependency pars- ing model is used to restrict the search space of the full model, thereby making it efficient. Experiments on the Penn WSJ treebank show that the model achieves state-of-the-art performance, for both con- stituent and dependency accuracy. 1 Introduction In global linear models (GLMs) for structured pre- diction, (e.g., (Johnson et al., 1999; Lafferty et al., 2001; Collins, 2002; Altun et al., 2003; Taskar et al., 2004)), the optimal label y∗ for an input x is y∗ = arg max y∈Y(x) w · f(x, y) (1) where Y(x) is the set of possible labels for the in- put x; f(x, y) ∈ Rd is a feature vector that rep- resents the pair (x, y); and w is a parameter vec- tor. This paper describes a GLM for natural lan- guage parsing, trained using the averaged percep- tron. The parser we describe recovers full syntac- tic representations, similar to those derived by a probabilistic context-free grammar (PCFG). A key motivation for the use of GLMs in parsing is that they allow a great deal of flexibility in the features which can be included in the definition of f(x, y). c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. A critical problem when training a GLM for parsing is the computational complexity of the inference problem. The averaged perceptron re- quires the training set to be repeatedly decoded under the model; under even a simple PCFG rep- resentation, finding the arg max in Eq. 1 requires O(n3G) time, where n is the length of the sen- tence, and G is a grammar constant. The average sentence length in the data set we use (the Penn WSJ treebank) is over 23 words; the grammar con- stant G can easily take a value of 1000 or greater. These factors make exact inference algorithms vir- tually intractable for training or decoding GLMs for full syntactic parsing. As a result, in spite of the potential advantages of these methods, there has been very little previ- ous work on applying GLMs for full parsing with- out the use of fairly severe restrictions or approxi- mations. For example, the model in (Taskar et al., 2004) is trained on only sentences …

Content truncated to 500 words