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, including the popular XGBoost and LightGBM libraries, are built on the same idea, so it is worth knowing what they do.

Bagging vs boosting in one picture

In the bias and variance terms of Table 1: 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 rows

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

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

wrong rows are multiplied by $\bad{e^{\key{0.4236}}} = 1.5275$, right ones by $\good{e^{-\key{0.4236}}} = 0.6547$ (Table 2):

After one round, the 3 wrong rows carry half the total weight ($3 \times 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 (section 18.5.3, equations 18.30 and 18.34) 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 4,930 training rows (2020 to 2023) of the stress-month problem: will the next 20 days’ volatility be above 30%? 36.8% of training rows had a stress month ahead but only 24.1% of test rows, so accuracy is misleading (saying “calm” every time scores 75.9% on the test rows); that’s why the scores below are AUC (0.5 is a coin flip, 1.0 is perfect). Boosting libraries also offer class weights (scale_pos_weight in XGBoost) for rarer classes than this. The first three rounds are in Table 3:

Round 1’s stump gets the easy cases: one cut on 20-day volatility is wrong on $\risk{18.7\%}$ of the weight, far better than the 36.8% of calling everything calm. AdaBoost then gives the rows 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 39.7% of the reweighted problem, so it earns a much smaller vote. Round 3 stays on 20-day volatility at a third cut-off, is wrong on 37.5%, and earns a vote a little larger than round 2’s. 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.824 on the test rows. Boosting 81 of them reaches $\key{0.895}$.

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

$$\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)}$$

The final model is the sum of all the shrunken trees (symbols in Table 4):

$$\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 (Figure 1):

For Figure 1 the models trained on 2020 to 2022 (3,680 rows) and kept 2023 (1,250 rows) aside as a validation set, after the fitting rows in time, 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 2024 to 2025 (Table 5):

Two lessons from Figure 1:

• Too high a learning rate overfits fast. At rate 1.0 each tree over-corrects. The score peaks after a handful of trees, then falls to 0.85 by fifty and 0.84 by three hundred as the model fits noise; the validation set stops it at 3.
• Boosting can overfit by adding trees, unlike a random forest. Even at rate 0.1 the score drifts down from 0.898 at fifty trees to 0.882 at 300. In practice you use early stopping: watch a validation score and stop adding trees when it stops improving, which is what the dots show. Here the 2023 validation year stopped rate 0.1 at three trees, well before the test curve’s best (0.898 at fifty); the validation year is not the test years, and that gap is the price of choosing without looking at the test set.

On this data the three finish within 0.004 of each other: AdaBoost 0.895, gradient boosting 0.891, random forest 0.891, a gap small enough to be noise. With few features, overlapping rows and noisy labels, the model that is harder to overfit is the safer bet, and ISLP notes the same difference: random forests do not overfit as trees are added, while boosting can.

The code

The worked example by hand, then both kinds of boosting on made-up data, so it runs as pasted (pip install numpy scikit-learn). X holds two features, this month’s volatility and return; y the answer, 1 if a stress month followed. The first 3,000 rows train, the last 1,000 test.

import numpy as np
import sklearn
from sklearn.ensemble import AdaBoostClassifier, GradientBoostingClassifier
from sklearn.metrics import roc_auc_score
from sklearn.tree import DecisionTreeClassifier

# 1. One AdaBoost round by hand: ten rows, weight 0.1 each, three of them wrong
w = np.full(10, 0.1)
wrong = np.array([True] * 3 + [False] * 7)
eps = w[wrong].sum()                                  # weighted error: 0.3
alpha = 0.5 * np.log((1 - eps) / eps)                 # the model's vote: 0.4236
w = w * np.where(wrong, np.exp(alpha), np.exp(-alpha))
w = w / w.sum()                                       # back to a total of 1
print(f"error {eps:.1f}, vote {alpha:.4f}, wrong rows now {w[0]:.4f}, right rows {w[-1]:.4f}, "
      f"wrong rows' share {w[wrong].sum():.1f}")

# 2. Boosting on made-up data: two features, stress is rare
rng = np.random.default_rng(0)
n = 4000
X = np.c_[rng.uniform(5, 50, n), rng.normal(0, 5, n)]          # [volatility, return]
y = ((X[:, 0] / 50 - X[:, 1] / 40 + rng.normal(0, 0.2, n)) > 0.8).astype(int)
X_train, X_test, y_train, y_test = X[:3000], X[3000:], y[:3000], y[3000:]

ada = AdaBoostClassifier(DecisionTreeClassifier(max_depth=1), n_estimators=100, random_state=0)
ada.fit(X_train, y_train)                             # each round: a stump on reweighted rows
print("AdaBoost: first three errors", np.round(ada.estimator_errors_[:3], 3),
      "and weights", np.round(ada.estimator_weights_[:3], 3))
print("AdaBoost test AUC", round(roc_auc_score(y_test, ada.predict_proba(X_test)[:, 1]), 3))

gb = GradientBoostingClassifier(n_estimators=300, learning_rate=0.1, max_depth=3,
                                validation_fraction=0.1, n_iter_no_change=20, random_state=0)
gb.fit(X_train, y_train)                              # stops when the held-back 10% stops improving
print("gradient boosting used", gb.n_estimators_, "of 300 trees, test AUC",
      round(roc_auc_score(y_test, gb.predict_proba(X_test)[:, 1]), 3))
print("scikit-learn", sklearn.__version__)

It prints the worked example’s numbers: error 0.3, vote 0.4236, the wrong rows at 0.1667, the right ones at 0.0714, and the wrong rows’ share at exactly 0.5. Then the first three AdaBoost rounds, each with its weighted error and scikit-learn’s weight. Check one: an error of 0.192 gives $\ln(0.808 / 0.192) = 1.437$, the SAMME weight without the $\tfrac{1}{2}$. Then the test AUCs, about 0.90 for both, and the number of trees early stopping kept (about 77 of 300). The last line prints the scikit-learn version, 1.9 when this was written.

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

The script behind the real numbers

The tables and the chart come from examples/boosting/boosting.py, which runs on the blog’s five tickers. To run it yourself, clone the examples repo: its README has a three-command Docker setup, or run uv run boosting/boosting.py.

What the big libraries add

• Speed and extras. XGBoost and LightGBM add penalties on tree size (regularisation), histogram-based splits (faster, by bucketing each feature’s values) and built-in handling of missing values.
• Monotonic constraints, for example “predicted risk can only go up as a borrower’s debt goes up”, so the model can’t contradict a rule everyone agrees on.
• Explanations. SHAP values split one prediction into a contribution from each feature.
• The trade-off: more settings to tune than a random forest, and easier to overfit.

Summary

Table 6 is the post in six lines.

That is the last model in the Machine Learning Series 1. One post remains: putting all of them side by side.

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) and the typical learning rates of 0.01 or 0.001
• Kevin P. Murphy, Probabilistic Machine Learning: An Introduction (MIT Press, 2022), section 18.5: boosting; section 18.5.3: AdaBoost, its vote β (equation 18.30) and weight update (18.34)
• 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