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

article2002EMNLP2,303 citationsBest Paper Award, NAACL 2018 Test-of-Time Award

Introduces a computationally efficient, discriminative perceptron training algorithm for sequence labeling that matches or outperforms maximum-entropy models and CRFs on natural language processing tasks while providing theoretical convergence guarantees.

Listen

Sequence tagging tasks, such as assigning parts of speech or identifying phrases in text, are foundational for language processing applications. While popular approaches like maximum-entropy taggers offer flexibility, their parameter estimation methods have known limitations, and newer alternatives like conditional random fields can be complex to train. The article addresses this challenge by evaluating whether a simpler training approach based on the perceptron algorithm can serve as an efficient and theoretically grounded alternative for sequence labeling tasks.

The objective of the article is to demonstrate the theoretical convergence of perceptron-based algorithms on sequential data and evaluate their empirical performance against standard maximum-entropy models on standard natural language tasks.

To evaluate this approach, the author formulated a training algorithm that combines standard sequence decoding with simple additive weight adjustments when predictions are incorrect. The study tested the approach across two benchmark datasets: part-of-speech tagging using the Wall Street Journal corpus and base noun phrase chunking. The experiments evaluated both standard and parameter-averaged perceptron variants against maximum-entropy baselines under various feature filtering thresholds.

The findings demonstrate clear performance and efficiency advantages for the proposed method. First, on part-of-speech tagging, the averaged perceptron achieved a 2.89% test error rate compared to 3.28% for the maximum-entropy model, representing an 11.9% relative error reduction. Second, on noun phrase chunking, the averaged perceptron achieved a higher accuracy score of 93.63% compared to 93.29% for the baseline, representing a 5.1% relative error reduction. Third, the perceptron required significantly fewer training iterations to converge—typically reaching peak performance in 10 to 13 passes over the data, compared to hundreds of iterations required by the baseline. Fourth, parameter averaging substantially improved stability and accuracy across all tests, and the method handled rare features effectively without requiring aggressive frequency cut-offs.

These results show that organizations can achieve superior sequence tagging accuracy using an algorithm that is simpler to implement and significantly faster to train than established maximum-entropy models. By avoiding the computational overhead of calculating local probability normalizations during training, the perceptron method reduces processing time and resource consumption while delivering equal or better predictive quality.

Based on these findings, teams maintaining sequence tagging pipelines should adopt the averaged perceptron algorithm as a high-performing alternative to maximum-entropy taggers. When implementing the algorithm, practitioners should retain all feature counts rather than filtering rare occurrences and use a separate validation dataset to tune the optimal number of training passes.

The conclusions are supported by both formal theoretical proofs and empirical evaluations on standard benchmark datasets. However, confidence should be bounded by the scope of the evaluation, which focused on two specific English-language tagging tasks; additional validation is warranted when applying the approach to broader sequence labeling or structural parsing domains.

AT&T Labs—Research backpropagation algorithm classification conditional random field Discriminative training methods Perceptron algorithms Hidden Markov Models

Collins (2002).pdf

Paper: Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, J. Lafferty et al. (2001). Conditional random fields established the foundational probabilistic sequence-labeling framework that the source paper directly aims to rival and complement using discriminative perceptron training.
Paper: Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network, Kristina Toutanova et al. (2003). This paper introduces rich feature templates and cyclic dependency structures for sequence tagging, offering essential context for the feature-based discriminative methods evaluated in the source.
Paper: Introduction to the CoNLL-2003 Shared Task: Language-Independent Named Entity Recognition, Erik F. Tjong Kim Sang et al. (2003). Providing the standard benchmark tasks and shared-task framework for named entity recognition, this paper frames the evaluation context relied upon by sequential discriminative taggers.
Paper: Word Representations: A Simple and General Method for Semi-Supervised Learning., Joseph Turian et al. (2010). Demonstrating how unsupervised word representations boost sequence labeling performance, this paper provides critical background on auxiliary feature engineering for linear taggers.
Paper: A training algorithm for optimal margin classifiers, B. Boser et al. (1992). Establishing the foundational margin-maximization and perceptron convergence principles upon which the source's Viterbi-based training algorithms are theoretically justified.

