Optimal Sparse Decision Trees

Xiyang Hu; Cynthia Rudin; Margo Seltzer

Source-linked AI summary

Optimal Sparse Decision Trees

Xiyang Hu, Cynthia Rudin, Margo Seltzer

arXiv:1904.12847v6Apr 29, 2019cs.LGstat.ML

TL;DR

Greedy decision-tree methods can produce suboptimal models, while optimal-tree search is computationally difficult. The paper introduces OSDT, which combines analytical pruning bounds with specialized data structures and bit-vector computation. OSDT finds and often proves optimal sparse trees efficiently, while its demonstrated scope is binary classification.

Problem
Greedy tree algorithms can be suboptimal, and existing optimal-tree approaches do not solve the optimization problem efficiently.
Method
OSDT minimizes misclassification error plus a leaf-count penalty using branch-and-bound, analytical bounds, specialized data structures, and bit-vector computation.
Results
OSDT is competitive with BinOCT despite using one thread, finds sparse optima missed by BinOCT's fixed topology, and reaches optimum substantially faster with major memory savings.
Takeaways & Limitations
The experiments show that practical optimal or provably near-optimal sparse decision trees are possible on datasets relevant to high-stakes decision problems.
Takeaways & Limitations
The framework focuses on binary classification, although the authors state that multiclass generalization is possible.

Abstract

from arXiv · show

Decision tree algorithms have been among the most popular algorithms for interpretable (transparent) machine learning since the early 1980's. The problem that has plagued decision tree algorithms since their inception is their lack of optimality, or lack of guarantees of closeness to optimality: decision tree algorithms are often greedy or myopic, and sometimes produce unquestionably suboptimal models. Hardness of decision tree optimization is both a theoretical and practical obstacle, and even careful mathematical programming approaches have not been able to solve these problems efficiently. This work introduces the first practical algorithm for optimal decision trees for binary variables. The algorithm is a co-design of analytical bounds that reduce the search space and modern systems techniques, including data structures and a custom bit-vector library. Our experiments highlight advantages in scalability, speed, and proof of optimality. The code is available at https://github.com/xiyanghu/OSDT.

1 Introduction

Decision trees are interpretable but dominant greedy methods can produce suboptimal, less-accurate, and less-interpretable models. OSDT addresses this gap with an efficient optimal sparse-tree algorithm that can prove optimality or closeness to optimality.

Decision trees are leading interpretable models for high-stakes applications where transparent predictions are needed.The paper discusses medical imaging, pollution modeling, recidivism risk, and credit scoring.
CART and C4.5 grow trees top down without backtracking, so an early suboptimal split can require extra splits to compensate.This can produce less-accurate and less-interpretable trees.
OSDT optimizes a regularized loss that balances accuracy with the number of leaves, unlike greedy, mathematical-programming, or brute-force approaches.Its search uses analytical bounds and specialized systems techniques.
OSDT can find optimal trees and prove optimality or closeness to optimality in reasonable time on datasets with tens of thousands or millions of observations and tens of features.The stated target includes datasets used in criminal justice systems.
The work reports 97% runtime savings, evaluates benchmark, recidivism, and credit-risk datasets, and identifies cases where prior claimed-optimal models were not optimal.It also provides ablations and releases code and supplementary materials.

2 Related Work

Prior optimal-tree methods either constrain topology or face a vastly larger search space than rule-list optimization. OSDT therefore builds on rule-list ideas while introducing tree-specific bounds and representations.

Some prior sparse-tree methods optimize only variable assignments for a topology specified in advance, rather than discovering the optimal topology.The paper explicitly distinguishes this restricted problem from its own setting.
OCT and BinOCT are recent mathematical-programming baselines, but BinOCT restricts trees to complete binary topologies of a chosen depth.That restriction speeds search while excluding some optimal sparse solutions.
The search space of decision trees grows explosively with variables and depth compared with rule lists.Table 1 compares p = 10 and 20 across depths d = 1 through 5.
Decision-tree optimization is harder than rule-list optimization because it considers every split, tree shape, and tree size, creating many symmetries.Rule lists select and permute pre-mined rules, whereas trees must consider possible splits and structures.
Applying rule-list techniques to trees requires new data structures, splitting mechanisms, and bounds because tree growth splits leaves into pairs.These operations differ fundamentally from adding one rule at a time.

