Implementing a Recommendation Engine with Amazon Braket

In this blog post, we detail an approach to solving a feature selection problem that implements a recommendation engine using Amazon Braket – the quantum computing service by Amazon Web Services. Our approach tackles the “cold-start” problem that recommendation systems face, produces a solution comparable with traditional approaches, and reaches the required levels of accuracy while removing less informative features. These results demonstrate how Amazon Braket supports fast prototyping of innovative solutions, enabling ContentWise and Moviri to innovate and explore a new generation of personalization engines.

About ContentWise and Moviri

ContentWise is a world leader in personalization systems. Moviri, ContentWise’s parent company, is a multinational technology consulting and software leader in IT services for digital transformation that brings emerging technologies to the market. ContentWise and Moviri joined forces to develop an innovative solution for the so-called cold-start problem in personalization applications that can be deployed on quantum computers using Amazon Braket.

Background on recommendation engines

In the world of media content, recommendation engines are at the heart of the user engagement process. As the name suggests, they are used to recommend to users the most attractive options from a list of items. Three types of information are usually used in the recommendation process. The first type is information about the user’s past choices. The second type is collaborative information describing the behavior and preferences of similar users. Lastly, the third type is content information represented through various metadata describing each list item. The effectiveness of recommendation engines generally depends on the type of available information. Recommendations based on collaborative information filtering are generally more effective than content-filtering-based recommendations. Often, however, collaborative information is not available. Let’s imagine, for example, a situation in which new items are added to a catalog. For the new items, there is no collaborative information that an algorithm could use, since past users behavior related to the items does not exist. This is the case, for example, in a TV broadcast where a viewer watches a TV program at its scheduled time. For a TV broadcast, most of a catalog’s content is new with nonexistent collaborative information. In this case, content-based filtering is usually applied. In general, when an item comes with inaccurate or missing collaborative information, it is designated as “cold” and recommending from a catalog with cold items is commonly known as the “cold-start” problem. Can we formulate our problem so that our recommendation engine performs better in this cold-start scenario?

Here we present a solution designed with quantum technology in mind, to address the recommendation system cold-start problem through feature engineering. Feature engineering is removing noisy or redundant item features and selecting only the useful ones, thus, improving the recommendation quality on the new “cold” items. Usually, feature engineering is a complex task that requires specific domain knowledge to be performed effectively. However, this kind of knowledge can also be extracted from users behavior on available “warm” items in the catalog. In our feature selection task, we specifically focus on selecting a subset of features that: a) generate a content-based model that performs as close as possible to a collaborative one on “warm” items where past user data is available; and b) do not overlap, avoiding those features that offer redundant information.

Problem formulation and solution

To improve the accuracy of a content-based recommendation engine, we are going to use feature filtering to narrow down the set of features that best resemble collaborative-based filtering. We determine a subset of features that describe the user’s behavior most accurately according to the similarity between collaborative-based and content-based models these features generate. This allows us to preserve properties of a good collaborative-based recommendation and avoid filter bubbles, i.e. situations where content recommendations are biased by the algorithm to a limited selection, ensuring a good level of serendipity (a technical term describing the ability of a recommendation engine to make recommendations that are not boring and predictable).

So how can we select those features effectively? We formulate the feature selection task as a Quadratic Unconstrained Binary Optimization (QUBO) problem. As the name suggests, this formulation represents quadratic optimization problems with binary variables and no hard constraints. By building and comparing a collaborative and a content-based model, we define the coefficients of the QUBO problem, in order to select features generating similarities present in both models. More details on the problem formulation can be found in Riccardo Nembrini et al., “Feature Selection for Recommender Systems with Quantum Computing” Entropy 23, no. 8: 970 (2021).

There are multiple ways to solve QUBO problems using classical operations research (e.g., tabu search, simulated annealing), quantum, or hybrid quantum-classical approaches. Here we explore a quantum solution. To validate the obtained solution, we benchmark it using non-QUBO-based classical approaches. We find that the quantum annealing solution to the feature selection problem is well-suited to our cold-start recommender system.

In quantum computing, several paradigms are available that can solve QUBO problems. To solve our problem, we selected the quantum annealing approach. A quantum annealer is a device composed of quantum bits (qubits) connected with each other according to the so-called topology graph of the device. By mapping each classical binary variable onto a qubit, a QUBO problem can be translated into a physics problem: finding the lowest energy state of a physical system of qubits. Quantum annealers solve the problem by first preparing uncoupled qubits in a minimum energy state and then slowly turn up the coupling between the qubits to its final strength, determined by the original QUBO problem. Under ideal conditions (no thermal noise and adiabatic coupling ramp up), the qubits will remain in the minimum energy state. Measuring the qubits at the end of the annealing cycle provides a solution to the underlying QUBO task and, thus, solves our feature selection problem. In a real-world annealer, the final qubit state does not always represent the minimum energy state due to noise and errors. Therefore, one has to repeat the computation multiple times to collect a statistical distribution of possible solutions.

Our solution architecture diagram is depicted in Figure 1. The recommendation engine builds the required models using input data stored in a Amazon Simple Storage Service (Amazon S3) bucket. After formulating our optimization task in the QUBO format, we send it to the D-Wave Advantage quantum annealer via a call to the Amazon Braket API. The annealer then processes the request and returns a list of potential solutions, ranked according to their energy. The lowest energy solution provides an answer to our feature selection problem. These features are used to generate recommendations that are then stored in Amazon S3.

Figure 1: Architecture diagram of the solution.

Results

We used two datasets to prototype and test our personalization engine:

1. a private small-scale dataset, which we will refer to as small-scale dataset; and
2. a public movies dataset from Kaggle, which we will refer to as the movies dataset.

The small-scale dataset is described by 79 features obtained by preprocessing a list of 190,000 users and 88,000 items. In contrast, the movies dataset is composed of 3,058 metadata features after preprocessing 260,000 users and 44,000 items. The main difference between the two sets is the initial number of features used to represent items in the datasets. The number of features defines the size of the corresponding QUBO problem. Today, quantum hardware is limited in the number of qubits. D-Wave’s most advanced chip, Advantage, has 5760 qubits that are connected with 35,000 couplers. As a consequence, the small-scale dataset with 79 features can be mapped on a QUBO problem which we solve with the D-Wave Advantage annealer. Then, we implement a hybrid approach on the movies dataset to assess the technology impact on a real business case. In particular, to build the hybrid solver we use D-Wave’s qbsolv library, which explores the solution space with tabu search, while solving small subproblems with the D-Wave Advantage annealer on Amazon Braket.

After we solve the feature selection problem via QUBO formulation, the next step is to measure the accuracy of our recommendations. We compute the accuracy in suggesting cold items to users by counting how many times a user would actually consume them, with an offline evaluation. In practice, we replicate the cold-start scenario by splitting the dataset into training and test sets, assigning each item’s interactions with users only to one of the two sets. This is called a cold-item split. It is introduced to ensure that new item recommendations are based solely on item’s features, that are also found in the training set. The best hyperparameters for our method are chosen depending on the recommendation accuracy on a validation set built by doing a cold-item split of the training set.

Typically, recommending the best-fit items to users is a difficult task, especially when using only content information. Therefore, typical values for these accuracy metrics must be compared to the results gained by classical content-based approaches, rather than to an absolute value.

As benchmarks, we consider three alternatives. The first one is a classical content-based recommender using all the features in the datasets, which we consider to be the reference. It gives us an indication about the number of features we can remove without losing accuracy. The second benchmark is an information retrieval method, which computes a score (TF-IDF) for each feature and allows the selection according to a user-defined parameter (we chose those ranking in the top 80% and 95%). A content-based recommender system is then built using the selected features. This is a well-known and fast method, but it does not exploit any domain-specific information. The last benchmark is a machine learning method which learns feature’s weights from a previously trained collaborative model with gradient descent. This algorithm solves a generalization of feature selection, by weighting all the features and producing recommendations accordingly. It optimizes an objective function analogous to our method, exploiting the user behavior and the domain semantics caught by the collaborative model. However, it suffers from long training times, which generally lead to slower solutions with respect to the other methods. We test this method with two different collaborative models (machine learning method -1 and -2 in Table 1).

