Optimal randomized classification trees

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.

arXiv commentThis research has been financed in part by research projects EC H2020 MSCA RISE NeEDS (Grant agreement ID: 822214), FQM-329 and P18-FR-2369 (Junta de Andalucía), and PID2019-110886RB-I00 (Ministerio de Ciencia, Innovación y Universidades, Spain). This support is gratefully acknowledged

References in corpus (7)

• Community detection in graphs
• European Union regulations on algorithmic decision-making and a "right to explanation"
• Supersparse Linear Integer Models for Optimized Medical Scoring Systems
• Interpretable Classification Models for Recidivism Prediction
• Efficient non-greedy optimization of decision trees
• Least quantile regression via modern optimization
• Learning optimization models in the presence of unknown relations

Cited by in corpus (7)

• Optimization Problems for Machine Learning: A Survey
• Variable selection for Naïve Bayes classification
• Sparsity in Optimal Randomized Classification Trees
• Margin Optimal Classification Trees
• The Backbone Method for Ultra-High Dimensional Sparse Machine Learning
• Evaluation of Human-Understandability of Global Model Explanations using Decision Tree
• Coresets for Decision Trees of Signals