Non-negative binary matrix factorization for digit recognition with a D-wave quantum annealer

The present study attempts to assay the capabilities of matrix factorization algorithms in the field of handwritten digit recognition. It compares different algorithms categorized into two major groups: classical algorithms, two of which are based on iterative approximation and one on the application of the k-means algorithm, and QUBO-based ones, namely steepest descent, tabu search, simulated annealing, and quantum annealing. Each of the test subjects becomes the central part of a common pipeline, whose execution allows the collection of information regarding mathematical metrics, such as RSS and Frobenius error, and practical ones, i.e. the classification accuracy of a simple Convolutional Neural Network. The results show that classical algorithms outperform QUBO-based ones in each metric, even by multiple orders of magnitude in some cases, but also highlight the potential of the simulated annealing approach, which was the best performer of the second group. Something to be noted is that the best-performing methods in each set of experiments were implementations based on the algorithm presented in Zhang et al. (2007), which is a known staple of matrix factorization in different fields. The last of the classical algorithms, based on the implementation presented in Kumar et al. (2019), was the one that showed the best improvement with increasing factors’ rank, suggesting that it might outperform the other methods for higher values not represented in this study. Future investigations might focus on widening the experiment volume to verify the drawn conclusion, or on the application of scheduling techniques such as “reverse annealing” to increase the performance of quantum-based approaches, as done for instance in Golden and O’Malley (2020).

Lo scopo della presente tesi è quello di valutare l’applicazione di algoritmi di fattorizzazione matriciale nel campo del riconoscimento di cifre scritte a mano. In particolare, i metodi studiati appartengono a due macrocategorie: gli algoritmi classici, due metodi di approssimazione iterativa ed uno basato sull’applicazione dell’algoritmo k-means, e quelli basati sulla formulazione QUBO, nello specifico steepest descent, tabu search, simulated annealing e quantum annealing. Lo studio è stato realizzato mediante l’implementazione di una pipeline comune, all’interno della quale tutti gli algoritmi sono stati inseriti per la rilevazione di metriche matematiche, come RSS e Frobenius norm, e metriche relative all’applicazione pratica, ovvero la correttezza della classificazione delle immagini ricostruite da parte di una Convolutional Neural Network. I risultati mostrano migliori performance da parte dei metodi classici, capaci di superare gli algoritmi QUBO in tutte le metriche, ed in tutte le suite di test eseguite; tra gli appartenenti a quest’ultimo gruppo si è invece distinto l’algoritmo di simulated annealing. Interessante è la considerazione del fatto che i due algoritmi che si sono contesi la prima posizione in tutti gli esperimenti siano implementazioni basate sullo stesso algoritmo proposto in Zhang et al. (2007), noto in diversi casi di applicazione di fattorizzazione matriciale. L’ultimo degli algoritmi classici, basato sull’implementazione proposta in Kumar et al. (2019), ha mostrato i più grandi miglioramenti al crescere del rango dei fattori, suggerendo di poter superare in performance gli altri metodi per valori più elevati non considerati nel presente studio. Ricerche future potrebbero concentrarsi sull’espansione della suite di test, per verificare le conclusioni tratte, o sull’applicazione di metodi di scheduling come il “reverse annealing” per migliorare le performance degli algoritmi quantistici, come mostrato ad esempio in Golden and O’Malley (2020).