Comparing Classifiers, and What Accuracy Hides

Comparing classifiers on real data has an awkward property: you never know how much room was left. A method scoring 12% error might be nearly optimal or might be leaving half the available accuracy on the table, and nothing in the data tells you which. This article works on simulated data instead, where the best possible classifier can be computed exactly - which turns vague comparisons into measurements.

A. The classifier that cannot be beaten

If you knew $P(Y = j \mid X = x)$ for every $x$, the best you could do is assign each point to the class with the largest one. That is the Bayes classifier, and it is optimal for a reason almost too short to be a proof: at each $x$ the chance of being wrong is $1 - \max_j P(Y = j \mid X = x)$, and no rule makes that smaller at that point. Optimal everywhere means optimal on average.

What it leaves behind,

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

is the Bayes error rate - the classification counterpart of irreducible error, non-zero because the classes genuinely overlap.

Two Gaussian classes on the line, $N(-1.25, 1)$ and $N(1.25, 1)$, equally likely. The densities are mirror images so the boundary is the midpoint $x = 0$, and the error rate is $\Phi(-1.25) = 0.105650$. Integrating the mixture over four million grid points agrees to six decimals.

B. Priors move the boundary - which way?

Make class 1 more common, $\pi_1 = 0.7$. The boundary solves $\pi_1 f_1(x) = \pi_2 f_2(x)$:

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

It moves toward the rarer class, enlarging the common class's region. The opposite is a tempting guess - surely the abundant class needs less room? - and it is wrong: a point near zero is now more likely to be class 1 precisely because there is more class 1 to draw from.

Ignoring the prior costs $0.012084$ at 0.7 and more than doubles the error at 0.9. This is worth checking numerically rather than trusting the algebra: the derived boundary was confirmed optimal against a grid of 240,001 thresholds, which is exactly the check that catches a sign error - and did, on the first attempt at this article.

C. Imitating it by counting

Real data lacks $P(Y \mid X)$. k-nearest-neighbours estimates it as directly as possible - take the $k$ closest training points and use their proportions - then applies the Bayes rule to that estimate. Nothing is fitted in advance; the training set is the model.

On a two-dimensional problem with Bayes error $0.092708$, fitted on 200 training points and scored on 20,000:

The ends are the lesson. At $k = 1$ the training error is exactly zero while the test error, $0.138200$, is the worst in the table apart from the degenerate $k = 199$ - the clearest demonstration available that training error estimates nothing. At $k = 199$ out of 200, almost the whole sample votes on every prediction, the classifier stops depending on $x$ at all, and its error is essentially the class prior.

Between them is the U the bias-variance decomposition predicts, with a best value of $0.097150$ at $k = 15$ - within half a point of the floor, from a method that assumed nothing about the boundary's shape.

D. Modelling the classes instead of the boundary

Logistic regression is discriminative: it goes straight for $P(Y \mid X)$. Discriminant analysis is generative - it models $P(X \mid Y = k)$ as Gaussian for each class, along with the priors, and inverts with Bayes' theorem.

Assume every class shares one covariance $\Sigma$. Taking logs and dropping what does not depend on $k$ leaves $\log \pi_k - \frac{1}{2}(x - \mu_k)^\top \Sigma^{-1}(x - \mu_k)$. Expand it: the term $x^\top \Sigma^{-1} x$ never mentions $k$, so it cancels when classes are compared, and what survives,

$$\delta_k(x) = x^\top \Sigma^{-1} \mu_k - \tfrac{1}{2}\mu_k^\top \Sigma^{-1}\mu_k + \log \pi_k ,$$

is linear in $x$. The linearity is a consequence of the shared covariance, not an independent modelling choice. Give each class its own $\Sigma_k$ and the quadratic term stays: the boundary curves. That is QDA, at $K$ times the covariance parameters.

E. When the shared assumption fails, and when it saves you

Class A at the origin with correlation $+0.75$; class B at $(1.5, 1.5)$ with correlation $-0.75$. No single covariance describes both, so the optimal boundary genuinely curves, and integrating the mixture gives a floor of $0.092708$. On 200 training points, 200,000 test points:

The pooled covariance explains it: averaging $+0.75$ against $-0.75$ gives an off-diagonal of $-0.046809$, near zero, describing neither class. QDA estimates $+0.685607$ and $-0.722339$ separately and lands $0.0008$ above the floor.

Note the diagnosis. What identifies LDA's problem as bias is the gap to the floor, not the gap to QDA - without the benchmark you would know only that one method beat another, which is compatible with both being bad.

Now reverse it. A second problem whose true boundary really is linear, floor $0.244211$, averaged over 400 runs:

QDA is not wrong here - a quadratic model contains the linear one, so its bias is nil and both converge to the floor. It simply cannot afford its parameters at $n = 20$. The gap closes monotonically, which is the bias-variance trade-off appearing as a model-selection rule rather than a diagram.

Two of those three numbers are properties of the population rather than of a fit, and the figure below computes them: the Bayes floor at 0.092708, and the error of the line LDA converges to with unlimited data, 0.114143. The gap between them is LDA's bias, and no amount of data removes it - the 0.118955 measured above is that bias plus the estimation error of a 200-point fit. That line is not even the best straight one: the error-minimising line, parallel to LDA's but shifted towards B, makes 0.106416, because LDA assumes a covariance the classes do not share. Slide the correlation to zero and watch the curve settle onto the line and the bias go to nothing, which is the premise of the reversal below.

F. What one error rate conceals

Every figure above is a single number, and single numbers hide the shape of the errors. The QDA classifier's $0.093480$ decomposes as:

Sensitivity $0.961083$, specificity $0.851753$. It is markedly better at one job than the other.

Before blaming the fit, compute what the Bayes rule does class by class: sensitivity $0.952845$, specificity $0.861738$. The optimal classifier is asymmetric too, by almost the same margin. The two classes are equally spread, but A's long axis points at B (variance 1.75 along the line joining the centres) while B is narrow in that direction (0.25) - A's tail reaches into B's region, and the optimal rule gives away more of A in exchange. The imbalance belongs to the problem, not the model, and the way to tell is to compute the benchmark rather than reason about it.

G. The threshold is a decision, not a default

The threshold is not part of the model. Moving it changes the decision rule while every fitted parameter stays put:

The error rate says 0.5 is best, but the error rate weights a false positive and a false negative equally, and that weighting is an assumption. Where a missed positive costs ten times a false alarm, minimising the error rate is minimising the wrong quantity.

Sweeping the threshold and recording each (false positive rate, true positive rate) pair traces the ROC curve, whose area has an exact reading: the probability that a random positive outscores a random negative. Computing that area by the trapezoid rule and computing the Mann-Whitney $U$ statistic on the raw scores agree here to floating-point precision - the equivalence is an identity, not an approximation. Across all thresholds, QDA scores $0.965269$ against LDA's $0.933488$.

Because only the ordering matters, AUC is blind to calibration: a model that ranks perfectly while reporting every probability between $0.98$ and $0.99$ has an AUC of 1.

The figure below is this problem's optimal rule, integrated rather than fitted, so its default row is the benchmark quoted above: 9.27% error, sensitivity 0.953, specificity 0.862. Move the threshold and nothing is refitted; only the line between yes and no moves, and the four cells rebalance. Then make class B one case in a hundred. Sensitivity and specificity do not budge, because neither one can see how rare the class is, while accuracy climbs toward specificity and precision falls through the floor.

Key takeaways

• The Bayes classifier is optimal and needs the answer to compute, which makes simulated data the only place a method's remaining headroom is visible.
• Priors move the boundary toward the rarer class; ignoring them cost $0.012084$ at a 0.7/0.3 split and doubled the error at 0.9/0.1.
• In k-nearest-neighbours, $k$ is the flexibility dial: zero training error at $k = 1$, the class prior at $k \approx n$, and the best value in between.
• A shared covariance is what makes a discriminant boundary linear. Whether to share is decided by sample size as much as by truth.
• Diagnose bias against the Bayes floor, not against a competing method.
• Report the confusion matrix before the accuracy, choose the threshold from costs, and read AUC as ranking rather than calibration.

What's next

Every method here drew one boundary from one fitted model. Ensembles take a different route - fit many weak models and combine them - and the reason that works is a variance argument rather than a bias one.