Abstract
Decision trees are fundamental to interpretable machine learning, yet finding the smallest tree that perfectly classifies a dataset—the Minimum-Size Decision Tree (MSDT) problem—is NP-hard. This paper introduces Witty, a solver that leverages the "witness tree" paradigm combined with advanced heuristic improvements. Witty achieves a 324-fold speedup over naive implementations and significantly outperforms state-of-the-art solvers like MurTree and SAT-based approaches.
Introduction
In machine learning, simplicity often correlates with interpretability and better generalization. While greedy algorithms like CART are widely used to build decision trees, they do not guarantee optimality in terms of tree size. The MSDT problem seeks the absolute smallest tree for a given training set. Historically, solving MSDT exactly has been computationally prohibitive. Witty addresses this by refining the witness tree approach, making optimal decision trees practical for a broader range of datasets.
The Witness Tree Paradigm
Witty is built upon the witness tree framework. Unlike traditional top-down induction, this method starts with a minimal tree and iteratively refines it. When the current tree misclassifies a training example, the algorithm branches to resolve the error.
A key feature is the use of "witnesses"—specific examples that, once correctly classified, must remain correctly classified in all subsequent refinements. This constraint significantly prunes the search space by anchoring the search to valid partial solutions.
Heuristic Improvements
To achieve its performance gains, Witty incorporates several critical engineering enhancements:
- Data Reduction: Rules to eliminate redundant features and examples, and merging equivalent feature thresholds.
- Lower Bounding: Two new lower bounds, ImpLB and PairLB, use set-cover logic to estimate the minimum number of additional nodes required.
- Symmetry Breaking: Subset constraints prevent the solver from exploring redundant permutations of the same feature cuts.
- Efficient Caching: A specialized "set-trie" data structure caches lower bounds for subsets of data, allowing the solver to skip previously solved subproblems.
Empirical Evaluation
The researchers benchmarked Witty against 700 instances derived from 35 datasets in the Penn Machine Learning Benchmarks (PMLB). The evaluation focused on both binary and continuous features.
Witty demonstrated a mean 32-fold speedup over MurTree and a 61-fold speedup over SAT-based solvers. Notably, Witty's performance advantage was most pronounced on datasets with large feature domains, where its native handling of continuous data outperformed solvers requiring binarization.
Conclusion
Witty represents a significant leap in the practical solvability of the MSDT problem. By combining a robust theoretical framework with sophisticated heuristics, it enables the computation of optimal, highly interpretable decision trees for real-world datasets. Future work will explore extending Witty to multi-class classification and allowing for near-optimal trees that tolerate small amounts of noise.
Summary updated