The Bias–Variance Trade-off

Machine Learning · L-BiasVar

Target functions · overfitting · generalisation · the decomposition

The question we left open

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?

Learning objectives (1/2)

  1. distinguish the target function $t(\vec x)$, the noise $\epsilon$, and the hypothesis $h$,
  2. explain underfitting and overfitting in terms of the hypothesis set $\mathcal{H}$,
  3. distinguish in-sample error $E_{in}$, out-of-sample error $E_{out}$ and the generalisation error, and use a test set,

Learning objectives (2/2)

  1. state the bias–variance decomposition and interpret both terms,
  2. read learning curves and diagnose whether more data or a different model is needed.

Prerequisite: the recap Estimators — estimators, bias, variance, and $\operatorname{mse}(\hat\theta) = \operatorname{bias}(\hat\theta)^2 + \operatorname{var}(\hat\theta)$.

Overview

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:

Part The question it answers Sections
1 · Target function and noise What is a model supposed to learn, and which part of the data can it never learn? The target function · Noisy targets · The goal of learning · Sampling error · The learning diagram
2 · Underfitting and overfitting In which two ways can a fitted model fail, and how does the hypothesis set $\mathcal{H}$ cause each? Underfitting and overfitting in classification · The hypothesis set $\mathcal{H}$ · Underfitting · Overfitting
3 · Training error, test error, out-of-sample error Which error measures the quality of a model, and how is it estimated from data? Training error · Training error is not enough · Out-of-sample error (expected risk) · Generalisation error · Test data · Test error · The complete learning diagram
4 · Model complexity How does the richness of $\mathcal{H}$ trade fitting the data against generalising? The influence of complexity · A bound on generalisation
5 · The bias–variance decomposition Into which two parts does the expected out-of-sample error split, and which failure does each part measure? The quantity of interest · The average hypothesis · The decomposition · Interpretation: $\text{bias}^2$ · Interpretation: variance · The classic example
6 · Learning curves Given the errors at a growing training-set size: more data, or a different model? Goal, restated · How do we see whether the model fits? · Idealised learning curves · Reading a learning curve
In [1]:
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)

1. Target function and noise

The target function

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) . $$

Noisy targets

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)$.

The goal of learning

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.

Sampling error

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.

The learning diagram

No description has been provided for this image

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.

2. Underfitting and overfitting

In [2]:
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
In [3]:
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()
No description has been provided for this image

Underfitting and overfitting in classification

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) $$

In [4]:
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
In [5]:
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()
No description has been provided for this image

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 hypothesis set $\mathcal{H}$

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)$.

Underfitting

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$.

Overfitting

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.

3. Training error, test error, out-of-sample error

Training error

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.

Training error is not enough

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.

Out-of-sample error (expected risk)

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.

Generalisation error

$$ \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:

  • even without noise, there are too few data in $\mathcal{D}$, so the learning algorithm finds a poorly generalising $h$;
  • too few training data, so the noise is learned as well.

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.

Test data

$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\} $$

Test error

$$ \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.

The complete learning diagram

No description has been provided for this image

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.

In [6]:
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]
In [7]:
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()
No description has been provided for this image

$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.

4. Model complexity

Informally, the complexity (capacity) of $\mathcal{H}$ describes how many differently-complex functions are covered by $\mathcal{H}$.

Measures include

  • the VC dimension $d_{VC}$ (Vapnik–Chervonenkis dimension)
  • the Rademacher complexity

The influence of complexity

  • More complex $\mathcal{H}$ $\Rightarrow$ greater chance of being able to represent the target function — $t$ is in $\mathcal{H}$ or close to it.
  • Less complex $\mathcal{H}$ $\Rightarrow$ greater chance that the generalisation error is small.

Two forces pulling in opposite directions.

A bound on generalisation

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

  • the model complexity is not too high, and
  • there are enough training data.

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.

In [8]:
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()
No description has been provided for this image

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.

5. The bias–variance decomposition

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}$.

The quantity of interest

$$ \mathbb{E}_{\mathcal{D}}\left[E_{out}\bigl(h^{\mathcal{D}}\bigr)\right] $$

  • $h^{\mathcal{D}}$ — the hypothesis learned from training data $\mathcal{D}$
  • $E_{out}(h^{\mathcal{D}})$ — its out-of-sample error
  • $\mathbb{E}_{\mathcal{D}}$ — expectation over training sets (one training set = one event)

The average hypothesis

$$ \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.

The decomposition

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 $$

Interpretation: $\text{bias}^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.

No description has been provided for this image

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.

Interpretation: variance

$$ \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.

No description has been provided for this image

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.

The classic example

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:

  • $\mathcal{H}_0$: constant functions $h(x) = b$
  • $\mathcal{H}_1$: lines $h(x) = ax + b$

Which one gives the smaller expected out-of-sample error?

In [9]:
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
In [10]:
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}")
H0 (constant)    bias^2 = 0.499   variance = 0.249   E_out = 0.747
H1 (line)        bias^2 = 0.206   variance = 1.651   E_out = 1.857
In [11]:
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()
No description has been provided for this image

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.

6. Learning curves

Goal, restated

$$ h(\vec x) \approx t(\vec x) $$

is achieved when $E_{out}$ (i.e. the test error) is small. That holds if both:

  • $E_{in}$ is small — no underfitting
  • $|E_{out} - E_{in}|$ is small, i.e. test error $\approx$ training error — no overfitting

How do we see whether the model fits?

"Fitting" is relative to three quantities:

  • the number $m$ of training points in $\mathcal{D}_{train}$
  • the complexity of the hypothesis set $\mathcal{H}$
  • the strength of the noise $\epsilon$ relative to the target function $t$ — the signal-to-noise ratio

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.

Idealised learning curves

No description has been provided for this image

simple model

No description has been provided for this image

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.

In [12]:
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)
In [13]:
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
In [14]:
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()
No description has been provided for this image

Reading a learning curve

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.

7. Summary

The one identity

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.

Take away (1/2)

  1. An estimator is a random variable; it has a bias and a variance.
  2. Unbiased is not the goal — low error is. Trading bias for variance is often worth it.
  3. Data are noisy: $y = t(\vec x) + \epsilon$. A hypothesis should not fit the training targets perfectly.
  4. Underfitting = $\mathcal{H}$ too weak (high bias). Overfitting = $\mathcal{H}$ too powerful, fits the noise (high variance).

Take away (2/2)

  1. $E_{in}$ falls monotonically with complexity — it cannot select a model. Estimate $E_{out}$ with a test set.
  2. The test error is itself an estimator: small test sets give noisy verdicts.
  3. There is an optimal complexity, because $E_{in}$ falls while the complexity penalty rises.
  4. Learning curves tell you whether to get more data or change the model.

Where this leads

  • Regularisation — buying a variance reduction by constraining $\mathcal{H}$ continuously, instead of choosing a discrete degree.
  • Validation and cross-validation — how to select a model without burning the test set (→ L-Eval).

Everything here applies unchanged to logistic regression: only the loss function differs, and the decomposition is stated for squared loss purely for convenience.

Exercises and Lab

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.

Literature

  • [Abu] Y. Abu-Mostafa, M. Magdon-Ismail, H.-T. Lin: Learning from Data, AMLBook 2012 — especially §2.3 (bias–variance) and the learning diagrams. Course: http://home.caltech.edu/telecourse.html
  • [Has] T. Hastie, R. Tibshirani, J. Friedman: The Elements of Statistical Learning, Springer 2009 — chapter 7
  • Andrew Ng: Machine Learning, Coursera
  • C. M. Bishop: Pattern Recognition and Machine Learning, Springer 2006 — §3.2