Dottoressa di ricerca

ciclo: XXXVI

supervisore: Laura Palagi

Titolo della tesi: Interpretable Machine Learning: Leveraging SVMs to construct Optimal Decision Trees

In recent years, with the widespread use of machine learning (ML) methods in real-world applications, there has been growing attention to interpretable ML models that can give explanatory insights into their decision-making process. Thanks to their interpretability, Decision Trees are one of the most widely used Supervised ML tools for classification tasks. Due to the remarkable advances over the last thirty years in mixed integer programming, various approaches have been proposed to formulate the problem of training an Optimal Classification Tree (OCT) as a mixed-integer model. As a first contribution, we present a novel mixed integer quadratic programming (MIQP) formulation for the OCT problem, which exploits the generalization capabilities of Support Vector Machines (SVMs) for binary classification. The proposed model, denoted as Margin Optimal Classification Tree (MARGOT), defines the decision rules of the tree as maximum margin multivariate hyperplanes following the soft SVM approach along the binary tree structure. MARGOT has been evaluated on benchmark datasets from the UCI repository against state-of-the-art OCT approaches. The MARGOT formulation turns out to be easier to solve than other OCT methods, and the generated tree better generalizes on new observations. To enhance the interpretability of our method, we analyze two alternative versions of MARGOT, which include feature selection techniques inducing sparsity of the hyperplanes’ coefficients. The two interpretable versions effectively select the most relevant features, maintaining good prediction quality. Along this research line, we propose a variant of MARGOT, referred to as the Hard Margin Optimal Classification Tree (MARGOThard), which employs margin-based hyperplane splits across the nodes of the tree relying on either the hard or the soft SVM paradigm. Following the approach adopted for MARGOT, we developed a feature selection embedded version that promotes the local sparsity of the decision rules. To assess the main differences between the two margin optimal tree formulations, we provide a comprehensive set of results comparing MARGOT and MARGOThard, which show that both methods represent valid approaches for learning robust classifiers. Further, for all the proposed optimization problems, we developed ad-hoc heuristic algorithms to efficiently produce a feasible solution that can be used as a warm start for the optimization procedure. Lastly, driven by the fact that the margin optimal tree models exhibit a particular decomposable structure, we lay the foundations for a future research line, whose final aim is to develop a tailored decomposition algorithm that leverages the SVM nature of the proposed problems. Along this direction, we propose an initial version of a Benders-like method to handle the simpler case of margin optimal trees, based on ℓ1-SVMs, that can be formulated as mixed-integer linear programs. This early-stage work offers insights into the design of a general decomposition procedure for the problem and paves the way for devising an ad-hoc algorithm for the MIQP-based versions of margin optimal trees.

Produzione scientifica

11573/1657211 - 2024 - Margin Optimal Classification Trees
D’Onofrio, Federico; Grani, Giorgio; Monaci, Marta; Palagi, Laura - 01a Articolo in rivista
rivista: COMPUTERS & OPERATIONS RESEARCH (Elsevier Science Limited:Oxford Fulfillment Center, PO Box 800, Kidlington Oxford OX5 1DX United Kingdom:011 44 1865 843000, 011 44 1865 843699, EMAIL:,, INTERNET:,, Fax: 011 44 1865 843010) pp. - - issn: 0305-0548 - wos: WOS:001097562000001 (4) - scopus: 2-s2.0-85175167637 (4)

11573/1669860 - 2024 - Unboxing Tree ensembles for interpretability: A hierarchical visualization tool and a multivariate optimal re-built tree
Di Teodoro, Giulia; Monaci, Marta; Palagi, Laura - 01a Articolo in rivista
rivista: EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION (Heidelberg: Springer) pp. - - issn: 2192-4406 - wos: WOS:001166643700001 (0) - scopus: 2-s2.0-85182604515 (0)

11573/1645969 - 2024 - An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents
Monaci, Marta; Agasucci, Valerio; Grani, Giorgio - 01a Articolo in rivista
rivista: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL:, INTERNET:, Fax: 011 31 20 4853598) pp. 910-926 - issn: 0377-2217 - wos: WOS:001085357600001 (2) - scopus: 2-s2.0-85167977834 (2)

11573/1675899 - 2023 - Optimization-based approaches for learning Optimal Classification Trees
D'onofrio, Federico; Monaci, Marta; Palagi, Laura - 01a Articolo in rivista
rivista: IFORS NEWS (Manila: International Federation of Operational Research Societies) pp. 5-7 - issn: 2223-4373 - wos: (0) - scopus: (0)

11573/1565049 - 2021 - Heuristics for the Traveling Salesperson Problem based on Reinforcement Learning
Coppola, Corrado; Grani, Giorgio; Monaci, Marta; Palagi, Laura - 13a Altro ministeriale

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma