Ranking Algorithms for Named Entity Extraction: Boosting and the VotedPerceptron

Ranking Algorithms for Named–Entity Extraction: Boosting and the Voted Perceptron Michael Collins AT&T Labs-Research, Florham Park, New Jersey. mcollins@research.att.com Abstract This paper describes algorithms which rerank the top N hypotheses from a maximum-entropy tagger, the applica- tion being the recovery of named-entity boundaries in a corpus of web data. The first approach uses a boosting algorithm for ranking problems. The second ap- proach uses the voted perceptron algo- rithm. Both algorithms give compara- ble, significant improvements over the maximum-entropy baseline. The voted perceptron algorithm can be considerably more efficient to train, at some cost in computation on test examples. 1 Introduction Recent work in statistical approaches to parsing and tagging has begun to consider methods which in- corporate global features of candidate structures. Examples of such techniques are Markov Random Fields (Abney 1997; Della Pietra et al. 1997; John- son et al. 1999), and boosting algorithms (Freund et al. 1998; Collins 2000; Walker et al. 2001). One appeal of these methods is their flexibility in incor- porating features into a model: essentially any fea- tures which might be useful in discriminating good from bad structures can be included. A second ap- peal of these methods is that their training criterion is often discriminative, attempting to explicitly push the score or probability of the correct structure for each training sentence above the score of competing structures. This discriminative property is shared by the methods of (Johnson et al. 1999; Collins 2000), and also the Conditional Random Field methods of (Lafferty et al. 2001). In a previous paper (Collins 2000), a boosting al- gorithm was used to rerank the output from an ex- isting statistical parser, giving significant improve- ments in parsing accuracy on Wall Street Journal data. Similar boosting algorithms have been applied to natural language generation, with good results, in (Walker et al. 2001). In this paper we apply rerank- ing methods to named-entity extraction. A state-of- the-art (maximum-entropy) tagger is used to gener- ate 20 possible segmentations for each input sen- tence, along with their probabilities. We describe a number of additional global features of these can- didate segmentations. These additional features are used as evidence in reranking the hypotheses from the max-ent tagger. We describe two learning algo- rithms: the boosting method of (Collins 2000), and a variant of the voted perceptron algorithm, which was initially described in (Freund & Schapire 1999). We applied the methods to a corpus of over one million words of tagged web data. The methods give signif- icant improvements over the maximum-entropy tag- ger (a 17.7% relative reduction in error-rate for the voted perceptron, and a 15.6% relative improvement for the boosting method). One contribution of this paper is to show that ex- isting reranking methods are useful for a new do- main, named-entity tagging, and to suggest global features which give improvements on this task. We should stress that another contribution is to show that a new algorithm, the voted perceptron, gives very credible results on a natural language task. It is …

Content truncated to 500 words