AdaBoost

What AdaBoost is

AdaBoost, short for Adaptive Boosting, is a statistical classification meta-algorithm: it is not a classifier in its own right, but a procedure used together with many other learning algorithms to improve their performance^[1]. It was formulated by Yoav Freund and Robert Schapire in 1995^[1]. The usual setting is binary classification, deciding between two classes, though the method can be generalised to multiple classes or to bounded intervals of real values^[1].

How it works

AdaBoost maintains a probability distribution over the training samples. That distribution is initially uniform, giving every example the same weight, and it is modified iteratively with each new weak classifier^[2]. Once a weak learner has been trained, the examples it got wrong are weighted more heavily, so later weak learners are adjusted in favour of instances that earlier models misclassified and concentrate on the harder examples^[1]. The learners do not simply vote equally either: their outputs are combined into a weighted sum that represents the final boosted classifier^[1].

A rough picture: the first weak learner might be a very simple rule that gets most training examples right but fails on a few. Those few are up-weighted, so the second learner is pushed towards them; whatever the first two still miss becomes the focus of the third, and so on. No single rule needs to be good on its own — the weighted combination is what carries the performance.

The guarantee

The method comes with theory attached. Provided each weak learner performs slightly better than random guessing, the combined model can converge to a strong learner^[1]. AdaBoost also carries a theoretical guarantee that the training misclassification rate can be made arbitrarily small as more weak classifiers are added, together with a bound on generalization error^[2]. So the analysis covers both the fit to the training data and the error on unseen data.

Where it came from

The main reference is the original paper by Freund and Schapire, "A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting", in the Proceedings of the 2nd European Conference on Computational Learning Theory, 1995^[2]. Freund and Schapire won the 2003 Godel Prize for this work^[1].

Where it is used

Because it is a meta-algorithm, AdaBoost can be paired with many other, simpler learning algorithms rather than being tied to one particular model^[1]. It became particularly famous after Viola and Jones showed that it could be used to create face detectors with false-positive rates as low as 10^-6^[2].

Limits

The guarantees come with conditions. Each weak learner has to perform slightly better than random guessing^[1]. The guarantee on the training misclassification rate says nothing on its own about new data, which is why the theory pairs it with a bound on generalization error^[2]. And the basic formulation is for binary classification, so multiple classes or real-valued outputs need a generalisation of the method^[1].