Skewing: An Efficient Alternative to Lookahead for Decision Tree Induction

David Page, Soumya RayIJCAI 2003 · OpenReview

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.

Introduction: The Myopia of Greedy Induction

Top-down induction of decision trees (TDIDT), utilized in algorithms like ID3 and C4.5, typically employs a "greedy" strategy. At each node, the algorithm selects the single variable that provides the highest information gain. While efficient, this approach is fundamentally myopic; it fails to recognize variables that are only informative when considered in combination with others.

A truth table illustrating an XOR-like relationship where individual features (Gender, Sexual Activity) show no information gain in isolation.

This weakness is most apparent in parity functions (such as XOR). In a balanced XOR dataset, knowing the value of a single variable provides zero information about the target. Consequently, a greedy learner may ignore these critical variables in favor of irrelevant "noise" variables that show a slight gain by chance. The traditional solution, lookahead, involves searching combinations of variables, but its computational cost grows exponentially with depth, making it impractical for complex functions.

The Skewing Algorithm

This paper proposes Skewing as a constant-time alternative to lookahead. The core insight is that parity functions only appear invisible to greedy learners under uniform data distributions. By artificially skewing the distribution, these hidden dependencies become visible even to a standard depth-1 search.

The Skewing algorithm operates as follows:

  1. Multiple Trials: The algorithm performs a set number of trials (e.g., $T=30$).
  2. Favored Settings: In each trial, it randomly assigns a "favored" value (0 or 1) to every variable.
  3. Re-weighting: It creates a skewed version of the dataset by boosting the weight of examples that match these favored settings.
  4. Voting: Information gain is calculated for all variables across all trials. A variable is selected if it consistently exceeds a gain threshold across the majority of skewed distributions.

By simulating diverse distributions through re-weighting, the algorithm "forces" logical dependencies to manifest as measurable information gain, turning an exponential search problem into a linear one ($O(T \cdot n)$).

Experimental Results

The effectiveness of Skewing was tested on both synthetic "hard" parity targets and real-world benchmarks from the UCI repository.

Accuracy comparison of ID3 with and without Skewing on hard parity targets involving 3, 4, and 5 variables.

As shown in the results for hard targets, standard ID3 performs no better than random guessing (approximately 50-60% accuracy). In contrast, ID3 with Skewing achieves near 100% accuracy once a sufficient sample size is provided.

Key takeaways include:

  • Real-World Performance: On the Monk-1 problem, which features an XOR-like subfunction, Skewing achieved perfect accuracy, outperforming standard ID3's 92.6%.
  • Computational Efficiency: The runtime penalty is a constant factor. Interestingly, as sample size increases, the relative overhead of skewing decreases because it produces more accurate, shallower trees than the standard greedy approach.
  • Robustness: The authors demonstrated that standard ensemble methods like Boosting or Bagging could not solve these parity problems, proving that Skewing's specific re-weighting strategy is uniquely suited for uncovering logical dependencies.

Conclusion and Limitations

Skewing provides a promising path for decision tree induction to handle complex logical relationships without the ruinous cost of lookahead. While highly effective, the method requires a modest amount of data to distinguish true signals from noise in skewed distributions. Future research will focus on scaling the approach to high-dimensional datasets and continuous variables, where the risk of overfitting to specific skewed points may increase.

Summary updated

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.
BibTeX
@inproceedings{page2003skewing,
  author = {David Page and Soumya Ray},
  title = {{Skewing: An Efficient Alternative to Lookahead for Decision Tree Induction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
  url = {https://openreview.net/forum?id=SyZRDXG_-B},
}
Figure