Sparse soft decision trees and kernel logistic regression : optimization models and algorithms

Machine Learning (ML) methods have recently achieved remarkable performance in several tasks arising in a variety of fields, ranging from medical diagnosis to natural language processing. Unfortunately, most of the underlying models are black boxes (e.g., deep neural networks) and this may substantially restrict their applicability. Model interpretability is of particular importance in applications where the ML models support the decisions of the domain experts and justifiable predictions are required. In fields such as healthcare, finance, education and criminal justice, ML models should not only provide accurate predicted responses for new input vectors but also valuable explanations concerning the derivation of the response in terms of the features. For some ML models, the interpretability can be improved by increasing the sparsity, that is, by reducing the number of nonzero parameters. According to Occam’s razor principle, sparser models may also lead to lower generalization error. In this thesis, we investigate and improve two ML methods, namely, soft decision trees for classification and regression tasks as well as kernel logistic regression for binary classification. In particular, we devise improved model variants, establish theoretical properties and develop decomposition algorithms for training them. Decision trees are supervised ML methods widely used for classification and regression tasks. They are inherently interpretable since, for every input vector, they reveal to the domain experts the clear sequence of decisions (explanation) leading to the tree response. A decision tree is a binary directed graph where at each branch (internal) node a splitting rule is applied to the input space and at each leaf node is associated either a class label or a continuous response. During the past decade, growing attention has been devoted to globally optimized decision trees with deterministic or soft splitting rules at each branch nodes, which are trained by optimizing the error function over all the tree parameters. Concerning soft classification trees, we first propose alternative sparsification methods based on concave approximation of the l0 norm. The results reported for 24 benchmark datasets from UCI and KEEL repositories indicate that our approximate l0 norm performs better than the original l1 and l∞ regularizations and leads to sparser trees, namely, with a smaller number input features per branch node. Then, we determine bounds on the Vapnik-Chervonenkis (VC) dimension of such models, which plays a key role in statistical learning to derive bounds on testing (generalization) error. Finally, we present a general node-based decomposition scheme for training soft classification trees and a practical proximal version. Experiments on larger datasets show that the proposed decomposition method is able to significantly reduce the training times without compromising the testing accuracy. As to soft regression trees, we propose a model variant where, for every data point, a potential linear prediction is available at each leaf node but the actual tree prediction is the one associated to a particular leaf node. Our nonlinear optimization formulation for training such soft trees is well-suited to decomposition and to impose fairness constraints. After investigating the universal approximation property of our model variant, we present a convergent node-based decomposition algorithm which includes a heuristic for the reassignment of the data points along the tree and a specific initialization procedure. Experiments on 15 benchmark datasets from different types of applications show that our model trained with the decomposition algorithm outperforms two state-of-the-art soft and deterministic regression tree models based on continuous nonlinear and discrete optimization approaches in terms of both accuracy and/or computational time. Other experiments on the same datasets show that our soft regression tree approach is significantly more robust than classical Hierarchical Mixture of Experts trained with the Expectation-Maximization algorithm and provides single soft trees whose testing accuracy is comparable to that of Random Forest. We also present l0-based sparsification method to tackle sparsity on the branch nodes of soft regression tree. Moreover, we focus on enhancing the flexibility of such trees to consider two distinct group fairness measures, addressing potential algorithmic bias. Finally, we apply our model and decomposition algorithm to investigate a real-world case on the evolution of multidimensional inequality of opportunity in Australian HILDA survey dataset. Logistic regression is a well-known probabilistic classification model that provides in addition to the class membership of the input vector also an estimate of the corresponding conditional probability. While the use of kernels allows to capture complex nonlinear relationships within the data, the resulting kernel logistic regression models are generally not sparse with respect to data points. Nevertheless, inducing sparsity by involving only a subset of data points can positively affect the model’s generalization capability. We consider sparse kernel logistic regression for binary classification. In particular, we present an exact sparsity-inducing formulation and devise a decomposition algorithm of sequential minimal optimization type, which exploits second order information, and for which we establish global convergence. Numerical experiments conducted on 12 datasets from the literature show that the proposed binary kernel logistic regression approach achieves a competitive trade-off between accuracy and sparsity with respect to two well-known alternative approaches, while retaining the advantages of providing informative estimates of the class probabilities.

