Improvements and extensions of sparse optimal randomized classification trees

Decision trees are a very popular family of classification models because of their interpretability and of the interesting results they offer in terms of accuracy. However, they sometimes tend to overfit the data and, if allowed to grow large, they lose interpretability. In the first two decades the algorithms used to train decision trees (e.g. CART) were based on greedy criteria since building an optimal decision tree is NP-hard. During the last five years, some works aimed at optimal decision trees exploiting state of the art mixed-integer linear or non linear continuous optimization techniques. In this thesis, we start from a very recent continuous optimization approach for building Optimal Randomized Classification Trees (ORCTs) and for sparsifying them (S-ORCTs). Sparsification is important not only for feature selection but also to improve interpretability. In the first part, we propose alternative methods to improve ORCT sparsification based on l0-norm approximation. The results obtained on nine datasets from the UCI Machine Learning Repository indicate that our methods are more efficient than the original approach and lead to more interpretable models. We also discuss the symmetry of the solutions and we compare our objective function with the SVM cost function. In the second part, we propose an extension of the above S-ORCT methods which includes polynomial feature expansion. The algorithm exploits the information adaptively gathered during the training process of the base model in order to generate new couples of predictor variables wisely. Combining it with our methods for sparsification often leads to better performance in terms of accuracy, while preserving the model interpretability. Finally, we apply and compare the classical ensemble approaches (bagging, random forest, boosting techniques) to ORCTs, as it has been done previously for CARTs.

Gli alberi decisionali sono una celebre famiglia di modelli di classificazione spesso usati per la loro interpretabilità e per gli interessanti risultati che offrono in termini di accuratezza. Tuttavia sono a volte inclini all’eccessivo adattamento ai dati e, se si lasciano crescere, si rischia di perdere interpretabilità. Nei primi due decenni gli algoritmi (ad es. CART) utilizzati per addestrare gli alberi decisionali si basavano su criteri greedy poiché il problema di determinare alberi decisionali ottimali è NP-difficile. Negli ultimi cinque anni, alcuni lavori mirano ad ottenere alberi decisionali ottimali tramite tecniche di ottimizzazione mista intera o non lineare continua. Questa tesi tratta di un recente approccio di ottimizzazione continua per costruire alberi decisionali randomizzati ottimali per la classificazione (ORCT) e per la loro sparsificazione (S-ORCT). La sparsificazione è un aspetto fondamentale sia per la selezione delle variabili, sia perché consente al modello di essere più interpretabile. Nella prima parte di questo lavoro, proponiamo dei metodi alternativi di riduzione dello spazio delle variabili basati sull'approssimazione della norma l0. I risultati ottenuti su nove basi di dati tratti dal Machine Learning Repository UCI, mostrano come i nostri metodi si rivelino più efficienti di quelli dell'approccio originale e portano a modelli più interpretabili. Inoltre discutiamo della simmetria delle soluzioni e confrontiamo la nostra funzione obiettivo con quella del noto metodo di classificazione SVM. Nella seconda parte proponiamo un'estensione dei suddetti metodi S-ORCT che prevede l'espansione del spazio delle variabili attraverso l’inclusione di termini polinomiali di grado superiore ad uno. L'algoritmo sfrutta le informazioni raccolte durante l’addestramento del modello base per generare nuove coppie di variabili predittive. Combinando questa estensione con i nostri metodi di sparsificazione si ottengono spesso migliori prestazioni in termini di accuratezza mantenendo il modello interpretabile. Nella parte finale applichiamo e confrontiamo i classici metodi di apprendimento di insieme agli SORCT (bagging, random forest, tecniche di boosting), in passato applicati per i CART.