3 Optimal Sparse Decision Trees (OSDT)

OSDT searches binary-feature decision trees represented by leaf sets and optimizes misclassification error plus a leaf-count penalty. Branch-and-bound bounds prune subtrees while preserving optimality guarantees.

3 Optimal Sparse Decision Trees (OSDT): The framework focuses on binary classification with binary features and labels, while noting that multiclass generalization is possible.Training examples are represented as {(x_n, y_n)} with x_n ∈ {0,1}^M and y_n ∈ {0,1}.
3 Optimal Sparse Decision Trees (OSDT): A tree is represented as a collection of Boolean leaf predicates, whose order does not affect classification and whose paths encode conjunctions of tests.Each leaf predicts a label for the data it captures.
3 Optimal Sparse Decision Trees (OSDT): The search alternates between unchanged leaves and leaves eligible for splitting, with child trees generated by splitting existing leaves.This prefix representation distinguishes fixed leaves from leaves still under exploration.
3.1 Objective Function: The objective R(d, x, y) = ℓ(d, x, y) + λH_d combines training misclassification error with a penalty proportional to the number of leaves.The penalty favors smaller trees and provides a regularized empirical-risk objective.
3 Optimal Sparse Decision Trees (OSDT): OSDT uses branch-and-bound with specialized lower and upper bounds to eliminate large portions of the tree search space.The bounds include parent-child, support, accuracy, leaf-permutation, and leaf-count constraints.
3.3 Hierarchical Objective Lower Bound: The hierarchical lower bound prunes all descendants when the unchanged-leaf bound plus one additional leaf penalty reaches the current best objective.This one-step lookahead can prune child trees even when the current prefix itself remains competitive.

4 Experiments

Experiments evaluate OSDT’s optimality, convergence, scalability, and tree structure against baseline methods across benchmark and high-stakes datasets. OSDT is competitive in runtime, can certify optimality, and avoids topology-driven unnecessary splits.

Experimental setup: Experiments compare OSDT with CART and BinOCT across seven benchmark, recidivism, and credit-risk datasets under 30-minute time limits.The evaluation measures accuracy, optimality, convergence, scalability, ablations, and tree structure.
Accuracy and optimality: OSDT can evaluate how close existing methods are to optimality, while sometimes finding sparse optima missed by topology-constrained baselines.BinOCT searches only complete binary trees of a specified depth, restricting its search space but potentially excluding optimal sparse solutions.
Convergence: Curiosity scheduling finds the optimal tree much faster than lower-bound scheduling on the COMPAS execution traces.The traces plot the objective and lower bound, marking each policy’s time to optimum and optimal objective value.
Scalability: With 4 features, OSDT spends about 75% of runtime reaching the optimum, compared with about 5% with 12 features.The scalability experiments duplicate the ProPublica dataset and include the four features of the optimal tree; extra differing features can improve pruning.
Ablation experiments: The lookahead and equivalent-points bounds are the most significant optimizations, reducing time to optimum by at least two orders of magnitude and memory by more than one order.The ablation evaluates execution time, time to optimum, trees evaluated, trees evaluated to optimum, and memory consumption.

Optimal Sparse Decision Trees: Supplementary Material

The supplementary material formalizes OSDT as a branch-and-bound search over decision trees. It combines objective lower bounds, leaf-count upper bounds, and specialized bounds to prune candidates while returning a provably optimal tree.

