Optimal Sparse Decision Trees

By Xiyang Hu, Cynthia Rudin, Margo I. Seltzer. 2019

204 citations recorded by the source corpus.

Decision tree algorithms have been among the most popular algorithms for interpretable (transparent) machine learning since the early 1980's. The problem that has plagued decision tree algorithms since their inception is their lack of optimality, or lack of guarantees of closeness to optimality: decision tree algorithms are often greedy or myopic, and sometimes produce unquestionably suboptimal models. Hardness of decision tree optimization is both a theoretical and practical obstacle, and even careful mathematical programming approaches have not been able to solve these problems efficiently. This work introduces the first practical algorithm for optimal decision trees for binary variables. The algorithm is a co-design of analytical bounds that reduce the search space and modern systems techniques, including data structures and a custom bit-vector library. Our experiments highlight advantages in scalability, speed, and proof of optimality.

Subfields: Optimization & Training

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “For customized branch-and-bound search algorithms such as GOSDT and OSDT (Lin et al., 2020; Hu et al., 2019), there are several mechanisms to improve scalability: (1) effective lower bounds, which prevent branching into parts of the search space where we can prove there is no optimal solution, (2) e”
Mathematical optimization in classification and regression trees (2021, background): “Instead, and as advocated by Rudin (2019), it is better to work with models that can derive local explanations directly, as is the case for Neural Networks (Gevrey et al. 2003) but also for the Optimal Randomized Classification and Regression Trees in Sect.”
Optimal Decision Lists using SAT (2020, methodology): “…et al. 2019), 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…”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “The AND-OR search method (Verhaeghe et al. (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).”
Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost (2020, neutral): “Therefore, other methods [ Ni-jssen and Fromont, 2007; Bertsimas and Dunn, 2017; Verwer and Zhang, 2019; Verhaeghe et al. , 2019; Aglin et al. , 2020; Hu et al. , 2019 ] opt instead for optimizing accuracy (on the training set) subject to constraints on the maximum depth.”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “For optimizing non-additive loss function, we use Py-GOSDT: a variant of GOSDT that is closer to OSDT (Hu et al., 2019).”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, methodology): “Hu et al. (2019) use analytical bounds (to aggressively prune-out the search space) combined with a tailored bit-vector based implementation.”
Learning Optimized Risk Scores (2016, neutral): “[53] Hu, Xiyang, Cynthia Rudin, and Margo Seltzer.”
Optimal Decision Trees for Nonlinear Metrics (2020, methodology): “Hu, Rudin, and Seltzer (2019) presented an algorithm that computes the optimal decision tree by considering a balance between misclassifications and number of nodes.”
Born-Again Tree Ensembles (2020, methodology): “(1988) [SmithEtAl] and Hu et al. (2019) [HuEtAl] for which using random forests (with ten trees) showed a significant improvement upon stand-alone CART.”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “This objective was used in the original CART paper (Breiman et al. (1984)) and discussed in some of the other optimal decision tree works (Bertsimas and Dunn (2017); Hu et al. (2019)).”
COPOD: Copula-Based Outlier Detection (2020, background): “Interpretable algorithms provide both transparency and reliability [11].”
Decision Trees for Decision-Making under the Predict-then-Optimize Framework (2020, unknown): “, 1984); several recent works have also proposed integer programming strategies for training decision trees to optimality (Bertsimas & Dunn, 2017; Günlük et al., 2018; Verwer & Zhang, 2019; Hu et al., 2019; Aghaei et al., 2020).”
Classification Based on Decision Tree Algorithm for Machine Learning (2021, background): “[69] S. Patil and U. Kulkarni, “Accuracy Prediction for Distributed Decision Tree using Machine Learning approach,” in 2019 3rd International Conference on Trends in Electronics and Informatics (ICOEI), Apr. 2019, pp. 1365–1371, doi: 10.1109/ICOEI.2019.8862580.”
A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees (2020, methodology): “…have used optimality criteria such as the average testing length [Laurent and Rivest, 1976], training accuracy, the combination of training accuracy and model interpretability [Bertsimas and Dunn, 2017, Hu et al., 2019], and the combination of training accuracy and fairness [Aghaei et al., 2019].”
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 .”
SAT-Based Encodings for Optimal Decision Trees with Explicit Paths (2020, background): “Another approach is taken by [14], which optimizes a linear combination of accuracy and size.”
Learning Binary Trees via Sparse Relaxation (2020, result): “This resulted in a line of recent follow-up works (Günlük et al., 2018; Aghaei et al., 2019; Verwer & Zhang, 2019; Hu et al., 2019; Aghaei et al., 2020; Lin et al., 2020).”