When a Decision Tree Learner Has Plenty of Time

Saher Esmeir, Shaul MarkovitchAAAI 2006

Abstract

Standard decision tree induction algorithms like ID3 and C4.5 utilize greedy top-down strategies that are computationally efficient but often result in sub-optimal models. This paper introduces LSID3 (Lookahead Stochastic ID3), an anytime algorithm designed to utilize additional computational resources to find smaller and more accurate trees. By employing stochastic sampling and Monte-Carlo estimation, LSID3 overcomes the limitations of both greedy heuristics and exhaustive lookahead methods.

Introduction

The popularity of decision tree learners stems from their speed and the interpretability of their output. However, traditional algorithms are "resource rigid": they take a fixed, minimal amount of time and cannot improve their results even if more time is available. Furthermore, they are susceptible to local optima because they make irreversible "greedy" choices at each node based on immediate information gain.

Existing attempts to address this via lookahead (e.g., ID3-k) suffer from exponential computational growth, making deep lookahead impractical. LSID3 addresses these issues by framing attribute selection as a search problem that can be explored via stochastic sampling.

Methodology: Lookahead Stochastic ID3

LSID3 is a "contract" anytime algorithm, meaning it operates within a pre-specified resource budget. The algorithm evaluates candidate splits at each node by estimating the size of the resulting tree if that split were chosen.

The core components of LSID3 include:

  1. Stochastic ID3 (SID3): A randomized version of the standard ID3 algorithm. Instead of always selecting the attribute with the highest information gain, SID3 selects an attribute with a probability proportional to its gain.
  2. Monte-Carlo Estimation: For every possible attribute split at a node, LSID3 invokes SID3 $r$ times. This generates a sample of potential trees.
  3. Size Minimization: Guided by Occam’s Razor, LSID3 selects the attribute that yielded the smallest tree among its $r$ samples.

As the number of samples $r$ increases, the algorithm's estimate of the "best" split becomes more accurate, allowing for a smooth trade-off between computation time and model quality.

Experimental Evaluation

The performance of LSID3 was evaluated using 17 standard datasets from the UCI Machine Learning Repository and several synthetic "hard" concepts, such as XOR and Multiplexer problems. These synthetic datasets are specifically designed to challenge greedy learners, as no single feature provides significant information gain until multiple features are considered simultaneously.

Key Results

Anytime Scaling and Accuracy

A primary advantage of LSID3 is its efficient anytime behavior. Unlike exhaustive lookahead methods where the time requirement jumps significantly between levels, LSID3 allows for fine-grained control over the time budget.

Anytime performance of LSID3 compared to ID3-k, ID3, and C4.5.

As shown in the figure above, LSID3's accuracy improves steadily as more time is allocated. It significantly outperforms ID3-k for any given time budget, demonstrating that stochastic sampling is a more efficient way to explore the search space than exhaustive shallow lookahead.

Model Complexity

In addition to improved accuracy, LSID3 consistently produces more compact models. Smaller trees are generally preferred as they are more interpretable and less likely to overfit the training data.

Ratio of LSID3 tree size to ID3 tree size across various datasets.

The experimental results across various datasets show that LSID3 almost always produces trees that are smaller than those generated by ID3, often reducing the number of leaves by 20% to 60%.

Conclusion

LSID3 demonstrates that stochastic lookahead is a powerful technique for decision tree induction when computational time is not the primary constraint. By replacing exhaustive search with sampling, LSID3 provides a flexible, anytime framework that yields smaller and more accurate models. Future research will focus on developing interruptible versions of the algorithm and extending this sampling-based lookahead approach to other greedy AI domains.

Summary updated

BibTeX
@inproceedings{esmeir2006when,
  author = {Saher Esmeir and Shaul Markovitch},
  title = {{When a Decision Tree Learner Has Plenty of Time}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure