12. Trees That Fix Each Other's Mistakes
Summary
Boosting by hand on four houses
Gradient boosting builds small trees in sequence. Each tree is fitted to what the model so far still gets wrong, and its output is added with a small weight. A random forest instead averages many deep trees grown side by side. The lesson works a four-house example on paper. It starts from the mean price, fits a one-question stump to the residuals, and adds half of that correction. The squared error falls from 40 to 13 to 6.25. Two stumps on the same cut leave the first two houses tied, and a stump learns only one cut per round, which is why real boosting uses trees with several leaves. A small learning rate means more trees but usually generalizes better, and the number of trees is set by watching a validation score.
Why it is called gradient boosting
With squared error, the residual is the negative gradient of the loss, so each tree is a downhill step in the space of prediction functions. That is the framing in Friedman's 2001 Annals of Statistics paper. For classification, the loss is log loss, and each class's tree is fitted to the true indicator minus the predicted probability.
Boosting on MNIST
The tool is HistGradientBoostingClassifier, run on the same 50,000 training and 10,000 validation images as the forest. Features are binned into at most 255 bins, so split search adds up gradients per bin instead of sorting values. The defaults give shallow trees of up to 31 leaves. Early stopping switches on automatically at this data size and holds out 5,000 training images. After fitting, n_iter_, validation_score_ and train_score_ show what happened.
Each iteration grows ten trees, one per digit. That may shrink the speed edge over the forest, but this is reasoning, not a measurement. Published comparisons on raw MNIST pixels are thin. One informal report on unknown hardware put the histogram version near 97.1 percent in about 29 seconds, against the older GradientBoostingClassifier at about 96.3 percent in nearly twenty minutes. Raw pixels are not boosting's home ground. It does best on tables with mixed columns. XGBoost and LightGBM use the same core method.
The exercise is six runs, at learning rates 0.05, 0.1 and 0.3 with max_iter of 100 and 300. Record n_iter_, validation accuracy, fit time and predict time, then compare with the forest.
Library news
No new release of PyTorch, scikit-learn, XGBoost or LightGBM was confirmed in the past two weeks. Two earlier changes matter:
- PyTorch 2.15 makes a rewritten NCCL backend the default for multi-GPU training, with a rollback option. It drops Python 3.10 and macOS 14 for MPS. PyTorch is not yet in the lock file, so check the pinned Python and macOS version, try it in a copy of the project, and only then commit.
- XGBoost 3.3.0 deprecates gblinear, the booster that adds linear models instead of trees. Treat tutorials that use it with caution and stay with the default tree booster.
Gradient boosting, one small tree at a time
A random forest grows hundreds of deep trees side by side, each on its own resampled copy of the data, and averages their votes. Gradient boosting works the other way around. It grows small trees in a row. Each new tree is fitted to whatever the model so far still gets wrong, and it is added to the running total with a small weight. A forest cuts variance by averaging trees that make different mistakes. Boosting chips away at the error that is left, one correction after another. That steady correction is why boosted trees, through Friedman's method and later XGBoost and LightGBM, became the usual first tool for a table of rows and columns.
Last time we ended on a forest that reaches close to 97 percent on our MNIST validation images. This lesson answers two questions. How does a model learn by fixing its own leftovers? And what happens when we point scikit-learn's boosting classifier at the same 50,000 training images and 10,000 validation images?
Start with a hand case small enough to do on paper. This is an illustration, not real data. Say you have four houses. Their sizes, on some simple scale, are one, two, three and four. Their prices are one, three, seven and nine. You want to predict price from size. You will use one setting called the learning rate, the fraction of each correction you actually keep. Real libraries use something like a tenth. Here you will use one half, so each step is big enough to see.
Step one is the dumbest possible model: one number for every house. The best single number under squared error is the mean. The four prices add up to twenty, so the mean is five. Your model says five for every house.
Now look at what it gets wrong. A residual is the true value minus the prediction. For the four houses the residuals are minus four, minus two, plus two and plus four. The model guesses too high on the small houses and too low on the big ones. To measure the damage, square each residual and add them: sixteen plus four plus four plus sixteen makes forty. That is your squared error at the start.
Step two is the first tree. It is a stump, a tree with a single yes-or-no question and two leaves. The stump is not trained on the prices. It is trained on the residuals. Its job is to predict how wrong the current model is. A stump on four points has three possible cuts: between one and two, between two and three, or between three and four. Try the middle cut. The left leaf holds residuals minus four and minus two, so it predicts their mean, minus three. The right leaf holds plus two and plus four, so it predicts plus three. Inside each leaf the points miss the leaf mean by one each way, so the stump's own squared error is four. Try the cut between one and two instead. The left leaf is just minus four. The right leaf holds minus two, two and four, with a mean of about one and a third, and its squared error comes to about eighteen and two thirds. The cut between three and four mirrors that. So the middle cut wins. This is the same greedy split search from the decision-tree lesson, with squared error standing in for Gini impurity.
Now add the stump to the model, scaled by the learning rate. The small houses get five plus half of minus three, which is three and a half. The big houses get five plus half of three, which is six and a half. The new predictions are three and a half, three and a half, six and a half, six and a half.
Check the damage again. The residuals are now minus two and a half, minus a half, plus a half and plus two and a half. Squared, that is six and a quarter, a quarter, a quarter and six and a quarter, so the total is thirteen. One small tree took the error from forty to thirteen.
Step three is the second tree, and it is fitted to these new residuals. Try the middle cut again. The left leaf averages minus two and a half and minus a half, which is minus one and a half. The right leaf is plus one and a half. Each leaf misses by one, so the stump's error is four. The cut between one and two leaves a right leaf with a squared error near four and two thirds, so the middle cut wins again. Half of one and a half is three quarters. The small houses drop to two and three quarters. The big houses rise to seven and a quarter.
Check once more. Against true prices of one, three, seven and nine, the residuals are minus one and three quarters, plus a quarter, minus a quarter and plus one and three quarters. The squares are about three, a sixteenth, a sixteenth and about three, and the total is six and a quarter. So the error went forty, then thirteen, then six and a quarter.
Notice what these two stumps did not do. Both split between two and three, so after two rounds the model still says one number for the small houses and one for the big houses, and the gap between house one and house two is untouched. Score the cuts on the new residuals and the outer cuts now win, each with an error near two, so a third stump would finally start to pull those houses apart. A stump learns one cut per round. A tree with several leaves can carve several cuts in one round, and it can capture how two features work together, which a stump never can. That is why real boosting uses trees with several leaves rather than single stumps.
Why keep only half of each correction, or a tenth? Had you kept the whole stump, the first tree alone would have jumped straight to two and eight, and the next tree would chase smaller and noisier leftovers. A small learning rate means each tree only nudges the model, and many trees together build the final shape. The trade is plain. A smaller learning rate needs more trees to fit the training data equally well, and it usually generalizes better. Friedman found that rates of a tenth or less gave lower prediction error. Because the right number of trees depends on the rate, you don't guess it. You watch a validation score as trees are added and stop when it stops improving.
Now the word gradient. With squared error, the residual is exactly the negative gradient of the loss with respect to the prediction. Take one house with loss of one half times the true value minus the prediction, squared. Its slope with respect to the prediction is the prediction minus the true value. Flip the sign and you get the residual. So each tree is a step downhill on the loss, taken in the space of whole prediction functions rather than in a set of weights. That is how Friedman framed it in his 2001 paper in the Annals of Statistics. Gradient descent usually moves numbers. Boosting moves the function itself, one tree at a time.
That framing is what lets boosting classify. For classes, the loss is log loss, the same one we met with logistic regression. The model keeps a score for each class, and softmax turns the scores into probabilities. For one image and one class, the negative gradient of log loss with respect to that class's score is the true indicator minus the predicted probability. That is one if the image belongs to the class and zero if not, minus the probability. Say the model gives an image of a seven a probability of 0.6 for seven. The seven score gets a pseudo-residual of 0.4, a push upward. If it gives that image 0.3 for one, the one score gets minus 0.3, a push down. A tree is fitted to those pseudo-residuals for each class, exactly as the stumps were fitted to residuals for the houses. scikit-learn's version also uses the curvature of the loss to size each leaf's step, but the idea is the one you just worked by hand.
That brings us to MNIST. The tool is HistGradientBoostingClassifier, from sklearn.ensemble. You can reach for it directly because it ships with the scikit-learn already in the project's lock file. There is an older class, GradientBoostingClassifier, which implements the same method more slowly. The newer one wins on speed because of the histogram in its name.
Binning is that histogram. Before training begins, the classifier sorts each feature's values once and cuts them into at most 255 bins at quantiles, plus one extra bin reserved for missing values. From then on every pixel is a small integer bin number rather than a float. To find a split, the tree no longer sorts thousands of values at each node. It adds up gradients per bin, a histogram, and checks only the bin edges. For MNIST this costs almost nothing, since pixels take at most 256 values anyway. On tables with continuous columns it is a large speedup, and using fewer bins also acts as a mild brake on overfitting.
The defaults, as the current documentation lists them, are a loss of log loss, a learning rate of 0.1, max_iter of 100, max_leaf_nodes of 31, min_samples_leaf of 20, l2_regularization of zero and max_bins of 255. Compare that with the forest. Its trees grow until their leaves are pure. These trees stop at 31 leaves, and every leaf must hold at least 20 images. Boosting wants many weak, slightly wrong trees. The forest wants deep, strong ones.
One more default changes what you see. The early_stopping setting starts at "auto". That turns early stopping on when the training set has more than 10,000 rows, or when you pass separate validation data to fit. Your 50,000 rows clear that bar, so it is on. The classifier quietly sets aside its own ten percent, here 5,000 images, scores the loss on them after each iteration, and stops once ten rounds pass with no gain. So it trains on 45,000 of your 50,000 images, and max_iter becomes a ceiling rather than a count.
Here is the fit in the order you would run it. Load MNIST as before and slice the first 50,000 training images and the next 10,000 for validation, test set sealed. No scaling is needed, for the same reason as with trees: a threshold on a pixel does not care about units. Create the model with HistGradientBoostingClassifier, setting random_state to a fixed number, because the internal validation split is random. Call fit on the 50,000 images, timing it. Then call score on the 10,000 validation images, timing predict separately.
After the fit, three attributes tell you what happened. The attribute n_iter_ says how many iterations actually ran before early stopping fired. The attribute validation_score_ holds the internal validation score after each iteration. With the default scoring on the loss, it holds negative log loss, so higher is better. The attribute train_score_ holds the same for the training part. Plot both against the iteration number. Expect the training curve to keep climbing. Expect the validation curve to rise steeply, flatten, and perhaps sag a little near the end. The gap between them is the overfitting the learning rate and leaf limits are holding back.
There is a cost hidden in the ten digits. Each iteration grows not one tree but one per class, so ten. A hundred iterations means up to a thousand trees of 31 leaves. That may narrow boosting's speed advantage over the forest on MNIST. This is reasoning about the method, not a measured result, so measure it on your own machine.
The numbers to expect are not well pinned down. No careful published comparison on raw MNIST pixels sets this classifier against a random forest. One informal report, on unspecified hardware, gives about 97.1 percent accuracy in about 29 seconds for HistGradientBoostingClassifier, against about 96.3 percent in about 1,152 seconds, nearly twenty minutes, for the older GradientBoostingClassifier. That says the histogram version is far faster than the old one, on that person's setup. It says nothing about your forest. So put your own boosting run beside a forest run on the same split and the same machine, your sweep from last time if you ran it or a single default forest if not, and compare validation accuracy, fit time and predict time together.
Be clear about where boosting shines. Raw pixels are not its home ground. Neighboring pixels carry overlapping information, and the useful patterns are shapes that convolutional networks capture far better. Boosted trees win on tables with mixed columns: prices, counts, categories, dates and missing values, where each column means something on its own. MNIST is useful here because you already know what logistic regression, nearest neighbors, a single tree and a forest do on it, so you can judge boosting by the same yardstick.
XGBoost and LightGBM are the same method in other packages. Both start from a constant, fit trees to gradients of the loss, and add them with a learning rate. LightGBM also bins features into histograms, which is where scikit-learn's design came from. They differ in defaults, speed tricks and how they grow trees, not in the core idea you worked by hand.
Now your turn. Before running anything, write down a guess for each run. Then fit HistGradientBoostingClassifier on the 50,000 and 10,000 split with early stopping left on and a fixed random_state. Use learning rates of 0.05, 0.1 and 0.3, each with max_iter of 100 and then 300, which makes six runs. For each one, record n_iter_, validation accuracy, fit time and predict time. It has worked when you can say which learning rate stopped earliest, and whether the smaller rate's extra trees bought any accuracy at all, or only cost time. Expect 0.3 to stop soonest and 0.05 to hit the 100 ceiling, though your own numbers decide it. That table of six rows, set next to your forest results, is the start of a real model comparison.
Library news for your environment
Moving from your own trees to the tools under them: no new release of PyTorch, scikit-learn, XGBoost or LightGBM was confirmed in the past two weeks. The changes worth knowing arrived a little earlier, and they matter for the environment you will build on.
PyTorch 2.15, which came up a few lessons ago, has more changes worth knowing. It drops Python 3.10, and it drops macOS 14 for MPS, the backend that runs PyTorch on Apple's GPUs. It also makes a rewritten backend for NCCL the default for distributed training. NCCL is NVIDIA's library for passing gradients between GPUs, and the release keeps an option to roll back to the old backend. That change waits until you train across several cards. The first two matter sooner. The course's advice of Python 3.14 is well past 3.10, so only a Mac on macOS 14 or older loses the GPU. When PyTorch joins the lock file, run uv add torch in a copy of the project, run a small tensor on the device you expect, and only then commit the new lock file.
On the tree side, XGBoost 3.3.0 arrived on the twenty-first of July 2026, and it deprecates gblinear. That is the booster that adds linear models instead of trees at each round, the same gradient idea with straight lines in place of splits. Deprecated means it still works for now but is scheduled to go. If a tutorial you find sets the booster to gblinear, treat it as a warning sign and use the default tree booster, which is the method you worked through today.
Want a book of your own?
Gnothi wrote and narrated this chapter. Name a subject and it writes you a course, or a story that teaches it, one chapter at a time, delivered to your podcast app.
Get started free