Generalized and Scalable Optimal Sparse Decision Trees

By Jimmy J. Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, Margo I. Seltzer. 2020

178 citations recorded by the source corpus.

Decision tree optimization is notoriously difficult from a computational perspective but essential for the field of interpretable machine learning. Despite efforts over the past 40 years, only recently have optimization breakthroughs been made that have allowed practical algorithms to find optimal decision trees. These new techniques have the potential to trigger a paradigm shift where it is possible to construct sparse decision trees to efficiently optimize a variety of objective functions without relying on greedy splitting and pruning heuristics that often lead to suboptimal solutions. The contribution in this work is to provide a general framework for decision tree optimization that addresses the two significant open problems in the area: treatment of imbalanced data and fully optimizing over continuous variables. We present techniques that produce optimal decision trees over a variety of objectives including F-score, AUC, and partial area under the ROC convex hull. We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables and speeds up decision tree construction by several orders of magnitude relative to the state-of-the art.

Subfields: Artificial Intelligence, Mathematical Optimization, 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 Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “Lin et al. (2020) preprocesses the data by transforming continuous features into a set of dummy variables, with many different split points; they take split points at the mean values between every ordered pair of unique values present in the training data.”
Mathematical optimization in classification and regression trees (2021, methodology): “We refer the reader to Liu et al. (2002) for a comprehensive review on enhancing classification and regression tree methods through the discretization of continuous predictor variables (Dougherty et al. 1995).”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “The method was improved and extended by Lin et al. (2020), providing good performance if the sparsity coeﬃcient, which controls the balance between accuracy and number of nodes, is suﬃciently high.”
Harnessing Interpretable Machine Learning for Origami Feature Design and Pattern Selection (2022, methodology): “More state-of-the-art decision tree methods (like the Generalized and Scalable Optimal Sparse Decision Trees (32) and the Optimal Classification Trees (33)) could also be used in the future to further improve the performance.”
Recent advances in decision trees: an updated survey (2022, methodology): “More sophisticated approaches include efficiently considering every possible threshold via specialized approaches (Lin et al. 2020), using supervised discretization algorithms (Demirović et al. 2021), or decile binning (Günlük et al. 2021).”
Optimal Decision Trees for Nonlinear Metrics (2020, background): “(Lin et al. 2020) noted the difficulty of the F1-score and proposed to linearise the problem by changing the node classification criteria, however this does not address the optimisation problem.”
Exploring the cloud of variable importance for the set of all good models (2020, methodology): “In ‘Approximation of VIC with correlated variables’, we have approximated the VIC by an ellipsoid characterized by equation (5).”