A PAC-Bayesian Analysis of Distance-Based Classifiers: Why Nearest-Neighbour works!
This provides theoretical justification for why nearest-neighbor methods work, which is incremental as it builds on existing PAC-Bayesian analysis.
The paper tackles the generalization error of K-nearest-neighbor classifiers by deriving PAC-Bayesian bounds through a kernel space framework, showing non-trivial results for small sample sizes (e.g., m ~ 100) when sparseness and redundancy are high.
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.