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

2.3 Maximum-Entropy Taggers

1. How does a maximum-entropy tagger score a tag sequence?
   Each decision is locally normalized: \(P(t \mid h, \bar\alpha) = e^{\sum_s \alpha_s \phi_s(h, t)} / Z(h, \bar\alpha)\), so the sequence log probability is \(\sum_i \sum_s \alpha_s \phi_s(h_i, t_i) - \sum_i \log Z(h_i, \bar\alpha)\). Parameters are trained by maximum likelihood (e.g. Generalized Iterative Scaling); Viterbi finds the best 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.3, p. 3