Instance-Based Learning Algorithms

David W. AhaDennis KiblerMarc K. Albert

article1991Machine-mediated learning2,043 citations

Introduces incremental instance-based learning algorithms that extend nearest neighbor classification by significantly reducing storage requirements and filtering noisy instances with formal learnability guarantees.

Listen

Instance-based learning algorithms classify new examples solely by comparing them directly to stored training instances rather than deriving rules or decision trees. The paper examines this approach because many supervised learning tasks benefit from retaining specific examples, yet prior work had not systematically analyzed incremental algorithms that rely only on instances while addressing practical issues such as storage growth and noise.

The authors first define a general framework consisting of a similarity function, a classification rule, and an updater that decides which instances to retain. They analyze the simplest version, IB1, which stores every instance and classifies by nearest neighbor, proving that it can learn any concept whose boundary consists of a finite number of closed curves and that the number of instances required grows polynomially with boundary length. They then introduce IB2, which stores only misclassified instances, and IB3, which further applies a statistical significance test to discard likely noisy instances before they influence future predictions. These algorithms were evaluated on six real-world and artificial data sets, including congressional voting records, medical diagnosis collections, and two noisy synthetic domains, with results averaged over repeated random splits and compared against the pruned decision-tree learner C4.

IB2 reduced storage to between 11 % and 71 % of the original training set while maintaining classification accuracy within a few percentage points of IB1 on clean data. IB3 achieved still lower storage (often under 20 %) and, on noisy or imperfectly described domains, produced higher accuracy than both IB1 and IB2, matching or exceeding C4. The performance gap widened as noise increased, because IB3’s filter prevented noisy instances from participating in later decisions. These gains matter for applications that must update models frequently or operate under memory constraints, since instance-based methods incur almost no cost when incorporating a new training example and naturally represent probabilistic concepts through graded similarity.

The results indicate that selective retention of instances can deliver accuracy comparable to more elaborate abstractions while keeping computational overhead low during learning. For deployment, organizations should therefore consider IB3-style filters when data contain noise or when storage and update costs are primary concerns; when concepts are sparse or contain many irrelevant attributes, additional mechanisms for attribute weighting will be needed before reliable decisions can be made. Further controlled trials on larger, higher-dimensional data and integration with indexing structures are the logical next steps to confirm scalability. The main limitations are sensitivity to irrelevant attributes and the assumption that concepts are disjoint; both are acknowledged by the authors and remain open for refinement.

University of California, Irvine classification rules database systems k-nearest neighbors Instance‑Based Learning Nearest Neighbor IB1

Aha et al (1991).pdf

Paper: Induction of Decision Trees, J. R. Quinlan (1986). Reading Quinlan's foundational work on decision tree induction provides essential context on non-incremental classification paradigms before exploring instance-based alternatives.

Paper: Distance Metric Learning for Large Margin Nearest Neighbor Classification, Kilian Q. Weinberger et al. (2005). This paper extends instance-based and nearest-neighbor principles by introducing sophisticated metric learning techniques to optimize classification performance.

Cover for Instance-Based Learning Algorithms

Abstract

Storing and using specific instances improves the performance of several supervised learning algorithms. These include algorithms that learn decision trees, classification rules, and distributed networks. However, no investigation has analyzed algorithms that use only specific instances to solve incremental learning tasks. In this paper, we describe a framework and methodology, called instance-based learning, that generates classification predictions using only specific instances. Instance-based learning algorithms do not maintain a set of abstractions derived from specific instances. This approach extends the nearest neighbor algorithm, which has large storage requirements. We describe how storage requirements can be significantly reduced with, at most, minor sacrifices in learning rate and classification accuracy. While the storage-reducing algorithm performs well on several real-world databases, its performance degrades rapidly with the level of attribute noise in training instances. Therefore, we extended it with a significance test to distinguish noisy instances. This extended algorithm's performance degrades gracefully with increasing noise levels and compares favorably with a noise-tolerant decision tree algorithm.

Topics

classification rules database systems k-nearest neighbors supervised machine learning decision tree classification decision-tree algorithm

Keywords

Instance‑Based Learning Nearest Neighbor IB1 IB2 IB3 Storage Reduction Noise Tolerance Incremental Learning Similarity Function Classification Accuracy

