Why Machines Learn: The Elegant Math Behind Modern AI

by Anil Ananthaswamy

Perhaps the most important feature of the k-NN algorithm is that it’s a so-called nonparametric model. Cast your mind back to the perceptron. Once you have a trained model, using some initial training dataset, the perceptron is simply characterized by its weight vector, w. The number of elements of this vector equals the number of parameters that define the perceptron. This number is not dependent on the amount of training data. You could train the perceptron with one hundred instances of data or a million, but at the end of the training session, the hyperplane would still be defined by w. A nonparametric model, by contrast, has no fixed number of parameters. The k-NN model is an example. You basically store all the instances of the training data (whether one hundred or one million) and use all the instances when doing the inference about a new piece of data. And therein, unfortunately, lies one of the biggest concerns with the k-NN algorithm. As the size of datasets has exploded, making inferences using k-NN requires increasing amounts of computational power and memory, to the point where it can become mind-numbingly slow and resource-intensive.