I am trying to understand in which situations the 1-NN classifier asymptotically attains the Bayes error rate. My intuition is that if the domain is countable, then 1-NN will asymptotically do as well as the Bayes classifier. Here is my proof:

We wish to show that:

$$\mathbb P(Y \neq \hat Y_N) \rightarrow \mathbb P(Y \neq \hat Y_*)$$

as $N \rightarrow \infty$ where $\hat Y_N$ is the 1-nearest neighbor classifier with a dataset of size $N$ and $\hat Y_*$ is the Bayes classifier. Recall the Bayes classifier is given by $\mathbb 1(\eta(X) \geq 1/2)$ where $\eta(X) = \mathbb P(Y=1 | X)$.

Rewriting $\mathbb P\left(Y \neq \hat Y_N\right)$ by expanding the cases in which the 1-NN prediction is incorrect:

$$\mathbb E \left[\mathbb P\left(Y \neq \hat Y_N | X\right)\right] = \mathbb E \left[\mathbb P\left(Y = 0, \hat Y_N =1 | X\right) + \mathbb P\left(Y = 1, \hat Y_N =0 | X\right)\right] $$

Then since $Y,\hat Y_N$ are independent given $X$ and conditioning on the dataset:

$$=\mathbb E \left[\mathbb 1\left(\hat \eta_N(\phi_N(X)) > 1/2\right)(1-\eta(X)) + \mathbb 1\left(\hat \eta_N(\phi_N(X)) \leq 1/2\right)\eta(X) \right ]$$

where $\phi_N$ gives the nearest neighbor in the training dataset of size $N$ and $\hat\eta_N(x)$ is the counting estimate from the training set given by: $\sum_i \mathbb 1 (Y_i = 1, X_i = x) / \mathbb 1 (X_i = x)$.

Expanding the expectation into a summation:

$$\sum_{x \in \mathcal X} \left \{\sum_{\mathcal D_N} \left [\mathbb 1\left(\hat \eta_N(\phi_N(x)) > 1/2\right)(1-\eta(x)) + \mathbb 1\left(\hat \eta_N(\phi_N(x)) \leq 1/2\right)\eta(x)\right] \mathbb P (D_N) \right \} \mathbb P(X=x)$$

Where the second summation is over all possible datasets of size $N$.

Since $\hat \eta _N$ converges uniformly in probability to $\eta$, and $\phi_N(x)$ converges to $x$ in probability, each term in the summation converges to $\min \{\eta(x), 1-\eta(x)\} = \mathbb P(Y \neq \hat Y_* | X)$.

I believe that if $\mathcal X$ was not countable, then we would also need a dominated convergence argument, which is not possible without more information about $\eta$.

I could use some feedback on my proof and reasoning.

EDIT: I realized this claim is incorrect since the asymptotic error rate is given by $\mathbb E 2\eta(1-\eta)$ which is only equal to $\mathbb E \min\{\eta, 1-\eta \}$ when $\eta \in \{0, 1/2, 1\}$ for all $x \in \mathcal X$. But this condition is unrelated to the countability of $\mathcal X$.

The error in this proof comes from assuming that $\hat \eta_N$ converges uniformly to $\eta$. This might be true for the k-NN classifier where $k$ grows with the sample size, $N$, but it is not true in general for $k=1$ or any fixed $k$. The expectation of the indicator $\mathbb 1\left(\hat \eta_N(\phi_N(x)) > 1/2\right)$ over the set of datasets $D_N$ is given by $\mathbb P(\hat \eta_N(\phi_N(x)) > 1/2)$, but $\hat \eta_N$ is not given by the counting estimate stated earlier, it is simply given by the $Y$ corresponding with the nearest neighbor of $x$. When $\mathcal X$ is finite, the nearest neighbor is the point itself with high probability when $N$ is large enough, so $\mathbb P(\hat \eta_N(\phi_N(x)) > 1/2)$ converges to $\mathbb P (Y = 1 | X=x)$ which is just $\eta(x)$.

  • $\begingroup$ From what I recall of this proof, it makes use of a result by Cover & Hart (1967). It might be best to consult an authoritative reference and compare, as these kinds of proofs tend fall in a blind spot on Cross Validated. (At least from my own experience with these kinds of questions). $\endgroup$
    – microhaus
    Aug 29, 2021 at 16:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.