Lookahead and Pathology in Decision Tree Induction

Sreerama K. Murthy, Steven Salzberg

In the field of machine learning, a long-standing intuition suggests that "looking ahead"—considering the consequences of a decision several steps into the future—should lead to better outcomes. This principle is a cornerstone of game-playing AI, such as Chess or Go. However, in their classic 1995 study, Sreerama Murthy and Steven Salzberg challenge this assumption within the context of decision tree induction. They demonstrate that more computation does not necessarily yield better performance and can, in fact, lead to "pathological" results.

The Search for Optimal Trees

Building the smallest possible decision tree that perfectly fits a given dataset is an NP-complete problem. Because finding the global optimum is computationally infeasible for large datasets, standard algorithms like CART and C4.5 rely on a greedy approach. These algorithms make the locally optimal split at each node using heuristics like the Gini Index or Information Gain, without considering how that choice might limit future partitioning options.

Murthy and Salzberg investigated whether a one-level lookahead algorithm (LOOK) could outperform the standard GREEDY approach. The LOOK algorithm evaluates every possible split at a node by calculating the best subsequent splits for its children, choosing the initial partition that maximizes "goodness" at the second level.

Key Insights: Why More Search Fails

The study's most significant finding is that lookahead is often "pathological." In many instances, looking one step ahead led the algorithm to choose a split that appeared superior in the short term but ultimately resulted in a tree that was both larger and less accurate than one built with simple local heuristics.

Comparison of Greedy and Lookahead algorithms across Accuracy, Tree Size, and Maximum Depth. Note that while lookahead can reduce depth, it does not significantly improve accuracy or size.

As shown in the comparative data, while lookahead can successfully reduce the maximum depth of a tree, this is often a byproduct of favoring more "balanced" splits rather than discovering a more logical categorization of the data. For most data distributions, local heuristics serve as a surprisingly robust proxy for the global optimum, and the extra search performed by LOOK rarely finds a better partition of the feature space.

The Phenomenon of Pathology

The authors highlight specific cases where the greedy approach produced a simple, highly accurate tree, while the lookahead approach over-complicated the model. For example, in one synthetic case, greedy induction produced a 4-node tree with 99.7% accuracy, whereas lookahead produced a 10-node tree with only 99.1% accuracy.

A visual example of pathology: the greedy approach (left) creates a simpler, more accurate partition of the feature space than the lookahead approach (right), which over-partitions the data.

Results and Practical Implications

The empirical results on real-world datasets from the UCI repository were telling:

  • Accuracy: Lookahead actually decreased classification accuracy in 6 out of 8 cases compared to greedy induction.
  • Computational Cost: One-level lookahead is orders of magnitude more expensive. In synthetic tests, GREEDY evaluated approximately 1,700 splits per tree, while LOOK evaluated over 419,000.
  • Pruning vs. Lookahead: The study found that post-induction pruning—removing branches that do not improve accuracy on a validation set—was far more effective at reducing tree size than lookahead, and at a fraction of the computational cost.

Conclusion

Murthy and Salzberg’s work serves as a cautionary tale against the assumption that more search always leads to better models. In decision tree induction, the greedy approach is not just a computational shortcut; it is a robust method that often avoids the pitfalls of over-searching. Future research in this area focuses on identifying specific non-linear data characteristics where lookahead might be beneficial, rather than applying it as a general-purpose improvement.

Summary updated

BibTeX
@inproceedings{murthy1995lookahead,
  author = {Sreerama K. Murthy and Steven Salzberg},
  title = {{Lookahead and Pathology in Decision Tree Induction}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure