Introduction
Decision trees are highly valued in machine learning for their inherent interpretability. Unlike "black-box" models, decision trees allow users to trace the logic behind specific classifications. However, standard algorithms like CART or C4.5 rely on greedy heuristics that optimize local splits rather than the global tree structure. Finding an "optimal" decision tree—defined as the smallest tree (minimum depth or nodes) that perfectly fits a dataset—is a classic NP-complete problem.
Historically, exact methods using Boolean satisfiability (SAT) solvers have struggled to scale beyond very small datasets. This research introduces a novel incremental approach that significantly improves the scalability of optimal decision tree inference, enabling the processing of datasets with thousands of examples in seconds or minutes.
Methodology
The proposed approach leverages two primary innovations: a compact SAT encoding and an incremental inference strategy.
Perfect Tree SAT Encoding
The authors represent the decision tree as a "perfect" binary tree where all leaves reside at the same depth. By employing a binary indexing system—where a parent node $i$ has children $2i$ and $2i+1$—the researchers can formulate compact Boolean constraints. These constraints define feature assignments at internal nodes and the paths examples must traverse to reach leaf nodes.
Incremental Inference: The "Secret Sauce"
The core breakthrough is an incremental algorithm. Rather than encoding the entire training set into a single massive SAT formula, the solver begins with an empty set of examples. It infers a candidate tree, identifies misclassified training examples, and adds only those specific "counter-examples" as new constraints. This iterative process typically converges on an optimal solution using only a small fraction of the total data, drastically reducing computational overhead.
Experimental Results
The methodology was evaluated against standard benchmarks from the UCI Machine Learning Repository and synthetic datasets. The researchers developed two variants: $DT_{depth}$, which minimizes tree depth, and $DT_{size}$, which minimizes the total number of nodes for a given minimum depth.
Performance and Scalability
The incremental approach demonstrated massive speedups over previous state-of-the-art SAT methods. For instance, on the "Mouse" dataset, inference time dropped from 12.9 seconds to just 0.02 seconds. On the "Car" dataset (1728 examples), the algorithm successfully inferred an optimal tree in approximately 2 minutes, whereas previous methods failed to process more than 10% of the data within a reasonable timeframe.
Accuracy and Generalization
By adhering to the principle of parsimony—finding the simplest model that fits the data—the optimal trees often exhibited superior generalization compared to heuristic-based models.
As shown in the table above, the $DT_{size}$ and $DT_{depth}$ methods frequently outperformed heuristic algorithms like CART and other optimization frameworks like BinOCT. On the Balance-scale dataset, the optimal tree achieved 93.0% accuracy, a significant improvement over CART's 77.5%. On average, $DT_{size}$ achieved the highest accuracy at 88.3%.
Conclusion
This work demonstrates that optimal decision tree inference is no longer confined to toy problems. By combining clever SAT encodings with an incremental "active learning" style approach, the authors have made exact optimization viable for real-world data sizes. While challenges remain regarding high-depth trees and feature explosion in non-binary datasets, this research provides a powerful tool for creating interpretable, parsimonious, and highly accurate machine learning models.
Summary updated