Witty: An Efficient Solver for Computing Minimum-Size Decision Trees

Luca Pascal Staus, Christian Komusiewicz, Frank Sommer, Manuel Sorge

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.

The witness tree refinement process: (a) initial tree with misclassified example z, (b-d) potential refinements to correctly classify 'witness' examples.

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.

Performance comparison: Witty solves a higher percentage of instances faster than MurTree, Basic witness tree, and dtfinder.

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

Abstract

Decision trees are a classic model for summarizing and classifying data. To enhance interpretability and generalization properties, it has been proposed to favor small decision trees. Accordingly, in the minimum-size decision tree training problem (MSDT), the input is a set of training examples in $\mathbb{R}^d$ with class labels and we aim to find a decision tree that classifies all training examples correctly and has a minimum number of nodes. MSDT is NP-hard and therefore presumably not solvable in polynomial time. Nevertheless, Komusiewicz et al. [ICML '23] developed a promising algorithmic paradigm called witness trees which solves MSDT efficiently if the solution tree is small. In this work, we test this paradigm empirically. We provide an implementation, augment it with extensive heuristic improvements, and scrutinize it on standard benchmark instances. The augmentations achieve a mean 324-fold (median 84-fold) speedup over the naive implementation. Compared to the state of the art they achieve a mean 32-fold (median 7-fold) speedup over the dynamic programming based MurTree solver [Demirovi\'c et al., J. Mach. Learn. Res. '22] and a mean 61-fold (median 25-fold) speedup over SAT-based implementations [Janota and Morgado, SAT '20]. As a theoretical result we obtain an improved worst-case running-time bound for MSDT.
BibTeX
@inproceedings{staus2025witty,
  author = {Luca Pascal Staus and Christian Komusiewicz and Frank Sommer and Manuel Sorge},
  title = {{Witty: An Efficient Solver for Computing Minimum-Size Decision Trees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i19.34268},
}
Figure