Index Ai Academy
Phase 3 · Models

Gradient boosting in depth

Boosting built from scratch: trees fit to the gradient of the loss, depth and interactions, learning rate against number of trees, early stopping, and what XGBoost and LightGBM add.

About 45 minutes · A free account opens the whole lesson.
Already have an account? Sign in to open this lesson

What it covers6

Why it matters

On tables of data, with rows and columns of mixed kinds, gradient-boosted trees are still the model to beat. They win most competitions on that kind of data, and they sit inside a great many fraud, pricing, ranking and churn systems. Random forests and boosting gave you the idea in one section. This lesson builds the whole machine: about thirty lines of NumPy, and then every dial on it, so that the settings of a library such as XGBoost or LightGBM stop being a list to copy and become choices you can reason about.

What you'll be able to do

  • Build gradient boosting from scratch: fit a small tree to what is still wrong, and add a fraction of it
  • Explain the word gradient: which leftovers to fit for squared error and for log loss
  • Choose tree depth by the interactions the model has to express
  • Trade learning rate against the number of trees, and stop on validation data
  • Say what XGBoost, LightGBM and CatBoost add, and what their main settings do
Quick check
A guess before you start. A model predicts 60 for a house that sold for 100. You may add one more small model on top of it. What should the small model be trained to predict?
  1. The average price of all houses
  2. The price again: 100
  3. The current prediction: 60
  4. The leftover: 40
Show the answer

The leftover: 40

The first model already supplies 60. What it lacks is 40, so a second model that predicts 40 for this house, added on top, gives 100. Training each new model on what the models so far still get wrong is the whole idea of boosting. Everything else in this lesson is about doing that carefully.

The idea: fit what is left, then add a fraction of the fix

This lesson rests on The gradient (Foundation lesson 78) and Gradient descent (Foundation lesson 79): the leftover each tree fits is the downhill direction of a loss, and each tree is a step of that descent. It builds on Random forests and boosting, which gave the idea in one section.

Fitting what is left

The whole method in three lines:

  1. Start with one prediction for every row: the average of the target.
  2. Work out the leftover for every row: the target minus the current prediction. (The usual name is the residual.)
  3. Fit a small tree to the leftovers, and add a fraction of it to the prediction. Go back to step 2.

The tree here is as small as a tree gets: one question, two answers. That is called a stump. best_split finds the question. It tries every threshold on every feature, and keeps the one that removes the most squared error when each side is replaced by its own mean.

The cell below uses the three helpers of this lesson, best_split, fit_tree and predict_tree, which sit in the lesson's setup (the next part shows them in full). It plays the three-line method on six points: targets 2, 3, 3, 7, 8 and 9 at x = 1 to 6, stumps added at half their size.

Setup (runs before every cell) · 88 lines

The lesson runs this once, before its first cell, and every cell, drill and example starts with what it defines. A cell that changes a setup object changes it for the cells after it, until the page reloads.

import numpy as np

def best_split(X, r):
    """The feature and threshold that best separate rows with high leftovers from
    rows with low ones."""
    best, total, n = (1e-9, None, None), r.sum(), len(r)
    for f in range(X.shape[1]):
        order = np.argsort(X[:, f])
        x, left_sum, left_n = X[order, f], np.cumsum(r[order])[:-1], np.arange(1, n)
        # squared error removed by this split
        gain = (left_sum ** 2 / left_n + (total - left_sum) ** 2 / (n - left_n)
                - total ** 2 / n)
        # no threshold fits between two equal values
        gain[x[1:] == x[:-1]] = 0
        # two splits that divide the rows the same way now tie exactly
        gain = np.round(gain, 8)
        i = int(np.argmax(gain))
        if gain[i] > best[0]:
            best = (float(gain[i]), f, float((x[i] + x[i + 1]) / 2))
    return best

def fit_tree(X, r, depth, split=best_split, gains=None):
    """A small regression tree: (feature, threshold, left, right), or a number at a
    leaf: the mean leftover there."""
    gain, f, t = split(X, r) if depth > 0 and len(r) > 1 else (0, None, None)
    if f is None:
        return float(r.mean()) if len(r) else 0.0
    if gains is not None:
        gains[f] += gain
    left = X[:, f] <= t
    return (f, t, fit_tree(X[left], r[left], depth - 1, split, gains),
            fit_tree(X[~left], r[~left], depth - 1, split, gains))

def predict_tree(tree, X):
    if not isinstance(tree, tuple):
        return np.full(len(X), tree)
    f, t, a, b = tree
    out, left = np.empty(len(X)), X[:, f] <= t
    out[left], out[~left] = predict_tree(a, X[left]), predict_tree(b, X[~left])
    return out

def rmse(a, b):
    return float(np.sqrt(((a - b) ** 2).mean()))
def sigmoid(z):
    return 1 / (1 + np.exp(-z))


def curved(n, seed):
    """Three features. The label depends on features 0 and 1 separately. Feature 2 is
    noise, and 1 label in 10 is flipped."""
    rng = np.random.default_rng(seed)
    X = rng.uniform(-1, 1, (n, 3))
    y = ((np.sin(3 * X[:, 0]) + 2 * X[:, 1] ** 2 - 0.7) > 0).astype(float)
    return X, np.where(rng.random(n) < 0.1, 1 - y, y)


