CLiMF: Collaborative Less-Is-More Filtering

1 Introduction

Collaborative Filtering (CF) [Adomavicius and Tuzhilin, 2005] methods are at the core of most recommendation engines in online web-stores and social networks. The main underlying idea behind CF methods is that users that shared common interests in the past would still prefer similar products/items in the future [Resnick et al., 1994]. While a lot of the CF literature has been devoted to recommendation scenarios where explicit user feedback is present (i.e., typically ratings), CF has also shown to be very valuable in scenarios with only implicit feedback data [Hu et al., 2008], e.g., the counts of a user watching a TV show, the counts of a user listening to songs of an artist, etc. These counts can be interpreted as a measure of preference and thus a proxy to explicit feedback.

However, in some scenarios even the "count" information is not available, while only binary relevance data exists, e.g., the friendship between users in a Online Social Network, the follow relationship between users (or between a user and an

Linas Baltrunas

Telefonica Research linas@tid.es

Alan Hanjalic

Delft University of Technology a.hanjalic@tudelft.nl

event, etc.) in Twitter 1 or the dating history in online dating sites [Pizzato et al., 2010], etc. In these scenarios, we use a "1" for a given user-item pair to denote that the user has an interaction (e.g., friendship, follow, "like") with the item, and "0" otherwise. Typically the observed interactions are regarded as positive signals (i.e., indicating relevant items), and although not all items without observed interactions are irrelevant it is safe to assume the vast majority of these items will be irrelevant for the user. In other words, for a given user, the signal "0" indicates an item set containing unobserved items that could be relevant but are most likely irrelevant.

Bayesian Personalized Ranking (BPR) [Rendle et al., 2009] has been recently proposed as a state-of-the-art recommendation algorithm for situations with binary relevance data. The optimization criterion of BPR is essentially based on pair-wise comparisons between relevant and a sample of irrelevant items. This criterion leads to the optimization of the Area Under the Curve (AUC). However, the AUC measure does not reflect well the quality of the recommendation lists, since it is not a top-biased measure [Yue et al., 2007], i.e., the position at which the pairwise comparisons are made is irrelevant to the contribution to the loss: mistakes at the lower ranked positions are penalized as equally as mistakes in higher ranked positions, which is not the desired behavior in a ranked list.

In view of these drawbacks, we propose a new CF approach, Collaborative Less-is More Filtering (CLiMF), that is tailored to recommendation domains where only binary relevance data is available. CLiMF models the data by means of directly optimizing the Mean Reciprocal Rank (MRR) [Voorhees, 1999], a well-known evaluation metric in Information Retrieval (IR). Given the analogy between querydocument search and user-item recommendation, we can define the Reciprocal Rank (RR) for a given recommendation list of a user, by measuring how early in the list (i.e. how highly ranked) is the first relevant recommended item. The MRR is the average of the RR across all the recommendation lists for individual users. MRR is a particularly important measure of recommendation quality for domains that usually provide users with only few but valuable recommendations (i.e., the less-is-more effect [Chen and Karger, 2006]), such as friends recommendation in social networks where top-3 or top-5 performance is important.

1 http://twitter.com/

Taking insights from the area of learning to rank and integrating latent factor models from CF, CLiMF directly optimizes a lower bound of the smoothed RR for learning the model parameters, i.e., latent factors of users and items, which are then used to generate item recommendations for individual users.

The contributions in this paper can be summarized as:

• We present a new CF approach, CLiMF, for MRR optimization for scenarios with binary relevance data. We demonstrate that CLiMF outperforms other state-of-theart approaches with respect to making only a few but relevant recommendations.
• We introduce a lower bound of the smoothed RR measure, significantly reducing the computational complexity of RR optimization, and enabling CLiMF to scale for large datasets.

2 CLiMF

In this section, we present the CLiMF, Collaborative Lessis-More Filtering, algorithm. We first introduce a smoothed version of Reciprocal Rank by taking insights from the area of learning to rank. Then, we derive a lower bound of the smoothed reciprocal rank, and formulate an objective function for which standard optimization methods can be deployed. Finally, we discuss the properties of the CLiMF model.

2.1 Smoothing the Reciprocal Rank

The definition of reciprocal rank of a recommendation list for user i, as defined in information retrieval [Voorhees, 1999], can be expressed as:

in which N is the number of items, Yij denotes the binary relevance score of item j to user i, i.e., Yij = 1 if item j is relevant to user i, 0 otherwise. I(x) is an indicator function that is equal to 1, if x is true, otherwise 0. Rij denotes the rank of item j in the recommendation list for user i. Note that the items are ranked in a descending order according to their predicted relevance scores for user i. Clearly, RRi is dependent on the rankings of relevant items. The rankings of the relevant items change in a non-smooth way as a function of the predicted relevance scores and thus, RRi is a non-smooth function over the model parameters. The non-smoothness of the RR measure makes it impossible to use standard optimization methods -such as gradient-based methods- to directly optimize RRi. Inspired by recent developments in the area of learning to rank [Chapelle and Wu, 2010], we derive an approximation of I(Rik < Rij) by using a logistic function:

where g(x) = 1/(1+e-x ), fij denotes the predictor function that maps the parameters from user i and item j to a predicted relevance score. The predictor function that we use in our model is the basic and widely-used factor model, expressed as:

where Ui denotes a d-dimensional latent factor vector for user i, and Vj a d-dimensional latent factor vector for item j. Even though a sophisticated approximation for the item rank was proposed in [Chapelle and Wu, 2010], it has not been deployed in practice. Notice that in the case of RRi in Eq. (1), only 1/Rij is actually in use. We thus propose to directly approximate 1/Rij by another logistic function:

which makes the basic assumption that the lower the item rank, the higher the predicted relevance score, i.e., 1/Rij would approach to 1. Substituting Eq. (2) and (4) into Eq. (1), we obtain a smooth version of RRi:

Notice that although Eq. (5) is a smooth function with respect to the predicted relevance scores and thus the model parameters U and V , optimizing this function could still be practically intractable, due to its multiplicative nature. For example, the complexity of the gradient of Eq. (5) with respect to Vj (i.e., only for one item) is O(N 2 ): the computational cost grows quadratically with the number of items N and for most recommender systems N is typically large. In the following, we present a lower bound of an equivalent variant of Eq. (5), for which we derive a computationally tractable optimization procedure.

2.2 Lower Bound of Smooth Reciprocal Rank

Suppose that the number of relevant items for user i in the given data collection is n+i . Given the monotonicity of the logarithm function, the model parameters that maximize Eq. (5) are equivalent to the parameters that maximize ln( 1 n+i RRi). Specifically, we have:

Based on Jensen's inequality and the concavity of the logarithm function, we derive the lower bound of ln( 1 n+i RRi) as below:

We can take a close look at the two terms within the first summation. The maximization of the first term contributes to learning latent factors that promote relevant items. However, given one relevant item, e.g., item j, maximizing the second term turns to learning latent factors of all the other items (e.g., item k) in order to degrade their relevance scores. In sum, the two effects come together to promote and scatter the relevant items at the same time. In other words, CLiMF will lead to a recommendation where some but not all relevant items are at the very top of the recommendation list for a user. We notice that this behavior of CLiMF corresponds to the analysis of MRR optimization for a search result list [Wang and Zhu, 2010], i.e., optimizing MRR results in diversifying ranked documents.

Taking into account the regularization terms that usually serve to control the complexity of the model (i.e. in order to avoid overfitting), and all the M users in the given data collection, we obtain the objective function of CLiMF:

in which λ denotes the regularization coefficient, and ‖U‖ denotes the Frobenius norm of U. Note that the lower bound F(U, V ) is much less complex than the original objective function in Eq. (5), and standard optimization methods, e.g., gradient ascend, can be used to learn the optimal model parameters U and V .

2.3 Optimization

We use stochastic gradient ascend to maximize the objective function in Eq. (8). By taking the deriviatives of eq. (8) with respect to Ui and Vj.

Note that optimizing (8) involves a sum over the average number of relevant items ˜n for each user since usually we have ˜n << S, the complexity is O(dS) even in the case that ˜n is large, i.e., being linear to the number of non-zeros (i.e. relevant observations in the data). In sum, our analysis shows that CLiMF is suitable for large scale use cases.

3 Experimental Evaluation

In this section we present a series of experiments to evaluate CLiMF. We first describe the datasets used in the experiments and the setup.

3.1 Experimental Setup

Datasets

We conduct experiments using two social network datasets from Epinions 2 and Tuenti 3 . The Epinions dataset is publicly available 4 , and contains trust relationship between 49288

2 http://www.epinions.com

3 http://www.tuenti.com

4 http://www.trustlet.org/wiki/Downloaded Epinions dataset

users. The Epinions dataset represents a directed social network, i.e., if user i is a trustee of user j, user j is not necessary a trustee of user i. For the purpose of our experiments, we exclude from the dataset the users who have less than 25 trustees. The second dataset collected from Tuenti, one of the largest social networks in Spain, represents an undirected social network, containing friendship between 50K users. Similar to the Epinions dataset, we also exclude the users with less than 25 friends. Note that in these two datasets, friends or trustees are regarded as "items" of users. The task is to generate friend or trustee recommendations to individual users. Statistics on the two datasets used in our experiments are summarized in Table 1.

