# The expected error of 1 nearest Neighbor (1-NN) on large or infinite dataset

I have question regarding the expected error of 1NN. Assume the training set is large enough or infinite. let x' is a test point and r be its nearest point. the probability distribution of two classes( 1 and 0) will be essentially the same. Two classes are overlapping totally. The Bayes error rate in this case will be 0.50% (I think). I want to know what is the expected error of 1NN for x' point, is it 1 or 0.50 ?! if Not what is the value.

R(x')=P(Y=1,x')P(Y=0,r)+P(Y=0,x')P(Y=1,r)

R(x')=0.50

I attached figure for the problem.

• What, numerically, are the values of $P(y=1, x')$ and $P(y=0, r)$? When you multiplied them, you got $0.5$... is this correct? – jbowman Nov 17 '19 at 3:22
• No, you have two types of error FN and FP. In the example above , we need to calculate the probability of these error. 𝑃(𝑦=1,𝑥′) and 𝑃(𝑦=0,𝑟) means when you predict the label as 0 which actual label is 1. You don't multiply them. So the probability of FN and FP will be 0.50 for each. So what ever you classify the point you will get error 0.50. – miss Ran Nov 17 '19 at 14:27

1-NN converges to an asymptotic error rate of at most twice the Bayes error rate. It can be less than that, like in this situation, where the Bayes error rate is 50%, and so is the asymptotic error of the classifier. In fact, the result of Cover and Hart (1967), Nearest neighbor pattern classification, is that if the Bayes error rate is $$\rho$$, then $$\rho \le \text{1-NN error} \le 2 \rho (1 - \rho) \le 2 \rho .$$ If $$\rho = 0.5$$, then $$2 \rho (1 - \rho) = \frac12$$ and we see that we have $$\frac12 \le \text{1-NN error} \le \frac12$$.

In fact, if the Bayes error rate is 50%, then the asymptotic error rate of any classifier is 50%.

It can't be less than 50%, by definition.

Suppose you found a classifier $$f(x)$$ with a worse error rate, $$p > 0.5$$. Then think about the classifier that takes what $$f(x)$$ and then says the opposite, $$1 - f(x)$$. ("Ask an idiot what they would do, and do the opposite.") This classifier's error rate would be $$1 - p$$, which is less than the Bayes error of $$0.5$$, and that's impossible, so finding such an $$f$$ must be impossible. That is, every classifier has an error rate of 50% when the Bayes error rate is 50%.

Further explanation about error rates here, since it might help to be a little bit formal.

The Bayes error rate refers to a test error rate. That is:

• Choose a predictor $$f$$ mapping input points $$x$$ to a label $$f(x)$$, somehow, presumably based on some training data.
• The error rate of $$f$$ is $$\Pr(f(X) \ne Y)$$: given a new random test point $$X$$ with true label $$Y$$, the probability that $$f(X)$$ disagrees with $$Y$$. Importantly, $$X$$ and $$Y$$ here are independent of the training data.
• The Bayes error rate is the lowest error rate achievable by any predictor $$f$$, no matter how it's chosen.

Now, in your case $$X$$ and $$Y$$ are independent of each other: $$X$$ follows some arbitrary distribution, and $$Y$$ is just equally likely to be $$0$$ or $$1$$, i.e. it's Bernoulli$$(1/2)$$. In this case, for any $$f$$, regardless of whether it's the 1-NN predictor corresponding to some distribution, a deep neural net, or the predictor that always says $$1$$, we have that $$\Pr(f(X) = Y) = \frac12$$ as we proved above.

In the particular case of the 1-NN predictor corresponding to some training set: we get $$N$$ training examples $$(x_i, y_i)$$, and our predictor $$f(x)$$ returns the $$y_i$$ corresponding to the closest $$x_i$$ to $$x$$.

In the case where both distributions have densities, even as $$N \to \infty$$, the probability that $$X$$ is exactly equal to any of the $$x_i$$ is $$0$$. Remember that we're not talking about the training error rate but the test error rate. So, when the two distributions are the same, $$f(X)$$ will be whatever point happened to be closest, and importantly the true label $$Y$$ will be totally independent of that because the two distributions are the same: it'll just be uniform. So the error rate when the distributions are the same is 50%, as we proved that it must be.

(Even if they didn't have densities, this would still be true; we just have to define what 1-NN does when there are ties.)

• OK, why 1NN is statistically inconsistent when data set is infinite or very large. What is the fact that makes 1NN inconsistent? if the 1NN error will be 50% when the Bayes error rate is 50%. – miss Ran Nov 15 '19 at 19:41
• Yes, but if the Bayes error rate is 5%, the 1NN error might be up to 10%. If the problem is perfectly possible (Bayes error rate 0%) or impossible (50%), then 1NN is asymptotically optimal; in between, it's not quite. – Dougal Nov 15 '19 at 19:47
• Sorry, could you clarify more why 1-NN inconsistent ?! I could not understand why inconsistent in this setting. – miss Ran Nov 15 '19 at 19:54
• Ah, see, (a) you have to do a train/test split and (b) infinity is weird. It's not actually "1-NN with infinitely many training points," it's "1-NN with $N$ training points as $N \to \infty$". When you query a point, if the distributions have densities, you won't have seen that exact point, but you'll have seen one extremely close by. The label of that nearby point is random. – Dougal Nov 15 '19 at 21:55
• @missRan I just edited to hopefully make things a little clearer. Yes, the error rate is 0.5 when the two distributions agree. – Dougal Nov 15 '19 at 22:38