Bayes classifier and KNN
The Bayes classifier is the best classifier there could ever be, and you can never actually build it. KNN is the simplest way to imitate it. Both come back in every later week.
The 2023 paper had a full KNN question: write a distance in \(\mathbb R^n\), explain KNN for regression and for classification, explain the role of \(K\) in terms of bias and variance, and classify a point by hand. By the end of this stage you can do all of it.
Book: what to read for this stage
ISLP 2.2.3 The classification setting: read all of it (Bayes classifier, Bayes error rate, KNN, figures 2.13 to 2.17). Exercise 2.4.7 (KNN by hand) is excellent practice. KNN regression is in 3.5 (you’ll meet it properly in stage 8).
Slide typo
Slide equation (33) for KNN leaves out the \(\frac1K\). Without it you get a count, not a probability. The book (2.12) and the slide’s own \(K = 3\) example (\(\frac13\), \(\frac23\)) both include it.
1. The Bayes classifier: pick the most likely class
For a classification problem, the conditional probability \(P(Y = k \mid X = x_0)\) is the chance that a point at \(x_0\) belongs to class \(k\). The Bayes classifier picks the class with the biggest one:
\[\hat Y(x_0) = \arg\max_k P(Y = k \mid X = x_0).\]
(\(\arg\max_k\) means “the \(k\) that makes it biggest”, not the biggest value.) With two classes this is: predict 1 if \(P(Y = 1 \mid x_0) > 0.5\).
It minimises the test error rate: no classifier can do better. Its error rate, the Bayes error rate, is
\[1 - \mathbb E\Big[\max_k P(Y = k \mid X)\Big],\]
and at a single point \(x_0\) the chance it’s wrong is \(1 - \max_k P(Y = k \mid x_0)\). Whenever the classes overlap this is not zero: it’s the classification version of the irreducible error.
Worked example.
- \(P(Y = 1 \mid x_0) = 0.7\): predict 1; chance of being wrong at \(x_0\) is \(0.3\).
- Three classes with probabilities \((0.2, 0.5, 0.3)\): predict class 2; error at \(x_0\) is \(0.5\).
- \(X\) takes two values: \(P(X = a) = 0.6\) with \(P(Y = 1 \mid a) = 0.9\), and \(P(X = b) = 0.4\) with \(P(Y = 1 \mid b) = 0.3\). Bayes predicts 1 at \(a\) and 0 at \(b\). Overall Bayes error \(= 0.6 \times 0.1 + 0.4 \times 0.3 = 0.18\).
Four classes with \(P(Y = k \mid x_0) = (0.1, 0.25, 0.35, 0.3)\). What is the probability that the Bayes classifier is wrong at \(x_0\)?
It predicts class 3 (0.35), so the error probability is \(1 - 0.35 = 0.65\).
Why can’t we use the Bayes classifier in practice?
It’s the gold standard. Every classifier in the course (KNN, logistic regression, LDA, naive Bayes, trees, networks) is a way of estimating those probabilities and then applying the same “pick the biggest” rule.
2. K-nearest neighbours
KNN estimates \(P(Y = k \mid x_0)\) by looking at the training points nearest to \(x_0\):
- Choose \(K\). Find the \(K\) training points closest to \(x_0\) (Euclidean distance, stage 2). Call them \(\mathcal N_{x_0}\).
- Estimate each class probability as the fraction of those neighbours in the class: \[\tilde P(Y = k \mid x_0) = \frac{1}{K}\sum_{(x, y) \in \mathcal N_{x_0}}\mathbb 1(y = k).\]
- Predict the class with the biggest estimate: a majority vote.
For regression, step 2 changes to averaging the neighbours’ responses: \(\hat y(x_0) = \frac1K\sum_{i \in \mathcal N_{x_0}} y_i\).
Worked example (1-D). Training data \(x = 1, 2, 3, 4, 5, 6\) with labels A, A, B, B, B, A. Test point \(x_0 = 3.4\).
Distances: \(|3 - 3.4| = 0.4\) (B), \(0.6\) (B, at 4), \(1.4\) (A, at 2), \(1.6\) (B, at 5), \(2.4\) (A, at 1), \(2.6\) (A, at 6).
- \(K = 1\): {B}, so \(\tilde P(B) = 1\): predict B.
- \(K = 3\): {B, B, A}, so \(\tilde P(B) = 2/3\): predict B.
- \(K = 5\): {B, B, A, B, A}, so \(\tilde P(B) = 3/5\): predict B.
- \(K = 6\): three of each, a tie. That’s one reason to use odd \(K\) with two classes.
KNN regression: \(x = (1, 2, 3, 4, 5, 6)\) with \(y = (1.0, 1.5, 2.5, 3.0, 5.0, 6.0)\). Predict at \(x_0 = 3.4\) with \(K = 3\).
The nearest are \(x = 3, 4, 2\) (distances 0.4, 0.6, 1.4), so \(\hat y = (2.5 + 3.0 + 1.5)/3 \approx 2.333\).
3. The role of \(K\)
\(K\) is KNN’s flexibility knob, and it runs backwards: small \(K\) means flexible.
- Small \(K\) (e.g. \(K = 1\)): the decision boundary is jagged and follows individual points. Low bias, high variance. The training error of 1-NN is 0 (each training point is its own nearest neighbour), which tells you nothing about the test error. This is overfitting.
- Large \(K\) (e.g. \(K = 100\), or \(K = n\), which predicts the majority class everywhere): a smooth, almost straight boundary. High bias, low variance. Underfitting.
- In between, KNN can come surprisingly close to the Bayes classifier (the slides show \(K = 10\)).
Plot error against \(1/K\) (so flexibility increases to the right): training error falls steadily, test error is U-shaped, and the test error never goes below the Bayes error rate. Choose \(K\) on a validation set.
One more practical point: because KNN measures distances, inputs on big scales (income in pounds) swamp inputs on small scales (number of children). Standardise the inputs first.
The true decision boundary is highly non-linear. Should the best \(K\) be small or large?
ISLP exercise 2.4.7(c). A large \(K\) smooths the boundary towards a straight line, which has high bias here.
Stage test
(5 marks, exam format 3; 2023 Q2.) Explain the role of \(K\) in KNN and how it controls the bias and the variance of the model.
In KNN, \(K\) is the number of nearest training points whose labels are combined to predict at a new point (by majority vote for classification, by averaging for regression). It controls the model’s flexibility. With small \(K\), the prediction depends on very few nearby points, so the decision boundary is jagged and can follow complicated shapes: the bias is low but the variance is high, because changing a single training point changes the predictions; \(K = 1\) even has zero training error, which is overfitting. With large \(K\) many points are averaged, so the boundary is smooth: the variance is low but the bias is high, and at \(K = n\) the model predicts the majority class everywhere. The test error is therefore U-shaped as \(K\) varies, and \(K\) should be chosen to minimise the error on a validation set (or by cross-validation).
Binary problem with \(P(Y = 1 \mid x_0) = 0.45\). What is the Bayes classifier’s probability of error at \(x_0\)?
It predicts 0 (probability 0.55), so it’s wrong with probability \(1 - 0.55 = 0.45\).
True or false: with enough data and the right \(K\), KNN can achieve a test error rate below the Bayes error rate.
False. The Bayes classifier is optimal by definition, so its error rate is a lower bound for every classifier, KNN included.
How does KNN for regression differ from KNN for classification?
Same neighbours, same distance: only the way the neighbours’ outputs are combined changes.
\(P(X = a) = 0.5\) with \(P(Y = 1 \mid a) = 0.8\), and \(P(X = b) = 0.5\) with \(P(Y = 1 \mid b) = 0.4\). What is the overall Bayes error rate?
At \(a\) predict 1 (wrong with probability 0.2); at \(b\) predict 0 (wrong with probability 0.4). Overall \(0.5 \times 0.2 + 0.5 \times 0.4 = 0.3\).