Part I · Foundations of supervised learning | features and labels, loss and risk, empirical risk minimisation, k-nearest neighbours, overfitting, cross-validation, a first look at bias and variance, the Bayes-optimal predictor | reading: James et al., ISLP, ch. 2 and 5.1; Cover & Hart (1967)
Machine learning is the craft of turning examples into rules. We are shown penguins whose species we know, and we want a rule that names the species of penguins we have not seen. We are shown past crash-test readings, and we want a curve that predicts the next one. This lecture sets up the language the whole course uses: what a prediction problem is, how we score a rule, how we pick one from data, why the rule that fits the data best is often not the best rule, and what the best possible rule looks like. Along the way we meet our first learning algorithm, k-nearest neighbours, which is simple enough to write in ten lines and good enough to still be in use.
By the end of this lecture you should be able to state a supervised learning problem in terms of features, labels, a loss and a risk; explain empirical risk minimisation and why it is a proxy for what we want; implement and tune k-nearest neighbours; use a train/validation/test split and K-fold cross-validation correctly, and say what cross-validation estimates; describe bias and variance and how a complexity knob trades one for the other; derive the Bayes-optimal classifier and state the Cover–Hart theorem; and explain why a good predictor need not tell us what causes what.
Between 2007 and 2009, Dr Kristen Gorman and the Palmer Station Long Term Ecological Research program measured adult penguins nesting on three islands near Palmer Station, Antarctica. Three species breed there: Adélie, Chinstrap and Gentoo. Each penguin became one row of a table: its species, its island, the length and depth of its bill, the length of its flipper, its body mass and its sex.
344 penguins (342 with bill measurements): 152 Adélie, 124 Gentoo, 68 Chinstrap. Columns: species, island, bill length (mm), bill depth (mm), flipper length (mm), body mass (g), sex, year. Collected by K. B. Gorman with the Palmer Station LTER (Gorman, Williams & Fraser, 2014); packaged by Horst, Hill & Gorman (2020) and released under the CC0 licence. In Python: pip install palmerpenguins.
from palmerpenguins import load_penguins penguins = load_penguins() print(penguins.shape) print(penguins[['species', 'island', 'bill_length_mm', 'bill_depth_mm', 'body_mass_g']].head(4)) print(penguins['species'].value_counts())
(344, 8) species island bill_length_mm bill_depth_mm body_mass_g 0 Adelie Torgersen 39.1 18.7 3750.0 1 Adelie Torgersen 39.5 17.4 3800.0 2 Adelie Torgersen 40.3 18.0 3250.0 3 Adelie Torgersen NaN NaN NaN species Adelie 152 Gentoo 124 Chinstrap 68 Name: count, dtype: int64
Suppose a field assistant measures a new penguin's bill but does not know the species. Can we predict the species from the bill? That is a prediction problem. The quantities we measure are the features (also called inputs, covariates or predictors), and the quantity we want to predict is the label (or output, target, response).
A feature space \(\mathcal X\) (here \(\mathbb R^d\), one coordinate per measurement) and a label space \(\mathcal Y\).
There is an unknown probability distribution \(P\) on \(\mathcal X\times\mathcal Y\), the population.
We observe a training set
$$S=\big((x_1,y_1),\dots,(x_n,y_n)\big),\qquad (x_i,y_i)\ \text{drawn independently from } P.$$The goal is a predictor (or hypothesis) \(h:\mathcal X\to\mathcal Y\) whose prediction \(h(X)\) is close to \(Y\) for a new pair \((X,Y)\sim P\).
When \(\mathcal Y=\mathbb R\) the problem is regression; when \(\mathcal Y\) is a finite set of classes it is classification.
Two words in this definition carry most of the weight. Unknown: if we knew \(P\) there would be nothing to learn (Section 6 shows what we would do). Independently: the new penguin is assumed to come from the same population as the old ones, and no penguin's measurements tell us about another's. Much of what goes wrong in practice comes from violating this assumption, for example training on penguins from one island and predicting on another.
Which of these is a regression problem?
For decades the first dataset in every machine learning course was Fisher's iris data: 150 flowers, four measurements, three species, published by R. A. Fisher in 1936 (the measurements were Edgar Anderson's). Fisher's paper appeared in the Annals of Eugenics, and in 2020 Allison Horst, Alison Hill and Kristen Gorman released the penguin data as a modern alternative with the same shape: a handful of body measurements and three species. The phrase "machine learning" itself was popularised by Arthur Samuel, whose 1959 paper described a checkers program at IBM that improved by playing against itself, three years after the 1956 Dartmouth workshop gave "artificial intelligence" its name.
To choose between predictors we need to score them. A score for a single prediction is a loss; the score for a predictor is its average loss over the population.
A loss function \(\ell(\hat y,y)\ge0\) is the cost of predicting \(\hat y\) when the truth is \(y\). The two we use in this lecture:
$$\text{squared loss } \ell(\hat y,y)=(\hat y-y)^2\ \ (\text{regression}),\qquad \text{0–1 loss } \ell(\hat y,y)=\mathbf 1[\hat y\ne y]\ \ (\text{classification}).$$Here \(\mathbf 1[A]\) is 1 if \(A\) is true and 0 otherwise. Lecture 5 is devoted to other losses and what each one is good for.
The risk (or test error, generalisation error) of a predictor \(h\) is its expected loss on a new example,
$$R(h)=\mathbb E_{(X,Y)\sim P}\big[\ell(h(X),Y)\big].$$The empirical risk (training error) is its average loss on the training set,
$$\hat R_S(h)=\frac1n\sum_{i=1}^n\ell\big(h(x_i),y_i\big).$$For 0–1 loss, \(R(h)=P\big(h(X)\ne Y\big)\) is the probability of a mistake and \(\hat R_S(h)\) is the fraction of training examples misclassified.
The risk is what we care about and cannot compute, because \(P\) is unknown. The empirical risk is what we can compute. For a fixed predictor \(h\), chosen before seeing the data, \(\hat R_S(h)\) is an average of \(n\) independent copies of \(\ell(h(X),Y)\), so by the law of large numbers it converges to \(R(h)\), and the central limit theorem tells us its error is of order \(1/\sqrt n\). This suggests the most natural strategy in machine learning.
Fix a set of candidate predictors \(\mathcal H\), the hypothesis class. ERM returns a predictor with the smallest training error:
$$\hat h\in\operatorname*{arg\,min}_{h\in\mathcal H}\ \hat R_S(h).$$Here is the catch that occupies much of this course. The predictor \(\hat h\) is chosen because it did well on \(S\), so its training error is no longer an honest estimate of its risk. The law of large numbers applies to a fixed \(h\), not to the winner of a contest judged on the same data. How far apart \(\hat R_S(\hat h)\) and \(R(\hat h)\) can be depends on how rich \(\mathcal H\) is; Lecture 6 makes this precise.
Take the simplest hypothesis class: constant predictors \(h(x)=c\), ignoring the features. With squared loss, which \(c\) does ERM choose for predicting penguin body mass?
\(\hat R_S(c)=\frac1n\sum_i(y_i-c)^2\) is a parabola in \(c\). Its derivative is \(-\frac2n\sum_i(y_i-c)\), which is zero at \(c=\bar y=\frac1n\sum_iy_i\). So ERM predicts the sample mean: 4201.75 g for the 342 weighed penguins. With absolute loss \(|y-c|\) the answer is the sample median, 4050 g (Exercise 2). The loss decides which summary of the data the prediction becomes.
Among constant predictors, ERM with squared loss returns the of the training labels, and with 0–1 loss on a classification problem it returns the .
A slightly richer class: threshold classifiers on one feature. Adélie and Chinstrap penguins overlap in body size, but Chinstraps tend to have longer bills. Consider \(\mathcal H=\{h_\theta:\theta\in\mathbb R\}\) where \(h_\theta(x)\) says "Chinstrap" if the bill length \(x\) exceeds \(\theta\) mm and "Adélie" otherwise. Each \(\theta\) is a hypothesis, and ERM picks the \(\theta\) with the fewest training mistakes. The widget lets you be the learning algorithm.
ERM lands on \(\theta=44.65\) mm, with 5 training mistakes out of 153 (empirical risk 0.033). On the 66 test penguins it makes 4 mistakes (0.061). Look at \(\theta=42\): its training error is three times larger (0.105), yet on these particular 66 test penguins it makes only one mistake. That is not a reason to prefer 42. A test set of 66 penguins is small, so a difference of three mistakes is mostly luck, and a threshold chosen by looking at the test set would no longer have an honest test error. The test set is for reporting, not choosing; Section 4 makes this a rule.
A student picks the threshold with the smallest test error, \(\theta=42\), and reports its test error of 0.015 as an estimate of how well it will do on future penguins. What is wrong?
Here is perhaps the most natural idea of all: to classify a new penguin, find the penguins in the training set that look most like it and go with the majority. "Look most like it" means "closest in feature space".
Fix \(k\ge1\) and a distance on \(\mathcal X\), usually the Euclidean distance
$$\|x-x'\|=\sqrt{\sum_j(x_j-x'_j)^2}.$$For a query point \(x\), let \(N_k(x)\) be the indices of the \(k\) training points closest to \(x\).
The kNN classifier predicts the most common label among \(\{y_i:i\in N_k(x)\}\) (ties broken by a fixed rule).
The kNN regressor predicts their average,
$$\hat h(x)=\frac1k\sum_{i\in N_k(x)}y_i.$$kNN has no training step beyond storing the data; all the work happens at prediction time. It is not ERM over a fixed class in the sense of Definition 1.4, but it has the same structure: a family of predictors indexed by \(k\), from which we must choose. One practical point matters a great deal. Distances add up differences in every feature, so a feature measured in large units dominates. Body mass varies by hundreds of grams while bill depth varies by a few millimetres, so in raw units "nearest" would mean "nearest in mass". The standard fix is to standardise each feature: subtract its mean and divide by its standard deviation, both computed on the training set.
At \(k=1\) the regions are jagged, with small islands around individual penguins, and every training penguin is classified correctly: its nearest neighbour is itself. As \(k\) grows the boundaries smooth out. At \(k=51\) Chinstraps, the smallest group, start to lose ground to their neighbours. Here is the classifier from scratch.
import numpy as np from sklearn.model_selection import train_test_split df = penguins.dropna(subset=['bill_length_mm', 'bill_depth_mm']) X = df[['bill_length_mm', 'bill_depth_mm']].to_numpy() y = df['species'].to_numpy() X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, stratify=y, random_state=1) mu, sd = X_tr.mean(axis=0), X_tr.std(axis=0) # standardise with TRAINING statistics only Z_tr, Z_te = (X_tr - mu) / sd, (X_te - mu) / sd def knn_predict(Z_train, y_train, Z_query, k): d2 = ((Z_query[:, None, :] - Z_train[None, :, :]) ** 2).sum(axis=-1) # squared distances nearest = np.argsort(d2, axis=1)[:, :k] # indices of k nearest preds = [] for votes in y_train[nearest]: labels, counts = np.unique(votes, return_counts=True) preds.append(labels[counts.argmax()]) # majority vote return np.array(preds) print(len(y_tr), 'training penguins,', len(y_te), 'test penguins') for k in [1, 5, 25]: train_err = np.mean(knn_predict(Z_tr, y_tr, Z_tr, k) != y_tr) test_err = np.mean(knn_predict(Z_tr, y_tr, Z_te, k) != y_te) print(f'k = {k:2d}: training error {train_err:.3f}, test error {test_err:.3f}')
239 training penguins, 103 test penguins k = 1: training error 0.000, test error 0.039 k = 5: training error 0.025, test error 0.039 k = 25: training error 0.033, test error 0.058
Two things to notice. The training error at \(k=1\) is exactly zero, and it would be zero on any data with distinct feature vectors, so it tells us nothing about how good 1-NN is. And the test errors are small for every \(k\): bill length and depth together separate these species well. To see why standardising matters, add flipper length and body mass and run kNN with and without it.
cols = ['bill_length_mm', 'bill_depth_mm', 'flipper_length_mm', 'body_mass_g'] df4 = penguins.dropna(subset=cols) X4_tr, X4_te, y4_tr, y4_te = train_test_split(df4[cols], df4['species'], test_size=0.3, stratify=df4['species'], random_state=1) raw = KNeighborsClassifier(n_neighbors=5).fit(X4_tr, y4_tr) scaled = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5)).fit(X4_tr, y4_tr) print('test error, raw units :', round(1 - raw.score(X4_te, y4_te), 3)) print('test error, standardised :', round(1 - scaled.score(X4_te, y4_te), 3)) print('feature spreads (sd):', X4_tr.std().round(1).to_dict())
test error, raw units : 0.233
test error, standardised : 0.039
feature spreads (sd): {'bill_length_mm': 5.4, 'bill_depth_mm': 2.0, 'flipper_length_mm': 13.6, 'body_mass_g': 790.3}
Why is kNN in raw units six times worse here, even though it has more information than the two-feature version?
With distinct training points, the training error of 1-NN is , and as \(k\) increases to \(n\) every prediction becomes .
The nearest-neighbour rule was introduced by Evelyn Fix and Joseph Hodges in a 1951 technical report for the US Air Force School of Aviation Medicine, as a way to classify without assuming the data were normal. It was not formally published until International Statistical Review reprinted it in 1989. In 1967 Thomas Cover and Peter Hart proved that, with enough data, the 1-NN rule has at most twice the error of the best possible classifier (Theorem 1.4 below). It was one of the first theorems about how well a learning algorithm can do.
Nearest-neighbour search is now infrastructure. Modern systems turn text, images and audio into vectors (embeddings, Lectures 12 and 16), and a "vector database" stores billions of them and answers "which stored vectors are closest to this one?" in milliseconds. Exact search is too slow at that scale, so these systems use approximate methods such as graph-based HNSW indexes or the FAISS library. This is how semantic search, "more like this" recommendations, duplicate detection and the retrieval step of chatbot question answering work. The algorithm is still kNN; the engineering is in finding neighbours fast.
To see the central difficulty clearly, switch to regression. The motorcycle data record the acceleration of a crash-test dummy's head (in units of \(g\)) at 133 times during a simulated motorcycle crash. The curve is flat, plunges, rebounds and settles: hard to fit with a simple formula.
133 measurements of head acceleration (g) against time after impact (ms), from experiments testing crash helmets, made famous by Silverman (1985) and distributed with the R package MASS (Venables & Ripley, 2002). We use the copy in the Rdatasets collection. We take a deliberately small training set of 40 readings, chosen at random, and keep the other 93 for testing.
Fit polynomials of increasing degree by least squares. Higher degree means a richer hypothesis class, and since each class contains the previous one, the training error can only go down.
The training error falls steadily, from 45.2 g at degree 1 to 19.4 g at degree 12. The test error falls too at first, reaching its smallest value, 34.3 g, at degree 6, and then rises sharply: at degree 7 it is 134.5 g. Slide to degree 7 or 11 and look at the curve. It passes close to the training points but swings wildly between them and beyond them, especially near the ends where training points are sparse. This is overfitting: the predictor has adapted to the particular noise in the training sample rather than to the pattern in the population. Degree 1 shows the opposite failure, underfitting: the class is too poor to follow the curve, and both errors are high.
As a model becomes more flexible, training error keeps falling, while test error first falls and then rises. The training error alone cannot locate the bottom of the U. This picture is the starting point for most of what follows. Lecture 5 explains it with bias and variance; Lecture 6 bounds the gap between the two curves and also shows the surprise of modern deep learning: with enough parameters the test curve can come back down ("double descent").
If the training error cannot choose the degree, what can? Data the model has not been fitted to. The standard protocol gives data three separate roles:
The test set must play no part in any choice, including choices made by looking at plots. When data are scarce, setting aside a validation set is expensive, and the usual answer is to rotate the validation role.
Split the training set \(S\) at random into \(K\) folds \(S_1,\dots,S_K\) of (nearly) equal size \(m=n/K\).
For each \(j\), fit the learning algorithm \(A\) on the other \(K-1\) folds, giving \(\hat h_{-j}=A(S\setminus S_j)\), and compute its average loss on the held-out fold. The cross-validation estimate is
$$\mathrm{CV}_K=\frac1K\sum_{j=1}^K\ \frac1m\sum_{(x,y)\in S_j}\ell\big(\hat h_{-j}(x),y\big).$$Each example is held out exactly once. \(K=n\) is leave-one-out cross-validation.
To choose a hyperparameter, compute \(\mathrm{CV}_K\) for each value and take the smallest; then refit on all of \(S\).
What exactly does the cross-validation estimate estimate? Not quite the risk of the final model, and the difference explains a real feature of the motorcycle results.
Let \(S\) consist of \(n\) independent draws from \(P\), and let \(A\) be any learning algorithm. For \(K\)-fold cross-validation with folds of size \(m=n/K\),
$$\mathbb E\big[\mathrm{CV}_K\big]=\mathbb E_{S'}\Big[R\big(A(S')\big)\Big],$$where \(S'\) is a training set of \(n-m\) independent draws from \(P\).
In words: cross-validation is an unbiased estimate of the expected risk of the algorithm trained on \(n-m\) examples.
Fix a fold \(j\) and an example \((x,y)\in S_j\). The fitted predictor \(\hat h_{-j}=A(S\setminus S_j)\) depends only on the other folds, which are independent of \((x,y)\). So, conditioning on \(S\setminus S_j\),
$$\mathbb E\big[\ell(\hat h_{-j}(x),y)\ \big|\ S\setminus S_j\big]=\mathbb E_{(X,Y)\sim P}\big[\ell(\hat h_{-j}(X),Y)\big]=R(\hat h_{-j}).$$Taking expectations,
$$\mathbb E[\ell(\hat h_{-j}(x),y)]=\mathbb E[R(A(S\setminus S_j))],$$and \(S\setminus S_j\) is a set of \(n-m\) independent draws from \(P\). Every term in \(\mathrm{CV}_K\) has this same expectation, and \(\mathrm{CV}_K\) is an average of them, so by linearity of expectation
$$\mathbb E[\mathrm{CV}_K]=\mathbb E_{S'}[R(A(S'))]$$with \(|S'|=n-m\). \(\square\)
Note what the theorem does not say. It says nothing about the variance of \(\mathrm{CV}_K\), which can be large: the \(K\) terms share most of their training data, so they are positively correlated, and averaging them reduces variance less than averaging independent terms would.
import pandas as pd from numpy.polynomial import Polynomial from sklearn.model_selection import KFold mc = pd.read_csv('mcycle.csv') # 133 readings: time (ms), head acceleration (g) t, a = mc['times'].to_numpy(), mc['accel'].to_numpy() perm = np.random.default_rng(0).permutation(len(t)) train, test = perm[:40], perm[40:] # a small training set of 40, test set of 93 def rmse(p, idx): return np.sqrt(np.mean((p(t[idx]) - a[idx]) ** 2)) def cv_rmse(deg, idx, folds=5): errs = [] for f_tr, f_va in KFold(folds, shuffle=True, random_state=0).split(idx): p = Polynomial.fit(t[idx[f_tr]], a[idx[f_tr]], deg) errs.append(np.mean((p(t[idx[f_va]]) - a[idx[f_va]]) ** 2)) return np.sqrt(np.mean(errs)) for deg in [1, 3, 5, 6, 8, 10, 12]: p = Polynomial.fit(t[train], a[train], deg) # least squares on a rescaled time axis print(f'degree {deg:2d}: train RMSE {rmse(p, train):6.1f} 5-fold CV RMSE {cv_rmse(deg, train):7.1f} test RMSE {rmse(p, test):7.1f}')
degree 1: train RMSE 45.2 5-fold CV RMSE 47.1 test RMSE 47.1 degree 3: train RMSE 40.3 5-fold CV RMSE 43.8 test RMSE 39.5 degree 5: train RMSE 34.8 5-fold CV RMSE 49.9 test RMSE 36.8 degree 6: train RMSE 34.8 5-fold CV RMSE 107.6 test RMSE 34.3 degree 8: train RMSE 26.3 5-fold CV RMSE 174.0 test RMSE 64.4 degree 10: train RMSE 19.7 5-fold CV RMSE 285.9 test RMSE 72.7 degree 12: train RMSE 19.4 5-fold CV RMSE 845.5 test RMSE 76.4
Cross-validation picks degree 3, while the test set favours degree 6. Theorem 1.1 explains a large part of this. Five-fold cross-validation on 40 readings fits each candidate on only 32 of them, and with 32 points a degree-6 polynomial already swings badly near the edges; CV is honestly reporting how degree 6 performs at that sample size. The final model is refit on all 40 points, where degree 6 behaves better. With small \(n\), cross-validation tends to prefer simpler models than the full data could support. The same experiment for kNN on penguins:
from sklearn.neighbors import KNeighborsClassifier from sklearn.pipeline import make_pipeline from sklearn.preprocessing import StandardScaler from sklearn.model_selection import cross_val_score for k in [1, 3, 5, 9, 15, 25, 51, 101]: model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k)) cv_acc = cross_val_score(model, X_tr, y_tr, cv=10).mean() # 10-fold CV on the training set print(f'k = {k:3d}: 10-fold CV error {1 - cv_acc:.3f}') cv_err = {k: 1 - cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k)), X_tr, y_tr, cv=10).mean() for k in range(1, 52, 2)} k_best = min(cv_err, key=cv_err.get) best = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k_best)).fit(X_tr, y_tr) print(f'CV over odd k = 1..51 chooses k = {k_best}; its test error is {1 - best.score(X_te, y_te):.3f}')
k = 1: 10-fold CV error 0.046 k = 3: 10-fold CV error 0.021 k = 5: 10-fold CV error 0.034 k = 9: 10-fold CV error 0.029 k = 15: 10-fold CV error 0.037 k = 25: 10-fold CV error 0.054 k = 51: 10-fold CV error 0.054 k = 101: 10-fold CV error 0.096 CV over odd k = 1..51 chooses k = 3; its test error is 0.049
Cross-validation chooses \(k=3\), whose test error is 0.049; \(k=5\) had 0.039. The difference is a single test penguin out of 103. Neither number is wrong, and neither choice is wrong. Differences this small are within the noise of the test set itself, which is worth remembering whenever a paper reports that its method beats another by a fraction of a percentage point.
You run 10-fold cross-validation on a training set of 240 examples. On how many examples is each of the 10 models fitted?
Which of these are legitimate? Select all that apply.
Why does the U-curve have its shape? Imagine running the whole experiment again with a fresh training set from the same population, and again, and again. Each time the learning algorithm returns a slightly different predictor. Two things can go wrong with its prediction at a point \(x_0\):
The image is a dartboard. Each training set throws one dart. Bias is how far the centre of the cluster of darts is from the bullseye; variance is how spread out the cluster is.
Suppose \(Y=f(x_0)+\varepsilon\) at a point \(x_0\), with noise \(\mathbb E[\varepsilon]=0\), \(\mathrm{Var}(\varepsilon)=\sigma^2\), independent of the training set \(S\).
Let \(\hat h_S\) be the predictor learned from \(S\). Then, averaging over both \(S\) and the noise,
$$\mathbb E\big[(Y-\hat h_S(x_0))^2\big]=\underbrace{\sigma^2}_{\text{noise}}+\underbrace{\big(\mathbb E_S[\hat h_S(x_0)]-f(x_0)\big)^2}_{\text{bias}^2}+\underbrace{\mathrm{Var}_S\big(\hat h_S(x_0)\big)}_{\text{variance}}.$$Write \(\hat h=\hat h_S(x_0)\) and \(\bar h=\mathbb E_S[\hat h]\). Then
$$Y-\hat h=\varepsilon+(f(x_0)-\bar h)+(\bar h-\hat h).$$Square and take expectations. The three cross terms vanish: \(\varepsilon\) has mean zero and is independent of \(\hat h\); \(f(x_0)-\bar h\) is a constant and \(\mathbb E[\bar h-\hat h]=0\). What remains is
$$\mathbb E[\varepsilon^2]+(f(x_0)-\bar h)^2+\mathbb E[(\hat h-\bar h)^2],$$which is the claimed sum. \(\square\)
Lecture 5 computes the bias and variance exactly for kNN and for ridge regression, and asks what happens for losses other than squared error.
The noise \(\sigma^2\) is a floor no predictor can get under. The other two terms are under our control, and a single knob usually moves them in opposite directions. For kNN regression the knob is \(k\): averaging more neighbours averages away noise (lower variance), but reaches further from \(x_0\) to points where \(f\) is different (higher bias).
At \(k=1\) the darts are centred on the bullseye but scattered widely: no bias, high variance. At \(k=40\), out of 50 points, every prediction is an average over most of the data, so the darts cluster tightly, far from the bullseye, because the average of a sine wave over most of its period is near zero. The best \(k\) balances the two. The same experiment with 5000 training sets per \(k\), at the single point \(x_0=0.25\):
rng = np.random.default_rng(1) f = lambda x: np.sin(2 * np.pi * x) # the true regression function sigma, n, x0 = 0.3, 50, 0.25 # noise sd, training-set size, query point def knn_regress(x_train, y_train, x_query, k): nearest = np.argsort(np.abs(x_train - x_query))[:k] return y_train[nearest].mean() for k in [1, 5, 15, 40]: preds = [] for rep in range(5000): # 5000 independent training sets x = rng.uniform(0, 1, n) y = f(x) + rng.normal(0, sigma, n) preds.append(knn_regress(x, y, x0, k)) preds = np.array(preds) bias2, var = (preds.mean() - f(x0)) ** 2, preds.var() print(f'k = {k:2d}: bias^2 {bias2:.4f} variance {var:.4f} expected test error {sigma**2 + bias2 + var:.4f}')
k = 1: bias^2 0.0000 variance 0.0918 expected test error 0.1818 k = 5: bias^2 0.0006 variance 0.0185 expected test error 0.1091 k = 15: bias^2 0.0251 variance 0.0109 expected test error 0.1260 k = 40: bias^2 0.7404 variance 0.0195 expected test error 0.8499
At \(k=1\) the variance, 0.0918, is almost exactly \(\sigma^2=0.09\): the prediction is a single noisy label. At \(k=5\) the variance has fallen roughly fivefold while the bias is still tiny, and the expected test error is lowest. By \(k=40\) the bias dominates everything.
In kNN, as \(k\) increases the bias usually and the variance usually . In the polynomial experiment, raising the degree plays the role of .
Suppose we knew the population \(P\) exactly. What predictor would we use? The answer gives a benchmark that every learning algorithm aims at, and it explains why even a perfect method makes mistakes.
Write \(\eta_c(x)=P(Y=c\mid X=x)\) for the probability that a penguin with features \(x\) belongs to class \(c\). Penguins with identical measurements can belong to different species, so \(\eta_c(x)\) can be strictly between 0 and 1.
The Bayes classifier predicts the most probable class at each point,
$$h^*(x)=\operatorname*{arg\,max}_{c\in\mathcal Y}\ \eta_c(x),$$and the Bayes risk is its risk,
$$R^*=R(h^*)=\mathbb E\big[1-\max_c\eta_c(X)\big].$$For 0–1 loss, every classifier \(h\) satisfies \(R(h)\ge R(h^*)=R^*\).
Condition on the features. For any classifier \(h\) and any point \(x\),
$$P\big(h(X)\ne Y\mid X=x\big)=1-P\big(Y=h(x)\mid X=x\big)=1-\eta_{h(x)}(x)\ \ge\ 1-\max_c\eta_c(x),$$with equality when \(h(x)\) is a most probable class, that is, for \(h=h^*\).
The inequality holds at every \(x\), so it survives averaging over \(X\):
$$R(h)=\mathbb E\big[1-\eta_{h(X)}(X)\big]\ \ge\ \mathbb E\big[1-\max_c\eta_c(X)\big]=R^*.\qquad\square$$The regression version is the same idea with squared loss: the best predictor is the conditional mean \(f^*(x)=\mathbb E[Y\mid X=x]\), the "best constant" of Example 1.1 applied separately at each \(x\) (Lecture 5 gives the proof). In both cases the optimal rule needs the conditional distribution of \(Y\) given \(X\), which is exactly what we do not know. Learning algorithms can be read as different ways of estimating it: kNN estimates \(\eta_c(x)\) by the fraction of class \(c\) among the \(k\) neighbours.
Class 0 has features \(X\sim N(0,1)\) and class 1 has \(X\sim N(2,1)\), each with probability \(\tfrac12\). Find the Bayes classifier and the Bayes risk.
By Bayes' theorem, \(\eta_1(x)=\dfrac{\tfrac12\varphi(x-2)}{\tfrac12\varphi(x)+\tfrac12\varphi(x-2)}\), where \(\varphi\) is the standard normal density. \(\eta_1(x)>\tfrac12\) exactly when \(\varphi(x-2)>\varphi(x)\), that is, when \(x\) is closer to 2 than to 0: \(x>1\). So \(h^*(x)=\mathbf 1[x>1]\). It errs when a class-0 point exceeds 1 or a class-1 point falls below 1:
$$R^*=\tfrac12P(N(0,1)>1)+\tfrac12P(N(2,1)<1)=\Phi(-1)\approx0.1587.$$Even knowing everything about the population, we misclassify about 16% of points, because the two classes genuinely overlap.
In Example 1.2, move the second class to \(N(4,1)\), keeping equal priors. What is the Bayes risk? (Give a decimal; you can check it with the widget.)
How close can a learning algorithm get to \(R^*\)? For the simplest learner of all there is a beautiful answer.
Consider two classes, and let \(\eta(x)=P(Y=1\mid X=x)\). Under mild regularity conditions (for example, \(\eta\) continuous), as the training set size \(n\to\infty\) the risk of the 1-NN classifier converges to
$$R_{1\text{NN}}=\mathbb E\big[2\eta(X)(1-\eta(X))\big],\qquad\text{and}\qquad R^*\ \le\ R_{1\text{NN}}\ \le\ 2R^*(1-R^*)\ \le\ 2R^*.$$With enough data, one nearest neighbour is at most twice as bad as the best classifier possible, whatever the distribution.
The limit. As \(n\) grows, the nearest training point \(x'\) to a query \(x\) gets arbitrarily close to \(x\), so (by continuity) its label \(Y'\) has probability \(\approx\eta(x)\) of being 1, independently of the query's own label \(Y\). 1-NN errs when \(Y'\ne Y\), which has probability
$$\eta(1-\eta)+(1-\eta)\eta=2\eta(1-\eta).$$Averaging over \(X\) gives the formula. Making "gets arbitrarily close" rigorous is the technical part; see Devroye, Györfi & Lugosi (1996, ch. 5).
The bounds. Let
$$r(x)=\min(\eta(x),1-\eta(x)),$$the Bayes classifier's conditional error, so \(R^*=\mathbb E[r(X)]\) and \(2\eta(1-\eta)=2r(1-r)\). Since \(r\le\tfrac12\), \(2r(1-r)\ge r\), which gives \(R_{1\text{NN}}\ge R^*\).
For the upper bound,
$$\mathbb E[2r(1-r)]=2\mathbb E[r]-2\mathbb E[r^2]\ \le\ 2R^*-2(R^*)^2,$$because \(\mathbb E[r^2]\ge(\mathbb E[r])^2\) (the variance of \(r(X)\) is non-negative). \(\square\)
from scipy.stats import norm from scipy.integrate import quad from sklearn.neighbors import KNeighborsClassifier # class 0 ~ N(0,1), class 1 ~ N(2,1), equal priors eta = lambda x: norm.pdf(x, 2) / (norm.pdf(x, 0) + norm.pdf(x, 2)) # P(Y = 1 | X = x) p_x = lambda x: 0.5 * norm.pdf(x, 0) + 0.5 * norm.pdf(x, 2) # density of X bayes = quad(lambda x: min(eta(x), 1 - eta(x)) * p_x(x), -10, 12, limit=200)[0] nn_limit = quad(lambda x: 2 * eta(x) * (1 - eta(x)) * p_x(x), -10, 12, limit=200)[0] print(f'Bayes error R* = {bayes:.4f} (= Phi(-1) = {norm.cdf(-1):.4f})') print(f'asymptotic 1-NN error = {nn_limit:.4f}') print(f'Cover-Hart upper bound 2R*(1-R*) = {2 * bayes * (1 - bayes):.4f}') rng = np.random.default_rng(2) def sample(m): yy = rng.integers(0, 2, m) return rng.normal(2 * yy, 1).reshape(-1, 1), yy X_test, y_test = sample(200_000) for n_train in [10, 100, 1000, 10_000]: errs = [] for rep in range(20): Xs, ys = sample(n_train) errs.append(1 - KNeighborsClassifier(1).fit(Xs, ys).score(X_test[:20_000], y_test[:20_000])) print(f'n = {n_train:6d}: 1-NN test error {np.mean(errs):.4f}')
Bayes error R* = 0.1587 (= Phi(-1) = 0.1587) asymptotic 1-NN error = 0.2248 Cover-Hart upper bound 2R*(1-R*) = 0.2670 n = 10: 1-NN test error 0.2562 n = 100: 1-NN test error 0.2190 n = 1000: 1-NN test error 0.2253 n = 10000: 1-NN test error 0.2237
For Example 1.2, the asymptotic 1-NN risk is 0.2248, between \(R^*=0.1587\) and the bound \(0.2670\), and the simulated 1-NN risk is already close to its limit by \(n=1000\). The theorem also tells us what 1-NN cannot do: its limit is above \(R^*\) whenever the classes overlap, because a single neighbour's label is a noisy vote. Letting \(k\) grow with \(n\) (with \(k/n\to0\)) fixes this, and the resulting kNN rule's risk converges to \(R^*\) for every distribution, a result due to Stone (1977).
A problem has Bayes risk \(R^*=0.1\). What is the Cover–Hart upper bound on the asymptotic 1-NN risk?
Write \(\pi_c=P(Y=c)\) for the prior probability of class \(c\) and \(p_c(x)\) for the density of the features within class \(c\). Bayes' theorem gives the posterior \(\eta_c(x)=\pi_c\,p_c(x)\big/\sum_{c'}\pi_{c'}\,p_{c'}(x)\), and the Bayes classifier picks the class with the largest posterior. The denominator is the same for every class, so it compares \(\pi_c\,p_c(x)\), exactly the curves in the widget. This suggests two ways to learn a classifier: model \(\pi_c\) and \(p_c\) and apply Bayes' theorem (a generative classifier: naive Bayes, discriminant analysis), or model \(\eta_c(x)\) directly (a discriminative classifier: logistic regression, kNN). Lecture 4 compares the two.
A predictor that works well tells us that the features carry information about the label. It does not tell us that changing a feature would change the label, and it can mislead us badly about how features relate to each other. Penguin bills give a clean example.
df = penguins.dropna(subset=['bill_length_mm', 'bill_depth_mm']) print('all penguins:', round(df['bill_length_mm'].corr(df['bill_depth_mm']), 3)) for sp, g in df.groupby('species'): print(f'{sp:10s}:', round(g['bill_length_mm'].corr(g['bill_depth_mm']), 3))
all penguins: -0.235 Adelie : 0.391 Chinstrap : 0.654 Gentoo : 0.643
The overall correlation is negative; within every species it is positive. Nothing is wrong with either number. Species affects both measurements: Gentoos have long, shallow bills and Adélies short, deep ones. Pooling species mixes these groups, and the between-species pattern swamps the within-species one. This reversal is called Simpson's paradox (Simpson, 1951). Which number answers a question depends on the question: within a species, a penguin with a longer bill tends to have a deeper bill, and that is the relationship biology would care about. For prediction this causes no trouble; kNN uses both features and does well. It causes trouble the moment someone reads a pattern in data as a statement about cause, or about what would happen under an intervention. Telling those apart requires assumptions about how the data were generated, which is the subject of causal inference. This course returns to it in Lectures 3, 8, 13 and 20.
A colleague fits a straight line to all 342 penguins, finds a negative slope, and concludes that "penguins evolve shallower bills as their bills get longer". What is the best response?
Next: Lecture 2 builds the geometry and calculus the rest of the course runs on: vectors, projections, matrices, the SVD and gradient descent.
For \(x=3.2\) the distances to \(1,2,4,5,7\) are \(2.2, 1.2, 0.8, 1.8, 3.8\). The nearest point is 4 (label 1), so 1-NN predicts 1. The three nearest are 4, 2, 5 with labels 1, 0, 0, so 3-NN predicts 0. For \(x=6.2\) the distances are \(5.2, 4.2, 2.2, 1.2, 0.8\): 1-NN uses 7 and predicts 1; 3-NN uses 7, 5, 4 with labels 1, 0, 1 and predicts 1.
The function \(c\mapsto\sum_i|y_i-c|\) is piecewise linear. Away from the data points, raising \(c\) by a small amount \(\delta\) increases \(|y_i-c|\) by \(\delta\) for every \(y_i\) below \(c\) and decreases it by \(\delta\) for every \(y_i\) above \(c\), so the slope is \(\#\{i:y_i\lt c\}-\#\{i:y_i\gt c\}\). The slope is negative while more points lie above \(c\) than below, and positive once more lie below. So the minimum is where at least half the points are \(\le c\) and at least half are \(\ge c\), which is the definition of a median. For an even number of points, every \(c\) between the two middle values is a minimiser.
Leaving out point \(i\), 1-NN predicts the label of the nearest remaining point, so the held-out loss is \(\mathbf 1[\text{label of nearest other point}\ne y_i]\); averaging over \(i\) gives the general statement. For the data: 1's nearest other point is 2 (same label, correct); 2's is 1 (correct); 4's is 5 (label 0, wrong); 5's is 4 (label 1, wrong); 7's is 5 (label 0, wrong). LOOCV error \(=3/5\). Compare the training error of 1-NN, which is 0.
Predict class 1 when \(0.2\,\varphi(x-2)>0.8\,\varphi(x)\). Taking logs, \(-\tfrac12(x-2)^2+\tfrac12x^2>\ln4\), i.e. \(2x-2>\ln4\), so the threshold is \(x^*=1+\tfrac12\ln4\approx1.693\). The rarer class needs stronger evidence. The Bayes risk is \(0.8\,(1-\Phi(1.693))+0.2\,\Phi(1.693-2)\approx0.1121\). The old threshold \(x=1\) has risk \(0.8\,\Phi(-1)+0.2\,\Phi(-1)=\Phi(-1)\approx0.1587\), about 40% worse. Check both with the widget.
\(2r(1-r)-r=r(1-2r)\ge0\) because both factors are non-negative when \(0\le r\le\tfrac12\). For the second, \(\mathbb E[2r(1-r)]=2\mathbb E[r]-2\mathbb E[r^2]\) and \(\mathbb E[r^2]=\mathrm{Var}(r)+(\mathbb E r)^2\ge(R^*)^2\). Equality needs \(\mathrm{Var}(r(X))=0\): the Bayes classifier's conditional error must be the same constant at every \(x\). (For example, \(\eta(x)\) constant, or taking only the values \(\rho\) and \(1-\rho\).)
Standardising with all the data uses the held-out fold's means and spreads, a (mild) use of held-out information. With 342 penguins and only two location-and-scale numbers per feature, the leak barely changes anything, so the two estimates agree to within a penguin or two. The leak becomes large when the data-dependent step has many degrees of freedom relative to \(n\): selecting a handful of features from thousands, as in the gene-expression example of spot check 1.7, or tuning many hyperparameters. The fix is always the same: put the step inside a pipeline (make_pipeline(StandardScaler(), ...)), so it is refitted on each training fold.
Cross-validation chooses \(k=3\) (CV RMSE 27.9 g), with test RMSE 25.5 g, better than any polynomial (the best, degree 6, had 34.3 g). The crash curve has a sharp local shape that polynomials, being global, can only follow by wiggling everywhere; a local method follows it where it happens. Lecture 3 (splines) and Lecture 7 (kernels) build smoother local methods.
The sub-cube has volume \(0.01=e^d\), so its edge is \(e=0.01^{1/d}\): \(0.01\), \(0.1\), \(0.631\) and \(0.955\). In 10 dimensions a neighbourhood holding 1% of the data spans 63% of the range of every feature; in 100 dimensions, almost the whole range. The "nearest" neighbours are not near, so local averaging has high bias. This is the curse of dimensionality, studied in Lecture 14.
A test accuracy is a sample proportion, so its standard error is about \(\sqrt{0.96\times0.04/1000}\approx0.0062\), or 0.6 percentage points. An improvement of 0.3 points, 3 test examples, is well within that. (A paired comparison of the two classifiers on the same test examples is more precise than this, because it uses only the examples on which they disagree, but it cannot rescue a 3-example difference.) The kNN comparison in Section 4 had the same character.
Each project is sized for one term and uses only this lecture's methods plus some data cleaning. Each has a clear result and could become a poster or a short paper.
Data. Palmer penguins: K. B. Gorman, T. D. Williams, W. R. Fraser, "Ecological sexual dimorphism and environmental variability within a community of Antarctic penguins (genus Pygoscelis)", PLoS ONE 9(3), e90081 (2014), doi:10.1371/journal.pone.0090081; A. M. Horst, A. P. Hill, K. B. Gorman, palmerpenguins: Palmer Archipelago (Antarctica) penguin data (2020), doi:10.5281/zenodo.3960218, CC0. Motorcycle crash data: B. W. Silverman, "Some aspects of the spline smoothing approach to non-parametric regression curve fitting", Journal of the Royal Statistical Society B 47(1), 1–52 (1985); distributed as mcycle in W. N. Venables, B. D. Ripley, Modern Applied Statistics with S (4th ed., Springer, 2002), package MASS; copy from V. Arel-Bundock, Rdatasets. Software: F. Pedregosa et al., "Scikit-learn: machine learning in Python", JMLR 12, 2825–2830 (2011).
every number in the text and widgets is computed in verify_L01.py; code-box outputs are pasted from actual runs; figures are drawn by figs_L01.py