Machine Learning’s Debt to Nearest Neighbors

The simplicity of the k-Nearest Neighbor rule—one of the staples of machine learning—belies its rich history and enormous impact. Here’s why the k-NN rule can help us appreciate some key conceptual underpinnings of ML.

First, what is the k-NN rule? Simply put, an instance of unlabeled data can be categorized as being of one class or the other by comparing it to its nearest neighbor(s) in some possibly high-dimensional vector space (where each instance of data is a vector). Birds of a feather flock together. As Peter Hart, the co-inventor of the Cover-Hart k-NN algorithm in the 1960s, told me: “That’s the nearest neighbor rule. That’s the caveman intuition: If they look alike, they probably are alike.”

This intuition was also recognized in the 11th century by the Alhazen, a Muslim Arab mathematician, astronomer, and physicist, as he speculated on how humans recognize objects. Then, there’s the extraordinary story of the British epidemiologist John Snow, who used techniques that presage the k-NN rule, to figure out the epicenter of London’s deadly 1854 cholera outbreak; these mathematical ideas were formalized by Ukrainian mathematician Georgy Voronoi, who gave us his eponymous Voronoi cells. Then, in 1951, the amazing statistician Evelyn Fix, while working ceaselessly at UC Berkeley to help the US war efforts, teamed up with Joseph Hodges to first elucidate the nearest neighbor rule.

Then, in the 1960s, Peter Hart, working on his PhD with advisor Thomas Cover at Stanford (who was himself just beginning his academic career), came up with some rigorous math to show that the k-NN rule (where k refers to the number of neighbors in the vector space), in the limit of large k and small k/n (n=number of data samples), begins approaching the best possible ML algorithm: the Bayes Optimal classifier. And even at its worst, the k-NN rule is not that bad, despite its algorithmic simplicity.

But the k-NN rule would also show up the limits of ML algorithms when the dimensionality of data (i.e. the number of elements in the vector being used to represent an instance of data) begins growing. Something called the “curse of dimensionality” takes over! The k-NN rule is a brilliant way to understand this curse—which then leads us to appreciate dimensionality reduction methods, such as Principal Component Analysis (PCA). It also helps us appreciate the counter-intuitive brilliance of kernel methods, which deliberately project data into higher dimensions. How do they avoid the curse? As do deep neural networks, which also operate in extremely high dimensions. How so?

This historical narrative, with inputs from Peter Hart himself, along with the relevant math, and intuitive visualizations can be found in WHY MACHINES LEARN.

US:UK: