Boosting: models that learn from the last one's mistakes

Boosting is covered in section 8.2.3 of An Introduction to Statistical Learning, and its classic example is AdaBoost. Boosted trees (the XGBoost and LightGBM family) are among the most common models in banking today for tabular data, so it is worth knowing what they do.

Bagging vs boosting in one picture

In the bias and variance terms: bagging takes complex, unstable models and steadies them. Boosting takes simple, stable models and makes them smarter.

AdaBoost: reweight the mistakes

AdaBoost (adaptive boosting, Freund and Schapire, 1997) was the first widely used boosting method.

1. Give every training example the same weight.
2. Train a weak model, often a stump: a tree with a single question.
3. Measure its weighted error $\risk{\varepsilon}$: the total weight of the examples it got wrong.
4. Give the model a vote $\key{\alpha}$: the lower its error, the bigger its say.
5. Increase the weight of the examples it got wrong, decrease the rest, and repeat from step 2.

The final prediction is a weighted vote of all the models.

The formulas

α, the model's voteε, its weighted errorwrong examplesright examples

The vote of model $t$:

If $\risk{\varepsilon_t} = 0.5$ (a coin flip), $\key{\alpha_t} = 0$: no say. The smaller the error, the larger $\key{\alpha_t}$.

The weight update for each example $i$, depending on whether model $t$ got it wrong or right:

$$w_i \leftarrow w_i \times \begin{cases} \bad{e^{\key{\alpha_t}}} & \bad{\text{if wrong}} \\ \good{e^{-\key{\alpha_t}}} & \good{\text{if right}} \end{cases}$$

Then all the weights are divided by their total, so they add up to 1 again.

Worked example: one round, ten trades

Ten trades, each with weight 0.1. The first stump gets 3 of them wrong:

$$\begin{aligned} \risk{\varepsilon} &= 3 \times 0.1 \\ &= \risk{0.3} \end{aligned}$$ $$\begin{aligned} \key{\alpha} &= \tfrac{1}{2} \ln\!\left(\tfrac{0.7}{\risk{0.3}}\right) \\ &= \key{0.4236} \end{aligned}$$

wrong trades are multiplied by $\bad{e^{\key{0.4236}}} = 1.5275$, right ones by $\good{e^{-\key{0.4236}}} = 0.6547$:

After one round, the 3 wrong trades carry half the total weight (3 × 0.1667 = 0.5), and the 7 right ones the other half. That’s always true after an AdaBoost update: the next model is forced to treat the previous model’s mistakes as half of its whole problem.

Notation in other books

Murphy’s Probabilistic Machine Learning: An Introduction (chapter 18, on boosting) writes the same algorithm slightly differently. He calls the vote $\key{\beta_m} = \tfrac{1}{2}\ln\big((1 - \risk{\text{err}_m}) / \risk{\text{err}_m}\big)$, and only multiplies the wrong examples, by $\bad{e^{\key{\alpha_m}}}$ with $\key{\alpha_m} = 2\key{\beta_m}$, before normalising. That’s the same result: either way, a wrong example ends up $e^{2\key{\beta}}$ times heavier than a right one.

A note on scikit-learn’s numbers

scikit-learn’s AdaBoostClassifier (version 1.9) uses the SAMME form of the algorithm. With two classes, the weight it reports is

$$\key{\alpha_t} = \ln\!\left(\frac{1 - \risk{\varepsilon_t}}{\risk{\varepsilon_t}}\right)$$

without the $\tfrac{1}{2}$. That’s exactly Murphy’s $\key{\alpha_m} = 2\key{\beta_m}$. Every vote is twice as big, so the final ranking of predictions is the same; only the printed numbers differ. If you compare a textbook with ada.estimator_weights_, that’s why.

What AdaBoost did on the stress-month data

I boosted stumps on the 3,685 training rows (2019 to 2021) of the stress-month problem: will the next 20 days’ volatility be above 30%? Only 20.5% of months are, so accuracy is misleading (saying “calm” every time scores 77.4% on the test months); that’s why the scores below are AUC. Boosting libraries also offer class weights (scale_pos_weight in XGBoost) for imbalance like this. The first three rounds:

Round 1’s stump gets the easy cases: one cut on 20-day volatility is wrong on $\risk{14.1\%}$ of the weight, far better than the 20.5% of calling everything calm. AdaBoost then gives the months it got wrong, mostly stress months that followed a calm one, half the total weight, which forces round 2 to look at them.

Round 2 asks about the same feature at a different cut-off and is wrong on 38.7% of the reweighted problem, so it earns a small vote. Round 3 moves to the price against its moving average. Each round fixes a part of what the earlier ones missed, and each gets a vote sized by how well it did on its version of the problem.

