GeezerVison

In machine learning, instance-based learning (sometimes called memory-based learning^[1]) is a family of learning algorithms that compare new problem instances with instances seen in training, which have been stored in memory. Because computation is postponed until a new instance is observed, these algorithms are sometimes referred to as "lazy."^[2]

It is called instance-based because it constructs hypotheses directly from the training instances themselves.^[3]

An example of an instance-based learning algorithm is the k-nearest neighbors algorithm. It stores (a subset of) its training set; when predicting a value or class for a new instance, it computes distances or similarities between this instance and the training instances to make a decision.^{[2]: ch. 8}

For classification, the k nearest instances can be combined by majority voting or distance-weighted voting; for regression, their target values can be combined by a mean or weighted mean.^{[4]: 128:2–128:3} The choice of distance metric and feature scaling can change which instances are identified as nearest.^[3]

The hypothesis complexity can grow with the data.^[3] In the worst case, a hypothesis is a list of n training items and the computational complexity of classifying a single new instance is O(n) if the cost of comparing two instances is treated as constant.^{[4]: 128:2, 128:10}

Deferring computation makes training inexpensive but shifts computation to prediction time.^{[2]: ch. 8} For a basic k-nearest neighbors classifier using a simple Minkowski distance, exhaustive search over n stored samples described by d features takes O(dn) time. A balanced k-d tree can reduce retrieval time to O(d log n), although this advantage diminishes as the number of features grows.^{[4]: 128:10–128:11}

To reduce the storage required for training instances and sensitivity to noise in the training set, instance reduction algorithms have been proposed.^[5]

• Analogical modeling