Proceedings

Skewing: An Efficient Alternative to Lookahead for Decision Tree Induction

C. David Page Jr., Soumya Ray

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 601-611.

Abstract

This paper presents a novel, promising approach that allows greedy decision tree induction algorithms to handle problematic functions such as parity functions. Lookahead is the standard approach to addressing difficult functions for greedy decision tree learners. Nevertheless, this approach is limited to very small problematic functions or subfunctions (2 or 3 variables), because the time complexity grows more than exponentially with the depth of lookahead. In contrast, the approach presented in this paper carries only a constant run-time penalty. Experiments indicate that the approach is effective with only modest amounts of data for problematic functions or subfunctions of up to six or seven variables, where the examples themselves may contain numerous other (irrelevant) variables as well.

C. David Page Jr., and Soumya Ray. 2003. Skewing: An Efficient Alternative to Lookahead for Decision Tree Induction. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 601–611. https://ijcai.org/proceedings/2003/89
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards