Abstract
Finding the minimum-size decision tree for a given dataset is a fundamental NP-hard problem. While heuristic approaches like CART and C4.5 are widely used, they often produce sub-optimal, overly complex trees that hinder interpretability. This paper introduces a novel SAT-based encoding, DT1, which significantly prunes the search space through compact representation and symmetry breaking. Our results demonstrate that this approach can find truly optimal trees for practical datasets, offering up to a 30% reduction in tree size compared to standard heuristics while maintaining accuracy.
Introduction
In the field of eXplainable AI (XAI), decision trees are favored for their inherent interpretability. However, as tree size increases, this interpretability diminishes; a tree with hundreds of nodes can become as opaque as a deep neural network. To maximize human understanding, it is essential to find the smallest possible tree that accurately fits the data.
Historically, finding the minimum-size decision tree has been computationally prohibitive. Previous exact methods using Boolean Satisfiability (SAT) or Constraint Programming (CP) were limited to small, synthetic datasets. This research bridges the gap by proposing a more efficient SAT encoding that scales to real-world benchmarks.
Methods: The DT1 Encoding
The core contribution is a new SAT model, DT1, designed to determine if a decision tree of size $N$ exists for a dataset. The model incorporates several innovations to manage complexity:
- Breadth-First Node Numbering: Instead of a fixed tree structure, the model uses a breadth-first scheme, allowing the SAT solver to explore various topologies dynamically.
- Discrimination Tracking: The model uses specific variables to track feature branching from the root to each node, ensuring correct classification of positive and negative examples.
- Symmetry Breaking: Constraints are added to eliminate redundant searches, such as ensuring the left branch always corresponds to a feature value of 0.
- Inference Constraints: Mathematical rules prune the search space by limiting child indices based on whether a node is a leaf.
The search for the minimum size is iterative. Starting from an upper bound provided by a heuristic (like ITI), the SAT solver checks for the existence of a tree of size $N-2$ until the problem becomes "unsatisfiable," confirming the optimality of the last found size.
Key Results
The DT1 model was evaluated against benchmarks from the PMLB and UCI repositories. The results highlight significant improvements in both computational efficiency and model interpretability.
Efficiency and Encoding Scale
The proposed encoding is $O(K \times N^2 + M \times N \times K)$, which is significantly tighter than previous $O(M^2)$ models. This reduction in complexity allows the SAT solver (Glucose3) to handle much larger datasets. For instance, on the "Mouse" dataset, DT1 proved optimality in just 12.94 seconds, compared to nearly 10 minutes for previous state-of-the-art models. In some cases, the encoding size was reduced by several orders of magnitude compared to older SAT formulations.
Tree Size Reduction
A key finding is that standard heuristics often produce "bloated" trees. For the "Car" dataset, the ITI heuristic generated trees with an average of 22.3 nodes, whereas the SAT model consistently found optimal trees with only 18.8 nodes. This reduction in size directly translates to better interpretability without sacrificing training accuracy.
Conclusion
This work demonstrates that finding optimal decision trees is no longer restricted to toy problems. By refining SAT encodings, researchers can now produce the most interpretable models possible for medium-sized practical datasets. Future work will focus on scaling these methods to trees with more than 100 nodes and integrating information-gain heuristics directly into the SAT solver's branching logic to further accelerate the search.
Summary updated