A single stump scores an AUC of 0.608 on the test months. Boosting 78 of them reaches $\key{0.795}$.

Gradient boosting: fit the leftover error

Gradient boosting (Friedman, 2001) generalises the idea. Instead of reweighting examples, each new tree is trained to predict what the current model still gets wrong.

For regression with squared error, that’s literally the residuals. An Introduction to Statistical Learning gives it as Algorithm 8.2. Start with $\hat{f}(x) = 0$ and residuals $\risk{r_i} = y_i$. Then, for each round $b = 1, 2, \dots, B$, fit a small tree $\hat{f}^b$ to the residuals and update:

λ, how much of each tree is addedr, the error left

$$\begin{aligned} \hat{f}(x) &\leftarrow \hat{f}(x) + \key{\lambda} \hat{f}^b(x) & \text{(8.10)} \\ \risk{r_i} &\leftarrow \risk{r_i} - \key{\lambda} \hat{f}^b(x_i) & \text{(8.11)} \end{aligned}$$

The final model is the sum of all the shrunken trees:

$$\hat{f}(x) = \sum_{b=1}^{B} \key{\lambda} \hat{f}^b(x) \qquad \text{(8.12)}$$

Plain meaning: start with a rough guess. Look at the errors. Train a small tree to predict the errors. Add a fraction of it to the guess. Repeat. For other losses, like the log loss used for classification, “residuals” become the negative gradient of the loss (often called pseudo-residuals), which gives the method its name. The idea is the same.

The learning rate $\key{\lambda}$ matters a lot. Each tree only corrects part of the error, so no single tree can push the model too far:

For this chart the models trained on 2019 and 2020 (2,425 rows) and kept 2021 (1,260 rows) aside as a validation set, after the fitting months, never mixed in. The number of trees to use is chosen on that validation set, never on the test set, and the dot on each line marks the round it picked. Test AUC on 2022 to 2023:

Two lessons from the chart above:

• Too high a learning rate overfits fast. At rate 1.0 each tree over-corrects. The score peaks after five trees, then falls to 0.72 by fifty as the model fits noise; the validation set stops it at 5.
• Boosting can overfit by adding trees, unlike a random forest. Even at rate 0.1 the score drifts down from 0.817 to 0.786 over 300 trees. In practice you use early stopping: watch a validation score and stop adding trees when it stops improving, which is what the dots show.

On this data the random forest (0.820) edged out the best boosting run (0.817). Common experience on tabular data is the reverse, but it isn’t a law: with few features, overlapping rows and noisy labels, forests often win because they’re harder to overfit, and that is exactly this problem.

The code

from sklearn.ensemble import AdaBoostClassifier, GradientBoostingClassifier
from sklearn.tree import DecisionTreeClassifier

ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1),   # stumps
                         n_estimators=300, learning_rate=1.0)
ada.fit(X_train, y_train)
ada.estimator_errors_[:3], ada.estimator_weights_[:3]           # epsilon and alpha per round (0.1414, 1.8038, ...)

gb = GradientBoostingClassifier(n_estimators=300, learning_rate=0.1, max_depth=3,
                                validation_fraction=0.1, n_iter_no_change=20)   # early stopping
gb.fit(X_train, y_train)
gb.n_estimators_                                                # trees actually used (42 here)

For large datasets, scikit-learn’s HistGradientBoostingClassifier, XGBoost and LightGBM are much faster versions of the same idea.

Why banks use boosted trees

• Stronger libraries. XGBoost and LightGBM add regularisation, histogram-based splits and built-in handling of missing values.
• Monotonic constraints, for example “risk can only go up as hours booked late rises”, which credit and model-risk teams like because the model can’t contradict common sense.
• Explanations. SHAP values explain an individual prediction, feature by feature.
• The trade-off: more settings to tune than a random forest, and easier to overfit.

Summary

That completes the ML basics series: what machine learning is, regression versus classification, linear regression, decision trees, bias and variance, bagging, random forests and boosting.

Next

The next series is coming soon. Until then, the finance stats series covers the probability and risk ideas these models are measured with.

References

• James, Witten, Hastie, Tibshirani and Taylor, An Introduction to Statistical Learning, with Applications in Python (Springer, 2023), section 8.2.3: boosting, Algorithm 8.2 (equations 8.10 to 8.12)
• Kevin P. Murphy, Probabilistic Machine Learning: An Introduction (MIT Press, 2022), chapter 18: AdaBoost (β and α = 2β) and gradient boosting
• Yoav Freund and Robert E. Schapire, “A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting”, Journal of Computer and System Sciences 55(1), 119–139, 1997
• Jerome H. Friedman, “Greedy Function Approximation: A Gradient Boosting Machine”, The Annals of Statistics 29(5), 1189–1232, 2001
• scikit-learn: AdaBoost and gradient boosting