A Bayes consistent 1-NN classifier
This provides a new, efficient alternative to k-NN for classification tasks, with potential applications in machine learning where computational resources are limited.
The paper tackles the problem of achieving strong Bayes consistency in proximity-based classifiers by modifying the 1-nearest neighbor classifier, resulting in a method with statistical and algorithmic advantages such as finite-sample error bounds and efficient algorithms.
We show that a simple modification of the 1-nearest neighbor classifier yields a strongly Bayes consistent learner. Prior to this work, the only strongly Bayes consistent proximity-based method was the k-nearest neighbor classifier, for k growing appropriately with sample size. We will argue that a margin-regularized 1-NN enjoys considerable statistical and algorithmic advantages over the k-NN classifier. These include user-friendly finite-sample error bounds, as well as time- and memory-efficient learning and test-point evaluation algorithms with a principled speed-accuracy tradeoff. Encouraging empirical results are reported.