Ice-Breaking: Mitigating Cold-Start Recommendation Problem by Rating Comparison

1 Introduction

Since the concept of recommender systems emerged in 1990s [Resnick and Varian, 1997], both industry and academia have witnessed the rapid advancement in this field. For example, during the last decade, many mainstream e-commerce companies have reported significant profit growth by integrating recommender systems [Davidson et al., 2010; Das et al., 2007; Linden et al., 2003; Sarwar et al., 2000].

Despite the success of existing recommender systems, the cold-start problem [Merve Acilar and Arslan, 2009; Schafer et al., 2007], i.e., how to make proper recommendations for cold-start users or cold-start items, largely remains a daunting dilemma. On one hand, cold-start users (e.g., who have rated less than 10 items) and cold-start items (e.g., which have received less than 10 ratings) occupy a large proportion in many real applications such as Netflix [T¨oscher et al., 2009]. On the other hand, the effectiveness of the existing recommendation approaches (e.g., collaborative filtering) largely depends on the sufficient amount of historical ratings, and hence the effectiveness for cold-start users/items with very few ratings could degrade dramatically.

To date, many efforts have been made to mitigate the coldstart problem, and these efforts can be divided into three to serve as an ice-breaker for the cold-start problem. The key idea of RAPARE is to exploit the knowledge from warm users/items to help calibrate the latent profiles of cold-start users/items.

• We instantiate the proposed RAPARE strategy on matrix factorization based collaborative filtering (RAPAREMF), together with an effective and efficient solver.
• We conduct extensive experimental evaluations on two real data sets, showing that our approach (1) outperforms several benchmark collaborative filtering methods and online updating methods in terms of prediction accuracy; (2) earns better quality-speed balance while enjoying a linear scalability.

The rest of the paper is organized as follows. In Section 2, we provide the problem statement. In Section 3, we describe the proposed rating comparison strategy and the proposed model. In Section 4, we present the experimental results. In Section 5, we review related work. Finally, we conclude the paper in Section 6.

2 Problem Statement

In this section, we present the problem statement of cold-start recommendation. Suppose we have sets of users U, items I and observed ratings R. Let u, v represent the users, and i, j represent the items, respectively. Then, rui ∈ R is the rating of user u for item i accordingly. For the scenario of cold-start user problem, we call the users who have given less than a certain amount of ratings (e.g., 10 ratings) as cold-start users and the rest as warm users. Meanwhile, Rc and Rw denote the sets of ratings that belong to cold-start users and warm users, respectively. We use Rw(i) to represent the set of ratings on item i from warm users. Based on the notations, we have the following problem definition for recommending items to cold-start users. Similar notations and definition can be derived for the cold-start item problem, and thus are omitted for brevity.

Problem 1 The Cold-Start User Problem

Given: (1) the existing ratings Rw from warm users, (2) a new rating ruj from a cold-start user u to item j, and (3) an item i (i ̸= j);

Find: the estimated rating ˆ rui from user u to item i.

As we can see from the definition, the input of our problem includes the existing ratings from warm users, as well as the new ratings from cold-start users. No side information is needed. When a new rating from a cold-start user arrives, we aim to immediately update the estimated rating ˆ rui for any given item i. The estimated rating indicates to what extent the cold-start user u would prefer to an item i.

Preliminary #1. To date, matrix factorization has been one of the most dominate methods in recommender systems. Matrix factorization (MF) [Koren et al., 2009] assumes that users' opinions to items are based on the latent profiles for both users and items. With this assumption, MF projects both users and items into a common latent factor space to predict the rating (e.g., ˆ rui) by the following equation

where vector pu and qi are latent profiles for user u and item i, respectively. To learn these latent profiles, the square loss is usually used as the loss function

where L2 regularization is to avoid over-fitting.

In Eq. (2), the learned latent profiles may be less accurate for cold-start users/items due to the lack of sufficient ratings. To this end, we pay special attention to the cold-start users/items, and aim to calibrate the latent profiles for coldstart users/items with the help of the warm users/items. We will describe how to calibrate the latent profiles for cold-start users/items in the following section.

Preliminary #2. Elo Rating System, which is first adopted in chess, can be used to measure the relative skill levels between players in a certain competition. The basic idea behind Elo is that a player's rating (skill level) is determined by the competition outcomes against her opponents and the ratings of these opponents. For example, a player's rating will be greatly changed if she wins an opponent whose rating is much higher or if she loses to an opponent who has a much lower rating. In other words, the system implicitly aims to minimize the difference between the expected and the actual outcome of competitions.

3 The Proposed Approach

In this section, we present our rating comparison strategy (i.e., RAPARE) and the instantiation of RAPARE on matrix factorization based collaborative filtering (i.e., RAPAREMF). For brevity, we use the cold-start users as the subject throughout this section. It is straightforward to apply the proposed method for the cold-start items.

3.1 The RaPare Strategy

We aim to break the ice barrier between cold-start users and warm users with the help of warm users, so that we could better build the latent profiles of cold-start users. Specially, we achieve this goal by borrowing the idea of rating comparison from Elo Rating System. That is, we use the difference between the expected result and actual result from the rating comparison strategy to update the latent profiles of cold-start users. For example, suppose u is a cold-start user who has just rated item i, and v is an existing warm user who rated item i in the past. The expected result of this competition can be calculated as the difference between ˆ rui and rvi. Here, ˆ rui is estimated based on the latent profiles of user u (which is also the parameters that we aim to estimate). In the meanwhile, with the actual rating rui, we can have the actual result of the competition, which is the difference between rui and rvi. Based on the expected result and actual result of the competition, we may update the latent profiles of user u by following a similar strategy as in Elo Rating System. That is, the farther the expected result of competition deviates from its actual result, the larger the latent profiles of user u will be changed.

The basic idea of our RAPARE strategy is to tune the ratings (i.e., the latent profiles) according to the difference between the expected result and actual result of a rating comparison. From the perspective of optimization, the RAPARE strategy is equivalent to minimize the difference between the expected result and actual result by learning/tuning the the latent profiles of cold-start users. Therefore, we can minimize the following equation

where g is the loss/difference function for a rating comparison, and the square loss is used as the loss function, calculating the difference between expected result and actual result of a rating comparison. As we can see from the above formulation, for a given cold-start user, we can employ the potentially large amount of existing ratings from warm users to help calibrate the latent profiles of this cold-start user.

In this paper, we put our focus on the g function. We provide several candidates, including the linear difference, the logistic difference, and the elo difference. For the first two candidates, the are defined as follows

We use g(rui, rvi) as an example in the above equations, and equations for g(ˆ rui, rvi) can be similarly obtained by substituting rui with ˆ rui. For the elo candidate, two difference functions are used to compute g(rui, rvi) and g(ˆ rui, rvi), which are directly from Elo Rating System

where geloactual is used for calculating the actual result of the competition, and geloexpected is used for the expected result. Notice that geloexpected is actually the same with glogistic.

3.2 The RAPARE-MFModel

Next, we instantiate RAPARE with the matrix factorization method. Formally, we have the following optimization problem for RAPARE-MF

where Rw is the set of ratings from warm users, Riw is the set of ratings from warm users to item i, Rc is the set of ratings from cold-start users, Pc is the matrix of latent profiles for cold-start users, and Q is the matrix of latent profiles for items. To avoid the over-fitting problem, we also add a regularization term which is controlled by λ in the formulation.

As we can see from Eq. (8), given the input of the existing ratings from warm users, the arrival ratings from cold-start users, the initial latent profiles of cold-start users, and the latent profiles of items (learnt by MF method beforehand), the RAPARE-MF model aims to minimize the loss function defined in Eq. (9) by adjusting the Pc. The reason we focus on calibrating Pc while fixing Q is based on the observation that a few number of arrival ratings from cold-start users would not change the latent profiles of the corresponding items dramatically, but could have a much bigger impact on the latent profiles of cold-start users. Once the Pc is solved, we can estimate the rating from a cold-start user by Eq. (1).

Connections to existing methods. Notice that the RAPAREMF model with linear difference function is closely connected to the traditional MF model. The expanded form of RAPARE-MF model with linear difference can be written as

As we can see, similar to the traditional MF method [Rendle and Schmidt-Thieme, 2008], the above formulation also aims to optimize over the square loss between the actual rating and the predicted rating. In other words, our RAPARE-MF with linear difference function can be viewed as a weighted matrix factorization method for cold-start users.

3.3 Fast Model Inference Algorithm

Here, we propose a fast learning algorithm to solve the optimization problem in Eq. (8), which is based on the following two key observations of the inherent structure in the optimization formulation. First, there are usually a small set of possible ratings (e.g., 1-5 stars) for most recommender systems. Second, in Eq. (8), the contribution of the ratings from different warm users to item i is equal to each other if they share the same rating on item i. Specially, the optimization equation in Eq. (8) could be re-written as

where rmax is the maximal rating scale (e.g., rmax = 5 in Netflix), and |ΩRiw ,r| indicates the number of ratings in Riw with a value r.

For a given rating rui (from the cold-start user u to item i), we can now aggregate over the existing ratings (from the warm users to item i) with the same value, to form the basic update unit. Specially, we have the following general updating rule for Eq. (11)pu,f ← pu,f - α∇∗pu,f (12)

where the basic update unit ∇∗pu,f for the linear and the logistic differences is

Algorithm 1: Fast learning RAPARE-MF

Input: ratings fromwarm users Rw, ratings from cold-start users Rc, item latent factors Q, and the maximal rating scale rmax

Output: cold-start user latent factors Pc

• 1 initialize Pc

• 7 until convergence;
• 8 return Pc

where

for the linear difference function, and

for the logistic difference function.

For the elo difference, we directly use the difference between expected result and actual result as the basic update unit. The equation is as follows.

We use mini-batch gradient descent method to learn the parameters, and the algorithm is summarized in Algorithm 1. As we can see from the algorithm, we first initialize the Pc matrix. There are several initialization methods such as random initialization or cluster-based initialization. In this work, we adopt a heuristic averaging method. That is, for each coldstart user u, we first find the set of warm users who have given the same rating to item i as u does, and computes the average pi over latent profiles from these warm users. Then, we can have the initial pu for user u by further averaging pi over all rated items by user u. After initialization, the algorithm starts the iteration.

The time complexity of each iteration (Steps 3-6) in Algorithm 1 is O(|Rc| · rmax · k). Notice that if we use a straightforward gradient descent method, its average-case time complexity is O(|Rc| · |Riw | · k)). Thus, Algorithm 1 is much faster, since rmax ≪ |Riw | where |Riw | is the average number of ratings from warm users to each item.

4 Experiments

In this section, we present the experimental evaluations. All the experiments are designed to answer the following questions:

• Effectiveness: How accurate is the proposed approach for the cold-start problem?
• Efficiency: How fast is the proposed approach for updating the latent profiles of cold-start users/items?

4.1 Experimental Setup

Data Sets and Evaluation Metrics

We use two real, benchmark data sets: MovieLens 1 and EachMovie. The MovieLens data contains 1M ratings that are collected and published from the MovieLens website 2 . Each user in this data set rated at least 20 movies. EachMovie is organized by HP/Compaq Research. The statistics of the two data sets are summarized in Table 1.

As for evaluation metrics, we adopt the commonly used root mean square error (RMSE) for effectiveness comparison

where test set E contains the ratings for evaluation, ˆ rui is the predicted rating from user u to item i, rui is the ground truth, and |E| represents the number of ratings in E. For efficiency, we report the wall-clock time of the compared methods for updating the latent profiles of cold-start users/items.

Evaluation Protocol

Here, we describe how we evaluate the performance of our method for recommending items to cold-start users. Similar evaluation protocol can be applied to the cold-start items. Notice that our evaluation protocol follows the existing work [Rendle and Schmidt-Thieme, 2008].

We summarize the overall evaluation protocol for the coldstart users with the following descriptions.

1. Setup the cold-start user scenario

• Randomly choose 25% users (as cold-start users), put them into set Uc, and put all their ratings into the set Ec. The rest users are considered as warm users.
• Train the model for warm users via the MF method [Koren et al., 2009]. After this step, we can obtain the latent profiles of warm users and the latent profiles for all items
• Evaluate the cold-start user scenario
• Create an empty set Rc
• for n = 1, ..., 10 do:
• for each cold-start user u ∈ Uc do:
• randomly pick up 3 one of his ratings from the Ec and move it to Rc

