studies have shown that the predictive accuracy of NN (nearest-neighbor)
algorithms is comparable to that of the decision trees, rule learning systems,
and neural net learning algorithms on many tasks. In addition, the
probability of error of NN rules is bounded above by twice the optimal
Bayes probability error.
The theorems below show that NN algorithms can learn some concepts
very efficiently using the best-case model. The teacher simply selects
examples of the best possible locations in the n-dimensional features
space, and provides these examples to the algorithm.