Learning Small Decision Trees for Data of Low Rank-Width
Authors: Konrad K. Dabrowski, Eduard Eiben, Sebastian Ordyniak, Giacomo Paesani, Stefan Szeider
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that the problem is fixed-parameter tractable when parameterized by the rank-width of the incidence graph of the given classification instance. Our algorithm proceeds by dynamic programming using an NLC decomposition obtained from a rank-width decomposition. The key to the algorithm is a succinct representation of partial solutions. This allows us to limit the space and time requirements for each dynamic programming step in terms of the parameter. |
| Researcher Affiliation | Academia | 1Newcastle University, 2Royal Holloway, University of London, 3University of Leeds, 4TU Wien |
| Pseudocode | No | The paper describes the algorithmic steps and dynamic programming approach in prose and through lemmas, but it does not include any formal pseudocode blocks or clearly labeled algorithm sections. |
| Open Source Code | No | The paper does not provide any statements about releasing source code or links to a code repository for the described methodology. |
| Open Datasets | No | This paper is theoretical and focuses on algorithm design and fixed-parameter tractability for decision trees. It defines classification instances abstractly but does not involve practical datasets, training, or evaluation on data, so no dataset access information is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with datasets. Therefore, no training/test/validation dataset splits are specified for reproducibility. |
| Hardware Specification | No | This is a theoretical paper focusing on algorithms and complexity. It does not describe any empirical experiments, and therefore, no hardware specifications are mentioned for running experiments. |
| Software Dependencies | No | This is a theoretical paper focused on algorithm design and complexity. It does not describe any empirical experiments, and thus, no specific ancillary software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This paper is theoretical, presenting an algorithm and its fixed-parameter tractability. It does not involve empirical experiments, and consequently, no experimental setup details like hyperparameters or training configurations are provided. |