Using Quantum Computers to solve problems in Recommender Systems that classical computers cannot address is a worthwhile research topic. In this paper, we use Quantum Annealers to address the feature selection problem in recommendation algorithms. This feature selection problem is a Quadratic Unconstrained Binary Optimization (QUBO) problem. By incorporating Counterfactual Analysis, we significantly improve the performance of the item-based KNN recommendation algorithm compared to using pure Mutual Information. Extensive experiments have demonstrated that the use of Counterfactual Analysis holds great promise for addressing such problems.
Collaborative filtering technology [1,2], which predicts potential user-item interactions based on the patterns of user behavior and item characteristics, is widely applied in recommendation algorithms, Some well-known techniques in this field include matrix factorization methods [3], neighborhood-based methods [4], deep learning approaches [5,6], graph-based techniques [7,8], factorization machines [9], hybrid methods [10], Bayesian methods [11], and large language models (LLMs) [12]. However, collaborative filtering technology [1] heavily relies on the quality of data. For instance, using user profiles, item features, reviews, images, and other information can significantly improve the performance of recommendation algorithms, but in some cases, it can also decrease their performance. Therefore, it's critical to distinguish what information are useful for recommendations so as to help the the construction of efficient systems and reduction of energy consumption [13,14,15,16]. Quantum computers, with its use of qubits and quantum effects like superposition, entanglement, and quantum tunneling, is an effective tool for identifying useful information from redundant data [17]. It significantly enhances the processing speed of search problems and large integer factorization [18]. Therefore, in this paper, we aim to find useful features for recommendations by leveraging quantum computing techniques. Our goal is to improve the efficiency and accuracy of recommendation systems by identifying and utilizing relevant data, thereby reducing computational requirements and energy consumption [18,19,20].
In QuantumCLEF 2024, we focus on Task 1B, where 150 and 500 features are provided for each item, respectively [21,22]. We will analyze these features to extract the most relevant ones for recommender systems. The task requires participants to use Quantum Annealing and Simulated Annealing to select appropriate features from the given data for an Item-Based KNN recommendation algorithm (Item-KNN). The organizers provided an example of feature selection by using Mutual Information [18]. However, our preliminary experiments showed that using only Mutual Information for feature selection resulted in limited improvement in the performance of Item-KNN compared to using all features without any selection. This is because Mutual Information only reflects the mutual relationship between two variables and is not associated with the final goal of the recommendation algorithm. Therefore, to achieve better performance, we propose taking the impact of features on recommendation quality into consideration when performing feature selection.
One approach to achieve this is through Counterfactual Analysis [23], which is a causal research tool to examine the impact of a factor on the final result by hypothesizing the absence or alteration of that factor. This approach mainly considers three aspects: Which factors need to be evaluated? What metrics are used to assess the impact of these factors on the model's outcomes? And what models are used to derive the values of these metrics? In this work, due to the limited time for this task, we aim to measure and explore the impact of item features by Counterfactually Analyzing their effect on nDCG [24] performance of recommendation lists and we chose the KNN-based recommendation algorithm, a commonly used method in collaborative filtering, to perform these measurements. Specifically, we used Item-KNN to derive the change in nDCG values after removing a specific item feature. Since Mutual Information can reflect the relationship between two features, which may positively affects the final results, we did not discard it. Instead, we integrated the results of Counterfactual Analysis into Mutual Information using a temperature coefficient, which is used to control the influence of Counterfactual Analysis on the final results. Given the current limitations on the number of qubits in Quantum Computers, directly performing Quantum Annealing on 500 variables remains a challenging task. Therefore, in this task, we first partitioned the 500 features into subsets manageable by the Quantum Computer, and then combined the results.
The paper is organized as follows: Section 2 introduces related works; Section 3 describes the QUBO formulation, how Mutual Information is applied to QUBO for feature selection, and our proposed method of using Counterfactual Analysis for feature selection in QUBO; Section 4 explains our experimental setup and experimental result; Section 5 discusses our main findings; finally, Section 6 draws some conclusions and outlooks for future work.
In recent years, the rapid development of Quantum Computers has demonstrated their tremendous potential in solving problems that Classical Computer cannot address, such as NP and NP-hard problems [25]. Based on their functionality and application scenarios, Quantum Computers can be categorized into Universal Quantum Computers, Quantum Annealers, Quantum Machine Learning Accelerators, and others [26]. Recent studies have utilized Quantum Annealers for feature selection to enhance the performance of recommendation systems or retrieval systems [27,28,18]. Nembrini et al. [27] attempted to apply Quantum Computers to recommendation systems by using Quantum Annealing to solve a hybrid feature selection approach. Their work demonstrates that current Quantum Computers are already capable of addressing real-world recommendation system problems. Nikitin et.al. [28] reproduced Nembrini's work and employed Tensor Train-based Optimization (TTOpt) as an optimizer for the cold start problem in recommendation systems. MIQUBO [18] discussed the problem of feature selection using Quantum Computers and formalizes it as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It demonstrates the potential of Quantum Computers to solve ranking and classification problems more efficiently.
Existing deep learning models have complex decision-making processes that are difficult for people to understand, often functioning as black-box models, Counterfactual Analysis is a highly effective method for helping people understand these complex models and robust them [29]. For example, CF 2 [30] used Counterfactual Analysis to explore the explanations of Graph Neural Networks. In recommender systems, Counterfactual Analysis is primarily used for explainability and to combat data sparsity. ACCENT [31] was the first to apply Counterfactual Analysis to neural network-based recommendation algorithms. CountER [32] utilizes Counterfactual Analysis to construct a low-complexity, high-strength model for explaining recommendation systems. It also highlights that using Counterfactual Analysis contributes to the interpretability and evaluation of recommendation systems. Zhang et al [33] designed a CauseRec framework that utilizes Counterfactual to enhance representations in the data distribution, aiming to mitigate data sparsity.
In summary, Counterfactual Analysis can help people understand complex deep learning decision systems and has the potential to analyze how various factors interact in recommendation systems. Given the current advancements in Quantum Computers, utilizing Counterfactual Analysis combined with the ability of Quantum Computers to handle NP problems presents a promising direction.
In this work, we follow the approach described in [18], which utilizes Quantum Annealing for feature selection. To apply these methods, the feature selection problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO formulation can be used to solve certain NP and NP-hard optimization problems and is defined as follows [18]:
where π₯ is a binary vector of length π, with each element of the vector being either 0 or 1. π is a symmetric matrix, where each element represents the relationship between the elements of π₯. π denotes the number of features to be selected. In other words, the elements of vector π₯ indicate whether the corresponding features are selected, and the elements in π influence the search direction of the function, determining feature selection.
Following [18], Mutual Information QUBO (MIQUBO) is a quadratic feature selection model based on Mutual Information. MIQUBO aims to maximize the Mutual Information, which measures the dependency between two variables, and the Conditional Mutual Information, which measures the dependency between two variables given a target variable, of the selected features. In this context, the matrix π in Equation 1 is defined as:
where MI(π π ; π¦) is the Mutual Information between feature π π and target feature π¦, and CMI(π π ; π¦ | π π ) is the Conditional Mutual Information between feature π π and target feature π¦ given feature π π . Since QUBO formulation is used to find the minimum state, a negative sign is required before MI and CMI.
To control the number of selected features, a penalty term is added to Equation 1, which is then transformed to:
This formula will be minimized when selecting π features, this also following the descriptions in [18].
To better identify features directly associated with recommendation performance, we integrate a widely used recommendation ranking metric into Mutual Information through Counterfactual Analysis.
Counterfactual Analysis [23] is usually used to examine the causal relationship between conditions, decisions, and outcomes by hypothesizing how the results of observed events would change if the conditions and decisions were altered. In the field of Recommender System, Counterfactual Analysis is often used for the interpretability of recommendation models, helping researchers enhance algorithm performance [32,33]. Inspired by existing works [32,33], the impact of item features can be explored by excluding the corresponding feature and analyzing the difference in recommendation performance between the recommendation lists generated by the model with and without the corresponding feature.
In this work, we use the widely used Item-KNN recommendation algorithm, termed as model πΊ, and employ the recommendation performance metric Normalized Discounted Cumulative Gain (nDCG) [24] for Counterfactual Analysis. nDCG is defined as:
where πΈ π represents the change in the nDCG result of the recommendation model πΊ after removing the feature π π . nDCG πΊ(F) represents the nDCG@10 value obtained by the πΊ using all item features set πΉ , while nDCG πΊ(Fβπ π ) represents the nDCG@10 value obtained by the πΊ using features set which is set πΉ removing feature π. It is important to note that πΈ π ultimately reflects the impact of feature π on the result. Since the final outcome is influenced by the interactions between all features, simply removing features with positive πΈ π values does not yield the optimal feature selection solution.
When πΈ π β₯ 0, it indicates that the algorithm's performance decreases after removing the feature π. The extent of this decrease reflects the positive impact of this feature on the algorithm. Conversely, an increase in the value reflects the negative impact of this feature on the algorithm. We hypothesize that if the selected set of features is π ππ‘(πΉ * ), the maximization the sum of πΈ π (π β π ππ‘(πΉ * )), the maximization the performance improvement of the baseline algorithm. Since the QUBO problem is a minimization optimization problem, we redefine π as follows:
where π is a coefficient used to control the influence of πΈ on the search results. The larger the value of π, the greater the influence of πΈ on the final results. The overall process of the above algorithm, which we refer to as Counterfactual Analysis QUBO (CAQUBO), is as follows in Algorithm 1.
Although Quantum Computers are developing rapidly, the limitation in the number of qubits restricts them to handling only a limited number of feature selection problems. For selecting from 500 features, we partition them into several subsets and use Quantum Annealing (QA) or Simulated Annealing (SA) to perform feature selection on these subsets individually, then combine the results. First, partition the 500 features into π subsets by order,
where π π is the π-th subset of features, and π is the number of subsets.
Then, use Quantum Annealing (QA) or Simulated Annealing (SA) to perform feature selection on each subset, and combine the results:
where π Λis the final selected features set, represents each partitioned subset of features, and QA/SA (π_π) represents the selected features from subset π π using QA and SA. The final feature set is obtained by merging the selected features from all subsets.
Algorithm 1 Counterfactual Analysis QUBO
Datasets: In this work, two tasks are undertaken: the first involves selecting appropriate features from a set of 150 item features for training πΊ, and the second involves selecting features from a set of 500 item features. Three data sets are provided for these tasks: 150_ICM, 500_ICM, and URM. The 150_ICM and 500_ICM contain item features, while the URM includes interaction data between 1,890 users and 18,022 interacted items. Experimental parameter setting: We used a self-implemented Item-KNN recommendation model based on the problem statement to calculate πΈ. The interaction data was split into training and test sets in an 80:20 ratio. It is worth noting that calculating πΈ is very time-consuming, so we only used a subset of items for the calculations. In the use of Quantum Annealing (QA) and Simulated Annealing(SA), the coefficient π significantly affects the features selected by QA and SA. Due to the limited usage time of the Quantum Annealer (QA), it is necessary to use Simulated Annealing (SA) to explore the effectiveness of the selected features under different parameters π and π before using QA. In preliminary experiment, we attempt [π: 0, 1e1, 1e3, 1e5, 1e7], [k: 50, 100, 130, 140, 145] in Feature 150 and [π: 0, 1e1, 1e3, 1e5, 1e7], [k: 300, 350, 400, 450, 470] in Feature 500. For the selection of 500 features, n (is mentioned in Section 3.3) is set to 5. The preliminary experiment results can be found in Table 1. Repeated Calculations: Due to the heuristic nature of Simulated Annealing (SA) and Quantum Annealing (QA), the final results may vary even with fixed parameters. To mitigate this effect, we perform multiple iterations of QA and SA under the same parameters and select the final feature set via voting. For example, we repeated the experiment five times. π π was not included in πΉ * in any of the five experiments, while π π was included in πΉ * in four out of the five experiments. Therefore, the final submitted feature set πΉ * does not include π π but includes π π .
Table 1 describes the performance in nDCG@10 of πΊ using features selected by QA and SA under different parameters π and π. When π = 0, QA and SA select features based solely on Mutual Information (MI) and Conditional Mutual Information (CMI). Across different values of parameter π, the performance of selected features in πΊ rarely surpasses the performance in Counterfactual Analysis QUBO. As the parameter π increases, the performance of the features selected by QA and SA in the item-KNN shows significant improvement compared to using all features. The effectiveness of feature selection shows no significant improvement when π > 1π5 . This may be because as the value of π increases, the impact of MI and CMI on feature selection diminishes, causing QA and SA to rely entirely on πΈ for feature selection. Table 2 reflects the same situation: feature selection relying solely on MI and CMI does not surpass the performance in Counterfactual Analysis QUBO. After incorporating the counterfactual analysis-derived πΈ into π, the features selected by QA and SA show a significant performance improvement in item-KNN compared to using all features. An unusual observation is that, under the same parameters, the features selected by QA generally do not perform as well as those selected by SA in item-KNN, and sometimes do not even surpass the performance of using all features. During the experiments, we noticed that this is due to QA often returning results before finding the optimal solution.
In this paper, we present the explorations conducted by our team and the details of our final submission for the QuantumCLEF 2024 activities. We used Counterfactual Analysis of individual item features to select appropriate features for item-KNN using Quantum Annealing. Our preliminary experiments and the results returned by QuantumCLEF 2024 demonstrated that our use of Counterfactual Analysis significantly improved the performance of item-KNN.
Within the limited time of QuantumCLEF, we attempted Counterfactual Analysis of individual features. However, because the performance of collaborative filtering is actually the result of feature interactions, Counterfactual Analysis of individual features has significant limitations. Additionally, since Quantum Annealing cannot directly handle the selection of 500 features, we adopted a sequential partitioning and merging approach. As negative features are not uniformly distributed by their indices among all features, this sequential partitioning and merging method still requires improvement.