PaperlayerView exact revision on arXiv

Source-linked AI summary

Generalized and Scalable Optimal Sparse Decision Trees

Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, Margo Seltzer

arXiv:2006.08690v4cs.LGstat.ML

TL;DR

Decision-tree optimization is difficult because heuristic and approximate methods can produce suboptimal trees, while exact optimization is computationally hard. The paper introduces GOSDT, a generalized sparse optimization framework with specialized search representations and bounds for diverse objectives and continuous variables. It provides provably optimal sparse trees, scales to tens of thousands of observations, and reports an optimality gap when stopped early, while remaining most effective for datasets with few or medium-sized feature sets.

  • Problem

    Heuristic methods can produce suboptimal trees without a known optimality gap, while exact optimization is NP-hard and existing methods face limitations on imbalanced objectives and continuous variables.

  • Method

    GOSDT combines generalized objective handling with dynamic programming, computational reuse, and bounds that reduce the search space for sparse decision-tree optimization.

  • Results

    GOSDT produces provably optimal sparse decision trees across objectives including F-score, AUC, and partial AUC, and scales to tens of thousands of observations.

  • Takeaways & Limitations

    GOSDT enables exact optimization of sparse interpretable trees while allowing users to assess near-optimality through a reported optimality gap when computation stops early.

  • Takeaways & Limitations

    GOSDT is most effective for datasets with a small or medium number of features, and further speedups and broader constraints remain future work.

Abstract

from arXiv · show

Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have optimization breakthroughs been made that have allowed practical algorithms to find optimal decision trees. These new techniques have the potential to trigger a paradigm shift where it is possible to construct sparse decision trees to efficiently optimize a variety of objective functions without relying on greedy splitting and pruning heuristics that often lead to suboptimal solutions. The contribution in this work is to provide a general framework for decision tree optimization that addresses the two significant open problems in the area: treatment of imbalanced data and fully optimizing over continuous variables. We present techniques that produce optimal decision trees over a variety of objectives including F-score, AUC, and partial area under the ROC convex hull. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables and speeds up decision tree construction by several orders of magnitude relative to the state-of-the art.

1. Introduction

Existing decision-tree methods often rely on heuristics or computational approximations that can yield suboptimal solutions without a certifiable optimality gap. GOSDT provides a generalized sparse optimization framework designed to address imbalanced objectives and continuous variables.

  • Motivation: Heuristic splitting and pruning can produce suboptimal trees without revealing or correcting the size of the optimality gap.The gap between attainable and attained performance can sometimes be large.
  • Motivation: Full decision-tree optimization is NP-hard, and practical assumptions that simplify it generally do not hold for real data.SAT-based approaches can rapidly solve perfectly separable data, but real datasets are generally not separable.
  • Prior approaches: Dynamic-programming methods improve search efficiency, but prior approaches either inherit suboptimality from greedy trees or sacrifice optimality through bucketization.DL8.5 reduces its search space using bucketization, while DL8 without comparable reductions is computationally impractical.
  • Contribution: GOSDT generalizes sparse decision-tree optimization to objectives including weighted accuracy, balanced accuracy, F-score, AUC, and partial area under the ROC convex hull.Rank-statistic objectives such as AUC can be optimized efficiently because sparse trees contain relatively few tied-score leaves.
  • Contribution: GOSDT is a custom optimal decision-tree algorithm named Generalized and Scalable Optimal Sparse Decision Trees.Its framework builds on computational-reuse ideas while targeting a broader class of objectives than earlier methods.

2. Notation and Objectives

The paper represents trees as sparse sets of leaves and defines objectives through monotonic losses, including classification and rank-based criteria. Its dynamic-programming search uses hierarchical and specialized bounds to prune provably non-optimal partial trees.

  • Representation: A tree is represented as a set of distinct leaves, with each leaf specifying conditions and a label prediction.This representation stores the conditions leading to each leaf rather than the tree’s splits directly.
  • Objectives: The objective combines a training loss with a penalty on the number of leaves, controlled by regularization parameter λ.The framework considers losses monotonic in false positives and false negatives.
  • Objectives: Supported classification objectives include accuracy, balanced accuracy, weighted accuracy, and F-score, with weighted accuracy allowing cost-sensitive penalties.F-score optimization requires enforcing monotonicity by sweeping leaves from highest to lowest predictions.
  • Rank statistics: The rank-based objectives are AUC convex hull and partial AUC convex hull, where partial AUC focuses on the ROC curve’s leftmost region below a predetermined false-positive threshold.For binary leaf predictions, AUC equals balanced accuracy; real-valued leaf scores require ROC-convex-hull optimization.
  • Search bounds: For incomplete trees, the hierarchical lower bound compares a partial tree’s best possible loss with the current objective and prunes it when it is provably non-optimal.The framework adds bounds including equivalent-points, similar-support, incremental-progress, and subset bounds to reduce search.
  • Rank statistics: The method optimizes exact rank statistics directly on the training set rather than using convex proxies, while regularizing by sparsity.Convex proxies for rank statistics can produce results far from optimal.

