PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction

Jiancheng Tu, Wenqi Fan

arXiv:2609.05826v1cs.LG

TL;DR

Dynamic-programming optimal classification trees become costly as feature and sample counts grow. The paper combines weighted aggregation after candidate projection with adaptive refinement of bounded feature sets. Experiments report substantial speedups for Weighted STreeD and lower runtime for Adaptive STreeD in matched comparisons, while its full-feature search remains heuristic.

  • Problem

    STreeD's computational cost increases with candidate-feature and training-sample counts, making dynamic programming costly for larger instances.

    Source: §1 · p. 2

  • Method

    The framework combines lossless weighted aggregation for fixed candidate sets with adaptive refinement of bounded candidate sets and rebuilding of the weighted representation.

    Source: §1 · p. 2

  • Results

    Across five data sets, Weighted STreeD achieved speedups of up to 121.41× over standard STreeD, while Adaptive STreeD reduced runtime at depths 2–4 and returned feasible trees at greater depths.

    Source: §1 · p. 2, §6 · p. 18

  • Takeaways & Limitations

    Joint feature- and sample-space reduction improves scalability while each certified inner solution is optimal only for its current candidate set.

    Source: §6 · p. 18

    Adaptive STreeD does not guarantee full-feature optimality because its feature-proposal procedure may omit features used by an optimal tree.

    Source: §6 · p. 18

Abstract

from arXiv · show

Dynamic programming for optimal classification trees becomes computationally expensive as the numbers of features and training samples increase. We develop a joint feature- and sample-space reduction framework based on STreeD. Weighted STreeD merges duplicate records created after projection onto a fixed candidate set into weighted representatives. This reduces sample-dependent computation without changing the fixed-candidate optimization problem. Adaptive STreeD repeatedly refines a bounded candidate set, retains features used by the incumbent tree, rebuilds the weighted representation, and solves the resulting reduced problems. Each certified Weighted STreeD solution is optimal for its current candidate set, while the outer feature search remains heuristic over the full feature space. Experiments on five data sets show that Weighted STreeD achieves speedups of up to 121.41 times over standard STreeD. Adaptive STreeD reduces runtime in matched comparisons at depths 2 to 4 and continues to return feasible trees at greater depths where full-feature methods are limited by time or memory. Under the same computational budget, its predictive performance remains comparable to the evaluated optimal classification tree baselines and is higher in some comparisons. These results show how joint feature- and sample-space reduction can scale dynamic-programming-based optimal-tree learning to more demanding instances.

1 Introduction

The paper addresses the scaling costs of dynamic-programming optimal-tree learning by jointly reducing candidate features and training records. It introduces fixed-candidate weighted aggregation and adaptive candidate refinement, with different optimality guarantees for the two methods.

1 Introduction

  • STreeD's computational cost grows with candidate-feature and training-sample counts, especially after preprocessing creates high-dimensional binary features.More features increase states and split evaluations, while many states repeatedly process training records.Source: §1 · p. 2
  • Weighted STreeD merges duplicate records after projection onto a fixed candidate set, yielding a lossless reformulation for that set.Restricting candidates reduces split enumeration and can create additional duplicates for weighted aggregation.Source: §1 · p. 2
  • Up to 121.41× speedups over standard STreeD were achieved by Weighted STreeD; Adaptive STreeD reduced runtime at depths 2–4 and returned feasible trees at greater depths.Under the same computational budget, Adaptive STreeD's predictive performance remained comparable to evaluated optimal-tree baselines.Source: §1 · p. 2
  • Adaptive STreeD iteratively refines bounded candidate sets, retains incumbent-tree features, and rebuilds the weighted representation.Each certified Weighted STreeD solution is optimal for its fixed candidate set, whereas Adaptive STreeD's search over the full feature space remains heuristic.Source: §1 · p. 2

2 Related Work

The related work spans exact optimal-tree optimization, data and feature reduction, and methods that seek high-quality trees under limited computational budgets. The paper distinguishes its candidate-space refinement and weighted aggregation from these approaches by their reduction targets and guarantee scope.

2.1 Optimal Classification Trees

  • Exact optimal-tree methods include mixed-integer, dynamic-programming, SAT/MaxSAT, constraint-programming, and branch-and-bound approaches.Mixed-integer formulations jointly model tree structure, splits, and leaf predictions, while column-generation and path-based methods generate rules or paths as needed.Source: §2.1 · p. 2
  • Dynamic-programming methods reuse recursive subproblems through caching and bounds, with approaches including DL8.5, MurTree, OSDT, GOSDT, and STreeD.Other lines include AND/OR or AO* search and methods specialized for continuous features.Source: §2.1 · pp. 2–3

2.2 Data and Feature Reduction

  • Prior data-reduction methods exploit repeated or indistinguishable records, while GOSDT and WFlowOCT aggregate records in fixed representations or flow-based models.Weighted STreeD defines duplicates after projection onto the current candidate set, so candidate restriction can create more duplicates; it rebuilds the weighted data when that set changes.Source: §2.2 · p. 3

2.3 Near-Optimal Classification Trees

  • Adaptive STreeD solves sequential bounded candidate-set problems and rebuilds weighted data, unlike feature-reduction methods that do not generally ensure selected features include those of a full-feature optimum.Compared with near-optimal search that retains the full feature space or restricts tree structure or search order, it certifies each inner solve only for its current candidates; full-feature optimality is recovered only under the stated visited-set and solve conditions.Source: §2.2 · p. 3, §2.3 · p. 3

3 Weighted Unique-Data Dynamic Programming

This section develops a weighted reformulation of STreeD for fixed candidate sets and analyzes its equivalence and computational implications. Its guarantees depend on retaining task-relevant information, and its sample-space savings do not remove the tree-search factors.

3.1 Problem Setting

  • The problem setting fixes a post-binarized feature set, candidate subset, and feasible tree class; training accuracy is optimized by minimizing misclassification count.Separable tasks permit subtree solutions to be determined independently of outside-subtree decisions, and the stored statistics must retain information used by the task's dynamic program.Source: §3.1 · p. 4

3.2 STreeD Dynamic Programming Baseline

  • The baseline STreeD recursion caches visited states and enumerates records, splits, and tree budgets; its stated complexity bounds are accounting bounds, not runtime predictions.The space expressions exclude the input feature matrix, returned trees, and auxiliary solver statistics.Source: §3.2 · p. 5

3.3 Weighted STreeD

  • Weighted STreeD represents duplicate projected records with weighted representatives and applies the fixed-candidate recursion using task-preserving sufficient statistics.For training accuracy, projected features and class labels suffice; for nonlinear separable objectives such as F1, weighted counts must reproduce the required confusion-matrix statistics.Source: §3.3 · pp. 6–7
  • For a fixed candidate set, the weighted reformulation preserves the optimization problem for separable tasks when the aggregation key retains all task-relevant information.Each feasible tree has the same task statistics and value in the original and weighted representations, so the fixed-candidate problems have the same optimal value and optimal trees.Source: §3.3 · p. 6
  • Replacing original-sample terms with weighted-record terms can reduce record-processing work and bitset length, but candidate, depth, and node-budget factors remain.The ratio n/u_S approximates sample-scanning and storage reductions only when comparable compression persists across visited states; it is not a wall-clock speedup, and aggregation is repeated for each changed candidate set.Source: §3.3 · pp. 7–8

4 Adaptive STreeD

Adaptive STreeD repeatedly solves bounded feature sets, preserving incumbent features while projecting and aggregating records into weighted representatives. Its inner solve can be certified for each set, but full-feature optimality depends on visiting the right support and certifying that reduced problem.

4.1 Candidate-Refinement Algorithm

  • Each iteration retains incumbent features, proposes additional candidates with repeated CART fits, then projects, aggregates, and solves the reduced problem with Weighted STreeD.Random forests initialize the candidate set; random forests and CART propose features but do not provide optimality guarantees.Source: §4 · p. 8, §4.1 · p. 9

4.2 Joint Feature- and Sample-Space Reduction

  • Candidate capacity K reduces split enumeration and can increase duplicate projected records, enabling joint feature- and sample-space reduction.The inner dynamic program depends on K rather than the full feature dimension p, while feature proposal, projection, and aggregation still use the original data.Source: §4.2 · p. 10, Figure 1 · p. 11
  • The n/u_t and H_D(p)/H_D(q_t) ratios describe reductions in sample- and feature-dependent dynamic-programming components, not guaranteed total wall-clock speedups.The complete procedure still depends on the original sample size n and feature dimension p.Source: §4.2 · p. 10

