Machine Learning · Lecture 5

Lecture 5
Loss Functions and the Bias–Variance Trade-off

Part I · Foundations of supervised learning  |  decisions and costs, the Bayes decision rule, squared, absolute, quantile and Huber losses, losses as likelihoods, cross-entropy and KL divergence, surrogate losses and calibration, proper scoring rules, the bias–variance decomposition, approximation and estimation error  |  reading: Hastie, Tibshirani & Friedman, ESL, Sections 2.4, 7.1–7.3 and 10.6; Gneiting & Raftery (2007)

Cartoon: three targetsA stick figure holding a bow faces three targets labelled mean, median and 90 percent. It asks: which one should I aim for? A second stick figure answers: that depends on what a miss costs you. meanmedian90% Which one should Iaim for? That depends on whata miss costs you.
The loss function is where you say what you care about; the "best" prediction changes with it
In this lecture
  1. What a loss encodes
  2. Regression losses and what they estimate
  3. Losses from likelihoods
  4. Classification: the 0–1 loss and its surrogates
  5. Scoring probabilities: proper scoring rules
  6. Bias and variance, precisely
  7. Approximation, estimation, and choosing complexity
  8. Losses you will meet later
  9. Summary, exercises, projects, reading

Every method so far minimised some loss: squared error for regression, cross-entropy for logistic regression, 0–1 loss when counting mistakes. This lecture asks what those choices mean. A loss is not a neutral measure of error; it decides which feature of the data the model learns to predict. Squared loss learns the mean, absolute loss the median, the quantile loss a percentile. For probabilities, some losses reward honest forecasts and others reward exaggeration. Then we return to the U-shaped test error of Lecture 1 and take it apart exactly: noise, bias and variance, computed in closed form for ridge regression and nearest neighbours.

By the end of this lecture you should be able to derive the optimal decision from a predictive distribution and a loss, including cost-sensitive thresholds; say which statistical functional each regression loss estimates and prove it; read common losses as negative log-likelihoods and relate cross-entropy to KL divergence; explain why classifiers are trained on surrogate losses and which surrogates recover the Bayes classifier; define proper scoring rules and prove that the Brier and log scores are strictly proper; derive the bias–variance decomposition and compute bias and variance exactly for ridge and kNN; and separate approximation, estimation and optimisation error.

1 — What a loss encodes

A prediction is usually an input to a decision: order stock, send a patient for a biopsy, hold a flight. The loss should be the cost of that decision when the truth is revealed. Suppose we have a predictive distribution for \(Y\) given the features \(x\), from a model or a posterior. Which single action should we take?

theorem 5.1 — the Bayes decision rule

Given a loss \(\ell(a,y)\) for taking action \(a\) when the outcome is \(y\), the action minimising expected loss at \(x\) is

$$a^*(x)=\operatorname*{arg\,min}_a\ \mathbb E\big[\ell(a,Y)\mid X=x\big],$$

and using \(a^*(x)\) at every \(x\) minimises the overall risk \(\mathbb E[\ell(a(X),Y)]\).

In particular, for a binary outcome with \(\eta(x)=P(Y=1\mid x)\), a false negative costing \(c_{\text{FN}}\) and a false positive costing \(c_{\text{FP}}\), the optimal rule predicts 1 exactly when

$$\eta(x)\ \ge\ \frac{c_{\text{FP}}}{c_{\text{FP}}+c_{\text{FN}}}.$$

The risk of any rule \(a(\cdot)\) is

$$\mathbb E\big[\mathbb E[\ell(a(X),Y)\mid X]\big],$$

an average over \(x\) of the conditional expected loss. Minimising the inner expectation separately at each \(x\) minimises the average (the same argument as Theorem 1.3, which is the case of 0–1 loss).

For the binary case, predicting 1 costs \(c_{\text{FP}}(1-\eta)\) in expectation and predicting 0 costs \(c_{\text{FN}}\,\eta\). Predict 1 when

$$c_{\text{FN}}\,\eta\ \ge\ c_{\text{FP}}(1-\eta),$$

which rearranges to the threshold. With equal costs it is \(\tfrac12\). \(\square\)

If missing a cancer is ten times as costly as a false alarm, the threshold drops from ½ to \(1/11\approx0.09\). The theorem needs calibrated probabilities: the threshold is only right if \(\eta(x)\) means what it says. Here is the test set of Lecture 4's breast-cancer model.

Choosing a threshold from costs

171 test patients from Lecture 4, scored by penalised logistic regression. Set how much worse a missed cancer is than a false alarm. The curve is the total cost of each threshold on these patients; the moss line is the Bayes threshold \(1/(1+\text{ratio})\), the amber line your choice.

At a ratio of 20, the Bayes threshold 0.048 misses one cancer and raises 20 false alarms, a cost of 40 units; hindsight on these same patients finds a threshold costing only 24. That gap is the familiar optimism of choosing with the data you report on (Lecture 1, Section 4): the hindsight threshold is tuned to 64 particular malignant patients. The Bayes threshold was fixed before looking, and would be optimal if the probabilities were perfectly calibrated. They are not quite: only 17 of the 171 patients have probabilities between 0.2 and 0.8, so the middle of the probability scale is barely tested, and at a cost ratio of 5 the default threshold of ½ happens to beat the Bayes threshold on these particular patients. With a test set this small, differences of a few patients are noise (Lecture 1, Exercise 9).

spot check 5.1

A false negative costs 4 times as much as a false positive. Above what predicted probability should you predict positive?

\(c_{\text{FP}}/(c_{\text{FP}}+c_{\text{FN}})\) with \(c_{\text{FP}}=1\), \(c_{\text{FN}}=4\).
\(1/5=0.2\). At \(\eta=0.2\) the expected costs balance: predicting 1 costs \(0.8\times1\), predicting 0 costs \(0.2\times4\).
bayes — decision theory turns a posterior into an action

Bayesian inference ends with a posterior distribution; Bayesian decision theory says what to do with it. Theorem 5.1 applies with the posterior (predictive) distribution in place of the true conditional law. Under squared loss the optimal point estimate is the posterior mean; under absolute loss, the posterior median; under 0–1 loss for a discrete parameter, the posterior mode, the MAP estimate of Lecture 3. "Which estimate should I report?" is therefore not a question about the posterior at all, but about the loss. The classic reference is Berger (1985).

2 — Regression losses and what they estimate

definition 5.1 — four regression losses

With residual \(u=y-\hat y\):

theorem 5.2 — each loss estimates a different summary

For a random variable \(Y\) with finite mean, the constant \(c\) minimising \(\mathbb E[\ell(Y-c)]\) is:

Applied conditionally on \(X=x\), the best predictor under each loss is the conditional mean, median or quantile.

Squared.

$$\mathbb E[(Y-c)^2]=\mathrm{Var}(Y)+(\mathbb E Y-c)^2,$$

minimised at \(c=\mathbb EY\).

Pinball (absolute loss is twice \(\rho_{1/2}\)). The function \(g(c)=\mathbb E[\rho_\tau(Y-c)]\) is convex. Moving \(c\) up by a small \(h>0\) changes the loss of an outcome \(y>c\) by \(-\tau h\) (we under-predict it by less) and of an outcome \(y\le c\) by \(+(1-\tau)h\). So the right derivative is

$$g'_+(c)=-\tau P(Y>c)+(1-\tau)P(Y\le c)=P(Y\le c)-\tau,$$

and similarly the left derivative is \(P(Y<c)-\tau\).

A convex function is minimised where the left derivative is \(\le0\) and the right derivative is \(\ge0\):

$$P(Y<c)\le\tau\le P(Y\le c),$$

the definition of a \(\tau\)-quantile. \(\square\)

When the distribution is skewed, these summaries differ, and the difference is not a technicality.

data — every flight out of New York in 2013

All 336,776 flights that departed from JFK, LaGuardia and Newark in 2013, with scheduled and actual times, carrier, origin, destination and distance, from the US Bureau of Transportation Statistics, packaged by Hadley Wickham as the R package nycflights13 (CC0); we use the copy in the Rdatasets collection. 327,346 flights have an arrival delay (the rest were cancelled or diverted). Arrival delay is in minutes; negative means early.

code — the best single prediction under four losses
import numpy as np
import pandas as pd
from scipy.optimize import minimize_scalar

fl = pd.read_csv('data/flights.csv', usecols=['month', 'hour', 'origin', 'carrier', 'distance', 'arr_delay'])
fl = fl.dropna(subset=['arr_delay'])                # cancelled and diverted flights have no arrival delay
d = fl['arr_delay'].to_numpy()                      # minutes late on arrival (negative = early)
print(f'{len(d)} flights: mean {d.mean():.2f}, median {np.median(d):.0f}, 90th percentile {np.quantile(d, 0.9):.0f} minutes')

def pinball(u, tau):                                # the quantile loss
    return np.maximum(tau * u, (tau - 1) * u)

def huber(u, delta):
    return np.where(np.abs(u) <= delta, 0.5 * u ** 2, delta * (np.abs(u) - delta / 2))

losses = {'squared': lambda c: np.mean((d - c) ** 2),
          'absolute': lambda c: np.mean(np.abs(d - c)),
          'pinball, tau = 0.9': lambda c: np.mean(pinball(d - c, 0.9)),
          'Huber, delta = 15': lambda c: np.mean(huber(d - c, 15))}
for name, risk in losses.items():
    c = minimize_scalar(risk, bounds=(-60, 120), method='bounded', options={'xatol': 1e-4}).x
    print(f'{name:19s}: best constant prediction {c:6.2f} minutes')
327346 flights: mean 6.90, median -5, 90th percentile 52 minutes
squared            : best constant prediction   6.90 minutes
absolute           : best constant prediction  -5.00 minutes
pinball, tau = 0.9 : best constant prediction  52.00 minutes
Huber, delta = 15  : best constant prediction  -3.81 minutes

The mean delay is about 7 minutes late, the median 5 minutes early. Both are correct answers to different questions. Most flights arrive a little early; a long tail of badly delayed flights (the worst more than 21 hours) pulls the mean up. An airline promising "typical" arrival times should quote the median; one budgeting total passenger delay needs the mean; a traveller with a tight connection cares about the 90th percentile, 52 minutes. Huber loss lands near the median: it treats the tail as outliers to be resisted.

The loss chooses the target

Fifteen real arrival delays at JFK in 2013 (minutes). Drag any delay along the line. The curve below is the average loss of predicting the constant \(c\); its lowest point (rose) is the best prediction. Amber marks the mean, moss the median.

Drag the 248-minute delay further right: the mean follows it, the median does not move. A single bad record can shift a least-squares model as far as you like, which is why squared loss is called non-robust. Now fit linear models with features (hour, airport, airline, month and distance) under three losses, and score each on held-out flights with two metrics.

code — each loss wins on its own metric
from sklearn.linear_model import LinearRegression, QuantileRegressor, HuberRegressor

Xf = pd.get_dummies(fl[['hour', 'origin', 'carrier', 'month']].astype(str), drop_first=True).astype(float)
Xf['log_distance'] = np.log(fl['distance'].to_numpy())
idx = np.random.default_rng(0).permutation(len(fl))
tr, te = idx[:30_000], idx[30_000:60_000]
X_tr, X_te = Xf.to_numpy()[tr], Xf.to_numpy()[te]
y_tr, y_te = d[tr], d[te]

models = {'squared loss (OLS)': LinearRegression(),
          'absolute loss (median)': QuantileRegressor(quantile=0.5, alpha=0, solver='highs'),
          'Huber loss': HuberRegressor(epsilon=1.35, max_iter=2000)}
for name, m in models.items():
    p = m.fit(X_tr, y_tr).predict(X_te)
    print(f'{name:23s} test MSE {np.mean((p - y_te) ** 2):7.1f}   test MAE {np.mean(np.abs(p - y_te)):6.2f}'
          f'   average prediction {p.mean():6.2f}')
squared loss (OLS)      test MSE  1862.1   test MAE  26.80   average prediction   7.01
absolute loss (median)  test MSE  2011.6   test MAE  24.72   average prediction  -3.79
Huber loss              test MSE  1976.1   test MAE  24.76   average prediction  -2.38

Least squares has the lowest test MSE; least absolute deviations has the lowest test MAE; Huber sits between. There is no "best model" until the loss is fixed, and evaluating a model with a different loss from the one it was trained on is a common, quiet mistake.

spot check 5.2

Training with absolute loss estimates the conditional ; training with the pinball loss at \(\tau=0.9\) estimates the conditional .

Theorem 5.2.
With \(\tau=0.9\), under-prediction costs nine times as much as over-prediction, so the best prediction sits high: 90% of outcomes fall below it.
history — absolute or squared?

The absolute-error criterion is older than least squares. Roger Boscovich fitted a line to measurements of the Earth's shape in 1757 by minimising the sum of absolute deviations, and Pierre-Simon Laplace argued for absolute error in 1774. Squared error won in the nineteenth century largely for convenience: it has a closed-form minimiser, and Gauss tied it to the normal distribution (Lecture 3). The other losses returned when computers made optimisation cheap. Peter Huber's 1964 paper founded robust statistics, and Roger Koenker and Gilbert Bassett's 1978 quantile regression became a standard tool in economics for studying inequality, where what happens in the tails matters as much as the average.

3 — Losses from likelihoods

Lecture 3 showed that squared loss is the negative log-likelihood of Gaussian noise, and Lecture 4 that cross-entropy is the negative log-likelihood of a Bernoulli label. This is a general recipe: choose a noise distribution suited to the data, and its negative log-likelihood is the loss.

proposition 5.3 — a dictionary of likelihoods and losses

Up to terms that do not depend on the prediction \(\mu\):

model for \(Y\)negative log-likelihoodname
\(\mathcal N(\mu,\sigma^2)\)\((y-\mu)^2/2\sigma^2\)squared loss
Laplace\((\mu,b)\)\(|y-\mu|/b\)absolute loss
Bernoulli\((\mu)\)\(-y\log\mu-(1-y)\log(1-\mu)\)cross-entropy (log loss)
Poisson\((\mu)\)\(\mu-y\log\mu\)Poisson deviance

Take minus the log of each density and drop terms free of \(\mu\).

Gaussian: \(\tfrac12\log(2\pi\sigma^2)+(y-\mu)^2/2\sigma^2\).

Laplace, density \(\frac1{2b}e^{-|y-\mu|/b}\): \(\log2b+|y-\mu|/b\).

Bernoulli, mass \(\mu^y(1-\mu)^{1-y}\): immediate.

Poisson, mass \(e^{-\mu}\mu^y/y!\): \(\mu-y\log\mu+\log y!\).

The deviance rescales by 2 and subtracts the same expression at \(\mu=y\), so that a perfect prediction scores 0. \(\square\)

The cross-entropy has an information-theoretic reading that runs through the rest of the course.

definition 5.2 — entropy, cross-entropy, KL divergence

For distributions \(p\) and \(q\) on a finite set, the entropy is

$$H(p)=-\sum_kp_k\log p_k,$$

the cross-entropy is

$$H(p,q)=-\sum_kp_k\log q_k,$$

and the Kullback–Leibler divergence is

$$\mathrm{KL}(p\,\|\,q)=\sum_kp_k\log\frac{p_k}{q_k}=H(p,q)-H(p).$$
proposition 5.4 — Gibbs' inequality

\(\mathrm{KL}(p\,\|\,q)\ge0\), with equality if and only if \(q=p\).

Hence the cross-entropy \(H(p,q)\) is minimised over \(q\) exactly at \(q=p\).

Sum over \(k\) with \(p_k>0\). Since \(\log\) is concave, Jensen's inequality gives

$$-\mathrm{KL}(p\|q)=\sum_kp_k\log\frac{q_k}{p_k}\le\log\sum_kp_k\frac{q_k}{p_k}=\log\sum_{k:p_k>0}q_k\le\log1=0.$$

Equality in Jensen requires \(q_k/p_k\) to be constant on the support of \(p\), and equality in the last step requires \(q\) to put no mass elsewhere, together forcing \(q=p\). \(\square\)

So minimising average cross-entropy over training data is minimising the KL divergence from the empirical label distribution to the model's: a model trained with log loss is pushed to match the true probabilities, not just the most likely class. Not all data are Gaussian, and counts are the commonest exception.

data — hourly bike rentals in Washington, D.C.

Number of Capital Bikeshare rentals in each hour of 2011 (8,645 hours), with month, hour of day, working day, weather situation, temperature, humidity and wind speed. From Fanaee-T & Gama (2014), as distributed with the ISLP Python package (James et al., 2023). Counts range from 1 to 651 per hour.

code — counts: least squares versus Poisson regression, and quantile bands
from sklearn.linear_model import PoissonRegressor

bk = pd.read_csv('data/Bikeshare.csv')              # hourly rentals, Capital Bikeshare, 2011
Xb = pd.get_dummies(bk[['mnth', 'hr', 'weathersit']].astype(str), drop_first=True).astype(float)
Xb[['temp', 'hum', 'windspeed', 'workingday']] = bk[['temp', 'hum', 'windspeed', 'workingday']]
yb = bk['bikers'].to_numpy()
j = np.random.default_rng(1).permutation(len(bk)); a, b = j[:6000], j[6000:]
Xa, Xz = Xb.to_numpy()[a], Xb.to_numpy()[b]

ols = LinearRegression().fit(Xa, yb[a]).predict(Xz)
poi = PoissonRegressor(alpha=1e-6, max_iter=5000).fit(Xa, yb[a]).predict(Xz)
def deviance(y, mu):                                # mean Poisson deviance: 2 * (log-lik of perfect fit - log-lik of model)
    mu = np.maximum(mu, 1e-9)
    return 2 * np.mean(np.where(y > 0, y * np.log(y / mu), 0) - (y - mu))
for name, p in [('least squares', ols), ('Poisson', poi)]:
    print(f'{name:14s} negative predictions {np.sum(p < 0):3d}   test MSE {np.mean((p - yb[b]) ** 2):8.0f}'
          f'   Poisson deviance {deviance(yb[b], p):6.2f}')

q10 = QuantileRegressor(quantile=0.1, alpha=0, solver='highs').fit(Xa, yb[a]).predict(Xz)
q90 = QuantileRegressor(quantile=0.9, alpha=0, solver='highs').fit(Xa, yb[a]).predict(Xz)
print(f'10%-90% quantile band covers {np.mean((yb[b] >= q10) & (yb[b] <= q90)):.3f} of test hours (target 0.80);'
      f' below the band {np.mean(yb[b] < q10):.3f}, above {np.mean(yb[b] > q90):.3f}')
least squares  negative predictions 259   test MSE     5852   Poisson deviance  85.01
Poisson        negative predictions   0   test MSE     4990   Poisson deviance  27.62
10%-90% quantile band covers 0.786 of test hours (target 0.80); below the band 0.112, above 0.102

Least squares predicts a negative number of riders for 259 of the 2,645 test hours. Poisson regression models the log of the expected count, so its predictions are always positive; it also captures that busy hours vary more than quiet ones, and it has lower test MSE even though it was not trained on squared error. Two quantile regressions give an 80% prediction band that covers 78.6% of test hours, with misses split almost evenly above and below: an interval forecast, which no mean model provides.

spot check 5.3

Why can a least-squares model predict negative bike counts, while Poisson regression cannot?

What is \(\mu\) as a function of the linear score in each model?
Poisson regression sets \(\mu=e^{w^\top x}\), the log link; logistic regression sets \(\mu=\sigma(w^\top x)\), the logit link. Each maps a linear score into the range the outcome lives in. Models built this way are generalised linear models, and their gradients all have the form \(X^\top(\mu-y)\) (Exercise 2).

4 — Classification: the 0–1 loss and its surrogates

For classification the loss we care about is usually the 0–1 loss. With labels \(y=\pm1\) and score \(s=f(x)\), write the margin \(m=ys\): positive when the prediction is correct, large when it is correct and confident. The 0–1 loss is \(\mathbf 1[m\le0]\). It is a step function: flat almost everywhere, so its gradient is zero and gradient descent cannot move; and minimising it over linear classifiers is NP-hard in general. So we train on a convex surrogate \(\varphi(m)\) that upper-bounds the step and has useful gradients.

definition 5.3 — margin losses

