Ranking Algorithms for Named Entity Extraction: Boosting and the VotedPerceptron

By Michael Collins. Annual Meeting of the Association for Computational Linguistics, 2002

301 citations recorded by the source corpus.

This paper describes algorithms which rerank the top N hypotheses from a maximum-entropy tagger, the application 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 approach uses the voted perceptron algorithm. Both algorithms give comparable, 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.

Subfields: Artificial Intelligence, Information Systems

View Paper: https://www.semanticscholar.org/paper/39fb0b6873c58ec182357721eaed75801505a9df

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms (2002, background): “See (Collins and Du y 2001; Collins and Du y 2002; Collins 2002) for other applications of the voted perceptron to NLP problems.1”
Semi-Supervised Learning for Natural Language (2005, methodology): “We train our models using the Averaged Perceptron algorithm, which is simple to use and provides theoretical guarantees (Collins, 2002a).”
LETOR: Benchmark Dataset for Research on Learning to Rank for Information Retrieval (2007, methodology): “These include document retrieval [3], collaborative filtering [14], key term extraction [8], definition finding [32], important email routing [4], sentiment analysis [26], product rating [9], and anti web spam [13].”
Discriminative Reranking for Semantic Parsing (2006, methodology): “While reranking has benefited many tagging and parsing tasks (Collins, 2000; Collins, 2002c; Charniak and Johnson, 2005) including semantic role labeling (Toutanova et al.”
Distributed Asynchronous Online Learning for Natural Language Processing (2010, methodology): “Our NER CRF used a standard set of features, following Kazama and Torisawa (2007), along with token shape features like those in Collins (2002) and simple gazetteer features; a feature was included if and only it occurred at least once in training data (total 1.3M).”
Learning to rank for information retrieval (2009, unknown): “Many IR problems are by nature ranking problems, such as document retrieval, collaborative filtering [58], key term extraction [30], definition finding [130], important email routing [23], sentiment analysis [94], product rating [36], and anti Web spam [56].”
LETOR: A benchmark collection for research on learning to rank for information retrieval (2010, methodology): “These include document retrieval (Cao et al. 2006), collaborative filtering (Harrington 2003), key term extraction (Collins 2002), definition finding (Xu et al. 2005), important email routing (Chirita et al. 2005), sentiment analysis (Pang et al. 2005), product rating (Dave et al. 2003), and anti…”
Discriminative Reranking for Natural Language Parsing (2000, methodology): “See Collins (2002a) for an application of the boosting approach to named entity recognition, and Walker, Rambow, and Rogati (2001) for the application of boosting techniques for ranking in the context of natural language generation.”
Biomedical Named Entity Recognition using Conditional Random Fields and Rich Feature Sets (2004, unknown): “Words are also assigned a generalized “word class” similar to Collins (2002), which replaces capital letters with ‘A’, lowercase letters with ‘a’, digits with ‘0’, and all other characters with ‘ ’.”
Comparative experiments on learning information extractors for proteins and their interactions (2005, background): “The word class features cf and cb are based on the similar features introduced in [40].”
Softmax-Margin CRFs: Training Log-Linear Models with Cost Functions (2010, methodology): “We compared softmax-margin to several baselines: the structured perceptron (Collins, 2002a), 1-best MIRA with cost-augmented inference (Crammer et al., 2006), CLL, max-margin, risk, and our Jensen risk bound (JRB) introduced above.”
Part-of-Speech Tagging from 97% to 100%: Is It Time for Some Linguistics? (2011, background): “5 As far as I am aware, features of this sort were first introduced by Collins [9].”
A survey of named entity recognition and classification (2007, methodology): “Pattern features were introduced by M. Collins (2002) and then used by others (W. Cohen & Sarawagi 2004 and B. Settles 2004).”
Efficient Inference in Large Conditional Random Fields (2006, background): “The observation features included word identity, prefixes and suffixes, whether the word contains a number, uppercase letter or a hyphen, nearby words at relative positions −2, −1, +1 and +2, and the word shape [ 7 ].”
Structured Sparsity in Structured Prediction (2011, background): “…(Taskar et al., 2003; Tsochantaridis et al., 2004), where δ φ ( y (cid:48) ) = φ ( x, y (cid:48) ) − φ ( x, y ) ; and the loss underlying the structured perceptron (Collins, 2002a), Empirical comparison among these loss functions can be found in the literature (see, e.g. , Martins et al.,…”
Learning with Annotation Noise (2009, methodology): “This algorithm and its many variants are widely used in the computational linguistics community (Collins, 2002a; Collins and Duffy, 2002; Collins, 2002b; Collins and Roark, 2004; Henderson and Titov, 2005; Viola and Narasimhan, 2005; Cohen et al., 2004; Carreras et al., 2005; Shen and Joshi, 2005;…”
Rank learning for factoid question answering with linguistic and semantic constraints (2010, methodology): “The Committee Perceptron algorithm is a generalization of previous Perceptron variants [5], and is adapted for learning ranking functions based on preferences between pairs of judged passages.”