B-output writes when the script runsDictionary of Applied Machine Learning · overfitting
Numerical companion to the entry overfitting: it recomputes what the entry states and prints one line per check
Run it without installing anything:uv run https://dictionaryofml.org/terms/overfitting.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 overfitting.py into a folder and run uv run overfitting.py there. With NumPy and Matplotlib already installed, python3 overfitting.py, from any directory — it writes its output files into the current directory. Fixed seeds, so the printed numbers reproduce exactly. Download overfitting.py · Notebook · Open in Colab
One cell per block of the script: the code, and what that code printed when it last ran here
#!/usr/bin/env python3
"""
overfitting.py — Training error vs. validation error over polynomial degree.
This demo generates the data behind the polynomial-degree figure of the
"overfitting" entry. It illustrates overfitting as a growing gap between a
small training error and a large validation error as the model capacity
(polynomial degree) increases.
Setup
-----
The true relationship between a scalar feature x and a label y is the
sinusoid f(x) = sin(2*pi*x) on x in [0, 1]. Training sets of m = 5,
m = 10, and m = 20 data points are drawn uniformly on [0, 1] with
additive Gaussian label noise, y = f(x) + eps, eps ~ N(0, sigma^2),
sigma = 0.2. A single validation set of 100 data points is drawn from
the same distribution and shared by all three training-set sizes, so
their validation errors are comparable.
For each polynomial degree p = 0, 1, ..., 9 a polynomial hypothesis is
learned by empirical risk minimization under the squared-error loss
(polynomial fit on the Vandermonde matrix). Degree p = 9 has 10 model
parameters and interpolates the m = 10 training points exactly; for
m = 5 every degree p >= 4 already interpolates, while for m = 20 no
degree in the sweep can.
Output
------
Three CSV files (committed to the repo) are written to pythondemos/:
overfitting_errors.csv degree,trainerr,valerr (m = 10)
overfitting_errors_m5.csv degree,trainerr,valerr (m = 5)
overfitting_errors_m20.csv degree,trainerr,valerr (m = 20)
trainerr — average squared-error loss on the training set
valerr — average squared-error loss on the validation set
For m = 10 the training error decreases monotonically with the degree
and reaches (numerically) zero at r = 9, while the validation error
passes through a minimum at moderate degree and then grows by orders of
magnitude: the high-degree polynomials overfit the training set. The
comparison across training-set sizes shows the validation error growing
earlier and further for m = 5 and staying much lower for m = 20 — the
generalization gap shrinks with the number of training data points. The
TikZ figure shows one panel of training/validation curves per
training-set size and reads the CSVs via pgfplots (log-scaled y-axis),
so the LaTeX build does not depend on Python. A matplotlib preview with
the same three panels is written to pythondemos/overfitting.png.
Reproducibility
---------------
The numpy RNG is seeded from 5 (RNG = default_rng(5)); the extra
training sets of size 5 and 20 use their own seeded generators
(default_rng(500 + m)), so the m = 10 draws — and with them the
original overfitting_errors.csv — are bit-identical to the two-CSV-era
output, and re-running produces bit-identical CSVs. Run from the repo
root:
python3 pythondemos/overfitting.py
Blocks
------
[B-data] the sinusoid, the training sets of m = 5, 10, 20 noisy data
points, and the shared validation set of 100 data points from
the same distribution
[B-sweep] ERM with the squared-error loss over polynomials of degree
0, ..., 9, for each training-set size: training error falls
with the degree, validation error passes through a minimum and
then grows — the earlier and the further, the smaller the
training set
[B-three] the three collinear points of the first figure: ERM over the
constants has a unique solution that meets one point of three,
ERM over the linear model is unique and interpolating, and over
all continuous functions a whole family attains zero training
error, so ERM has no unique solution there
[B-reg] the three elementary forms of regularization applied to the
overfitting degree-9 fit -- pruning the model, a penalty term on
the empirical risk, and augmenting the training set -- each
lowering the validation error
[B-output] the committed CSV and the matplotlib preview
"""
from __future__ import annotations
import warnings
from pathlib import Path
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
OUTDIR = Path(__file__).resolve().parent
RNG = np.random.default_rng(5)
M_TRAIN = 10
M_VAL = 100
SIGMA = 0.2
MAX_DEGREE = 9
def f_true(x: np.ndarray) -> np.ndarray:
return np.sin(2.0 * np.pi * x)
the sinusoid, the training sets of m = 5, 10, 20 noisy data points, and the shared validation set of 100 data points from the same distribution
x_train = RNG.uniform(0.0, 1.0, M_TRAIN)
y_train = f_true(x_train) + SIGMA * RNG.standard_normal(M_TRAIN)
x_val = RNG.uniform(0.0, 1.0, M_VAL)
y_val = f_true(x_val) + SIGMA * RNG.standard_normal(M_VAL)
# Extra training sets of size 5 and 20 from the same distribution, each
# with its own seeded generator so the m = 10 draws above stay unchanged.
# All three sizes share the validation set (x_val, y_val).
train_sets = {M_TRAIN: (x_train, y_train)}
for m in (5, 20):
g = np.random.default_rng(500 + m)
x_m = g.uniform(0.0, 1.0, m)
y_m = f_true(x_m) + SIGMA * g.standard_normal(m)
train_sets[m] = (x_m, y_m)
ERM with the squared-error loss over polynomials of degree 0, ..., 9, for each training-set size: training error falls with the degree, validation error passes through a minimum and then grows — the earlier and the further, the smaller the training set
degrees = np.arange(MAX_DEGREE + 1)
def sweep(x_tr: np.ndarray, y_tr: np.ndarray) -> tuple[np.ndarray, np.ndarray]:
"""ERM with the squared-error loss over polynomials of each degree."""
tr = np.empty_like(degrees, dtype=float)
va = np.empty_like(degrees, dtype=float)
for r in degrees:
# For degree p >= len(x_tr) there are more model parameters than
# data points, so the minimizer is not unique; the fit still
# minimizes the training error — silence the RankWarning.
with np.errstate(all="ignore"), warnings.catch_warnings():
warnings.simplefilter("ignore")
coeffs = np.polynomial.polynomial.polyfit(x_tr, y_tr, int(r))
yhat_train = np.polynomial.polynomial.polyval(x_tr, coeffs)
yhat_val = np.polynomial.polynomial.polyval(x_val, coeffs)
tr[r] = np.mean((y_tr - yhat_train) ** 2)
va[r] = np.mean((y_val - yhat_val) ** 2)
# Floor the (numerically zero) training error at high degrees so the
# log-scaled pgfplots axis stays finite and readable.
return np.maximum(tr, 1e-6), va
errors = {m: sweep(*train_sets[m]) for m in sorted(train_sets)}
trainerr, valerr = errors[M_TRAIN]
for m in sorted(errors):
tr, va = errors[m]
print(f"[B-sweep] m = {m}: degree trainerr valerr")
for r in degrees:
print(f"{r:>24} {tr[r]:.3e} {va[r]:.3e}")
[B-sweep] m = 5: degree trainerr valerr
0 2.587e-01 9.227e-01
1 2.368e-01 7.202e-01
2 3.815e-02 1.605e+00
3 6.834e-03 5.490e-02
4 1.000e-06 4.405e+01
5 1.000e-06 2.104e+01
6 1.000e-06 1.084e+01
7 1.000e-06 5.914e+00
8 1.000e-06 3.377e+00
9 1.000e-06 2.004e+00
[B-sweep] m = 10: degree trainerr valerr
0 4.497e-01 6.121e-01
1 2.916e-01 3.312e-01
2 2.784e-01 3.205e-01
3 3.401e-02 6.034e-02
4 1.622e-02 1.108e-01
5 1.185e-02 3.268e-01
6 1.162e-02 4.155e-01
7 1.102e-02 3.243e+00
8 7.864e-05 9.588e+01
9 1.000e-06 2.244e+02
[B-sweep] m = 20: degree trainerr valerr
0 5.344e-01 7.642e-01
1 2.510e-01 2.912e-01
2 2.132e-01 3.177e-01
3 3.525e-02 5.741e-02
4 3.503e-02 5.673e-02
5 1.338e-02 1.072e-01
6 1.324e-02 1.209e-01
7 1.271e-02 1.630e-01
8 1.006e-02 1.289e-01
9 8.506e-03 1.246e+00
the three collinear points of the first figure: ERM over the constants has a unique solution that meets one point of three, ERM over the linear model is unique and interpolating, and over all continuous functions a whole family attains zero training error, so ERM has no unique solution there
# The first figure of the entry fits three points that lie on a straight line,
# using three nested hypothesis spaces. Nothing here is drawn by hand: each
# claim the paragraph makes is checked numerically.
x3 = np.array([1.0, 2.0, 3.0])
y3 = np.array([1.0, 2.0, 3.0])
# H1, the constants h(x) = b. ERM over a constant has the average label as its
# unique solution, and it cannot reach the outer two points.
b_hat = float(y3.mean())
err_const = float(np.mean((y3 - b_hat) ** 2))
hit_const = int(np.sum(np.isclose(y3, b_hat)))
# H2, the linear model h(x) = w x + b. Three distinct feature values
# determine the two model parameters, so the solution is unique; the
# points lie on one line, so it attains zero training error.
c_lin = np.polynomial.polynomial.polyfit(x3, y3, 1)
err_lin = float(np.mean((y3 - np.polynomial.polynomial.polyval(x3, c_lin)) ** 2))
rank_lin = int(np.linalg.matrix_rank(np.vander(x3, 2, increasing=True)))
# H3, all continuous functions. Every member of the family
# h_c(x) = x + c sin(2 pi (x - 1))
# is continuous and passes through all three points, whatever c is, so ERM has
# infinitely many solutions there and the training error cannot choose.
cs = np.array([0.0, 0.25, 0.55, 1.0, -2.0, 7.5])
err_family = np.array([np.mean((y3 - (x3 + c * np.sin(2 * np.pi * (x3 - 1)))) ** 2)
for c in cs])
print(f"[B-three] H1 constants: b = {b_hat:.3f}, trainerr = {err_const:.3f}, "
f"points met = {hit_const} of 3")
print(f"[B-three] H2 linear: rank = {rank_lin} of 2 columns (unique), "
f"trainerr = {err_lin:.2e}")
cs_txt = ", ".join(f"{c:g}" for c in cs)
print(f"[B-three] H3 continuous: trainerr for c = {cs_txt}:")
print(f"[B-three] {np.array2string(err_family, precision=2)}"
f" -> all zero, so ERM has no unique solution")
assert hit_const == 1 and err_const > 0.5 # the constant underfits
assert rank_lin == 2 and err_lin < 1e-20 # unique, and interpolating
assert np.all(err_family < 1e-20) # a continuum of ERM solutions
[B-three] H1 constants: b = 2.000, trainerr = 0.667, points met = 1 of 3 [B-three] H2 linear: rank = 2 of 2 columns (unique), trainerr = 1.31e-31 [B-three] H3 continuous: trainerr for c = 0, 0.25, 0.55, 1, -2, 7.5: [B-three] [0.00e+00 0.00e+00 8.22e-32 8.22e-32 3.29e-31 5.26e-30] -> all zero, so ERM has no unique solution
the three elementary forms of regularization applied to the overfitting degree-9 fit -- pruning the model, a penalty term on the empirical risk, and augmenting the training set -- each lowering the validation error
# The degree-9 fit above overfits. Each elementary form of regularization is
# applied to it in turn, and the validation error is reported. Pruning the
# model and augmenting the training set reuse what is already above; the
# penalty term is a ridge solve on the same polynomial fit.
deg9_val = float(valerr[MAX_DEGREE])
# 1. pruning the model: search degree 3 rather than degree 9
c_pruned = np.polynomial.polynomial.polyfit(x_train, y_train, 3)
val_pruned = float(np.mean(
(y_val - np.polynomial.polynomial.polyval(x_val, c_pruned)) ** 2))
# 2. a penalty term on the empirical risk: ridge on the degree-9 coefficients
V_train = np.vander(x_train, MAX_DEGREE + 1, increasing=True)
V_val = np.vander(x_val, MAX_DEGREE + 1, increasing=True)
LAMBDA = 1e-3
w_ridge = np.linalg.solve(
V_train.T @ V_train + LAMBDA * np.eye(MAX_DEGREE + 1), V_train.T @ y_train)
val_ridge = float(np.mean((y_val - V_val @ w_ridge) ** 2))
# 3. augmenting the training set: more data points from the same distribution
x_aug = np.concatenate([x_train, RNG.uniform(0.0, 1.0, 90)])
y_aug = f_true(x_aug) + SIGMA * RNG.standard_normal(x_aug.size)
y_aug[:M_TRAIN] = y_train # keep the original labels
c_aug = np.polynomial.polynomial.polyfit(x_aug, y_aug, MAX_DEGREE)
val_aug = float(np.mean(
(y_val - np.polynomial.polynomial.polyval(x_val, c_aug)) ** 2))
print(f"[B-reg] degree {MAX_DEGREE}, no regularization: valerr = {deg9_val:.3e}")
print(f"[B-reg] pruning the model (degree 3): valerr = {val_pruned:.3e}")
print(f"[B-reg] penalty term (ridge, a={LAMBDA:g}): valerr = {val_ridge:.3e}")
print(f"[B-reg] data augmentation (100 pts): valerr = {val_aug:.3e}")
assert val_pruned < deg9_val # each form lowers the val error
assert val_ridge < deg9_val
assert val_aug < deg9_val
[B-reg] degree 9, no regularization: valerr = 2.244e+02 [B-reg] pruning the model (degree 3): valerr = 6.034e-02 [B-reg] penalty term (ridge, a=0.001): valerr = 8.150e-02 [B-reg] data augmentation (100 pts): valerr = 4.724e-02
the committed CSV and the matplotlib preview """ from __future__ import annotations import warnings from pathlib import Path import numpy as np import matplotlib matplotlib.use("Agg") import matplotlib.pyplot as plt
csv_names = {5: "overfitting_errors_m5.csv",
10: "overfitting_errors.csv",
20: "overfitting_errors_m20.csv"}
for m, name in csv_names.items():
tr, va = errors[m]
with (OUTDIR / name).open("w") as fh:
fh.write("degree,trainerr,valerr\n")
for r in degrees:
fh.write(f"{r},{tr[r]:.6e},{va[r]:.6e}\n")
# One panel per training-set size, sharing the y-axis so the panels are
# comparable. Grayscale-safe: the two curves of a panel differ in line
# style AND marker shape, not only in color.
fig, axes = plt.subplots(1, 3, figsize=(8, 3.0), sharey=True)
for ax, m in zip(axes, sorted(errors)):
tr, va = errors[m]
ax.semilogy(degrees, tr, "o--", color="black", markersize=4,
label="training error")
ax.semilogy(degrees, va, "s-", color="tab:blue", markersize=4,
label="validation error")
ax.set_xlabel("degree $p$")
ax.set_title(f"$m = {m}$", fontsize=10)
axes[0].set_ylabel("average squared-error loss")
axes[2].legend(frameon=False, fontsize=8, loc="lower left")
fig.suptitle("Training vs. validation error per training-set size",
fontsize=10)
fig.tight_layout()
fig.savefig(OUTDIR / "overfitting.png", dpi=110)
print("[B-output] wrote overfitting_errors{,_m5,_m20}.csv and overfitting.png")
[B-output] wrote overfitting_errors{,_m5,_m20}.csv and overfitting.png
B-output writes when the script runs