AI seminar
Skewing: An Efficient Alternative to Lookahead for Decision Tree Induction
Soumya Ray, University of Wisconsin

Abstract:  In this talk, I present a novel 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.
However, Lookahead 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 I shall present carries only a
O(n) run-time penalty, where n is the example size.  Experiments
indicate that (i) 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, and (ii) the approach scales well with
increasing numbers of variables (example size). I present experiments with
randomly generated Boolean functions, several UCI data sets, and the
task of SH3 domain binding. The results indicate that this algorithm
almost always outperforms an information-gain based decision tree learner.