Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms

By Michael Collins. 2002

2,302 citations recorded by the source corpus.

We describe new algorithms for training tagging models, as an alternative to maximum-entropy models or conditional random fields (CRFs). The algorithms rely on Viterbi decoding of training examples, combined with simple additive updates. We describe theory justifying the algorithms through a modification of the proof of convergence of the perceptron algorithm for classification problems. We give experimental results on part-of-speech tagging and base noun phrase chunking, in both cases showing improvements over results for a maximum-entropy tagger.

Subfields: Artificial Intelligence, Model Architectures

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 Model Architectures

Citations in the corpus

Semi-supervised sequence tagging with bidirectional language models (2017, methodology): “uence tagging problems are based on bidirectional RNN models. However, many other sequence tagging models have been proposed in the literature for this class of problems (e.g., Lafferty et al., 2001; Collins, 2002). LM embeddings could also be used as additional features in other models, although it”
Neural Text Generation with Unlikelihood Training (2019, methodology): “Some representative algorithms include structured perceptron (Collins, 2002), energy-based models (LeCun et al.”
Reasoning about Quantities in Natural Language (2015, methodology): “A Semi-CRF model (Sarawagi and Cohen, 2004), trained using a structured Perceptron algorithm (Collins, 2002), with Parameter Averaging (Freund and Schapire, 1998).”
On Structured Prediction Theory with Calibrated Convex Surrogate Losses (2017, methodology): “Following standard practices in structured prediction [12, 44], we define the prediction model by a score function f : X → R specifying a score fy(x) for each possible output y ∈ Y .”
Search-based structured prediction (2009, positive): “The structured perceptron is an extension of the standard perceptron (Rosenblatt 1958) to structured prediction (Collins 2002).”
Modeling Biological Processes for Reading Comprehension (2014, methodology): “For the joint model, we use a linear model for the scoring functions, and train jointly using the structured averaged perceptron algo-rithm (Collins, 2002).”
AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (2020, methodology): “This is reminiscent of the averaged perceptron [16] and neural network weight averaging during training [65, 26].”
Open Sesame: Getting inside BERT’s Linguistic Knowledge (2019, methodology): “Following the setup of Collins (2002) and filtering for sentences between 10 to 30 tokens BERT tokenization, we obtained training, development and generalization sets of sentences of sizes 21142, 3017 and 2999.”
Learning Context-Dependent Mappings from Sentences to Logical Form (2009, methodology): “Learning We model the problem of selecting the best derivation as a structured prediction problem (Johnson et al., 1999; Lafferty et al., 2001; Collins, 2002; Taskar et al., 2004).”
Overcoming the Lack of Parallel Data in Sentence Compression (2013, methodology): “In our study we employ an averaged variant of online structured perceptron (Collins, 2002).”
Multilingual Distributed Representations without Word Alignment (2013, methodology): “We train the multiclass classiﬁer using the same settings and implementation of the averaged perceptron classiﬁer [6] as used in [16].”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, methodology): “For example, the exponentiated gradient method of Collins et al. [2008] processes the data online and only requires O(log(1/ )) iterations to reach an accuracy of in terms of the dual objective. However, this does not guarantee good performance in terms of the primal objective or the weight vector. ”
A Primer on Neural Network Models for Natural Language Processing (2015, methodology): “…neural network model is held fixed, and the different layers (output as well as hidden layer vectors) for each input are then concatenated and used as the input features of a linear structured perceptron model (Collins, 2002) that is trained to perform beam-search for the best resulting structure.”
Annotating Derivations: A New Evaluation Strategy and Dataset for Algebra Word Problems (2016, methodology): “ al., 2015), we do not model the alignment of nouns phrases to variables, allowing for tractable inference when scoring the generated derivations. The solver is trained using a structured perceptron (Collins, 2002). We extract the following features for a (x;z) pair, Template Features. Unigrams and ”
Training a Natural Language Generator From Unaligned Data (2015, methodology): “Our approach to sentence planning is most similar to Zettlemoyer and Collins (2007), which use a candidate generator and a perceptron ranker for CCG parsing.”