01727086

j

01727086 Servedio, R. PAC analogues of Perceptron and Winnow via boosting the margin. Mach. Learn. 47, No. 2-3, 133-151 (2002). 2002 Springer, Dordrecht EN linear threshold functions PAC model algorithms Zbl 0988.68147

doi:10.1023/A:1013633619373

Summary: We describe a novel family of PAC model algorithms for learning linear threshold functions. The new algorithms work by boosting a simple weak learner and exhibit sample complexity bounds remarkably similar to those of known online algorithms such as Perceptron and Winnow, thus suggesting that these well-studied online algorithms in some sense correspond to instances of boosting. We show that the new algorithms can be viewed as natural PAC analogues of the online $p$-norm algorithms which have recently been studied by {\it A. J. Grove}, {\it N. Littlestone} and {\it D. Schuurmans} [Mach. Learn. 43, 173--210 (2001; Zbl 0988.68147)] and {\it C. Gentile} and {\it N. Littlestone} [Proc. Twelfth Annual Conference on Computational Learning Theory, 1--11 (1999)]. As special cases of the algorithm, by taking $p=2$ and $p=\infty$ we obtain natural boosting-based PAC analogues of Perceptron and Winnow respectively. The $p= \infty$ case of our algorithm can also be viewed as a generalization (with an improsed sample complexity bound) of Jackson and Craven's PAC-model boosting-based algorithm for learning ``sparse perceptrons''. The analysis of the generalization error of the new algorithms relies on techniques from the theory of large margin classification.