Gradient boosting: trees that fix each other’s errors

In lesson 5.2 a random forest averaged many trees built independently of each other, and adding trees did no harm. Gradient boosting builds trees one after another. Every new tree learns the residuals, that is, how far the ensemble of trees before it is still off for each example. It adds its correction, multiplied by the learning rate, a number between 0 and 1, to the prediction. The trees are small, often with one question (a stump) or with three. On tables of medium size, tree models, with boosting in front, usually beat neural networks (Grinsztajn et al., 2022). Boosting has one trait a forest does not: later corrections can start correcting noise.

Try it

• Start where the lab opens: step 1, depth 2, 200 trees. How many steps does the ensemble's function have, and how far apart are the training and validation curves?
• Move the number of trees down. At how many trees is the validation error lowest? Only then look at the test.
• Lower the step to 0.1 and take a stump. What does the validation curve look like now as trees are added?
• Compare boosting's best validation with the dashed line of the straight line. Which one is lower?

Once you have checked it in the lab, let's name what you see.

The idea in plain words

The first tree asks a few questions about BMI and predicts the average disease progression in each group. It is wrong, so we compute the residuals: how much is missing to the truth for each patient. The second tree no longer predicts the disease, only those residuals. Its output times the learning rate is added to the first. The third tree learns what is left after two, and so on. The ensemble grows from small corrections.

At first the corrections catch the real pattern: higher BMI, more disease progression. Once the pattern is caught, what is left in the residuals is mostly noise, the random deviations of the patients the model learns from. Later trees learn exactly that. At step 1 with three-question trees, training falls from 3713 with one tree to 2287 with 200, while the test rises from 4319 to 5944. This is overfitting, as with a tree that is too deep, only this time it grows with the number of trees. In a random forest each tree sees the data on its own, and averaging cancels their errors. In boosting each tree adds itself to the errors of the ones before.

That is why the number of trees, the step and the depth are chosen by validation, not by the test. The lab computes the validation error with 5-fold cross-validation inside the 309 training patients. The lowest is a stump with step 0.1 and 50 trees: validation 3960. The straight line gets 3823 on the same validation, so on BMI alone the line wins. The test confirms it only at the end: 4154 for boosting against 4095 for the line.

Jak to policzono

• Data: Diabetes (Efron et al., 2004), in scikit-learn under the BSD-3-Clause licence. 442 patients, 10 measurements, disease progression after a year. We take BMI only. Split: 309 patients to learn from, 133 for the test.
• Model: gradient boosting with regression trees of depth 1 or 2 on BMI alone, squared loss, step 0.05 to 1, up to 200 trees; a straight-line regression on BMI for comparison. The lab's numbers match scikit-learn's GradientBoostingRegressor.
• Validation: 5-fold cross-validation inside the 309 training patients, the same folds for every setting and for the line.

Why it works

The residual y − F(x) is the direction in which the prediction must move for the squared error to fall fastest. Each tree therefore takes a small step of gradient descent, only in the space of functions instead of weights. Hence the name: gradient boosting. A small step means one tree fixes only part of the error. More trees are needed, but each adds less noise. On 20 other splits, 200 three-question trees at step 0.1 get a test MSE from 3747 to 4802, lower every time than the same trees at step 1 (from 4617 to 6983).

This does not mean boosting always beats a line. On BMI alone the link with the disease is almost linear, and trees can only imitate a line with steps. On 20 other splits, boosting chosen by validation beats the line on the test in 7. Boosting shines where there are many features and their effects are threshold-like and tangled. Then later trees catch dependencies a line cannot express.

An older relative, AdaBoost, changes the weights of the examples instead of using residuals. Examples the ensemble gets wrong weigh more in the next round. In the Atlas entry on AdaBoost, the first stump on breast tumours misclassifies 10.3% of the training tumours. Before round two those misclassified tumours carry exactly 50% of the total weight, so the second stump learns mostly from them.

A common mistake

True or false: “more boosting rounds always help”. False. Every round improves training, but the test only up to a point. At step 1 with three-question trees, 1 tree is best on validation, and 200 trees give 5944 on the test instead of 4319. In the code below the test rises from 4079 after one tree to 6437 after 200, while training falls from 3827 to 2044.

The safe route is a small step, many trees and early stopping from lesson 3.6: stop adding trees when the validation error stops falling. In the code below early stopping keeps 83 of 1000 trees.

from sklearn.datasets import load_diabetes
from sklearn.model_selection import train_test_split, cross_val_score, KFold
from sklearn.ensemble import GradientBoostingRegressor
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error as mse

X, y = load_diabetes(return_X_y=True, as_frame=True)
x_tr, x_te, y_tr, y_te = train_test_split(X[["bmi"]], y, test_size=0.3, random_state=0)
big = GradientBoostingRegressor(n_estimators=200, max_depth=2, learning_rate=1.0, random_state=0).fit(x_tr, y_tr)
for m, (p_tr, p_te) in enumerate(zip(big.staged_predict(x_tr), big.staged_predict(x_te)), start=1):
    if m in (1, 10, 50, 200):
        print(f"step 1, depth 2, {m:3d} trees: train MSE {mse(y_tr, p_tr):.0f}, test MSE {mse(y_te, p_te):.0f}")
cv = KFold(5, shuffle=True, random_state=0)
models = {"line": LinearRegression(), "step 1, 200 trees": big,
          "step 0.1, 50 stumps": GradientBoostingRegressor(n_estimators=50, max_depth=1, learning_rate=0.1, random_state=0)}
for name, model in models.items():
    val = -cross_val_score(model, x_tr, y_tr, cv=cv, scoring="neg_mean_squared_error").mean()  # validation inside the training part only
    print(f"{name}: validation MSE {val:.0f}")
stop = GradientBoostingRegressor(n_estimators=1000, max_depth=1, learning_rate=0.1, validation_fraction=0.2, n_iter_no_change=10, random_state=0).fit(x_tr, y_tr)
print(f"early stopping kept {stop.n_estimators_} of 1000 trees; test MSE {mse(y_te, stop.predict(x_te)):.0f}, line {mse(y_te, models['line'].fit(x_tr, y_tr).predict(x_te)):.0f}")

step 1, depth 2,   1 trees: train MSE 3827, test MSE 4079
step 1, depth 2,  10 trees: train MSE 3013, test MSE 4798
step 1, depth 2,  50 trees: train MSE 2122, test MSE 6233
step 1, depth 2, 200 trees: train MSE 2044, test MSE 6437
line: validation MSE 3956
step 1, 200 trees: validation MSE 5728
step 0.1, 50 stumps: validation MSE 4030
early stopping kept 83 of 1000 trees; test MSE 4062, line 3921