4.3 Conditional Solution-Quality Analysis

  • Full-feature optimality is conditional: a visited candidate set must contain an optimal tree’s split features, and its reduced problem must be solved to certified optimality.The outer candidate refinement remains heuristic over the full feature space.Source: §4 · p. 8, §4.3 · p. 11
  • The quality bound depends on baseline ratio r_0, completed iterations N, and support-coverage bounds ρ_t; candidate capacity trades broader feature coverage against harder reduced problems.Random-forest and CART importance scores rank candidates but are not estimates of the coverage probabilities ρ_t.Source: §4.3 · p. 12

5 Computational Experiments

Across five data sets, the experiments compare Adaptive STreeD with tree-learning baselines, isolate fixed-candidate weighted aggregation, and assess candidate-set capacity. Adaptive STreeD scales better at greater depths, while weighted aggregation and candidate capacity expose tradeoffs between runtime and predictive performance.

5.1 Experimental Setup

  • The experiments use five public tabular data sets, five independent 80/20 train–test splits, and a 600-second time limit per configuration.Continuous features are quantile-binned into at most 100 intervals; categorical features are one-hot encoded.Source: §5.1 · p. 13

5.2 Overall Computational Performance

  • At depths 2–4, Adaptive STreeD’s median runtimes are 5.38, 12.70, and 17.84 seconds, versus 7.19, 98.48, and 607.11 seconds for full-feature STreeD.The corresponding runtime ratios are 1.34×, 7.75×, and 34.02×; the depth-4 ratio is capped because many full-feature runs reach the time or memory limit.Source: §5.2 · p. 14, Figure 2 · p. 14
  • Across reported comparisons, Adaptive-minus-STreeD differences average −0.0553 percentage points for training accuracy and 0.08 percentage points for test accuracy; these differences are descriptive, with no statistical significance claimed.For Transactions at depth 4, under the same 600-second budget, Adaptive STreeD obtains higher predictive performance than full-feature STreeD and DL8.5 by searching a reduced feature space.Source: §5.2 · p. 15
  • Adaptive STreeD returns feasible trees at depths 5–7, where full-feature STreeD does not, and its predictive performance remains comparable to evaluated optimal-tree methods under the same budget.On the largest data set, it achieves higher predictive performance within that budget; this finite-budget comparison does not imply a certified full-feature optimum would score lower.Source: §5.2 · pp. 14–15

5.3 Fixed-Candidate Weighted Aggregation

  • Weighted STreeD is faster in 100 of 150 matched fixed-candidate cases, with an arithmetic-mean speedup of 8.20× and a maximum of 121.41×.Training misclassification is identical in 138 of 150 cases; all 12 differences occur in time-limited runs, where Weighted STreeD obtains a better incumbent.Source: §5.3 · p. 16, Table 2 · p. 16, Figure 4 · p. 17
  • Weighted aggregation is faster in every matched case from depth 4 onward; its largest gains tend to occur at smaller candidate-set sizes, which create more duplicate records.Compression and log speedup have a Spearman correlation of 0.342, so a larger compression ratio does not imply an equally large wall-clock speedup.Source: §5.3 · p. 16

5.4 Sensitivity to Candidate-Set Capacity

  • Pooled median runtime rises from 10.48 seconds at K=20 to 32.03 seconds at K=40, with a median matched runtime ratio of 2.433×.At depth 6, the median matched runtime ratio for K=40 relative to K=20 reaches 7.75×; seven planned runs are unavailable, only at larger capacities and depths.Source: §5.4 · p. 17, Figure 5 · p. 18
  • Relative to K=20, mean matched test-accuracy differences range from −0.127 percentage points at K=10 to +0.122 percentage points at K=40.Increasing K modestly improves average predictive performance compared with its runtime effect, but additional feature coverage does not necessarily improve test accuracy at every depth.Source: §5.4 · pp. 17–18

6 Conclusion

The paper pairs weighted aggregation with adaptive candidate refinement to scale dynamic-programming-based optimal classification trees, while distinguishing fixed-candidate optimality from heuristic full-feature search. Experiments show runtime gains and comparable predictive performance, but Adaptive STreeD does not guarantee full-feature optimality.

