Improving Decision Trees through the Lens of Parameterized Local Search

AI summary

Overview

Research area: Machine learning (decision-tree learning and post-hoc optimization) combined with algorithmic theory, specifically parameterized complexity analysis.

Technical level: Advanced. The paper's core content is complexity-theoretic (FPT vs. W[1]/W[2]-hardness vs. paraNP-hardness) plus a dynamic-programming algorithm; readers need familiarity with parameterized complexity to follow the proofs, though the high-level messages are accessible.

Scope: A systematic study of the algorithmic complexity of optimizing a given decision tree by a fixed number of local-search operations (adjusting a cut's threshold, or also exchanging the cut's feature), covering FPT algorithms, XP algorithms, and matching hardness results across eight parameters.

What This Paper Is About

Standard decision-tree learners such as CART, C4.5, C5.0, and J48 build trees with heuristics and prune them afterwards, but they generally do not run local search on the finished tree, even though local search appears in simulated annealing, genetic, and SAT-based approaches. This paper asks what the algorithmic potential of such local search actually is: given a decision tree and training data, can we perform exactly k local operations — either Threshold Adjustment (change a cut's threshold) or Cut Exchange (also change the cut's feature) — so that the resulting tree makes at most t errors? The authors characterize when this problem is efficiently solvable and when it is not.

Key Contributions

1. A full complexity classification of local search for decision trees. Both Threshold Adjustment and Cut Exchange are shown to be NP-complete in general, and the paper maps eight parameters — n (examples), d (features), D (domain size), s (input tree size), k (number of operations), ℓ = s - k (unmodified cuts), t (error bound), and δ_max (maximum number of features on which two differently labeled examples differ) — and most of their combinations into FPT, W[1]-hard-but-XP, and paraNP-hard regions.

2. An FPT algorithm for the combined parameter d + D. While the problems are not expected to be FPT in d or in D alone, combining them is tractable. Theorem 4.1 solves Threshold Adjustment in O((D+1)^{2d+1} n k^2 + n s) time and Theorem 4.2 solves Cut Exchange in O((D+1)^{2d+1} n d k^2 + n s) time; the abstract states the bound as (D+1)^{2d} · |I|^{O(1)}.

3. Integration of local search with pruning. Theorem 4.3 shows that the problem DT-PLS, which allows threshold adjustments, cut exchanges, subtree replacements, and subtree raisings under four separate budgets, can be solved in O((D+1)^{2d+1} n d k^8 + n s) time, so local search and the earlier parameterized pruning algorithm of Harviainen et al. can be combined.

4. A new reduction connecting the two operations and the two problem types. Theorem 3.6 reduces Threshold Adjustment to Cut Exchange, formally justifying that Cut Exchange is at least as hard; Observation 3.2 reduces the fixed-structure learning problems FS-DT and FSFF-DT to Cut Exchange and Threshold Adjustment with k = s, transferring learning hardness into local-search hardness.

5. A proof-of-concept implementation with empirical results. The authors implement the algorithm and report that local improvements exist but are mild (their Table 1); code is archived on Zenodo.

Main Findings

• Both problems are NP-complete in general, so the subsequent parameterized analysis is needed to say anything practically useful.

• Hard for small d or small D alone, tractable for d + D together. Threshold Adjustment is W[1]-hard for d even when t = 0 and δ_max = 20 (Theorem 5.2), and cannot be solved in |I|^{o(d)} time under the ETH. Cut Exchange is W[1]-hard for d even when δ_max = 6, ℓ = 0, and t = 0 (Theorem 5.1), also with an |I|^{o(d)} ETH lower bound. Their combination yields fixed-parameter tractability.

• Hard for the number of operations k. Threshold Adjustment is W[2]-hard for k even if D = 2 and t = 0 (Theorem 5.3); under the ETH it cannot be solved in O(|I|^{o(k)}) time, and under the SETH not in O(s^{k-ε}) for any ε > 0. This implies the brute-force algorithm of Proposition 4.6 cannot be substantially improved unless the ETH fails.

• Parameterization by tree size s gives W[1]-hardness and XP-tractability. As stated with Figure 1, both problems are W[1]-hard and in XP parameterized by s, and consequently at least W[1]-hard for smaller parameters such as ℓ and at least XP for larger ones such as n.

• FPT for s + t on Threshold Adjustment, but not for Cut Exchange. Theorem 4.4 solves Threshold Adjustment in s^{O(3s+t)} · poly(|I|) time using binary search over thresholds; for Cut Exchange only s^{O(3s+t)} d^k · |I|^{O(1)} (Theorem 4.5) is shown, because Cut Exchange remains W[2]-hard for s even when t = 0 (Proposition 3.3), making an FPT algorithm for s + t unlikely.

• s + d is hard for both. Threshold Adjustment is W[1]-hard with respect to s + d and cannot be solved in |I|^{o(s+d)} time even when the inner nodes induce a path, ℓ = 0, and δ_max is constant (Proposition 3.4); the same holds for Cut Exchange (Proposition 3.7), obtained via the reduction from Threshold Adjustment.

• Learning decision trees reduces to local search. The authors strengthen the known hardness of Decision Tree Learning: it is W[1]-hard for s and not solvable in |I|^{o(s)} time unless the ETH fails, even when δ_max = 2 and D = 2 (Theorem 3.1), improving on the earlier bound of δ_max = 3.

• Some parameter combinations remain open. Figure 2 notes that Threshold Adjustment parameterized by t + ℓ + D is W[1]-hard but its XP-tractability is open.

• Local search yields only mild practical gains. While some improvement is achievable on the experimental instances already with a single local search operation, the decrement in errors tends to be mild, echoing the earlier observation that pruning heuristics in common libraries tend to be near-optimal on common benchmark datasets. The specific benchmark dataset names and instance sizes are not reported in the provided content.

Methodology in Plain English

The authors first formalize local search as a decision problem: take an existing tree, a budget k of operations, and a target error count t, and ask whether some sequence of operations meets the target. They adopt the notion of reasonability from Harviainen et al., requiring that no leaf be empty and that each leaf's label match the majority class of the examples reaching it.

To find where the problems are easy and where they are hard, they run a parameterized-complexity analysis. On the hardness side, they build reductions from well-studied hard problems — Multicolored Clique for the parameter d (using two features per color class), Multicolored Independent Set for d + t, and Hitting Set for k — and they construct "scaffolding" input trees that must be repaired by local-search moves whose number roughly equals the size of the tree to be learned. They also reduce Threshold Adjustment to Cut Exchange with a gadget that attaches long paths of cuts in new features below each leaf, forcing exchanged cuts back to threshold-only changes.

On the algorithmic side, their main dynamic program works over threshold sequences: for each feature it tracks an interval, and a box of examples is the set of examples falling inside all those intervals simultaneously. The DP table stores, for each subtree root, box, and remaining budget, the minimum achievable errors. Their second algorithm guesses which cuts are changed, how many errors land in each leaf, and the leaf label assignment, then uses recursive binary search to pin down the exact thresholds. They also give simple brute-force XP algorithms for the parameter k, and implement the approach as a proof of concept for the experiments.

Why This Matters

Impact on research. This is, by the authors' account, the first systematic algorithmic analysis of local search as a decision-tree optimization problem. It situates local search within the recent line of parameterized work on learning and pruning decision trees, and it delineates exactly which structural properties of the input explain hardness and which enable tractability. It also shows that even structure-restricted decision-tree learning remains hard, which sharpens the picture for the broader learning problem.

Real-world applications (the paper itself does not enumerate specific application domains; decision trees are used in interpretable-model settings, and the paper motivates the work via explainable AI):

• Domains where classification models must be explained to a human decision maker, since decision trees are cited in the paper as relevant to explainable AI because of their interpretability.
• Settings where an existing, deployed tree needs targeted improvement rather than retraining from scratch, which is exactly the local-search use case studied here.
• Pipelines built on standard heuristic learners (CART, C4.5, C5.0, J48) that could add a bounded-budget local-search step after pruning.
• Workflows where pruning is already applied and the user wants to combine pruning with a small number of cut modifications under explicit operation budgets, as in the DT-PLS problem.

Industry relevance. The paper's empirical message is directly relevant to practitioners: because the heuristics apparently already produce near-optimal trees locally, adding local search is unlikely to be worth large computational effort on typical benchmark data. At the same time, the FPT algorithm in d + D and the s + t algorithm give a principled way to know when exact local optimization is affordable.

Future Directions

• Resolving the open case for t + ℓ + D. Figure 2 explicitly records that Threshold Adjustment parameterized by t + ℓ + D is W[1]-hard while its XP-tractability is open.
• Tightening the gap between the two operations. The reductions show Cut Exchange is at least as hard as Threshold Adjustment, and Figure 2 indicates there are parameter combinations where Threshold Adjustment is strictly harder than learning decision trees and Cut Exchange strictly harder than Threshold Adjustment; pinning down the exact separations is left open.
• Extending the empirical study. The provided content does not report the benchmark dataset names or the size of the experimental instances, and only summarizes the results; broader evaluation of the proof-of-concept implementation would be a natural follow-up.
• Improving the positive-side algorithms. Whether the (D+1)^{2d}-style FPT algorithm, the s^{O(3s+t)} algorithm, or the brute-force XP algorithms for k can be substantially improved is constrained by the paper's ETH- and SETH-conditional lower bounds, so any further gains must come from additional parameters or restricted inputs.
• Combining with other optimization techniques. The authors already fold pruning into

Authors’ abstract

Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut. We study minimizing the number of classification errors by performing a fixed number of a single type of these operations. Although we discover that the corresponding problems are NP-complete in general, we provide a comprehensive parameterized-complexity analysis with the aim of determining those properties of the problems that explain the hardness and those that make the problems tractable. For instance, we show that the problems remain hard for a small number $d$ of features or small domain size $D$ but the combination of both yields fixed-parameter tractability. That is, the problems are solvable in $(D + 1)^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results.