Equivalent points bound: Equivalent points impose an unavoidable misclassification lower bound when identical-feature observations have opposite labels.The resulting bound is added to the unchanged-leaf bound, tightening the objective lower bound for descendant trees.
Branch-and-bound algorithm: Algorithm 1 initializes a best known tree and a queue containing the empty tree, then repeatedly removes states for bound checks and expansion.It evaluates each retained tree, updates the incumbent when the objective improves, and enqueues children generated from possible feature splits.
Branch-and-bound algorithm: The algorithm prunes a tree when its lower bound is no better than the current best objective, and stops when the queue is empty.The current best objective is cached and decreases monotonically as better trees are found, enabling hierarchical pruning.
Leaf-count bounds: The current best objective yields an upper bound on the maximum number of leaves that remaining optimal trees can have.A parent-specific version can tighten this bound for child trees whose unchanged leaves contain the parent’s unchanged leaves.
Leaf-count bounds: The regularization parameter λ controls several structural bounds, including a minimum support of 2λ through each internal node of an optimal tree.These bounds restrict candidate tree structures and support more aggressive pruning.

D Upper Bounds on Number of Tree Evaluations

The algorithm bounds how many tree evaluations remain and how many evaluations may occur in total. These bounds use execution state for tighter estimates or rely only on features and regularization for a naïve total bound.

State-dependent bounds: Theorem D.1 bounds remaining tree evaluations from the current objective, queue, and unchanged-leaf structure during execution.It counts trees currently in or later inserted into the queue and uses current execution information.
Total bound: The naïve total-evaluation bound depends only on the number of features and regularization parameter λ, without using algorithm execution state.Corollary D.2 contrasts with Theorem D.1 by bounding the search space without the current queue or objective.
Symmetry: Equivalent trees formed from the same leaves up to permutation have identical classifications, objective lower bounds, and corresponding child trees.This equivalence means one permutation can represent the others during search.
Symmetry: Symmetry-aware pruning keeps one representative among permutation-equivalent trees, avoiding redundant child-tree generation.The method prunes either tree when two trees contain the same leaves up to permutation.

E.1 Upper bound on tree evaluations with symmetry-aware pruning

Symmetry-aware pruning exploits permutation equivalence among leaf sets to reduce the tree-search space. The resulting evaluation savings can become extremely large as the feature and leaf bounds grow.

Pruning mechanism: For each subset of K leaves, symmetry-aware pruning retains one of K! permutation-equivalent leaf sets during breadth-first search.The state space uses 3^M possible leaves because each feature can take value 1, value 0, or be omitted.
Evaluation bound: The pruning bound is combined with an upper bound K on the number of leaves in any optimal tree, where K ≡ min(⌊1/2λ⌋, 2M).The proof propagates the retained counts across tree lengths using permutations and combinations.
Evaluation savings: Pruning based on permutation symmetries yields computational savings measured by the difference between permutation and combination counts across tree sizes.The corresponding reduction is represented by Σ from k=1 to K of P(M,k) − C(M,k).
Evaluation savings: About 35,463 evaluations are eliminated when M = 10 and K = 5, while about 7.36891 × 10^11 are eliminated when M = 20 and K = 10.These examples illustrate the growth of savings with larger feature and leaf bounds.
Similar support bound: The similar support bound prunes a tree and all its children when a counterpart using a similar split is already worse than the current best by a margin.The objective difference between the two trees’ best child continuations is bounded by normalized support ω.

G.1 Data Structure of Leaf and Tree

OSDT stores leaf- and tree-level state to incrementally evaluate bounds and objectives, while a priority queue and canonical caches organize and deduplicate search. The curiosity scheduling metric gives the best reported runtime and memory performance.

