ML Explorer · Level 3 · Classic ML
Gradient boosting
Add small trees one at a time, each fitted to what the model still gets wrong.
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
-
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.
There are 40 training points (cyan circles), scattered around a wave. Boosting starts from the plainest model there is: predict the mean of y everywhere. Call it F₀. Here F₀ = , the dotted line, and its training MSE is .
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.
The best stump splits at x = , the dashed line. It predicts to the left and to the right. Training MSE falls from to .
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 and levels and is
For a given , the sum of squares is smallest when and are the means of the on each side. The page tries every midway between neighbouring values and keeps the one with the smallest sum. This is a least-squares stump.
The starting model is the mean, with :
Its training MSE, , is the population variance of (dividing by , not ).
Strictly, the stump on the plot is , where is the best stump fitted to . That is the same as a stump fitted to itself: shifting every value by shifts both levels by and leaves every split's sum of squares unchanged.
-
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ᵢ.
Square every stick's length and take the mean: that is the training MSE, .
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 rounds, the residual of training point is
and the training MSE of is . This is the residual of earlier lessons, with .
-
Fit the next stump to the residuals
Fit a second stump, not to y but to the residuals. Then add it to the model.
The new stump, h₂, is the dashed violet line on the right. It splits at x = . To the left it is , a small lift. To the right it is , which pulls the model down where the wave turns down.
Adding it gives the new model, F₂ = F₁ + h₂ (η = 1 here). On the left, the old model is dashed and the new one solid. Training MSE falls from to .
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 fits a least-squares stump to the pairs and adds η times it:
After rounds the model is the mean plus a sum of shrunken stumps:
-
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.
At M = 20 the training MSE is . The test MSE, on 300 new points from the same source (violet squares), is . By M = 300 the training MSE is down to .
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 , the training MSE never rises from one round to the next.
Write for the residuals at the training points and 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: , that is, . (The stump is a least-squares projection of the residuals.) The new residuals are , so
For , , so the sum of squares, and with it the MSE, cannot rise. It stays the same only if the stump is 0 everywhere. At the step overshoots so far that the MSE comes back to exactly where it started, and above 2 it rises.
-
When to stop
The test error does not keep falling. It reaches a lowest point, then creeps back up.
With η = 0.1, the test MSE is lowest at M = , where it is (the ring on the chart). By M = 300 it has crept up to , while the training MSE has kept falling, to .
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.
Now move the η slider. Smaller steps need more rounds. The test MSE is lowest at M = for η = 0.05, for 0.1, for 0.3 and for 1.
The three smaller values of η all get down to about the same test MSE, . η = 1 rushes: its lowest is , after only rounds.
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 is over the 300 test points. The training and test curves are worked out once for each η, for every from 0 to 300, so moving the M slider only looks values up.
The noise in this data has variance . On average over new points, no model can get its MSE below that.
-
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.
The plot shows the model after 10 rounds with η = 0.1. Each stick on the right is one point's residual: how far, and which way, that point's loss says its prediction should move. The next stump, dashed, splits at x = .
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 ,
Treat the predictions as the things being learned. The total loss is , and a gradient descent step on those numbers would move each one by . That step only changes the predictions at the training points. Boosting replaces by the stump that fits it best, , and steps along that: .
For another loss, is replaced by at , and the rest of the recipe is unchanged.
Quick check
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.
- "A smaller η is always better." It needs many more rounds for about the same result: here the best M is at η = 0.05 against at η = 0.1, with the same lowest test MSE, , to three decimals.
Further reading
- 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.
- 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 .