1. Introduction
1.1. History and related work
1.2. Outline of this article
2. Instance-based learning
2.1. Learning task
2.2. Methodology and framework
2.3. Performance dimensions
2.4. The IBI algorithm
2.5. Analysis of the IB1 algorithm
2.5.1. Coverage lemma
2.5.2. Convergence theorems for the IB1 algorithm
2.6. Consequences of the theorems
3. Reducing storage requirements
3.1. Description of the IB2 algorithm
3.2. IB2's behavior on a simple domain
3.3. Empirical studies with IB2
3.3.1. Noise-free databases
3.3.2. Sparse databases
3.3.3. Noisy artificial domains
3.3.4. Learning concepts with imperfect attributes
4. Tolerating noisy instances
4.2. IB3's behavior on a simple domain
4.3. Empirical studies with IB3
4.3.1. Noise-free databases
4.3.2. Sparse databases
4.3.3. Noisy artificial domains
4.3.4. Learning concepts with imperfect attributes
4.4. Generality of the noise-tolerant extension
5. Discussion and summary
5.1. Limitations
5.2. Advantages
5.3. Summary and future directions
Acknowledgments
Notes
References

Knowls

Knowl 1 — IB3 Noise-Tolerant Instance-Based Learning Algorithm
algorithm
The IB3 algorithm is an incremental, noise-tolerant instance-based learning algorithm that maintains a concept description by saving selected instances and filtering them using statistical significance tests based on their classification records.
Input: A sequence of training instances x with associated category labels class(x)
Output: A concept description CD containing saved instances and their classification records
CD = empty_set
for each training instance x do
    for each saved instance y in CD do
        Sim[y] = Similarity(x, y)

    if there exists y in CD such that acceptable(y) is true then
        ymax = an acceptable instance y in CD with maximal Sim[y]
    else
        i = randomly selected integer from [1, |CD|]
        ymax = the i-th most similar instance y in CD to x

    if class(x) == class(ymax) then
        classification = correct
    else
        classification = incorrect
        CD = CD union {x}

    for each instance y in CD with Sim[y] >= Sim[ymax] do
        Update y's classification record (number of correct/incorrect predictions)
        if record of y is significantly poor then
            CD = CD \ {y}
Classification records track the number of correct and incorrect classification attempts for each saved instance when presented with subsequent training instances. An instance is classified as acceptable, mediocre, or significantly poor by comparing confidence intervals for its historical classification accuracy against confidence intervals for its class's observed relative frequency. An acceptance confidence level of 90% ( $z = 1.64$ ) and a dropping confidence level of 75% ( $z = 1.15$ ) are used as hyperparameters.
Knowl 2 — IB3 Significance Test for Instance Acceptance and Removal
model/method
To distinguish reliable exemplar instances from noisy or atypical instances, IB3 maintains a classification history for each stored instance $y$ and computes confidence intervals of proportions for both its classification accuracy and the observed base rate of its category.

Let $p$ be an observed proportion (either the instance's classification accuracy based on $n$ classification attempts, or the category's empirical frequency based on $N$ total processed training instances). The confidence interval bounds are calculated using the normal approximation to the binomial distribution:

$p \pm z \sqrt{\frac{p(1-p)}{n}}$

where $z$ is the critical value for the specified confidence level.

Two criteria govern instance management in the concept description:
1. Acceptance Criterion: An instance is declared acceptable (and thus permitted to make classification predictions) if the lower bound of its accuracy confidence interval (at the 90% confidence level, $z \approx 1.64$ ) is strictly greater than the upper bound of its class's observed frequency confidence interval.
2. Discarding Criterion: An instance is discarded from memory if the upper bound of its accuracy confidence interval (at the 75% confidence level, $z \approx 1.15$ ) is strictly less than the lower bound of its class's observed frequency confidence interval.
If the confidence intervals overlap, the instance remains in a pending status (mediocre) and is not used for primary classification decisions until additional evidence is collected. Comparing instance accuracy against category base rates normalizes the test against skewed class distributions.
Knowl 3 — IB1 Baseline Instance-Based Learning Algorithm
algorithm
The IB1 algorithm is the baseline instance-based classifier. It processes training instances incrementally, normalizes feature ranges continuously, classifies query instances using a 1-nearest-neighbor rule, and stores every presented instance in its concept description.
Input: A stream of training instances x with associated category labels class(x)
Output: A concept description CD containing all stored training instances
CD = empty_set
for each training instance x do
    for each saved instance y in CD do
        Sim[y] = Similarity(x, y)

    if CD is not empty then
        ymax = some y in CD with maximal Sim[y]
        if class(x) == class(ymax) then
            classification = correct
        else
            classification = incorrect

    CD = CD union {x}
