AdaBoost

AdaBoost (short for Adaptive Boosting) is an ensemble algorithm introduced by Yoav Freund and Robert Schapire in 1997, in the paper «A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting». It combines many weak classifiers —each only slightly better than chance— into a single weighted vote that is more accurate than any of them alone.

Its founding assumption is modest, and worth stating plainly: you only need a base learner that, on any weighting of the data, does a little better than a coin flip (error below 0.5). In its original form, AdaBoost solves a binary classification problem, with labels of +1 and −1.

How it works

AdaBoost trains weak learners in sequence. Every example starts with equal weight. In each round it fits a learner on the weighted data, measures its weighted error, and gives it a coefficient that grows as that error shrinks. It then reweights: the weight of misclassified examples goes up and that of correct ones goes down, so the next round concentrates on what the committee still gets wrong. The final prediction is the sign of the weighted sum of the votes. The usual weak learner is the decision stump: a one-level tree that splits on a single threshold of a single feature. Later statistical work by Friedman, Hastie and Tibshirani showed that the procedure amounts to stagewise minimization of an exponential loss, although the original derivation came from learning theory.

Sensitivity to noise and outliers

The mechanism that gives AdaBoost its strength is also its weak spot. By insisting on the difficult examples, it piles weight onto them round after round. If a difficult example is in fact a mislabeled instance or an outlier, the algorithm keeps pushing weight toward that point, and later learners end up chasing noise. On datasets with label noise, its generalization can deteriorate and overfit. The open question is worth stating: on many clean problems AdaBoost resists overfitting better than expected —why it does so is still studied— yet under noise it degrades. To ease this, variants such as LogitBoost, BrownBoost, MadaBoost and RobustBoost soften the reweighting so that anomalous points may be left on the wrong side.

From the binary version to the extensions

The 1997 version is binary. For more than two classes, Zhu, Zou, Rosset and Hastie proposed SAMME in 2009, which extends AdaBoost to the multiclass case without breaking it into two-class problems and reduces to the original algorithm when there are only two labels; earlier reductions included AdaBoost.M1 and AdaBoost.MH. For regression, AdaBoost.R2 (Drucker, 1997) adapts the reweighting idea to continuous targets. AdaBoost is, in any case, one concrete instance of the broader boosting family.