Distributed randomized model selection for nonlinear identification and supervised machine learning

Today thousands of variables or features are often used in classification problems. It is therefore crucial to select the most relevant ones in order to obtain robust, reliable, and easily interpretable models, not to mention storage space and classification time issues. Feature Selection (FS) aims precisely at selecting features that allow a good discrimination among samples of different classes. Suitable criteria are required to remove irrelevant and redundant features. Similar issues are encountered in nonlinear identification. For example when identifying polynomial NAR[MA]X models from data one is faced with the task of selecting the most appropriate model structure to represent the underlying system. This task, denoted Model Structure Selection (MSS), is akin to FS. Both mentioned tasks configure combinatorial optimization problems aiming at selecting the combination of features or model terms that result in the most accurate classifier or model. The objective of this thesis is to investigate the possibility of employing some recent randomized techniques, originally developed in the nonlinear identification area, to FS problems, and to extend those techniques in both contexts, in order to deal with large-size problems. Indeed, the difficulty of these subset selection techniques increases rapidly with the size, given the exponential complexity of the underlying combinatorial problems. The first outcome of the research is a novel classification approach (denoted RFSC, for Randomized Feature Selectionand Classification), adapted from the nonlinear model identification framework, which jointly addresses the feature selection and classifier design tasks. The classifier is constructed as a polynomial expansion of the original features and a selection process is applied to find the relevant model terms. The selection method progressively refines a probability distribution defined on the model structure space, by extracting sample models from the current distribution and using the aggregate information obtained from the evaluation of the population of models to reinforce the probability of extracting the most important terms. The performance of the RFSC was found to be quite satisfactory on small/medium size problems. To address large size problems, a distributed scheme is here proposed, which employs a vertical partitioning on the features and operates the selection in parallel on different feature subsets. The method alternates the parallel selection phase with a partial information exchange among the different processors, which reinforces the probability that promising terms be selected. The proposed scheme is applicable to both nonlinear identification and FS problems and in both frameworks it resulted in significant improvements in performance and efficiency. Moreover, the method has a tendency to produce small models, easily amenable to interpretation. While capable of addressing much larger problems than the non-distributed approach developed previously, the distributed scheme was found to be ineffective when dealing with extra-large search spaces (as are encountered, e.g., with micro-arrays), due to computational issues associated with parameter estimation and classifier design. An alternative version of the distributed scheme was then developed to target micro-arrays in particular, which employs a non-parametric multivariate filter algorithm and population extraction using the distance correlation index (dCor) as a criterion. Finally, while analyzing the behavior of the RFSC, it was noticed that structurally different classifiers may result in equivalent performance due to the discrete nature of the 0 - 1 loss function in classification problems. The randomized characteristic of the RFSC was then exploited to generate ensembles of classifiers. In most cases the results demonstrate an improved accuracy when ensembles of classifiers are employed with respect to the 'single classifier' case. All proposed methods have been evaluated and compared to other well-known FS and MSS methods on standard benchmarks for classification/nonlinear identification problems. The results show the effectiveness of the proposed methods with respect to competitor methods both in terms of prediction accuracy and model complexity.

Al giorno d’oggi, i problemi di classificazione spesso richiedono l’uso di migliaia di variabili o caratteristiche. Quindi, è fondamentale selezionare quelle più rilevanti, al fine ottenere modelli robusti, affidabili e facilmente interpretabili. La Feature Selection (FS) mira proprio a selezionare le variabili che consentano una buona discriminazione tra campioni di classi diverse. Per rimuovere caratteristiche irrilevanti e ridondanti è necessario adottare criteri e metodi specifici. Problemi simili si riscontrano nell'identificazione non lineare. Ad esempio, quando si identificano modelli NAR[MA]X polinomiali dai dati, occorre selezionare la struttura del modello più appropriata per rappresentare il sistema sottostante. Questo compito, denominato Model Structure Selection (MSS), è simile alla FS. Entrambe le attività menzionate configurano problemi di ottimizzazione combinatoria, in cui si mira a selezionare la combinazione di caratteristiche o termini del modello che dia luogo poi al classificatore o al modello più accurato. L'obiettivo di questa tesi è di investigare la possibilità di utilizzare per problemi di FS delle tecniche randomizzate sviluppate di recente nel contesto dell’identificazione non lineare, e di estendere queste tecniche in entrambi i contesti, allo scopo di affrontare problemi di grandi dimensioni. Infatti, la difficoltà di tecniche di selezione di sottogruppi aumenta rapidamente con la dimensione, data la complessità esponenziale del problemi combinatori sottostanti. Il primo risultato della ricerca è un nuovo approccio di classificazione (denominato RFSC, Randomized Feature Selection and Classification), che affronta congiuntamente l’attività di selezione delle caratteristiche e il progetto del classificatore. Il classificatore è costruito come espansione polinomiale delle funzioni originali e il processo di selezione trova i termini rilevanti del modello. Il metodo di selezione perfeziona progressivamente una distribuzione di probabilità definita sullo spazio delle strutture dei modelli, estraendo modelli dalla distribuzione corrente e utilizzando le informazioni aggregate ottenute dalla valutazione della popolazione di modelli estratti per rafforzare la probabilità di estrarre i termini più importanti. Le prestazioni del RFSC sono risultate molto promettenti su problemi di piccola / media dimensione. Per problemi di grandi dimensioni, abbiamo proposto uno schema distribuito, che utilizza un partizionamento verticale delle caratteristiche, e opera la selezione in parallelo su diversi sottoinsiemi di caratteristiche. Il metodo prevede uno scambio parziale di informazioni tra i diversi processori, allo scopo di rafforzare la probabilità di selezionare termini promettenti. Lo schema proposta è applicabile sia all'identificazione non lineare che a problemi di FS. In entrambi i contesti applicativi ha prodotto dei miglioramenti significativi in termini di prestazioni ed efficienza rispetto ad altri metodi di letteratura. Inoltre, il metodo ha la tendenza a produrre modelli di piccole dimensione, facilmente interpretabili. Sebbene sia in grado di affrontare problemi molto più grandi rispetto all'approccio non distribuito sviluppato in precedenza, lo schema distribuito è risultato inefficace nel caso di spazi di ricerca estremamente grandi (come si trovano, ad esempio, nel caso dei micro-array), per il peso computazionale associati con la stima dei parametri e il progetto del classificatore. Per ovviare a questo problema, abbiamo sviluppato una versione alternativa dello schema distribuito mirato in particolare ai micro-array, che non richiede il calcolo del classificatore ma utilizza un criterio multivariato e non parametrico (l'indice di correlazione della distanza, o dCor) per valutare e confrontare sottoinsiemi di caratteristiche. Infine, l'analisi del comportamento dell'RFSC ha rivelato che classificatori strutturalmente diversi possono dare risultati equivalenti, a causa della natura discreta della funzione di costo 0-1 nei problemi di classificazione. Si è allora pensato di sfruttare la randomizzazione presente nell’algoritmo RFSC per generare classificatori diversi, per poi aggregare questi ultimi in un classificatore combinato. Nella maggior parte dei casi, i risultati dimostrano una maggiore precisione del classificatore combinato rispetto ai classificatori individuali. Tutti i metodi proposti sono stati valutati e confrontati con altri ben noti metodi di FS e MSS su benchmark standard per i problemi di classificazione e identificazione non lineare. I risultati mostrano l'efficacia dei metodi proposti rispetto ai metodi di letteratura in termini di accuratezza della previsione e di complessità del modello.