Research map / Learning theory and algorithms / Combinatorial and search optimization
Improving Decision Trees through the Lens of Parameterized Local Search
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.
Studies the parameterized complexity of optimally performing k threshold adjustments or cut exchanges on a decision tree to minimize training errors, giving FPT results for (D+1)^{2d} and hardness results for other parameters, plus a proof-of-concept implementation.
Problem
Local search for decision trees: given a decision tree and training data, can at most k cuts be modified (threshold adjustment or cut exchange) so that the tree makes at most t errors? Both are NP-complete in general.
Approach
A comprehensive parameterized-complexity map of threshold adjustment and cut exchange over parameters (n, d, D, s, k, l, t, delta_max); dynamic programming over threshold boxes gives FPT in d+D, and binary search with error-vector guessing gives FPT in s+t+d for threshold adjustment, while W[1]-hardness is shown for d, s, and d+t.
Key results
- Threshold Adjustment and Cut Exchange are solvable in (D+1)^{2d} times polynomial time (FPT in d+D), via dynamic programming over threshold boxes.
- Both problems are W[1]-hard for the number of features d even with t=0, and Cut Exchange is W[2]-hard for s even with t=0.
- Threshold Adjustment admits an FPT-algorithm for s+t+d-style parameterization via guessing changed cuts, error distribution, and binary search for thresholds, with running time s^{O(3s+t)} poly(|I|).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| perform a single local-search operation | heuristic-built decision trees · benchmark instances | classification errors | Helped |
Surprising findings
- Local search gains from a single operation on practical instances tend to be mild, suggesting heuristic trees are near-optimal locally.
Limitations
- Problems are NP-complete and W[1]-hard for many single parameters, so tractability requires parameter combinations.
- Proof-of-concept implementation only; empirical scope limited to small-scale evaluation.
Experimental setup
Metrics: number of misclassifications running time
Baselines: brute-force algorithm
Builds on: Harviainen et al. decision tree pruning with raising reasonability of decision trees parameterized complexity of decision tree learning (Gahlawat and Zehavi)
Closest papers by meaning
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.92)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.92)
- Learning Small Decision Trees for Data of Low Rank-Width (AAAI 2024 · similarity 0.89)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.89)
- Witty: An Efficient Solver for Computing Minimum-Size Decision Trees (AAAI 2025 · similarity 0.88)
- 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.