Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
Luca Pascal Staus, Christian Komusiewicz, Frank Sommer, Manuel Sorge · 2024
Read Witty: An Efficient Solver for Computing Minimum-Size Decision Trees by Luca Pascal Staus, Christian Komusiewicz, Frank Sommer, Manuel Sorge (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11954.txt.
Introduction
Luca Pascal Staus, Christian Komusiewicz, Frank Sommer, and Manuel Sorge implement Witty, a solver that trains decision trees with the fewest possible nodes. Their paper from twenty twenty-four tackles an NP-hard problem prized for interpretability: classify every training example correctly with a minimum-size tree. The engine follows the witness tree paradigm, efficient when the optimal tree is small. Extensive heuristic upgrades are layered onto a careful implementation.
The augmentations speed the naive version by hundreds of times on average. Against the dynamic programming solver MurTree and SAT-based rivals, Witty wins by wide mean and median margins. An improved worst-case running-time bound lands as a theoretical bonus. Small-tree learning becomes practical on standard benchmarks.
Catalog record
| CREATOR | Luca Pascal Staus, Christian Komusiewicz, Frank Sommer, Manuel Sorge |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-11954
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Witty: An Efficient Solver for Computing Minimum-Size Decision Trees Luca Pascal Staus, Christian Komusiewicz, Frank Sommer, Manuel Sorge Abstract Decision trees are a classic model for summarizing and classifying data. To enhance interpretability and generalization properties, it has been proposed to favor small decision trees. Accordingly, in the minimum-size decision tree training problem ( MSDT ), the input is a set of training examples in ℝ d \mathbb{R}^{d} with class labels and we aim to find a decision tree that classifies all training examples correctly and has a minimum number of nodes. MSDT is NP-hard and therefore presumably not solvable in polynomial time. Nevertheless, Komusiewicz et al. [ICML ’23] developed a promising algorithmic paradigm called witness trees which solves MSDT efficiently if the solution tree is small. In this work, we test this paradigm empirically. We provide an implementation, augment it with extensive heuristic improvements, and scrutinize it on standard benchmark instances. The augmentations achieve a mean 324-fold (median 84-fold) speedup over the naive implementation. Compared to the state of the art they achieve a mean 32-fold (median 7-fold) speedup over the dynamic programming based MurTree solver [Demirović et al., J. Mach. Learn. Res. ’22] and a mean 61-fold (median 25-fold) speedup over SAT-based implementations [Janota and Morgado, SAT ’20]. As a theoretical result we obtain an improved worst-case running-time bound for MSDT . 1 Institute of Computer Science, University of Jena, Germany 2 Institute of Logic and Computation, TU Wien, Austria [email protected], [email protected], [email protected], [email protected] Code, Data and Experimental Results — https://doi.org/10.5281/zenodo.11235017 1 Introduction Traditional decision trees recursively partition the feature space with axis-parallel binary cuts and assign a class to each part of the partition. When learning decision trees, we are given a training data set that consists of examples E\subseteq\mathbb{R}^{d} labeled by classes and we want to find a decision tree that classifies the training data set (see Section 2 for the formal definitions). In addition, we want to optimize certain criteria, chiefly among them we want to minimize the number of cuts in the tree (or, equivalently, the size of the tree). 1 1 1 Another popular choice is to minimize the depth of the tree. We opted for the size criterion instead for simplicity. Our techniques are broadly applicable to the depth criterion, see the discussion in Section 8 . This is because small trees are more easily interpretable ( Molnar 2020 ; Moshkovitz et al. 2020 ) and they are thought to be more accurate on unknown data ( Fayyad and Irani 1990 ; Hu et al. 2020 ) . The resulting optimization problems are NP-hard, however ( Hyafil and Rivest 1976 ; Ordyniak and Szeider 2021 ) . Therefore, researchers traditionally use heuristics such as CART ( Breiman et al. 1984 ) . Recent advancements in hardware and algorithms have made it feasible to compute provably optimal trees for training data sets with up to several hundreds of examples (see the surveys by Carrizosa, Molero-Río, and Romero Morales (2021) ; Costa and Pedreira (2023) and a full list of 24 implementations in the appendix). The implementations still suffer from poor scalability, however ( Costa and Pedreira 2023 ) . In this paper we contribute towards overcoming this limitation. To that end, as has been done before ( Janota and Morgado 2020 ; Narodytska et al. 2018 ; Demirovic et al. 2022 ) , we focus on the training problem in which we want to find the smallest size perfect decision tree for the input training examples from two classes. Perfect means that all examples are classified correctly. This choice is to create a baseline method and we aim to later extend our approach to weaker accuracy guarantees and more classes. We build on recent theoretical algorithmic research that investigated what properties of the training data make computing smallest decision trees hard or tractable ( Ordyniak and Szeider 2021 ; Eiben et al. 2023 ; Kobourov et al. 2023 ; Komusiewicz et al. 2023 ) . Our starting point is the algorithmic paradigm of witness trees , introduced by Komusiewicz et al. (2023) . This paradigm improved on previous approaches ( Ordyniak and Szeider 2021 ; Eiben et al. 2023 ) with a better running time guarantee of \mathcal{O}((6\delta Ds)^{s}\cdot sn) in terms of the number n of training examples and the small parameters largest domain size D ( D=2 is common), largest number \delta\leq d of features in which two training examples differ, 2 2 2 See Ordyniak and Szeider (2021) and Table 3 in the appendix for evidence that \delta is a reasonably small parameter (much smaller than the number d of dimensions) in several datasets. and the number s of cuts in the solution tree. Importantly for us, the paradigm simplified previous theoretical approaches to such an extent as to make it promising as a foundation of a competitive solver. Additionally, the approach generalizes to other learning models and even ensembles ( Komusiewicz et al. 2023 ; Ordyniak et al. 2024 ) , making it particularly interesting to test in practice. The main idea of the witness-tree paradigm is to start with a trivial decision tree consisting of a single leaf labeled by an arbitrary class. Then we pick a training example which is classified incorrectly, we call it dirty , and we recursively try in a branching over all possibilities to refine the current tree with a new cut and a new leaf in which the dirty example is classified correctly. We label the new leaf with the dirty example as witness and mandate that all future refinements maintain all witnesses at their assigned leafs. This reduces the search space that we need to explore to find the desired decision tree. See Section 3 for a more detailed description. In this work, we provide an implementation of the above paradigm and we extensively engineer it with improvements that give heuristic speedups while maintaining the optimality of the computed decision tree. Our main result is that these improvements substantially speed up the algorithm to the point where the resulting solver, called Witty , performs substantially better than the state of the art (see Section 7 ). To the best of our knowledge, the state-of-the-art solvers for computing minimum-size perfect decision trees are SAT-based solvers by Narodytska et al. (2018) and Janota and Morgado (2020) and the dynamic-programming algorithm MurTree by Demirovic et al. (2022) . All other implementations for computing variants of optimal decision trees solve different optimization problems and are not suitable for the task discussed in the present paper, see the appendix for details. We tested the solvers on standard benchmark data sets from the Penn Machine Learning Benchmarks ( Romano et al. 2022 ) . Out of the three state-of-the-art solvers MurTree performed the best, solving 371 out of the 700 instances. In comparison, Witty was able to solve 388 instances and achieves a mean 32 -fold (median 7 -fold) speedup over MurTree . Witty performs especially well compared to MurTree on instances that have dimensions with a large number of different values. This is due to the fact that Witty does not require binary dimensions and one of the above-mentioned improvements specifically exploits large domains. We should