Nearest neighbour classification

The nearest-neighbour rule is the simplest learning algorithm there is: to label a new example, find the stored example most like it and copy the label. It is memorisation with a distance function, and it looks too naive to be worth analysing. In January 1967 Thomas Cover and Peter Hart showed that it is nearly optimal. With enough data, its error rate is at most twice that of the best classifier that could exist for the problem, and often much closer.

The result was one of the first theorems in pattern recognition, a field that had been growing beside artificial intelligence since the 1950s and had far more in common with statistics than with logic. Where the AI laboratories wanted programs that reasoned, pattern recognition wanted decision rules that worked, and was willing to evaluate them by counting mistakes on held-out data.

That habit, of testing on data the method has not seen, is the discipline that made the statistical era of the 1990s possible and the benchmark culture of ImageNet inevitable. Nearest-neighbour search itself never went away. Retrieval-augmented language models and the embedding databases of the 2020s are the 1967 rule applied to vectors of a thousand dimensions.