def sales(n, seed):
    """Six features. Four matter: two only together, one in a curve and one in a
    straight line. Two are noise. The target has noise of size 2."""
    rng = np.random.default_rng(seed)
    X = rng.uniform(0, 1, (n, 6))
    y = (10 * np.sin(np.pi * X[:, 0] * X[:, 1]) + 20 * (X[:, 2] - 0.5) ** 2
         + 10 * X[:, 3] + rng.normal(0, 2.0, n))
    return X, y


X, y = sales(200, 0)                     # training data
X_val, y_val = sales(200, 1)             # validation data: used to choose when to stop
X_new, y_new = sales(1000, 2)            # test data: looked at once, at the end

def boost(rate, trees, depth=2, split=best_split, share=1.0, gains=None):
    """Returns, for each number of trees, the error on the training, validation and
    test data."""
    rng = np.random.default_rng(0)
    pred, pred_val, pred_new = (np.full(len(t), y.mean()) for t in (y, y_val, y_new))
    curve = []
    for k in range(trees):
        rows = rng.random(len(y)) < share                  # with share=1.0, every row
        tree = fit_tree(X[rows], (y - pred)[rows], depth, split, gains)
        pred += rate * predict_tree(tree, X)
        pred_val += rate * predict_tree(tree, X_val)
        pred_new += rate * predict_tree(tree, X_new)
        curve.append((rmse(pred, y), rmse(pred_val, y_val), rmse(pred_new, y_new)))
    return curve


def best_round(curve):
    return min(range(len(curve)), key=lambda k: curve[k][1])   # lowest validation error
import numpy as np

x = np.array([[1.0], [2.0], [3.0], [4.0], [5.0], [6.0]])
y = np.array([2.0, 3.0, 3.0, 7.0, 8.0, 9.0])
pred = np.full(6, y.mean())
print(0, pred.round(2).tolist())
for k in range(1, 4):
    tree = fit_tree(x, y - pred, depth=1)
    pred = pred + 0.5 * predict_tree(tree, x)
    print(k, "cut at x <=", tree[1], pred.round(2).tolist())
Try it now
Quick check
From the lesson on random forests and boosting: a random forest also combines many trees. How does it differ from boosting?
  1. A forest trains each tree on the errors of the last one
  2. A forest trains its trees independently and averages them
  3. A forest adds its trees together with a learning rate
  4. A forest uses a single very deep tree, split many times
Show the answer

A forest trains its trees independently and averages them

A forest's trees don't know about each other: each is trained on its own random sample, and their predictions are averaged, which mainly reduces variance. Boosting's trees are trained in sequence, each on what the earlier ones left wrong, and added together, which mainly reduces bias. That is why a forest uses deep trees and boosting uses small ones.

In your own words
Each tree is added at only 0.3 of its size. What would be lost by adding each tree in full?

Write a sentence or two, then compare it with a good answer in the lesson.

Where the gradient comes in

So far the loss was squared error, and the leftover was simply target minus prediction. That is not a coincidence. Ask of squared error, "if I nudge this row's prediction, which way does the loss fall fastest, and how steeply?" and the answer, the negative gradient, is target minus prediction.

That gives a recipe for any loss you can differentiate: at every round, compute the negative gradient of the loss for each row, and fit the next tree to that. It is gradient descent, where each step is a tree in place of a change to some weights. That is the full meaning of gradient boosting.

For a yes or no label the loss is the log loss. The model keeps a score for each row, and the sigmoid turns it into a chance. The negative gradient is then label minus chance.

Quick check
The leftover for log loss is the label minus the chance. What does this print for three rows: a 1 and a 0 the model knows nothing about, and a 1 it already scores at 3.0?
import math

rows = ((1, 0.0), (0, 0.0), (1, 3.0))
print([round(label - 1 / (1 + math.exp(-score)), 2) for label, score in rows])
  1. [1.0, 0.0, -2.0]
  2. [0.5, -0.5, 0.95]
  3. [0.5, 0.5, 0.95]
  4. [0.5, -0.5, 0.05]
Show the answer

[0.5, -0.5, 0.05]

A score of 0 is a chance of 0.5, so the leftovers are 1 − 0.5 = 0.5 and 0 − 0.5 = −0.5. A score of 3.0 is a chance of about 0.95, and the label is 1, so only 0.05 is left. The row the model already gets right asks for almost nothing from the next tree.

Drill

The best stump for one feature

Write best_stump(xs, leftovers). Try a threshold halfway between each pair of neighboring distinct values of xs, in increasing order. Rows with x <= threshold go left. Each side predicts the mean of its leftovers. Return (threshold, left_value, right_value) for the threshold with the lowest total squared error, and on a tie the smallest such threshold. If no threshold is possible, return (None, m, m), where m is the mean of all the leftovers (0.0 for an empty list).

Uses the setup above, 88 lines.

def best_stump(xs, leftovers):
    return (None, 0.0, 0.0)


print(best_stump([1, 2, 3, 4], [-1.0, -1.0, 2.0, 2.0]))
In the lesson, your code is checked as you write it.
In your own words
Why does fitting trees to "label minus chance" deserve the name gradient descent?

