# Optimal randomized classification trees

arXiv: https://arxiv.org/abs/2110.11952 · HTML: https://mlsanity.com/paper/2110.11952/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 61 references that are in the map.
- First posted on arXiv 19 Oct 2021.

## Builds on (most cited first, 10 of 10)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [European Union regulations on algorithmic decision-making and a "right to explanation"](https://mlsanity.com/paper/1606.08813/) (2016)
- [A Random Forest Guided Tour](https://mlsanity.com/paper/1511.05741/) (2015)
- [Supersparse Linear Integer Models for Optimized Medical Scoring Systems](https://mlsanity.com/paper/1502.04269/) (2015)
- [Interpretable Classification Models for Recidivism Prediction](https://mlsanity.com/paper/1503.07810/) (2015)
- [Efficient non-greedy optimization of decision trees](https://mlsanity.com/paper/1511.04056/) (2015)
- [Simple rules for complex decisions](https://mlsanity.com/paper/1702.04690/) (2017)
- [Learning optimization models in the presence of unknown relations](https://mlsanity.com/paper/1401.1061/) (2014)
- [Random Forests for Big Data](https://mlsanity.com/paper/1511.08327/) (2015)
- [A Second-Order Method for Strongly Convex L1-Regularization Problems](https://mlsanity.com/paper/1306.5386/) (2013)

## Built on by (most cited first, 16 of 16)

- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Margin Optimal Classification Trees](https://mlsanity.com/paper/2210.10567/) (2022)
- [Multiclass Optimal Classification Trees with SVM-splits](https://mlsanity.com/paper/2111.08674/) (2021)
- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [An improved column-generation-based matheuristic for learning classification trees](https://mlsanity.com/paper/2308.11477/) (2023)
- [Flexible Modeling and Multitask Learning using Differentiable Tree Ensembles](https://mlsanity.com/paper/2205.09717/) (2022)
- [A Mathematical Programming Approach to Optimal Classification Forests](https://mlsanity.com/paper/2211.10502/) (2022)
- [Evaluation of Human-Understandability of Global Model Explanations using Decision Tree](https://mlsanity.com/paper/2309.09917/) (2023)
- [Rolling Lookahead Learning for Optimal Classification Trees](https://mlsanity.com/paper/2304.10830/) (2023)
- [Towards the Formalization of a Trustworthy AI for Mining Interpretable Models explOiting Sophisticated Algorithms](https://mlsanity.com/paper/2510.20621/) (2025)
- [On multivariate randomized classification trees: l0-based sparsity, VC~dimension and decomposition methods](https://mlsanity.com/paper/2112.05239/) (2021)
- [Loss-Optimal Classification Trees: A Generalized Framework and the Logistic Case](https://mlsanity.com/paper/2306.00857/) (2023)
- [Variable selection for Na"ive Bayes classification](https://mlsanity.com/paper/2401.18039/) (2024)
- [Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees](https://mlsanity.com/paper/2408.01297/) (2024)
- [Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction](https://mlsanity.com/paper/2609.05826/) (2026)
- [Largest Rashomon sets of decision trees for robust contextual optimization](https://mlsanity.com/paper/2610.04385/) (2026)

## Abstract (arXiv)

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.