--- title: "Instance-Based Learning Algorithms — Aha 1991" description: "The paper frames nearest-neighbour classification as a family of incremental \"instance-based\" learners that keep stored examples… Cited by 73 papers here." authors: ["David W. Aha", "Dennis Kibler", "Marc K. Albert"] year: 1991 venue: "Machine Learning 6(1), 37–66" source: "https://doi.org/10.1007/bf00153759" doi: "10.1007/bf00153759" licence: "Not open access (publisher copyright) — card only, no text (Machine Learning, Kluwer/Springer)" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/aha-1991-instance-based-learning-algorithms/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/aha-1991-instance-based-learning-algorithms/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1991](https://md.research.elamur.ai/free/en/papers/1991/) / Instance-Based Learning Algorithms # Instance-Based Learning Algorithms **Authors:** David W. Aha, Dennis Kibler and Marc K. Albert · **Year:** 1991 · **Venue:** Machine Learning 6(1) **Link:** [doi.org/10.1007/BF00153759](https://doi.org/10.1007/BF00153759) (DOI [10.1007/BF00153759](https://doi.org/10.1007/BF00153759)) **License of the paper:** unknown (publisher copyright) [**5,175** citations](https://openalex.org/works?filter=cites:W2147169507) OpenAlex, 2026-10-14 · [**73** citations in our library](https://md.research.elamur.ai/free/en/papers/aha-1991-instance-based-learning-algorithms/cited-by/) of the 140,884 papers whose bibliographies we read · [Machine Learning 6(1), 37–66](https://md.research.elamur.ai/free/en/venues/machine-learning/) · published by [Springer Science+Business Media](https://md.research.elamur.ai/free/en/publishers/springer-science-business-media/) - [Publisher's page](https://doi.org/10.1007/bf00153759) - [PDF](https://link.springer.com/content/pdf/10.1007/BF00153759.pdf) - [DOI 10.1007/bf00153759](https://doi.org/10.1007/bf00153759) - [OpenAlex](https://openalex.org/W2147169507) **Authors (3)** 1. [David W. Aha](https://openalex.org/A5063806691) [Semantic Scholar](https://www.semanticscholar.org/author/1969847) · h 45 · 14,899 citations · 330 works 2. [Dennis Kibler](https://openalex.org/A5051278868) [Semantic Scholar](https://www.semanticscholar.org/author/2787844) · h 24 · 8,221 citations · 98 works 3. [Marc K. Albert](https://openalex.org/A5111546666) [Semantic Scholar](https://www.semanticscholar.org/author/145232424) · h 12 · 5,707 citations · 37 works Citations and author metrics: OpenAlex, 2026-10-14; authors with the same name are not always told apart. ## Summary The paper frames nearest-neighbour classification as a family of incremental "instance-based" learners that keep stored examples instead of building an abstract model. The baseline, IB1, stores every training instance and classifies a new case by the label of its most similar stored instances under a simple distance. Follow-up variants reduce storage by keeping only instances that were misclassified (IB2) and add a significance test to discard noisy instances (IB3). The authors analyse the trade-offs between storage, noise tolerance and accuracy and compare the algorithms with decision-tree learners on standard benchmark datasets. The main message is that a lazy, memory-based learner can be competitive while staying very simple and making each decision traceable to concrete stored examples. ## How Mova uses it - `prag/src/model.rs` — the k-NN / IB1 classifier, one of three models behind a shared `Classifier` trait in the pragmatics crate (sentence form, speech act, indirectness, hedging, polarity, voice). - Adaptation, following the TiMBL tradition: the whole training memory is kept, distance is feature overlap weighted by gain ratio, and the k nearest distance levels vote; k is chosen by leave-one-out on the training data (form 3, act 5, indirect 11, hedge 3, polarity 11, voice 7). - Transparency: the explanation for a prediction is the list of most similar remembered sentences carrying the same label. ## Effectiveness in Mova Measured in the development notes of `prag` (accuracy / macro-F1, %). Held-out silver test (538 sentences), k-NN vs majority baseline vs averaged perceptron: - form 91,6 / 63,5 (baseline 77,3 / 12,5; perceptron 94,1 / 70,9) - act 67,5 / 29,4 (baseline 33,3 / 3,6; perceptron 68,8 / 30,0) - indirect 90,1 / 52,5; hedge 98,0 / 77,5; polarity 53,5 / 37,5; voice 98,9 / 98,9 5-fold cross-validation on all silver data (2,986 sentences): form 92,5 / 68,4, act 68,1 / 26,0, indirect 92,5 / 53,9, hedge 97,8 / 73,4, polarity 54,3 / 38,9, voice 98,2 / 98,2. The negative control (same model on shuffled labels) stays at baseline level (e.g. form 77,0 / 12,4). k-NN is close to, but generally below, the perceptron; its value in Mova is example-based explanations. ## Institutions [🎓**University of California, Irvine** Irvine · United States 22 works · 35,120 citations](https://md.research.elamur.ai/free/en/universities/university-of-california-irvine/) 📚 Shelves 3[Computer Science · 7,349 works](https://md.research.elamur.ai/free/en/shelves/computer-science/) · [Artificial Intelligence · 7,183 works](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · [Information Systems · 402 works](https://md.research.elamur.ai/free/en/shelves/computer-science/information-systems/) ## Appears in Articles of ours that cite this paper. Agglomerations[Los Angeles](https://md.research.elamur.ai/free/en/agglomerations/los-angeles/) ## Cite Cite as David W. Aha, Dennis Kibler and Marc K. Albert. 1991. Instance-Based Learning Algorithms. Machine Learning 6(1), 37–66. The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.1007/bf00153759](https://doi.org/10.1007/bf00153759) ```bibtex @inproceedings{aha1991instance, title = {{Instance-Based Learning Algorithms}}, author = {David W. Aha, Dennis Kibler and Marc K. Albert}, booktitle = {Machine Learning 6(1), 37–66}, year = {1991}, doi = {10.1007/bf00153759}, url = {https://doi.org/10.1007/bf00153759} } ``` - [next → Lexical Cohesion Computed by Thesaural relations as an indicator of the structure of text](https://md.research.elamur.ai/free/en/papers/morris-1991-lexical-cohesion-computed-thesaural-relations/) - [↑ back to papers of 1991](https://md.research.elamur.ai/free/en/papers/1991/) Updated 23 October 2026