B-bagging writes when the script runsDictionary of Applied Machine Learning · boosting
Numerical companion to the entry boosting: it recomputes what the entry states and prints one line per check
Runs boosting with the squared error loss on a task with one feature and a real-valued label and checks the entry's claims numerically: each base learner is fit to the residuals, which are the negative gradient of the training error with respect to the current predictions, so each iteration lowers the training error; with enough iterations the training error becomes arbitrarily small while the validation error eventually rises, so the number of iterations is a hyperparameter chosen by early stopping; and accumulating base learners (boosting) differs from averaging them (bagging). Self-contained (numpy and matplotlib only), fixed seed.
Run it without installing anything:uv run https://dictionaryofml.org/terms/boosting.py
uv downloads this script and the pinned NumPy and Matplotlib it needs, then runs it; the script fetches any input file it uses. To keep the output files, download boosting.py into a folder and run uv run boosting.py there. With NumPy and Matplotlib already installed, python3 boosting.py, from any directory — it writes its output files into the current directory. Fixed seeds, so the printed numbers reproduce exactly. Download boosting.py · Notebook · Open in Colab
One cell per block of the script: the code, and what that code printed when it last ran here
"""
boosting.py — numerical companion to the glossary entry 'boosting'.
Purpose
-------
Runs boosting with the squared error loss on a task with one feature
and a real-valued label and checks the entry's claims numerically: each base learner is fit
to the residuals, which are the negative gradient of the training error
with respect to the current predictions, so each iteration lowers the
training error; with enough iterations the training error becomes
arbitrarily small while the validation error eventually rises, so the
number of iterations is a hyperparameter chosen by early stopping; and
accumulating base learners (boosting) differs from averaging them
(bagging). Self-contained (numpy and matplotlib only), fixed seed.
Setup
-----
Training pairs: m = 30 pairs (x, y) with feature x in [0, 1] and label
y = sin(2 pi x) + 0.5 x + noise; a validation set of 30 further pairs
of the same kind. Base learners: decision trees of depth one
(one split of the feature range, one constant prediction on each side).
Learning rate eta = 0.5, up to T = 300 iterations, initialization
h^(0) = mean label of the training pairs.
Blocks
------
[B-gradstep] The base learner of iteration t is fit to the residuals
y - h^(t-1)(x), i.e. to the negative gradient of the training
error with respect to the predictions; adding it with
learning rate eta lowers the training error in every
iteration.
[B-overfit] The training error falls below 0.02 by T = 300, while the
validation error reaches its minimum at an earlier iteration
and is at least 0.03 larger at T = 300 than at that minimum:
early stopping picks the number of iterations.
[B-bagging] Averaging 300 base learners, each trained on a random draw
with replacement from the training pairs (bagging), leaves the
training error more than five times that of accumulating
them (boosting).
Outputs
-------
boosting_errors.csv : t, trainerr, valerr of boosting, and the training
error of bagging with t base learners.
boosting_fit.csv : x grid with the label function, the boosted
hypothesis after early stopping and after T = 300.
boosting.png : matplotlib preview of the two panels (checking
only).
"""
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
from pathlib import Path
OUT_DIR = Path(__file__).parent
report = []
def check(name, ok):
report.append((name, bool(ok)))
print(f" [{'ok' if ok else 'FAIL'}] {name}")
rng = np.random.default_rng(0)
m = 30
x_tr = np.sort(rng.uniform(0.0, 1.0, m))
x_va = np.sort(rng.uniform(0.0, 1.0, m))
def truth(xs):
return np.sin(2.0 * np.pi * xs) + 0.5 * xs
y_tr = truth(x_tr) + 0.3 * rng.standard_normal(m)
y_va = truth(x_va) + 0.3 * rng.standard_normal(m)
def fit_stump(xs, target):
"""Depth-one decision tree: the split and the two constants that
minimize the squared error of the fit to `target`."""
order = np.argsort(xs); xs_s, t_s = xs[order], target[order]
best = (np.inf, None, None, None)
for i in range(1, len(xs_s)):
left, right = t_s[:i].mean(), t_s[i:].mean()
err = ((t_s[:i] - left) ** 2).sum() + ((t_s[i:] - right) ** 2).sum()
if err < best[0]:
best = (err, 0.5 * (xs_s[i - 1] + xs_s[i]), left, right)
_, split, left, right = best
return lambda q: np.where(q < split, left, right)
def trainerr(pred, y):
return float(np.mean((y - pred) ** 2))
The base learner of iteration t is fit to the residuals y - h^(t-1)(x), i.e. to the negative gradient of the training error with respect to the predictions; adding it with learning rate eta lowers the training error in every iteration.
eta, T = 0.5, 300
h_tr = np.full(m, y_tr.mean()); h_va = np.full(m, y_tr.mean())
learners = []
err_tr, err_va = [trainerr(h_tr, y_tr)], [trainerr(h_va, y_va)]
monotone = True
for t in range(1, T + 1):
residual = y_tr - h_tr # negative gradient (up to 2/m)
g = fit_stump(x_tr, residual)
learners.append(g)
h_tr = h_tr + eta * g(x_tr); h_va = h_va + eta * g(x_va)
err_tr.append(trainerr(h_tr, y_tr)); err_va.append(trainerr(h_va, y_va))
monotone &= err_tr[-1] < err_tr[-2]
grad_check = np.allclose(residual, -0.5 * m * (-(2.0 / m) * residual))
check(f"[B-gradstep] residuals are the negative gradient of the training "
f"error (up to the factor 2/m), and all {T} iterations lower it: "
f"{err_tr[0]:.3f} -> {err_tr[-1]:.4f}", monotone and grad_check)
[ok] [B-gradstep] residuals are the negative gradient of the training error (up to the factor 2/m), and all 300 iterations lower it: 0.445 -> 0.0101
The training error falls below 0.02 by T = 300, while the validation error reaches its minimum at an earlier iteration and is at least 0.03 larger at T = 300 than at that minimum: early stopping picks the number of iterations.
t_best = int(np.argmin(err_va))
check(f"[B-overfit] training error {err_tr[-1]:.4f} at T={T}; validation "
f"error minimal at t={t_best} ({err_va[t_best]:.3f}), larger at T="
f"{T} ({err_va[-1]:.3f})",
err_tr[-1] < 0.02 and t_best < T and err_va[-1] > err_va[t_best] + 0.03)
[ok] [B-overfit] training error 0.0101 at T=300; validation error minimal at t=22 (0.105), larger at T=300 (0.158)
Averaging 300 base learners, each trained on a random draw with replacement from the training pairs (bagging), leaves the training error more than five times that of accumulating them (boosting).
bag_err = []
bag_sum = np.zeros(m)
for b in range(1, T + 1):
idx = rng.integers(0, m, m)
g = fit_stump(x_tr[idx], y_tr[idx])
bag_sum += g(x_tr)
bag_err.append(trainerr(bag_sum / b, y_tr))
check(f"[B-bagging] training error of {T} averaged base learners "
f"{bag_err[-1]:.3f} vs {err_tr[-1]:.4f} for {T} accumulated ones",
bag_err[-1] > 5 * err_tr[-1])
# ---------------------------------------------------------------- CSV
with open(OUT_DIR / "boosting_errors.csv", "w") as fh:
fh.write("t,trainerr,valerr,bagging_trainerr\n")
for t in range(T + 1):
be = bag_err[t - 1] if t > 0 else trainerr(np.full(m, y_tr.mean()), y_tr)
fh.write(f"{t},{err_tr[t]:.4f},{err_va[t]:.4f},{be:.4f}\n")
xg = np.linspace(0.0, 1.0, 201)
def boosted(xs, n):
out = np.full(len(xs), y_tr.mean())
for g in learners[:n]:
out = out + eta * g(xs)
return out
with open(OUT_DIR / "boosting_fit.csv", "w") as fh:
fh.write("x,truth,h_early,h_final\n")
for a, b, c, d in zip(xg, truth(xg), boosted(xg, t_best), boosted(xg, T)):
fh.write(f"{a:.4f},{b:.4f},{c:.4f},{d:.4f}\n")
# -------------------------------------------------------------- preview
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.6, 3.9))
ts = np.arange(T + 1)
ax1.plot(ts, err_tr, "k-", lw=1.3, label="training error (boosting)")
ax1.plot(ts, err_va, "k--", lw=1.3, label="validation error (boosting)")
ax1.plot(ts, [err_tr[0]] + bag_err, "k:", lw=1.5, label="training error (bagging)")
ax1.axvline(t_best, color="0.5", lw=0.8, ls="-.", label=f"early stopping, t={t_best}")
ax1.set_xlabel("iteration $t$"); ax1.set_ylabel("average squared error")
ax1.set_title("accumulated vs averaged base learners")
ax1.legend(frameon=False, fontsize=8)
ax2.plot(x_tr, y_tr, "ko", ms=3, label="training pairs")
ax2.plot(xg, truth(xg), "k-", lw=1.0, label="label function")
ax2.plot(xg, boosted(xg, t_best), "k--", lw=1.3, label=f"boosted hypothesis, t={t_best}")
ax2.plot(xg, boosted(xg, T), "k:", lw=1.3, label=f"boosted hypothesis, t={T}")
ax2.set_xlabel("feature $x$"); ax2.set_ylabel("label $y$")
ax2.set_title("boosting overfits when run too long")
ax2.legend(frameon=False, fontsize=8)
fig.tight_layout()
fig.savefig(OUT_DIR / "boosting.png", dpi=110)
n_ok = sum(ok for _, ok in report)
print(f"\n{n_ok}/{len(report)} checks pass")
print(f"wrote {OUT_DIR / 'boosting_errors.csv'}, {OUT_DIR / 'boosting_fit.csv'}, "
f"{OUT_DIR / 'boosting.png'}")
if n_ok != len(report):
raise SystemExit(1)
[ok] [B-bagging] training error of 300 averaged base learners 0.267 vs 0.0101 for 300 accumulated ones 3/3 checks pass wrote /Users/junga1/dictionaryappliedml/pythondemos/boosting_errors.csv, /Users/junga1/dictionaryappliedml/pythondemos/boosting_fit.csv, /Users/junga1/dictionaryappliedml/pythondemos/boosting.png
B-bagging writes when the script runs