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

3 Theory Justifying the Algorithm

1. What is the general setting of Collins’s perceptron algorithm, beyond tagging?
   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\).
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3, pp. 4–5
2. When is a training set separable with margin \(\delta\), in Collins’s sense?
   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\}\).
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3, pp. 4–5
3. State Collins’s Theorem 1 (perceptron convergence for structured outputs).
   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.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3, pp. 4–5
4. Why is it crucial that the mistake bound doesn’t depend on the size of GEN(x)?
   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.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3, pp. 4–5
5. Sketch the proof of the mistake bound \(k \le R^2/\delta^2\).
   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\).
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3, pp. 4–5