Tree data structure: Each tree stores its leaves, objective lower bound, and a binary vector marking leaves that can still be split.The vector distinguishes split leaves from unchanged leaves inherited by child trees.
Leaf data structure: Each leaf stores its defining clauses, captured samples, support count, dead features, error lower bound, label, and loss.Captured samples and dead-feature information are represented with binary vectors.
Queue and scheduling: A priority queue selects trees for expansion, and curiosity—the lower bound divided by unchanged-leaf support—achieves the best reported scheduling performance.Relative to objective-based ordering, curiosity reduces runtime by a factor of two and memory consumption by a factor of four.
Symmetry caches: LeafCache canonicalizes clause order to compute values for each permutation-equivalent leaf only once, while TreeCache prevents reevaluation of equivalent trees.Both caches use canonical representations as lookup keys.
Search execution: For each queued tree, the algorithm incrementally computes child bounds and objectives, updates the incumbent when improved, and queues a child only when bounds permit improvement.Otherwise, hierarchical lower bounds certify that no child can beat the current best objective.
Regularization bounds: If an optimal tree has one more leaf than a pruned candidate, the objective relation yields λ ≤ a_i, where a_i is their loss discrepancy.The same regularized-objective reasoning gives a 2λ lower threshold on the combined support of sibling leaves.

H.7 Proof of Theorem 3.5

The proof derives a lower bound on tree error by aggregating unavoidable minority-class mistakes within equivalent-point groups. Adding the leaf regularization term then produces the objective bound used by the algorithm.

Leaf-sibling comparison: Deleting sibling leaves and restoring their parent changes the loss by a_i, so optimality implies λ ≤ a_i.The regularization penalty for the additional leaf must not exceed the associated loss discrepancy.
Error lower bound: A tree assigns one label to each equivalent-point set, so it must misclassify at least the points belonging to that set’s minority class.Summing these unavoidable errors contributes to a lower bound on the tree’s misclassification error.
Objective bound: Because every datum must be captured by a leaf, the aggregated error bound extends to the regularized objective R(d, x, y) = ℓ(d, x, y) + λK.The proof then applies the definition of θ(e_u) to obtain the stated objective lower bound.

I Ablation Experiments

The ablation experiments evaluate how individual bounds and the scheduling metric contribute to OSDT’s execution performance on the recidivism data set.

I Ablation Experiments: Table 2 compares OSDT variants by total execution time, time to optimum, trees evaluated, trees evaluated to optimum, and memory consumption.The full implementation appears in the first row, while each other variant removes one specific bound.
I Ablation Experiments: The experiments assess how much each analytical bound contributes to OSDT’s performance.Each variant removes a specific bound from the full OSDT implementation.
I Ablation Experiments: The evaluation also examines the scheduling metric’s effect on execution.

J Regularized BinOCT

Regularized BinOCT can produce the same optimally regularized trees as OSDT, but OSDT reaches them substantially faster. The comparison highlights OSDT’s computational advantage over a complete-tree mathematical-programming formulation.

J Regularized BinOCT: RBinOCT adds a leaf-count penalization term so its complete binary trees can be compared with OSDT under the same regularization objective.The added term uses λ and indicates whether each leaf is nonempty.
J Regularized BinOCT: With λ = 0.007, regularized BinOCT and OSDT produce the same optimal trees on Monk1.Regularized BinOCT had not finished after 1 hour, while OSDT reached optimality in 3.390 seconds.
J Regularized BinOCT: OSDT converges much faster than RBinOCT, with RBinOCT taking several times longer on FICO and Monk1.
J Regularized BinOCT: CART trees with the same number of leaves perform much worse than corresponding OSDT trees on COMPAS, Tic-Tac-Toe, and Monk1.

L Cross-validation Experiments

Cross-validation evaluates OSDT, CART, and BinOCT across seven datasets and folds, comparing training and test accuracy at matched sparsity levels. The results generally associate higher training accuracy at a given sparsity with higher test accuracy, though exceptions and ties occur.

L Cross-validation Experiments: OSDT finds the most accurate tree for each given sparsity level by adjusting its regularization parameter across its full range.
L Cross-validation Experiments: Higher training accuracy at the same sparsity level generally yields higher test accuracy, but this pattern is not universal.
L Cross-validation Experiments: On the car dataset, OSDT’s almost-uniformly-higher training accuracy leads to higher test accuracy.
L Cross-validation Experiments: The figures report 10-fold cross-validation results for OSDT, CART, and BinOCT on COMPAS, FICO, Tic-Tac-Toe, car, Monk1, Monk2, and Monk3.Horizontal lines indicate the training accuracy of the best OSDT tree.