Paper: Bidirectional LSTM-CRF Models for Sequence Tagging, Zhiheng Huang et al. (2015). This work extends traditional linear sequence models like CRFs and perceptrons by introducing bidirectional LSTM-CRF neural architectures for sequence tagging.
Paper: Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling, J. Finkel et al. (2005). Building upon standard sequence labeling decoding, this paper extends Viterbi-based frameworks to incorporate non-local consistency constraints via Gibbs sampling.
Paper: End-to-end Sequence Labeling via Bi-directional LSTM-CNNs-CRF, Xuezhe Ma et al. (2016). This paper generalizes sequence labeling beyond hand-engineered feature sets by combining convolutional networks, LSTMs, and CRFs into an end-to-end architecture.
Paper: Neural Architectures for Named Entity Recognition, Guillaume Lample et al. (2016). Continuing the shift toward deep sequence models, this work applies bidirectional LSTMs paired with CRF decoding to eliminate task-specific feature engineering in entity recognition.
Paper: Large Margin Methods for Structured and Interdependent Output Variables, Ioannis Tsochantaridis et al. (2005). Generalizing the perceptron and margin updates of the source paper, this work establishes a unified large-margin framework for complex structured output prediction.

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

Abstract

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 the 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.

Topics

backpropagation algorithm classification conditional random field discriminative training markov model maximum entropy models part of speech viterbi decoding multilayer perceptrons markov chains

Keywords

Discriminative training methods Perceptron algorithms Hidden Markov Models POS tagging Maximum-entropy taggers Parameter estimation Trigram tagger Tag sequences

1 Introduction
2 Parameter Estimation
2.1 HMM Taggers
2.2 Local and Global Feature Vectors
2.3 Maximum-Entropy Taggers
2.4 A New Estimation Method
2.5 Averaging Parameters
3 Theory Justifying the Algorithm
3.1 Theory for inseparable data
3.2 Generalization results
4 Experiments
4.1 Data Sets
4.2 Features
4.3 Results
5 Proofs of the Theorems
6 Conclusions
Acknowledgements
References

Knowls

Knowl 1 — Structured Perceptron Training Algorithm
algorithm
The structured perceptron algorithm extends the classic perceptron to structured prediction problems such as sequence tagging and parsing, where the candidate output space is exponentially large. Given an input sentence or sequence $x \in \mathcal{X}$ (such as a word sequence $w_{[1:n]}$ ) and a candidate generator $\text{GEN}(x) \subseteq \mathcal{Y}$ (such as all tag sequences $\mathcal{T}^n$ ), candidate outputs are scored by a linear function $\Phi(x, y) \cdot \bar{\alpha} = \sum_{s=1}^d \alpha_s \Phi_s(x, y)$ , where $\Phi(x, y) \in \mathbb{R}^d$ is a global feature vector and $\bar{\alpha} \in \mathbb{R}^d$ is a weight parameter vector.

Decoding finds the highest-scoring candidate structure under the current weights: $z = \arg\max_{y \in \text{GEN}(x)} \Phi(x, y) \cdot \bar{\alpha}$ For sequence tagging, this argmax is solved exactly and efficiently using the Viterbi algorithm. When the predicted structure $z$ differs from the ground truth annotation $y$ , the parameter vector is updated by adding the gold feature vector and subtracting the predicted feature vector: $\bar{\alpha} \leftarrow \bar{\alpha} + \Phi(x, y) - \Phi(x, z)$ If the predicted structure matches the gold standard ( $z = y$ ), no update is performed.
Input: Training examples $(x_i, y_i)$ for $i = 1, \dots, n$ ; number of training iterations $T$ ; feature mapping $\Phi(x, y)$
Output: Parameter vector $\bar{\alpha} \in \mathbb{R}^d$
Initialize $\bar{\alpha} = 0$
for $t = 1 \dots T$ do
    for $i = 1 \dots n$ do
         $z_i \leftarrow \arg\max_{z \in \text{GEN}(x_i)} \Phi(x_i, z) \cdot \bar{\alpha}$
        if $z_i \neq y_i$ then
             $\bar{\alpha} \leftarrow \bar{\alpha} + \Phi(x_i, y_i) - \Phi(x_i, z_i)$
        end if
    end for
