Introduction
Standard decision tree induction algorithms, such as ID3 and C4.5, rely on greedy heuristics to construct models. While computationally efficient, these methods often produce suboptimal trees, particularly when dealing with complex attribute interactions like parity (XOR) problems. This paper introduces Interruptible Induction of Decision Trees (IIDT), an anytime algorithm that bridges the gap between fast greedy induction and computationally intensive optimal search. Unlike contract algorithms that require a pre-specified time limit, IIDT can be interrupted at any point to provide a valid, progressively improving model.
The IIDT Framework
The core of IIDT is an iterative improvement strategy that treats an initial greedy tree as a starting point for refinement. The algorithm continuously identifies subtrees for reconstruction using a sophisticated selection heuristic.
Algorithm Overview
The IIDT procedure begins by constructing a baseline tree using a standard greedy inducer. It then enters a loop that persists until interrupted. In each iteration, a node is selected, its corresponding subtree is extracted, and a new subtree is generated using LSID3, a contract algorithm that employs stochastic sampling. If the new subtree $t'$ is found to be "better" (e.g., smaller or more accurate) than the original subtree $t$, it replaces $t$ in the global tree $T$.
Node Selection Heuristic
To maximize the efficiency of the anytime process, IIDT must prioritize nodes where reconstruction is most likely to yield significant improvements. This is achieved through the CHOOSE-NODE procedure, which calculates the marginal utility ($u_{node}$) for each node in the tree.
The heuristic balances the expected benefit ($\Delta q$)—the potential reduction in tree size or error—against the expected cost ($cost_{node}$) of rebuilding. A granularity parameter ($g$) ensures that the algorithm does not over-invest in deep, local optimizations at the expense of higher-level splits that might have a greater global impact.
Experimental Evaluation
The authors evaluated IIDT across several challenging domains:
- UCI Benchmarks: Glass and Tic-Tac-Toe datasets.
- Artificial Hard Concepts: The 20-Multiplexer and 10-XOR problems. These are notoriously difficult for greedy inducers because no single attribute provides significant information gain in isolation.
- Noisy Environments: A Noisy XOR-5 problem was used to test the algorithm's robustness and pruning capabilities.
Key Results and Insights
IIDT demonstrates significant advantages over both standard greedy inducers and existing lookahead methods:
- Solving "Hard" Concepts: On the 10-XOR problem, where ID3 and C4.5 typically achieve only ~50% accuracy, IIDT successfully converged to nearly 100% accuracy given sufficient computation time.
- Anytime Performance: The algorithm exhibits a classic diminishing returns curve. It produces substantial improvements early in the execution and continues to refine the model as more time is allocated.
- Robustness: By ensuring that a subtree is only replaced if the new version is strictly better, IIDT guarantees monotonic improvement in model quality.
- Comparison with Other Learners: IIDT outperformed sophisticated techniques such as Skewing, GATree (genetic algorithms), and Bagging on complex tasks, often resulting in more compact and accurate trees.
Conclusion
IIDT provides a flexible framework for decision tree induction that adapts to available computational resources. By combining greedy initialization with targeted, iterative reconstruction, it overcomes the limitations of local search heuristics while maintaining the interruptibility required for real-time applications. Future work may involve leveraging data from failed reconstruction attempts to further refine the node selection process.
Summary updated