Nearest-neighbor classifier for the perceptron

Abstract

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 --> infinity. 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.