end for
return $\bar{\alpha}$
Knowl 2 — Averaged Perceptron Parameter Estimation
model/method
In the averaged perceptron algorithm for structured prediction, parameter updates during training proceed identically to the standard structured perceptron, but inference at test time uses an averaged weight vector rather than the final weight vector. Let $\bar{\alpha}^{t,i} \in \mathbb{R}^d$ denote the parameter vector after processing the $i$ -th training example in pass $t$ over a training dataset of size $n$ , with $T$ total training passes. The averaged parameter vector $\bar{\gamma} \in \mathbb{R}^d$ is defined as the arithmetic mean of all intermediate parameter vectors generated across all $n \times T$ steps:

$\bar{\gamma} = \frac{1}{nT} \sum_{t=1}^T \sum_{i=1}^n \bar{\alpha}^{t,i}$

At test time, decoding an input sequence $x$ uses the single averaged parameter vector $\bar{\gamma}$ : $F(x) = \arg\max_{y \in \text{GEN}(x)} \Phi(x, y) \cdot \bar{\gamma}$

This method serves as a computationally efficient approximation to the voted perceptron (which requires executing $nT$ separate decodings and computing a majority vote over all outputs), allowing a single Viterbi decoding pass while yielding higher accuracy and greater variance stability across training epochs compared to the final unaveraged parameter vector $\bar{\alpha}^{T,n}$ .
Knowl 3 — Mistake Bound of Structured Perceptron on Separable Data
theoretical result
Let $(x_1, y_1), \dots, (x_n, y_n)$ be a sequence of training examples where each $x_i \in \mathcal{X}$ and $y_i \in \mathcal{Y}$ . Let $\text{GEN}(x_i)$ denote the candidate set for $x_i$ , and let $\mathbf{GEN}(x_i) = \text{GEN}(x_i) \setminus \{y_i\}$ denote the set of incorrect candidate outputs. The training sequence is defined to be separable with margin $\delta > 0$ if there exists a unit vector $U \in \mathbb{R}^d$ ( $\|U\| = 1$ ) such that: $\forall i \in \{1, \dots, n\}, \forall z \in \mathbf{GEN}(x_i), \quad U \cdot \Phi(x_i, y_i) - U \cdot \Phi(x_i, z) \ge \delta$

If the training sequence is separable with margin $\delta$ , the total number of mistakes (parameter update steps) made by the structured perceptron algorithm across any number of passes over the training set is upper bounded by: $\text{Number of mistakes} \le \frac{R^2}{\delta^2}$ where $R$ is a constant such that $\|\Phi(x_i, y_i) - \Phi(x_i, z)\| \le R$ for all $i$ and all $z \in \mathbf{GEN}(x_i)$ .

The mistake bound depends solely on the geometric separation margin $\delta$ and the bounding radius $R$ , and is strictly independent of the number of candidate structures in $\text{GEN}(x_i)$ (which may grow exponentially with the length of the input sequence).
Knowl 4 — Mistake Bound of Structured Perceptron on Inseparable Data
theoretical result
When a structured training sequence $(x_1, y_1), \dots, (x_n, y_n)$ is not linearly separable with margin $\delta > 0$ , the structured perceptron retains a finite mistake bound on its first training pass. For any choice of unit vector $U \in \mathbb{R}^d$ ( $\|U\| = 1$ ) and margin parameter $\delta > 0$ , define the margin difference for example $i$ as: $m_i = U \cdot \Phi(x_i, y_i) - \max_{z \in \text{GEN}(x_i) \setminus \{y_i\}} U \cdot \Phi(x_i, z)$ and the margin slack violation as: $\epsilon_i = \max\{0, \delta - m_i\}$ The cumulative margin violation distance is $D_{U,\delta} = \sqrt{\sum_{i=1}^n \epsilon_i^2}$ .

