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

1 Introduction

1. What does Collins (2002) propose, and as an alternative to what?
   Perceptron-based training for tagging models (HMM-style taggers with rich features) as an alternative to maximum-entropy models and CRFs: decode each training example with Viterbi and make simple additive updates, justified by adapting the perceptron convergence proof.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §1, p. 1
2. What was the motivation for the structured perceptron, given MaxEnt taggers and CRFs?
   MaxEnt taggers allow flexible features, but Lafferty et al. (2001) had shown problems with their (locally normalized) parameter estimation, and CRFs fix this at a higher training cost. The voted/averaged perceptron of Freund and Schapire (1999) was competitive with SVMs, but had mainly been applied to classification, not tagging or parsing.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §1, p. 1
3. Beyond tagging, where did Collins expect the perceptron framework to apply?
   To any model where Viterbi-style algorithms can decode: e.g. probabilistic context-free grammars (weights for a weighted CFG could be trained this way) or ME models for parsing.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §1, p. 1