Machine Learning · L-BiasVar
Target functions · overfitting · generalisation · the decomposition
Polynomial regression (→ L-MultiReg) ended with polynomials of degree 1, 3 and 12 fitted to the same data — and logistic regression (→ L-LogReg) ended with the same question for classification.
The training cost falls monotonically with model complexity — so it cannot tell us which model to choose.
This lecture answers: what should we measure instead, and why?
Prerequisite: the recap Estimators — estimators, bias, variance, and $\operatorname{mse}(\hat\theta) = \operatorname{bias}(\hat\theta)^2 + \operatorname{var}(\hat\theta)$.
The training error falls monotonically with model complexity, so it cannot choose a model. This lecture builds the quantity that can. Parts 1–2 state what a model is supposed to learn and the two ways it fails, Parts 3–4 replace the training error by the out-of-sample error and relate it to model complexity, Part 5 lifts the estimator's split $\operatorname{mse} = \operatorname{bias}^2 + \operatorname{var}$ from a number to a function, and Part 6 reads it off a plot:
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
np.set_printoptions(precision=4, suppress=True)
plt.rcParams["figure.figsize"] = (9, 4)
plt.rcParams["axes.grid"] = True
plt.rcParams["grid.alpha"] = 0.3
rng = np.random.default_rng(0)
We want to approximate an unknown function, the target function $t(\vec x)$.
If the targets $y$ were obtained deterministically from $\vec x$, we could write
$$ y = t(\vec x) . $$
In reality $t(\vec x^{(i)})$ does not equal $y^{(i)}$ — the data are noisy:
$$ y^{(i)} = t(\vec x^{(i)}) + \epsilon $$
with a random variable $\epsilon$ (stochastic noise).
So instead of a function we really have a probability distribution
$$ p(y \mid \vec x) , $$
and the noise distribution may itself depend on $\vec x$: $p(\epsilon \mid \vec x)$.
Find a hypothesis with
$$ h(\vec x) \approx t(\vec x) $$
for all interesting $\vec x$ — those where a prediction will be made, i.e. where $p(\vec x)$ is appreciable.
The training data are noisy: $y^{(i)} = t(\vec x^{(i)}) + \epsilon$.
So $h(\vec x^{(i)})$ should not match the training $y^{(i)}$ perfectly.
But how close should the agreement be?
That is the question this lecture exists to answer.
Which patterns come from the target function, and which arise by chance from the particular choice of training data?
A finite sample always contains accidental structure. A powerful enough model will happily learn it.
After [Abu]. Everything on this slide is fixed before learning starts — except the final hypothesis, which is chosen by the learning algorithm from $\mathcal H$ using the training examples.
def t_fun(x):
"""The (unknown) target function."""
return np.sin(np.pi * x)
def sample(n, noise=0.1, rng=rng):
x = np.sort(rng.uniform(0, 1, n))
return x, t_fun(x) + rng.normal(0, noise, n)
def poly_fit(x, y, degree):
"""Least-squares polynomial fit; returns the coefficient vector."""
return np.linalg.lstsq(np.vander(x, degree + 1, increasing=True), y, rcond=None)[0]
def poly_eval(theta, x):
return np.vander(x, len(theta), increasing=True) @ theta
x_tr, y_tr = sample(12)
xs = np.linspace(0, 1, 300)
fig, ax = plt.subplots(1, 3, figsize=(12, 3.6))
for a, d, title in zip(ax, [1, 2, 11], ["underfitting", "just right", "overfitting"]):
a.plot(xs, t_fun(xs), "g-", lw=2, label="target $t$")
a.plot(x_tr, y_tr, "rx", markersize=8, markeredgewidth=2, label="data")
a.plot(xs, poly_eval(poly_fit(x_tr, y_tr, d), xs), "b-", label=f"degree {d}")
a.set_ylim(-2, 2); a.set_title(f"{title} (degree {d})"); a.legend(fontsize=7)
plt.tight_layout(); plt.show()
The same three regimes appear in logistic regression, when the decision boundary is made more flexible with polynomial features:
$$ h_\theta(\vec x) = g\bigl(\theta_0 + \theta_1 x_1 + \theta_2 x_1 x_2 + \theta_3 x_2^2 + \theta_4 x_1^3 + \theta_5 x_1^2 x_2 + \dots\bigr) $$
from scipy.optimize import minimize
from scipy.special import expit # the sigmoid g(z) = 1 / (1 + e^{-z})
def in_class_1(X):
"""The (unknown) true class region: an ellipse."""
return X[:, 0] ** 2 + 1.3 * X[:, 1] ** 2 < 0.5
clf_rng = np.random.default_rng(4) # own generator: leaves `rng` untouched
X_clf = clf_rng.uniform(-1, 1, (60, 2))
y_clf = in_class_1(X_clf).astype(float)
flip = clf_rng.random(60) < 0.1 # 10 % label noise
y_clf[flip] = 1 - y_clf[flip]
def poly_features(X, degree):
"""All monomials x1^i x2^j with i + j <= degree, including the constant 1."""
return np.stack([X[:, 0] ** i * X[:, 1] ** j
for i in range(degree + 1) for j in range(degree + 1 - i)], axis=1)
def fit_logreg(X, y, degree):
"""Minimise the mean cross-entropy with BFGS, using its hand-derived gradient."""
Phi = poly_features(X, degree)
def cost(theta):
z = Phi @ theta
return np.mean(np.logaddexp(0.0, z) - y * z) # numerically stable form
def grad(theta):
return Phi.T @ (expit(Phi @ theta) - y) / len(y)
return minimize(cost, np.zeros(Phi.shape[1]), jac=grad, method="BFGS",
options={"maxiter": 5000}).x
g = np.linspace(-1.05, 1.05, 300)
G1, G2 = np.meshgrid(g, g)
grid = np.c_[G1.ravel(), G2.ravel()]
fig, ax = plt.subplots(1, 3, figsize=(12, 4))
for a, d, title in zip(ax, [1, 2, 10], ["underfitting", "just right", "overfitting"]):
theta = fit_logreg(X_clf, y_clf, d)
Z = (poly_features(grid, d) @ theta).reshape(G1.shape)
a.contour(G1, G2, in_class_1(grid).reshape(G1.shape).astype(float), levels=[0.5],
colors="g", linestyles="--", linewidths=1.5) # true boundary
a.contour(G1, G2, Z, levels=[0], colors="b", linewidths=2) # learned boundary
a.scatter(*X_clf[y_clf == 0].T, c="darkred", s=30, label="class 0")
a.scatter(*X_clf[y_clf == 1].T, marker="x", c="tab:blue", s=40, label="class 1")
a.set_title(f"{title} (degree {d})"); a.set_xlabel("$x_1$"); a.set_aspect("equal")
ax[0].set_ylabel("$x_2$"); ax[0].legend(fontsize=7, loc="lower left")
plt.tight_layout(); plt.show()
Green dashed: the true class boundary. Blue: the learned decision boundary $h_\theta(\vec x) = 0.5$.
Degree 1 cannot bend at all; degree 10 bends around individual — partly mislabelled — points.
The goal is $h(\vec x) \approx t(\vec x)$, where $h$ is chosen out of a set of hypotheses $\mathcal{H}$ by the training procedure.
Example — univariate linear regression.
$\mathcal{H}$ is the set of all (infinitely many) hypotheses $h_\theta(x) = \theta_0 + \theta_1 x$ obtained by varying $\theta$.
Training picks one particular $h_{\theta_{\text{final}}}$ out of $\mathcal{H}$ — e.g. the minimiser of the cost, $\forall \theta: J(\theta_{\text{final}}) \le J(\theta)$.
The goal $h(\vec x) \approx t(\vec x)$ cannot be reached, because none of the hypotheses in $\mathcal{H}$ is sufficiently similar to the target function.
The hypothesis set $\mathcal{H}$ is not powerful (complex) enough.
No amount of data or optimisation helps. The model simply cannot express $t$.
The hypothesis $h$ found by training adapts too much to the particular realisation of the training data.
$\mathcal{H}$ is very powerful (complex).
It fits the noise. On new data it does badly — even though the training error is excellent.
So far we had only the training set $\mathcal{D}$ and the average loss on it — what we called the cost function.
Training error (in-sample error):
$$ E_{in}(h) = \frac{1}{m}\sum_{i=1}^{m} \operatorname{loss}\bigl(h(\vec x^{(i)}), y^{(i)}\bigr) $$
Until now we wrote the training error as $J(\theta)$ — a function of the parameters of one fixed model, used to learn $\theta$.
Now we write $E_{in}(h)$ — a function of the hypothesis, because we want to compare different models.
Same number, different role.
A low training error does not imply a good model — that is exactly overfitting.
$$ h(\vec x) \approx t(\vec x) $$
is not guaranteed. $h$ can predict badly for $\vec x$ values not contained in the training set.
The average loss on "typical" further data that were not used for training:
$$ E_{out}(h) = \mathbb{E}_{\vec x, y}\bigl[\operatorname{loss}(h(\vec x), y)\bigr] = \int_{\mathcal{X}\times\mathcal{Y}} \operatorname{loss}(h(\vec x), y)\, dp(\vec x, y) $$
This is the risk (→ L-LinReg) — the thing we actually care about.
$$ \bigl| E_{out}(h) - E_{in}(h) \bigr| $$
The error introduced by adapting $h$ to the particular realisation of $\mathcal{D}_{\text{train}}$, compared with the expected prediction error.
Two reasons for the difference:
Terminology warning. The literature uses "generalisation error" for several different things — sometimes $E_{out}(h) - \inf_{h' \in \mathcal{H}} E_{out}(h')$, sometimes simply $E_{out}(h)$.
Always check which definition an author means.
$E_{out}$ is not directly accessible — we do not know $p(\vec x, y)$.
Introduce $m_{test}$ labelled test data to check whether $h$ also predicts well for values not used in training:
$$ \mathcal{D}_{test} = \bigl\{ (\vec x'^{(1)}, y'^{(1)}), \dots, (\vec x'^{(m_{test})}, y'^{(m_{test})}) \bigr\} $$
$$ \text{test error} = \frac{1}{m_{test}}\sum_{i=1}^{m_{test}} \operatorname{loss}\bigl(h(\vec x'^{(i)}), y'^{(i)}\bigr) $$
It serves as an estimate of the out-of-sample error:
$$ \text{test error} \;\approx\; E_{out}(h) $$
The test error is an estimator — of $E_{out}(h)$.
Everything about estimators applies (Estimators): it has a bias and a variance, its scatter shrinks like $1/\sqrt{m_{test}}$ — and it should be reported with an error bar (Uncertainty).
A test set that is too small gives a noisy verdict.
And a test set used to choose a model stops being an unbiased estimate of $E_{out}$ — which is why a separate validation set exists.
After [Abu]. Compared with section 1, the test examples are drawn from the same $p(\vec x)$ and the same target, set aside, and used only for the evaluation of the final hypothesis — never by the learning algorithm.
x_tr, y_tr = sample(15)
x_te, y_te = sample(500)
degrees = np.arange(0, 13)
E_in = [np.mean((poly_eval(poly_fit(x_tr, y_tr, d), x_tr) - y_tr) ** 2) for d in degrees]
E_te = [np.mean((poly_eval(poly_fit(x_tr, y_tr, d), x_te) - y_te) ** 2) for d in degrees]
plt.figure(figsize=(6.5, 4))
plt.plot(degrees, E_in, "o-", label=r"$E_{in}$ (training error)")
plt.plot(degrees, E_te, "s-", label=r"test error $\approx E_{out}$")
plt.axvline(degrees[int(np.argmin(E_te))], color="k", ls=":", label="best degree")
plt.yscale("log"); plt.xlabel("polynomial degree (model complexity)"); plt.ylabel("mean squared error")
plt.legend(fontsize=9); plt.show()
$E_{in}$ falls monotonically — as polynomial regression already showed, it cannot select a model.
The test error falls, reaches a minimum, and then rises. The gap between the two curves is the generalisation error.
Informally, the complexity (capacity) of $\mathcal{H}$ describes how many differently-complex functions are covered by $\mathcal{H}$.
Measures include
Two forces pulling in opposite directions.
Theory gives, with probability at least $1 - \delta$:
$$ E_{out}(h) \;\le\; E_{in}(h) + \Omega(m, \mathcal{H}, \delta) $$
with, using the VC dimension as the complexity measure,
$$ \Omega(m, \mathcal{H}, \delta) \le \sqrt{\frac{8}{m}\ln\left(\frac{4\bigl((2m)^{d_{VC}} + 1\bigr)}{\delta}\right)} $$
So learning (generalisation) is possible if
Note that $E_{in}(h)$ falls with increasing complexity while $\Omega$ rises. Hence there is an optimal model complexity, a compromise between the two terms.
c = np.linspace(0.3, 10, 200)
E_in_s, Omega = 1.0 / (1 + c), 0.28 * np.sqrt(c)
plt.figure(figsize=(6.5, 4))
plt.plot(c, E_in_s, label=r"$E_{in}$ (in-sample error)")
plt.plot(c, Omega, label=r"$\Omega$ (model complexity penalty)")
plt.plot(c, E_in_s + Omega, "k-", lw=2, label=r"bound on $E_{out}$")
plt.axvline(c[int(np.argmin(E_in_s + Omega))], color="r", ls=":", label="optimal complexity")
plt.xlabel(r"model complexity $d_{VC}$"); plt.ylabel("error")
plt.legend(fontsize=9); plt.show()
This is a schematic — the constants are illustrative, not measured. The shape is what matters, and the VC bound is usually far too loose to use numerically.
Its value is conceptual: it explains why an optimum exists.
For squared loss and regression the decomposition is simple. Analogous results hold for classification and other loss functions.
Learning the hypothesis set $\mathcal{H}$ with training data $\mathcal{D}$ yields a hypothesis $h^{\mathcal{D}}$ — the superscript marks the dependence on $\mathcal{D}$.
$$ \mathbb{E}_{\mathcal{D}}\left[E_{out}\bigl(h^{\mathcal{D}}\bigr)\right] $$
$$ \tilde h(\vec x) = \mathbb{E}_{\mathcal{D}}\left[h^{\mathcal{D}}(\vec x)\right] $$
The hypothesis we would get by averaging the models learned from all possible training sets. It is a theoretical device — but we can approximate it by simulation.
Without noise, with squared error:
$$ \mathbb{E}_{\mathcal{D}}\left[E_{out}(h^{\mathcal{D}})\right] = \mathbb{E}_{\mathcal{D}}\left[\mathbb{E}_{\vec x}\left[\bigl(h^{\mathcal{D}}(\vec x) - t(\vec x)\bigr)^2\right]\right] $$
Swap the order of the expectations and insert $\pm\,\tilde h(\vec x)$:
$$ \boxed{\; \mathbb{E}_{\mathcal{D}}\left[E_{out}(h^{\mathcal{D}})\right] = \underbrace{\mathbb{E}_{\vec x}\left[\mathbb{E}_{\mathcal{D}}\left[\bigl(h^{\mathcal{D}}(\vec x) - \tilde h(\vec x)\bigr)^2\right]\right]}_{\textbf{variance}} + \underbrace{\mathbb{E}_{\vec x}\left[\bigl(\tilde h(\vec x) - t(\vec x)\bigr)^2\right]}_{\textbf{bias}^2} \;} $$
This is the estimator identity (Estimators) $\operatorname{mse} = \operatorname{bias}^2 + \operatorname{var}$, applied at every $\vec x$ and then averaged.
With noise a third term appears: the irreducible error (Bayes error), the variance of $\epsilon$ itself.
No model can do better than that, no matter how much data.
$$ \mathbb{E}_{\mathcal{D}}\left[E_{out}\right] = \text{bias}^2 + \text{variance} + \sigma_\epsilon^2 $$
$$ \mathbb{E}_{\vec x}\left[\bigl(\tilde h(\vec x) - t(\vec x)\bigr)^2\right] $$
Squared deviation of the average hypothesis $\tilde h$ from the target function $t$.
$\;\longleftrightarrow\;$ underfitting
It measures what the model cannot express, however much data it gets.
Each dot is one hypothesis in $\mathcal H$. The bias is the distance from the target function to what $\mathcal H$ can reach on average.
$$ \mathbb{E}_{\vec x}\left[\mathbb{E}_{\mathcal{D}}\left[\bigl(h^{\mathcal{D}}(\vec x) - \tilde h(\vec x)\bigr)^2\right]\right] $$
Average squared deviation of the learned hypotheses $\{h^{\mathcal{D}}\}$ from their own average $\tilde h$.
$\;\longleftrightarrow\;$ overfitting
It measures how much the model wobbles when the training data change.
Here the average hypothesis is close to the target (low bias), but each training set picks a different hypothesis from the red region — the variance.
Target $t(x) = \sin(\pi x)$ — the same function as before, now on $[-1, 1]$ — and a training set of just two points.
Two hypothesis sets:
Which one gives the smaller expected out-of-sample error?
reps = 20_000
xg = np.linspace(-1, 1, 400)
t_g = np.sin(np.pi * xg)
xp = rng.uniform(-1, 1, (reps, 2))
yp = np.sin(np.pi * xp)
H0 = np.repeat(yp.mean(axis=1)[:, None], xg.size, axis=1) # best constant
slope = (yp[:, 1] - yp[:, 0]) / (xp[:, 1] - xp[:, 0])
H1 = slope[:, None] * xg + (yp[:, 0] - slope * xp[:, 0])[:, None] # line through both
for name, H in [("H0 (constant)", H0), ("H1 (line)", H1)]:
h_bar = H.mean(axis=0)
bias2 = np.mean((h_bar - t_g) ** 2)
var = np.mean((H - h_bar) ** 2)
print(f"{name:15} bias^2 = {bias2:.3f} variance = {var:.3f} "
f"E_out = {bias2 + var:.3f}")
fig, ax = plt.subplots(1, 2, figsize=(11, 3.8))
for a, (name, H) in zip(ax, [("$\\mathcal{H}_0$: constant", H0), ("$\\mathcal{H}_1$: line", H1)]):
for k in range(60):
a.plot(xg, H[k], color="steelblue", alpha=0.12, lw=1)
a.plot(xg, t_g, "g-", lw=2, label="target $\\sin(\\pi x)$")
a.plot(xg, H.mean(axis=0), "r-", lw=2, label=r"average $\tilde h$")
a.set_ylim(-3, 3); a.set_title(name); a.legend(fontsize=8)
plt.tight_layout(); plt.show()
The simpler model wins — decisively.
$\mathcal{H}_1$ has the lower bias (a line approximates a sine better than a constant), but with only two data points its variance is enormous: every pair of points gives a wildly different line.
Choosing the model is not about matching the target. It is about balancing what the model can express against how much it wobbles.
$$ h(\vec x) \approx t(\vec x) $$
is achieved when $E_{out}$ (i.e. the test error) is small. That holds if both:
"Fitting" is relative to three quantities:
A learning curve plots $E_{in}$ and $E_{out}$ as functions of the training set size $m$, for a fixed model.
Its shape tells you which of the three is your problem.
simple model
complex model
Schematic, after [Abu]. Both curves approach the dashed level, bias + irreducible error. The variance is how far $E_{out}$ lies above that level; the generalisation error is the gap $E_{out} - E_{in}$. The complex model has the lower asymptote but needs many more data before the gap closes. The simulation below measures exactly these curves.
def learning_curve(degree, sizes, trials=60, noise=0.1):
ein, eout = [], []
x_te, y_te = sample(2000, noise)
for m in sizes:
a, b = [], []
for _ in range(trials):
x, y = sample(m, noise)
th = poly_fit(x, y, degree)
a.append(np.mean((poly_eval(th, x) - y) ** 2))
b.append(np.mean((poly_eval(th, x_te) - y_te) ** 2))
ein.append(np.mean(a)); eout.append(np.mean(b))
return np.array(ein), np.array(eout)
sizes = np.arange(3, 61, 3)
ein_s, eout_s = learning_curve(1, sizes) # simple model
ein_c, eout_c = learning_curve(9, sizes) # complex model
fig, ax = plt.subplots(1, 2, figsize=(11, 4), sharey=True)
for a, (ein, eout, ttl) in zip(ax, [(ein_s, eout_s, "simple model (degree 1)"),
(ein_c, eout_c, "complex model (degree 9)")]):
a.plot(sizes, ein, "o-", label=r"$E_{in}$")
a.plot(sizes, eout, "s-", label=r"$E_{out}$")
a.set_xlabel("training set size $m$"); a.set_title(ttl); a.legend(fontsize=9)
ax[0].set_ylabel("mean squared error"); ax[0].set_ylim(0, 0.4)
plt.tight_layout(); plt.show()
Simple model — the two curves converge quickly, but to a high error.
$\Rightarrow$ high bias / underfitting. More data will not help; you need a richer model.
Complex model — a large gap: $E_{in}$ is very low, $E_{out}$ much higher, and the gap closes only slowly.
$\Rightarrow$ high variance / overfitting. More data will help — or reduce the complexity, or regularise.
This is the practical payoff of the whole lecture: from a learning curve you can tell whether to collect more data or change the model — two very differently expensive decisions.
For an estimator of a number:
$$ \operatorname{mse}(\hat\theta) = \operatorname{bias}(\hat\theta)^2 + \operatorname{var}(\hat\theta) $$
For a model predicting a function:
$$ \mathbb{E}_{\mathcal{D}}\left[E_{out}\right] = \text{bias}^2 + \text{variance} \;(+\; \sigma_\epsilon^2) $$
Same algebra, one level up.
Everything here applies unchanged to logistic regression: only the loss function differs, and the decomposition is stated for squared loss purely for convenience.
lecture-BiasVar-exercises.ipynb — pen and paper: bias and variance of a model, read as the mse identity
of an estimator one level up; training, test and out-of-sample error, and model selection.
lecture-BiasVar-lab.ipynb — programming: training and test error against complexity, bias and variance
of polynomial models measured over many training sets, the $\sin(\pi x)$ example and learning curves.
The exercises on probability and on estimators belong to the recaps Probability and Estimators.