Instance-Based Learning

Instance-based learning is a family of machine learning methods that, instead of building a general model during training, merely store the examples and defer all computation until a new query arrives. For that deliberate laziness it is also known as lazy learning. Its premise is simple: similar inputs produce similar outputs.

The canonical example: k-nearest neighbors

The emblematic method is k-nearest neighbors (k-NN), which dates back to Cover and Hart (1967). To classify a new case, it finds the k closest stored examples—according to a distance metric, such as the Euclidean—and assigns it the majority class among them; in regression, it averages their values. There is no training as such: all the “intelligence” lies in comparing.

Lazy versus eager

This sets it against eager learning, which does generalize during training by building a model—a decision tree, a neural network—with which it then predicts quickly. The difference lies in when the work is done: the lazy learner trains in an instant but predicts slowly; the eager one invests time in training in order to predict fast afterward. One advantage of the lazy approach is that it adapts to new data without retraining: it is enough to add them to the memory.

Its limits

The price of that simplicity is high. In prediction it is slow, because each query must be compared with many examples, and it consumes memory, because it stores the whole set. It suffers from the curse of dimensionality: with many variables, distances become uniform and the notion of a “nearby neighbor” loses meaning. And it is sensitive to the scale of the features and to irrelevant ones, so it is advisable to normalize the data and choose carefully which variables to use.