A survey on feature selection methods for classification solved with quantum annealing

Modern Machine Learning problems are getting more and more complex: their size is increasing and the challenges to face are harder to overcome. The growth of the datasets implies an huge increase of the computational time to execute algorithms and train learners. Solving Feature Selection problem reduces the amount of data used to learn a process, but it is computationally expensive. Thus, finding more efficient strategies and approaches would lead to a significant impact. Feature Selection is a phase of a Machine Learning pipeline that has the goal to reduce the number of features of a dataset, without loosing generality and accuracy of the learner used. Solving efficiently this problem is crucial: we may be able to significantly reduce the number of features of a dataset, which implies a speed up of the training phase of the learner. Despite this, the accuracy obtained should be equal or better in both validation and test steps of the pipeline, thus improving its generalization ability. Furthermore, in a research scenario, cutting unnecessary or less relevant features gives a deeper insight about the dynamics of the process to learn. However, solving a feature selection problem can be computationally very expensive. So, it needs some speed-ups in terms of resources and new technologies. This thesis focuses on the filter category of Feature Selection methods for supervised learning classification problems. These techniques exploit statistical measurements (e.g. mutual information or correlation) between the features themselves and with the target variable(s) in order to determine their relevance for the problem. The goal of this work is to evaluate a graph based mutual information approach, called Graph Mutual Information QUBO, Quantum-Boosting and Quantum-Correlation methods, which can all be executed on Quantum Annealer devices. The evaluation is achieved through a series of experiments, which results are used to compare the quantum-based algorithms to classical (non-Quantum) ones from the point of view of accuracy, efficiency, and execution timings.

I problemi moderni di Machine Learning stanno diventando sempre più complessi: la loro dimensionalità continua a crescere a le sfide da affrontare sono sempre più difficili. Questa crescita riguarda i set di dati impiegati, la quale implica un grande aumento del tempo computazionale necessario per eseguire gli algoritmi e poter ”istruire” i regressori o classificatori. Una soluzione a questo problema è una efficiente esecuzione della fase di Feature Selection, letteralmente selezione delle caratteristiche. Feature Selection è una delle fasi di un algoritmo di Machine Learning che ha l’obiettivo di ridurre il numero di features (appunto, caratteristiche), senza però influenzare in maniera negativa la precisione e accuratezza del regressore o classificatore (learner), impiegato per imparare le dinamiche di un processo. Risolvere in maniera efficiente questo problema risulta estremamente importante, poichè diminuendo potenzialmente gran parte delle feature di un set di dati si ottiene una riduzione signicativa della complessità di un problema, nonchè del tempo necessario per l’addestramento del learner. Nonostante questa simplificazione, le performance dei nuovi modelli possono rimanere uguali oppure anche migliorare sia negli step di validazione che di test. Inoltre, soprattutto in analisi e problemi di ricerca, riuscire ad eliminare feature che risultano non necessarie e meno rilevanti può contribuire ad una maggiore comprensione delle dinamiche del processo da studiare. Tuttavia, risolvere il problema di Feature Selection può essere molto dispendioso dal punto di vista computazionale, con tempi di esecuzione che non rendono utile l’impiego e la soluzione di tale fase. Per questo motivo, è necessario migliorare le tecniche impiegate, nonchè le risorse e sfruttare nuove tecnologie. Questa tesi si concentra sui metodi di selezione di feature di tipo ”filtro”, chiamati filter methods, e su problemi di classificazione, con a disposizione anche la variabile target da imparare (supervised classification problems). I filter methods sfruttano delle grandezze statistiche (come mutual information e correlazione) tra le features stesse e con la variabile target, in modo tale da determinare la loro rilevanza per il problema. L’obiettivo di questa tesi è quello di testare e analizzare un metodo basato sui grafi e la mutual information, chiamato Graph Mutual Information QUBO, e di valutare i metodi Quantum-Boosting e Quantum-Correlation, i quali possono essere tutti eseguiti con un Quantum Annealer. Infine, confronteremo questi algoritmi con quelli classici (di tipo non-Quantum) dal punto di vista dell’accuratezza, efficienza e tempi di esecuzione.