Research map / Learning theory and algorithms / Combinatorial and search optimization
Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces ConTree, a dynamic programming plus branch-and-bound algorithm that learns optimal axis-aligned classification trees directly on continuous features via three similarity-based pruning rules and a fast depth-two subroutine.
Problem
Computing optimal classification trees of bounded size on continuous features is NP-hard and existing optimal methods either need binarization (losing optimality or scaling poorly) or scale only to shallow depth (around depth three).
Approach
Exploits sorted numeric features so that the similarity-based lower bound between subproblems is computed in O(1) from split index differences, enabling three novel pruning rules (neighborhood pruning, interval shrinking, sub-interval pruning) and a sorted-data depth-two subroutine that avoids quadratic memory.
Key results
- Depth-two subroutine speeds up computation by a factor of 320 (geometric mean) versus the no-D2 variant; pruning techniques cut D2Split calls by 99.6% with sub-interval pruning alone.
- For depth three, ConTree is on average 63x faster than Quant-BnB (geometric mean), ranging from 7x (Bidding) to 266x (Fault); Quant-BnB needs over 4h on Fault while ConTree takes 55 s.
- Out-of-sample depth-three accuracy averages 4.7% higher than CART and 0.7% higher than optimal trees on quantile-binarized data.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add neighborhood pruning (ablation) | ConTree · Depth 2 | D2Split calls pruned: 91.1% | Helped |
| add interval shrinking (ablation) | ConTree · Depth 2 | D2Split calls pruned: 97.5% | Helped |
| add sub-interval pruning (ablation) | ConTree · Depth 2 | D2Split calls pruned: 99.6% | Helped |
| combine neighborhood pruning, interval shrinking, and sub-interval pruning instead of using sub-interval pruning alone (ablation) | ConTree · Depth 2 | D2Split calls: 10% reduction | Helped |
| add the depth-two D2Split subroutine (ablation) | ConTree · Depth 2 | computation time: 320 | Helped |
| allow a 1% optimality gap rather than requiring an optimal solution (ablation) | ConTree · Depth 4 | runtime | Helped |
| allow an optimality gap rather than requiring an optimal solution (ablation) | ConTree · Depth 5 and depth 6 | training accuracy | Mixed |
| optimize continuous feature thresholds directly rather than using quantile binarization | ConTree · Out-of-sample, depth 3, UCI datasets | accuracy: 0.7% higher | Helped |
| optimize continuous feature thresholds directly rather than using threshold-guessing binarization | ConTree · Out-of-sample, depth 3, UCI datasets | accuracy: 1.0% higher | Helped |
| optimize continuous feature thresholds directly rather than use CART | ConTree · Out-of-sample, depth 3, UCI datasets | accuracy: 4.7% higher | Helped |
Surprising findings
- Using a permitted optimality gap sometimes yields higher final training accuracy at depth five and six, because pruning frees time for more of the search space.
- Interval-based pruning of a fixed-depth search can perform worse when the right upper bound is set tightly, so a hybrid upper bound was chosen empirically.
Limitations
- Depth-four search still times out on several datasets (e.g., Eeg, Bean, Magic), and the Skin dataset needs large memory at deeper depths.
- Only binary axis-aligned trees with classification objective; regression and node costs are future work.
- Anytime behaviour: good solutions are found early but most time is spent proving optimality.
Experimental setup
Datasets: Avila Bank Bean Bidding Eeg Fault Htru Magic Occupancy Page Raisin Rice
Benchmarks: UCI repository datasets (16)
Metrics: runtime (s) memory (MB) optimality gap out-of-sample accuracy (%) number of D2Split calls
Baselines: OCT RS-OCT SAT-Shati Quant-BnB CART STreeD
Builds on: DL8.5 Quant-BnB similarity-based lower bound GOSDT STreeD
Closest papers by meaning
- Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.87)
- Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach (ICML 2024 · similarity 0.87)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.86)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.86)
- Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.86)
- Literati: Towards Anytime Optimal Shape Generalized Trees via AO* (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.