A feature-relevance heuristic for indexing and compressing large case bases
Walter M. P. Daelemans, Antal van den Bosch, Jakub Zavrel · 1997
. This paper reports results with igtree, a formalism for indexing and compressing large case bases in Instance-Based Learning (ibl) and other lazy-learning techniques. The concept of information gain (entropy minimisation) is used as a heuristic feature-relevance function for performing the compression of the case base into a tree. igtree reduces storage requirements and the time required to compute classifications considerably for problems where current ibl approaches fail for complexity reasons. Moreover, generalisation accuracy is often similar, for the tasks studied, to that obtained with information-gain-weighted variants of lazy learning, and alternative approaches such as c4.5. Although igtree was designed for a specific class of problems --linguistic disambiguation problems with symbolic (nominal) features, huge case bases, and a complex interaction between (sub)regularities and exceptions-- we show in this paper that the approach has a wider applicability when generalising i...