Research map / Learning theory and algorithms / Combinatorial and search optimization
Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Implements and heavily engineers the witness-tree paradigm into the Witty solver for minimum-size perfect decision trees, with data reduction, improved branching, lower bounds, subset constraints and caching, outperforming MurTree and SAT-based solvers.
Problem
Computing a minimum-size decision tree that classifies all training examples perfectly (MSDT), an NP-hard problem whose existing exact solvers scale poorly.
Approach
Makes the theoretical witness-tree algorithm practical by adding heuristic speedups (dirty-example priority, data reduction rules, branching refinements, ImpLB/PairLB lower bounds, subset constraints and subset caching) while preserving optimality, and gives an improved running-time bound with log(s) in the base.
Key results
- Witty solves 388 of 700 instances versus 371 for MurTree, the best of the three state-of-the-art solvers.
- Witty achieves a mean 32-fold (median 7-fold) speedup over MurTree and a mean 61-fold (median 25-fold) speedup over SAT-based implementations.
- The heuristic augmentations give a mean 324-fold (median 84-fold) speedup over the naive witness-tree implementation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add all heuristic improvements (data reduction, branching improvements, lower bounds, subset constraints, subset caching) to naive witness-tree implementation (ablation) | Witty · Penn Machine Learning Benchmarks | running time speedup over naive implementation: mean 324-fold, median 84-fold | Helped |
| Use Witty instead of MurTree (state-of-the-art dynamic programming) | minimum-size perfect decision tree solving · Penn Machine Learning Benchmarks | running time speedup over MurTree: mean 32-fold, median 7-fold; 388 vs 371 instances solved | Helped |
| Use Witty instead of SAT-based implementations | minimum-size perfect decision tree solving · Penn Machine Learning Benchmarks | running time speedup over SAT-based solvers: mean 61-fold, median 25-fold | Helped |
| Dirty Subset Constraint (theoretical) giving improved worst-case bound | witness-tree algorithm for MSDT · worst-case running time | O((δDs)^s·sn) improved to O((δD log s)^s·sn) | Helped |
Limitations
- Only perfect trees on binary-class data are handled in the baseline setting.
- Speedup factors ignore instances solved in under one second by both solvers.
- Extension to weaker accuracy guarantees and more classes is left for future work.
Experimental setup
Datasets: Penn Machine Learning Benchmarks (PMLB) classification datasets (700 instances)
Benchmarks: Penn Machine Learning Benchmarks (700 instances)
Metrics: number of solved instances running time speedup (mean and median)
Baselines: MurTree SAT-based solver (Janota and Morgado 2020) naive witness-tree implementation
Builds on: witness-tree paradigm (Komusiewicz et al. ICML 2023) MurTree Set Cover ILP relaxation
Closest papers by meaning
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.89)
- Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms (ICML 2025 · similarity 0.89)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.89)
- Learning Small Decision Trees for Data of Low Rank-Width (AAAI 2024 · similarity 0.89)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.88)
- Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.