I metodi di Machine Learning (ML) hanno recentemente raggiunto prestazioni notevoli in diversi compiti relativi ad una grande varietà di campi, dalla diagnosi medica all'elaborazione del linguaggio naturale. Sfortunatamente, la maggior parte dei modelli sottostanti sono “black boxes” (ad esempio, reti neurali profonde) e questo può limitare in maniera sostanziale la loro applicabilità. L'interpretabilità del modello è di particolare importanza in applicazioni in cui i modelli di ML supportano le decisioni degli esperti del settore e sono necessarie predizioni giustificabili. In campi come la sanità, la finanza, l'istruzione e la giustizia penale, i modelli di ML non dovrebbero solo fornire come risposta previsioni accurate per nuovi vettori di input, ma anche spiegazioni valide riguardo la derivazione della risposta in termini delle caratteristiche dell’input. Per alcuni modelli di ML, l'interpretabilità può essere migliorata aumentando la sparsitá, cioè riducendo il numero di parametri non nulli. Secondo il principio del rasoio di Occam, modelli più sparsi possono anche portare a un errore di generalizzazione inferiore. In questa tesi, studiamo e miglioriamo due metodi di ML, ossia gli alberi decisionali continui (in inglese soft decision trees) per compiti di classificazione e regressione e la regressione logistica kernel per la classificazione binaria. In particolare, abbiamo ideato varianti migliorate del modello, stabilito proprietà teoriche e sviluppato algoritmi di decomposizione per l'addestramento. Gli alberi decisionali sono metodi di ML supervisionati ampiamente utilizzati per compiti di classificazione e regressione. Sono intrinsecamente interpretabili poiché, per ogni vettore di input, rivelano agli esperti del settore la chiara sequenza di decisioni (spiegazioni) che portano alla risposta dell'albero. Un albero decisionale è un grafo binario diretto in cui a ogni nodo di ramificazione (nodo interno) viene applicata una regola di divisione allo spazio di input e a ogni nodo foglia è associata un'etichetta di classe o una risposta continua. Nell'ultimo decennio, un'attenzione crescente è stata dedicata all’ottimizzazione a livello globale degli alberi decisionali con regole di suddivisione a ogni nodo interno deterministiche (rigide) o continue (morbide), cioè addestrando tali alberi attraverso l’ottimizzazione della funzione di errore su tutti i parametri dell'albero. Per quanto riguarda gli alberi decisionali continui per compiti di classificazione, proponiamo innanzitutto metodi alternativi di sparsificazione basati sull'approssimazione concava della norma l0. I risultati riportati per 24 set di dati di riferimento provenienti dagli archivi UCI e KEEL indicano che la nostra approssimazione della norma l0 ha prestazioni migliori rispetto alle regolarizzazioni originali l1 e l∞ e porta ad alberi più sparsificati, cioè con un numero minore di caratteristiche di input per nodo di ramificazione. In seguito, determiniamo dei limiti sulla dimensione Vapnik-Chervonenkis (VC) di tali modelli, la quale svolge un ruolo fondamentale nell'apprendimento statistico per ricavare dei limiti sull'errore di test (generalizzazione). Infine, presentiamo uno schema generale di decomposizione basato sui nodi interni per l'addestramento di alberi di classificazione continui e una versione pratica con un termine di “proximal”. Gli esperimenti condotti su grandi insiemi di dati dimostrano che il metodo di decomposizione proposto è in grado di ridurre significativamente i tempi di addestramento senza compromettere l'accuratezza nei dati di test. In merito agli alberi decisionali continuo per compiti di regressione, proponiamo una variante del modello in cui, per ogni dato, è disponibile una potenziale previsione lineare in ogni nodo foglia, ma la previsione effettiva dell'albero è quella associata ad uno in particolare. La nostra formulazione di ottimizzazione non lineare per l'addestramento di questi alberi morbidi è adatta alla decomposizione e all'imposizione di vincoli di equità. Dopo aver analizzato la proprietà di approssimazione universale della nostra variante del modello, presentiamo un algoritmo di decomposizione convergente basato sui nodi interni che include un'euristica per la riassegnazione dei dati lungo l'albero e una procedura di inizializzazione specifica. Esperimenti su 15 set di dati di riferimento provenienti da diversi tipi di applicazioni mostrano che il nostro modello addestrato con l'algoritmo di decomposizione supera sia in termini di precisione che di tempo di calcolo due modelli alternativi di albero di regressione continuo e deterministico rappresentanti lo stato dell'arte e basati su approcci di ottimizzazione continua non lineare e discreta. Altri esperimenti sugli stessi set di dati mostrano che il nostro approccio SRT è significativamente più robusto del classico “Hierarchical Mixture of Experts” addestrata con l'algoritmo di “Expectation-Maximization” e fornisce singoli alberi continui la cui accuratezza nei test è paragonabile a quella dei “Random Forest”. Presentiamo anche un metodo di sparsificazione basato su l0 per affrontare la sparsità sui nodi interni dell'albero di regressione continuo. Inoltre, ci concentriamo sul miglioramento della flessibilità di tali alberi per considerare due distinte misure di equità di gruppo, affrontando i potenziali “bias” algoritmici. Infine, applichiamo il nostro modello e l'algoritmo di decomposizione per indagare un caso reale sull'evoluzione dell'ineguaglianza multidimensionale di opportunità nel dataset del sondaggio australiano HILDA. La regressione logistica è un modello di classificazione probabilistica ben noto che fornisce, oltre all'appartenenza alla classe del vettore di input, anche una stima della probabilità condizionale corrispondente. Mentre l'uso di kernel consente di catturare relazioni non lineari complesse all'interno dei dati, i modelli di regressione logistica con kernel risultanti non sono generalmente sparsi rispetto ai punti dati. Tuttavia, indurre sparsitá coinvolgendo solo un sottoinsieme di punti dati può influire positivamente sulla capacità di generalizzazione del modello. In questo lavoro consideriamo la regressione logistica con kernel sparsa per la classificazione binaria. In particolare, presentiamo una formulazione esatta che induce la sparsità e sviluppiamo un algoritmo di decomposizione di tipo “sequential minimal optimization”, che sfrutta le informazioni del secondo ordine e per il quale stabiliamo la convergenza globale. Esperimenti numerici condotti su 12 insiemi di dati tratti dalla letteratura dimostrano che l'approccio proposto per la regressione logistica binaria con kernel raggiunge un compromesso competitivo tra accuratezza e sparsità rispetto a due noti approcci alternativi, mantenendo il vantaggio di fornire stime informative delle probabilità delle classi. Consideriamo la regressione logistica kernel sparsa per la classificazione binaria. In particolare, presentiamo una formulazione esatta per indurre sparsitá e ideiamo un algoritmo di decomposizione del tipo ottimizzazione minima sequenziale, che sfrutta le informazioni di secondo ordine, e per il quale stabiliamo la convergenza globale. Esperimenti numerici condotti su 12 dataset della letteratura mostrano che l'approccio proposto di regressione logistica kernel binaria raggiunge un compromesso competitivo tra accuratezza e sparsitá rispetto a due approcci alternativi ben noti, mantenendo i vantaggi di fornire stime informative delle probabilità di classe.