Skip to main content

Gradient boosting

Examples

Boosting adds up small trees, fitted one after the other:

\[ \hat f(x) = \hat f_0 + \eta \sum_{m=1}^M \mathrm{tree}_m(x). \]

Fitting the residuals

For the squared error the algorithm is short.

  1. Start with a constant, \(\hat f_0(x) = \frac1n\sum_{i=1}^n y_i\).
  2. For \(m = 1, \ldots, M\):
    1. compute the residuals \(r_i = y_i - \hat f_{m-1}(x_i)\),
    2. fit a small regression tree \(\mathrm{tree}_m\) to the data \((x_i, r_i)\),
    3. update \(\hat f_m(x) = \hat f_{m-1}(x) + \eta\, \mathrm{tree}_m(x)\).
import numpy as np
from sklearn.tree import DecisionTreeRegressor

rng = np.random.default_rng(1)

def data_generator(n=40):
    x = rng.uniform(-4, 4, n)
    return x.reshape(-1, 1), np.sin(x) + 0.3 * rng.standard_normal(n)

def boost(X, y, rate=0.1, n_trees=100, depth=2):
    f0 = y.mean()
    fx = np.full(len(y), f0)
    trees = []
    for m in range(n_trees):
        tree = DecisionTreeRegressor(max_depth=depth).fit(X, y - fx)
        fx = fx + rate * tree.predict(X)
        trees.append(tree)
    return lambda Xnew: f0 + rate * sum(t.predict(Xnew) for t in trees)

X, y = data_generator()
Xtest, ytest = data_generator(20000)
f_hat = boost(X, y)
print("test MSE after 100 trees:", round(np.mean((f_hat(Xtest) - ytest) ** 2), 3))
1
The tree is fitted to the residuals y - fx, not to y.
test MSE after 100 trees: 0.123
Top: the training data of the decision trees page and the boosted fit after number of trees trees of depth 2. Bottom: the residuals of that fit and the next tree, fitted to them. Test errors on 20 000 new points; the irreducible error is 0.09.

The number of trees

Code
import matplotlib.pyplot as plt
from sklearn.ensemble import GradientBoostingRegressor, RandomForestRegressor

Ms = np.unique(np.logspace(0, 3, 30).astype(int))
fig, ax = plt.subplots(figsize=(6.4, 3.0))
for rate in [1.0, 0.1]:
    gb = GradientBoostingRegressor(learning_rate=rate, n_estimators=Ms[-1],
                                   max_depth=2, random_state=0).fit(X, y)
    staged = [np.mean((p - ytest) ** 2) for p in gb.staged_predict(Xtest)]
    ax.plot(Ms, [staged[m - 1] for m in Ms], label=f"boosting, rate {rate}")
forest = [np.mean((RandomForestRegressor(n_estimators=m, min_samples_leaf=3, random_state=0)
                   .fit(X, y).predict(Xtest) - ytest) ** 2) for m in Ms[::3]]
ax.plot(Ms[::3], forest, "o-", ms=3, label="random forest")
ax.axhline(0.09, color="#7a838b", ls="--", lw=1, label="irreducible error")
ax.set(xscale="log", xlabel="number of trees", ylabel="test MSE", ylim=(0.08, 0.3))
ax.legend()
plt.show()
1
staged_predict gives the predictions after 1, 2, 3, … trees, so one fit gives the whole curve.
Figure 51.1: Test error against the number of trees for a random forest and for gradient boosting with two learning rates, on the 40 training points above.

With a learning rate of 1 the best test error comes after a handful of trees and is not very good. With 0.1 the curve is lower and flatter around its minimum, so the exact number of trees matters less. The forest levels off.

GradientBoostingRegressor(n_iter_no_change=10) stops early when the loss on a validation_fraction of the training data has not improved for 10 trees.

Libraries

Besides GradientBoostingRegressor and GradientBoostingClassifier, scikit-learn has HistGradientBoostingRegressor and HistGradientBoostingClassifier, which bin the predictors first. They are much faster for large \(n\) and handle missing values. XGBoost and LightGBM are widely used libraries of the same kind.