Research map / Learning theory and algorithms / Combinatorial and search optimization
Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO*
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.
Proposes Branches, an AO*-type best-first search over an AND/OR graph of branches that finds optimal sparse decision trees (accuracy minus lambda times splits), with a Purification Bound heuristic, optimality proof and complexity bound, and supports non-binary (multi-way) splits.
Problem
Learning optimal sparse decision trees that jointly maximise accuracy and minimise the number of splits; existing exact methods are either DFS (needs max depth, uninformed) or BFS (high memory, not exploiting AND/OR structure).
Approach
Formulate sparse DT learning as an AND/OR graph search solved with AO*, using a novel Purification Bound heuristic that upper-bounds the value of any sub-tree rooted at a branch, plus a focused selection strategy; supports non-binary ordinal splits natively.
Key results
- Branches matches optimal objective on all datasets where others terminate and is faster than GOSDT on most, e.g. car-eval finishes in 204s while GOSDT times out at 5 minutes.
- Branches is the only method supporting ordinal (non-binary) encodings; all ordinal experiments terminate, with the slowest (lymph-o) at 12.3s.
- Theoretical complexity bound on branch evaluations is numerically much smaller than OSDT's bound (e.g. 10^4 vs 10^13 for q=10, lambda=0.1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Branches instead of GOSDT | Sparse decision tree search · monk1 | time (s): 3.05 -> 0.05 | Helped |
| Use Branches instead of GOSDT | Sparse decision tree search · monk3 | time (s): 25.2 -> 4.05 | Helped |
| Use Branches instead of GOSDT | Sparse decision tree search · car-eval | time (s): TO -> 204 | Helped |
| Use GOSDT instead of Branches | Sparse decision tree search · balance-f | time (s): 162 -> 190 | Hurt |
| Use Branches instead of GOSDT | Sparse decision tree search · tic-tac-toe | objective: 0.757 -> 0.838 | Helped |
| Use STreeD instead of Branches | Sparse decision tree search · mushroom | time (s): TO -> 10.8 | Helped |
| Use ordinal rather than binary encoding | Branches · monk3 | objective: 0.985 -> 0.987 | Helped |
| Use ordinal rather than binary encoding | Branches · lymph | time (s): TO -> 12.3 | Helped |
| Use ordinal rather than binary encoding | Branches · Sparse decision tree search | objective | Mixed |
| Use Branches instead of GOSDT | Sparse decision tree search · balance | objective: 0.712 -> 0.776 | Helped |
Surprising findings
- Branches on mushroom and mushroom-f times out while STreeD terminates in about 11s and 126s, attributed to STreeD's depth-2 solver.
- MurTree's pymurtree implementation was suboptimal in the objective on several datasets.
Limitations
- Best-first search has high memory consumption and may run out of memory on some problems; hybrid BFS/DFS not implemented.
- Anytime solutions carry no quality guarantees; mushroom and mushroom-f timeout while STreeD terminates.
- Experiments run on a personal machine with a 5-minute time limit, and the method is currently Python-only.
Experimental setup
Datasets: monk1 monk2 monk3 tic-tac-toe car-eval nursery mushroom kr-vs-kp zoo lymph balance
Benchmarks: monk1 monk2 monk3 tic-tac-toe car-eval nursery mushroom kr-vs-kp zoo lymph balance
Metrics: regularised objective accuracy number of splits runtime (s) iterations
Baselines: MurTree STreeD GOSDT OSDT PYGOSDT CART DL8.5
Builds on: GOSDT STreeD DL8.5 OSDT AO*
Closest papers by meaning
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.92)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.89)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.88)
- GradTree: Learning Axis-Aligned Decision Trees with Gradient Descent (AAAI 2024 · similarity 0.88)
- Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.88)
- Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound (AAAI 2025 · similarity 0.87)
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.