Learning Optimal Decision Trees Using Caching Branch-and-Bound Search

By Gaël Aglin, Siegfried Nijssen, Pierre Schaus. 2020

139 citations recorded by the source corpus.

Several recent publications have studied the use of Mixed Integer Programming (MIP) for finding an optimal decision tree, that is, the best decision tree under formal requirements on accuracy, fairness or interpretability of the predictive model. These publications used MIP to deal with the hard computational challenge of finding such trees. In this paper, we introduce a new efficient algorithm, DL8.5, for finding optimal decision trees, based on the use of itemset mining techniques. We show that this new approach outperforms earlier approaches with several orders of magnitude, for both numerical and discrete data, and is generic as well. The key idea underlying this new approach is the use of a cache of itemsets in combination with branch-and-bound search; this new type of cache also stores results for parts of the search space that have been traversed partially.

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

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “Some methods [301, 222] preprocess the data using an approximation, whereby they consider a much smaller subset of possible thresholds, potentially sacrificing the optimality of the solution [see 185, Section 3, which explains this].”
Mathematical optimization in classification and regression trees (2021, methodology): “Throughout this section, we discuss optimization approaches that focus on the design of specific components of the tree model (Aglin et al. 2020; Bennett and Blue 1996; Nijssen and Fromont 2010; Savickỳ et al. 2020).”
Optimal Decision Lists using SAT (2020, methodology): “…where the decision tree agrees perfectly with the training data, as well as producing the smallest possible sparse decision trees (Hu, Rudin, and Seltzer 2019; Aglin, Nijssen, and Schaus 2020), where there is a trade-off between size of the decision tree versus its accuracy on the training data.”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “(2019)), pattern mining approach (Nijssen and Fromont (2007, 2010); Aglin et al. (2020a)), and the search by Hu et al. (2019) and Lin et al. (2020) use the independence property of the left and right subtree (Property 1). Those approaches save computed optimal subtrees (Property 2), which correspond”
On Explaining Decision Trees (2020, background): “5 [1,2] can only handle numerical and binary features, respectively, and so could not be included in the experiments.”
Recent advances in decision trees: an updated survey (2022, background): “…technical considerations, other algorithms assume that all attributes are categorical (Günlük et al. 2021) or, more often, binary (Bessiere et al. 2009; Nijssen and Fromont 2010; Narodytska et al. 2018; Verwer and Zhang 2019; Aglin et al. 2020; Janota and Morgado 2020; Demirović et al. 2021).”
SAT-based Decision Tree Learning for Large Data Sets (2021, background): “Given a class c , for all e i ; e j 2 E such that C ( e i ) = c; C ( e j ) 6 = c , we add the clauses : g i;j;w , where w = d (cid:0) d ( c ) + d min is the allowed depth in regards to the weight of c .”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “Previous approaches either place no constraint on the number of nodes apart from the depth (Nijssen and Fromont (2007); Aglin et al. (2020)), limit the number of nodes by penalising the objective function for each node in the tree (Hu et al. (2019)), or allow constraints on the number of nodes but…”
Learning optimal decision trees using constraint programming (2020, background): “The most popular setting studied in recent papers [Aghaei et al., 2019; Bertsimas and Dunn, 2017; Verwer and Zhang, 2019; Aglin et al., 2020] is the one in which a decision tree of bounded depth is learned by maximizing the accuracy on a given training dataset.”