6 Conclusion

  • Weighted STreeD aggregates duplicate projected records, while Adaptive STreeD refines bounded candidate sets and preserves incumbent-tree features.Certified inner solutions are optimal for their current candidate sets, but the outer search remains heuristic over the full feature space.Source: §6 · p. 18
  • Across five data sets, Adaptive STreeD reduces runtime in matched comparisons at depths 2–4 and remains feasible at greater depths; Weighted STreeD reaches a maximum 121.41× speedup.Adaptive STreeD has comparable predictive performance to evaluated optimal-tree methods under the same budget; Transactions has higher predictive performance than full-feature methods in a finite-budget comparison.Source: §6 · p. 18
  • Adaptive STreeD may omit features used by a full-feature optimum, so it does not guarantee full-feature optimality.Its performance also depends on candidate capacity, time allocation, and stopping rules; reducing feature and sample spaces does not remove the combinatorial dependence on depth.Source: §6 · p. 18
  • Fixed-candidate equivalence is separately established for separable tasks satisfying the information-preservation condition.Future work includes safe feature screening, stronger full-space bounds, adaptive candidate capacities, and extensions beyond the current analysis scope.Source: §6 · p. 19

A Binning Sensitivity

The binning sensitivity study isolates preprocessing resolution using Weighted STreeD and finds that finer binning substantially raises computational cost, while predictive effects are small and non-monotone. A 100-bin cap preserves a richer threshold universe, whereas a smaller cap can be computationally attractive but coarser.

A Binning Sensitivity

  • The study compares B∈{5, 10, 20, 50, 100} across five data sets and depths 2–4, using one fixed 80/20 train–test split.Adaptive candidate refinement is not used, isolating the effect of preprocessing resolution; accuracy differences are descriptive rather than estimates across random splits.Source: A Binning Sensitivity · p. 22
  • As B rises from 5 to 100, pooled median runtime increases from 1.50 to 119.71 seconds, while depth-4 median runtime rises from 7.74 to 609.26 seconds.Runs at or above 599 seconds increase from 6.7% to 33.3%; depth-4 observations near the budget are censored, not uncensored runtime measurements.Source: Table 3 · p. 22, A Binning Sensitivity · p. 22
  • Finer binning increases binary features from 100.8 to 512.0 on average and lowers median compression from 1.28 at B=5 to 1.01 at B=100.More candidate features expand the search space while leaving fewer duplicate projected records for aggregation.Source: A Binning Sensitivity · p. 22
  • Mean test accuracy rises by approximately 0.50 percentage points from B=5 to B=20, but B=20 and B=100 differ by only 0.02 percentage points in favor of B=20.The fixed-split sensitivity study does not identify 100 bins as a predictive optimum.Source: A Binning Sensitivity · p. 23, Figure 6 · p. 23
  • Bin100 serves as a conservative preprocessing cap, while a smaller cap such as B=20 offers similar predictive performance in this fixed-split experiment but may discard thresholds before optimization.The 100-bin value is an upper bound, not a requirement that each feature produce 100 distinct bins; K instead limits the active feature set during optimization.Source: A Binning Sensitivity · pp. 22–23

B Supplementary Method Details

The supplementary method details state the fixed-representation convention and show the baseline STreeD recursion for selecting a tree under depth and node-budget constraints.

B.1 Notation

  • The notation section treats the candidate set and post-binarized feature representation as fixed within each dynamic-programming solve.Table 4 is identified as notation for the weighted unique-data dynamic program.Source: §B.1 · p. 24, Table 4 · p. 24

B.2 Baseline STreeD Recursion

  • Baseline STreeD caches states, initializes the best leaf, evaluates nonempty candidate-feature splits, allocates the remaining node budget across child recursions, and retains the best tree.The recursion stops when remaining depth or internal-node budget reaches zero.Source: §B.2 · p. 25

C.1 Complete Candidate-Capacity Results

The candidate-capacity results are reported relative to K=20, and the proof details account for per-state computation, total runtime, and cache space.

C.1 Complete Candidate-Capacity Results

  • The candidate-capacity results report runtime as median [interquartile range], accuracy as mean ± sample standard deviation, and matched ratios and accuracy differences relative to K=20.The runtime ratio is the median of within-block ratios, not the ratio of pooled median runtimes.Source: Table 5 · p. 25, §C.1 · p. 25

