A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees

By Haoran Zhu, Pavankumar Murali, Dzung T. Phan, Lam M. Nguyen, Jayant R. Kalagnanam. 2020

46 citations recorded by the source corpus.

Several recent publications report advances in training optimal decision trees (ODT) using mixed-integer programs (MIP), due to algorithmic advances in integer programming and a growing interest in addressing the inherent suboptimality of heuristic approaches such as CART. In this paper, we propose a novel MIP formulation, based on a 1-norm support vector machine model, to train a multivariate ODT for classification problems. We provide cutting plane techniques that tighten the linear relaxation of the MIP formulation, in order to improve run times to reach optimality. Using 36 data-sets from the University of California Irvine Machine Learning Repository, we demonstrate that our formulation outperforms its counterparts in the literature by an average of about 10% in terms of mean out-of-sample testing accuracy across the data-sets. We provide a scalable framework to train multivariate ODT on large data-sets by introducing a novel linear programming (LP) based data selection method to choose a subset of the data for training. Our method is able to routinely handle large data-sets with more than 7,000 sample points and outperform heuristics methods and other MIP based techniques. We present results on data-sets containing up to 245,000 samples. Existing MIP-based methods do not scale well on training data-sets beyond 5,500 samples.

Subfields: Artificial Intelligence

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

Citations in the corpus

Mathematical optimization in classification and regression trees (2021, methodology): “In Zhu et al. (2020), a subset of the training sample is selected in a preprocessing step using an LP problem, while, in Zantedeschi et al. (2020), a continuous relaxation is developed.”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “…use generic optimisation methods, namely integer programming (Bertsimas and Dunn (2017); Verwer and Zhang (2017, 2019); Aghaei et al. (2019); Zhu et al. (2020)), constraint programming (Verhaeghe et al. (2019)), and SAT (Narodytska et al. (2018); Avellaneda (2020); Janota and Morgado…”
Recent advances in decision trees: an updated survey (2022, methodology): “However, more recently, some authors have proposed non-greedy trees that employ linear splits, using integer programming (Bertsi-mas and Dunn 2017; Blanquero et al. 2021; Zhu et al. 2020; Aghaei et al. 2019) and gradient-based optimization (Norouzi et al. 2015).”
SAT-based Decision Tree Learning for Large Data Sets (2021, methodology): “We can encode weights with DT pb by using different maximum depths for the different classes.”