What does '1-NN is statistically inconsistent' mean? I am confused about the fact "1-NN is statistically inconsistent". Why and how??
References
https://arxiv.org/pdf/1712.02369.pdf 
https://www.cs.bgu.ac.il/~karyeh/bayes-consistent-1nn.pdf 
https://pdfs.semanticscholar.org/a08f/133198a845589e6801e2125dc973d2652d66.pdf
( in introduction)
Thanks advance for any help :).
 A: In machine learning, we sometimes use this terminology, e.g. in these notes:
An algorithm is "statistically consistent" in a hypothesis class $\mathcal H$ for a distribution $P$ is one that whose error rate converges in probability to the minimum error rate over $\mathcal H$ as the number of samples goes to infinity. An algorithm is "Bayes consistent" for a distribution $P$ if it converges to the Bayes error rate, the best possible error rate. (Saying these properties hold "universally" implies they hold for all distributions $P$.)
The 1-NN algorithm is often said to be consistent only if the problem is realizable, i.e. the Bayes error is zero. As we saw in your other recent question, it is also Bayes-consistent when the Bayes error rate is 50%, but that's not very interesting since any predictor is Bayes-consistent in that case.
In Cover and Hart (1967), Nearest neighbor pattern classification, they give the following example (section VII): let $X \mid Y = 1$ have density $f_1$, and $X \mid Y = 2$ have density $f_2$, where
$$
f_1(x) = \begin{cases}
2 x & \text{if } 0 \le x \le 1 \\
0 & \text{otherwise}
\end{cases}
\qquad
f_2(x) = \begin{cases}
2 - 2 x & \text{if } 0 \le x \le 1 \\
0 & \text{otherwise}
\end{cases}
.$$

The expected error probability here with $n$ samples turns out to be, after "a lengthy but straightforward calculation,"
$$
\frac13 + \frac{1}{(n+1)(n+2)}
\to \frac13
.$$
But the Bayes error rate is the error rate of the predictor that says $2$ for $x < \frac12$ and $1$ for those above:
\begin{multline}
\frac12 \Pr(X > \tfrac12 \mid Y=2)
+ \frac12 \Pr(X<\tfrac12 \mid Y=1)
\\= \frac12 \int_0^{\frac12} f_1(x) \,\mathrm{d}x + \frac12 \int_{\frac12}^1 f_2(x) \,\mathrm{d}x
= \frac14
.\end{multline}
Thus the 1-NN expected error rate is always worse than the Bayes error rate.
Thus 1-NN is not Bayes consistent for this problem. It's also not statistically consistent for the hypothesis class of, say, locally constant predictors.
