Parameterized Complexity of Small Decision Tree Learning

Sebastian Ordyniak, Stefan SzeiderAAAI 2021 · DOI

Abstract

Learning the absolute smallest or shallowest decision tree from a dataset is a notoriously difficult NP-hard problem. This paper provides a breakthrough by showing that the problem becomes "Fixed-Parameter Tractable" (FPT) when considering three specific properties of the data: the desired tree size, the maximum number of values a feature can take, and the maximum difference between any two differently labeled examples.

Introduction: The Challenge of Optimal Decision Trees

Decision trees are fundamental to "interpretable AI" due to their human-readable structure. However, for a tree to remain truly interpretable, it must be small (low total node count) or shallow (low depth). Finding the optimal small tree that fits a given dataset is NP-hard. As the number of features or examples grows, the computational time required to find the best tree increases exponentially.

Example dataset and a corresponding decision tree for classification.

While common "greedy" heuristics like ID3 or C4.5 build trees quickly, they offer no guarantee of finding the smallest possible tree. This research investigates the parameterized complexity of the problem: can we find the optimal tree efficiently if certain "parameters" of the data remain small, even if the overall dataset is massive?

Methodology

The authors utilize the framework of Parameterized Complexity, analyzing runtime in terms of specific parameters rather than just total input size ($n$):

  1. Solution Size ($s$ or $d$): The number of nodes or the maximum depth of the tree.
  2. Maximum Domain Size ($D_{max}$): The maximum number of distinct values any single feature can take.
  3. Maximum Difference ($\delta_{max}$): The maximum number of features on which any two examples with different labels (one positive, one negative) disagree.

The core contribution is a two-stage algorithm. First, it performs Feature Selection by identifying a small subset of "useful" features, proving that an optimal tree only needs to pull from a pool related to $\delta_{max}$. Second, it performs Optimal Tree Construction using a recursive search. A key innovation is the use of binary search to efficiently find optimal thresholds for feature tests, avoiding exhaustive checks of every possible value.

Empirical Context and Datasets

To validate their parameter choices, the authors analyzed 16 standard Boolean classification instances from the UCI Machine Learning Repository (e.g., Car, Cancer, Heart-statlog). They discovered that in many real-world benchmarks, the "Maximum Difference" ($\delta_{max}$) is surprisingly small—often between 6 and 43—even when the total number of features is in the hundreds. This suggests that their FPT algorithm is practically relevant for real-world data.

Complexity Analysis and Key Results

The paper maps the boundary between tractability and intractability for various parameter combinations.

Complexity map of decision tree learning under various parameterizations.

Key Insights

  • The Complexity Map: Knowing only the desired tree size ($s$) is insufficient for tractability (it is W[2]-hard). Tractability requires accounting for data nature ($\delta_{max}$ and $D_{max}$).
  • Deconstructing Intractability: The hardness of learning decision trees is linked to the Hitting Set problem. By bounding $\delta_{max}$, the authors break this complexity barrier.
  • Threshold Monotonicity: The influence of a threshold on tree extendability is "monotone," allowing for efficient binary search.

Main Results

  • FPT Result: Finding the Minimum Decision Tree Size (DTS) and Depth (DTD) is Fixed-Parameter Tractable when parameterized by $(s, \delta_{max}, D_{max})$ and $(d, \delta_{max}, D_{max})$, respectively.
  • Hardness Proofs: The problem remains paraNP-hard if only $\delta_{max}$ is limited, and W[2]-hard if only solution size ($s$ or $d$) is limited, even for simple Boolean data.
  • Efficiency: The algorithm runs in time exponential in the parameters but polynomial in the number of examples, scaling well to large datasets with small optimal trees.

Limitations and Future Work

The current FPT result requires all three parameters to be small. The authors conjecture that $D_{max}$ (domain size) might not be strictly necessary for tractability. Future work could extend this approach to "noisy" data where perfect classification isn't required, or explore structural parameters like the "treewidth" of the data.

Summary updated

BibTeX
@inproceedings{ordyniak2021parameterized,
  author = {Sebastian Ordyniak and Stefan Szeider},
  title = {{Parameterized Complexity of Small Decision Tree Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16800},
}
Figure