Optimal randomized classification trees

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

52 citations recorded by the source corpus.

Abstract Classification and Regression Trees (CARTs) are off-the-shelf techniques in modern Statistics and Machine Learning. CARTs are traditionally built by means of a greedy procedure, sequentially deciding the splitting predictor variable(s) and the associated threshold. This greedy approach trains trees very fast, but, by its nature, their classification accuracy may not be competitive against other state-of-the-art procedures. Moreover, controlling critical issues, such as the misclassification rates in each of the classes, is difficult. To address these shortcomings, optimal decision trees have been recently proposed in the literature, which use discrete decision variables to model the path each observation will follow in the tree. Instead, we propose a new approach based on continuous optimization. Our classifier can be seen as a randomized tree, since at each node of the decision tree a random decision is made. The computational experience reported demonstrates the good performance of our procedure.

Subfields: Artificial Intelligence, Statistical Learning Theory, 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 Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

Mathematical optimization in classification and regression trees (2021, methodology): “In this section, we describe how Optimal Randomized Classification and Regression Trees work and what type of Nonlinear Continuous Optimization formulations have been provided in Blanquero et al. (2021, 2020a, b) to build them.”
Generalized and Scalable Optimal Sparse Decision Trees (2020, methodology): “Solvers have been used from the 1990’s (Bennett, 1992; Bennett & Blue, 1996) to the present (Verwer & Zhang, 2019; Blanquero et al., 2018; Nijssen et al., 2020; Bertsimas & Dunn, 2017; Rudin & Ertekin, 2018; Menickelly et al., 2018; Vilas Boas et al., 2019), but these generic solvers tend to be slow”
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).”
Optimal Sparse Decision Trees (2019, background): “Problems with greedy splitting and pruning have been known since the early 1990’s, when mathematical programming tools had started to be used for creating optimal binary-split decision trees [3, 4], in a line of work [5, 6, 16, 18] until the present [20], however, these techniques use all-purpose to”
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): “…can be easily formulated as linear constraints, the majority of MP approaches assume that all attributes are numerical, relying on transformations such as one-hot encoding to handle categorical data (Bertsimas and Dunn 2017; Verwer and Zhang 2017, 2019; Firat et al. 2020; Blanquero et al. 2021).”
Sparsity in Optimal Randomized Classification Trees (2020, methodology): “…trees have been grown with both orthogonal ( Bertsimas & Dunn, 2017; Firat et al., 2019; Günlük et al., 2019 ) and oblique cuts ( Bennett & Blue, 1996; Bertsimas & Dunn, 2017; Blanquero et al., 2018; Norouzi, Collins, Johnson, Fleet, & Kohli, 2015; Verwer & Zhang, 2017; Verwer et al., 2017 ).”