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

2.1 HMM Taggers

1. How does a trigram HMM tagger score a tagged sentence, in Collins’s formulation?
   \(\sum_{i=1}^{n} \alpha_{t_{i-2}, t_{i-1}, t_i} + \sum_{i=1}^{n} \alpha_{t_i, w_i}\), with a parameter per tag trigram and per tag/word pair. With \(\alpha_{x,y,z} = \log P(z \mid x, y)\) and \(\alpha_{t,w} = \log P(w \mid t)\) this is the log joint probability, and Viterbi finds the best tag sequence.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §2.1, pp. 1–2
2. Describe the perceptron training algorithm for a trigram tagger.
   Set all parameters to zero. For \(T\) passes over the data, for each sentence: Viterbi-decode with the current parameters to get \(z\); for every tag trigram or tag/word pair seen \(c_1\) times in the gold tags and \(c_2\) times in \(z\), add \(c_1 - c_2\) to its parameter. If \(z\) is correct, nothing changes.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §2.1, pp. 1–2
3. Gold: the/D man/N saw/V the/D dog/N. Predicted: the/D man/N saw/N the/D dog/N. Which parameters does the perceptron update change?
   Add 1 to \(\alpha_{D,N,V}\), \(\alpha_{N,V,D}\), \(\alpha_{V,D,N}\), \(\alpha_{V,\textit{saw}}\) (features missing from the prediction) and subtract 1 from \(\alpha_{D,N,N}\), \(\alpha_{N,N,D}\), \(\alpha_{N,D,N}\), \(\alpha_{N,\textit{saw}}\) (incorrect features). Shared features cancel out.

   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §2.1, pp. 1–2