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

3.2 Generalization results

1. What is the voted perceptron, and how does the averaged perceptron relate to it?
   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.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3.2, pp. 5–6
2. What generalization guarantee carries over from Freund and Schapire to structured outputs?
   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.
   • Collins, 2002, Discriminative Training Methods for Hidden Markov Models (Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002)), §3.2, pp. 5–6