A PAC-Bayesian Analysis of Distance-Based Classifiers: Why Nearest-Neighbour works!

Thore Graepel, Ralf Herbrich

Abstract We present PAC-Bayesian bounds for the generalisation error of the K-nearest-neighbour classifier (K-NN). This is achieved by casting the K-NN classifier into a kernel spa…