Experimental Protocol and Evaluation Metrics

We separate each dataset into a training set and a test set under various conditions of user profiles. The condition of "Given 5" denotes that for each user we randomly selected 5 out of her trustees/friends to form the training set, and use the remaining trustees/friends to form the test set. We repeat the experiment 5 times for each of the different conditions of each dataset, and the performances reported are averaged across 5 runs.

The main evaluation metric utilized to measure the recommendation performance is MRR, the measure that is optimized in our model. In addition, we also measure the performance by precision at top-ranked items, using precision at top-5 (P@5), which reflects the ratio of the number of relevant items in the top-5 recommended items. In order to emphasize the value of "less-is-more" recommendations, we also use the measure of 1-call at top-ranked items [Chen and Karger, 2006]. Specifically, 1-call at top-5 recommendations (1-call@5) reflects the ratio of test users who have at least one relevant item in their top-5 recommendation lists.

Finally, as revealed in recent studies from different recommender domains, popular items could highly dominate the recommendation performance [Cremonesi et al., 2010; Shi et al., 2011; Steck, 2011]. We also notice this effect in our experiments, namely, recommending the most popular friends or trustees (i.e., those have the most friends or trusters) could already result in a high performance. For this reason we consider the top three most popular items as being irrelevant in order to reduce the influence from the most trivial recommendations [Cremonesi et al., 2010; Shi et al., 2011].

3.2 Performance Comparison

We compare the performance of CLiMF with three baselines, PopRec, iMF and BPR, which are described below:

• PopRec. A naive baseline that recommends a user to be a friend or trustee in terms of her popularity, i.e., the number of friends or trusters of each user.
• iMF: A state-of-the-art matrix factorization technique for implicit feedback data by Hu et al. [Hu et al., 2008].
• BPR-MF and implemented in MyMediaLite [Gantner et al., 2011]. Bayesian personalized ranking (BPR) represents the state-of-the-art optimization framework of CF for binary relevance data [Rendle et al., 2009].

The recommendation performances of CLiMF and the baseline approaches on the Epinions and the Tuenti datasets are shown in Table 2 and Table 3, respectively.

Three main observations can be drawn from the results: First, the proposed CLiMF model significantly outperforms the three baselines in terms of MRR across all the conditions and the two datasets. Note that in our experiments, the statistical significance is measured based on the results from individual test users, according to a Wilcoxon signed rank significance test with p¡0.01. This result corroborates that CLiMF achieves the goal that was designed for and optimizes the value of the reciprocal rank for the recommendations to the individual users. Second, CLiMF also achieves a significant improvement over the baselines in terms of P@5 and 1call@5 across all the conditions and the two datasets. The improvement of P@5 indicates that by optimizing MRR, CLiMF also improve the quality of recommendations among the topranked items. In addition, the improvement of 1-call@5 supports that CLiMF particularly contributes to providing valuable recommendations at the top-k positions, i.e., raising the chance that users would receive at least one relevant recommendation among just a few top-ranked items. Compared to BPR, where AUC is optimized, CLiMF succeeds in enhancing the top-ranked performance by optimizing MRR, the top-biased metric. As can be also seen from the results, iMF performs worse than both BPR and CLiMF in all the conditions of the Epinions dataset and in most of the conditions of the Tuenti dataset. The reason might be that iMF is particularly designed for implicit feedback datasets with the "count" information, while it may not be suitable for the scenarios with only binary relevance data. Third, relatively large improvements are attained in terms of most of the metrics when users have a low number of known friends/trustees, i.e., the case of "Given 5". This result suggests that CLiMF's key mechanism of scattering relevant items could be particularly beneficial for recommendation scenarios under very high data sparseness.

4 Future work

Future work involves a few interesting directions. First, we would like to extend our CLiMF model to suit domains with explicit feedback data, e.g., ratings. Second, it is also interesting to experimentally investigate the impact of CLiMF on the recommendation diversity, by exploiting external information resources, such as the categories of items. Third, we are also interested in investigating recommendation models that optimize other evaluation measures, and in exploring the impact of optimizing different measures on various aspects of recommendation performance [Wang and Zhu, 2010].

5 Acknowledgements

This work is funded as part of a Marie Curie Intra European Fellowship for Career Development (IEF) award (CARS, PIEF-GA-2010-273739) held by Alexandros Karatzoglou.