Write a sentence or two, then compare it with a good answer in the lesson.

In code: the machine, its dials, and the library's version

Purpose. Build the whole method in about thirty lines of NumPy, turn each dial and watch the validation error, then get the same behavior from HistGradientBoostingClassifier.

Uses the setup above, 88 lines.

import numpy as np

def best_split(X, r):
    """The feature and threshold that best separate rows with high leftovers from
    rows with low ones."""
    best, total, n = (1e-9, None, None), r.sum(), len(r)
    for f in range(X.shape[1]):
        order = np.argsort(X[:, f])
        x, left_sum, left_n = X[order, f], np.cumsum(r[order])[:-1], np.arange(1, n)
        # squared error removed by this split
        gain = (left_sum ** 2 / left_n + (total - left_sum) ** 2 / (n - left_n)
                - total ** 2 / n)
        # no threshold fits between two equal values
        gain[x[1:] == x[:-1]] = 0
        # two splits that divide the rows the same way now tie exactly
        gain = np.round(gain, 8)
        i = int(np.argmax(gain))
        if gain[i] > best[0]:
            best = (float(gain[i]), f, float((x[i] + x[i + 1]) / 2))
    return best

def fit_tree(X, r, depth, split=best_split, gains=None):
    """A small regression tree: (feature, threshold, left, right), or a number at a
    leaf: the mean leftover there."""
    gain, f, t = split(X, r) if depth > 0 and len(r) > 1 else (0, None, None)
    if f is None:
        return float(r.mean()) if len(r) else 0.0
    if gains is not None:
        gains[f] += gain
    left = X[:, f] <= t
    return (f, t, fit_tree(X[left], r[left], depth - 1, split, gains),
            fit_tree(X[~left], r[~left], depth - 1, split, gains))

def predict_tree(tree, X):
    if not isinstance(tree, tuple):
        return np.full(len(X), tree)
    f, t, a, b = tree
    out, left = np.empty(len(X)), X[:, f] <= t
    out[left], out[~left] = predict_tree(a, X[left]), predict_tree(b, X[~left])
    return out

def rmse(a, b):
    return float(np.sqrt(((a - b) ** 2).mean()))
def wave(n, seed):
    """One feature, and a target that rises in waves, with noise of size 0.2."""
    rng = np.random.default_rng(seed)
    x = rng.uniform(0, 4, n)
    return x[:, None], np.sin(3 * x) + 0.5 * x + rng.normal(0, 0.2, n)

X, y = wave(200, 0)
X_new, y_new = wave(1000, 1)
rate = 0.3
pred, pred_new = np.full(len(y), y.mean()), np.full(len(y_new), y.mean())
print("trees | error on training data | error on new data | the tree just added")
print("    0 |", f"{rmse(pred, y):22.3f}", "|", f"{rmse(pred_new, y_new):17.3f}",
      "| (none yet: every prediction is the average,",
      str(round(float(y.mean()), 2)) + ")")
for k in range(1, 301):
    # trained on what is still wrong
    tree = fit_tree(X, y - pred, depth=1)
    # and added in at a fraction of its size
    pred += rate * predict_tree(tree, X)
    pred_new += rate * predict_tree(tree, X_new)
    if k in (1, 2, 5, 20, 100, 300):
        f, t, low, high = tree
        print(str(k).rjust(5), "|", f"{rmse(pred, y):22.3f}", "|",
              f"{rmse(pred_new, y_new):17.3f}", "|",
              f"x <= {t:.2f}: {low:+.2f}, otherwise {high:+.2f}")
It runs right here in your browser, with nothing to install.

The data has one feature, and a target that rises in waves, with noise of size 0.2. Predicting the average for everyone is off by 0.751.

The first stump says: below 2.05 the average was too high by 0.54, and above it too low by 0.44. Adding 0.3 of that brings the error down to 0.666. The second stump makes a similar cut. By the hundredth the corrections are tiny, ±0.03, and the error on new data is 0.241, near the 0.2 that noise makes unavoidable.

Then look at the last row. From 100 trees to 300, the training error falls from 0.207 to 0.165, below the noise. A model can't honestly be more accurate than the noise allows. It is memorizing the training rows, and the error on new data hardly moves. Boosting never stops finding something to fix, so deciding when to stop is your job.

Quick check
The noise in the wave data has size 0.2. After 300 stumps the error on the training rows is 0.165. What does an error below the noise tell you?
  1. The stumps are too deep
  2. The model is memorizing the training rows, noise included
  3. The learning rate is too small
  4. The model is more accurate than the data allows
Show the answer

The model is memorizing the training rows, noise included

Noise is the part of each target that no model can predict. A training error below it can only come from fitting that noise, which is why the error on new data hardly moves.

Uses the setup above, 88 lines.

import numpy as np


X, y = curved(400, 0)

def log_loss(score):
    p = sigmoid(score)
    return float(-(y * np.log(p) + (1 - y) * np.log(1 - p)).mean())

# the log-odds of the share of 1s
start = float(np.log(y.mean() / (1 - y.mean())))
score = np.full(len(y), start)
print("share of 1s:", y.mean(), "| starting score for every row:", round(start, 3),
      "| log loss:", round(log_loss(score), 4))
print()
print(
    "trees | label, chance and leftover (label - chance) for the first three rows | "
    "log loss after adding the tree")
for k in range(1, 151):
    chance = sigmoid(score)
    # the direction that lowers the log loss fastest
    leftover = y - chance
    tree = fit_tree(X, leftover, depth=1)
    score += 0.5 * predict_tree(tree, X)
    if k in (1, 2, 3, 50, 150):
        rows = "  ".join(f"{int(y[i])}, {chance[i]:.3f}, {leftover[i]:+.3f}"
                         for i in range(3))
        print(str(k).rjust(5), "|", rows.ljust(68), "|", round(log_loss(score), 4))

Every row starts with the same score, 0.03: the log-odds of the share of 1s. That is a chance of 0.507 for everyone, and a log loss of 0.693.

The first row has label 1, so its leftover is +0.493: "raise my score". The second has label 0 and a leftover of −0.507. One tree later the first row's chance is 0.541 and its leftover has shrunk to +0.459. After 150 trees it is at 0.850, and the log loss has fallen to 0.4069.

Notice what a leftover is here: a number between −1 and 1 that is large when the model is confidently wrong and near 0 when it is right. Rows the model already handles stop steering the trees.

Quick check
The leftover for log loss is label minus chance, a number between −1 and 1. When is it close to 0?
  1. When the label is 0
  2. When the model is confidently wrong about the label
  3. When the learning rate is small
  4. When the model already gives the right answer a chance near 1
Show the answer

When the model already gives the right answer a chance near 1

A row the model already handles has label and chance almost equal, so its leftover is near 0 and it stops steering the trees. A confident miss has a leftover near ±1.

Depth decides what the model can say

A stump looks at one feature. Add up a thousand stumps and you have a sum of one-feature pieces: a curve in the first feature, plus a curve in the second, and so on. Such a model can bend any way it likes along each feature. It can never say "this feature matters only when that one is high". That needs a tree that asks two questions on one path: a tree of depth 2.

The cell tests it. In the first dataset the label depends on two features separately, each through a curve. In the second it is 1 when two features have the same sign, so neither says anything alone.

Uses the setup above, 88 lines.

import numpy as np


def paired(n, seed):
    """The label is 1 when features 0 and 1 have the same sign: neither feature says
    anything alone."""
    rng = np.random.default_rng(seed)
    X = rng.uniform(-1, 1, (n, 3))
    y = (X[:, 0] * X[:, 1] > 0).astype(float)
    return X, np.where(rng.random(n) < 0.1, 1 - y, y)

def boosted_accuracy(X, y, X_new, y_new, depth, trees=150, rate=0.5):
    start = float(np.log(y.mean() / (1 - y.mean())))
    score, score_new = np.full(len(y), start), np.full(len(y_new), start)
    for k in range(trees):
        tree = fit_tree(X, y - sigmoid(score), depth)
        score += rate * predict_tree(tree, X)
        score_new += rate * predict_tree(tree, X_new)
    return float(((score_new > 0) == y_new).mean())

def logistic_accuracy(X, y, X_new, y_new):
    w, b = np.zeros(X.shape[1]), 0.0
    for step in range(2000):
        p = sigmoid(X @ w + b)
        w -= 0.5 * X.T @ (p - y) / len(y)
        b -= 0.5 * (p - y).mean()
    return float((((X_new @ w + b) > 0) == y_new).mean())

print(
    "accuracy on 2,000 new rows. One label in 10 is flipped, so 0.9 is the best "
    "possible")
print(
    "the label depends on               | logistic regression | boosted, depth 1 | "
    "depth 2 | depth 3")
for name, make in (("each feature separately (curved)", curved),
                   ("two features together", paired)):
    X, y = make(400, 0)
    X_new, y_new = make(2000, 1)
    cells = [logistic_accuracy(X, y, X_new, y_new)] + [
        boosted_accuracy(X, y, X_new, y_new, depth) for depth in (1, 2, 3)]
    print(name.ljust(34), "|", f"{cells[0]:19.3f}", "|", f"{cells[1]:16.3f}", "|",
          f"{cells[2]:7.3f}", "|", f"{cells[3]:7.3f}")

On the curved data, logistic regression reaches 0.755: it can only draw a straight boundary. Boosted stumps reach 0.809 without anyone engineering a squared feature. The curves come free.

On the paired data, logistic regression is at 0.499 and boosted stumps at 0.517: both are flipping coins, and no number of stumps will help. At depth 2 the accuracy jumps to 0.830.

So depth sets the order of interaction: depth 1 for none, depth 2 for pairs, depth 3 for triples. More is not better, though. On the curved data depth 3 scores 0.804, lower than depth 2 at 0.828: bigger trees fit the flipped labels sooner. Libraries default to somewhere between 3 and 8, and it is one of the first settings worth trying both ways.

Learning rate, number of trees, and stopping

Two settings work as a pair: the learning rate, the fraction of each tree that is added, and the number of trees. The data below has six features. Four matter and two are pure noise, and the target carries noise of size 2. There are three sets: training, validation, and a test set that is looked at once.

Uses the setup above, 88 lines.

import numpy as np


print("always predicting the average: test error",
      round(rmse(np.full(len(y_new), y.mean()), y_new), 3), "| the noise alone: 2.0")
print()
print(
    "learning rate | trees at the lowest validation error | test error there | after "
    "400 trees: training error | test error")
for rate in (1.0, 0.3, 0.1, 0.03):
    curve = boost(rate, 400)
    k = best_round(curve)
    print(str(rate).rjust(13), "|", str(k + 1).rjust(36), "|", f"{curve[k][2]:16.3f}",
          "|", f"{curve[-1][0]:31.3f}", "|", f"{curve[-1][2]:10.3f}")

Predicting the average is off by 5.133, and nothing can do better than 2.0.

At a learning rate of 1.0, each tree is added whole. Validation error is lowest after just 2 trees, at a test error of 3.657. After 400 trees the training error is 0.000 and the test error has risen to 3.983: the model has memorized 200 rows.

At 0.3 the best point comes at 32 trees, with a test error of 2.782. At 0.1 it comes at 184 trees, at 2.785. At 0.03 it takes 324 trees to reach 2.801.

Three things to take from the table:

  • A smaller rate needs more trees: 32 of them at 0.3, 184 at 0.1, and 324 at 0.03.
  • Small rates are forgiving. At 0.03, running to 400 trees costs nothing. At 0.3, overshooting the best point costs 0.185 (2.967 against 2.782).
  • Below some rate there is nothing more to gain, only more trees to pay for. 0.3 and 0.1 are level.

The number of trees is therefore not something to guess. Set it high, watch the validation error, and keep the number of trees where it was lowest. That is early stopping, and the worked example below does it.

Quick check
In the table, a learning rate of 0.3 reaches its best test error after 32 trees and 0.03 after 324. What does that say about the two settings?
  1. The number of trees doesn't depend on the rate
  2. A smaller rate needs more trees to get as far
  3. A smaller rate always gives a better final model
  4. A larger rate needs more trees
Show the answer

A smaller rate needs more trees to get as far

Each tree is added at a smaller fraction of its size, so more of them are needed to travel the same distance. The best test errors are about level, so the small rate buys steadiness, not accuracy.

The four rows of that table as curves: training and validation error against the number of trees, one panel per learning rate. The training line only goes down. The validation line goes down and then, for the large rates, back up.

Uses the setup above, 88 lines.

import matplotlib.pyplot as plt

fig, axes = plt.subplots(1, 4, figsize=(11, 2.8), sharey=True)
for ax, rate in zip(axes, (1.0, 0.3, 0.1, 0.03)):
    curve = boost(rate, 400)
    ax.plot([c[0] for c in curve], label="training")
    ax.plot([c[1] for c in curve], label="validation")
    ax.set_title(f"rate {rate}")
    ax.set_xlabel("trees")
axes[0].set_ylabel("error")
axes[0].legend()
plt.show()
Quick check
Suppose each tree fit the leftover perfectly, and was added at a learning rate of 0.1. Each tree then leaves 0.9 of the gap. What does this print: the share of the original gap closed after 10 trees, and after 50?
print(round(1 - 0.9 ** 10, 3), round(1 - 0.9 ** 50, 3))
  1. 1.0 1.0
  2. 0.349 0.005
  3. 0.1 0.5
  4. 0.651 0.995
Show the answer

0.651 0.995

After each tree, 0.9 of the gap remains, so after 10 trees 0.9¹⁰ ≈ 0.349 remains and 0.651 is closed. After 50 trees only 0.005 remains. A rate of 0.1 doesn't mean 10 trees finish the job: the steps shrink as the gap does, which is why small rates need trees in the hundreds.

Drill

When to stop adding trees

Write stop_round(losses, patience). losses[0] is the validation loss after 1 tree, losses[1] after 2, and so on. Read them in order. A loss strictly lower than every earlier one is a new best. Stop as soon as patience trees in a row have failed to set a new best. Return (best_trees, trees_built): the number of trees at the best loss, and the number built when you stopped. If you never stop, trees_built is the length of the list. For an empty list, return (0, 0).

Uses the setup above, 88 lines.

def stop_round(losses, patience):
    return (0, 0)


print(stop_round([5.0, 4.0, 3.0, 3.5, 3.2, 3.1, 2.9], 3))
In the lesson, your code is checked as you write it.
Quick check
A boosted model's training error falls at every one of 1,000 trees. Its validation error falls until tree 120 and then rises slowly. Which model should be kept?
  1. All 1,000 trees
  2. Whichever has the lowest training error
  3. The first tree alone
  4. The first 120 trees
Show the answer

The first 120 trees

Training error always falls in boosting, since every tree is fit to what is left on the training rows. It can't tell you when the trees have started fitting noise. Validation error can: its lowest point, 120 trees, is the best estimate of where the model does best on new data. A boosted model is a sum, so keeping the first 120 trees is all it takes.

Worked example

Worked example: choosing depth with early stopping

A complete, small tuning run on the six-feature data. fit adds trees until the validation error hasn't improved for 30 trees in a row, and keeps the number of trees at its best point. It also adds up, for each feature, the squared error removed by every split made on it.

Uses the setup above, 88 lines.

import numpy as np


def fit(rate, depth, patience, most=2000):
    """Adds trees until the validation error hasn't improved for `patience` trees in
    a row, then keeps the best number."""
    pred, pred_val = np.full(len(y), y.mean()), np.full(len(y_val), y.mean())
    trees, gains, best, best_k = [], np.zeros(X.shape[1]), float("inf"), 0
    gains_at_best = gains.copy()
    while len(trees) < most and len(trees) - best_k < patience:
        tree = fit_tree(X, y - pred, depth, gains=gains)
        trees.append(tree)
        pred += rate * predict_tree(tree, X)
        pred_val += rate * predict_tree(tree, X_val)
        if rmse(pred_val, y_val) < best:
            best, best_k = rmse(pred_val, y_val), len(trees)
            gains_at_best = gains.copy()
    return trees[:best_k], len(trees), best, gains_at_best

def predict(trees, rate, Xs):
    return y.mean() + rate * sum(predict_tree(tree, Xs) for tree in trees)

print("depth | trees built | trees kept | validation error | test error")
for depth in (1, 2, 3, 4):
    trees, built, val, gains = fit(0.1, depth, patience=30)
    print(str(depth).rjust(5), "|", str(built).rjust(11), "|",
          str(len(trees)).rjust(10), "|", f"{val:16.3f}", "|",
          f"{rmse(predict(trees, 0.1, X_new), y_new):.3f}")

trees, built, val, gains = fit(0.1, 3, patience=30)
print()
print("depth 3: share of the error removed by splits on each feature")
for f, share in enumerate(gains / gains.sum()):
    print("  feature", f, "|", f"{share:.3f}", "#" * round(40 * share),
          "" if f < 4 else " (noise)")
In the lesson you can change this and run it.

Four depths are tried, each with early stopping. Depth 3 has the lowest validation error, 2.563, with 77 trees kept of 107 built, and its test error is 2.756, the best of the four. Two details are worth a second look. First, the depth-2 run stopped after 98 trees and kept 68, with a test error of 2.819. The table in the last part showed that the same model, run for longer, was best at 184 trees with 2.785. Its validation error stalled for 30 trees and then improved again, so a patience of 30 gave up too soon. Patience is a setting too, and too little of it underfits. Second, the bars. Summing the error removed by each feature's splits gives a rough importance: features 0 to 3 take about 95% between them, and the two noise features 3.6% and 1.8%. A model that spent a third of its splits on a feature you believe is noise would be telling you something, either about the model or about your belief.

The same behavior from scikit-learn. HistGradientBoostingClassifier holds out part of the training rows (validation_fraction), watches its score on them, and stops after n_iter_no_change rounds without improvement. n_iter_ is how many trees it kept. The cell runs it on the shop's churn data at three learning rates.

Uses the setup above, 88 lines.

import pandas as pd
import requests
from sklearn.ensemble import HistGradientBoostingClassifier
from sklearn.metrics import roc_auc_score
from sklearn.model_selection import train_test_split

df = pd.DataFrame(requests.get("https://api.gradient.test/v1/customers").json()["data"])
features = ["tenure_months", "orders_last_year", "avg_order_value",
            "days_since_last_order", "discount_share", "email_open_rate",
            "support_tickets", "trail_club"]
X_tr, X_te, y_tr, y_te = train_test_split(df[features], df["churned"], test_size=0.3,
                                          random_state=0, stratify=df["churned"])
for rate in (0.3, 0.1, 0.03):
    model = HistGradientBoostingClassifier(
        learning_rate=rate, max_iter=1000, max_depth=3, early_stopping=True,
        validation_fraction=0.2, n_iter_no_change=20, random_state=0)
    model.fit(X_tr, y_tr)
    auc = roc_auc_score(y_te, model.predict_proba(X_te)[:, 1])
    print(f"rate {rate:<5} trees kept {model.n_iter_:>4}  test AUC {auc:.3f}")

The same pattern as the NumPy table: a rate of 0.3 stops after 27 trees, 0.1 after 48 and 0.03 after 107, and the test AUC is about the same in all three (0.741, 0.740 and 0.747). The smaller rate needs more trees for no loss. Note the column email_open_rate, which has missing values: the library handles them inside the trees, with no imputing step.

In your own words
A teammate sets the learning rate to 0.01 "to be safe" and trains 100 trees. What is likely to go wrong, and what would you change?

Write a sentence or two, then compare it with a good answer in the lesson.

In practice: tuning, libraries and what goes wrong

Purpose. Know what XGBoost, LightGBM and CatBoost add, the order in which to tune, and how a boosted model goes wrong.

What the libraries add

XGBoost, LightGBM, CatBoost and scikit-learn's HistGradientBoosting models all run the loop you have just built. What they add is speed, and more ways to hold the model back. Two of those are easy to try.

Uses the setup above, 88 lines.

import numpy as np


