An improved training algorithm for soft classification trees

In this thesis we improve the performance of a recently proposed algorithm for training soft classification trees, starting from a non-linear continuous formulation of the problem we investigate in two directions. The first is to experiment with alternative decomposition training algorithms and the second is to devise different initialization strategies. Regarding decomposition methods, we build upon a previous work and we propose several new working set selection strategies and two novel steps for the algorithms, so as to reduce the size of the training dataset and to exploit the complete tree. Experimental results on extensively used datasets indicate a notable improvement both in training and testing in accuracy, compared to the algorithm without decomposition, and the proposed working set selection strategies perform better than the existing ones. The second part of our work is devoted to the aspect of the initialization procedure. We design a procedure for building a good starting solution for the solver, based on clustering techniques. In particular, we partition the training dataset into clusters across the tree in such a way to obtain a hierarchical structure of the data points from which to derive the initial parameters. We investigate different clustering techniques and we combine the best performing ones. Numerical experiments on considered datasets suggest that the initialization procedure leads to significant improvements in terms of both train and test accuracy with respect to random starting solutions. Finally, we explore a possible technique for handling unbalanced datasets by modifying some parameters in the cost function, without increasing the complexity of the training problem. The experimental results are promising and we observe a noteworthy improvement in the test and training accuracies for under-represented classes of data points.

In questa tesi l’obbiettivo è quello di migliorare le prestazioni di un algoritmo recentemente proposto per l’addestramento di alberi di classificazione soft. Partendo da una formulazione continua non lineare del problema, esploriamo in due direzioni. La prima consiste nella sperimentazione di strategie alternative di decomposizione, mentre la seconda consiste nell’ideare procedure di inizializzazione. Per quanto riguarda i metodi di decomposizione, ci basiamo su un lavoro precedente e proponiamo diverse strategie di selezione dei working set e due fasi nuove rispetto all’algoritmo su cui ci basiamo, in modo da ridurre le dimensioni dell’insieme di dati di addestramento e sfruttare l’intero albero. I risultati sperimentali su dataset ampiamente utilizzati indicano un notevole miglioramento in termini di accuratezza, rispetto all’algoritmo senza decomposizione, e le strategie di selezione dei working set proposte si performano meglio rispetto a quelle esistenti. La seconda parte del nostro lavoro è dedicata all’aspetto della procedura di inizializzazione. Ideiamo una procedura per fornire al risolutore una buona soluzione iniziale, basata su tecniche di clustering. In particolare, suddividiamo l’insieme dei dati di addestramento in cluster lungo l’albero in modo da ottenere una struttura gerarchica dei dati da cui derivare i parametri iniziali. Esploriamo diverse tecniche di clustering e combiniamo quelle che funzionano meglio. Gli esperimenti sui dataset considerati mostrano che la procedura di inizializzazione porta a significativi miglioramenti in termini di accuratezza rispetto alla versione in cui vengono fornite soluzioni iniziali casuali. Infine, proponiamo una possibile strategia per gestire dataset sbilanciati, modificando alcuni parametri nella funzione di costo, senza aumentare la complessità del problema di addestramento. I risultati sperimentali sono promettenti e osserviamo un notevole miglioramento nelle accuratezze per le classi sottorappresentate.