Interactive demo · Statistical Learning: Theory and Methods · Chapter 13

How good can nearest neighbours be? The Cover–Hart bound

Here the truth is known: X is uniform on the square and the class probabilities pk(x) wind round in a spiral, sharper for larger β. So the Bayes rate E* = E[1 − maxk pk(X)], the asymptotic 1-nearest-neighbour rate E1 = E[∑k pk(1 − pk)] and the Cover–Hart bound E*(2 − K E*/(K − 1)) are computed exactly, and every error shown is the expected test error 1 − ppredicted class(x) averaged over 2,000 test points. Change the training size N and watch the k-NN curve approach its limit.

Number of classes K

Sharpness β (larger = smaller Bayes rate)

Training size N

Training samples averaged (replicates)

Random seed

Try these

Ties in the vote (possible with three classes) go to the tied class whose nearest member comes first. The bottom curve uses the same replicates and seeds for N = 25 to 6,400. The asymptotic k-NN curve (black) is drawn for two classes only.

In the lecture notes