Learning Optimal Classification Trees Using a Binary Linear Program Formulation

By Sicco Verwer, Yingqian Zhang. 2019

189 citations recorded by the source corpus.

We provide a new formulation for the problem of learning the optimal classification tree of a given depth as a binary linear program. A limitation of previously proposed Mathematical Optimization formulations is that they create constraints and variables for every row in the training data. As a result, the running time of the existing Integer Linear programming (ILP) formulations increases dramatically with the size of data. In our new binary formulation, we aim to circumvent this problem by making the formulation size largely independent from the training data size. We show experimentally that our formulation achieves better performance than existing formulations on both small and large problem instances within shorter running time.

Subfields: Artificial Intelligence, Optimization & Training, Statistical Learning Theory

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 Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “MIP solvers can be used directly when the problem is not too large and when the loss function is discrete or linear (e.g., classification error is discrete, as it takes values either 0 or 1).”
Mathematical optimization in classification and regression trees (2021, background): “…number of shortcomings to this approach around, for instance, the generation of data or the loss of accuracy, which have been addressed with enhancements (Botari et al. 2020; Visani et al. 2020; Zhang et al. 2019), or with alternative approaches (Lundberg et al. 2020, 2018; Lundberg and Lee 2017).”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “5 has been shown to largely outperform the other techniques based on generic optimisation modelling, such as integer programming (Verwer and Zhang (2019); Bertsimas and Dunn (2017)) and constraint programming (Verhaeghe et al. (2019)), when minimising the misclassiﬁcation score for full binary…”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “5 (Nijssen et al., 2020), BinOCT (Verwer & Zhang, 2019), DTC (Garofalakis et al., 2003), and CART (Breiman et al., 1984).”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, methodology): “Similar to Verwer and Zhang (2019), we run the different algorithms for 10 minutes on each dataset and for a maximum depth of 2, 3 and 4.”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, methodology): “The works of Bertsimas and Dunn (2017), Günlük et al. (2018), Aghaei et al. (2019), and Verwer and Zhang (2019) have served to showcase the modeling power of using MIP to learn decision trees and the potential suboptimality of traditional algorithms.”
Optimal Sparse Decision Trees (2019, methodology): “Verwer and Zhang [20] introduce a much faster mathematical programming formulation, and their experiments indicate that BinOCT outperforms OCT, but since BinOCT is constrained to create complete binary trees of a given depth rather than optimally sparse trees, it sometimes creates unnecessary leaves”
The Secrets of Machine Learning: Ten Things You Wish You Had Known Earlier to be More Effective at Data Analysis (2019, background): “, see [56, 27, 2]), so that all the splits are chosen together so that the overall tree is accurate and sparse.”
Column generation based heuristic for learning classification trees (2020, methodology): “, Bertsimas and Dunn [3], Verwer and Zhang [35], Verwer and Zhang [37]) failed to handle datasets with more than 10000 rows within their predefined time limits.”
Decision Trees for Decision-Making under the Predict-then-Optimize Framework (2020, unknown): “More recently, integer programming strategies have been proposed for optimally solving (3) with respect to classiﬁcation loss (Bertsimas and Dunn 2017, G¨unl¨uk et al. 2018, Verwer and Zhang 2019, Hu et al. 2019, Aghaei et al. 2020).”
IPBoost - Non-Convex Boosting via Integer Programming (2020, background): “…see, e.g., (Bertsimas & Shioda, 2007; Chang et al., 2012; Bertsimas & King, 2015; Bertsimas et al., 2016), as well as, (Günlük et al., 2016; Bertsimas & Dunn, 2017; Dash et al., 2018; Günlük et al., 2018; Verwer & Zhang, 2019); note that (Dash et al., 2018) also uses a column generation approach.”
Learning optimal decision trees using constraint programming (2020, methodology): “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.”
Born-Again Tree Ensembles (2020, methodology): “On a similar note, G¨unl¨uk et al. (2018) presented an integer programming approach for optimal decision trees with categorical data, and Verwer & Zhang (2019) presented a binary linear program for optimal decision trees.”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “It has been observed that a more accurate representation of the data oﬀers better generalisation on unseen data (Bertsimas and Dunn (2017); Verwer and Zhang (2017, 2019)).”
A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees (2020, methodology): “t (1a): OCT-H and Fair ; (1b): OCT-H, Fair and BinOCT [23], D = 2.”