# Gradient boosting: each tree fixes what the ensemble still gets wrong

Gradient-boosted trees, in libraries such as XGBoost, LightGBM and CatBoost, are still the method to beat on most tables of business data. The idea is simple: start with a constant, fit a small tree to the errors, add a fraction of it, and repeat a few hundred times.

<div data-sim="gboost"><p>Interactive simulation. It needs JavaScript; the text below explains what it shows.</p></div>

## What you are looking at

The points are 80 noisy training samples of the dashed curve. The blue line is the ensemble after the number of trees you choose; the orange step function at the bottom is what the last tree added, magnified four times. Every tree is a real regression tree, grown greedily on the residuals. The chart shows training and validation error as trees are added; the marker on the validation curve is its best point.

## Things to try

- Slide Trees used from 1 to 300 and watch the blue curve take shape, one correction at a time.
- Set the learning rate to 1: the first few trees fit fast, then validation error climbs while training error keeps falling.
- Use stumps (depth 1) and compare with depth 5: deeper trees fit faster and overfit sooner.
- Turn on 50% row subsampling: each tree sees half the data, which adds randomness and often helps validation error.
- Raise the noise and find where validation error is lowest: that is where early stopping would stop.

## How it works in real systems

Production libraries add much more: second-order gradients, histogram-based split finding, regularisation of leaf values, native handling of missing values and categorical features, and early stopping on a validation set. The core loop is the one here. For classification the residuals become gradients of the log-loss, which is why the method is called gradient boosting.














<!-- simx:start -->
## Key formulas

$$F_m(x)=F_{m-1}(x)+\eta\,h_m(x),\qquad h_m=\arg\min_h\sum_i\big(r_{im}-h(x_i)\big)^2,\quad r_{im}=y_i-F_{m-1}(x_i)$$

Each tree fits the residuals of the ensemble so far.

## Common mistakes

- Adding trees without early stopping: validation error eventually rises while training error keeps falling.
- Pairing a high learning rate with deep trees: each tree overshoots and the ensemble overfits within a few steps.
- Choosing the number of trees on the test set, which makes the reported score optimistic.

## Real-world numbers

- Friedman introduced gradient boosting machines in 2001.
- XGBoost (2016) added second-order gradients, regularised trees and fast split finding.
- Grinsztajn et al. (2022) found tree ensembles still beat deep learning on typical tabular benchmarks of medium size.

## Further reading

- [Greedy function approximation: a gradient boosting machine (Friedman)](https://doi.org/10.1214/aos/1013203451)
- [XGBoost: A Scalable Tree Boosting System](https://arxiv.org/abs/1603.02754)
- [Why do tree-based models still outperform deep learning on tabular data?](https://arxiv.org/abs/2207.08815)

<!-- simx:end -->

## Code lab

The same idea in real code, step by step. Copy each block into a notebook or a file and run it in order.

<div class="cl-start"></div>

### Step 1 · Boosting from scratch

Fit shallow trees to the residuals and add them with a learning rate.

```bash
pip install scikit-learn numpy
```

```python
import numpy as np
from sklearn.tree import DecisionTreeRegressor
rng = np.random.default_rng(0)
f = lambda x: np.sin(2 * np.pi * x) * (1 + x)
X = rng.random((300, 1)); y = f(X[:, 0]) + rng.normal(0, 0.3, 300)
Xtr, ytr, Xva, yva = X[:80], y[:80], X[80:], y[80:]

eta, trees = 0.1, []
pred_tr = np.full(len(ytr), ytr.mean()); pred_va = np.full(len(yva), ytr.mean())
for m in range(300):
    tree = DecisionTreeRegressor(max_depth=2).fit(Xtr, ytr - pred_tr)   # fit the residuals
    pred_tr += eta * tree.predict(Xtr); pred_va += eta * tree.predict(Xva)
    trees.append(((yva - pred_va) ** 2).mean())
best = int(np.argmin(trees))
print(f'best validation MSE {trees[best]:.4f} after {best + 1} trees')
```

### Step 2 · The library version with early stopping

scikit-learn's histogram-based booster holds out part of the data and stops when it stops improving.

```python
from sklearn.ensemble import HistGradientBoostingRegressor
model = HistGradientBoostingRegressor(learning_rate=0.1, max_depth=2, max_iter=1000,
                                      early_stopping=True, validation_fraction=0.2, n_iter_no_change=20, random_state=0)
model.fit(X[:240], y[:240])
print('trees used:', model.n_iter_)
print('test MSE:', ((model.predict(X[240:]) - y[240:]) ** 2).mean().round(4))
```

XGBoost and LightGBM work the same way: set a high maximum number of trees and let early stopping on a validation set pick the right one.

<div class="cl-end"></div>

## More simulations

[← Q-learning](/ai-simulations/q-learning-gridworld) · [All AI Simulations](/ai-simulations) · [Bayesian optimisation →](/ai-simulations/bayesian-optimisation)
