NEAREST-NEIGHBOR CLASSIFIER FOR THE PERCEPTRON

We calculate the generalization error for the nearest-neighbour classi fier based on a set of random examples generated by a teacher perceptr on. Explicit results are given for dimensions N = 2, N = 3 and N --> i nfinity. For a natural extension of the nearest-neighbour rule which i ncludes the k-nearest-neighbour rule and the Hebbian perceptron as par ticular cases it is found that the Hebbian perceptron gives the smalle st generalization error.