A brief introduction to boosting

Boosting is a general method for improving the accuracy of any given learning algorithm. This short paper introduces the boosting algorithm AdaBoost, and explains the underlying theory of boosting, including an explanation of why boosting often does not suffer from overfitting. Some examples of recent applications of boosting are also described. Background Boosting is a general method which attempts to "boost" the accuracy of any given learning algorithm. Boosting has its roots in a theoretical framework for studying machine learning called the "PAC" learning model, due to Valiant [37]; see Kearns and Vazirani [24] for a good introduction to this model. Kearns and Valiant [22, 23] were the first to pose the question of whether a "weak" learning algorithm which performs just slightly better than random guessing in the PAC model can be "boosted" into an arbitrarily accurate "strong" learning algorithm. Schapire [30] came up with the first provable polynomial-time boosting algorithm in ...