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
[edit]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
[edit]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
[edit]References
[edit]- ↑ Walter Daelemans; Antal van den Bosch (2005). Memory-Based Language Processing. Cambridge University Press.
- 1 2 3 Tom Mitchell (1997). Machine Learning. McGraw-Hill.
- 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
- 1 2 3 Cunningham, Pádraig; Delany, Sarah Jane (2021). "k-Nearest Neighbour Classifiers—A Tutorial". ACM Computing Surveys. 54 (6). Article 128. doi:10.1145/3459665.
- ↑ 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.
 | This machine learning–related article is a stub. You can help Wikipedia by adding missing information. |