def binned(bins):
    """A split search that tries only `bins - 1` thresholds for each feature, placed
    so each bin holds the same number of rows."""
    edges = [np.quantile(X[:, f], np.arange(1, bins) / bins) for f in range(X.shape[1])]
    def split(Xs, r):
        best, total, n = (1e-9, None, None), r.sum(), len(r)
        for f in range(Xs.shape[1]):
            # one row of yes/no for each threshold
            below = Xs[:, f][None, :] <= edges[f][:, None]
            left_n, left_sum = below.sum(axis=1), (below * r).sum(axis=1)
            ok = (left_n > 0) & (left_n < n)
            gain = (left_sum ** 2 / np.maximum(left_n, 1)
                    + (total - left_sum) ** 2 / np.maximum(n - left_n, 1)
                    - total ** 2 / n)
            gain = np.round(np.where(ok, gain, 0.0), 8)
            i = int(np.argmax(gain))
            if gain[i] > best[0]:
                best = (float(gain[i]), f, float(edges[f][i]))
        return best
    return split

print(
    "thresholds tried for each feature | trees at the lowest validation error | test "
    "error there")
for label, split in (("199 (every gap between rows)", best_split),
                     ("63 (64 bins)", binned(64)), ("15 (16 bins)", binned(16)),
                     ("3 (4 bins)", binned(4))):
    curve = boost(0.1, 300, split=split)
    k = best_round(curve)
    print(label.ljust(33), "|", str(k + 1).rjust(36), "|", f"{curve[k][2]:.3f}")

print()
print(
    "rows each tree is trained on | trees at the lowest validation error | test error "
    "there | test error after 300 trees")
for share in (1.0, 0.8, 0.5):
    curve = boost(0.1, 300, share=share)
    k = best_round(curve)
    print((str(int(100 * share)) + "%, picked at random").ljust(28), "|",
          str(k + 1).rjust(36), "|", f"{curve[k][2]:16.3f}", "|", f"{curve[-1][2]:.3f}")

Histograms. The split search above tries every gap between rows: 199 thresholds for each feature here, and a million on a million rows. The libraries sort each feature into bins once, 255 by default, and try only the bin edges. With 63 thresholds the test error is 2.709 and with 15 it is 2.806, against 2.785 for the full search. Only at 3 does it clearly suffer, at 3.068. A coarser search does little harm, and it is the main reason these libraries are fast.

Row sampling. Each tree can be trained on a random share of the rows. With 80% the test error at the best point is 2.699, and with 50% it is 2.686, both better than the 2.785 from using every row. Trees that see different rows make different mistakes, which partly cancel, as in a random forest.

The libraries also offer column sampling (each tree sees a random share of the features), a minimum leaf size, a penalty that shrinks leaf values toward zero, missing values handled inside the tree, and second-order steps that use the curvature of the loss to size each leaf.

Start with a learning rate near 0.1, depth 3 to 6, many trees and early stopping. Then tune depth and the sampling shares on validation data.

Quick check
Why do modern boosting libraries sort each feature into a few hundred bins before training?
  1. Split search then tries far fewer thresholds
  2. Bins remove the need for a validation set
  3. Trees can't split on features that aren't binned
  4. Binned features let each tree grow much deeper
Show the answer

Split search then tries far fewer thresholds

Finding a split is the expensive step, and it is repeated for every node of every tree. With bins, the candidates for a feature are the bin edges, a few hundred at most, however many rows there are. As the table showed, the accuracy lost by not trying every gap is small, and sometimes nothing at all.

In an engineer's week, boosted trees are the default model on a table once a forest isn't enough, and the work is in the tuning order: fix a learning rate near 0.1, let early stopping choose the number of trees, then try depth and the sampling shares on validation rows, and only at the end shrink the learning rate and let it run longer. What goes wrong is mostly the validation set: tune against one set for long enough and you have fit it, so keep a test set that is looked at once, and re-check with cross-validation when the gain is small. A boosted model also extrapolates badly, since a staircase cannot continue a trend past its data.

On the job: save the number of trees that early stopping found, not the ceiling you set, and record the learning rate with it. The two are a pair.

Goes deeper in

In your own words
You are handed a table of 50,000 customers and 40 columns, and asked for a churn model. Describe your first boosted model, and what you would watch.

Write a sentence or two, then compare it with a good answer in the lesson.

Practice what you just read

  • 9 code examples you can edit and run
  • a practice exercise that checks your code
  • a 5-question quiz
  • 12 review cards for spaced repetition

Try a quiz question

In gradient boosting, what is each new tree trained to predict?

  1. The negative gradient of the loss at the current predictions
  2. The original target, on a fresh random sample of rows
  3. The predictions of the tree that came before it
  4. The average of the target within each leaf of the last tree

Answer it at the end of the lesson to see if you're right, and why.

Before this lesson

Keep learning

Where this lesson leads.

575 lessons in thirteen phases. 176 are free without an account, and a free account opens the rest. See every lesson.

Phase 3 · about 39 hours of study

Machine learning

