Quantum technologies are a reality today, and the future is bright regarding its capabilities for real-world applications. Feature selection is a crucial preprocessing step in Information Retrieval. By identifying the most informative subset of features, feature selection can improve the eficiency of learning to rank models. In this paper, we propose a novel approach to feature selection for Information Retrieval using quantum annealing. This promising optimization technique leverages the principles of quantum mechanics. We focus on the MQ2007 dataset, a widely used benchmark for learning to rank tasks. We also explore diferent formulations of the feature selection problem as quadratic unconstrained binary optimization (QUBO) problems, including mutual information, conditional mutual information, and correlation coeficients. Our quantum annealing-based approaches demonstrate their efectiveness in selecting informative features, outperforming simulated annealing, which achieves an nDCG@10 score of 0.4024. The best quantum annealing-based approach achieves a score of 0.443 using a hybrid solver with only ten features. We discuss the importance of the number of selected features in the performance of learning to rank models and the role of hybrid quantum-classical solvers in incorporating additional constraints and preferences into the feature selection process. Our work demonstrates the potential of using quantum annealing to tackle complex optimization problems. It paves the way for further exploration in this domain.
Information Retrieval (IR) systems are crucial in eficiently and efectively retrieving relevant information
from large-scale data. Among the various components of IR systems, learning-to-rank (LTR) models,
such as LambdaMART[
Feature selection is an essential preprocessing step in IR to identify the most relevant subset of
features for training LTR models [
Recent advancements in quantum computing have opened up new possibilities for solving optimization problems, including feature selection. Quantum annealing, in particular, has shown promise in eficiently exploring vast search spaces and finding optimal solutions [ 8]. By leveraging the principles of quantum mechanics, such as superposition and entanglement, quantum annealing can outperform classical optimization algorithms [9]. Wang et al. [10] have demonstrated the efectiveness of integrating machine learning algorithms with quantum annealing solvers for online fraud detection, showcasing the potential of quantum annealing in real-world applications.
In this work, we propose a novel approach to feature selection for IR using quantum annealing. Specifically, we focus on the MQ2007 dataset [ 11], a widely used benchmark for LTR tasks, and aim to select the most informative subset of features to improve the performance of a LambdaMART model. We explore diferent formulations of the feature selection problem as quantum annealing problems, including mutual information (MI), conditional mutual information (CMI), and correlation coeficients.
The main contributions of our work are as follows: We present a quantum annealing-based approach to feature selection for IR, demonstrating its efectiveness on the MQ2007 dataset. We compare diferent problem formulations (MI, CMI, and correlation coeficients) and analyze their impact on the feature selection process. We evaluate the performance of the LambdaMART model trained with the selected features using the normalized discounted cumulative gain (nDCG) metric[12]. We provide insights into the quantum annealing process through energy histograms and discuss the feasibility of the solutions found by the hybrid solver.
Feature selection is a fundamental process in machine learning that involves the identification of a subset of pertinent features from a larger set to improve model performance. Several authors have developed various approaches to address this problem, each with unique contributions and benefits. Evolutionary Quantum Feature Selection (EQFS) employs principles of quantum computing to enhance the eficiency of feature selection. EQFS employs the Quantum Circuit Evolution (QCE) algorithm, which uses shallow-depth circuits to generate sparse probability distributions. It enables the identification of optimal feature combinations with quadratic scaling in the number of features, thus overcoming the curse of dimensionality. This technique is particularly efective for high-dimensional datasets [ 13, 14].
We can classify the various traditional feature selection methods into three main categories: filter, wrapper, and embedded methods. Filter methods, such as correlation and mutual information, use general dependency measures between features and the output. Wrapper methods evaluate subsets of variables based on the quality of the final classification, ofering superior performance but at a higher computational cost. Embedded methods integrate feature selection into the training process of the classifier, with examples including decision trees and methods with L1 regularization. These traditional approaches are fundamental in various Machine Learning applications, balancing computational eficiency and accuracy [13]. Moreover, methods based on mutual information have been highly influential in multiple applications [15].
Another approach to quantum computing involves integrating machine learning algorithms with quantum annealing solvers. This approach is particularly productive in online fraud detection, where data processing in real-time or near-real-time is of paramount importance. The quantum-enhanced SVM has demonstrated notable enhancements in speed and accuracy for time-series datasets with highly imbalanced data. However, the accuracy improvements for non-time series data were relatively marginal. This approach demonstrates the potential of quantum machine learning (QML) applications in time-series data. It illustrates that the optimal strategy depends on the dataset type and the balance between speed, accuracy, and cost [16]. Moreover, authors have demonstrated that conditional mutual information is a practical approach to feature selection in incomplete data [17].
Genetic algorithms represent a type of randomized feature selection method that attempts to emulate the processes of natural evolution. These algorithms generate feature subsets randomly and iteratively improve them through operations such as crossover and mutation. Genetic algorithms can efectively locate optimal feature subsets, thereby avoiding the pitfall of local optima. This robustness renders them well-suited for complex feature selection tasks. The capacity to evade local optima confers a substantial advantage over other sequential search methodologies. Furthermore, incorporating randomness into these processes can enhance the eficiency of identifying optimal feature sets [ 18]. Moreover, integrating mutual information into genetic algorithms has been employed to improve feature selection [19].
The integration of classical machine learning techniques with quantum computing ofers the potential for significant advantages. For example, a hybrid approach that employs quantum evolutionary algorithms to optimize feature combinations. In contrast, classical algorithms that evaluate these combinations can efectively leverage the strengths of both paradigms. This approach aims to enhance the precision and eficacy of feature selection in a range of machine-learning applications. The capacity of quantum algorithms to address the computational complexity of large datasets is a valuable complement to the resilience of classical methods in model evaluation. This type of integration promises significant advancements in the practical application of quantum feature selection [ 13]. Combining mutual information with other criteria has been demonstrated to enhance feature selection in various domains [20].
In supervised feature selection, a recent approach combines sparse representation and mutual information to enhance the feature selection process. The method begins with sparse representation, which evaluates the importance of each feature in the overall data structure. Subsequently, mutual information is employed to reduce redundancy among the selected features. The experimental results demonstrate that this approach significantly enhances classification outcomes and can achieve superior feature selection results at lower dimensions. This method illustrates the significance of considering the global importance of features and redundancy reduction to achieve optimal results [21]. Moreover, using conditional mutual information and other innovative methodologies has yielded encouraging outcomes in feature selection [22].
In this section, we describe our methodology for feature selection using quantum annealing. We ifrst formulate the feature selection problem as a quantum annealing problem and then present the approaches we explored, including mutual information, conditional mutual information, and correlation coeficients. We also discuss the use of hybrid quantum-classical solvers and simulated annealing for comparison.
Our experiments use the MQ2007 dataset, a widely used benchmark dataset for learning to rank tasks in Information Retrieval. The MQ2007 dataset consists of 1,692 queries and 69,623 documents, with each query-document pair represented by a 46-dimensional feature vector. The QuantumCLEF lab organizers provide a training set, which we use for feature selection. The organizers are the ones responsible for training and evaluating the learning to rank model using the selected features [23, 24].
Let = (x, ) = 1 be a dataset consisting of instances, where x ∈ R is a -dimensional feature vector and ∈ R is the corresponding target value. The goal of feature selection is to identify a subset of features ⊆ 1, 2, . . . , that maximizes the relevance to the target variable while minimizing the redundancy among the selected features.
We formulate the feature selection problem as a quadratic unconstrained binary optimization (QUBO) problem, which can be solved using quantum annealing. The QUBO formulation is given by: min q⊤Qq, q∈0,1 where q is a binary vector representing the selection of features, and Q is a × matrix capturing the interactions between features. The diagonal elements of Q represent the relevance of each feature to the target variable. In contrast, the of-diagonal elements represent the redundancy between pairs of features.
Mutual information (MI) measures the dependence between two random variables. In the context of feature selection, we use MI to quantify the relevance of each feature to the target variable. We define the MI between a feature and the target variable as: (1) CMI(; | ) = ∑︁
∑︁ ∑︁ (, , ) log ∈ ∈ ∈
(, |) (|)( |) where (, , ) is the joint probability distribution of , , and , and (|) and ( |) are the conditional probability distributions of and given , respectively.
To incorporate CMI into the feature selection problem, we update the Q matrix as follows: Q = {︃− MI(; )
if = , − CMI(; | ) if ̸= .
The negative sign in the of-diagonal elements ensures that the optimization problem seeks to minimize the redundancy between the selected features given the target variable.
Conditional mutual information (CMI) extends the concept of MI by considering the redundancy between pairs of features given the target variable. The CMI between two features and given the target variable is defined as:
Correlation coeficients measure the linear relationship between two variables. In the context of feature selection, we use the Pearson correlation coeficient to quantify the relevance of each feature to the target variable and the redundancy between pairs of features. The Pearson correlation coeficient between two variables and is defined as:
MI(; ) = ∑︁ ∑︁ (, ) log ∈ ∈ (, ) ()() , where (, ) is the joint probability distribution of and , and () and () are the marginal probability distributions of and , respectively.
To formulate the feature selection problem using MI, we construct the Q matrix as follows: Q = {︃− MI(; ) if = ,
0 otherwise.
The negative sign in the diagonal elements ensures that the optimization problem seeks to maximize the MI between the selected features and the target variable.
(, ) = cov(, )
, Q = {︃−| (, )|
if = , −| (, )| if ̸= .
where cov(, ) is the covariance between and , and and are the standard deviations of and , respectively.
To formulate the feature selection problem using correlation coeficients, we construct the Q matrix as follows:
The absolute values of the correlation coeficients capture both positive and negative relationships. The negative sign ensures that the optimization problem maximizes relevance and reduces redundancy. (2) (3) (4) (5) (6) (7)
Quantum annealing is an optimization technique that leverages the principles of quantum mechanics to solve complex optimization problems. It is particularly well-suited for solving QUBO problems, as it eficiently explores the vast solution space and finds the global minimum. To solve the feature selection problem using quantum annealing, we follow these steps: Algorithm 1 Quantum Annealing for Feature Selection 1: Construct the Q matrix based on the chosen approach (MI, CMI, or correlation coeficients). 2: Convert the Q matrix to a QUBO problem. 3: Submit the QUBO problem to the quantum annealer. 4: Retrieve the solution from the quantum annealer. 5: Interpret the solution as the selected subset of features.
Once the quantum annealer has completed its task, it returns a binary vector q. This vector is more than just a series of 1s, and 0s-it represents the selected subset of features. The indices of the non-zero elements in q are the features that have been chosen, providing a clear output of the quantum annealing process.
In addition to using pure quantum annealing, we explore using hybrid quantum-classical solvers for feature selection. Hybrid solvers combine the strengths of quantum and classical computation by leveraging quantum annealing to explore the solution space and classical optimization techniques for local refinement.
We specifically employ the LeapHybridCQMSampler, a hybrid solver provided by D-Wave Systems. This solver combines quantum annealing with a classical-constrained quadratic model (CQM) solver. The hybrid solver allows us to incorporate additional constraints into the feature selection problem, such as the desired number of selected features.
Our approach involves formulating the feature selection problem as a CQM and then submitting it to the LeapHybridCQMSampler. This hybrid solver, upon receiving our problem, diligently explores the solution space and returns a set of feasible solutions. From this set, we select the best solution based on the objective function value, ensuring the highest quality of our results.
For comparison purposes, we also implement feature selection using simulated annealing, a classical optimization technique inspired by the annealing process in metallurgy. Simulated annealing aims to ifnd the global minimum of an objective function by gradually decreasing the system’s temperature and allowing occasional uphill moves to escape local minima.
We use the SimulatedAnnealingSampler provided by the D-Wave Ocean SDK to solve the feature selection problem using simulated annealing. The simulated annealing algorithm follows a similar procedure to quantum annealing. Still, instead of leveraging quantum efects, it relies on a probabilistic acceptance criterion to explore the solution space.
By comparing the results obtained using quantum annealing, hybrid quantum-classical solvers, and simulated annealing, we can assess the relative efectiveness of these approaches for feature selection in Information Retrieval.
The organizers of the QuantumCLEF lab, in a collaborative efort, have evaluated the efectiveness of our quantum annealing-based feature selection approaches. We have submitted the selected features from the training set to the organizers, who have then used them to train a LambdaMART model on their internal training set. LambdaMART, a state-of-the-art learning-to-rank algorithm, combines the MART (Multiple Additive Regression Trees) algorithm with a lambda gradient optimization framework.
The organizers evaluate the performance of the LambdaMART model using their internal validation and test sets, which are inaccessible to us. They measure the performance using the normalized discounted cumulative gain (nDCG) metric, commonly used in Information Retrieval, to evaluate the quality of ranked results. We defined the nDCG@k metric as:
DCG@k nDCG@k = , (8)
IDCG@k where DCG@k is the discounted cumulative gain at position , and IDCG@k is the ideal discounted cumulative gain at position , which represents the maximum possible DCG@k value.
The evaluation results provided by the organizers, as explored in section 4, will ofer valuable insights into the efectiveness of our quantum annealing-based feature selection methods. These insights have the potential to significantly improve the performance of learning to rank models in Information Retrieval tasks, underscoring the relevance and potential of our research.
This section presents and discusses the experimental results of the diferent feature selection methods for the MQ2007 dataset. Figure 1 shows a pairplot comparing the nDCG@10 scores of the four implemented methods: Quantum Annealing Mutual Information (Quantum-MI), Hybrid Annealing Mutual Information (Hybrid-MI), Hybrid Annealing Correlation (Hybrid-Correlation), and Simulated Annealing Mutual Information (SA-MI). The pairplot visually represents the score distributions and relationships between the methods.
I1.0 M m tu0.5 n a u Q0.0 1.0 I M ird0.5 b y H 0.0 ion1.0 t a l e r ro0.5 C id r yb0.0 H1.0 I -M0.5 A S 0.0 0.0
0.5 1.0 Quantum-MI 0.0
0.5 Hybrid-MI 1.0 0.0 0.5 1.0 Hybrid-Correlation 0.0 0.5 1.0
SA-MI
Figure 2 presents a boxplot comparing the nDCG@10 scores of the four methods. The boxplot shows each method’s median, quartiles, and outliers of the score distributions. The boxplot indicates that Hybrid-Correlation and SA-MI have slightly higher median scores than Quantum-MI and Hybrid-MI. However, there is considerable overlap in the score distributions.
To summarize the performance, we calculated the average nDCG@10 scores for each method based on the provided data files. The average scores are as follows: 0.2 0.0
The Hybrid Correlation method achieved the highest average nDCG@10 score (0.4430), followed closely by the SA-MI method (0.4417). The quantum-MI (0.4299) and hybrid-MI (0.4195) methods had slightly lower average scores. These results suggest that the hybrid correlation method, which combines quantum techniques with classical correlation-based feature selection, was the most efective in selecting informative features for the MQ2007 dataset.
The oficial results shared by the organizers provide additional insights into the performance of the methods: QTB1A_MQ2007_QA_qtb_NT1 QTB1A_MQ2007_QA_qtb_NT2 QTB1A_MQ2007_QA_qtb_NT3 QTB1A_MQ2007_SA_qtb_NT1
The oficial results confirm the average scores obtained from our calculations and provide additional details. The Hybrid-Correlation method (QTB1A_MQ2007_QA_qtb_NT3) achieved the highest score of 0.4434, followed by the Quantum-MI method (QTB1A_MQ2007_QA_qtb_NT1) with a score of 0.4299. The SA-MI method (QTB1A_MQ2007_SA_qtb_NT1) scored 0.4024, slightly lower than our calculated average (0.4417). The Hybrid-MI method (QTB1A_MQ2007_QA_qtb_NT2) had the lowest score of 0.4195 among the four methods. It is worth noting that the Quantum-MI method (QTB1A_MQ2007_QA_qtb_NT1) used 13 features, while the other techniques used ten features. Despite using more features, the Quantum-MI method did not outperform the Hybrid-Correlation method, which used only ten features.
We conducted a one-way ANOVA test on the nDCG@10 scores to validate the statistical significance. The test yielded a p-value of 0.7659, indicating that there are no significant diferences between the methods at a significance level of 0.05. This suggests that despite the diferences in average scores, the methods’ overall performance is statistically comparable.
Despite the lack of significant diferences overall, we performed post-hoc pairwise comparisons using Tukey’s HSD test to explore the diferences further. We summarized Tukey’s HSD test results in Table 1. The pairwise comparisons did not reveal any statistically significant diferences between the methods, as indicated by the high p-values (> 0.05) and the confidence intervals that include zero.
It is important to note that our feature selection methods used only ten features, except for the Quantum-MI method, which used 13 features. Despite using fewer features, our hybrid correlation and SA-MI methods achieved competitive performance compared to other teams with 15 or more features. Our methods efectively selected a compact set of informative features while maintaining good performance. The ability to achieve comparable results with fewer features is advantageous in terms of computational eficiency and model simplicity.
The oficial results and our analysis indicate that the quantum-related methods, particularly HybridCorrelation (QTB1A_MQ2007_QA_qtb_NT3) and Quantum-MI (QTB1A_MQ2007_QA_qtb_NT1), achieved competitive performance compared to the fully simulated SA-MI method (QTB1A_MQ2007_SA_qtb_NT1). The Hybrid-Correlation method achieved the highest score of 0.4434, outperforming the SA-MI method, which scored 0.4024. The Quantum-MI method also performed well, with a score of 0.4299, despite using more features (13) than the other methods. The quantum-based approach in Quantum-MI efectively captured relevant information from the additional features.
The superior performance of the hybrid correlation method underscores the potential of combining quantum techniques with classical correlation-based feature selection. It ignites excitement about the future of feature selection tasks. By harnessing the strengths of both approaches, the hybrid correlation was able to identify informative features more efectively than the purely classical SA-MI method. The competitive performance of quantum-related methods, even without statistical significance in overall comparisons, hints at their immense potential in feature selection tasks. The theoretical foundation of quantum-based approaches ofers a more nuanced understanding of data correlations and dependencies, a prospect that could significantly enhance their efectiveness in identifying informative features.
However, it is essential to consider the variability in the nDCG@10 scores across diferent queries, as evident from the pairplot and boxplot. Some queries had scores of 0 for all methods, indicating that none of the selected features were relevant for those specific queries. This variability suggests that the performance of the feature selection methods may depend on the characteristics of individual queries. Future work could explore incorporating query-specific adaptations or using a more diverse set of features to capture the varying information needs of diferent queries.
Our feature selection methods used only ten features, except for the Quantum-MI method, which used 13 features. Despite using a smaller feature set, our hybrid correlation and SA-MI methods achieved competitive performance compared to other teams with 15 or more features. It demonstrates the efectiveness of our processes in selecting informative features while maintaining a compact representation.
The decision to use fewer features was not arbitrary but a strategic move that ofered several key advantages. It significantly reduces the computational complexity of the learning algorithms, as there are fewer dimensions to process. This, in turn, helps to mitigate the risk of overfitting, as the models are less likely to capture noise or irrelevant patterns when trained on a smaller set of relevant features. Moreover, a compact feature set enhances the interpretability of the models, as it hones in on the most important aspects of the data, enlightening us to the true essence of the information.
The fact that our methods achieved comparable performance to teams using more features suggests that our feature selection approaches were able to identify the most discriminative and informative features for the MQ2007 dataset. It highlights the potential of our methods to extract meaningful information from the data while maintaining eficiency and simplicity.
In this paper, we presented a novel approach to feature selection for Information Retrieval using quantum annealing. Our focus was on the MQ2007 dataset, where we explored various formulations of the feature selection problem as quantum annealing problems. Our approach demonstrated potential in selecting informative features, which contributed to the performance of the LambdaMART learning-torank model. When compared with classical feature selection techniques, our quantum annealing-based approaches showed competitive results. The evaluation conducted by the QuantumCLEF lab organizers indicated that the features selected by our approach contributed to improvements in ranking quality, although the diferences were not statistically significant. Our work provides insights into the application of quantum annealing for addressing optimization problems in Information Retrieval. However, we acknowledge that there are limitations and challenges that need to be addressed in future work. Future research directions include: 1. Scaling quantum annealing-based feature selection to larger datasets and higher-dimensional feature spaces. 2. Integrating quantum annealing-based feature selection with other components of the Information
Retrieval pipeline. 3. Adapting the approach to other Information Retrieval tasks, such as document clustering and recommendation systems. 4. Exploring the potential of newer generations of quantum hardware and algorithms for Information
Retrieval applications.
In conclusion, our work demonstrates the feasibility of using quantum annealing for feature selection in Information Retrieval. While the current results do not show significant improvements over classical methods, they suggest that the intersection of quantum computing and Information Retrieval may hold promise for future advancements in the field. Further research is needed to fully understand and leverage the potential of quantum annealing in improving the eficiency and efectiveness of information access.