Investigating MILP-based formulations for optimal regression trees

Decision trees are a popular and widely used machine learning algorithm for both classification and regression tasks. They are interpretable, easy to understand, and can handle a variety of data types, including categorical and numerical data, missing values, and outliers. Regression trees are a type of decision trees for forecasting continuous numeric values based on a collection of input features. They are especially useful in modeling complex systems because they can deal with non-linear relationships between input and output. Classical regression tree techniques train the tree one locally optimal split at a time using a greedy heuristic. As a consequence, the final tree may be far from optimal in terms of global accuracy. The improvement in performance of Mixed Integer Optimization (MIO) techniques over the last 30 years has enabled the construction of optimal regression trees, thereby overcoming this limitation. In this thesis, we focus on regression trees, and we study various Mixed-Integer Linear Programming (MILP) formulations to construct optimal regression trees. We first consider the case of trees with parallel splits (with decisions involving a single variable at each node) and binary input features, and then the case of trees with hyperplane splits (with decisions involving multiple variables at each node) and continuous input features. For the case of parallel splits, we compare alternative MILP formulations, and we describe the steps (in our reasoning) that lead us to our lightest and best performing formulation. Computational experiments on 11 real-world datasets taken from the well-known UCI Machine Learning Repository show that our MILP formulation reaches the same accuracies as the state-of-the-art flow-based formulations, while significantly improving the CPU time. For trees with hyperplane splits and continuous features, we adapt our MILP formulation for the parallel splits case. However, even for small datasets with shallow trees, it takes too long to find good quality solutions. To address this problem, we suggest a warm start algorithm, consisting of a clustering, a classification and a regression step, to produce a starting solution for the solver. Our experiments on 5 real-world datasets taken from UCI Machine Learning Repository show that the warm start increases accuracy significantly and acts as a strong starting point for our MILP formulation.

Gli alberi decisionali sono un algoritmo di apprendimento automatico popolare e ampiamente usato sia per compiti di classificazione che di regressione. Sono interpretabili, facili da capire e possono gestire una varietà di tipi di dati, tra cui dati categorici e numerici, valori mancanti e outlier. Gli alberi di regressione sono un tipo di alberi decisionali per la previsione di valori numerici continui basati su una collezione di caratteristiche di input. Sono particolarmente utili nella modellizzazione di sistemi complessi perché possono gestire relazioni non lineari tra input e output. Le tecniche di albero di regressione classico addestrano l'albero con una divisione localmente ottimale alla volta usando un'euristica avida. Di conseguenza, l'albero finale può essere lontano dall'essere ottimale in termini di accuratezza globale. Il miglioramento delle prestazioni delle tecniche di ottimizzazione a interi misti (MIO) negli ultimi 30 anni ha consentito la costruzione di alberi di regressione ottimali, superando così questa limitazione. In questa tesi, ci concentriamo sugli alberi di regressione e studiamo varie formulazioni di programmazione lineare a interi misti (MILP) per costruire alberi di regressione ottimali. Inizialmente consideriamo il caso di alberi con divisioni parallele (con decisioni che coinvolgono una singola variabile in ogni nodo) e caratteristiche di input binarie e poi il caso di alberi con divisioni iperpiane (con decisioni che coinvolgono più variabili in ogni nodo) e caratteristiche di input continue. Per il caso di divisioni parallele, confrontiamo formulazioni alternative di MILP e descriviamo i passaggi (nel nostro ragionamento) che ci portano alla nostra formulazione più leggera e performante. Gli esperimenti computazionali su 11 dataset del mondo reale presi dalla ben nota UCI Machine Learning Repository mostrano che la nostra formulazione MILP raggiunge le stesse accuratezze delle formulazioni basate sul flusso all'avanguardia, migliorando significativamente il tempo di elaborazione della CPU. Per gli alberi con divisioni iperpiane e caratteristiche continue, adattiamo la nostra formulazione MILP per il caso di divisioni parallele. Tuttavia, anche per piccoli dataset con alberi poco profondi, ci vuole troppo tempo per trovare soluzioni di buona qualità. Per affrontare questo problema, suggeriamo un algoritmo di avvio rapido, composto da un algoritmo di clustering, di classificazione e di regressione, per produrre una soluzione di partenza per il risolutore. I nostri esperimenti su 5 dataset del mondo reale presi dalla UCI Machine Learning Repository mostrano che l'avvio rapido aumenta significativamente l'accuratezza e agisce come un forte punto di partenza per la nostra formulazione MILP.