Which surrogates are safe? Fix \(x\) with \(\eta=P(Y=1\mid x)\). The best score at \(x\) minimises the conditional \(\varphi\)-risk \(C_\eta(s)=\eta\,\varphi(s)+(1-\eta)\,\varphi(-s)\). A surrogate is classification-calibrated if, for every \(\eta\ne\tfrac12\), this minimiser has the same sign as \(2\eta-1\): it points the same way as the Bayes classifier.

Surrogate losses and what they learn

Left: losses against the margin \(m=ys\); toggle them on and off. Right: for the selected loss and a point with \(P(Y=1\mid x)=\eta\), the conditional risk \(C_\eta(s)\) and its minimiser \(s^*\) (rose).

theorem 5.5 — classification-calibration of convex losses (Bartlett, Jordan & McAuliffe, 2006)

A convex loss \(\varphi\) is classification-calibrated if and only if it is differentiable at 0 with \(\varphi'(0)<0\).

For such \(\varphi\) there is an increasing function \(\psi\) with \(\psi(0)=0\) such that, for every classifier \(f\),

$$\psi\big(R_{0\text{-}1}(f)-R^*\big)\ \le\ R_\varphi(f)-R_\varphi^*,$$

so driving the surrogate risk to its minimum drives the 0–1 risk to the Bayes risk.

If. Take \(\eta>\tfrac12\). Then

$$C_\eta'(0)=\eta\varphi'(0)-(1-\eta)\varphi'(0)=(2\eta-1)\varphi'(0)<0,$$

so \(C_\eta\) is strictly decreasing at 0. A convex function decreasing at 0 takes its values on \(s\le0\) no lower than \(C_\eta(0)\), which is strictly above its infimum; so every near-minimiser has \(s>0\), the sign of the Bayes classifier. The case \(\eta<\tfrac12\) is symmetric.

Only if. If \(\varphi\) is not differentiable at 0, or \(\varphi'(0)\ge0\), one can find \(\eta\ne\tfrac12\) for which \(s=0\) (or a wrong-signed \(s\)) minimises \(C_\eta\); the perceptron loss is the standard example, with \(s^*=0\) for every \(\eta\).

The construction of \(\psi\) is in the paper (Bartlett et al., 2006, Section 2). \(\square\)

Hinge, logistic, exponential and squared losses all qualify; the perceptron loss does not (try it in the widget: \(s^*=0\) whatever \(\eta\), so it never learns which way to lean). The surrogates also differ in what \(s^*\) means. For logistic loss \(s^*=\log\frac{\eta}{1-\eta}\), the log-odds, so the score can be turned back into a probability; exponential loss gives half the log-odds; squared loss gives \(2\eta-1\). The hinge loss gives only \(s^*=\operatorname{sign}(2\eta-1)\): it learns the Bayes classifier but throws away the probability, which is why support vector machines do not output probabilities without extra calibration.

spot check 5.4

Which of these losses is not classification-calibrated?

Look at the slope at \(m=0\).
The perceptron loss has a kink at 0, with right-hand slope 0. For any \(\eta\), \(C_\eta(s)\) is minimised at \(s=0\), which says nothing about which class is more likely. The perceptron still works on separable data because it never reaches the population minimum: it stops when the training mistakes run out.

5 — Scoring probabilities: proper scoring rules

When the output is a probability, the loss should reward telling the truth. Suppose a forecaster believes the chance of rain is \(p\). A good scoring rule should make reporting \(p\) the best strategy, in expectation, for every \(p\).

definition 5.4 — proper scoring rule

A scoring rule \(S(q,y)\) charges a forecaster who reports probability \(q\) for an event that then happens (\(y=1\)) or not (\(y=0\)).

It is proper if, for every true probability \(p\), the expected charge

$$\mathbb E_{Y\sim\text{Bern}(p)}S(q,Y)$$

is minimised at \(q=p\), and strictly proper if \(q=p\) is the unique minimiser.

The Brier score is

$$S(q,y)=(q-y)^2;$$

the log score is

$$S(q,y)=-y\log q-(1-y)\log(1-q).$$
theorem 5.6 — the Brier and log scores are strictly proper

If \(Y\sim\mathrm{Bern}(p)\), then for the Brier score and the log score respectively

$$\mathbb E\,S(q,Y)=(q-p)^2+p(1-p),\qquad\mathbb E\,S(q,Y)=H(p)+\mathrm{KL}\big(\mathrm{Bern}(p)\,\|\,\mathrm{Bern}(q)\big).$$

Both are uniquely minimised at \(q=p\).

Brier:

$$\mathbb E(q-Y)^2=p(q-1)^2+(1-p)q^2=q^2-2pq+p=(q-p)^2+p(1-p).$$

Log:

$$\mathbb E\,S=-p\log q-(1-p)\log(1-q)$$

is the cross-entropy of the two Bernoulli distributions, which equals entropy plus KL divergence (Definition 5.2) and is uniquely minimised at \(q=p\) by Gibbs' inequality. \(\square\)

Not every natural-looking score is proper. The absolute score \(|q-y|\) has expected value \(p(1-q)+(1-p)q\), linear in \(q\), so it is minimised by reporting 0 or 1: it rewards exaggeration (Exercise 6). Proper scores combine two virtues. Calibration: among all occasions forecast at 70%, the event happens about 70% of the time. Sharpness (or resolution): forecasts are far from the base rate, so they actually distinguish occasions. Always forecasting the base rate is perfectly calibrated and useless.

data — seventy years of NBA forecasts

FiveThirtyEight's pre-game win probabilities from its NBA Elo model for every regular-season and playoff game from 1946–47 to 2014–15, 63,157 games, computed retrospectively from game results with the Elo rating system (Silver & Fischer-Baum, 2015). Published in FiveThirtyEight's public data repository under CC BY 4.0. We take one row per game, from the home team's point of view.

code — scoring 63,157 probability forecasts
nba = pd.read_csv('data/nbaallelo.csv')
games = nba[nba['_iscopy'] == 0]                    # one row per game (the other row is the opponent's view)
p = games['forecast'].to_numpy()                    # FiveThirtyEight's pre-game win probability
y = (games['game_result'] == 'W').to_numpy(float)
def brier(q): return np.mean((q - y) ** 2)
def logscore(q): return -np.mean(y * np.log(q) + (1 - y) * np.log(1 - q))
base = np.full_like(p, y.mean())
print(f'{len(y)} games, {games.year_id.min()}-{games.year_id.max()}; the listed team won {y.mean():.3f} of them')
print(f'Elo forecast : Brier {brier(p):.4f}   log score {logscore(p):.4f}')
print(f'constant {y.mean():.3f}: Brier {brier(base):.4f}   log score {logscore(base):.4f}')
bins = np.clip((p * 10).astype(int), 0, 9)
rel = pd.DataFrame({'bin': bins, 'p': p, 'y': y}).groupby('bin').agg(n=('y', 'size'), forecast=('p', 'mean'), won=('y', 'mean'))
print(rel.round(3).to_string())
63157 games, 1947-2015; the listed team won 0.622 of them
Elo forecast : Brier 0.2038   log score 0.5931
constant 0.622: Brier 0.2350   log score 0.6629
         n  forecast    won
bin                        
0       23     0.092  0.087
1      675     0.166  0.181
2     2522     0.257  0.255
3     5053     0.354  0.350
4     7641     0.453  0.468
5    10518     0.553  0.552
6    13281     0.651  0.651
7    12541     0.749  0.747
8     8943     0.845  0.845
9     1960     0.923  0.928
Reliability diagram: for each tenth of the forecast range, the average forecast against the fraction of games won; the points lie almost exactly on the diagonal000.250.250.50.50.750.7511average forecast win probabilityfraction of games won
Reliability diagram for the Elo forecasts. Each dot is one tenth of the forecast range (dot area proportional to the number of games); a perfectly calibrated forecaster lies on the dashed diagonal.

The forecasts are remarkably well calibrated: games forecast at 65% were won 65.1% of the time, and every bin is within about two points of the diagonal. They are also sharp enough to beat the best constant, the home team's 62.2% win rate, by 13% in Brier score. For the constant forecast, the Brier score equals \(\bar y(1-\bar y)\), the irreducible "uncertainty" of a coin with that bias (Exercise 7).

spot check 5.5

A forecaster always says 50%. What is their Brier score, whatever happens?

Each game contributes \((0.5-y)^2\) with \(y\in\{0,1\}\).
\(0.25\) every time. Any useful forecaster of a balanced event must beat 0.25; the Elo model's 0.204 against the home-team constant's 0.235 shows how much skill there is in it.
spot check 5.6

You believe an event has probability 0.6. Under the Brier score, what happens to your expected score if you report 0.7 instead?

Use \(\mathbb E\,S=(q-p)^2+p(1-p)\).
Honest reporting gives \(0.24\); reporting 0.7 gives \(0.25\). Proper scores make honesty the best policy, which is why weather services, forecasting tournaments and probabilistic machine learning use them.

6 — Bias and variance, precisely

Lecture 1 decomposed squared error at a single point. Averaging over test points gives the version used in practice. Fix a learning algorithm; let \(\hat f_S\) be its fit on a random training set \(S\), and \(\bar f(x)=\mathbb E_S\hat f_S(x)\) its average fit.

theorem 5.7 — bias–variance decomposition

If \(Y=f(X)+\varepsilon\) with \(\mathbb E[\varepsilon\mid X]=0\) and \(\mathrm{Var}(\varepsilon\mid X)=\sigma^2\), and the test point \((X,Y)\) is independent of \(S\), then

$$\mathbb E_{S,X,Y}\big[(Y-\hat f_S(X))^2\big]=\sigma^2+\underbrace{\mathbb E_X\big[(\bar f(X)-f(X))^2\big]}_{\text{bias}^2}+\underbrace{\mathbb E_X\big[\mathrm{Var}_S\,\hat f_S(X)\big]}_{\text{variance}}.$$

Condition on \(X=x\). Proposition 1.2 gives

$$\mathbb E\big[(Y-\hat f_S(x))^2\mid X=x\big]=\sigma^2+(\bar f(x)-f(x))^2+\mathrm{Var}_S\hat f_S(x),$$

using the independence of \(S\) and the test noise. Averaging over \(X\) gives the result. \(\square\)

To see the trade-off, simulate. The truth is \(f(x)=\sin2\pi x\) on \([0,1]\), each training set has 30 points with noise standard deviation 0.3, and the learner fits a polynomial of degree \(d\) by least squares.

code — bias and variance of polynomial fits, from 4000 training sets
from numpy.polynomial import legendre

rng = np.random.default_rng(0)
f = lambda x: np.sin(2 * np.pi * x)                 # the truth
sigma, n = 0.3, 30
xg = np.linspace(0.05, 0.95, 91)                    # where we measure bias and variance
for deg in [1, 3, 5, 7, 9, 11]:
    fits = []
    for rep in range(4000):                         # 4000 independent training sets
        x = rng.uniform(0, 1, n)
        y = f(x) + rng.normal(0, sigma, n)
        fits.append(legendre.legval(2 * xg - 1, legendre.legfit(2 * x - 1, y, deg)))
    fits = np.array(fits)
    bias2 = np.mean((fits.mean(axis=0) - f(xg)) ** 2)
    var = np.mean(fits.var(axis=0))
    print(f'degree {deg:2d}: bias^2 {bias2:.4f}   variance {var:.4f}   expected test MSE {sigma**2 + bias2 + var:.4f}')
degree  1: bias^2 0.1528   variance 0.0203   expected test MSE 0.2631
degree  3: bias^2 0.0030   variance 0.0129   expected test MSE 0.1059
degree  5: bias^2 0.0000   variance 0.0248   expected test MSE 0.1148
degree  7: bias^2 0.0000   variance 0.2300   expected test MSE 0.3201
degree  9: bias^2 0.0108   variance 12.9336   expected test MSE 13.0344
degree 11: bias^2 0.0148   variance 90.7140   expected test MSE 90.8188

The trade-off, live

Left: the truth (amber) and fits from 25 training sets (sky), with their average (moss). Right: bias², variance and expected test MSE for every degree (log scale), from 200 training sets. Change the degree and the training-set size.

Degree 1 cannot bend (bias² 0.153); by degree 3 bias is nearly gone and variance is still small, so degree 3 has the lowest expected test error. Beyond that, bias stays near zero while variance explodes: at degree 11 it is 91, from fits that swing wildly near the ends of the interval. Increase \(n\) in the widget and watch the variance curve drop, letting higher degrees become affordable: more data buys more complexity.

For ridge regression the two terms can be written down exactly, using the singular value decomposition of Lecture 2.

theorem 5.8 — bias and variance of ridge regression

Let the design \(X\) (\(n\times p\)) be fixed, with SVD

$$X=\sum_i\sigma_iu_iv_i^\top,$$

and \(y=X\beta+\varepsilon\) with \(\mathrm{Cov}(\varepsilon)=\sigma^2I\). The ridge fit \(\hat y_\lambda=X\hat\beta_\lambda\) has, averaged over the \(n\) training inputs,

$$\text{bias}^2(\lambda)=\frac1n\sum_i\Big(\frac{\lambda}{\sigma_i^2+\lambda}\Big)^2\big(u_i^\top X\beta\big)^2,\qquad\text{variance}(\lambda)=\frac{\sigma^2}{n}\sum_i\Big(\frac{\sigma_i^2}{\sigma_i^2+\lambda}\Big)^2.$$

Bias² increases and variance decreases as \(\lambda\) grows. At \(\lambda=0\) the variance is \(\sigma^2p/n\).

From Proposition 3.5,

$$\hat y_\lambda=\sum_is_i\,u_iu_i^\top y$$

with shrinkage factors \(s_i=\sigma_i^2/(\sigma_i^2+\lambda)\). Its mean is \(\sum_is_iu_iu_i^\top X\beta\); since \(X\beta\) lies in the span of the \(u_i\), \(X\beta=\sum_iu_iu_i^\top X\beta\), so the mean error is

$$-\sum_i(1-s_i)u_iu_i^\top X\beta,$$

with squared length \(\sum_i(1-s_i)^2(u_i^\top X\beta)^2\), and \(1-s_i=\lambda/(\sigma_i^2+\lambda)\).

The fluctuation \(\sum_is_iu_iu_i^\top\varepsilon\) has covariance

$$\sigma^2\sum_is_i^2u_iu_i^\top,$$

whose trace is \(\sigma^2\sum_is_i^2\). Divide both by \(n\). Each \(1-s_i\) increases and each \(s_i\) decreases in \(\lambda\). \(\square\)

code — ridge bias and variance from the formula, checked by simulation
rng = np.random.default_rng(1)
n, p_, sig = 50, 10, 3.0
C = 0.8 * np.ones((p_, p_)) + 0.2 * np.eye(p_)       # strongly correlated features
X = rng.normal(size=(n, p_)) @ np.linalg.cholesky(C).T
beta = rng.normal(0, 1, p_)
U, s, Vt = np.linalg.svd(X, full_matrices=False)

def ridge_bias_var(lam):                            # exact, from the SVD (Theorem 5.8)
    shrink = s ** 2 / (s ** 2 + lam)
    mean_fit = U @ (shrink * (U.T @ (X @ beta)))     # E[X beta_hat]
    return np.mean((mean_fit - X @ beta) ** 2), sig ** 2 * np.sum(shrink ** 2) / n

print('singular values of X:', np.round(s, 2))
for lam in [0, 1, 3, 10, 30, 100, 1000]:
    b2, v = ridge_bias_var(lam)
    print(f'lambda = {lam:5}: bias^2 {b2:.4f}   variance {v:.4f}   sum {b2 + v:.4f}')

lam = 10                                            # Monte Carlo check at one lambda
fits = []
for rep in range(20000):
    yy = X @ beta + rng.normal(0, sig, n)
    fits.append(X @ np.linalg.solve(X.T @ X + lam * np.eye(p_), X.T @ yy))
fits = np.array(fits)
print('simulated at lambda = 10: bias^2', round(np.mean((fits.mean(0) - X @ beta) ** 2), 4),
      '  variance', round(np.mean(fits.var(0)), 4))
singular values of X: [17.28  3.91  3.6   3.05  2.99  2.72  2.38  2.21  2.15  1.99]
lambda =     0: bias^2 0.0000   variance 1.8000   sum 1.8000
lambda =     1: bias^2 0.0256   variance 1.4151   sum 1.4407
lambda =     3: bias^2 0.1562   variance 0.9865   sum 1.1427
lambda =    10: bias^2 0.6763   variance 0.4817   sum 1.1580
lambda =    30: bias^2 1.4478   variance 0.2260   sum 1.6737
lambda =   100: bias^2 2.1635   variance 0.1114   sum 2.2749
lambda =  1000: bias^2 3.5226   variance 0.0096   sum 3.5322
simulated at lambda = 10: bias^2 0.6742   variance 0.4804

With ten strongly correlated features (one large singular value and nine small ones) and noisy data, least squares has variance 1.80. A modest penalty, \(\lambda\) between 3 and 10, trades a little bias for a large drop in variance and cuts the total by more than a third; a large penalty over-shrinks. The simulation at \(\lambda=10\) agrees with the formula to two decimals.

proposition 5.9 — bias and variance of kNN regression (fixed design)

With fixed training inputs \(x_1,\dots,x_n\) and \(y_i=f(x_i)+\varepsilon_i\), the kNN prediction at \(x_0\) has

$$\text{bias}=\frac1k\sum_{i\in N_k(x_0)}f(x_i)-f(x_0),\qquad\text{variance}=\frac{\sigma^2}{k}.$$

With the inputs fixed, the neighbour set \(N_k(x_0)\) is fixed. The prediction

$$\frac1k\sum_{i\in N_k}(f(x_i)+\varepsilon_i)$$

has mean \(\frac1k\sum f(x_i)\) and, the \(\varepsilon_i\) being independent with variance \(\sigma^2\), variance \(\sigma^2/k\). \(\square\)

This is the dartboard of Lecture 1 made exact: variance falls like \(1/k\), while bias grows as the neighbourhood reaches points where \(f\) differs.

spot check 5.7

As the ridge penalty \(\lambda\) increases, bias² and variance ; the directions shrunk most are those with .

Theorem 5.8.
Small singular values are directions the data barely pin down, where least squares is noisiest. Ridge shrinks exactly those, which is why it helps most when features are correlated.
bias and variance for 0–1 loss

The clean additive decomposition is special to squared loss. For classification with 0–1 loss, several competing definitions exist, and none adds up neatly. Worse, variance can help: at a point where the average classifier is on the wrong side of the Bayes boundary, random fluctuations sometimes push it to the right side (Friedman, 1997; James, 2003). This is one reason classifiers can tolerate a lot of variance in their scores, and one reason ensembles that average many unstable classifiers (Lecture 8) work so well.

7 — Approximation, estimation, and choosing complexity

Bias and variance describe one algorithm averaged over training sets. A second decomposition, useful for reading theory papers, splits the excess risk of the predictor we actually get. Let \(R^*\) be the Bayes risk, \(h^*_{\mathcal H}\) the best predictor in the hypothesis class \(\mathcal H\), \(\hat h\) the exact empirical risk minimiser, and \(\tilde h\) what our optimiser actually returns. Then

$$R(\tilde h)-R^*=\underbrace{R(h^*_{\mathcal H})-R^*}_{\text{approximation}}+\underbrace{R(\hat h)-R(h^*_{\mathcal H})}_{\text{estimation}}+\underbrace{R(\tilde h)-R(\hat h)}_{\text{optimisation}}.$$

A richer class lowers the approximation error and raises the estimation error, the analogue of bias and variance; Lecture 6 bounds the estimation error in terms of the class's complexity. The optimisation term is a modern addition (Bottou & Bousquet, 2008): with huge datasets it can be better to optimise a rich model roughly than a poor one exactly.

In practice we choose complexity by cross-validation. A refinement guards against noise in the CV curve: the one-standard-error rule picks the simplest model whose CV error is within one standard error of the minimum.

code — the one-standard-error rule
from sklearn.model_selection import KFold

rng = np.random.default_rng(7)
x = rng.uniform(0, 1, 40); y = f(x) + rng.normal(0, sigma, 40)
rows = []
for deg in range(1, 13):
    errs = []
    for a_, b_ in KFold(10, shuffle=True, random_state=0).split(x):
        c = legendre.legfit(2 * x[a_] - 1, y[a_], deg)
        errs.append(np.mean((legendre.legval(2 * x[b_] - 1, c) - y[b_]) ** 2))
    rows.append((deg, np.mean(errs), np.std(errs) / np.sqrt(len(errs))))   # CV estimate and its standard error
best = min(rows, key=lambda r: r[1])
one_se = min(r[0] for r in rows if r[1] <= best[1] + best[2])           # simplest model within one SE of the best
for deg, m, se in rows[:9]:
    print(f'degree {deg:2d}: CV MSE {m:.4f} (SE {se:.4f})')
print('lowest CV error at degree', best[0], '; one-standard-error rule picks degree', one_se)
degree  1: CV MSE 0.4119 (SE 0.0662)
degree  2: CV MSE 0.4221 (SE 0.0679)
degree  3: CV MSE 0.0669 (SE 0.0136)
degree  4: CV MSE 0.0660 (SE 0.0134)
degree  5: CV MSE 0.0620 (SE 0.0121)
degree  6: CV MSE 0.0686 (SE 0.0124)
degree  7: CV MSE 0.0739 (SE 0.0127)
degree  8: CV MSE 0.0739 (SE 0.0107)
degree  9: CV MSE 0.0747 (SE 0.0118)
lowest CV error at degree 5 ; one-standard-error rule picks degree 3

Degrees 3, 4 and 5 are statistically indistinguishable (differences of 0.005 against standard errors of 0.012); the rule prefers the simplest, degree 3, which matches the truth-based optimum of the simulation above.

spot check 5.8

Why choose the simplest model within one standard error of the best CV score, rather than the best score itself?

How large are the differences between degrees 3, 4 and 5 compared with their standard errors?
The rule is a guard against chasing noise, popularised by Breiman et al. (1984) for tree pruning and by Hastie, Tibshirani and Friedman for the lasso.

The U-curve is not the end of the story. Very flexible models such as large neural networks often have more parameters than training points, interpolate the training data exactly, and still generalise well. As complexity grows past the interpolation point, test error can fall again: double descent. Lecture 6 shows it happening and explains part of why.

causal — a loss for something you never observe

A treatment effect for one person, \(Y_i(1)-Y_i(0)\), is never observed, so there is no label to compute a loss against. Nie and Wager's (2021) R-learner manufactures one from the Frisch–Waugh–Lovell idea of Lecture 3. With \(\hat m(x)\) predicting the outcome and \(\hat e(x)\) predicting treatment (the propensity score of Lecture 4), estimate the effect function \(\tau(x)\) by minimising

$$\frac1n\sum_i\Big[\big(Y_i-\hat m(X_i)\big)-\big(T_i-\hat e(X_i)\big)\,\tau(X_i)\Big]^2+\text{penalty}(\tau).$$

This "R-loss" is minimised in expectation by the true effect function under unconfoundedness, so any method that minimises a loss (lasso, boosting, neural networks) can be turned into a heterogeneous-effect estimator. Designing the right loss is often the whole problem.

quantum — the loss decides whether a quantum circuit can learn at all

Variational quantum algorithms train a parameterised circuit by minimising a cost function estimated from measurements. Cerezo et al. (2021) showed that the choice of cost matters dramatically. A global cost, such as one minus the overlap between the output state and a target state, has gradients that vanish exponentially in the number of qubits even for shallow circuits: a "barren plateau" where the landscape is flat everywhere the optimiser can see. A local cost, averaging terms that each involve one or a few qubits, has gradients that shrink only polynomially for shallow circuits, and is trainable. Both costs have the same minimiser. The lesson matches this lecture's: two losses with the same target can behave completely differently during training.

8 — Losses you will meet later

losswhat it is forwhere
pairwise ranking (logistic or hinge on score differences)ordering search results and recommendationsLecture 8 (LambdaMART)
contrastive / InfoNCEpull matching pairs together and push others apart, to learn embeddings without labelsLectures 12, 14, 19
negative ELBOfit latent-variable models by maximising a lower bound on the likelihoodLectures 16, 17
focal lossdown-weight easy examples in very imbalanced classificationLecture 19
Bradley–Terry preference loss \(-\log\sigma(r(a)-r(b))\)learn a reward from human comparisons "a is better than b"Lecture 22
big picture — choosing the loss is choosing the product

Retail and logistics forecasters train neural networks on the pinball loss at several quantiles at once, because stocking decisions depend on the 90th or 95th percentile of demand, not its mean; Amazon's MQ-RNN (Wen et al., 2017) is a published example. Object detectors use the focal loss (Lin et al., 2017) because nearly every candidate box in an image is background. Every large language model is pre-trained on next-token cross-entropy, a proper scoring rule, which is part of why their raw probabilities are reasonably calibrated before fine-tuning. Chat models are then tuned with a Bradley–Terry loss on human preference comparisons. And weather centres verify their probability forecasts with proper scores, a practice that began with Glenn Brier's 1950 paper.

9 — Summary, exercises, projects, reading

summary

Next: Lecture 6 asks why a model that does well on its training data should do well on new data at all, and answers with PAC learning, VC dimension and Rademacher complexity.

exercises 5
  1. For the data \(\{1,2,3,10\}\), find every constant minimising the squared, absolute and pinball (\(\tau=0.75\)) losses.

    Squared: the mean, 4. Absolute: any \(c\in[2,3]\) (both middle values are medians). Pinball at 0.75: \(c\) with \(P(Y<c)\le0.75\le P(Y\le c)\); \(P(Y\le c)\ge0.75\) needs \(c\ge3\), and \(P(Y<c)\le0.75\) needs \(c\le10\), so any \(c\in[3,10]\). Small samples often have intervals of minimisers.

  2. Poisson regression sets \(\mu_i=\exp(w^\top x_i)\) and minimises \(\sum_i(\mu_i-y_i\log\mu_i)\). Show that its gradient is \(\sum_i(\mu_i-y_i)x_i\), the same "prediction minus label" form as least squares and logistic regression.

    With \(s_i=w^\top x_i\), each term is \(e^{s_i}-y_is_i\), whose derivative in \(s_i\) is \(e^{s_i}-y_i=\mu_i-y_i\); multiply by \(\partial s_i/\partial w=x_i\). This happens for every generalised linear model with its "canonical" link, a property of exponential families.

  3. A missed fraud costs a bank $500 and investigating a legitimate transaction costs $10. Above what fraud probability should a transaction be investigated?

    \(c_{\text{FP}}/(c_{\text{FP}}+c_{\text{FN}})=10/510\approx0.0196\). Investigate anything with at least a 2% chance of fraud. Thresholds this low are common, which is one reason fraud systems produce so many alerts.

  4. Show that the conditional hinge risk $$C_\eta(s)=\eta\max(0,1-s)+(1-\eta)\max(0,1+s)$$ is minimised at \(s=1\) when \(\eta>\tfrac12\) and at \(s=-1\) when \(\eta<\tfrac12\). Why does this mean an SVM score is not a probability?

    \(C_\eta\) is piecewise linear with kinks at \(\pm1\). On \([-1,1]\) it equals \(\eta(1-s)+(1-\eta)(1+s)=1+(1-2\eta)s\), decreasing when \(\eta>\tfrac12\); outside \([-1,1]\) it increases. So the minimum is at \(s=1\) (or \(-1\)), the same for \(\eta=0.51\) and \(\eta=0.99\): the minimiser carries the sign of \(2\eta-1\) and nothing else. To get probabilities from an SVM one fits a separate calibration map (Platt scaling).

  5. Show that \(\mathrm{KL}\big(\mathrm{Bern}(0.6)\,\|\,\mathrm{Bern}(0.5)\big)\approx0.0201\) nats, and that the expected excess log score from reporting \(q\) when the truth is \(p\) equals \(\mathrm{KL}(\mathrm{Bern}(p)\|\mathrm{Bern}(q))\).

    \(0.6\log1.2+0.4\log0.8=0.1094-0.0893=0.0201\). The expected log score is \(H(p)+\mathrm{KL}(p\|q)\) (Theorem 5.6), and honest reporting scores \(H(p)\), so the excess is exactly the KL divergence.

  6. Show that the absolute score \(|q-y|\) is not proper: for \(p>\tfrac12\) its expected value is minimised by reporting \(q=1\).

    \(\mathbb E|q-Y|=p(1-q)+(1-p)q=p+q(1-2p)\), linear in \(q\) with slope \(1-2p<0\) when \(p>\tfrac12\), so it is minimised at \(q=1\). A forecaster judged this way should exaggerate every forecast to 0 or 1.

  7. Show that a forecaster who always reports the base rate \(\bar y\) has Brier score \(\bar y(1-\bar y)\). Check against the NBA output.

    \(\frac1n\sum_i(\bar y-y_i)^2\) is the variance of the 0/1 outcomes, \(\bar y-\bar y^2=\bar y(1-\bar y)\). With \(\bar y=0.622\): \(0.622\times0.378\approx0.2351\), matching the printed 0.2350 (the difference is rounding of \(\bar y\)). In Murphy's decomposition, Brier = reliability − resolution + uncertainty, this is the uncertainty term; a forecaster beats it by having resolution.

  8. In one dimension with an orthonormal design, ridge returns \(z/(1+\lambda)\) where \(z\sim\mathcal N(\beta,\sigma^2)\). Find the \(\lambda\) minimising mean squared error, and interpret it as a prior variance.

    MSE \(=\big(\tfrac\lambda{1+\lambda}\big)^2\beta^2+\tfrac{\sigma^2}{(1+\lambda)^2}\). Differentiating, the minimum is at \(\lambda=\sigma^2/\beta^2\). In Bayesian terms (Theorem 3.7) \(\lambda=\sigma^2/\tau^2\), so the best penalty corresponds to a prior variance \(\tau^2=\beta^2\): a prior whose scale matches the true effect size.

  9. Using Proposition 5.9, at what \(k\) does kNN regression on evenly spaced points \(x_i=i/n\) with \(f(x)=x^2\) balance bias² and variance at \(x_0=0.5\)? (Take the neighbours symmetric about \(x_0\), \(n=100\), \(\sigma=0.3\).)

    The neighbours are \(x_0\pm j/n\) for \(j\) up to about \(k/2\). Averaging \(f(x_0+t)=x_0^2+2x_0t+t^2\) over symmetric \(t\) leaves bias \(\approx\overline{t^2}\approx\frac{(k/2n)^2}{3}=\frac{k^2}{12n^2}\). Bias² \(=k^4/(144n^4)\) and variance \(=\sigma^2/k\). Minimising the sum: \(4k^3/(144n^4)=\sigma^2/k^2\), so \(k^5=36\sigma^2n^4\), giving \(k=(36\cdot0.09\cdot10^8)^{1/5}\approx50\): half the data. With a gently curved function and noisy data, very wide neighbourhoods pay off; with sharper curvature \(k\) would be much smaller.

  10. In the bias–variance widget, set the degree to 9 and raise \(n\) from 30 to 120. By roughly what factor does the variance fall? Why is it more than the factor of 4 that \(\sigma^2/n\) scaling would suggest?

    It falls by far more than 4 (by one to two orders of magnitude). Variance of a high-degree polynomial fit is dominated by a few training sets in which the points near the ends of the interval happen to be sparse, giving wild extrapolation; with more points such gaps become rare. The \(\sigma^2p/n\) rule holds for a fixed, well-spread design, not for random designs near the interpolation threshold, a first glimpse of why Lecture 6's double descent happens.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Honest intervals for bike demand

question
Do quantile-regression prediction intervals for bike-share demand keep their promised coverage by hour, season and station?
data
Citi Bike trip data for New York (monthly files from the operator), aggregated to station–hour counts, with weather from NOAA.
method
Fit 10%–90% bands by linear quantile regression and by quantile gradient boosting; measure coverage and interval width by subgroup; compare with conformal prediction intervals.
outcome
A map of where intervals fail (rush hour? rainy days? outer boroughs?), useful to operators planning rebalancing, and a clean comparison of interval methods.

2. Who forecasts best?

question
How well calibrated and how sharp are public probability forecasts, and does the answer depend on the scoring rule?
data
FiveThirtyEight's archived sports forecasts (CC BY 4.0), National Weather Service probability-of-precipitation forecasts with verifying observations, or public forecasting-tournament data.
method
Brier and log scores, reliability diagrams, Murphy's decomposition into reliability, resolution and uncertainty; bootstrap confidence intervals; compare forecasters on the same events.
outcome
A scored league table of forecasters with honest uncertainty, and a clear demonstration of how improper scores would have changed the ranking.

3. Robust losses for messy civic data

question
How much do a few extreme records distort least-squares models of New York City service times, and do Huber or quantile losses fix it?
data
NYC 311 service requests (time to close by agency and complaint type) or NYC taxi trip durations from the Taxi and Limousine Commission.
method
Fit squared, absolute, Huber and quantile models; measure coefficient stability when the top 0.1% of durations are removed or corrupted; evaluate on held-out data with each loss.
outcome
Practical guidance on loss choice for heavy-tailed administrative data, a common situation in public-sector analytics.

Reading and sources

Data. NYC flights: H. Wickham, nycflights13: Flights that departed NYC in 2013, R package (CC0), from the US Bureau of Transportation Statistics; via V. Arel-Bundock, Rdatasets. Bike sharing: H. Fanaee-T, J. Gama, "Event labeling combining ensemble detectors and background knowledge", Progress in Artificial Intelligence 2, 113–127 (2014), as distributed in the ISLP package (James et al., 2023). NBA forecasts: N. Silver, R. Fischer-Baum, "How we calculate NBA Elo ratings", FiveThirtyEight (2015); data from github.com/fivethirtyeight/data (CC BY 4.0). Breast-cancer scores: Lecture 4.

every number in the text and widgets is computed in verify_L05.py; code-box outputs are pasted from actual runs