3. Data Preprocessing Using Bucketization Sacrifices Optimality

Bucketization restricts candidate splits by disallowing splits between neighboring observations with the same label. The paper proves that this preprocessing can reduce the maximum attainable training accuracy.

  • Definition: Bucketization forbids splits between neighboring positive observations and between neighboring negative observations after ordering data by a feature.All other splits remain permitted under the stated preprocessing rule.
  • Optimality result: Bucketization can make the maximum training accuracy lower than the maximum accuracy available without preprocessing.This is stated as a theorem for decision trees trained on the same dataset.
  • Proof by construction: 93.5% accuracy is optimal without bucketization, compared with 92.2% under bucketization on the constructed dataset.BinOCT, DL8.5, and GOSDT all obtained these respective optimal values.
  • Scope: The construction uses a two-dimensional dataset, and the authors expect the optimality sacrifice to worsen with higher dimensions.The higher-dimensional claim is presented as an expectation rather than a proved result in the supplied passage.

4. GOSDT’s DPB Algorithm

GOSDT’s DPB algorithm optimizes decision-tree subproblems using support-set representations, bounds, dynamic programming, and asynchronous computation. These components enable reuse across equivalent or similar problems and support efficient pruning of the search space.

  • Asynchronous Bound Updates: GOSDT uses a priority queue and dependency graph to solve child problems asynchronously, update parent bounds before exact child objectives are known, and avoid unnecessary work.When bounds establish that a parent solution no longer depends on one child, computation can focus on another child problem.
  • Support Set Identification of Nodes: The algorithm represents support sets as bit-vectors and stores lower and upper bounds for the optimal objective associated with each problem.These bounds are initialized for new subproblems and used to determine whether further optimization is necessary.
  • Support Set Identification of Nodes: GOSDT identifies optimization problems by the support sets of samples satisfying feature conditions, solving all assertions that produce the same support set simultaneously.This avoids repeated processing because the optimal child-tree possibilities depend on the captured samples rather than the particular Boolean assertion.
  • Incremental Similar Support Bound: The incremental similar support bound removes many similar partial trees by comparing support differences and accounting for the hierarchical objective lower bound.For child trees of sufficiently similar roots, the objective difference is bounded by (ω + 2S_uncertain)ℓ_max.
  • Incremental Similar Support Bound: For continuous features, nearby split points can reuse computations from previously visited splits because descendants share many support sets.The support-set representation allows shared upper and lower-bound components to be updated simultaneously.
  • GOSDT’s DPB Algorithm: The algorithm constructs subproblems by splitting on features, keys them by support-set bit-vectors, and extracts the optimal tree by choosing the split with the lowest objective value.Keying by support sets prevents duplicate processing, unlike dynamic-programming implementations that may process the same problem multiple times.

5. Experiments

The experiments evaluate GOSDT across objectives, sparsity–accuracy trade-offs, and continuous-variable scalability. Results show strong accuracy with sparse trees and smaller slowdowns as threshold features increase.

  • Optimizing Many Different Objectives: GOSDT optimizes trees for six objectives, including accuracy, AUC, and partial area under the ROC convex hull.Different objectives produce different trees and false-positive/false-negative trade-offs.
  • Binary Datasets, Accuracy vs Sparsity: Training and test accuracy are compared across BinOCT, CART, DL8.5, GOSDT, and OSDT as functions of leaf count.The figures evaluate accuracy while varying tree sparsity.
  • Binary Datasets, Accuracy vs Sparsity: GOSDT directly optimizes the training accuracy–sparsity trade-off and typically achieves excellent training and test accuracy with relatively few leaves.The method produces points on the efficient frontier.
  • Continuous Datasets, Slowdown vs Thresholds: As the number of binary features increases, GOSDT typically slows down less than DL8.5 and OSDT.The smaller slowdown allows GOSDT to handle more thresholds introduced by continuous variables.
  • Continuous Datasets, Slowdown vs Thresholds: Appendix results report training times several orders of magnitude better than the state-of-the-art.The implementation used for the experiments is publicly available.

