Instance-based learning, also called memory-based learning, is a family of machine learning algorithms that make predictions by comparing new problem instances with previously seen training instances stored in memory. Because computation is postponed until a new instance is observed, these algorithms are sometimes referred to as 'lazy.' This contrasts with eager learning methods, which build a generalized model during training and then discard the raw data.
The approach is called instance-based because it constructs hypotheses directly from the training instances themselves, rather than deriving a separate function or rule set. It is a core technique in fields such as pattern recognition and data mining, and it underpins many practical systems where training data is abundant but model interpretability is less critical.
Method
An example of an instance-based learning algorithm is the k-nearest neighbors (k-NN) 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. 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.
The choice of distance metric and feature scaling can change which instances are identified as nearest. Common metrics include Euclidean distance, Manhattan distance, and Minkowski distance, which generalizes both. Feature scaling, such as normalization or standardization, ensures that dimensions with larger ranges do not dominate the distance calculation. Other instance-based methods include locally weighted regression, case-based reasoning, and curriculum learning variants that organize training examples by difficulty.
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. Deferring computation makes training inexpensive but shifts computation to prediction time.
For a basic k-NN 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. In high-dimensional spaces, the 'curse of dimensionality' can degrade performance, as distances become less discriminative. To reduce the storage required for training instances and sensitivity to noise in the training set, instance reduction algorithms have been proposed, such as condensed nearest neighbor and edited nearest neighbor, which remove redundant or noisy points.
Applications and Variants
Instance-based learning is widely used in recommendation systems, medical diagnosis, and anomaly detection. In artificial intelligence applications, it serves as a baseline for evaluating more complex models like deep learning networks. Variants include weighted k-NN, where closer neighbors have greater influence, and prototype-based methods that cluster training data into representative exemplars. For large-scale datasets, approximate nearest neighbor search techniques, such as locality-sensitive hashing, are often employed to speed up retrieval.
Relationship to Other Learning Paradigms
Unlike neural networks or transformers used in modern large language models, instance-based methods do not require iterative optimization over parameters. They are non-parametric, meaning the model complexity grows with the number of training instances. This makes them easy to update with new data, but memory-intensive for massive datasets. In contrast, eager learning methods like residual networks or U-Net architectures compress information into fixed-size parameters, enabling faster inference at the cost of retraining for updates.
Limitations and Extensions
A key limitation is the computational cost at prediction time, especially with high-dimensional data. Instance reduction and indexing structures mitigate this but introduce overhead. Sensitivity to irrelevant features and noise can be addressed through feature weighting or distance metric learning. Extensions like data augmentation can generate synthetic instances to improve robustness. In practice, instance-based learning remains a valuable tool for small to medium-sized datasets and for problems where interpretability and incremental learning are priorities.