Research map / Learning theory and algorithms / Prediction and decision losses
Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
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.
Gives a classical and parameterized complexity analysis of optimal decision tree pruning under subtree replacement (polynomial, with faster algorithm) and subtree raising (NP-complete, with a full single- and multi-parameter classification), plus a proof-of-concept Pareto-front experiment on benchmark data.
Problem
Optimally pruning a given decision tree with subtree replacement or subtree raising, trading off the number of pruned inner nodes against classification errors on the training data.
Approach
Shows replacement pruning is polynomial (with a DP running linear in tree size when k or t is small), while raising is NP-complete; maps out the FPT/XP/W[1]-hardness borderline over single and combined parameters (e.g., D^{2d_T} algorithm), and uses the algorithm to compute exact Pareto fronts to evaluate heuristics.
Key results
- Subtree replacement pruning is solvable in O((n + min{k^2,t^2})·s) time, improving the earlier quadratic bound.
- Subtree raising (DTRais) is NP-complete; it is solvable in D^{2d_T}·|I|^{O(1)} time, giving an FPT-type result for the combined parameter.
- Experiments on benchmark datasets show the replacement and raising heuristics achieve nearly optimal tradeoffs between pruned nodes and errors (exact Pareto fronts computed).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use heuristic pruning (subtree replacement and subtree raising) instead of the optimal pruning tradeoff | Decision trees in benchmark datasets · Benchmark data (aggregate) | number of pruned nodes versus classification errors | No clear effect |
Surprising findings
- Subtree raising remains NP-hard even when pruning at least k=0 nodes.
- For subtree replacement, pruning becomes NP-complete for tree ensembles even with only two trees.
Limitations
- Raising problem is NP-hard in general, so only parameterized algorithms are available.
- Experiments are preliminary proof-of-concept on a limited set of benchmarks.
- Results are on training-data error, not generalization.
Experimental setup
Datasets: appendicitis australian banana phoneme titanic contraceptive Hill_Valley_without_noise soybean flare haberman
Benchmarks: OpenML/standard tabular benchmark datasets (about 45 datasets listed in appendix)
Metrics: number of pruned inner nodes k number of classification errors t tree size Pareto-front optimality of heuristics
Baselines: replacement heuristic (C4.5/CART-style) raising heuristic (C4.5/J48-style)
Builds on: CART C4.5 Tree Knapsack dynamic programming witness tree enumeration algorithm
Closest papers by meaning
- Improving Decision Trees through the Lens of Parameterized Local Search (NeurIPS 2025 · similarity 0.92)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.91)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.90)
- Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.89)
- SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration (NeurIPS 2025 · similarity 0.89)
- Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO* (ICML 2025 · similarity 0.88)
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.