Boosting

Bagging trains many strong, unstable models independently and averages away their variance. Boosting takes the opposite route: it trains many weak models (each only a little better than guessing) one after another, and each new model concentrates on the mistakes of the ones before it. Together they become a strong classifier. The question that started it, posed by Kearns and Valiant in the late 1980s, was whether "slightly better than chance" can always be turned into "arbitrarily accurate". Schapire showed in 1990 that it can, and AdaBoost (Freund and Schapire, 1995) made the idea practical.

Weak learners

A typical weak learner is a decision stump: a tree with a single question, such as is $x_2 \le 1.7$?, predicting $+1$ on one side and $-1$ on the other. On its own a stump is a poor classifier. The only requirement is that, on whatever weighting of the data it is given, its weighted error is below 50%.

AdaBoost

Labels are $y_i \in \{-1, +1\}$. Each training point carries a weight $D_t(i)$, starting uniform.

1. Initialise $D_1(i) = 1/n$.
2. For rounds $t = 1, \dots, T$:
   • Train a weak learner $h_t$ to minimise the weighted error $\epsilon_t = \sum_i D_t(i)\,\mathbf{1}[h_t(x_i) \ne y_i]$.
   • Give it a vote of strength $\alpha_t = \tfrac12 \ln\frac{1 - \epsilon_t}{\epsilon_t} .$
   • Reweight the points: $D_{t+1}(i) = \frac{D_t(i)\, e^{-\alpha_t\, y_i h_t(x_i)}}{Z_t},$ where $Z_t$ makes the weights sum to 1.
3. Output the weighted vote $H(x) = \operatorname{sign}\big(\sum_{t=1}^{T}\alpha_t h_t(x)\big)$.

Read the two formulas.

• The vote. A learner with error $\epsilon_t = 0.5$ (pure guessing) gets $\alpha_t = 0$. The more accurate it is, the larger its say: $\epsilon_t = 0.1$ gives $\alpha_t = \tfrac12\ln 9 \approx 1.10$.
• The reweighting. Since $y_ih_t(x_i) = +1$ for a correct point and $-1$ for a mistake, correctly classified points have their weight multiplied by $e^{-\alpha_t}$ (shrunk) and misclassified ones by $e^{+\alpha_t}$ (grown). After the update, the current learner's weighted error is exactly 50%: the next learner is forced to find something new.

Why it works: training error falls exponentially

A short calculation shows that the training error of the final vote is bounded by the product of the normalisers:

Write $\epsilon_t = \tfrac12 - \gamma_t$, where $\gamma_t$ is how much better than chance the learner is. Then $2\sqrt{\epsilon_t(1-\epsilon_t)} = \sqrt{1 - 4\gamma_t^2} \le e^{-2\gamma_t^2}$, so

If every learner is at least $\gamma$ better than chance, the training error falls like $e^{-2\gamma^2T}$: exponentially fast in the number of rounds. With $\gamma = 0.1$, for example, it is below 1% after about 230 rounds.

Where the formulas come from: the exponential loss

AdaBoost is not a collection of clever tricks; it is a greedy minimiser of one loss. Let $F(x) = \sum_t \alpha_t h_t(x)$ be the ensemble's score. AdaBoost minimises the exponential loss

one term at a time: at round $t$ it adds the learner $h_t$ and the coefficient $\alpha_t$ that reduce this loss the most, holding the earlier terms fixed. Working this out gives exactly the weighted-error criterion for $h_t$, the formula for $\alpha_t$, and the reweighting rule (the weights $D_t(i)$ are just the current loss of each point, normalised). The exponential loss is a smooth, convex stand-in for the 0-1 loss that punishes confident mistakes very heavily, which also explains boosting's weakness: mislabelled points get exponentially large weights, and the later learners chase them.

Bias, variance and overfitting

Boosting mainly reduces bias: it builds a flexible model from very rigid pieces. It can overfit if run for too many rounds on noisy data, so the number of rounds is chosen by validation. Remarkably, on clean data the test error often keeps falling after the training error has reached zero. The explanation is margins: extra rounds keep increasing $y_iF(x_i)$, the confidence of the vote on the training points, which (as with SVMs) tends to improve generalisation.

Gradient boosting

Viewing boosting as greedy loss minimisation suggests a generalisation: replace the exponential loss with any differentiable loss (squared error for regression, log loss for probabilities), and at each round fit a small tree to the negative gradient of the loss at the current predictions, then add it with a small step size (the learning rate). This is gradient boosting. With careful regularisation, it is the method behind XGBoost, LightGBM and CatBoost, which win a large share of machine learning competitions on tabular data.