Efficient Inference of Optimal Decision Trees

By Florent Avellaneda. 2020

62 citations recorded by the source corpus.

Inferring a decision tree from a given dataset is a classic problem in machine learning. This problem consists of building, from a labelled dataset, a tree where each node corresponds to a class and a path between the tree root and a leaf corresponds to a conjunction of features to be satisfied in this class. Following the principle of parsimony, we want to infer a minimal tree consistent with the dataset. Unfortunately, inferring an optimal decision tree is NP-complete for several definitions of optimality. For this reason, the majority of existing approaches rely on heuristics, and the few existing exact approaches do not work on large datasets. In this paper, we propose a novel approach for inferring an optimal decision tree with a minimum depth based on the incremental generation of Boolean formulas. The experimental results indicate that it scales sufficiently well and the time it takes to run grows slowly with the size of datasets.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “We use publicly available datasets used in previous works (Bertsimas and Dunn (2017); Verwer and Zhang (2019); Narodytska et al. (2018); Aglin et al.”
Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost (2020, neutral): “For instance, the SAT-encoding in [Avellaneda, 2020] can be easily adapted to use number of meaningful nodes as objective, however, the encoding will grow exponentially in the depth and therefore intractable.”
Optimal Decision Trees for Nonlinear Metrics (2020, methodology): “The SAT approach of (Avellaneda 2020) simplifies the encoding by fixing the depth of the tree and employing an incremental approach to gradually added instances to the formulation.”
Parameterized Complexity of Small Decision Tree Learning (2021, methodology): “In view of this complexity barrier, several constrained-based and SAT-based methods have been proposed for learning small decision trees (Bessiere, Hebrard, and O’Sullivan 2009; Narodytska et al. 2018; Avellaneda 2020; Schidler and Szeider 2021).”
Recent advances in decision trees: an updated survey (2022, methodology): “Several authors have proposed ways of sidestepping the scalability issue, for example by inducing trees on a subsample of the training data (Bessiere et al. 2009; Naro-dytska et al. 2018; Avellaneda 2020) or by reducing the input space (Narodytska et al. 2018; Firat et al. 2020).”
PyDL8.5: a Library for Learning Optimal Decision Trees (2020, methodology): “A recent publication studied the problem of finding the shallowest tree with perfect accuracy on training data (100%); it solved this problem using a SAT solver [Avellaneda, 2020].”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “These approaches use generic optimisation methods, namely integer programming (Bertsimas and Dunn (2017); Verwer and Zhang (2017, 2019); Aghaei et al.”
On Explaining Decision Trees (2020, unknown): “[2,68,25,32,1,7,57,24,26,70,67,58,44,30,17,5,73,35,4,78,69,10,34,72,71,36,46,11,45].”