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

2.4 A New Estimation Method

1. How does the perceptron tagger’s scoring differ from a MaxEnt tagger’s?
   It scores a sequence by \(\sum_i \sum_s \alpha_s \phi_s(h_i, t_i) = \bar\alpha \cdot \Phi(w_{[1:n]}, t_{[1:n]})\): the same features, but without the local normalization terms \(\log Z(h_i, \bar\alpha)\). Decoding is the same Viterbi search, minus computing the normalizers.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §2.4, pp. 3–4
2. Give the perceptron update for tagging with global feature vectors.
   Decode \(z_{[1:n_i]} = \arg\max_{u \in \mathcal{T}^{n_i}} \bar\alpha \cdot \Phi(w^i, u)\); if \(z \ne t^i\), set \(\bar\alpha = \bar\alpha + \Phi(w^i, t^i) - \Phi(w^i, z)\). With indicator features this adds \(c_s - d_s\) to each \(\alpha_s\), where \(c_s\) and \(d_s\) count feature \(s\) in the gold and predicted sequences.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §2.4, pp. 3–4