Lookahead and Pathology in Decision Tree Induction

TL;DR

This paper investigates whether adding "lookahead" (considering future splits) to greedy decision tree algorithms improves tree accuracy and size. Empirically, they found that one-level lookahead offers no significant advantage and can even lead to worse trees ("pathology"), while simpler post-processing techniques like pruning are more effective.

What Problem Does This Paper Address?

Decision tree induction algorithms typically use a greedy, top-down approach. At each node, they make a locally optimal decision about the best split based on a heuristic (like information gain or Gini index) without considering how this choice might affect future splits or the overall tree structure. This can lead to suboptimal trees in terms of size and accuracy. While "lookahead" (considering multiple future splits) is a common technique in other areas like game playing, its benefits and drawbacks in decision tree induction are not well-quantified. This paper aims to empirically assess whether one-level lookahead offers a worthwhile improvement over the standard greedy approach.

Methods

The authors compare two main algorithmic strategies:

  • Greedy: The standard approach where each node's split is chosen based solely on local information (e.g., maximizing information gain or minimizing Gini index).
  • Lookahead: An extension where the algorithm considers the best possible split at the current node, then simulates the greedy algorithm for one level deeper on the resulting child nodes, and finally chooses the current split that leads to the best overall outcome after this one-level lookahead.

They implemented four specific algorithms by combining these strategies with two common "goodness measures": Greedy-Gini, Greedy-Info, Look-Gini, and Look-Info. They also experimented with pruning as a post-processing technique.

Datasets

The paper uses two types of datasets:

  • Synthetic Data:
    • Class C: A set of 5,844 balanced binary decision trees with three internal nodes. This class was designed such that one-level lookahead is equivalent to exhaustive search, allowing for a direct comparison of greedy vs. optimal.
  • Class Cs: A slightly larger class of trees derived from Class C, with four internal nodes. Here, one-level lookahead is not equivalent to exhaustive search, providing a more realistic scenario.
  • Real-World Data: Eight datasets from the UCI Machine Learning Repository were used, including "difficult" domains known to be challenging for simple classification rules (e.g., breast cancer recurrence, heart disease, glass identification).

Key Insights and Ideas

  • Pathology is Real: The most striking finding is the phenomenon of "pathology," where the more expensive lookahead search actually produces worse trees (less accurate, larger, or deeper) than the simpler greedy approach. This is analogous to pathology observed in game tree search.
  • Lookahead Doesn't Buy Much Accuracy: For both synthetic and real-world data, one-level lookahead provided negligible improvements in classification accuracy compared to greedy induction.
  • Pruning is King: Post-processing techniques like cost-complexity pruning were found to be significantly more effective and much cheaper than lookahead for improving tree quality (accuracy and size).
  • Greedy is Surprisingly Good: The standard greedy approach, despite its local optimization, often produces trees that are nearly as good as those found by more complex methods, especially when combined with pruning.
  • Balancing Matters: While lookahead sometimes produced shallower trees, this was often due to better balancing. The authors propose a simple tree balancing technique (using rotations) as a more efficient way to achieve this benefit.

Key Results

  • Synthetic Data (Class C): Greedy algorithms produced trees with accuracy and size comparable to lookahead (which was equivalent to exhaustive search here). The main difference was in maximum depth, where greedy trees were slightly deeper.
  • Synthetic Data (Class Cs): Lookahead showed no significant improvement in accuracy or size, and only a marginal reduction in depth. Pathology was observed where lookahead hurt performance.
  • Real-World Data:
    • Accuracy: Lookahead generally did not improve accuracy and sometimes decreased it. Pruning was consistently more beneficial than lookahead.
  • Tree Size: Lookahead offered a small reduction in tree size, but pruning provided much larger reductions.
  • Tree Depth: Lookahead did help reduce tree depth, but pruning was again more effective.
  • Computational Cost: Lookahead significantly increased the computational effort (number of candidate splits considered) without commensurate gains in tree quality.

Limitations and Future Work

  • Limited Lookahead Depth: The study focused solely on one-level lookahead. While evaluating deeper lookahead is computationally prohibitive, the authors suggest that the observed pathology might persist.
  • Goodness Measures: The study used Gini index and information gain. It's an open question whether other goodness measures might behave differently.
  • Concept Classes: The synthetic data classes were specifically chosen to highlight certain properties. While they provide valuable insights, more diverse synthetic data could be explored.
  • Future Work: The authors suggest further research into:
  • Understanding the conditions under which pathology occurs.
  • Developing more effective goodness measures that guarantee no pathology.
  • Exploring deeper lookahead strategies if computationally feasible.
  • Investigating tree balancing techniques further, as they offer a more efficient path to improved tree depth.

Summary updated

BibTeX
@inproceedings{1995lookahead,
  title = {{Lookahead and Pathology in Decision Tree Induction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure