Incremental Parsing with the Perceptron Algorithm

Incremental Parsing with the Perceptron Algorithm Michael Collins MIT CSAIL mcollins@csail.mit.edu Brian Roark AT&T Labs - Research roark@research.att.com Abstract This paper describes an incremental parsing approach where parameters are estimated using a variant of the perceptron algorithm. A beam-search algorithm is used during both training and decoding phases of the method. The perceptron approach was implemented with the same feature set as that of an existing generative model (Roark, 2001a), and experimental results show that it gives competitive performance to the generative model on parsing the Penn treebank. We demonstrate that train- ing a perceptron model to combine with the generative model during search provides a 2.1 percent F-measure improvement over the generative model alone, to 88.8 percent. 1 Introduction In statistical approaches to NLP problems such as tag- ging or parsing, it seems clear that the representation used as input to a learning algorithm is central to the ac- curacy of an approach. In an ideal world, the designer of a parser or tagger would be free to choose any fea- tures which might be useful in discriminating good from bad structures, without concerns about how the features interact with the problems of training (parameter estima- tion) or decoding (search for the most plausible candidate under the model). To this end, a number of recently pro- posed methods allow a model to incorporate “arbitrary” global features of candidate analyses or parses. Exam- ples of such techniques are Markov Random Fields (Rat- naparkhi et al., 1994; Abney, 1997; Della Pietra et al., 1997; Johnson et al., 1999), and boosting or perceptron approaches to reranking (Freund et al., 1998; Collins, 2000; Collins and Duffy, 2002). A drawback of these approaches is that in the general case, they can require exhaustive enumeration of the set of candidates for each input sentence in both the train- ing and decoding phases1. For example, Johnson et al. (1999) and Riezler et al. (2002) use all parses generated by an LFG parser as input to an MRF approach – given the level of ambiguity in natural language, this set can presumably become extremely large. Collins (2000) and Collins and Duffy (2002) rerank the top N parses from an existing generative parser, but this kind of approach 1Dynamic programming methods (Geman and Johnson, 2002; Laf- ferty et al., 2001) can sometimes be used for both training and decod- ing, but this requires fairly strong restrictions on the features in the model. presupposes that there is an existing baseline model with reasonable performance. Many of these baseline models are themselves used with heuristic search techniques, so that the potential gain through the use of discriminative re-ranking techniques is further dependent on effective search. This paper explores an alternative approach to pars- ing, based on the perceptron training algorithm intro- duced in Collins (2002). In this approach the training and decoding problems are very closely related – the training method decodes training examples in sequence, and makes simple corrective updates to the parameters when errors are made. Thus the …

Content truncated to 500 words