Boosting: AdaBoost and Gradient Boosting

Definition

Can many weak learners, each fixing the last one's mistakes, become strong?

Boosting builds an ensemble sequentially, each new weak model focusing on the errors of the ensemble so far. AdaBoost re-weights training examples, increasing the weight of misclassified ones. Gradient boosting fits each new tree to the negative gradient of the loss (for squared error, the residuals) and adds it with a learning rate: Fₘ = Fₘ₋₁ + η·hₘ.

In simple words

The first small tree makes a rough guess. The second tree learns only what the first got wrong. The third fixes what's still wrong, and so on. A small learning rate means each tree only corrects a little, which needs more trees but generalises better.

Why it matters

Gradient boosting is the most successful method for tabular data in industry and competitions, behind fraud detection, credit scoring, ranking and demand forecasting.

How it works

	Bagging / random forest	Boosting
Trees built	Independently, in parallel	Sequentially
Each tree	Deep, low bias, high variance	Shallow, high bias
Mainly reduces	Variance	Bias
Overfits with more trees?	Rarely	Yes: use early stopping

The maths

Additive model built stage by stage

F_{m} (x) = F_{m - 1} (x) + η h_{m} (x)

Each tree fits the negative gradient (pseudo-residuals)

r_{im} = - [\frac{\partial L ( y _{i} , F ( x _{i} ))}{\partial F ( x _{i} )}]_{F = F_{m - 1}} = y_{i} - F_{m - 1} (x_{i}) for squared error

AdaBoost model weight

α_{m} = \frac{1}{2} ln \frac{1 - ε _{m}}{ε _{m}}

$ε_{m}$: Weighted error of the m-th weak learner

In code

Gradient boosting from scratch on residuals for a regression curve, then AdaBoost and gradient boosting classifiers improving stage by stage.

boosting.py

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import AdaBoostClassifier, GradientBoostingClassifier
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(0)
x = np.sort(rng.uniform(0, 6, 200)).reshape(-1, 1)
y = np.sin(x).ravel() + rng.normal(scale=0.2, size=200)
prediction = np.full_like(y, y.mean())
for m in range(1, 51):
    residuals = y - prediction                                   # negative gradient of squared error
    stump = DecisionTreeRegressor(max_depth=2).fit(x, residuals)
    prediction += 0.1 * stump.predict(x)
    if m in (1, 10, 50):
        print(f"From scratch, {m:>2} trees: MSE {np.mean((y - prediction) ** 2):.3f}")

X, yc = load_breast_cancer(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, yc, test_size=0.3, random_state=0)
ada = AdaBoostClassifier(n_estimators=200, random_state=0).fit(X_tr, y_tr)
gb = GradientBoostingClassifier(n_estimators=200, learning_rate=0.1, max_depth=2, random_state=0).fit(X_tr, y_tr)
print("AdaBoost test accuracy:", round(ada.score(X_te, y_te), 3))
staged = [np.mean(p == y_te) for p in gb.staged_predict(X_te)]
for m in (1, 10, 50, 200):
    print(f"Gradient boosting after {m:>3} trees: {staged[m - 1]:.3f}")

Output

From scratch,  1 trees: MSE 0.437
From scratch, 10 trees: MSE 0.119
From scratch, 50 trees: MSE 0.032
AdaBoost test accuracy: 0.988
Gradient boosting after   1 trees: 0.632
Gradient boosting after  10 trees: 0.930
Gradient boosting after  50 trees: 0.947
Gradient boosting after 200 trees: 0.971

Try it yourself

Boosting step by step

Put one round of gradient boosting for regression in order.

1Repeat with the new residuals
2Start with a constant prediction: the mean of y
3Compute residuals: true value minus current prediction
4Add the tree's output, scaled by the learning rate
5Fit a small tree to the residuals

Common mistakes

Using a large learning rate and many trees without early stopping.
Growing deep trees inside boosting; shallow trees (depth 2 to 6) work best.
Confusing boosting with bagging: boosting is sequential and can overfit.

Check yourself

1. In gradient boosting with squared error, each tree fits…

2. What does round two of AdaBoost focus on?

3. A smaller learning rate usually needs…

Summary

Boosting adds weak models in sequence, each fixing earlier errors.
Gradient boosting fits the negative gradient: Fₘ = Fₘ₋₁ + η·hₘ.
Use shallow trees, a small learning rate and early stopping.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: scikit-learn: Gradient boosting · Friedman, Greedy Function Approximation (2001)