SAT-based Encodings for Optimal Decision Trees with Explicit Paths

• Decision trees are valued for interpretability, but minimizing them is NP-hard; smaller trees are likely to generalize better.In practice, learning commonly uses suboptimal greedy algorithms, while recent work has applied SAT, CSP, or MILP solvers.Source: §1 · p. 1
• Shallow trees may be less prone to overfitting and easier for people to interpret, while depth thresholds otherwise require manual setting.Source: §1 · p. 1
• Finding an optimal tree is challenging because large feature and example sets create an extreme search space, and optimality requires proving no smaller tree exists.Source: §1 · p. 2
• The novel SAT encoding represents tree paths rather than nodes, natively controlling depth as well as size.It finds a tree conforming to the examples at a given depth and node count through iterative SAT-solver calls minimizing size and depth.Source: §1 · pp. 1–2
• Minimizing tree depth first and then size enables tackling harder instances.Source: §1 · p. 2
• Splitting the search space by tree topologies enables tackling harder instances.Source: §1 · p. 2
• The implemented tool outperforms existing work.Source: §1 · p. 2

2 Preliminaries

• The paper assumes propositional logic, converts non-CNF formulas and cardinality constraints to CNF, and uses PySAT cardinality encodings.Source: §2 · p. 2

2.1 Training Data

• Training data use complete, consistent examples over fixed binary features, with binary positive/negative classes; non-binary features may be encoded in binary.Source: §2.1 · p. 2

3.1 Path-based Encoding

• Modeling unique root-to-leaf paths instead of nodes exploits binary-tree properties: a tree with n nodes has (n + 1)/2 leaves and the same number of paths.The encoding imposes relations between paths so that they form a binary tree.Source: §3 · p. 3, §3.1 · p. 3

3 SAT-based Optimization of Decision Trees

• The optimization searches over tree size and depth, then uses an off-the-shelf SAT solver to test whether a tree with the chosen bounds exists.Size and depth can be optimized in combination; the section describes reducing size through a series of decision problems as one search strategy.Source: §3 · pp. 2–3

3.1.1 Assigning Features and their Semantics

• Unlike, the encoding classifies per path rather than node, reducing repeated semantics to (n + 2)/2 times from n and explicitly tracking example matches.It also ensures each step has exactly one feature, prevents a feature from repeating on a path, and requires path classifications to agree with the training examples.Source: §3.1.1 · pp. 5–6

3.2 Path encoding Optimizations

• Assuming superfluous nodes are unnecessary permits additional encoding optimizations while preserving trees that conform to the examples.The general encoding can construct any decision tree conforming to the given examples.Source: §3.2 · p. 6

3.2.1 Enforcing example matching

• Each path must match at least one example, since an unmatched leaf can be removed without changing the examples’ classifications.The encoding enforces this with additional formula constraints.Source: §3.2.1 · p. 6

3.2.2 Pure features

• Features constant across all examples are removed in preprocessing because they cannot distinguish examples of different classes.Source: §3.2.2 · p. 6

3.2.3 Quasi-pure features

• If a feature has a fixed value within one class, assigning that value forces its child to be a leaf classified with that class.Source: §3.2.3 · p. 6

3.2.4 Path lower bounds

• MaxSAT estimates lower bounds on separating-path length, with separate bounds for leftmost, rightmost, and intermediate branches.The bounds consider one path at a time, so feature order on that path is irrelevant; the encoding uses two variables per feature to represent whether it is absent or used in either direction.Source: §3.2.4 · p. 7

4 Search-space Splitting by Topologies

• Splitting the search by individual topologies leaves the SAT solver to find only tree labelings, while bounded templates keep enumeration manageable when topologies proliferate.Templates fix the upper topology to a cutoff depth and leave the remaining subtrees incomplete.Source: §4 · p. 7
• For Narodytska et al., equal cutoffs preserve BFS numbering for cubes; the path encoding instead uses cardinality-labeled incomplete subtrees to represent unknown paths.In the path model, each #k subtree fixes that many paths, while a leaf corresponds to one path.Source: §4 · p. 8

4.1 Topology Enumeration

• The implementation chooses incremental solving or a new solver per template according to how many templates must be examined.Incremental solving did not pay off on hard instances, but initializing a solver for every template was costly when there were many.Source: §4.1 · p. 8
• Templates are examined in increasing difference from a greedy solution, using a recursive mismatch penalty that decays by depth with Δ=0.75.Lower-depth subtrees receive less weight in the difference calculation.Source: §4.1 · pp. 8–9

5 Experimental Evaluation

• dtfinder outperforms mindt [27] in all cases, including when using Narodytska et al.’s encoding; the authors attribute this to CaDiCaL and k-Cardinality Modulo Totalizer.Source: Table 3 · p. 10, §5 · p. 11
• Solved-instance tree sizes show sharply increasing hardness with size: depth minimization solves a handful of size-29 instances, path-based encoding solves one, and mindt [27] also solves one.The implementation of Narodytska et al.’s encoding solves none at size 29; the paper attributes the pattern to the number of topologies.Source: Figure 3 · p. 10, §5 · p. 11
• The evaluation compares dtfinder’s path-based binary size search, dtfinder-DT1 using Narodytska et al.’s encoding, topology-based variants, and d-dtfinder’s depth-size search.Source: §5 · p. 10
• On one instance, d-dtfinder’s tree has depth 6 and size 29, versus depth 11 and size 37 for sklearn; the other approaches time out at 1000 s.Source: Figure 4 · p. 11, §5 · p. 11
• d-dtfinder computes a minimum-depth solution faster than dtfinder computes a minimum-size solution and solves more instances.Source: §5 · p. 11
• Topology enumeration solves more instances with both encodings, except for depth minimization; for path-based encoding on 50% sampling, average CPU time falls from 60s to 39s.Heuristic topology ordering provides only a small overall speed-up.Source: §5 · p. 11

6 Related Work

• Fixed-depth approaches optimize accuracy on a full balanced tree, while optimizes accuracy and size but brute-force search handled only a handful of features.The benchmarks considered contain hundreds of features; recursive-splitting greedy algorithms are also well known, with an overview in.Source: §6 · pp. 11–12
• Unlike, which explicitly models nodes and child relations, this encoding models paths, avoiding tree-validity cardinality constraints and enabling lexicographic path ordering for depth bounds.Classes are assigned per path rather than per node, saving half of the semantic constraint; could restrict implicit-path depth with counters or cardinality constraints, which the paper says would be less efficient.Source: §6 · p. 12
• Prior CP work minimizes decision trees, but strictly outperformed Bessiere et al.'s approach, likely because its CP encoding is asymptotically much larger.Source: §6 · p. 12
• Topology enumeration for Boolean-circuit synthesis partitions DAGs by nodes per BFS level, whereas this paper partitions tree topologies and enumerates all possibilities when trees are small.The paper argues the circuit partitioning is unlikely to work well for binary trees and is more expensive to encode.Source: §6 · p. 12
• Cube-and-conquer is more general than this approach, but preliminary experiments found it much worse than plain SAT on these instances.Its lookahead solver can be costly and may produce splits that differ from human choices; cube decision order was also studied by Heule et al..Source: §6 · p. 12

7 Conclusions and Future Work

• The explicit-path SAT encoding controls decision-tree size and depth, outperforms existing work, and reaches practically interesting instances previously out of reach.The paper also studies splitting the search space by enumerating tree topologies.Source: §7 · p. 12
• SAT solvers poorly handle search spaces with many topologies, which the authors identify as an important challenge for the SAT community.The paper studies search-space splitting through topology enumeration.Source: §7 · p. 12
• Future solver research could improve splitting, add parallelization or cube-and-conquer, extract more from examples using extended variables, and integrate SMT-based synthesis.The paper notes that some example preprocessing already supports its optimization techniques.Source: §7 · p. 13
• Future application work could integrate the tool with greedy ensembles or exact solving of smaller subproblems, and investigate depth’s effect on interpretability and its trade-off with size.The approach provides a means to quantify tree depth and size exactly.Source: §7 · p. 13