[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/daelemans-1997-igtree-trees-compression-classification-lazy/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / IGTree: Using Trees for Compression and Classification in Lazy Learning Algorithms

# IGTree: Using Trees for Compression and Classification in Lazy Learning Algorithms

**Authors:** Walter Daelemans, [Antal van den Bosch](https://md.mova.elamur.ai/free/en/docs/papers/authors/antal-van-den-bosch/), Ton Weijters · **Year:** 1997 · **Venue:** Artificial Intelligence Review 11 **Link:** unknown **License of the paper:** unknown (publisher copyright)

[**166** citations](https://openalex.org/works?filter=cites:W1586887050) openalex · 2026-10-19[**25** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/daelemans-1997-igtree-trees-compression-classification-lazy/) of the 140673 papers whose bibliographies we read[Artificial Intelligence Review 11, 407–423](https://openalex.org/S122814990)

- [Publisher's page](https://doi.org/10.1023/a:1006506017891)
- [PDF](https://www.clips.uantwerpen.be/~walter/papers/1997/dbw97-2.pdf)
- [DOI 10.1023/a:1006506017891](https://doi.org/10.1023/a:1006506017891)
- [OpenAlex](https://openalex.org/W1586887050)

**Authors (3)**

1. [Walter Daelemans](https://openalex.org/A5083411784) [ORCID](https://orcid.org/0000-0002-9832-7890) · [Semantic Scholar](https://www.semanticscholar.org/author/1735272) · h 55 · 11244 citations · 578 works
2. [Antal van den Bosch](https://openalex.org/A5031562992) [ORCID](https://orcid.org/0000-0003-2493-656X) · [Semantic Scholar](https://www.semanticscholar.org/author/145977875) · h 42 · 7226 citations · 676 works
3. [Ton Weijters](https://openalex.org/A5011157930) h 36 · 12307 citations · 186 works

Citations and author metrics from openalex (2026-10-19); authors with the same name are not always told apart.

## Summary

The paper introduces IGTree, a compressed approximation of memory-based (nearest-neighbour) learning. Features are ordered once by information gain, and the training instances are stored as a decision tree in which every level tests the next most informative feature. Each node keeps its default (most frequent) class, and branches whose class equals their parent's default are pruned, which shrinks memory considerably. Classification walks down the tree as long as feature values match and returns the default class of the last matched node. The authors show that this gives large speed and memory savings over full instance-based search while losing little accuracy on language-processing tasks. IGTree is one of the algorithms of the TiMBL memory-based learning toolkit.

## How Mova uses it

- `prag/src/model.rs` — IGTree is one of three models behind a shared `Classifier` trait in the pragmatics crate, trained on the same features as the perceptron and k-NN.
- Adaptation: feature slots ordered by gain ratio; each node stores a default label and counts; leaves with the parent's label are pruned; prediction walks the tree while values match.
- Transparency: the explanation of a prediction is the path walked through the tree.

## Effectiveness in Mova

Measured in the development notes of `prag` (accuracy / macro-F1, %). Held-out silver test (538 sentences), IGTree vs majority baseline vs averaged perceptron:

- form 88,7 / 55,8 (baseline 77,3 / 12,5; perceptron 94,1 / 70,9)
- act 65,6 / 25,1 (baseline 33,3 / 3,6; perceptron 68,8 / 30,0)
- hedge **98,5 / 84,2** — best of the three models on this field (perceptron 97,4 / 74,3)
- indirect 88,7 / 54,0; polarity 48,9 / 31,1; voice 98,5 / 98,5

5-fold cross-validation (2 986 sentences): form 89,6 / 64,5, act 64,1 / 23,9, indirect 92,2 / 58,2, hedge 98,0 / 75,5, polarity 49,0 / 31,8, voice 97,6 / 97,6. Shuffled-label negative control stays at baseline level. Overall IGTree trails the perceptron except on hedging in the held-out split.

---

👨‍🔬💥

## Cite

The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.1023/a:1006506017891](https://doi.org/10.1023/a:1006506017891)

```
@article{daelemans1997igtree,
  title = {{IGTree: Using Trees for Compression and Classification in Lazy Learning Algorithms}},
  author = {Daelemans, Walter and Bosch, Antal van den and Weijters, Ton},
  journal = {Artificial Intelligence Review 11, 407–423},
  year = {1997},
  doi = {10.1023/a:1006506017891},
  url = {https://doi.org/10.1023/a:1006506017891}
}
```

- [← previous Syntax of referents of relative markers: Evidence from a corpus of learner English](https://md.mova.elamur.ai/free/en/docs/papers/czerniak-2025-syntax-referents-relative-markers-evidence/)
- [next → ICLE-RC: International Corpus of Learner English for Relative Clauses](https://md.mova.elamur.ai/free/en/docs/papers/das-2025-icle-rc-international-corpus-learner/)
- [↑ back to papers](https://md.mova.elamur.ai/free/en/docs/papers/)

## References

24 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Aha, D. W., Kibler, D., & Albert, M. (1991). Instance-based learning algorithms. Machine Learning , 7, 37{66. [find](https://scholar.google.com/scholar?q=Aha%2C+D%2E+W%2E%2C+Kibler%2C+D%2E%2C+%26+Albert%2C+M%2E+%281991%29%2E+Instance%2Dbased+learning+algorithms%2E+Machine+Learning+%2C+7%2C+37%7B66%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/aha-1991-instance-based-learning-algorithms/)
2. Aha, D. W. (1992). Generalizing from case studies: A case study. In Proceedings of the Ninth International Conference on Machine Learning , 1{10. Aberdeen, Scotland: Morgan Kaufmann. [find](https://scholar.google.com/scholar?q=Aha%2C+D%2E+W%2E+%281992%29%2E+Generalizing+from+case+studies%3A+A+case+study%2E+In+Proceedings+of+the+Ninth+International+Conference+on+Machine+Learning+%2C+1%7B10%2E+Aberdeen%2C+Scotland%3A+Morgan+Kaufmann%2E)
3. Cardie, C. (1993). A case-based approach to knowledge acquisition for domain-specic sentence analysis. In AAAI-93 , 798{803. [find](https://scholar.google.com/scholar?q=Cardie%2C+C%2E+%281993%29%2E+A+case%2Dbased+approach+to+knowledge+acquisition+for+domain%2Dspeci%03c+sentence+analysis%2E+In+AAAI%2D93+%2C+798%7B803%2E)
4. Daelemans, W. (1995). Memory-based lexical acquisition and processing. In Steffens, P., editor, Machine Translation and the Lexicon , Lecture Notes in Articial Intelligence 898. Berlin: Springer. [find](https://scholar.google.com/scholar?q=Daelemans%2C+W%2E+%281995%29%2E+Memory%2Dbased+lexical+acquisition+and+processing%2E+In+Steffens%2C+P%2E%2C+editor%2C+Machine+Translation+and+the+Lexicon+%2C+Lecture+Notes+in+Arti%03cial+Intelligence+898%2E+Berlin%3A+Springer%2E)
5. Daelemans, W., Van den Bosch, A. (1992). Generalisation performance of backpropagation learning on a syllabication task. In M. Drossaers & A. Nijholt (Eds.), TWLT3: Connectionism and Natural Language Processing . Enschede: Twente University. [find](https://scholar.google.com/scholar?q=Daelemans%2C+W%2E%2C+Van+den+Bosch%2C+A%2E+%281992%29%2E+Generalisation+performance+of+backpropagation+learning+on+a+syllabi%03cation+task%2E+In+M%2E+Drossaers+%26+A%2E+Nijholt+%28Eds%2E%29%2C+TWLT3%3A+Connectionism+and+Natural+Language)
6. Daelemans, W., Van den Bosch, A. (1994). A language-independent, data-oriented architecture for grapheme-to-phoneme conversion. In Proceedings of ESCA-IEEE Speech Synthesis Conference '94 , New York. [find](https://scholar.google.com/scholar?q=Daelemans%2C+W%2E%2C+Van+den+Bosch%2C+A%2E+%281994%29%2E+A+language%2Dindependent%2C+data%2Doriented+architecture+for+grapheme%2Dto%2Dphoneme+conversion%2E+In+Proceedings+of+ESCA%2DIEEE+Speech+Synthesis+Conference+%2794+%2C+New+York%2E)
7. Deng, K. & Moore, A. W. (1995). Multiresolution Instance-Based Learning. In Proceedings of the Fourteenth International Joint Conference on Artical Intelligence . Montreal: Morgan Kaufmann. [find](https://scholar.google.com/scholar?q=Deng%2C+K%2E+%26+Moore%2C+A%2E+W%2E+%281995%29%2E+Multiresolution+Instance%2DBased+Learning%2E+In+Proceedings+of+the+Fourteenth+International+Joint+Conference+on+Arti%08%08cal+Intelligence+%2E+Montreal%3A+Morgan+Kaufmann%2E)
8. Dougherty, J., Kohavi, R. & Sahami, M. (1995). Supervised and unsupervised discretization of continuous features. In Proceedings of the International Conference on Machine Learning '95 . [find](https://scholar.google.com/scholar?q=Dougherty%2C+J%2E%2C+Kohavi%2C+R%2E+%26+Sahami%2C+M%2E+%281995%29%2E+Supervised+and+unsupervised+discretization+of+continuous+features%2E+In+Proceedings+of+the+International+Conference+on+Machine+Learning+%2795+%2E)
9. Friedman, J., Bentley, J., and Ari Finkel, R. (1977). An algorithm for nding best matches in logarithmic expected time. ACM Transactions on Mathematical Software , 3(3). [find](https://scholar.google.com/scholar?q=Friedman%2C+J%2E%2C+Bentley%2C+J%2E%2C+and+Ari+Finkel%2C+R%2E+%281977%29%2E+An+algorithm+for+%03nding+best+matches+in+logarithmic+expected+time%2E+ACM+Transactions+on+Mathematical+Software+%2C+3%283%29%2E)
10. Kitano, H. (1993). Challenges of massive parallelism. In IJCAI , 813{834. [find](https://scholar.google.com/scholar?q=Kitano%2C+H%2E+%281993%29%2E+Challenges+of+massive+parallelism%2E+In+IJCAI+%2C+813%7B834%2E)
11. Kohavi, R., & Li, C-H. (1995). Oblivious decision trees, graphs, and top-down pruning. Proceedings of the Fourteenth International Joint Conference on Articial Intelligence , 1071{1077. Montreal: Morgan Kaufmann. [find](https://scholar.google.com/scholar?q=Kohavi%2C+R%2E%2C+%26+Li%2C+C%2DH%2E+%281995%29%2E+Oblivious+decision+trees%2C+graphs%2C+and+top%2Ddown+pruning%2E+Proceedings+of+the+Fourteenth+International+Joint+Conference+on+Arti%08cial+Intelligence+%2C+1071%7B1077%2E+Montreal%3A+Mor)
12. Langley, P., & Sage, S. (1994). Oblivious decision trees and abstract cases. In D. W. Aha (Ed.), Case-Based Reasoning: Papers from the 1994 Workshop (Technical Report WS-94-01). Menlo Park, CA: AAAI Press. [find](https://scholar.google.com/scholar?q=Langley%2C+P%2E%2C+%26+Sage%2C+S%2E+%281994%29%2E+Oblivious+decision+trees+and+abstract+cases%2E+In+D%2E+W%2E+Aha+%28Ed%2E%29%2C+Case%2DBased+Reasoning%3A+Papers+from+the+1994+Workshop+%28Technical+Report+WS%2D94%2D01%29%2E+Menlo+Park%2C+CA%3A+AAAI+P)
13. Nunn, A. & van Heuven, V. J. (1993). Morphon, lexicon-based text-to-phoneme conversion and phonological rules. In V. J. van Heuven & L. C. Pols (Eds.), Analysis and Synthesis of Speech: Strategic Research Towards High-Quality Text-to-Speech Generation . Berlin: Mouton de Gruyter. [find](https://scholar.google.com/scholar?q=Nunn%2C+A%2E+%26+van+Heuven%2C+V%2E+J%2E+%281993%29%2E+Morphon%2C+lexicon%2Dbased+text%2Dto%2Dphoneme+conversion+and+phonological+rules%2E+In+V%2E+J%2E+van+Heuven+%26+L%2E+C%2E+Pols+%28Eds%2E%29%2C+Analysis+and+Synthesis+of+Speech%3A+Strategic+Rese)
14. Omohundro, S. M. (1991). Bumptrees for E cient Function, Constraint, and Classi-cation Learning. In R. P. Lippmann, J. E. Moody, and D. S. Touretzky (eds.) Advances in Neural Information Processing Systems 3 . San Mateo, CA: Morgan Kaufmann. [find](https://scholar.google.com/scholar?q=Omohundro%2C+S%2E+M%2E+%281991%29%2E+Bumptrees+for+E+cient+Function%2C+Constraint%2C+and+Classi%2D%03cation+Learning%2E+In+R%2E+P%2E+Lippmann%2C+J%2E+E%2E+Moody%2C+and+D%2E+S%2E+Touretzky+%28eds%2E%29+Advances+in+Neural+Information+Processing+S)
15. Quinlan, J. (1993). C4.5: Programs for Machine Learning . San Mateo, CA: Morgan Kaufmann. [find](https://scholar.google.com/scholar?q=Quinlan%2C+J%2E+%281993%29%2E+C4%2E5%3A+Programs+for+Machine+Learning+%2E+San+Mateo%2C+CA%3A+Morgan+Kaufmann%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/quinlan-1993-c45-programs-machine-learning/)
16. Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986). Learning internal representations by error propagation. In D. E. Rumelhart & J. L. McClelland (Eds.), Parallel Distributed Processing: Explorations in the Microstructure of Cognition , volume 1: Foundations. Cambridge, MA: The MIT Press. [find](https://scholar.google.com/scholar?q=Rumelhart%2C+D%2E+E%2E%2C+Hinton%2C+G%2E+E%2E%2C+%26+Williams%2C+R%2E+J%2E+%281986%29%2E+Learning+internal+representations+by+error+propagation%2E+In+D%2E+E%2E+Rumelhart+%26+J%2E+L%2E+McClelland+%28Eds%2E%29%2C+Parallel+Distributed+Processing%3A+Explor)
17. Sejnowski, T. J., Rosenberg, C. S. (1987). Parallel networks that learn to pronounce English text. Complex Systems , 1, 145{168. [find](https://scholar.google.com/scholar?q=Sejnowski%2C+T%2E+J%2E%2C+Rosenberg%2C+C%2E+S%2E+%281987%29%2E+Parallel+networks+that+learn+to+pronounce+English+text%2E+Complex+Systems+%2C+1%2C+145%7B168%2E)
18. Stanll, C. and Waltz, D. (1986). Toward memory-based reasoning. Communications of the ACM , 29, 1212{1228. [find](https://scholar.google.com/scholar?q=Stan%03ll%2C+C%2E+and+Waltz%2C+D%2E+%281986%29%2E+Toward+memory%2Dbased+reasoning%2E+Communications+of+the+ACM+%2C+29%2C+1212%7B1228%2E)
19. Van den Bosch, A., Daelemans, W. (1993). Data-oriented methods for grapheme-to-phoneme conversion. In Proceedings of the 6th Conference of the EACL , 45{53. Utrecht: OTS. [find](https://scholar.google.com/scholar?q=Van+den+Bosch%2C+A%2E%2C+Daelemans%2C+W%2E+%281993%29%2E+Data%2Doriented+methods+for+grapheme%2Dto%2Dphoneme+conversion%2E+In+Proceedings+of+the+6th+Conference+of+the+EACL+%2C+45%7B53%2E+Utrecht%3A+OTS%2E)
20. Weijters, A., & Hoppenbrouwers, G. (1990). NetSpraak: een neuraal netwerk voor grafeem-foneem-omzetting. Tabu , 20:1, 1-25. [find](https://scholar.google.com/scholar?q=Weijters%2C+A%2E%2C+%26+Hoppenbrouwers%2C+G%2E+%281990%29%2E+NetSpraak%3A+een+neuraal+netwerk+voor+grafeem%2Dfoneem%2Domzetting%2E+Tabu+%2C+20%3A1%2C+1%2D25%2E)
21. Weijters, A. (1991). A simple look-up procedure superior to NETtalk? In Proceedings of the International Conference on Articial Neural Networks , Espoo, Finland. [find](https://scholar.google.com/scholar?q=Weijters%2C+A%2E+%281991%29%2E+A+simple+look%2Dup+procedure+superior+to+NETtalk%3F+In+Proceedings+of+the+International+Conference+on+Arti%08cial+Neural+Networks+%2C+Espoo%2C+Finland%2E)
22. Wess, S., Altho , K. D., and Derwand, G. (1994). Using k-d trees to improve the retrieval step in case-based reasoning. In S. Wess, K. D. Altho , and M. M. Richter (Eds.), Topics in Case-Based Reasoning . Berlin: Springer Verlag. [find](https://scholar.google.com/scholar?q=Wess%2C+S%2E%2C+Altho+%2C+K%2E+D%2E%2C+and+Derwand%2C+G%2E+%281994%29%2E+Using+k%2Dd+trees+to+improve+the+retrieval+step+in+case%2Dbased+reasoning%2E+In+S%2E+Wess%2C+K%2E+D%2E+Altho+%2C+and+M%2E+M%2E+Richter+%28Eds%2E%29%2C+Topics+in+Case%2DBased+Reasoni)
23. Wess, S. (1995). Fallbasiertes Probleml osen in wissensbasierten Systemen zur Entschei-dungsunterst utzung und Diagnostik. Doctoral Dissertation, University of Kaiserslautern. [find](https://scholar.google.com/scholar?q=Wess%2C+S%2E+%281995%29%2E+Fallbasiertes+Probleml+osen+in+wissensbasierten+Systemen+zur+Entschei%2Ddungsunterst+utzung+und+Diagnostik%2E+Doctoral+Dissertation%2C+University+of+Kaiserslautern%2E)
24. Wolpert, D. H. (1990). Constructing a generalizer superior to NETtalk via a mathematical theory of generalization. Neural Networks , 3, 445{452. [find](https://scholar.google.com/scholar?q=Wolpert%2C+D%2E+H%2E+%281990%29%2E+Constructing+a+generalizer+superior+to+NETtalk+via+a+mathematical+theory+of+generalization%2E+Neural+Networks+%2C+3%2C+445%7B452%2E)