Learning Optimal Decision Trees with SAT

By Nina Narodytska, Alexey Ignatiev, Filipe Pereira, Joao Marques-Silva. 2018

148 citations recorded by the source corpus.

Explanations of machine learning (ML) predictions are of fundamental importance in different settings. Moreover, explanations should be succinct, to enable easy understanding by humans. Decision trees represent an often used approach for developing explainable ML models, motivated by the natural mapping between decision tree paths and rules. Clearly, smaller trees correlate well with smaller rules, and so one challenge is to devise solutions for computing smallest size decision trees given training data. Although simple to formulate, the computation of smallest size decision trees turns out to be an extremely challenging computational problem, for which no practical solutions are known. This paper develops a SAT-based model for computing smallest-size decision trees given training data. In sharp contrast with past work, the proposed SAT model is shown to scale for publicly available datasets of practical interest.

Subfields: Artificial Intelligence, Information Systems, Algorithms & Complexity

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 Information Systems

In Algorithms & Complexity

Citations in the corpus

Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI (2019, positive): “A neural network considered as a black-box can be explained by associating it to a more interpretable model such as a Decision Tree [306] , a (fuzzy) rule-based system [19] or KNN [264] . of knowledge in the neuron as another parametric characteristic that can be learned from data.”
Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “…Blue, 1996; Rudin and Ertekin, 2018; Verwer and Zhang, 2019; Vilas Boas et al., 2019; Menickelly et al., 2018; Aghaei et al., 2020) and SAT solvers (Narodytska et al., 2018; Hu et al., 2020) (see also the review of Carrizosa et al., 2020), (2) stochastic search through the space of trees (e.g.,…”
Mathematical optimization in classification and regression trees (2021, methodology): “The reader is referred to, e.g., Verhaeghe et al. (2019) for a constraint programming paradigm, an SAT one in Narodytska et al. (2018), Yu et al. (2020), and a dynamic programming one in Demirović et al. (2020).”
Optimal Decision Lists using SAT (2020, background): “There has been considerable investigation into producing the smallest possible optimal perfect decision trees (Narodytska et al. 2018; Verhaeghe et al. 2019), where the decision tree agrees perfectly with the training data, as well as producing the smallest possible sparse decision trees (Hu,…”
Computing Optimal Decision Sets with SAT (2020, methodology): “We follow the notation used in earlier work [8, 31, 34, 44].”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “Encodings of decision trees using propositional logic (SAT) and constraint programming have been initially devised by Bessiere et al. (2009).”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “If the data can be perfectly separated with zero error, SAT solvers can be used to find optimal decision trees rapidly (Narodytska et al., 2018); however, real data is generally not separable, leaving us with no choice other than to actually solve the problem.”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, methodology): “Another class of methods for learning optimal decision trees is that based on SAT Solvers (Narodytska et al. 2018; Bessiere, Hebrard, and O’Sullivan 2009).”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, methodology): “For example, Nijssen and Fromont (2010) use itemset mining algorithms and Narodytska et al. (2018) use satisﬁability (SAT) solvers.”
Learning Fair Rule Lists (2019, background): “For instance, when they have small or of reasonable size [44], ∗ Principal contributor. the following models can be considered as interpretable: rules sets [18, 43, 46, 54], rule lists [3, 59, 61], decision trees [9, 51] and scoring systems [39, 57, 64].”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, methodology): “This power has led to interesting new approaches for learning models and rules, see e.g., (Bessiere, Hebrard, and OSullivan 2009; De Raedt, Guns, and Nijssen 2010; Narodytska et al. 2018; Verwer, Zhang, and Ye 2017).”
Optimal Sparse Decision Trees (2019, background): “Some exploration of learning optimal decision trees is based on boolean satisfiability (SAT) [17], but again, this work looks only for the optimal tree of a given number of nodes.”
Constructing classification trees using column generation (2018, methodology): “In Narodytska et al. (2018), the authors model the smallest-size decision tree learning problem as a satisfiability problem, and solve the model using a SAT solver.”
On Explaining Decision Trees (2020, background): “Motivated by this perception, there has been extensive work on learning DTs (and related logic ML models) with properties deemed important for interpretability, e.g. number of nodes, maximum/average depth, etc. [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] 2 .”
Learning optimal decision trees using constraint programming (2020, result): “Two earlier studies [Bessiere et al., 2009; Narodytska et al., 2018] did, however, study the setting in which one finds the smallest decision tree consistent with a training dataset (i.”
Complete Search for Feature Selection in Decision Trees (2019, background): “Other approaches, e.g. Narodytska et al. (2018), encode tree construction as a constraint solving problem, with the aim of minimizing tree size.”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “As ﬁnding the zero-misclassiﬁcation tree using the complete dataset was computationally infeasible for SAT, and also prone to overﬁtting, the authors proposed to subsample datasets by selecting 5-20% of the instances.”