Sparsity in Optimal Randomized Classification Trees

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.

This research has been financed in part by research projects EC H2020 Marie Skłodowska-Curie Actions, Research and Innovation Staff Exchange Network of European Data Scientists, NeEDS, Grant agreement ID 822214, COSECLA - Fundación BBVA, MTM2015-65915R, Spain, P11-FQM-7603 and FQM-329, Junta de Andaluc\'ıa. This support is gratefully acknowledged. Available online 16 December 2019

References in corpus (6)

• European Union regulations on algorithmic decision-making and a "right to explanation"
• Supersparse Linear Integer Models for Optimized Medical Scoring Systems
• Efficient non-greedy optimization of decision trees
• Learning optimization models in the presence of unknown relations
• Optimal randomized classification trees
• Optimal Generalized Decision Trees via Integer Programming

Cited by in corpus (6)

• Optimization Problems for Machine Learning: A Survey
• Generating collective counterfactual explanations in score-based classification via mathematical optimization
• MurTree: Optimal Classification Trees via Dynamic Programming and Search
• Margin Optimal Classification Trees
• The Backbone Method for Ultra-High Dimensional Sparse Machine Learning
• Dive into Decision Trees and Forests: A Theoretical Demonstration