New Ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures, and the Voted Perceptron

New Ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures, and the Voted Perceptron Michael Collins AT&T Labs-Research, Florham Park, New Jersey. mcollins@research.att.com Nigel Duffy iKuni Inc., 3400 Hillview Ave., Building 5, Palo Alto, CA 94304. nigeduff@cs.ucsc.edu Abstract This paper introduces new learning al- gorithms for natural language processing based on the perceptron algorithm. We show how the algorithms can be efficiently applied to exponential sized representa- tions of parse trees, such as the “all sub- trees” (DOP) representation described by (Bod 1998), or a representation tracking all sub-fragments of a tagged sentence. We give experimental results showing sig- nificant improvements on two tasks: pars- ing Wall Street Journal text, and named- entity extraction from web data. 1 Introduction The perceptron algorithm is one of the oldest algo- rithms in machine learning, going back to (Rosen- blatt 1958). It is an incredibly simple algorithm to implement, and yet it has been shown to be com- petitive with more recent learning methods such as support vector machines – see (Freund & Schapire 1999) for its application to image classification, for example. This paper describes how the perceptron and voted perceptron algorithms can be used for pars- ing and tagging problems. Crucially, the algorithms can be efficiently applied to exponential sized repre- sentations of parse trees, such as the “all subtrees” (DOP) representation described by (Bod 1998), or a representation tracking all sub-fragments of a tagged sentence. It might seem paradoxical to be able to ef- ficiently learn and apply a model with an exponential number of features.1 The key to our algorithms is the 1Although see (Goodman 1996) for an efficient algorithm for the DOP model, which we discuss in section 7 of this paper. “kernel” trick ((Cristianini and Shawe-Taylor 2000) discuss kernel methods at length). We describe how the inner product between feature vectors in these representations can be calculated efficiently using dynamic programming algorithms. This leads to polynomial time2 algorithms for training and apply- ing the perceptron. The kernels we describe are re- lated to the kernels over discrete structures in (Haus- sler 1999; Lodhi et al. 2001). A previous paper (Collins and Duffy 2001) showed improvements over a PCFG in parsing the ATIS task. In this paper we show that the method scales to far more complex domains. In parsing Wall Street Journal text, the method gives a 5.1% relative reduction in error rate over the model of (Collins 1999). In the second domain, detecting named- entity boundaries in web data, we show a 15.6% rel- ative error reduction (an improvement in F-measure from 85.3% to 87.6%) over a state-of-the-art model, a maximum-entropy tagger. This result is derived using a new kernel, for tagged sequences, described in this paper. Both results rely on a new approach that incorporates the log-probability from a baseline model, in addition to the “all-fragments” features. 2 Feature–Vector Representations of Parse Trees and Tagged Sequences This paper focuses on the task of choosing the cor- rect parse or tag sequence for a sentence …

Content truncated to 500 words