Instance-based learning

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]

Method

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]

Computational characteristics

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]

See also

References

  1. ^ Walter Daelemans; Antal van den Bosch (2005). Memory-Based Language Processing. Cambridge University Press.
  2. ^ a b c Tom Mitchell (1997). Machine Learning. McGraw-Hill.
  3. ^ a b c Stuart Russell and Peter Norvig (2003). Artificial Intelligence: A Modern Approach, second edition, pp. 733–735. Prentice Hall. ISBN 0-13-080302-2
  4. ^ a b c 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.
Stub icon

This machine learning–related article is a stub. You can help Wikipedia by adding missing information.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.