Learning from data, and knowing when it worked 50 lessons 1 free
  1. What machine learning is FreePrograms that learn rules from examples instead of being told them.30 min
  2. Features and labelsSupervised learning: inputs, targets and predictions.30 min
  3. Train, validation and test setsHold data back so you can trust your results.38 min
  4. Preparing dataClean, encode and scale data before a model sees it.40 min
  5. Linear regressionFit a line, and predict numbers from features.42 min
  6. Loss functionsOne number that says how wrong the model is.35 min
  7. Training with gradient descentAdjust weights step by step to reduce the loss.42 min
  8. Learning rateStep size, convergence and divergence.35 min
  9. Logistic regressionPredict probabilities for yes/no outcomes.42 min
  10. Multiclass classificationSoftmax and cross-entropy for more than two classes.42 min
  11. The same three models in PyTorchA line, logistic regression and softmax regression fitted both ways: the loss, the gradient and the update opened up, with weight decay and mini-batches.35 min
  12. Precision, recall and F1Accuracy lies; these don't.42 min
  13. ROC curves and AUCJudge a classifier across every threshold.30 min
  14. Calibration: can the probability be trusted?Bands of predicted risk against what happened, the Brier score, why naive Bayes is over-confident, and fixing it on rows the model did not fit.30 min
  15. Overfitting and underfittingMemorizing versus learning.30 min
  16. RegularizationPenalize complexity so models generalize.40 min
  17. Bias and varianceThe two ways a model can be wrong.30 min
  18. Cross-validationReuse limited data for more reliable estimates.42 min
  19. Imbalanced classes in depthRare classes measured: why rebalancing mostly moves the threshold, correcting inflated probabilities, average precision against AUC, why the count of rare cases matters, and thresholds from costs.45 min
  20. Naive Bayes: classifying with countsA classifier trained by counting: Bayes' rule over words, the naive assumption, log scores, smoothing for unseen words, why it is overconfident, and when it beats logistic regression.45 min
  21. Nearest neighborsPredict from the most similar examples.35 min
  22. Decision treesLearn a flowchart of yes/no questions.42 min
  23. Random forests and boostingMany weak models voting beat one strong one.42 min
  24. Gradient boosting in depthBoosting built from scratch: trees fit to the gradient of the loss, depth and interactions, learning rate against number of trees, early stopping, and what XGBoost and LightGBM add.45 min
  25. Support vector machinesThe widest margin, support vectors, the hinge loss and C, kernels for curved boundaries, and when an SVM fits.40 min
  26. Recommender systemsShrunk averages, item-to-item collaborative filtering, matrix factorization, and cold start.40 min
  27. Project: a price modelMultiple regression on log prices, one-hot categories, percentage effects and an extrapolation flag.45 min
  28. Feature engineeringTurn raw data into signals a model can use.35 min
  29. The scikit-learn workflowFit, predict and evaluate with the standard ML library.45 min
  30. Explaining a model: what it uses, and why this predictionPermutation importance on held-back rows, a linear model's contributions for one customer, partial dependence, and what none of them can say.35 min
  31. Capstone: churn predictionPredict which customers will leave, and measure it properly.45 min
  32. ClusteringGroup similar items without labels (k-means).35 min
  33. Clusters of any shape: DBSCAN and hierarchiesWhy k-means needs round clusters, DBSCAN's core points and noise, and hierarchical clustering with its linkages.40 min
  34. Anomaly detectionMasking, robust scores with the median and MAD, baselines from the past, isolation forests and thresholds from a review budget.40 min
  35. Dimensionality reductionVisualize and compress high-dimensional data.35 min
  36. Cleaning messy dataDuplicates, junk rows, text numbers, mixed dates and missing values that mean something.45 min
  37. Grouping, pivoting and reshapingNamed aggregation, pivot tables, transform, running totals and groups too small to rank.45 min
  38. Data in pieces: partitions and mergeable summariesSplit, summarize and combine; which statistics merge exactly, merging variances, sketches for the rest, and partitioning well.30 min
  39. Combining tables with mergeJoin on keys safely, stack tables, and divide by the right denominator.44 min
  40. Time series with pandasResample, smooth, compare across years, and test whether one series leads another.45 min
  41. Forecasting: baselines, lag features and backtestsThree baselines, lag features that never see their own future, a walk-forward backtest, and a range around the number.40 min
  42. Text mining: TF-IDF, search and labelsBag of words and TF-IDF, similarity search and its blind spots, text classifiers and topics, and when LLM labels are worth it.35 min
  43. Location dataHaversine distances, nearest places, GeoJSON, point in polygon and simple maps.40 min
  44. Comparing groups: t-testsWelch's t-test, pooled vs average rates, and a control group for before-and-after changes.40 min
  45. More tests: groups, categories, relationshipsChoose a test, ANOVA by hand, chi-square on counts, Pearson vs Spearman, one-sided tests.40 min
  46. Project: an exploratory analysis reportFive business questions answered with cleaning, joins, charts and a test, then written up.45 min
  47. Bandits: explore or exploitLearning from rewards with no labels: a running estimate for each option, why the greedy choice gets stuck, epsilon-greedy and an optimism bonus.35 min
  48. Decisions in sequence: states, rewards and valueA Markov decision process on a grid world: discounted return, the value of a state, the Bellman equation, and value iteration to the best policy.40 min
  49. Q-learning: learning values by doingA value for every action, learned from experience with no rules given: the update, a grid world you can watch, and why optimism explores better than chance.40 min
  50. Policy gradients: learning what to do directlyA policy as probabilities you can nudge: turn up what worked, measure it against a baseline, and see how the same update trains a language model.40 min

Never trained an AI? Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account. Teach it to write