Overview
Researchers have introduced Witty, a high-performance solver designed to find the smallest possible decision tree that perfectly classifies a given dataset. By optimizing the "witness-tree" algorithmic paradigm, Witty achieves a massive 32-fold speedup over current state-of-the-art solvers like MurTree. It is particularly effective for datasets with many feature values, a scenario where previous methods often struggled.
The Challenge of Minimum-Size Decision Trees
Decision trees are highly valued for their interpretability. However, to remain interpretable and generalize well to unseen data, these trees must be compact. Finding the absolute smallest tree that correctly classifies every point in a training set—known as the Minimum-Size Decision Tree (MSDT) problem—is NP-hard.
Existing optimal solvers typically rely on SAT-based encodings or Dynamic Programming. These methods often require "binarizing" data (converting all features into binary yes/no questions), which can lead to a combinatorial explosion in complexity. Witty addresses these scalability issues by avoiding mandatory binarization and utilizing a more flexible search strategy.
The Witness-Tree Paradigm
Witty is built on the witness-tree paradigm. Unlike traditional top-down heuristics (such as CART), this approach starts with a single leaf and iteratively refines it. When the current tree misclassifies an example (a "dirty" example), that example becomes a "witness." The algorithm then branches to find a new cut that separates this witness, ensuring all future refinements maintain correct classification for that witness.
To make this search efficient, Witty incorporates several key optimizations:
- Data Reduction Rules: Simplifying the dataset by removing redundant features or examples before the search begins.
- Dirty Example Priority: A heuristic that selects which misclassified example to fix first to minimize the search space.
- Advanced Lower Bounds: Using Set Cover logic to prune hopeless branches early.
- Subset Constraints and Caching: Novel techniques to skip redundant thresholds and reuse lower bounds for specific data subsets.
Performance and Key Results
The researchers evaluated Witty using 700 instances derived from the Penn Machine Learning Benchmarks (PMLB). Witty significantly outperformed previous state-of-the-art tools:
- Vs. MurTree: Witty achieved a 32-fold mean speedup and was particularly dominant on datasets with high-cardinality features.
- Vs. SAT-based Solvers: Witty was approximately 61 times faster than leading SAT implementations.
- Solving Capacity: Witty solved 388 out of 700 test instances, surpassing MurTree (371) and SAT-based methods.
The combination of these optimizations resulted in a 324-fold speedup compared to a naive implementation of the witness-tree algorithm.
Limitations and Future Outlook
Witty currently focuses on perfect classification for binary problems, meaning it finds trees with 100% accuracy on training data. While this is ideal for certain logic-based tasks, real-world data is often noisy. Future work aims to adapt Witty to handle misclassification tolerances, multi-class data, and different optimization objectives, such as minimizing tree depth rather than total node count. Despite these current limits, Witty represents a significant leap in making optimal decision tree induction practical for real-world datasets.
Summary updated