Skip to the lesson
ML Explorer Reju Sam John

ML Explorer · Level 3 · Classic ML

Gradient boosting

Add small trees one at a time, each fitted to what the model still gets wrong.

About 12 minutes · No maths needed; the maths is there if you want it

Overview

In bagging and random forests, many trees are grown side by side and their answers averaged. Boosting grows trees one after another instead. Each new tree is tiny, and its job is to fix what the trees before it still get wrong.

We use the wave data from Overfitting and regularisation, with more points. We start with one tiny tree, look at what it misses, add a second, then add hundreds and watch training and test error. We finish with the reason for the word "gradient".

The points are made up. See "About the data" at the end.

You'll learn

  • how boosting builds a model round by round, each small tree fitted to the residuals of the model so far
  • why training error keeps falling while test error turns back up, and how the learning rate η and the number of rounds M work together
  • why the residuals are a gradient, which puts the "gradient" in gradient boosting
  1. A stump: one split, two flat levels

    A stump is the smallest possible tree: one question, two answers. On its own it is a poor fit.

    A stump asks one question, "is x below some value s?", and gives one flat prediction for yes and another for no. Each level is the mean of y on its side. The split s goes wherever the two levels fit the points best, with the lowest MSE.

    That is a big step up from the mean, but a stump can only say "low" or "high". It cannot follow the rise and fall of the wave.

    The maths

    A stump with split ss and levels aa and bb is

    h(x)={aif x<sbif x≥sh(x) = \begin{cases} a & \text{if } x < s \\ b & \text{if } x \ge s \end{cases}

    For a given ss, the sum of squares ∑i(yi−h(xi))2\sum_i (y_i - h(x_i))^2 is smallest when aa and bb are the means of the yiy_i on each side. The page tries every ss midway between neighbouring xx values and keeps the one with the smallest sum. This is a least-squares stump.

    The starting model is the mean, with n=40n = 40:

    F0=yˉ=1n∑i=1nyiF_0 = \bar{y} = \frac{1}{n}\sum_{i=1}^{n} y_i

    Its training MSE, 1n∑i(yi−yˉ)2\frac{1}{n}\sum_i (y_i - \bar{y})^2, is the population variance of yy (dividing by nn, not n−1n - 1).

    Strictly, the stump on the plot is F1=F0+h1F_1 = F_0 + h_1, where h1h_1 is the best stump fitted to yi−yˉy_i - \bar{y}. That is the same as a stump fitted to yiy_i itself: shifting every value by yˉ\bar{y} shifts both levels by yˉ\bar{y} and leaves every split's sum of squares unchanged.

  2. What's left over

    Draw a stick from each point to the model. The sticks are what the model still gets wrong.

    Each stick is a residual, rᵢ = yᵢ − F₁(xᵢ): the point's y minus the model's prediction there. It is positive when the point is above the model and negative when it is below. Earlier lessons wrote a residual as eᵢ; with boosting it is usually written rᵢ.

    The right-hand plot shows the same residuals standing on a line at 0. They have a pattern. On the far right, most points sit below the stump, because the wave turns down there and the stump stays flat.

    A pattern in the leftovers is something another stump can fit.

    The maths

    After m−1m - 1 rounds, the residual of training point ii is

    rmi=yi−Fm−1(xi)r_{mi} = y_i - F_{m-1}(x_i)

    and the training MSE of Fm−1F_{m-1} is 1n∑irmi2\frac{1}{n}\sum_i r_{mi}^2. This is the residual ei=yi−y^ie_i = y_i - \hat{y}_i of earlier lessons, with y^i=Fm−1(xi)\hat{y}_i = F_{m-1}(x_i).

  3. Fit the next stump to the residuals

    Fit a second stump, not to y but to the residuals. Then add it to the model.

    That is the whole method: fit a stump to the residuals, add it, work out the new residuals, and repeat. Each repeat is called a round.

    In practice you add only a fraction of each stump: η times it, where η (eta) is a small number such as 0.1. η is the learning rate. It plays the same role as the learning rate in gradient descent: it sets the size of each step. In these first three steps η = 1, so each change is easy to see. From the next step on, η = 0.1 (step 5 lets you change it).

    The maths

    Round mm fits a least-squares stump hmh_m to the pairs (xi,rmi)(x_i, r_{mi}) and adds η times it:

    Fm(x)=Fm−1(x)+η hm(x)F_m(x) = F_{m-1}(x) + \eta\, h_m(x)

    After MM rounds the model is the mean plus a sum of shrunken stumps:

    FM(x)=yˉ+η∑m=1Mhm(x)F_M(x) = \bar{y} + \eta \sum_{m=1}^{M} h_m(x)
  4. Many rounds

    Repeat for many rounds. The staircase gets finer, and the training error falls every round.

    Now η = 0.1. Slide M, the number of rounds, from 0 to 300. Each round adds one more small stump, so the staircase can follow the wave more and more closely.

    The chart on the right shows both errors against M, on a log scale. The training curve (solid) only goes down. That is guaranteed here, not luck: each stump is the best two-level fit to the residuals, and adding η times it, for any η between 0 and 2, cannot make the training MSE go up. The maths has the one-line reason.

    On this data the training MSE falls in every one of the 300 rounds, for every η on the slider in the next step.

    The maths

    Claim. With least-squares stumps and 0<η<20 < \eta < 2, the training MSE never rises from one round to the next.

    Write r\mathbf{r} for the residuals at the nn training points and h\mathbf{h} for the new stump's values there. Each level is the mean of the residuals on its side, so on each side the residuals minus the level add up to 0. Multiply each side's sum by its level and add: (r−h)⋅h=0(\mathbf{r} - \mathbf{h})\cdot\mathbf{h} = 0, that is, r⋅h=∥h∥2\mathbf{r}\cdot\mathbf{h} = \lVert\mathbf{h}\rVert^2. (The stump is a least-squares projection of the residuals.) The new residuals are r−ηh\mathbf{r} - \eta\mathbf{h}, so

    ∥r−ηh∥2=∥r∥2−2η r⋅h+η2∥h∥2=∥r∥2−η(2−η)∥h∥2\lVert\mathbf{r} - \eta\mathbf{h}\rVert^2 = \lVert\mathbf{r}\rVert^2 - 2\eta\,\mathbf{r}\cdot\mathbf{h} + \eta^2\lVert\mathbf{h}\rVert^2 = \lVert\mathbf{r}\rVert^2 - \eta(2 - \eta)\lVert\mathbf{h}\rVert^2

    For 0<η<20 < \eta < 2, η(2−η)>0\eta(2 - \eta) > 0, so the sum of squares, and with it the MSE, cannot rise. It stays the same only if the stump is 0 everywhere. At η=2\eta = 2 the step overshoots so far that the MSE comes back to exactly where it started, and above 2 it rises.

  5. When to stop

    The test error does not keep falling. It reaches a lowest point, then creeps back up.

    After the lowest point, new stumps mostly chase noise: the random scatter of these 40 points around the wave, which new points do not share. That is overfitting, as in Overfitting and regularisation, and the remedy is to stop early.

    Choosing M by looking at the test points, as the chart does, is a simplification for the picture. In practice you choose M with a validation set or cross-validation (see Train, validate, test), and keep the test set for one final check.

    The maths

    The test MSE of FMF_M is 1300∑j(yj−FM(xj))2\frac{1}{300}\sum_{j} (y_j - F_M(x_j))^2 over the 300 test points. The training and test curves are worked out once for each η, for every MM from 0 to 300, so moving the M slider only looks values up.

    The noise in this data has variance 0.252=0.06250.25^2 = 0.0625. On average over new points, no model can get its MSE below that.

  6. Why "gradient"?

    The residuals are not just leftovers. They point downhill on the loss, one number per training point.

    Score the prediction F at one training point with the loss ½(yᵢ − F)², half the squared error. If F is too low, raising it lowers the loss; if F is too high, lowering it does. The slope of this loss with respect to F is −(yᵢ − F). So the downhill direction, the negative gradient, is yᵢ − F: exactly the residual.

    So each round is like a step of gradient descent, where what moves is the model's predictions rather than a weight. This is a simplification. The negative gradient is only known at the 40 training points, so boosting approximates it with a stump, which also says what to do between and beyond them, and then steps η times that stump.

    Change the loss and the recipe still works: fit each stump to the new loss's negative gradient instead of the residual. That is how gradient boosting does classification, using the log-loss from logistic regression.

    The maths

    With the loss L(y,F)=12(y−F)2L(y, F) = \tfrac{1}{2}(y - F)^2,

    −∂L∂F∣F=Fm−1(xi)=yi−Fm−1(xi)=rmi-\frac{\partial L}{\partial F}\bigg|_{F = F_{m-1}(x_i)} = y_i - F_{m-1}(x_i) = r_{mi}

    Treat the nn predictions F(x1),…,F(xn)F(x_1), \dots, F(x_n) as the things being learned. The total loss is ∑iL(yi,F(xi))\sum_i L(y_i, F(x_i)), and a gradient descent step on those nn numbers would move each one by η rmi\eta\, r_{mi}. That step only changes the predictions at the training points. Boosting replaces r\mathbf{r} by the stump that fits it best, hmh_m, and steps along that: Fm=Fm−1+η hmF_m = F_{m-1} + \eta\, h_m.

    For another loss, rmir_{mi} is replaced by −∂L/∂F-\partial L / \partial F at Fm−1(xi)F_{m-1}(x_i), and the rest of the recipe is unchanged.

Quick check

What does each new stump try to fit?

Only the first stump is fitted to y (after taking off the mean). Fitting y again would give the same stump every round.

Right. Each stump is fitted to rᵢ = yᵢ − F(xᵢ), what the model so far still gets wrong. For squared error, that is also the negative gradient of the loss.

Every training point is used in every round. Points the model already fits well have small residuals, so they pull the next stump less.

The test points are never used for fitting. They are kept aside to check the model on points it has not seen.

Why might you stop early?

With least-squares stumps and 0 < η < 2, the training error never rises. That is exactly why it cannot tell you when to stop.

Right. With η = 0.1, the test MSE (on held-out data) is lowest at M = () and is by M = 300, while the training MSE keeps falling. The later stumps fit noise.

There is always a split to make: 40 points have 39 gaps between them, and the residuals change every round. The rounds never run out.

η and M are separate settings. Stopping early changes M, not η. A smaller η usually needs more rounds, not fewer.

Lesson complete

  • Boosting builds a model as a sum: start from the mean, then add η times a small tree, round after round.
  • Each tree is fitted to the residuals of the model so far. For squared error, the residuals are the negative gradient of the loss.
  • With least-squares stumps and 0 < η < 2 the training error never rises, but the test error has a lowest point, so the number of rounds M is chosen on held-out data.
  • A smaller η takes smaller steps and needs more rounds.

Common misconceptions

  • "More rounds is always better." The training error keeps falling, but the test error turns back up.
  • "Boosting averages independent trees, like a random forest." Its trees are built one after another, and each depends on the ones before it.
Next lesson: k-means clustering →

Further reading

  1. James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning (2nd ed.), Section 8.2.3, "Boosting", which boosts small regression trees by fitting each one to the current residuals. It calls η the shrinkage parameter and writes it λ, writes the number of trees as B, and notes that boosting can overfit if B is too large.
  2. Hastie, Tibshirani & Friedman, The Elements of Statistical Learning (2nd ed.), Section 10.10, "Numerical Optimization via Gradient Boosting", which presents boosting as steepest descent with each step approximated by a tree, and Section 10.12.1, "Shrinkage".

About the data. The points are made up. For each point, x is drawn uniformly between −1 and 1, then y = sin(πx) + 0.25 z, where z is a draw from a normal distribution with mean 0 and SD 1, made with mulberry32. The 40 training points use seed 91 and the 300 test points seed 92. The mean and every MSE divide by the number of points. Stumps split midway between neighbouring x values. The page runs 300 rounds once for each η and keeps every round. Displayed values are rounded; the calculations are not.

If this helped, you can .