EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3997. Margin Optimal Trees: a novel formulation and a SVM-based decomposition approach

Invited abstract in session TB-52: Mixed Integer Optimization II, stream Combinatorial Optimization.

Tuesday, 10:30-12:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Marta Monaci
Institute for System Analysis and Computer Science "Antonio Ruberti" (IASI), National Research Council of Italy
2. Laura Palagi
Department of Computer, Control, and Management Engineering A. Ruberti, Sapienza University of Rome

Abstract

In recent years there has been growing attention to interpretable machine learning models which can give explanatory insights into their decision-making process. Thanks to their interpretability, decision trees have been intensively studied for classification tasks. Due to the remarkable advances in mixed-integer programming (MIP) of the last years, various MIP models for training an Optimal Classification Tree (OCT) have been proposed. Along the research line of Margin Optimal Trees [1], we present an alternative mixed-integer quadratic formulation to construct multivariate OCTs. The proposed model defines the decision rules of the tree as maximum margin hyperplanes following the Support Vector Machine (SVM) paradigm along the binary tree structure. Further, we exploit the decomposable structure of the model to develop a tailored algorithmic approach able to leverage the SVM nature of each subproblem. First, the algorithm 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 method has been tested on benchmark datasets from the UCI repository in order to evaluate its computational efficiency and the generalization capabilities of the generated trees.

References
[1] F. D’Onofrio, G. Grani, M. Monaci, and L. Palagi. Margin optimal classification trees. Computers & Operations Research, 161:106441, 2024.

Keywords

Status: accepted

Back to the list of papers