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

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

@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}
}

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 our card
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
3. Cardie, C. (1993). A case-based approach to knowledge acquisition for domain-specic sentence analysis. In AAAI-93 , 798{803. find
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
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
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
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
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
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
10. Kitano, H. (1993). Challenges of massive parallelism. In IJCAI , 813{834. find
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
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
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
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
15. Quinlan, J. (1993). C4.5: Programs for Machine Learning . San Mateo, CA: Morgan Kaufmann. find our card
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
17. Sejnowski, T. J., Rosenberg, C. S. (1987). Parallel networks that learn to pronounce English text. Complex Systems , 1, 145{168. find
18. Stanll, C. and Waltz, D. (1986). Toward memory-based reasoning. Communications of the ACM , 29, 1212{1228. find
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
20. Weijters, A., & Hoppenbrouwers, G. (1990). NetSpraak: een neuraal netwerk voor grafeem-foneem-omzetting. Tabu , 20:1, 1-25. find
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
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
23. Wess, S. (1995). Fallbasiertes Probleml osen in wissensbasierten Systemen zur Entschei-dungsunterst utzung und Diagnostik. Doctoral Dissertation, University of Kaiserslautern. find
24. Wolpert, D. H. (1990). Constructing a generalizer superior to NETtalk via a mathematical theory of generalization. Neural Networks , 3, 445{452. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/daelemans-1997-igtree-trees-compression-classification-lazy/