Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming
Authors: Jacobus van der Linden, Mathijs de Weerdt, Emir Demirović
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on five application domains show the general applicability of this framework, while outperforming the scalability of general-purpose solvers by a large margin. |
| Researcher Affiliation | Academia | Jacobus G. M. van der Linden Mathijs M. de Weerdt Emir Demirovi c Delft University of Technology, Department of Computer Science {J.G.M.vander Linden, M.M.de Weerdt, E.Demirovic}@tudelft.nl |
| Pseudocode | Yes | Pseudo-code for STree D and additional algorithmic techniques for speeding up computation, such as a special depth-two solver, caching, and upper and lower bounds, as well as techniques for sparse trees and hypertuning, can be found in Appendix B. |
| Open Source Code | Yes | STree D is implemented in C++ and is available as a Python package.1 |
| Open Datasets | Yes | Table 1 lists the datasets used in this experiment [24, 41, 95]. |
| Dataset Splits | No | Every dataset is split randomly 100 times in a train and test set, with 80% and 20% of the instances respectively. |
| Hardware Specification | Yes | All experiments are run on a 2.6 GHz Intel i7 CPU with 8GB RAM using only one thread. |
| Software Dependencies | Yes | MIP models are solved using Gurobi 9.0 with default parameters [33]. |
| Experiment Setup | Yes | We tune STree D with a depth limit of d = 4. In Appendix C we show extended results and also compare with several heuristics from the literature. To our knowledge, no MIP methods for cost-sensitive classification including group discounts (i.e., when certain features are tested together, the feature cost decreases) exist, and therefore are not considered here. |