Learning Small Decision Trees with Large Domain
Authors: Eduard Eiben, Sebastian Ordyniak, Giacomo Paesani, Stefan Szeider
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present FPT algorithms for learning a smallest or lowest-depth DT from data, with the only parameters solution size and maximum difference. Thus, our algorithm is significantly more potent than the one by Szeider and Ordyniak as it can handle problem inputs with features that range over unbounded domains. We also close several gaps concerning the quality of approximation one obtains by only considering DTs based on minimum support sets. In this paper, we investigate the problem of finding small decision trees (w.r.t. size or depth) under the framework of Parameterized Complexity [Downey and Fellows, 2013; Gottlob et al., 2002; Niedermeier, 2006]. |
| Researcher Affiliation | Academia | Royal Holloway University of London, UK University of Leeds, UK Algorithms and Complexity Group, TU Wien, Vienna, Austria |
| Pseudocode | Yes | Algorithm 1 Main method for finding a DT of minimum size. Algorithm 2 Method for finding a DT of minimum size using at least the features in a given support set S. Algorithm 3. Algorithm 4 Algorithm to compute the pair (λL(r), λR(r)) for the root r of T. Algorithm 5 Algorithm to compute the triple (EXPt, λL(t), λR(t)) for every node t V (T). |
| Open Source Code | No | The paper does not mention providing open-source code for the described methodology. |
| Open Datasets | Yes | Ordyniak and Szeider [2021] list values for various standard benchmark sets from the UCI Machine Learning Repository (http://archive.ics.uci.edu/ml). |
| Dataset Splits | No | The paper is theoretical and does not describe experimental validation or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not specify 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 provide details about an experimental setup, hyperparameters, or training settings. |