Decomposition algorithms for training sparse soft regression trees

Decision trees are among the most popular and simple models for prediction and interpretation of datasets. Over decades of research, many algorithms have been developed, most of which are fast, greedy heuristics. Recent contributions to the field have formulated algorithms within Continuous Optimization paradigms, aiming to build better trees globally in a reasonable amount of time. In this thesis, we focus on the Soft Regression Tree model, which presents a non-linear, unconstrained optimization problem for building multivariate regression trees. In the first part, we propose decomposition algorithms that use different working set selection strategies to solve the problem formulation. The algorithm requires better starting points, and two initialization procedures are proposed to enhance the quality of the starting solutions. Results obtained from nine real-world datasets indicate which is the best combination of initialization procedure and working set selection strategies. In the second part, for the selected combination, we propose an approximation of the subproblem associated that is easier to solve and convex. Tests on both artificial and real-world datasets suggest that the approximated subprolem is superior in terms of solution quality. Finally, to improve interpretability, we propose an extension of the algorithm. Sparsity in the tree’s branch nodes is promoted by adding an l1-norm penalty term, and a bisection search is devised to fine-tune the penalty hyperparameter during training. This sparsity-promoting version of the algorithm produces very sparse trees without loss of accuracy and incurs little additional time cost. The effectiveness and accuracy of the algorithm are demonstrated on both small and large datasets.

Gli alberi decisionali sono tra i modelli più popolari e semplici per la previsione e l'interpretazione di insiemi di dati. Nel corso di decenni di ricerca, sono stati sviluppati molti algoritmi, la maggior parte dei quali sono euristiche veloci e greedy. Recenti contributi nel campo formulano algoritmi nell'ottica di ottimizzazione continua, con l'obiettivo di costruire alberi migliori in modo globale e in tempi ragionevoli. In questa tesi, ci concentriamo sul modello Soft Regression Tree, che presenta un problema di ottimizzazione non lineare e non vincolato per costruire alberi di regressione multivariata. Nella prima parte della tesi, proponiamo un metodo di decomposizione che per risolvere la formulazione del problema seleziona diversi insieme di lavoro. L'algoritmo richiede soluzioni iniziali migliori e vengono proposte due procedure di inizializzazione per migliorarne la qualità. I risultati ottenuti su nove dataset reali mostrano quale sia la migliore combinazione tra procedura di inizializzazione e insieme di lavoro considerato. Nella seconda parte, per la combinazione selezionata, proponiamo un'approssimazione convessa del sottoproblema associato che è più facile da risolvere. Test su dataset artificiali e reali suggeriscono che la funzione obiettivo convessa è superiore in termini di qualità della soluzione e costo computazionale. Infine, per migliorare l'interpretabilità, proponiamo un'estensione dell'algoritmo. Incentiviamo l'addestramento di alberi sparsi aggiungendo una penalizzazione con norma l1. Per ottimizzare il parametro di penalizzazione durante l'addestramento proponiamo un metodo di ricerca a bisezione. Questa versione dell'algoritmo è in grado di produrre alberi decisionali molto sparsi, più interpretabili, senza perdita di accuratezza e con un costo computazionale aggiuntivo limitato. L'efficacia e l'accuratezza di questo algoritmo sono dimostrate su dataset di medie e grandi dimensioni.