Sparsity in Optimal Randomized Classification Trees

By Rafael Blanquero, Emilio Carrizosa, Cristina Molero-Río, Dolores Romero Morales. 2020

51 citations recorded by the source corpus.

Abstract Decision trees are popular Classification and Regression tools and, when small-sized, easy to interpret. Traditionally, a greedy approach has been used to build the trees, yielding a very fast training process; however, controlling sparsity (a proxy for interpretability) is challenging. In recent studies, optimal decision trees, where all decisions are optimized simultaneously, have shown a better learning performance, especially when oblique cuts are implemented. In this paper, we propose a continuous optimization approach to build sparse optimal classification trees, based on oblique cuts, with the aim of using fewer predictor variables in the cuts as well as along the whole tree. Both types of sparsity, namely local and global, are modeled by means of regularizations with polyhedral norms. The computational experience reported supports the usefulness of our methodology. In all our data sets, local and global sparsity can be improved without harming classification accuracy. Unlike greedy approaches, our ability to easily trade in some of our classification accuracy for a gain in global sparsity is shown.

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): “See, for instance, (Blanquero et al. 2019, 2020) for a related approach in Support Vector Machines.”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “The parameter values are ﬁxed to match those produced by the decision tree com-39 puted using CART.”
Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, methodology): “…various Mathematical Optimization methods to build better quality decision trees, e.g., (Bennett and Blue 1996; Bessiere, Hebrard, and OSullivan 2009; Verwer and Zhang 2017; Bertsimas and Dunn 2017; Silva 2017; Dash, G ¨ unl ¨ uk, and Wei 2018; Blanquero et al. 2018a; 2018b; Firat et al. 2018).”
Optimization Models for Machine Learning: A Survey (2019, background): “The approach of [37] which is extended in [38] to account for sparsity by using regularization, is based on a nonlinear continuous optimization formulation to learn decision trees with general splits.”
Recent advances in decision trees: an updated survey (2022, methodology): “3.1) have also been adapted to the optimal framework, such as OCT-H (Bertsimas and Dunn 2017), ORCT (Blanquero et al. 2021, 2020), SVM-1 ODT (Zhu et al. 2020) and the formulation by Aghaei et al. (2019).”