When: Thursday, July 31
Time: 3:30pm
Where: 2310 CS
Speaker: Prof. David Page

Title: Skewing: An Efficient Alternative to Lookahead for Decision Tree Induction

Joint work with Soumya Ray.  This is a practice talk for the International
Joint Conference on Artificial Intelligence (IJCAI-03).

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 other (irrelevant) variables as well.  Future
work focuses on extending the approach so that it handles continuous
features and performs well in the presence of more (hundreds or thousands
of) irrelevant variables.