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

Summary

The paper proposes training sequence-labelling models, such as part-of-speech taggers and base-NP chunkers, with a perceptron instead of maximum-entropy models or CRFs. The classic perceptron is extended from classification to structured outputs: for each training sentence the current weights are used to decode the best tag sequence with Viterbi, and if it is wrong, the features of the correct sequence are rewarded and those of the predicted one penalised. Features are the same as in maximum-entropy taggers, but there is no local probability normalisation. The author adapts the perceptron convergence proof to give mistake bounds for separable data and a bound for the non-separable case. In practice the averaged-parameters variant works best, and it outperforms a maximum-entropy tagger on both tasks. The method is simple, fast and applies to any model with Viterbi-style decoding; it became the basis of the structured perceptron in NLP.

How Mova uses it

• en/src/ptag.rs: the English PTB part-of-speech tagger is an averaged perceptron in the spirit of this paper, run as a left-to-right greedy/beam tagger (following Honnibal 2013) with hashed integer features and per-tag weights.
• Adaptations: a dictionary hint (mask of tags the built-in lexicon allows for a word form) is just another feature, so the model learns how much to trust it; for unknown words the prior from the older TnT tagger is added to the perceptron score with a weight; a small beam (width 2) with state merging on the last two tags replaces full Viterbi.
• A noise-robust variant stops updating on words that are wrong in every epoch, which also yields a list of suspected gold-label errors.
• The same averaged structured perceptron recipe is reused elsewhere in Mova (word-problem solver, reader models).

Effectiveness in Mova

Measured on UD English EWT test (recorded in the module header of en/src/ptag.rs): the TnT HMM tagger gives 93.12%; the greedy averaged perceptron 93.74%; plus the TnT prior for unknown words 94.13%; plus neighbouring-word shape features and beam 94.35%. The dependency parser on these tags improved from LAS 77.27 to 79.00. With 5% corrupted training tags, the robust variant raised accuracy from 94.00 to 94.10 and found the corrupted labels with 95.8% precision and 63% recall.

Note: the code cites "Collins 2002"; this refers to the EMNLP 2002 perceptron paper above, not Collins & Duffy 2002 (kernel-based reranking, ACL 2002).

👨‍🔬💥

Topics: Part-of-speech tagging

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/1118693.1118694

@inproceedings{collins2002discriminative,
  title = {{Discriminative Training Methods for Hidden Markov 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)},
  year = {2002},
  doi = {10.3115/1118693.1118694},
  url = {https://doi.org/10.3115/1118693.1118694}
}

References

12 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Brill, E. (1995). Transformation-Based Error-Driven Learning and Natural Language Processing: A Case Study in Part of Speech Tagging. Computational Linguistics . find
2. Collins, M., and Du y, N. (2001). Convolution Kernels for Natural Language. In Proceedings of Neural Information Processing Systems (NIPS 14) . find
3. Collins, M., and Du y, N. (2002). New Ranking Algorithms for Parsing and Tagging: Kernels over Discrete Structures, and the Voted Perceptron. In Proceedings of ACL 2002 . find
4. Collins, M. (2002). Ranking Algorithms for Named{ Entity Extraction: Boosting and the Voted Perceptron. In Proceedings of ACL 2002 . find
5. Freund, Y. & Schapire, R. (1999). Large Margin Classication using the Perceptron Algorithm. In Machine Learning , 37(3):277{296. find
6. Helmbold, D., and Warmuth, M. On weak learning. Journal of Computer and System Sciences , 50(3):551-573, June 1995. find
7. La erty, J., McCallum, A., and Pereira, F. (2001). Conditional random elds: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML 2001 . find
8. McCallum, A., Freitag, D., and Pereira, F. (2000) Maximum entropy markov models for information extraction and segmentation. In Proceedings of ICML 2000 . find
9. Marcus, M., Santorini, B., & Marcinkiewicz, M. (1993). Building a large annotated corpus of english: The Penn treebank. Computational Linguistics, 19. find our card
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. find
11. Ratnaparkhi, A. (1996). A maximum entropy part-of-speech tagger. In Proceedings of the empirical methods in natural language processing conference . find
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).) find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/collins-2002-discriminative-training-methods-hidden-markov/