Parameterized Complexity of Small Decision Tree Learning
Authors: Sebastian Ordyniak, Stefan Szeider6454-6462
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide the first parameterized complexity analysis of the problem and draw a detailed parameterized complexity map for the natural parameters: size or depth of the DT, maximum domain size of all features, and the maximum Hamming distance between any two examples. Our main result shows that learning DTs of smallest depth or size is fixed-parameter tractable (FPT) parameterized by the combination of all three of these parameters. We contrast this FPT-result by various hardness results that underline the algorithmic significance of the considered parameters. |
| Researcher Affiliation | Academia | 1University of Leeds, School of Computing, Leeds, UK 2Algorithms and Complexity Group, TU Wien, Vienna, Austria |
| Pseudocode | Yes | Algorithm 1 Algorithm to compute the threshold assignment for a pseudo DT and a feature assignment. Algorithm 2 Sub-routine Binary Search used by Algorithm 1. Algorithm 3 Main method for finding a DT of minimum size. Algorithm 4 Method for finding a DT of minimum size using at least the features in a given support set S. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | Yes | Boolean classification instances from Narodytska et al. (2018) with their number of examples |E|, the number of features |F|, and their maximum difference δmax. The instances originate from the UCI Machine Learning Repository (Dua and Graff 2017). |
| Dataset Splits | No | The paper is theoretical and does not describe experimental procedures or dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not report on hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |