Nearest-Neighbour Classifier for the Perceptron
M. -C. Bouten, C. van den Broeck · Europhysics Letters (EPL) · 1994
We calculate the generalization error for the nearest-neighbour classifier based on a set of random examples generated by a teacher perceptron. Explicit results are given for dimensions N = 2, N = 3 and N → ∞. For a natural extension of the nearest-neighbour rule which includes the k -nearest-neighbour rule and the Hebbian perceptron as particular cases it is found that the Hebbian perceptron gives the smallest generalization error.