For the first pass over the training sequence ( $t=1$ ), the structured perceptron algorithm makes at most: $\text{Number of mistakes} \le \min_{U, \delta} \frac{(R + D_{U,\delta})^2}{\delta^2}$ where $R$ is a constant satisfying $\|\Phi(x_i, y_i) - \Phi(x_i, z)\| \le R$ for all $i$ and all $z \in \text{GEN}(x_i)$ , and the minimum is taken over all $\delta > 0$ and unit vectors $U$ with $\|U\| = 1$ . When the data is perfectly separable with margin $\delta$ , $D_{U,\delta} = 0$ , recovering the separable mistake bound.
Knowl 5 — Global Feature Vector Scoring for Discriminative Sequence Models
model/method
In maximum-entropy sequence taggers (such as Maximum Entropy Markov Models), the conditional probability of a tag sequence $t_{[1:n]}$ given a word sequence $w_{[1:n]}$ is formulated as a sequence of locally normalized decisions: $\log P(t_{[1:n]} \mid w_{[1:n]}, \bar{\alpha}) = \sum_{i=1}^n \sum_{s=1}^d \alpha_s \phi_s(h_i, t_i) - \sum_{i=1}^n \log Z(h_i, \bar{\alpha})$ where $h_i = \langle t_{i-1}, t_{i-2}, w_{[1:n]}, i \rangle$ is the local history, $\phi_s(h_i, t_i)$ is a local indicator feature function, and $Z(h_i, \bar{\alpha}) = \sum_{l \in \mathcal{T}} \exp(\sum_s \alpha_s \phi_s(h_i, l))$ is the local partition function.

In the global linear sequence model trained by the perceptron, the local normalization terms $\log Z(h_i, \bar{\alpha})$ are omitted entirely. The score for a sentence/tag sequence pair $(w_{[1:n]}, t_{[1:n]})$ is given directly by: $\sum_{i=1}^n \sum_{s=1}^d \alpha_s \phi_s(h_i, t_i) = \sum_{s=1}^d \alpha_s \Phi_s(w_{[1:n]}, t_{[1:n]})$ where $\Phi_s(w_{[1:n]}, t_{[1:n]}) = \sum_{i=1}^n \phi_s(h_i, t_i)$ is a global feature value obtained by aggregating local feature activations over the whole sequence. This avoids label bias and local normalization estimation artifacts while retaining exact Viterbi decoding.
Knowl 6 — Generalization Error Bound for the Voted Structured Perceptron
theoretical result
Assume training examples $(x_1, y_1), \dots, (x_n, y_n)$ and a test example $(x_{n+1}, y_{n+1})$ are drawn independently and identically distributed (i.i.d.) from an unknown distribution $P(x, y)$ over $\mathcal{X} \times \mathcal{Y}$ . The voted perceptron computes predictions on test input $x_{n+1}$ by taking the majority vote among the $n$ candidate outputs $v_i = \arg\max_{z \in \text{GEN}(x_{n+1})} \bar{\alpha}^{1,i} \cdot \Phi(x_{n+1}, z)$ produced by each intermediate parameter vector $\bar{\alpha}^{1,i}$ from the first training pass.