6. Discussion and Future Work

GOSDT provides sparse, interpretable decision trees with exact optimality information, while remaining most effective for small or medium feature sets. Future work targets broader objectives and further search-space acceleration.

  • Discussion: GOSDT produces sparse interpretable models and provides a proof of optimality for the non-convex optimization problem.It avoids convex proxies and solves the stated problem directly.
  • Discussion: GOSDT’s training-time evaluation concerns continuous variables encoded as binary features, with performance shown as a function of feature count.The associated figure uses λ = 0.3125 or maximum depth 5.
  • Discussion: If stopped early, GOSDT reports an optimality gap; it scales well with observations but is most effective for small or medium numbers of features.The algorithm can handle tens of thousands of observations.
  • Future Work: Future extensions include objectives with other monotonicities, fairness, ease-of-use, cost constraints, and additional search-space speedups.The authors identify exploration, garbage collection, and further bounds as acceleration directions.

A. Comparison Between Decision Tree Methods

This section presents the notation and bounding arguments used to compare and optimize decision-tree methods. The bounds support pruning partial trees and constraining the search over tree size and splits.

  • Tree Representation: A tree is represented by fixed and splittable leaves, together with their predicted labels and the number of leaves.This representation distinguishes leaves that cannot be further split from those still under consideration.
  • Objective Lower Bounds: For monotonic losses, the hierarchical lower bound uses false positives, false negatives, and the leaf penalty to lower-bound a tree’s risk.The loss is assumed to increase monotonically in false positives and false negatives.
  • Objective Lower Bounds: If a node’s lower bound plus the cost of another leaf reaches the current best objective, all child trees can be pruned as suboptimal.The bound applies even before the child trees are fully constructed.
  • Leaf and Split Bounds: The framework includes upper bounds on the number of leaves and incremental-progress bounds that constrain optimal tree size and splitting decisions.An internal node contributing less than λ in loss cannot belong to an optimal tree under the stated conditions.

B.6. Similar Support Bound

The similar support bound compares trees that differ at one split by bounding the objective difference caused by observations captured differently. This bound supports pruning among alternative child subtrees.

  • Bound Definition: The bound applies to two trees identical except for the feature used at one internal split.The differing observations are those captured by only one of the corresponding subtrees.
  • Bound Definition: γ bounds the objective difference by maximizing the loss change over all possible assignments of the observations captured differently.The construction varies the number of additional false positives from 0 through |ω|.
  • Bound Consequence: The resulting inequality is −γ ≤ R(d, x, y) − R(D, x, y) ≤ γ.Thus, the two trees’ objectives differ by at most γ in either direction.
  • Bound Consequence: The same bound transfers to the best child trees of the two alternatives, enabling comparisons during dynamic-programming search.The corresponding child objectives remain within γ under the stated construction.

C. Objectives and Their Lower Bounds for Rank Statistics

The section develops rank-statistic analysis for AUCch, showing that splitting an impure leaf cannot reduce the ROC convex hull area and increases it when leaf rankings change. It also derives bounds by comparing ROCCH areas before and after splitting.

  • Rank-order cases: The analysis considers four possible relative positions of the two child leaves after splitting a ranked parent leaf.Each case specifies whether the children move before, at, or after the parent’s original position.
  • AUCch derivation: For each rank-order case, the change in AUCch is computed from differences between shaded rectangle and triangle areas under the two ROC convex hulls.Figure 8 maps the terms in each expression to colored geometric regions before and after splitting.
  • AUCch derivation: The resulting positive increments establish that AUCch increases across all rank-changing cases.The proofs reduce each case to inequalities implied by the ordering of parent and child leaf scores.
  • AUCch monotonicity: Splitting an impure leaf does not decrease AUCch, and it increases AUCch when the split changes leaf rank order.If child leaves retain the same rank order, AUCch is unchanged; otherwise the increase is positive.
  • Lower bounds: A bound is obtained by comparing the convex-hull area of a tree with the hypothetical maximum obtained when all newly generated leaves are pure.The proof expresses the bound through ROCCH rectangles and triangles associated with positive and negative samples.