D.1 Proof of Proposition 1

  • For a cached state, the stated conservative accounting includes class-count work O(|K|n_A), candidate-split work O(qn_A), and budget allocation work O(qm).The budget-allocation term applies once child values are available.Source: §D.1 · p. 26
  • The runtime bound sums per-state work over the state set, using a worst-case path-state bound and the limits n_A≤n and m≤M.The path-state count is bounded using nonredundant paths that fix binary features and outcomes.Source: §D.1 · p. 26
  • The space bound assigns O(n/b) machine words to a bitset for each record subset and sums storage over cached states.Input feature matrix, returned trees, and auxiliary solver statistics are excluded.Source: §D.1 · p. 26

D.2 Proof of Proposition 2

For a fixed candidate set, duplicate observations have identical task information and follow the same tree path, so their contributions can be represented by weighted groups. This preserves each feasible tree’s task statistics, objective value, and feasibility, leaving the fixed-candidate optimization problem unchanged.

D.2 Proof of Proposition 2

  • Observations in each projected group share the same features, label, and record-level task information, so every tree using that candidate set sends them to the same leaf.Their sufficient-statistic contributions are therefore identical within each group.Source: §D.2 · p. 26
  • Summing each group’s common sufficient-statistic contribution with its group weight preserves the total task statistics of every feasible tree.The groups partition the original data, and each group’s size is its weight.Source: §D.2 · p. 26
  • Because tree-only terms are unchanged, the original and weighted fixed-candidate problems give every feasible tree the same objective value and feasibility status.Consequently, they have the same optimal value and the same set of optimal trees.Source: §D.2 · p. 26

D.3 Proof of Corollary 1

The weighted and unweighted recursions agree on optimal misclassification count for a fixed candidate set. Aggregation also changes the sample representation without changing the candidate features or possible feature–outcome paths, which underlies the stated state and space bounds.

D.3 Proof of Corollary 1

  • Aggregation-preserving bounds and pruning retain the correspondence, so weighted and unweighted recursions return the same optimal misclassification count over the fixed-candidate tree class.The proof matches leaf costs, split features, child-state allocations, and recursive values.Source: §D.3 · p. 27

D.4 Proof of Proposition 3

  • Aggregation leaves the logical path-state bound at H_D(q), since it changes record representation but not candidate features or possible feature–outcome paths.The space analysis uses bitsets over u_S weighted records; it excludes storage for the weighted input table, returned trees, and auxiliary solver statistics.Source: §D.4 · p. 27

D.5 Proof of Proposition 4

These proofs bound sample-scanning and bitset costs under stated correspondence and compression assumptions, then establish conditions for optimal-score recovery and properties of Adaptive STreeD’s incumbent and stopping rules.

D.5 Proof of Proposition 4

  • When corresponding states have compression ratios close to the root-level ratio, the sample-scanning bound follows; for bitsets, the per-state space ratio approaches n/u_S when both bitset sizes are large.The sample-scanning comparison excludes the q m budget-allocation terms.Source: §D.5 · p. 28

D.6 Proof of Proposition 5

  • For ordinary classification with binarized candidate features, each iteration’s projected vectors are bounded by 2^q_t and labels by |K|; the proposition’s bound starts after candidate-set construction and aggregation.Random-forest or CART fitting, projection, and aggregation are accounted for separately.Source: §D.6 · p. 28

D.7 Proof of Proposition 6

  • A certified solve of a covered reduced problem can attain the full-feature optimum’s score, which incumbent preservation retains.The reduced tree class is a subset of the full-feature tree class.Source: §D.7 · p. 29

D.8 Proof of Corollary 2

  • The best constant-leaf tree initializes the incumbent at score π_max, and the algorithm never replaces it with a worse solution.Thus the baseline condition holds with r_0 = π_max.Source: §D.8 · p. 29

D.9 Verification of the Algorithmic Properties

  • Adaptive STreeD runs at most N_max iterations, keeps a nondecreasing incumbent score, and retains the best feasible tree when an inner solve is unsuccessful.A certified Weighted STreeD solve is optimal only over its active candidate set, not over the full feature set.Source: §D.9 · p. 30
Loading 2609.05826v1…