Theoretical Views of Boosting

. Boosting is a general method for improving the accuracy of any given learning algorithm. Focusing primarily on the AdaBoost algorithm, we briefly survey theoretical work on boosting including analyses of AdaBoost's training error and generalization error, connections between boosting and game theory, methods of estimating probabilities using boosting, and extensions of AdaBoost for multiclass classification problems. We also briefly mention some empirical work. Background Boosting is a general method which attempts to "boost" the accuracy of any given learning algorithm. Kearns and Valiant [21, 22] were the first to pose the question of whether a "weak" learning algorithm which performs just slightly better than random guessing in Valiant's PAC model [34] can be "boosted" into an arbitrarily accurate "strong" learning algorithm. Schapire [28] came up with the first provable polynomial-time boosting algorithm in 1989. A year later, Freund [13] developed a much more efficient boosting..