The main purpose of the small-scale dataset is to validate our QUBO approach by running exclusively on quantum hardware. Nevertheless, it is worth noting that the quantum feature selection technique increases the precision by 17% when compared with the content-based recommender, reaching 0.0292 (or 2.9%) while using 80% of the initial features. In addition, we benchmark time to the solution for our QUBO problem using a classical QUBO solver based on simulated annealing and D-Wave Advantage quantum annealer. Time to the solution takes 0.2 seconds for the simulated annealing solver, whereas with D-Wave Advantage the computation takes 0.04 seconds.

The full comparison results, including metrics such as precision, recall and mean average precision (MAP), between the classical approaches and our QUBO-based personalization method are reported in Table 1.

Table 1 – Small-scale dataset results.

Next, let us analyze the results from the movies dataset, the industry-relevant dataset. Using all the 3,058 features to generate the recommendations leads to a precision of 0.1218 or 12%. The classical information retrieval approach that used 95% of the initial features results in a decrease of precision (9%), whereas the quantum solution matches the initial accuracy, using only 80% of the 3,058 features (line 3 Table 2). Furthermore, even reducing the percentage of features selected to 40%, the reference accuracy is still achieved.

This means that our QUBO-based method is able to weight, identify, and remove uninformative features in the dataset, while preserving the quality of the recommendations.

Table 2 – The movie’s dataset results. The two analyses performed with our QUBO-based method are related to a different parameter setting, leading to a different percentage of features selected.

From an industrial point of view, reducing the number of features used by the recommendation system by up to 60% has a very important implication in terms of model usability. In fact, we save time in collecting the reduced feature metadata, potentially speeding up model training, adapting to new items, and ultimately providing accurate recommendations to the users. This aspect is particularly important in TV broadcast applications, where metadata is usually unavailable, and optimizing the quality of the recommendation using fewer features is desirable.

Indeed, when looking at the semantics of the selection, we can point out that there are a few features, which are very unlikely to drive user behavior, and therefore can be removed, providing users with more tailored recommendations. Figures 2 and 3 respectively show the most and least selected features across all of our experiments on the movies dataset. As we can see, our method is able to automatically filter out old media companies that have been closed for many years (Biograph, PM Entertainment, and Lippert Films), languages, and release years, while retaining more useful features such as movie collections (for example, Transformers, X-Men and Mission Impossible) and media companies that specialize on specific genres (Kontsept Film).

Figure 2: Most selected features word cloud.

Figure 3: Least selected features word cloud.

Conclusion

We proposed an approach to solve the cold-start recommendation problem – a challenging personalization setting for ContentWise – by posing the feature selection task as a QUBO problem. We then solved it with classical operations research (OR) solvers and, as a proof of principle, on a small-scale dataset, with the D-Wave Advantage quantum annealer on Amazon Braket. The quantum-annealing-based QUBO solution provided improvements in terms of the solution’s quality in the presence of a significant feature reduction and computational speedups compared to the out-of-the box classical solvers we utilized. In the future, we will investigate its performance also against optimized classical approaches and QUBO solvers like, for example, AlphaQUBO, available on AWS Marketplace. We confirmed the improvement of the quality of the solution by also performing the comparison on the movies dataset, which is an industry-relevant one. We showed that for this specific problem, the same accuracy in recommendation quality can be achieved by reducing the number of features, up to 40%, thanks to an efficient QUBO-based feature selection algorithm.

Being a fully-managed service, Amazon Braket enabled us to perform fast prototyping of innovative QUBO-based solutions. This was particularly convenient for plug-and-play applications such as our model, since cold-start problem solutions are likely to require re-training and data-adaptation at different times.

In keeping with its focus on bringing to market the most advanced technologies and enabling innovation for its customers, Moviri strengthened its experience on this highly promising technology, investing through its R&D program in training and development of quantum computing expertise and solutions.

Finally, for ContentWise, this experiment validated QUBO and quantum annealing approaches to personalization as an additional technology asset for continuous innovation in the implementation of new use cases and better personalized customer experience.

The content and opinions in this post are those of the third-party author and AWS is not responsible for the content or accuracy of this post.