The Bayes Classifier and Nearest Neighbours

Logistic regression gave one way to draw a boundary. Before comparing it with others, it is worth knowing what the best possible boundary looks like - because there is one, it is unbeatable, and every method in this path is a different attempt to guess at it.

The classifier that cannot be beaten

Suppose you knew, for every point $x$, the true conditional probability of each class, $P(Y = j \mid X = x)$. The Bayes classifier assigns $x$ to whichever class has the largest one.

That rule minimises the error rate, and the argument is almost too short to count as a proof. At each individual $x$ the probability of being wrong is $1 - \max_j P(Y = j \mid X = x)$, and no other rule can make that smaller at that point. A rule that is optimal at every point is optimal on average. The resulting error,

$$1 - E\left[\max_j P(Y = j \mid X)\right],$$

is the Bayes error rate: the classification analogue of irreducible error. It is not zero, because the classes genuinely overlap in the population.

Notice what the rule requires. It needs $P(Y \mid X)$ - precisely the quantity every real method is trying to estimate. The Bayes classifier is therefore a benchmark you can only evaluate in a simulation where you built the data yourself. That is not a reason to ignore it; it is the reason simulations are worth running.

Working it out on the line

Take two classes on the real line. Class 1 is $N(-1.25, 1)$, class 2 is $N(1.25, 1)$, and they are equally likely. Where is the boundary?

The posteriors are equal where $\pi_1 f_1(x) = \pi_2 f_2(x)$. With equal priors and equal variances the densities are mirror images, so the boundary is the midpoint, $x = 0$. Everything left of zero is called class 1.

The error rate follows immediately. A class 2 observation is misclassified when it falls below zero, which happens with probability $\Phi(-1.25) = 0.105650$, and by symmetry the same holds for class 1. So the Bayes error rate is

$$0.105650 .$$

About one prediction in ten is wrong, and no method, however sophisticated, will do better on this problem. Integrating the mixture numerically over four million points on the line returns the same value to six decimal places.

What the priors do

Now make class 1 more common, with $\pi_1 = 0.7$. The boundary solves $\pi_1 f_1(x) = \pi_2 f_2(x)$, and taking logs gives

$$x = \frac{\sigma^2 \log(\pi_1/\pi_2) + (\mu_2^2 - \mu_1^2)/2}{\mu_2 - \mu_1} = +0.338919 .$$

The boundary moved toward the rarer class, enlarging class 1's region. That is the right direction, and it is worth pausing on because the opposite is a natural guess: since class 1 is more common, shouldn't its region shrink to avoid swamping class 2? No - a point near zero is now more likely to have come from class 1 simply because there are more class 1 points to come from, and the optimal rule follows the posterior, not the density.

The payoff is measurable. At the shifted boundary the error rate is $0.093565$; keeping the boundary at zero and ignoring the prior gives $0.105650$, so the mistake costs $0.012084$. At $\pi_1 = 0.9$ the boundary reaches $+0.878890$ and the error falls to $0.050496$, while the boundary at zero still gives $0.105650$ - by then, ignoring the prior more than doubles the error.

Checked against a grid of 240,001 candidate thresholds, the derived boundary really is the best available. It is a small thing to verify and it catches sign errors, which are easy to make here and invisible afterwards.

Imitating the Bayes classifier by counting

Real data does not come with $P(Y \mid X)$. k-nearest-neighbours estimates it in the most direct way imaginable: look at the $k$ training points closest to $x_0$, and use the proportions among them.

$$P(Y = j \mid X = x_0) = \frac{1}{k} \sum_{i \in \mathcal{N}_0} I(y_i = j)$$

Then apply the Bayes rule to that estimate. Nothing is fitted in advance - the training set is the model, which makes training instantaneous and prediction expensive.

k is the flexibility dial

Take a two-dimensional problem whose Bayes error rate, computed by integration, is $0.092708$. Fit on 200 training points, score on 20,000 test points:

Read the two ends first. At $k = 1$ every training point is its own nearest neighbour, so the training error is exactly zero - and the test error, $0.138200$, is the worst in the table apart from the degenerate $k = 199$. That single pair of numbers is the clearest demonstration you will see that training error is not an estimate of test error.

At $k = 199$ out of 200 training points, nearly the whole sample votes on every prediction. The classifier has stopped depending on $x$ at all and simply returns the majority class, so its error, $0.504850$, is essentially the class prior. Maximum bias, minimum variance, no information.

Between them the curve is U-shaped, with a shallow floor from $k = 9$ to $k = 45$ and a best value of $0.097150$ at $k = 15$ - within half a percentage point of the Bayes floor, from a method that assumed nothing about the shape of the boundary. There is no formula for the best $k$; it is chosen by cross-validation, and the flatness of the floor means it usually only has to be roughly right.

What it costs

The method imposes no shape on the boundary, so it can trace curves and disconnected regions no linear model can express. In exchange it has no way to ignore an irrelevant feature: every dimension enters the distance, so accuracy degrades as uninformative features are added. In high dimensions the "nearest" neighbours are not close to $x_0$ in any useful sense, which is one face of the curse of dimensionality.

And because the distance is Euclidean, a feature measured in large units dominates it. Standardising is not a refinement here; it is a precondition for the method meaning anything at all.

Before the quiz

The Bayes classifier picks the most probable class at every point and cannot be beaten; what it leaves behind is the Bayes error rate, $0.105650$ for the one-dimensional example. Priors move the boundary toward the rarer class, and ignoring them costs measurably. k-nearest-neighbours imitates the rule by counting neighbours, with $k$ as the flexibility dial: $k = 1$ memorises, $k \approx n$ returns the majority class, and the useful values are in between.