ML5.6 · LESSON 6 OF 6

Boosting

Choose a split by impurity reduction and distinguish bagging, random forests and boosting.

THE IDEA

Fix what is still wrong

Bagging trains models independently. Boosting trains them in sequence, each one aimed at the mistakes of the ensemble so far. For regression with squared error the recipe is short:

Gradient boosting for squared error

F0(x)  = mean(y)                          # start with a constant
repeat for m = 1..M:
    r_i = y_i - F_{m-1}(x_i)              # residuals: what is still wrong
    h_m = a small tree (here a stump) fitted to r
    F_m(x) = F_{m-1}(x) + eta * h_m(x)    # eta is the learning rate

For the loss ½(y − F)² the residual y − F is exactly the negative slope of the loss with respect to F, which is why this is called gradient boosting: each stump is one step of gradient descent, taken in the space of functions instead of the space of parameters. A stump is a tree with a single cut, a very weak model on its own. The sum of many is not.

Step through it

Top: data (orange), current model F (green), the red segments are the residuals y - F. Bottom: those residuals alone, and the stump that the next round will fit to them.

Learning rate:

Rounds 0

train MSE 1.32held-out MSE 1.694

next stump on the residuals: x ≤ 3.85 → 1.188, else -0.345 it is added with weight 0.5: F moves by 0.594 on the left, -0.172 on the right

Press Step. The red dots in the lower plot are the residuals, the purple step is the stump fitted to them, and the green curve above moves by eta times that step.

The first round learns the biggest gap, and later rounds chip at what is left. With learning rate 1 the training MSE drops from 1.32 to 0.28 in 3 rounds. With learning rate 0.1 it takes 26 rounds just to reach 0.445. A small step is slower, but each step is less likely to chase noise.

Predict first. Training error keeps falling every round. Does the held-out error keep falling too?

Knobs and the common mistake

Learning rate: smaller steps need more rounds but usually generalise better.
Tree capacity (stump, depth 3, ...): bigger trees fit more per round and overfit faster.
Number of rounds / early stopping: stop when held-out error stops improving.

Learning rate 0.5 reaches a held-out MSE of 0.554 after 30 rounds on this data.

Chapter context

A decision tree recursively asks questions that partition data. An ensemble combines many models to improve behavior, but the way those models are trained determines what kind of errors the combination can reduce.

TRY IT YOURSELF

Part 1. Do it by hand

Pick the learning rate and step or slide the rounds. The tasks tick from the real boosting run on 40 training points, with 300 held-out points for the held-out column.

Top: data (orange), current model F (green), the red segments are the residuals y - F. Bottom: those residuals alone, and the stump that the next round will fit to them.

Learning rate:

Rounds 0

train MSE 1.32held-out MSE 1.694

next stump on the residuals: x ≤ 3.85 → 1.188, else -0.345 it is added with weight 0.5: F moves by 0.594 on the left, -0.172 on the right

To do: With learning rate 1, get the training MSE to 0.3 or lower in as few rounds as you can (at most 6)
To do: With learning rate 0.1, find the first round where the training MSE reaches 0.45 or lower
To do: Use a learning rate of 0.5 or smaller and get the held-out MSE to 0.56 or lower
To do: Overfit on purpose: learning rate 1 and at least 60 rounds, until held-out MSE is 10% or more above its best value so far

Part 2. Do it in code

fit_stump(x, r) finds the single threshold t minimising the squared error when the left side (x <= t) predicts its mean of r and the right side predicts its mean. Return (t, left_value, right_value). Candidates are midpoints between neighbouring distinct x values; ties go to the smallest threshold. If x is constant return (None, m, m) with m the mean of r.
stump_predict(stump, x) returns the stump output for each x (an array).
gradient_boost(x, y, n_rounds, lr) starts from F = mean(y). Each round: residual = y - F, fit a stump to the residual, then F = F + lr * stump(x). Return (f0, stumps).
boost_predict(f0, stumps, lr, x) returns f0 plus lr times every stump, for the new inputs x.

import numpy as np

def fit_stump(x, r):
    pass

def stump_predict(stump, x):
    pass

def gradient_boost(x, y, n_rounds, lr):
    # returns (f0, list_of_stumps)
    pass

def boost_predict(f0, stumps, lr, x):
    pass

x = np.array([1.0, 2.0, 3.0, 4.0, 5.0, 6.0])
y = np.array([1.0, 1.0, 1.0, 5.0, 5.0, 5.0])
f0, stumps = gradient_boost(x, y, 3, 0.5)
print(boost_predict(f0, stumps, 0.5, x))

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Are boosting stages trained independently in arbitrary order?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

G(p)=1-\sum_kp_k^2,\quad \Delta G=G_{parent}-\frac{n_L}{n}G_L-\frac{n_R}{n}G_R.

A boosted additive model has the form $F_{t+1}(x)=F_t(x)+\eta h_t(x)$ . The stage target depends on the loss and boosting method.

Worked example

A parent contains three red examples and one blue example. Its Gini is 1−0.75²−0.25²=0.375. Split into a left child with two red examples and a right child with one red and one blue. Weighted child Gini is 2/4×0 + 2/4×0.5 = 0.25, giving gain 0.125.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
gini = lambda counts: 1-sum((n/sum(counts))**2 for n in counts)
parent = gini([3,1])
children = .5*gini([2,0]) + .5*gini([1,1])
assert isclose(parent, .375)
assert isclose(children, .25)
assert isclose(parent-children, .125)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Feature importance is not causal influence. A pure training leaf need not generalize. Bagging and boosting are different training strategies, not interchangeable names for averaging.