Learning Optimal Oblique Decision Trees with (Max)SAT

Florent AvellanedaIJCAI 2025 · DOI

TL;DR

This paper introduces a novel method for learning optimal oblique decision trees by reformulating the problem as a (Max)SAT instance. This allows them to leverage powerful SAT solvers to find globally optimal trees, overcoming the limitations of traditional greedy heuristics. Their approach demonstrates competitive accuracy and computational efficiency for small to medium-sized datasets.

What Problem Does This Paper Address?

Decision trees are a cornerstone of machine learning due to their interpretability and effectiveness. However, standard decision trees use "axis-parallel" splits, meaning they divide data based on a single feature's threshold (e.g., "if feature X > 5"). This can lead to very large and complex trees when the true decision boundaries in the data are not aligned with the feature axes.

"Oblique" decision trees offer a solution by allowing splits based on linear combinations of features (e.g., "if 0.5featureX + 0.3featureY > 2"). This can create smaller, more accurate, and more interpretable trees. The challenge, however, is finding the globally optimal oblique decision tree, as existing methods often rely on greedy heuristics that don't guarantee the best possible solution. This paper tackles the problem of learning provably optimal oblique decision trees efficiently.

Methods

The core contribution of this paper is a novel encoding of the optimal oblique decision tree learning problem into a (Max)SAT (Maximum Satisfiability) or SMT (Satisfiability Modulo Theories) instance.

Here's a breakdown of their approach:

  • Boolean Variables: They define a set of Boolean variables to represent different aspects of the tree structure and decision rules. For example, Se,n indicates if example e is directed towards node n, and An,f1,f2 indicates if features f1 and f2 are used for a split at node n.
  • Constraints: They formulate a series of logical constraints that capture the rules of decision tree construction, including:
  • Ensuring each branching node selects at most one pair of features for splitting.
  • Ensuring each branching node selects at least one pair of features.
  • Enforcing that examples follow the correct path through the tree to reach a leaf node.
  • Ensuring leaf nodes are assigned to a single class.
  • Crucially, encoding the linear separability constraint for oblique splits.
  • Linear Separation Encoding: This is a key novelty. They propose two ways to encode the linear separation required for oblique splits:
  • SMT-based: Using linear arithmetic constraints within an SMT solver.
  • SAT-based: A more ingenious approach that leverages a geometric theorem about linear separability in the projective plane. This method uses fictitious points at infinity and triangle containment to define constraints, significantly reducing the number of clauses compared to a direct encoding.
  • Optimality: By formulating the problem as a SAT instance, they can use state-of-the-art SAT solvers to find a solution that satisfies all "hard" constraints (tree structure, path consistency) and minimizes the number of "soft" constraints violated (e.g., misclassifications, if aiming for a tree that minimizes errors rather than a perfectly accurate one).
  • Tree Reconstruction: After obtaining a solution from the SAT/SMT solver, they reconstruct the oblique decision tree. For the SAT approach, they use a hard-margin Support Vector Machine (SVM) to compute the actual separating hyperplanes at each node, using the features identified by the SAT solver.

Datasets

The paper evaluates their approach on 13 small to medium-sized real-world datasets from the UCI Machine Learning Repository. These datasets vary in size, number of features, and number of classes. They also generated synthetic datasets to systematically study the impact of dataset size and tree depth on computational efficiency.

Key Insights and Ideas

  • (Max)SAT as a Powerful Tool for Optimal Oblique Trees: The paper demonstrates that (Max)SAT solvers, traditionally used for logical reasoning, are highly effective for finding globally optimal oblique decision trees. This opens up a new avenue for solving this challenging optimization problem.
  • Geometric Theorem for Linear Separability: The novel SAT encoding for linear separation, based on a geometric theorem involving points at infinity and triangle containment, is a significant theoretical contribution. It allows for a more compact and efficient encoding compared to direct arithmetic constraints.
  • SAT Outperforms SMT for Efficiency: The experiments show that the SAT-based encoding is orders of magnitude faster than the SMT-based encoding for solving the problem, highlighting the power of specialized SAT techniques for this task.
  • Trade-off Between Optimality and Speed: While their method finds provably optimal trees, it is computationally more expensive than heuristic methods. However, for small to medium datasets, the time taken is still within practical limits, and the optimality guarantee is valuable.

Key Results

  • Superior Accuracy: The proposed (Max)SAT and SMT encodings consistently achieved superior training accuracy compared to heuristic methods (HHCART, IAI) on the tested real-world datasets.
  • Computational Efficiency: The SAT encoding, particularly when solved with the EvalMaxSAT solver, demonstrated significantly better runtime performance than the SMT encoding solved with Z3. For example, on synthetic datasets, SAT was orders of magnitude faster.
  • Scalability with Incomplete Solvers: When faced with larger datasets that exceeded the 3-hour timeout for exact solvers, they used incomplete MaxSAT solvers (NuWLS) which provided high-quality solutions within practical time limits, often outperforming heuristic methods in accuracy.
  • Optimal Trees are Feasible: The paper successfully found provably optimal oblique decision trees for small to medium datasets within reasonable computational times (e.g., finding an optimal depth-2 tree for the Wine dataset in 40 seconds, compared to 5 minutes reported in prior work for a similar task).

Limitations and Future Work

  • Computational Complexity: The primary limitation remains computational complexity, especially for larger datasets and deeper trees. Both SAT and SMT encodings exhibit exponential growth in execution time with increasing tree depth.
  • Generalization Performance: The evaluation focused on finding optimal trees rather than optimizing generalization performance (e.g., through pruning or regularization). Future work could explore integrating these techniques.
  • Incomplete Solvers: While incomplete MaxSAT solvers offer practical solutions for larger instances, they do not guarantee optimality. Future research could focus on improving the scalability of exact methods or developing better incomplete solver strategies.
  • Comparison with Mixed-Integer Programming: The authors mention they were unable to compare with mixed-integer programming approaches for optimal oblique trees, which could be a valuable future comparison.

Summary updated

BibTeX
@inproceedings{avellaneda2025learning,
  author = {Florent Avellaneda},
  title = {{Learning Optimal Oblique Decision Trees with (Max)SAT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/285},
}
Figure