1 http://www.grouplens.org/datasets/movielens/

2 http://movielens.org

3 The timestamps provided by these two datasets are the time that users rated the movies on their websites for data collection. Thus, all these timestamps cannot reflect the time sequences that user watch these movies. In other words, such timestamps do not capture the cold-start scenario.

(a) Cold-start user scenario on MovieLens (b) Cold-start item scenario on MovieLens (c) Cold-start user scenario on EachMovie (d) Cold-start item scenario on EachMovie

Figure 1: The effectiveness comparisons for cold-start scenarios on the EachMovie data and the MovieLens data. In general, RAPARE-MF outperforms all the compared methods for both cold-start users and cold-start items on both data sets.

• learn the latent profile of user u by the proposed method RAPARE-MF
• calculate the error between the predicted result and the actual result for the rest of u's ratings in the Ec
• calculate the error over all cold-start users

Compared Methods

In our evaluation protocol, the ratings in Rc are treated as the early ratings for the cold-start users/items in a dynamic manner. These ratings can also be regarded as the historical information for existing methods in a static manner. For example, MF method may take the ratings from warm users and coldstart users together as input. Here, we compare our RAPAREMF model with several classic collaborative filtering methods for both effectiveness and efficiency. The compared methods include: user/item based neighborhood methods (i.e., user KNN and itemKNN) [Sarwar et al., 2001], incremental SVD (iSVD) [Sarwar et al., 2002], matrix factorization (MF) [Koren et al., 2009], and Online Update which is proposed for updating the latent profiles of cold-start users/items [Rendle and Schmidt-Thieme, 2008].

4.2 Effectiveness Results

We first evaluate the effectiveness of the proposed method with the compared methods under the cold-start scenario. The results for both cold-start users and cold-start items on both data sets are shown in Fig. 1. The x-axis of Fig. 1 indicates the cold-start degree (i.e., the number of ratings given by each cold-start user/item), and the y-axis indicates the RMSE value. Smaller RMSE is better. Due to the limited page length, we do not provide the comparison of effectiveness on the three proposed difference functions in section 3.1. In this paper, we only choose logistic to evaluate the effectiveness, since it performs better than other two difference functions. On the EachMovie data, the performance of user KNN and item KNN are significantly worse than the other methods. Therefore, we exclude these two KNN methods in the comparison on the EachMovie data.

There are several observations from the results on the MovieLens data (Fig. 1(a) and Fig. 1(b)). First of all, in general, RAPARE-MF performs better than all the compared methods for both cold-start users and cold-start items. The item KNN and user KNN perform relatively poorly, especially at the beginning of the evaluation. The reason is that the preferences of the cold-start users/items are not accurately captured. The iSVD method performs very well at the beginning of the evaluation. This is because iSVD fills in all the missing values in the rating matrix with the mean rating values of the corresponding items. However, as the evaluation continues, no significant improvement is observed in the iSVD method. The MF method and Online Update method perform relatively well in the compared methods. The RMSE of these two methods decreases as the evaluation continues. However, RAPARE-MF still outperforms these two methods in all cases. This is due to the special calibration on the latent profiles of cold-start users/items. In other words, our proposed method indeed helps to lower the prediction error. Notice that, small improvements in RMSE could gain practically significant improvement in recommendation [Koren, 2008].

Similar results are observed on the EachMovie data (Fig. 1(c) and Fig. 1(d)). Meanwhile, we perform statistical t-test, which indicates that the improvement of RAPARE-MF is significant. For example, when the cold-start degree is 5, the p-value is less than 0.05 in all four settings (i.e., two coldstart scenarios on two data sets), against the corresponding best competitors. Overall, these results show the effectiveness of the proposed method for the cold-start problem.

4.3 Efficiency Results

Next, we present the efficiency results of the compared methods. We still report the results on the MovieLens data, while similar results are observed on the EachMovie data. All the experiments are run on a Macbook Pro. The machine has four 2.2GHz Intel i7 Cores and 8GB memory.