The probability that the voted perceptron fails to predict the correct label $y_{n+1}$ on input $x_{n+1}$ (over the random choice of all $n+1$ examples) is bounded by: $\mathbb{P}(\text{voted prediction} \neq y_{n+1}) \le \frac{2}{n+1} \mathbb{E}_{n+1}\left[ \min_{U, \delta} \frac{(R + D_{U,\delta})^2}{\delta^2} \right]$ where $\mathbb{E}_{n+1}$ is the expectation over $n+1$ examples drawn i.i.d. from $P(x, y)$ , $R$ satisfies $\|\Phi(x_i, y_i) - \Phi(x_i, z)\| \le R$ for all $z \in \text{GEN}(x_i)$ , and $D_{U,\delta} = \sqrt{\sum_{i=1}^{n+1} (\max\{0, \delta - m_i\})^2}$ is the cumulative margin slack of unit vector $U$ ( $\|U\| = 1$ ) at target margin $\delta > 0$ across the $n+1$ examples.
Knowl 7 — Comparative Performance of Averaged Perceptron on POS Tagging and NP Chunking Test Sets
empirical result
The averaged perceptron tagger using all features without count cut-offs ( $cc=0$ ) was compared against Maximum Entropy (ME) models on two standard benchmark test sets:
- Part-of-Speech Tagging: Evaluated on the Penn Wall Street Journal treebank (training on sections 0–18, development on sections 19–21, testing on sections 22–24). The averaged perceptron achieved a test error rate of 2.89% (97.11% accuracy), compared to 3.28% error for the Maximum Entropy tagger, representing an 11.9% relative reduction in tagging error.
- Base Noun Phrase Chunking: Evaluated on the CoNLL/Ramshaw & Marcus dataset (training on WSJ sections 15–18, development on section 21, testing on section 20). The averaged perceptron achieved a test F-measure of 93.63%, compared to 93.29% for the Maximum Entropy tagger, representing a 5.1% relative reduction in error.

Knowl 8 — Development Set Comparison Across Perceptron and Maximum Entropy Variants

data/table

Experimental configurations were evaluated on development data for Base Noun Phrase (NP) chunking (Penn Treebank WSJ section 21, measured by F-measure) and Part-of-Speech (POS) tagging (Penn Treebank WSJ sections 19–21, measured by percentage error rate). Evaluated variants include perceptron with parameter averaging (Perc, avg) versus without averaging (Perc, noavg), feature count cut-off thresholds (cc=0 retaining all features vs cc=5 retaining only features occurring $\ge 5$ times), and Maximum Entropy (ME) trained via Generalized Iterative Scaling. Numits denotes the number of training iterations where optimal development performance occurred.

NP Chunking Method	F-Measure	Numits
Perc, avg, cc=0	93.53	13
Perc, noavg, cc=0	93.04	35
Perc, avg, cc=5	93.33	9
Perc, noavg, cc=5	91.88	39
ME, cc=0	92.34	900
ME, cc=5	92.65	200
POS Tagging Method	Error rate/%	Numits
Perc, avg, cc=0	2.93	10
Perc, noavg, cc=0	3.68	20
Perc, avg, cc=5	3.03	6
Perc, noavg, cc=5	4.04	17
ME, cc=0	3.40	100
ME, cc=5	3.28	200

The development results demonstrate that:

Parameter averaging consistently improves accuracy (e.g., reducing POS error from 3.68% to 2.93% with cc=0) and significantly stabilizes convergence across iterations compared to unaveraged perceptron training.
The averaged perceptron achieves its best performance when retaining rare features (cc=0), whereas Maximum Entropy models suffer performance degradation when rare features are included without a cut-off (e.g., POS error degrades from 3.28% at cc=5 to 3.40% at cc=0).

Knowl 9 — Feature Templates and Tag Representation for Base NP Chunking
experimental setup
Base noun phrase chunking is formulated as a three-tag sequential labeling task with labels $\{B, I, O\}$ , where $B$ denotes a token that begins a base NP chunk, $I$ denotes a token that continues a chunk, and $O$ denotes a token outside any chunk. All base NP chunks begin with a $B$ tag regardless of the preceding tag.

The input representation for sentence position $i$ contains words $w_1 \dots w_n$ and part-of-speech tags $p_1 \dots p_n$ generated by a Brill tagger. The local indicator feature templates paired with the proposed chunking tag $t_i$ include:
- Word features: Current word $w_i$ , preceding words $w_{i-1}, w_{i-2}$ , following words $w_{i+1}, w_{i+2}$ , and word bigrams $(w_{i-2}, w_{i-1})$ , $(w_{i-1}, w_i)$ , $(w_i, w_{i+1})$ , $(w_{i+1}, w_{i+2})$ .
- POS tag features: Current POS tag $p_i$ , preceding POS tags $p_{i-1}, p_{i-2}$ , following POS tags $p_{i+1}, p_{i+2}$ , POS tag bigrams $(p_{i-2}, p_{i-1})$ , $(p_{i-1}, p_i)$ , $(p_i, p_{i+1})$ , $(p_{i+1}, p_{i+2})$ , and POS tag trigrams $(p_{i-2}, p_{i-1}, p_i)$ , $(p_{i-1}, p_i, p_{i+1})$ , $(p_i, p_{i+1}, p_{i+2})$ .

