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)
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.
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?
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.
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).
A false negative costs 4 times as much as a false positive. Above what predicted probability should you predict positive?
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).
With residual \(u=y-\hat y\):
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.
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.
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.
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.
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.
Training with absolute loss estimates the conditional ; training with the pinball loss at \(\tau=0.9\) estimates the conditional .
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.
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.
Up to terms that do not depend on the prediction \(\mu\):
| model for \(Y\) | negative log-likelihood | name |
|---|---|---|
| \(\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.
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).$$\(\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.
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.
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.
Why can a least-squares model predict negative bike counts, while Poisson regression cannot?
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.
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.
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.
Which of these losses is not classification-calibrated?
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\).
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).$$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.
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.
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
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).
A forecaster always says 50%. What is their Brier score, whatever happens?
You believe an event has probability 0.6. Under the Brier score, what happens to your expected score if you report 0.7 instead?
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.
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.
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
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.
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\)
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.
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.
As the ridge penalty \(\lambda\) increases, bias² and variance ; the directions shrunk most are those with .
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.
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.
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.
Why choose the simplest model within one standard error of the best CV score, rather than the best score itself?
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.
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.
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.
| loss | what it is for | where |
|---|---|---|
| pairwise ranking (logistic or hinge on score differences) | ordering search results and recommendations | Lecture 8 (LambdaMART) |
| contrastive / InfoNCE | pull matching pairs together and push others apart, to learn embeddings without labels | Lectures 12, 14, 19 |
| negative ELBO | fit latent-variable models by maximising a lower bound on the likelihood | Lectures 16, 17 |
| focal loss | down-weight easy examples in very imbalanced classification | Lecture 19 |
| Bradley–Terry preference loss \(-\log\sigma(r(a)-r(b))\) | learn a reward from human comparisons "a is better than b" | Lecture 22 |
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.
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.
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.
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.
\(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.
\(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).
\(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.
\(\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.
\(\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.
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.
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.
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.
Each project uses this lecture's methods and public data, and has a clear result.
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