Feature Selection via Quantum Annealers for Ranking and Classification Tasks*Discussion PaperMaurizio Ferrari Dacrema1Fabio Moroni1Riccardo Nembrini01Nicola Ferro2Guglielmo Faggioli2Paolo Cremonesi1ContentWise
,
Milano
,
ItalyPolitecnico di Milano
,
Milano
,
ItalyUniversity of Padova
,
Padova
,
Italy2022
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. Our experimental analysis shows that the efectiveness obtained with quantum computing hardware is comparable to that of classical solvers, indicating that quantum computers are now reliable enough to tackle interesting problems.
1. Introduction
Information Retrieval (IR) is concerned with delivering relevant information to people, according
to their information needs, context, and profile, in the most efective and eficient way possible.
Central to this goal are ranking and classification , often exploited in conjunction. Machine
learning approaches have been widely investigated for this purpose. These methods however
sufer from the known feature selection problem. As the data becomes more rich and complex,
identifying the relevant features may require to evaluate an exponentially increasing number of
cases which rapidly becomes prohibitively resource intensive. The feature selection problem is
mitigated by deep learning and, more generally, neural approaches that have gained popularity
in recent years. Despite these methods being extremely versatile and generally able to provide
good overall efectiveness, it is known their performance is not always stable and may vary a lot
across topics, for example the performance may improve for half of the topics while degrade for
the other half [
2
]. A further disadvantage is that these neural approaches are very demanding
in terms of computing resources and require enormous amounts of data which leads to larger
and larger models that are not free from risks, as pointed out by Bender et al. [
3
]. In this paper
we take a step back and wonder ourselves if it is possible to make the feature selection problem
more “afordable” in order to make more appealing the use of “traditional” machine learning
approaches for ranking and classification. To this end, we investigate the feasibility of and
how to apply current generation quantum computing technologies to improve feature selection.
To the best of our knowledge very little work has been done to asses the efectiveness and
eficiency of such technologies to tackle feature selection problems, especially for both ranking
and classification. In this paper, we show how to formulate the feature selection problem as
a Quadratic Unconstrained Binary Optimization (QUBO) problem which can be solved using
Quantum Annealing (QA) and show that a quantum computer is able to more eficiently solve the
feature selection problem, for both ranking and classification, with an efectiveness comparable
to classical solvers. The results show that quantum computing approaches have become a viable
option for the feature selection problem in IR and that they are worthy of further investigation.
2. Methodology and Experimental Pipeline
Quadratic models for feature weighting and selection have been studied for several years [
4, 5
].
In this work, we focus only on feature selection, since it is a more dificult NP-hard problem.
In particular, we take into consideration three approaches that model the feature selection
problem with the Quadratic Unconstrained Binary Optimization (QUBO) formulation: Mutual
Information QUBO (MIQUBO) based on the mutual information maximization [
6, 7, 8
];
QUBOCorrelation that maximizes the Pearson correlation between selected features and the target
variable while minimizing the correlation between features [
9
]; and QUBO-Boosting that is
based on multiple single features Support Vector Classifier ( SVC) [
10
]1. The QUBO formulation
is rather flexible and such problems can be solved with several techniques. Among them, in
this work we consider the following: Simulated Annealing (SA) [
11
], Tabu Search (TS) [
12
],
and Steepest Descent (SD). Besides traditional approaches, QUBO problems are particularly
well suited to be solved via Quantum Annealing (QA). QA is a binary optimization technique
performed via a special-purpose physical device – a Quantum Annealer or Quantum Processing
Unit (QPU) – capable of escaping local minima thanks to a quantum mechanical phenomenon
called tunneling. In this work, the D-Wave Advantage QPU is used, which has 5600 qubit and
a topology called Pegasus, in which every qubit is connected to 15 others [
13
]. Because of
the sparse connections between qubits, a QUBO problem has to be first adapted to the QPU
topology via minor embedding [
14
]. The embedded problem is served to the QPU on the cloud
via APIs and low-energy solutions are sampled by repeating the QA process, which by default
has a duration of 20 . If a QUBO problem cannot fit on the QPU, a hybrid quantum-classical
approach can be used, to decompose the problem in smaller ones that can be solved directly on
the QPU. This can be done with the D-Wave Leap2 Hybrid cloud service.
1For more details on these QUBO formulations, we refer to the original work [
1
]
2D-Wave Leap - https://cloud.dwavesys.com/leap/
Experimental Pipeline The efectiveness of the QPU is assessed on two diferent tasks,
classification and ranking 3. Given the usually high number of features, feature selection is
important and largely used in classification, in order to identify the most useful subset of
features for the specific task. For the classification experiments, we considered 9 datasets
from OpenML [15], ranging from 34 to 5000 features. We report here results only for 4 of
them: spambase, nomao, isolet, and gisette. The algorithm used for the classification task
is Random Forest. Concerning the ranking task, to evaluate diferent feature selection strategies
in a traditional IR setting, we consider the Learning to Rank (LtR) task. Following previous
literature on LtR, we adopt three LETOR datasets (i.e., OHSUMED, MQ2007, and MQ2008) to assess
the performance of diferent feature selectors. We use LambdaMART [ 16] as ranking algorithm.
3. Results and Discussion
The results obtained by the QUBO solvers are compared and displayed in Table 1 (Classification
Task) and Table 2 (Ranking Task). To determine statistically significant diferences between
features selection strategies applied to the classification task, we employ the McNemar’s test
with significance level = 0.05 and Bonferroni correction following the procedure described
by Japkowicz and Shah [17], while, for the ranking task, we applied ANalysis Of VAriance
(ANOVA) as employed by Banks et al. [18]. Concerning the efectiveness of the solvers, the first
observation that can be made is that there is no single QUBO solver that is superior to the others,
rather, the solver that is able to achieve the best result is diferent depending on the dataset.
Across all experiments TS is able to reach the best result 11 times, SA and QPU 8 times, Hybrid
7 times and SD 6 times. This is likely due to the peculiarities of each dataset, task and, to some
extent, the stochastic nature of some solvers. Some diferences instead emerge by comparing
across tasks, in particular no feature selection approach is able to improve the efectiveness
on dataset MQ2008 and the Hybrid solver is slightly less efective when applied to the Ranking
task. The behavior of the various QUBO solvers remains instead consistent across the feature
3Source code available at: https://github.com/qcpolimi/SIGIR22_QuantumFeatureSelection.git
selection methods, although diferent QUBO heuristics result in diferent overall efectiveness.
For example, MIQUBO appears to produce better results compared to the others. Looking at the
QPU solver, its efectiveness is very close, if not almost identical, to that of the other solvers,
sometimes resulting in the best selection of features. In very few cases the solution obtained
with the QPU is worse compared to the other solvers, but within 5% of the best one. This result
indicates that the QPU is indeed a reliable solver that can be used to tackle real problems across
diferent datasets, heuristics and tasks. Note however that the largest problem that could be
solved directly on the QPU had 124 features. Although the QPU has more than 5000 qubits,
the QUBO matrix resulting from the feature selection problem is fully-connected and therefore
its structure is dificult to fit on the limited connectivity structure of the QPU, therefore the
problem size that can fit the hardware is greatly reduced. For larger problems it is still possible
to use the Hybrid QPU-Classical approach, which was used for datasets of up to 5000 features
but is able to tackle even larger problems. With respect to the computational time needed to
solve the QUBO problems with diferent solvers, some patterns can be denoted. In general, SD
is faster than QPU, SA and TS. It is also faster than Hybrid on datasets with only hundreds of
features, but it scales worse, thus Hybrid comes out as the fastest solver for bigger datasets. The
QPU is almost always faster than TS and SA, but slower than the latter for the MIQUBO model.
Finally, most of the time currently required to solve a fully-connected QUBO problem with a
QPU can be eliminated by ofering pre-built embeddings and by reducing the network delay
and queuing time required to access the quantum computer on the cloud.
Discussion and Future Works Overall, this work has shown that Quadratic Unconstrained
Binary Optimization (QUBO) and Quantum Annealing (QA) are viable options for improving
feature selection for both classification and ranking. QA is an emerging technology that has
now evolved to the point where it can be used to tackle real problems and is easily accessible for
researchers. There is indeed much room for improvement, which could lead to more competitive
results. It would be worth if we, as a community, undertake a systematic exploration of these
promising research directions, by developing a formulation suitable for applying quantum
computing approaches to other relevant tasks. It would be extremely valuable if IR large scale
evaluation campaigns take a lead and promote the organization of shared activities for exploring
the application of quantum computing to IR, NLP, and RecSys in a comparable and shared way.
ting problem, Quantum Inf. Process. 7 (2008) 193–209. URL: https://doi.org/10.1007/
s11128-008-0082-9. doi:10.1007/s11128-008-0082-9.
[15] J. Vanschoren, J. N. van Rijn, B. Bischl, L. Torgo, Openml: Networked science in machine
learning, SIGKDD Explorations 15 (2013) 49–60. URL: http://doi.acm.org/10.1145/2641190.
2641198. doi:10.1145/2641190.2641198.
[16] C. J. Burges, From ranknet to lambdarank to lambdamart: An overview, Learning 11 (2010)
81.
[17] N. Japkowicz, M. Shah, Evaluating learning algorithms: a classification perspective,
Cambridge University Press, 2011.
[18] D. Banks, P. Over, N. Zhang, Blind men and elephants: Six approaches to trec data (1998).