Asymptotic slowing down of the nearest-neighbor classifier
Robert R. Snapp, Demetri Psaltis, Santosh S. Venkatesh · Neural Information Processing Systems · 1990
If patterns are drawn from an n-dimensional feature space according to a probability distribution that obeys a weak smoothness criterion, we show that the probability that a random input pattern is misclassified by a nearest-neighbor classifier using M random reference patterns asymptotically satisfies PM(error) - P∞(error) + a/M2/n, for sufficiently large values of M. Here, P∞(error) denotes the probability of error in the infinite sample limit, and is at most twice the error of a Bayes classifier. Although the value of the coefficient a depends upon the underlying probability distributions, the exponent of M is largely distribution free. We thus obtain a concise relation between a classifier's ability to generalize from a finite reference sample and the dimensionality of the feature space, as well as an analytic validation of Bellman's well known curse of dimensionality.