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 space framework in the limit of vanishing kernel
bandwidth. We establish a relation between prior measures over the coefficients
in the kernel expansion and the induced measure on the weight vectors in kernel
space. Defining a sparse prior over the coefficients allows the application of
a PAC-Bayesian folk theorem that leads to a generalisation bound that is a
function of the number of redundant training examples: those that can be left
out without changing the solution. The presented bound requires to quantify a
prior belief in the sparseness of the solution and is evaluated after learning
when the actual redundancy level is known. Even for small sample size (m ~ 100)
the bound gives non-trivial results when both the expected sparseness and the
actual redundancy are high.

本文介绍了一种基于稀疏先验的 PAC-Bayesian 限制方法，将 K 最近邻分类器转化为核空间框架以求得其广义误差的界限，并在实验中证明了其高效性。