Instance-based learning

In machine learning, instance-based learning (sometimes called memory-based learning) 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."

Method

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

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.: 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.: 128:2–128:3  The choice of distance metric and feature scaling can change which instances are identified as nearest.

Computational characteristics

The hypothesis complexity can grow with the data. 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.: 128:2, 128:10 

Deferring computation makes training inexpensive but shifts computation to prediction time.: 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.: 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.

See also

References

  1. ↑ Walter Daelemans; Antal van den Bosch (2005). Memory-Based Language Processing. Cambridge University Press.
  2. 1 2 3 Tom Mitchell (1997). Machine Learning. McGraw-Hill.
  3. 1 2 3 Stuart Russell and Peter Norvig (2003). Artificial Intelligence: A Modern Approach, second edition, pp. 733–735. Prentice Hall. ISBN 0-13-080302-2
  4. 1 2 3 Cunningham, Pádraig; Delany, Sarah Jane (2021). "k-Nearest Neighbour Classifiers—A Tutorial". ACM Computing Surveys. 54 (6). Article 128. arXiv:2004.04523. doi:10.1145/3459665.
  5. ↑ D. Randall Wilson; Tony R. Martinez (2000). "Reduction techniques for instance-based learning algorithms". Machine Learning. 38 (3): 257–286. doi:10.1023/A:1007626913721.