Soft classification trees: model variants, decomposition algorithms and pruning techniques

Classification trees are widely used Machine Learning models due to their interpretability and good accuracy. Traditional methods, such as CART (1984), build greedily the trees one node at a time. In the last decades, with the remarkable progresses in computing power and optimization solvers, there has been increasing interest in optimal classification trees, where all the model parameters are optimized simultaneously. Blanquero et al. (2021) introduced a nonlinear continuous optimization formulation for training Soft Classification Trees (SCTs) with soft decision rules at branch nodes. In this work, we present two de-randomized SCT model variants and evaluate them against the original model, highlighting the advantages in terms of interpretability and prediction complexity. Given the computational challenges of training such SCTs on large datasets, decomposition algorithms are proposed to improve training effectiveness by splitting the training problem into smaller, more manageable subproblems. To avoid that the optimization gets stuck in poor solutions, ad hoc heuristics are devised. The decomposition algorithms combined with the reassignment heuristics significantly reduce the solution dependence on the initialization and favor a more effective exploration of the solution space. The benefits of these training methods are demonstrated empirically through experiments conducted on 14 well-known datasets from the machine learning literature. Additionally, to better exploit the SCT structure and mitigate the slight tendency towards overfitting, post-processing pruning techniques are investigated. This post-processing pruning step generates memory-efficient and interpretable SCTs with higher testing accuracy. We propose two distinct pruning techniques: the first one is an adaptation of the CART pruning step and the second one is an approach based on an Integer Linear Programming formulation. The effectiveness of these techniques is demonstrated on 11 datasets, underscoring the crucial role of a pruning phase in refining model performance.

Gli alberi di classificazione sono modelli di Machine Learning ampiamente utilizzati per la loro interpretabilità e buona accuratezza. I metodi tradizionali, come CART (1984), costruiscono gli alberi in maniera greedy un nodo per volta. Negli ultimi decenni, grazie ai notevoli progressi nella potenza di calcolo e nei solutori di ottimizzazione, è aumentato l'interesse per gli alberi di classificazione ottimali, in cui tutti i parametri del modello vengono ottimizzati simultaneamente. Blanquero et al. (2021) hanno introdotto una formulazione di ottimizzazione continua non lineare per l'addestramento degli alberi di classificazione soft (Soft Classification Tree, SCT) con regole decisionali soft ai nodi di branching. In questo lavoro, presentiamo due varianti del modello SCT de-randomizzato e le valutiamo rispetto al modello originale, evidenziando i vantaggi in termini di interpretabilità e complessità della previsione. Data la sfida computazionale dell'addestramento di tali SCT su grandi dataset, vengono proposti algoritmi di decomposizione per migliorare l'efficacia dell'addestramento, suddividendo il problema di addestramento in sottoproblemi più gestibili. Per evitare che l'ottimizzazione si blocchi in soluzioni subottimali, vengono introdotte euristiche ad hoc. Gli algoritmi di decomposizione combinati con le euristiche di riassegnamento riducono significativamente la dipendenza della soluzione dall'inizializzazione e favoriscono un'esplorazione più efficace dello spazio delle soluzioni. I benefici di questi metodi di addestramento vengono dimostrati empiricamente attraverso esperimenti condotti su 14 dataset ben noti nella letteratura del machine learning. Inoltre, per sfruttare meglio la struttura degli SCT e mitigare la leggera tendenza all’overfitting, vengono investigate tecniche di potatura in fase di post-processing. Questa fase di potatura genera SCT più efficienti in termini di occupazione di memoria, più interpretabili e con un’accuratezza di testing più alta. Proponiamo due tecniche di potatura distinte: la prima è un adattamento del processo di potatura di CART e la seconda è un approccio basato su una formulazione di Programmazione Lineare Intera. L'efficacia di queste tecniche viene dimostrata su 11 dataset, sottolineando il ruolo fondamentale di una fase di potatura nel migliorare le prestazioni del modello.