  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.