Coverage note — No substantial contributed material was omitted; intermediate proof derivations for Theorems 1 and 2 were excluded in accordance with the rules.

References

1.Brill, E. (1995). Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part of Speech Tagging. Computational Linguistics.
2.Collins, M., and Duffy, N. (2001). Convolution Kernels for Natural Language. In Proceedings of Neural Information Processing Systems (NIPS 14).
3.Collins, M., and Duffy, N. (2002). New Ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures, and the Voted Perceptron. In Proceedings of ACL 2002.
4.Collins, M. (2002). Ranking Algorithms for Named–Entity Extraction: Boosting and the Voted Perceptron. In Proceedings of ACL 2002.
5.Freund, Y. & Schapire, R. (1999). Large Margin Classification using the Perceptron Algorithm. In Machine Learning, 37(3):277–296.
6.Helmbold, D., and Warmuth, M. On weak learning. Journal of Computer and System Sciences, 50(3):551-573, June 1995.
7.Lafferty, J., McCallum, A., and Pereira, F. (2001). Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML 2001.
8.McCallum, A., Freitag, D., and Pereira, F. (2000) Maximum entropy markov models for information extraction and segmentation. In Proceedings of ICML 2000.
9.Marcus, M., Santorini, B., & Marcinkiewicz, M. (1993). Building a large annotated corpus of english: The Penn treebank. Computational Linguistics, 19.
10.Ramshaw, L., and Marcus, M. P. (1995). Text Chunking Using Transformation-Based Learning. In Proceedings of the Third ACL Workshop on Very Large Corpora, Association for Computational Linguistics, 1995.
11.Ratnaparkhi, A. (1996). A maximum entropy part-of-speech tagger. In Proceedings of the empirical methods in natural language processing conference.
12.Rosenblatt, F. 1958. The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain. Psychological Review, 65, 386–408. (Reprinted in Neurocomputing (MIT Press, 1998).)

Citation

MLA

Collins, M. “Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms”. Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002), 2002, pp. 1–8, https://doi.org/10.3115/1118693.1118694.

APA

Collins, M. (2002). Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002), 1–8. https://doi.org/10.3115/1118693.1118694

Chicago

Collins, M. 2002. “Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms”. Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002), 1–8. https://doi.org/10.3115/1118693.1118694.

Harvard

Collins, M. (2002) “Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms”, Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002). Association for Computational Linguistics, pp. 1–8. Available at: https://doi.org/10.3115/1118693.1118694.

Vancouver

1. Collins M (2002) Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms. In: Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002). Association for Computational Linguistics, pp 1–8

BibTeX

@inproceedings{collins-2002-discriminative,
    title = "Discriminative Training Methods for Hidden {M}arkov Models: Theory and Experiments with Perceptron Algorithms",
    author = "Collins, Michael",
    booktitle = "Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing ({EMNLP} 2002)",
    month = jul,
    year = "2002",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/W02-1001/",
    doi = "10.3115/1118693.1118694",
    pages = "1--8"
}

Metadata:ACL Anthology

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by-nc-sa/4.0/

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Structured Perceptron Training Algorithm

Knowl 2 — Averaged Perceptron Parameter Estimation

Knowl 3 — Mistake Bound of Structured Perceptron on Separable Data

Knowl 4 — Mistake Bound of Structured Perceptron on Inseparable Data

Knowl 5 — Global Feature Vector Scoring for Discriminative Sequence Models

Knowl 6 — Generalization Error Bound for the Voted Structured Perceptron

Knowl 7 — Comparative Performance of Averaged Perceptron on POS Tagging and NP Chunking Test Sets

Knowl 8 — Development Set Comparison Across Perceptron and Maximum Entropy Variants

Knowl 9 — Feature Templates and Tag Representation for Base NP Chunking

References

Citation

BibTeX

Access the Paper