For each training instance, the incorporation cost requires computing similarities across all $|CD|$ saved instances over $|A|$ attributes, resulting in an update time complexity of $O(|CD| \cdot |A|)$ .
Knowl 4 — IB2 Storage-Reducing Instance-Based Learning Algorithm
algorithm
The IB2 algorithm reduces memory requirements by saving only training instances that are misclassified by the current concept description under a 1-nearest-neighbor policy.
Input: A stream of training instances x with associated category labels class(x)
Output: A concept description CD containing a boundary-approximating subset of instances
CD = empty_set
for each training instance x do
    for each saved instance y in CD do
        Sim[y] = Similarity(x, y)

    if CD is not empty then
        ymax = some y in CD with maximal Sim[y]
        if class(x) == class(ymax) then
            classification = correct
        else
            classification = incorrect
            CD = CD union {x}
    else
        CD = CD union {x}
Correctly classified instances are assumed to lie within the interior of concept regions (the $\epsilon$ -core) and are discarded without updating the concept description. Misclassified instances are retained because they tend to lie near decision boundaries. While IB2 substantially reduces storage in noise-free domains, its storage and error rate degrade rapidly in noisy domains because noisy instances are almost always misclassified and retained.
Knowl 5 — PAC-Learnability of Concepts with Nice Boundaries by IB1
theoretical result
Let $\mathcal{C}$ be the class of all concepts in the unit hypercube $[0, 1]^n$ whose boundaries consist of a finite union of closed hyper-surfaces of finite total $(n-1)$ -dimensional measure at most $L$ . Let $\mathcal{P}$ be the class of probability distributions on $[0, 1]^n$ whose probability density functions are bounded from above by a constant $B$ .

Then the concept class $\mathcal{C}$ is polynomially learnable from examples with respect to $\mathcal{P}$ using the IB1 algorithm. Specifically, for any error parameter $\epsilon \in (0, 1)$ and confidence parameter $\delta \in (0, 1)$ , if the number of training instances $N$ satisfies

$N > \left( \frac{\lceil 4LB\sqrt{n}/\epsilon \rceil^n}{\epsilon/2} \right) \ln\left( \frac{\lceil 4LB\sqrt{n}/\epsilon \rceil^n}{\delta} \right)$

then, with confidence at least $1 - \delta$ , IB1 produces a hypothesis concept description $C'$ that differs from the target concept $C$ on a set of probability measure less than $\epsilon$ .

The required sample complexity is polynomial in $1/\epsilon$ , $1/\delta$ , $L$ , and $B$ , but exponential in the instance space dimension $n$ .
Knowl 6 — Coverage Lemma and Core-Neighborhood Convergence of Nearest Neighbor
theoretical result
Let $C \subset \mathbb{R}^n$ be a target concept. Define the $\epsilon$ -core of $C$ as the set of points $x \in C$ such that the open ball $B_\epsilon(x) = \{y \in \mathbb{R}^n \mid \text{distance}(x,y) < \epsilon\}$ is entirely contained within $C$ . Define the $\epsilon$ -neighborhood of $C$ as the set of points within distance $\epsilon$ of some point in $C$ .

Coverage Lemma: Let $\epsilon, \delta, \gamma \in (0, 1)$ . A random sample $S$ of size

$N > \left( \frac{\lceil \sqrt{n}/\epsilon \rceil^n}{\gamma} \right) \ln\left( \frac{\lceil \sqrt{n}/\epsilon \rceil^n}{\delta} \right)$

drawn from a bounded domain in $\mathbb{R}^n$ according to any fixed probability distribution forms an $(\epsilon, \gamma)$ -net with confidence greater than $1 - \delta$ .

Convergence Theorem: If $S$ forms an $(\epsilon, \gamma)$ -net, then the concept description $C'$ generated by the 1-nearest-neighbor rule (IB1) satisfies:

$(\epsilon\text{-core}(C) \setminus G) \subseteq (C' \setminus G) \subseteq (\epsilon\text{-neighborhood}(C) \setminus G)$

with confidence at least $1 - \delta$ , where $G$ is an exceptional set with probability measure strictly less than $\gamma$ .
Knowl 7 — Instance-Based Similarity Function and Missing Value Handling
equation
The similarity between two instances $x = \langle x_1, \dots, x_n \rangle$ and $y = \langle y_1, \dots, y_n \rangle$ defined over $n$ attributes is defined as the negative Euclidean distance:

$\text{Similarity}(x, y) = -\sqrt{\sum_{i=1}^n f(x_i, y_i)}$

where attribute differences $f(x_i, y_i)$ are computed as follows:
1. For continuous numeric attributes (dynamically normalized to the interval $[0, 1]$ based on observed extrema): $f(x_i, y_i) = (x_i - y_i)^2$
2. For Boolean and symbolic (nominal) attributes: $f(x_i, y_i) = \begin{cases} 0 & \text{if } x_i = y_i \\ 1 & \text{if } x_i \neq y_i \end{cases}$
3. For missing attribute values, maximal difference is assumed: $f(x_i, y_i) = 1 \quad \text{if } x_i \text{ is missing or } y_i \text{ is missing (or both)}$

Knowl 8 — Empirical Classification Accuracy and Storage Requirements of IB1, IB2, IB3, and C4

data/table

The empirical performance of IB1, IB2, IB3, and the pruned decision-tree induction algorithm C4 was evaluated across six benchmark datasets using 50 independent trials with disjoint training and testing sets.

Database	IB1 (Acc % / Stor %)	IB2 (Acc % / Stor %)	IB3 (Acc % / Stor %)	C4 (Acc %)
Voting	91.8 $\pm$ 0.4 / 100.0	90.9 $\pm$ 0.5 / 11.1	91.6 $\pm$ 0.5 / 7.4	95.5 $\pm$ 0.3
Primary Tumor	34.7 $\pm$ 0.8 / 100.0	32.9 $\pm$ 0.8 / 71.3	38.6 $\pm$ 0.9 / 16.4	37.8 $\pm$ 0.9
LED Display	70.5 $\pm$ 0.4 / 100.0	62.4 $\pm$ 0.6 / 41.5	71.7 $\pm$ 0.4 / 28.7	68.3 $\pm$ 0.3
Waveform	75.2 $\pm$ 0.3 / 100.0	69.6 $\pm$ 0.4 / 32.5	73.8 $\pm$ 0.4 / 14.6	70.7 $\pm$ 0.3
Cleveland Heart	75.7 $\pm$ 0.8 / 100.0	71.4 $\pm$ 0.8 / 30.4	78.0 $\pm$ 0.8 / 7.7	75.5 $\pm$ 0.7
Hungarian Heart	58.7 $\pm$ 1.5 / 100.0	55.9 $\pm$ 2.0 / 36.0	80.5 $\pm$ 0.9 / 7.5	78.2 $\pm$ 0.9

The results demonstrate that:

IB2 reduces storage requirements relative to IB1 (saving 11.1% to 71.3% of instances) but suffers significant accuracy degradation in noisy domains (e.g., LED Display, Waveform, Hungarian Heart).
IB3 matches or exceeds the classification accuracy of IB1 across all datasets while requiring dramatically less storage (retaining only 7.4% to 28.7% of instances).
In noisy, non-axis-aligned numeric domains (LED Display, Waveform, Cleveland, and Hungarian Heart), IB3 outperforms the pruned decision tree algorithm C4, whereas C4 excels on axis-aligned, linearly separable domains (Voting).

Knowl 9 — Piecewise-Linear Inductive Bias and Incremental Update Complexity of IBL
model/method
Instance-based learning algorithms possess a flexible, piecewise-linear inductive bias defined implicitly by the Voronoi tessellation generated by stored exemplars. Unlike univariate decision tree algorithms (such as C4) that partition instance space into axis-orthogonal hyper-rectangles, instance-based boundaries consist of hyper-planes situated midway between neighboring stored instances of opposing classes.

This inductive bias enables IBL algorithms to learn concepts whose decision boundaries are diagonal or non-orthogonal to attribute axes without requiring expensive multi-attribute test generation. Computationally, updating an instance-based concept description upon encountering a new training instance requires only $O(|CD| \cdot |A|)$ attribute comparisons (where $|CD|$ is the number of stored instances and $|A|$ is the number of attributes), compared to $O(|I| \cdot |A|^2)$ operations required by batch decision tree reconstruction from a dataset of size $|I|$ .
Knowl 10 — Sensitivity of Instance-Based Learning to Irrelevant Attributes
limitation
The standard distance metrics in IB1, IB2, and IB3 assign equal weight to all attributes. Consequently, as the number of irrelevant attributes increases, the instance space dimensionality increases and Euclidean distance becomes dominated by non-informative dimensions.

Under unweighted metrics, the storage requirement of instance-based classifiers increases exponentially with the number of irrelevant attributes, while the learning rate and classification accuracy decrease exponentially. To maintain robust performance in the presence of irrelevant dimensions, instance-based representations require extensions that dynamically learn feature weights and adjust attribute salience in the similarity function.

Coverage note — None omitted; all primary algorithm definitions (IB1, IB2, IB3), theoretical PAC-learning bounds, statistical significance filtering mechanics, empirical benchmark comparisons, and analyzed inductive bias/limitations are included.

References

1.Aha, D.W. (1989a). Incremental, instance-based learning of independent and graded concept descriptions. Proceedings of the Sixth International Workshop on Machine Learning (pp. 387-391). Ithaca, NY: Morgan Kaufmann.
2.Aha, D.W. (1989b). Incremental learning of independent, overlapping, and graded concepts with an instance-based process framework (Technical Report 89-10). Irvine, CA: University of California, Irvine, Department of Information and Computer Science.
3.Aha, D.W. (1989c). Tolerating noise, irrelevant attributes, and novel attributes in instance-based learning algorithms. Proceedings of the IJCAI-1989 Workshop on Symbolic Problem Solving in Noisy, Novel, and Uncertain Task Environments. Detroit, MI: Computing Research Laboratory, New Mexico State University.
4.Aha, D.W., & Kibler, D. (1989). Noise-tolerant instance-based learning algorithms. Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (pp. 794-799). Detroit, MI: Morgan Kaufmann.
5.Bareiss, E.R., Porter, B., & Wier, C.C. (1987). PROTOS: An exemplar-based learning apprentice. Proceedings of the Fourth International Workshop on Machine Learning (pp. 12-23). Irvine, CA: Morgan Kaufmann.
6.Barsalou, L.W. (1983). Ad hoc categories. Memory and Cognition, 11, 211-227.
7.Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. (1986). Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension. Proceedings of the Eighteenth Annual Association for Computing Machinery Symposium on Theory of Computing (pp. 273-282). Berkeley, CA: Association for Computing Machinery.
8.Breiman, L., Friedman, J.H., Olshen, R.A., & Stone, C.J. (1984). Classification and regression trees. Belmont, CA: Wadsworth International Group.
9.Bradshaw, G. (1987). Learning about speech sounds: The NEXUS project. Proceedings of the Fourth International Workshop on Machine Learning (pp. 1-11). Irvine, CA: Morgan Kaufmann.
10.Brooks, L. (1978). Nonanalytic concept formation and memory for instances. In E. Rosch & B.B. Lloyd (Eds.), Cognition and categorization. Hillsdale, NJ: Lawrence Erlbaum Associates.
11.Brooks, L. (1989). Concept formation and particularizing learning. In S. Hanson & R. Davis (Eds.), Information, language, & cognition: Vancouver studies in cognitive science (Vol. 1). Vancouver, B.C.: UBC Press.
12.Cestnik, B., Kononenko, I., & Bratko, I. (1987). ASSISTANT-86: A knowledge-elicitation tool for sophisticated users. In I. Bratko & N. Lavrac (Eds.), Progress in machine learning. Bled, Yugoslavia: Sigma Press.
13.Clark, P.E. (1989). Exemplar-based reasoning in geological prospect appraisal (Technical Report 89-034). Glasgow, Scotland: Turing Institute.
14.Clark, P.E., & Niblett, T. (1989). The CN2 induction algorithm. Machine Learning, 3, 261-284.
15.Cover, T.M., & Hart, P.E. (1967). Nearest neighbor pattern classification. Institute of Electrical and Electronics Engineers Transactions on Information Theory, 13, 21-27.
16.Dasarathy, B.V. (1980). Nosing around the neighborhood: A new system structure and classification rule for recognition in partially exposed environments. Pattern Analysis and Machine Intelligence, 2, 67-71.
17.Detrano, R., M.D. (1988). International application of a new probability algorithm for the diagnosis of coronary artery disease. Unpublished manuscript.
18.Dietterich, T.G., & Michalski, R.S. (1983). A comparative review of selected methods for learning from examples. In R.S. Michalski, J.G. Carbonell, & T.M. Mitchell (Eds.), Machine learning: An artificial intelligence approach. San Mateo, CA: Morgan Kaufmann.
19.Fisher, D.H. (1989). Noise-tolerant concept clustering. Proceedings of the Eleventh International Conference on Artificial Intelligence (pp. 825-830). Detroit, MI: Morgan Kaufmann.
20.Gates, G.W. (1972). The reduced nearest neighbor rule. IEEE Transactions on Information Theory, 431-433.
21.Hart, P.E. (1968). The condensed nearest neighbor rule. Institute of Electrical and Electronics Engineers and Transactions on Information Theory, 14, 515-516.
22.Hintzman, D.L. (1986). "Schema abstraction" in a multiple-trace memory model. Psychological Review, 93, 411-428.
23.Hogg, R.V., & Tanis, E.A. (1983). Probability and statistical inference. New York, NY: Macmillan.
24.Jabbour, K., Riveros, J.F.V., Landsbergen, D., & Meyer, W. (1987). ALFA: Automated load forecasting assistant. Proceedings of the 1987 IEEE Power Engineering Society Summer Meeting. San Francisco, CA.
25.Kibler, D., & Aha, D.W. (1988). Case-based classification. Proceedings of the Case-Based Reasoning Workshop at AAAI 1988 (pp. 62-67). Unpublished manuscript.
26.Kibler, D., & Aha, D.W. (1989). Comparing instance-saving with instance-averaging learning algorithms. In D.P. Benjamin (Ed.), Change of representation and inductive bias. Norwell, MA: Kluwer Academic Publishers.
27.Kibler, D., Aha, D.W., & Albert, M. (1989). Instance-based prediction of real-valued attributes. Computational Intelligence, 5, 51-57.
28.Koton, P. (1988). Reasoning about evidence in causal explanations. Proceedings of the Seventh National Conference on Artificial Intelligence (pp. 256-261). St. Paul, MN: Morgan Kaufmann.
29.Markovitch, S., & Scott, P.D. (1989). Information filters and their implementation in the SYLLOG system. Proceedings of the Sixth International Workshop on Machine Learning (pp. 404-407). Ithaca, NY: Morgan Kaufmann.
30.Medin, D.L., & Schaffer, M.M. (1978). Context theory of classification learning. Psychological Review, 85, 207-238.
31.Michalski, R.S., & Larson, J.B. (1978). Selection of most representative training examples and incremental generation of VL1 hypotheses: The underlying methodology and the description of programs ESEL and AQ11 (Technical Report 867). Urbana, IL: University of Illinois, Department of Computer Science.
32.Michalski, R.S., Mozetic, I., Hong, J., & Lavrač, N. (1986). The multi-purpose incremental learning system AQ15 and its testing application to three medical domains. Proceedings of the Fifth National Conference on Artificial Intelligence (pp. 1041-1045). Philadelphia, PA: Morgan Kaufmann.
33.Michie, D., Muggleton, S., Riese, C., & Zubrick, S. (1984). Rulemaster: A second-generation knowledge-engineering facility. 1984 Conference on Artificial Intelligence and Applications.
34.Nosofsky, R.M. (1986). Attention, similarity, and the identification-categorization relationship. Journal of Experimental Psychology: General, 15, 39-57.
35.Quinlan, J.R. (1986). Induction of decision trees. Machine Learning, 1, 81-106.
36.Quinlan, J.R. (1987). Generating production rules from decision trees. Proceedings of the Tenth International Joint Conference on Artificial Intelligence (pp. 304-307). Milan, Italy: Morgan Kaufmann.
37.Quinlan, J.R. (1988). An empirical comparison of genetic and decision-tree classifiers. Proceedings of the Fifth International Conference on Machine Learning (pp. 135-141). Ann Arbor, MI: Morgan Kaufmann.
38.Quinlan, J.R., Compton, P.J., Horn, K.A., & Lazurus, L. (1986). Inductive knowledge acquisition: A case study. Proceedings of the Second Australian Conference on Applications of Expert Systems. Sydney, Australia.
39.Rendell, L. (1988). Learning hard concepts. Proceedings of the Third European Working Session on Learning (pp. 177-200). Glasgow, Scotland: Pitman Publishing.
40.Rissland, E.L., Kolodner, J., & Waltz, D. (1989). Case-based reasoning from DARPA: Machine learning program plan. Proceedings of the Case-Based Reasoning Workshop (pp. 1-13). Pensecola Beach, FL: Morgan Kaufmann.
41.Rosenblatt, F. (1962). Principles of neurodynamics. New York, NY: Spartan.
42.Rumelhart, D.E., McClelland, J.L., & The PDP Research Group (Eds.) (1987). Parallel distributed processing: Explorations in the microstructure of cognition (Vol. 1). Cambridge, MA: MIT Press.
43.Shamos, M.I., & Hoey, D. (1975). Closest point problems. Proceedings of the Sixteenth Annual Institute of Electrical and Electronic Engineers Symposium on the Foundations of Computer Science (pp. 151-162. IEEE Computer Society.
44.Salzberg, S. (1988). Exemplar-based learning: Theory and implementation (Technical Report TR-10-88). Cambridge, MA: Harvard University, Center for Research in Computing Technology.
45.Schlimmer, J.C., & Fisher, D. (1986). A case study of incremental concept induction. Proceedings of the Fifth National Conference on Artificial Intelligence (pp. 496-501). Philadelphia, PA: Morgan Kaufmann.
46.Smith, E.E., & Medin, D.L. (1981). Categories and concepts. Cambridge, MA: Harvard University Press.
47.Stanfill, C., & Waltz, D. (1986). Toward memory-based reasoning. Communications of the ACM, 29, 1213-1228.
48.Utgoff, P.E. (1989). Incremental induction of decision trees. Machine Learning, 4, 161-186.
49.Valiant, L.G. (1984). A theory of the learnable. Communications of the Association for Computing Machinery, 27, 1134-1142.
50.Van de Velde, W. (1989). IDL, or taming the multiplexer. Proceedings of the Fourth European Working Session on Learning (pp. 211-225). Montpellier, France: Morgan Kaufmann.
51.Volper, D.J., & Hampson, S.E. (1987). Learning and using specific instances. Biological Cybernetics, 57, 57-71.

Citation

MLA

Aha, D. W., et al. “Instance-Based Learning Algorithms”. Machine Learning, vol. 6, no. 1, 1991, pp. 37–66, https://doi.org/10.1023/A:1022689900470.

APA

Aha, D. W., Kibler, D., & Albert, M. K. (1991). Instance-Based Learning Algorithms. Machine Learning, 6(1), 37–66. https://doi.org/10.1023/A:1022689900470

Chicago

Aha, D. W., D. Kibler, and M. K. Albert. 1991. “Instance-Based Learning Algorithms”. Machine Learning 6 (1): 37–66. https://doi.org/10.1023/A:1022689900470.

Harvard

Aha, D.W., Kibler, D. and Albert, M.K. (1991) “Instance-Based Learning Algorithms”, Machine Learning, 6(1), pp. 37–66. Available at: https://doi.org/10.1023/A:1022689900470.

Vancouver

1. Aha DW, Kibler D, Albert MK (1991) Instance-Based Learning Algorithms. Machine Learning 6:37–66

BibTeX

@article{Aha_1991, title={Instance-Based Learning Algorithms}, volume={6}, ISSN={1573-0565}, url={http://dx.doi.org/10.1023/A:1022689900470}, DOI={10.1023/a:1022689900470}, number={1}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Aha, David W. and Kibler, Dennis and Albert, Marc K.}, year={1991}, month=Jan, pages={37–66} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Instance-Based Learning Algorithms

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — IB3 Noise-Tolerant Instance-Based Learning Algorithm

Knowl 2 — IB3 Significance Test for Instance Acceptance and Removal

Knowl 3 — IB1 Baseline Instance-Based Learning Algorithm

Knowl 4 — IB2 Storage-Reducing Instance-Based Learning Algorithm

Knowl 5 — PAC-Learnability of Concepts with Nice Boundaries by IB1

Knowl 6 — Coverage Lemma and Core-Neighborhood Convergence of Nearest Neighbor

Knowl 7 — Instance-Based Similarity Function and Missing Value Handling

Knowl 8 — Empirical Classification Accuracy and Storage Requirements of IB1, IB2, IB3, and C4

Knowl 9 — Piecewise-Linear Inductive Bias and Incremental Update Complexity of IBL

Knowl 10 — Sensitivity of Instance-Based Learning to Irrelevant Attributes

References

Citation

BibTeX

Access the Paper