D. Optimizing F-score with Decision Trees

F-score optimization is difficult because its loss is non-additive across leaves: the best label for one leaf depends on labels assigned elsewhere. The section therefore adapts labeling and recursive optimization procedures to handle this coupling.

  • F-score coupling: F-score loss cannot be computed as a sum of independent leaf losses because false positives and false negatives appear in both numerator and denominator.This distinguishes F-score from accuracy, balanced accuracy, and weighted accuracy objectives.
  • F-score coupling: The predicted label of one leaf depends on the labels of other leaves and on the positive and negative samples captured by that leaf.The comparison between assigning label 1 or 0 uses the errors accumulated in the other leaves.
  • F-score coupling: A labeling that gives lower loss on the first H_d−1 leaves is not guaranteed to minimize the complete tree’s F1 loss.The final leaf’s contribution can reverse the ordering between two partial labelings.
  • F-score handling: The method addresses this challenge by enforcing monotonicity through a sweep across leaves ordered from highest to lowest predictions.The sweep is used to calculate F-score while avoiding inconsistent label assignments across ranked leaves.
  • Recursive optimization: The optimization decomposes the tree problem into a leaf base case and feature-specific recursive tree cases over strict subsets of the data.Bit-vector representations identify previously visited subsets so reusable subproblems can be recognized during recursion.

F. Incremental Similar Support Bound Proof

The incremental similar support bound removes redundant branches by comparing trees whose root splits differ only slightly in support. Its tightness depends on how many observations change sides and how much of the tree remains uncertain.

  • Bound definition: The incremental similar support bound prunes many similar trees by examining only one representative from a group of trees with comparable supports.The bound applies when root branches differ by at most an ω fraction of observations.
  • Bound definition: S_uncertain is defined as the maximum support among the split leaves of the two compared trees.This quantity captures the portion of the tree whose future refinement can still change the objective.
  • Bound implication: Any child trees generated from the two similar parents have objective values constrained by the bound whenever they are not already excluded by the hierarchical objective lower bound.The comparison applies to descendants grown from the respective split leaves.
  • Bound implication: The bound becomes tighter when most of the tree is fixed, because less uncertain support remains to affect the loss.Its looseness increases with the support affected by changing the top split and with the remaining uncertain portion.
  • Proof structure: The proof decomposes the objective difference into changes on moved observations, fixed leaves, and descendant split leaves, then combines the three bounds with the triangle inequality.This yields the final bound from separate controls on each source of objective variation.

G. Subset Bound Proof

The subset bound exploits nested supports created by different thresholds of a continuous feature to reduce recursive comparisons. The section also situates this pruning within the broader search complexity and experimental evaluation.

  • Subset bound: The subset bound removes thresholds from the continuous-feature search space by comparing trees with the same root node and nested child supports.It is stated for additive losses and uses optimal subtrees on the respective supports.
  • Subset bound: When two thresholds produce nested right-hand supports, only the corresponding left subtrees need to be developed and compared.For example, a stricter threshold can create a support contained within that of a less strict threshold.
  • Search complexity: The number of binary decision trees has complexity O(M!).The recurrence f(M)=2M f(M−1) yields f(M)=2^M M! K for M binary features and K classes.
  • Experimental setup: The experiments evaluate the approach on 11 datasets, including UCI, LIBSVM, COMPAS, FICO, and coupon data.Continuous variables are commonly discretized using thresholds between adjacent observed values.
  • Experimental results: Different objectives produce different ROC curves and sparsity levels, while pAUCch can preserve left-ROC performance and trade away less relevant middle and right areas for sparsity.The results also report cases where a single split gives a strong TPR/FPR tradeoff.
  • Experimental results: GOSDT or OSDT reliably produces a more efficient training-accuracy-versus-leaf-count frontier than the compared solutions.When training accuracies differ, the frontier advantage can also appear in test accuracy; when CART is nearly optimal, test differences may be insignificant.

I.7. Experiment: Scalability

