Towards Feature Selection for Ranking and Classification Exploiting Quantum Annealers

Abstract

Feature selection is a common step in many ranking, classification, or prediction tasks and serves many purposes. By removing redundant or noisy features, the accuracy of ranking or classification can be improved and the computational cost of the subsequent learning steps can be reduced. However, feature selection can be itself a computationally expensive process. While for decades confined to theoretical algorithmic papers, quantum computing is now becoming a viable tool to tackle realistic problems, in particular special-purpose solvers based on the Quantum Annealing paradigm. This paper aims to explore the feasibility of using currently available quantum computing architectures to solve some quadratic feature selection algorithms for both ranking and classification. The experimental analysis includes 15 state-of-the-art datasets. The effectiveness obtained with quantum computing hardware is comparable to that of classical solvers, indicating that quantum computers are now reliable enough to tackle interesting problems. In terms of scalability, current generation quantum computers are able to provide a limited speedup over certain classical algorithms and hybrid quantum-classical strategies show lower computational cost for problems of more than a thousand features.

arXiv commentSource code is available on Github https://github.com/qcpolimi/SIGIR22_QuantumFeatureSelection.git

References in corpus (9)

• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• OpenML: networked science in machine learning
• Quantum Boltzmann Machine
• Introducing LETOR 4.0 Datasets
• Support vector machines on the D-Wave quantum annealer
• Application of Quantum Annealing to Training of Deep Neural Networks
• Feature Selection for Recommender Systems with Quantum Computing
• Reverse Annealing for Nonnegative/Binary Matrix Factorization

Cited by in corpus (6)

• Quantum computing for finance
• Feature Selection for Classification with QAOA
• Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection
• Nonnegative/Binary Matrix Factorization for Image Classification using Quantum Annealing
• Analyzing the Effectiveness of Quantum Annealing with Meta-Learning
• Minor Embedding for Quantum Annealing with Reinforcement Learning