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

3.1 Theory for inseparable data

1. What does the perceptron guarantee when the training data is not separable?
   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.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3.1, p. 5
2. How is the inseparable-case bound (Theorem 2) proved?
   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.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3.1, p. 5