The scalability experiment evaluates runtime as binary-feature and sample counts increase, finding that GOSDT generally handles harder continuous datasets more effectively than competing methods. Its advantage is especially clear over DL8.5, while implementation language affects comparisons.

  • Experimental setup: The experiment measures runtime by varying binary-feature count and sample size across four datasets requiring 14, 85, 647, and 1,407 binary features.Training time measures completion with an optimality certificate, while slow-down normalizes against the fastest method.
  • Sample scaling: For bar-7 and compas-2016, runtime grows logarithmically with sample size, giving GOSDT, PyGOSDT, and OSDT a significant advantage over DL8.5.These datasets are sufficiently represented at small sample sizes, so additional samples increase difficulty only modestly.
  • Feature scaling: Runtime grows approximately factorially with feature count, but GOSDT usually supports a higher practical problem-size limit than other full-tree optimizers.The result is consistent with the theoretical worst-case complexity of full tree optimization.
  • Comparative scalability: GOSDT, OSDT, and PyGOSDT outperform DL8.5 increasingly clearly as dataset difficulty rises, with GOSDT slightly ahead of OSDT on larger datasets.The comparisons concern the reported runtime behavior under the experiment’s configurations.
  • Implementation effects: GOSDT is several orders of magnitude faster and more scalable than DL8.5 in the C++ comparison, while PyGOSDT is less performant than Python OSDT.The paper notes that previous comparisons did not account for implementation-language differences.
  • Optimization progress: GOSDT and PyGOSDT generally complete optimality certificates earlier than OSDT, although PyGOSDT can progress less smoothly before a sharp final improvement.PyGOSDT lacks high-priority bound updates, whereas GOSDT and OSDT aggressively lower the best observed objective score.

I.10. Summary of Experimental Results

The experiments show that GOSDT combines broader objective optimization with efficient sparse-tree search and stronger handling of continuous-feature encodings. Across the reported comparisons, it produces accurate sparse models, scales to more binary features, and improves optimality guarantees under time limits.

  • Objective functions: GOSDT optimizes objectives including ROC efficiency beyond the standard accuracy objective used by other algorithms.Experiment G.5 reports more efficient ROC curves from the broader objective set.
  • Accuracy and sparsity: Under time constraints, GOSDT produces more highly accurate models along the regularized training-accuracy-versus-sparsity frontier than OSDT.The regularized risk objective used by both methods produces the most efficient reported frontier.
  • Continuous variables: GOSDT handles significantly more binary features than BinOCT, DL8.5, and, to a lesser extent, OSDT, supporting higher-cardinality continuous datasets.The binary features encode thresholds over continuous features.
  • Optimality guarantees: GOSDT reduces the optimality gap faster than OSDT and PyGOSDT, enabling stronger optimality guarantees when runs terminate prematurely.This result concerns the algorithm’s ability to certify solutions under incomplete runs.
  • Model structure: Under equal sparsity constraints, GOSDT captures the ground truth more accurately than BinOCT.The comparison links efficient accuracy-versus-sparsity optimization with recovery of the generating model.

J. Algorithm

The algorithm searches a dependency graph of support-set subproblems using lower and upper bounds, priority-based expansion, and recursive tree extraction. Bound updates propagate through parent nodes until the root is solved or the best available tree is extracted.

  • Algorithm components: GOSDT combines a main optimization algorithm with lower-bound, upper-bound, bound-failure, splitting, and tree-extraction subroutines.The extraction routine constructs the optimal tree from the dependency graph after optimization completes.
  • Search procedure: The main procedure initializes a root support set, inserts it into a priority queue and dependency graph, and expands unresolved problems until the root bounds coincide.Solved nodes are skipped, while bound updates can propagate to parent problems and reprioritize them.
  • Bounding: Lower bounds estimate risk from independently assigning classes to equivalence classes, while upper bounds evaluate leaf predictions and complexity penalties.The bounds use positive and negative class weights associated with equivalence classes.
  • Pruning: The failure test closes a problem when incremental or leaf-accuracy bounds show that further descendants cannot improve the current solution.In that case, the problem’s lower and upper bounds are set equal, preventing additional splitting.
  • Splitting: Splitting maps a support set into left and right child keys by selecting samples whose feature value is respectively 0 or 1.The split routine returns the two support subsets for recursive optimization.
  • Tree extraction: Tree extraction compares the leaf risk with candidate split risks, returning a leaf when stopping is better and otherwise recursing on the best split’s children.The resulting node is either a predicted leaf or a split containing left and right subtrees.
Loading 2006.08690v4…