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

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.

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.

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.

\(\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.

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.

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.

A history is \(\langle t_{-1}, t_{-2}, w_{[1:n]}, i \rangle\): the previous two tags, the whole sentence and the current position. A local representation \(\phi: \mathcal{H} \times \mathcal{T} \to \mathbb{R}^d\) maps a history/tag pair to features, typically indicators, e.g. \(\phi_{1000}(h, t) = 1\) iff the current word is the and \(t = \text{DT}\).

\(\Phi_s(w_{[1:n]}, t_{[1:n]}) = \sum_{i=1}^{n} \phi_s(h_i, t_i)\): local features summed over all positions. For indicator features, global features are counts, e.g. how often the is tagged DT in the sentence.

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.

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.

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.

Instead of the final parameters \(\alpha_s^{T,n}\), output the average of the parameter vectors after every training example in every pass: \(\gamma_s = \sum_{t=1}^{T} \sum_{i=1}^{n} \alpha_s^{t,i} / nT\). It is simple to maintain during training and performed significantly better than the final parameters.

Training pairs \((x_i, y_i)\); a function \(\text{GEN}(x)\) enumerating candidate outputs; a feature map \(\Phi(x, y) \in \mathbb{R}^d\); parameters \(\bar\alpha\). The model outputs \(F(x) = \arg\max_{y \in \text{GEN}(x)} \Phi(x, y) \cdot \bar\alpha\). For tagging, \(\text{GEN}(w_{[1:n]}) = \mathcal{T}^n\), all tag sequences of length \(n\).

If some \(\mathbf{U}\) with \(\|\mathbf{U}\| = 1\) scores every correct output at least \(\delta\) above every incorrect candidate: \(\mathbf{U} \cdot \Phi(x_i, y_i) - \mathbf{U} \cdot \Phi(x_i, z) \ge \delta\) for all \(i\) and all \(z \in \text{GEN}(x_i) - \{y_i\}\).

If the training data is separable with margin \(\delta\), the perceptron makes at most \(R^2/\delta^2\) mistakes, where \(\|\Phi(x_i, y_i) - \Phi(x_i, z)\| \le R\) for all \(i\) and candidates \(z\). So with a zero-error \(\mathbf{U}\), training converges to zero training error after finitely many passes.

In NLP, GEN(x) is often exponential in the input length (e.g. \(|\mathcal{T}|^n\) tag sequences). The bound depends only on the separation of the data, so learning stays feasible however many candidates there are, as long as decoding (e.g. Viterbi) is efficient.

Let \(\bar\alpha^k\) be the weights before the \(k\)th mistake. Lower bound: each update adds at least \(\delta\) to \(\mathbf{U} \cdot \bar\alpha\), so \(\|\bar\alpha^{k+1}\| \ge k\delta\). Upper bound: \(\|\bar\alpha^{k+1}\|^2 \le \|\bar\alpha^k\|^2 + R^2\), because the cross term \(\bar\alpha^k \cdot (\Phi(x_i, y_i) - \Phi(x_i, z)) \le 0\) when \(z\) was the argmax; so \(\|\bar\alpha^{k+1}\|^2 \le kR^2\). Hence \(k^2\delta^2 \le kR^2\).

For any \(\mathbf{U}\), \(\delta\), let \(\epsilon_i = \max\{0, \delta - m_i\}\) be how far example \(i\) falls short of margin \(\delta\), and \(D_{\mathbf{U},\delta} = \sqrt{\sum_i \epsilon_i^2}\). Theorem 2: the first pass makes at most \(\min_{\mathbf{U},\delta} (R + D_{\mathbf{U},\delta})^2/\delta^2\) mistakes, so a few hard or mislabelled examples don’t ruin it.

By reduction to the separable case: add one extra feature per training example, nonzero only for that example’s correct output, with weight \(\epsilon_j/\Delta\). The extended data is separable with a smaller margin, the extra features never affect other examples, and minimizing over \(\Delta\) (\(\Delta = \sqrt{R D_{\mathbf{U},\delta}}\)) gives the bound.

Each parameter setting \(\bar\alpha^{1,i}\) during the first pass votes for its output on a test input; the majority wins. The averaged perceptron approximates this with a single decoding using the averaged weights, instead of \(n\) decodings.

Assuming i.i.d. examples, the probability that the voted perceptron errs on a new example is at most \(\frac{2}{n+1} E_{n+1}\big[\min_{\mathbf{U},\delta} (R + D_{\mathbf{U},\delta})^2/\delta^2\big]\): few training mistakes suggest good generalization, again independent of the size of GEN.

POS tagging on the Penn WSJ treebank (train sections 0–18, dev 19–21, test 22–24), with Ratnaparkhi’s (1996) MaxEnt tagger features, and base NP chunking on Ramshaw and Marcus’s data (sections 15–18 train, 20 test), measured by F-measure.

As a three-tag task: B begins a chunk, I continues it, O is outside. Every chunk starts with B whether the previous word is O or I. Features combine the current chunk tag \(t_i\) with nearby words and POS tags (from Brill’s tagger), up to two positions away, plus bigram and trigram combinations.

Averaging improved the perceptron significantly and made it much more stable across iterations. Including all features (count cut-off 0) helped the perceptron but hurt the MaxEnt model, which did better with a cut-off of 5. The perceptron also needed far fewer training iterations (about 6–39 vs 100–900).

POS tagging: 2.89% error vs 3.28% (an 11.9% relative error reduction). NP chunking: F-measure 93.63% vs 93.29% (a 5.1% relative error reduction).

It uses the same features and Viterbi decoding, but training needs only decoding and additive updates: no normalizers, no gradients of a partition function. Its guarantees depend on separability of the data rather than on the number of candidate outputs, and it beat a MaxEnt tagger on both tasks.