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.
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
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:
- Start with one prediction for every row: the average of the target.
- Work out the leftover for every row: the target minus the current prediction. (The usual name is the residual.)
- 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())
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.
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.
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])
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.
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]))
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}")
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.
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.
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.
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()
print(round(1 - 0.9 ** 10, 3), round(1 - 0.9 ** 50, 3))
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.
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))
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: 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)")
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.
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.
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
- Random forests and boosting: the forest side of the story, and the comparison on churn.
- Cross-validation: a steadier way to compare two tunings.
- Hyperparameter search: searching the dials systematically.
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?
Before this lesson
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
- What machine learning is FreePrograms that learn rules from examples instead of being told them.30 min
- Features and labelsSupervised learning: inputs, targets and predictions.30 min
- Train, validation and test setsHold data back so you can trust your results.38 min
- Preparing dataClean, encode and scale data before a model sees it.40 min
- Linear regressionFit a line, and predict numbers from features.42 min
- Loss functionsOne number that says how wrong the model is.35 min
- Training with gradient descentAdjust weights step by step to reduce the loss.42 min
- Learning rateStep size, convergence and divergence.35 min
- Logistic regressionPredict probabilities for yes/no outcomes.42 min
- Multiclass classificationSoftmax and cross-entropy for more than two classes.42 min
- 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
- Precision, recall and F1Accuracy lies; these don't.42 min
- ROC curves and AUCJudge a classifier across every threshold.30 min
- 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
- Overfitting and underfittingMemorizing versus learning.30 min
- RegularizationPenalize complexity so models generalize.40 min
- Bias and varianceThe two ways a model can be wrong.30 min
- Cross-validationReuse limited data for more reliable estimates.42 min
- 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
- 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
- Nearest neighborsPredict from the most similar examples.35 min
- Decision treesLearn a flowchart of yes/no questions.42 min
- Random forests and boostingMany weak models voting beat one strong one.42 min
- 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
- Support vector machinesThe widest margin, support vectors, the hinge loss and C, kernels for curved boundaries, and when an SVM fits.40 min
- Recommender systemsShrunk averages, item-to-item collaborative filtering, matrix factorization, and cold start.40 min
- Project: a price modelMultiple regression on log prices, one-hot categories, percentage effects and an extrapolation flag.45 min
- Feature engineeringTurn raw data into signals a model can use.35 min
- The scikit-learn workflowFit, predict and evaluate with the standard ML library.45 min
- 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
- Capstone: churn predictionPredict which customers will leave, and measure it properly.45 min
- ClusteringGroup similar items without labels (k-means).35 min
- 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
- Anomaly detectionMasking, robust scores with the median and MAD, baselines from the past, isolation forests and thresholds from a review budget.40 min
- Dimensionality reductionVisualize and compress high-dimensional data.35 min
- Cleaning messy dataDuplicates, junk rows, text numbers, mixed dates and missing values that mean something.45 min
- Grouping, pivoting and reshapingNamed aggregation, pivot tables, transform, running totals and groups too small to rank.45 min
- 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
- Combining tables with mergeJoin on keys safely, stack tables, and divide by the right denominator.44 min
- Time series with pandasResample, smooth, compare across years, and test whether one series leads another.45 min
- 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
- 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
- Location dataHaversine distances, nearest places, GeoJSON, point in polygon and simple maps.40 min
- Comparing groups: t-testsWelch's t-test, pooled vs average rates, and a control group for before-and-after changes.40 min
- More tests: groups, categories, relationshipsChoose a test, ANOVA by hand, chi-square on counts, Pearson vs Spearman, one-sided tests.40 min
- Project: an exploratory analysis reportFive business questions answered with cleaning, joins, charts and a test, then written up.45 min
- 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
- 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
- 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
- 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