# Margin Optimal Classification Trees

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 50 references that are in the map.
- First posted on arXiv 19 Oct 2022.

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

- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making](https://mlsanity.com/paper/1903.10598/) (2019)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Optimal randomized classification trees](https://mlsanity.com/paper/2110.11952/) (2021)
- [Optimization Problems for Machine Learning: A Survey](https://mlsanity.com/paper/1901.05331/) (2019)
- [HHCART: An Oblique Decision Tree](https://mlsanity.com/paper/1504.03415/) (2015)
- [Sparsity in Optimal Randomized Classification Trees](https://mlsanity.com/paper/2002.09191/) (2020)
- [A novel embedded min-max approach for feature selection in nonlinear support vector machine classification](https://mlsanity.com/paper/2004.09863/) (2020)
- [Robust Optimal Classification Trees under Noisy Labels](https://mlsanity.com/paper/2012.08560/) (2020)
- [Multiclass Optimal Classification Trees with SVM-splits](https://mlsanity.com/paper/2111.08674/) (2021)
- [Mixed Integer Linear Programming for Feature Selection in Support Vector Machine](https://mlsanity.com/paper/1808.02435/) (2018)
- [A Mathematical Programming approach to Binary Supervised Classification with Label Noise](https://mlsanity.com/paper/2004.10170/) (2020)

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

- [An improved column-generation-based matheuristic for learning classification trees](https://mlsanity.com/paper/2308.11477/) (2023)
- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [Unboxing Tree Ensembles for interpretability: a hierarchical visualization tool and a multivariate optimal re-built tree](https://mlsanity.com/paper/2302.07580/) (2023)
- [Loss-Optimal Classification Trees: A Generalized Framework and the Logistic Case](https://mlsanity.com/paper/2306.00857/) (2023)
- [A Unified Optimization Framework for Multiclass Classification with Structured Hyperplane Arrangements](https://mlsanity.com/paper/2510.05047/) (2025)
- [RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees](https://mlsanity.com/paper/2510.23901/) (2025)
- [Scaling Optimal Classification Trees via Adaptive Feature and Sample Reduction](https://mlsanity.com/paper/2609.05826/) (2026)

## Abstract (arXiv)

In recent years, there has been growing attention to interpretable machine learning models which can give explanatory insights on their behaviour. Thanks to their interpretability, decision trees have been intensively studied for classification tasks and, due to the remarkable advances in mixed integer programming (MIP), various approaches have been proposed to formulate the problem of training an Optimal Classification Tree (OCT) as a MIP model. We present a novel mixed integer quadratic formulation for the OCT problem, which exploits the generalization capabilities of Support Vector Machines for binary classification. Our model, denoted as Margin Optimal Classification Tree (MARGOT), encompasses maximum margin multivariate hyperplanes nested in a binary tree structure. To enhance the interpretability of our approach, we analyse two alternative versions of MARGOT, which include feature selection constraints inducing sparsity of the hyperplanes' coefficients. First, MARGOT has been tested on non-linearly separable synthetic datasets in a 2-dimensional feature space to provide a graphical representation of the maximum margin approach. Finally, the proposed models have been tested on benchmark datasets from the UCI repository. The MARGOT formulation turns out to be easier to solve than other OCT approaches, and the generated tree better generalizes on new observations. The two interpretable versions effectively select the most relevant features, maintaining good prediction quality.