For efficiency, we first evaluate the quality-speed balance of different methods in both cold-start user and cold-start item scenarios. The results are shown in Fig. 2. In the figures, we plot the RMSE on the y-axis and the wall-clock time (in log scale) on the x-axis. An ideal method would locate at the leftbottom corner. As we can see from Fig. 2(a) and Fig. 2(b), our RAPARE-MF shows good balance between quality and speed in both cold-start user and cold-start item scenarios. In terms of the speed comparisons, our RAPARE-MF is 40% faster on average than the best competitor (i.e., Online Update).

Figure 3: Scalability of RAPARE-MF. RAPARE-MF scales linearly wrt the data size.

Finally, we study the scalability of the proposed RAPAREMF in Fig. 3. In the figures, we show the scalability of our method in terms of both the number of ratings from warm users/items (Fig. 3(a) and Fig. 3(b)) and the number of ratings from cold-start users/items (Fig. 3(c) and Fig. 3(d)). As we can see from the figures, our proposed RAPARE-MF scales linearly in all four cases.

5 Related work

In this section, we review the related work including the classic collaborative filtering methods and the existing recommendation approaches for the cold-start problem.

Classic Collaborative Filtering. Collaborative filtering (CF) has become an indispensable building block in many recommender systems. Two prevalent CF methods are the neighborhood method and the matrix factorization method. The basic idea of neighborhood method is to calculate the similarities between users/items, and make recommendations based on the most similar users/items. As for the matrix factorization method, it aims to learn the latent factors with the assumption that the ratings are based on the interactions between user latent factors and item latent factors [Koren et al., 2009; Shapira, 2011].

Recommendations for Cold-Start Scenarios. Existing efforts for the cold-start problem can be divided into three classes. In the first class, an additional step of rating collection is required. For example, an interview process where a set of items are usually presented for the cold-start users to provide their ratings [Zhou et al., 2011; Golbandi et al., 2011; Harpale and Yang, 2008; Sun et al., 2013]. The main focus in different interview processes lies in the selection of a proper item set. However, Rashid et al. [Rashid et al., 2002] point out that such interview process should be deliberately controlled to avoid user loss.

Methods in the second class resort to side information such as the user/item attributes [Zhang et al., 2014] and social relationships [Lin et al., 2013; Yao et al., 2014] to tackle the cold-start problem. However, these methods become infeasible in many real recommender systems where such side information may not be available.

In the third class, no additional rating collection or side information is required. Instead, the cold-start problem is considered and tackled in a dynamic manner. Methods in this class emphasize on the importance of new ratings from cold-start users, and aim to adjust the recommendation for these users as their new ratings arrive. For example, Sarwar et al. [Sarwar et al., 2002] introduce an incremental SVD (iSVD) algorithm for the cold-start users; Tackcs et al. [Tak´acs et al., 2008] and Rendle et al. [Rendle and Schmidt-Thieme, 2008] also provide incremental algorithms to update the latent factor vectors for cold-start users when they give new ratings. Our method falls into this class, and we propose a rating comparison model to give special treatments to the cold-start users/items.

6 Conclusions

In this paper, we have proposed a rating comparison strategy (RAPARE) to make proper recommendations for cold-start users/items. In particular, the RAPARE strategy provides a special, fine-grained treatment for cold-start users and coldstart items. Instantiating RAPARE with the matrix factorization method, we further propose the RAPARE-MF model as well as an effective and efficient algorithm to solve it. Experimental evaluations on two real data sets show that our approach outperforms several benchmark collaborative filtering and online updating methods in terms of prediction accuracy, and it provides fast recommendations with linear scalability.

7 Acknowledgments

This work is supported by the National Natural Science Foundation of China (No. 61373011, 91318301, 61321491). This material is supported by the National Science Foundation under Grant No. IIS1017415, by the Army Research Laboratory under Cooperative Agreement Number W911NF09-2-0053,by Defense Advanced Research Projects Agency (DARPA) under Contract Number W911NF-11-C-0200 and W911NF-12-C-0028, by National Institutes of Health under the grant number R01LM011986, Region II University Transportation Center under the project number 49997-33 25.

The content of the information in this document does not necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.