GBPR: Group Preference Based Bayesian Personalized Ranking for One-Class Collaborative Filtering

1 Introduction

In industry, recommender system as a critical engine in various online entertainments and shopping services has caught much attention and contributed significant revenue growth in recent years. Lots of internet, electronic and telecom giants embed recommendation technologies in their existing systems to increase user engagement and business revenues from more product or advertisement sales.

In academia, most research studies in recommender systems are somehow biased to the Netflix competition 1 , partially due to the public availability of the data. The Netflix contest can be categorized as a "multi-class" recommendation problem, where the inputs are categorical scores. For example, the input data of Netflix are ratings with "1" for bad, "2" for fair, "3" for good, "4" for excellent, and "5" for perfect, for which various algorithms are proposed in order to predict the users' preference scores accurately. Such categorical data contain both positive feedback of "4" and "5", and negative feedback of "1" and "2", where some regression or ranking loss functions were designed to fit the score or to preserve the ordering, among which matrix-factorization based models have been shown to be the most effective solutions [Weimer et al., 2007; Koren, 2008; Rendle, 2012; Liu et al., 2013].

1 http://www.netflixprize.com/

However, in most applications, the collected data of user behaviors are in "one-class" form rather than multi-class form, e.g., "like" in Facebook, "bought" in Amazon, and "click" in Google Advertisement. Such data are usually called implicit [Nichols, 1997; Rendle et al., 2009] or oneclass [Pan et al., 2008] feedback. The one-class collaborative filtering problem is different from that of 5-star rating prediction in the Netflix competition, since the former only contains positive feedback rather than both positive feedback and negative feedback in the contest, and the goal is item ranking instead of rating prediction.

For solving the one-class collaborative filtering problem, previous matrix-factorization based algorithms can be roughly summarized in two manners, (1) pointwise regression methods, and (2) pairwise ranking methods. The former learn a latent representation of both users and items via minimizing a pointwise square loss [Pan et al., 2008; Hu et al., 2008] to approximate the absolute rating scores, while the latter take pairs of items as basic units and maximize the likelihood of pairwise preferences over observed items and unobserved items [Rendle et al., 2009]. Empirically, the pairwise ranking method [Rendle et al., 2009] achieves much better performance [Du et al., 2011] than pointwise methods [Pan et al., 2008; Hu et al., 2008], and has been successfully adopted in many applications, e.g., tag recommendation [Rendle and Schmidt-Thieme, 2010], news recommendation [Yang et al., 2011], and shopping items recommendation [Kanagal et al., 2012].

In this paper, we study the two fundamental assumptions made in the seminal work of pairwise ranking method [Rendle et al., 2009], and point out its limitations. As a response, we introduce group preference instead of individual preference alone in [Rendle et al., 2009], in order to inject richer interactions among users and thus relax the individual and independence assumptions. We then propose a new and improved assumption called group Bayesian personalized ranking (GBPR) and design an efficient algorithm correspondingly. Empirically, we find that our new assumption digests the one-class data more effectively and achieves better recommendation performance on all four real-world datasets in our experiments.

2 RelatedWork

In this section, we discuss some related works of one-class collaborative filtering in two branches of work, (1) pointwise methods with absolute preference assumptions, and (2) pairwise methods with relative preference assumptions.

Pointwise methods with absolute preference assumptions Pointwise methods take implicit feedback as absolute preference scores. For example, an observed user-item pair, (u, i), is interpreted as that user u likes item i with a high absolute score, e.g., 1. OCCF (one-class collaborative filtering) [Pan et al., 2008] and iMF (implicit matrix factorization) [Hu et al., 2008] are two typical pointwise approaches for solving this recommendation problem. OCCF [Pan et al., 2008] proposes different sampling strategies for unobserved user-item pairs and take them as negative feedback to augment the observed positive feedback, so that existing matrix factorization methods can be applied. iMF [Hu et al., 2008] introduces confidence weights on implicit feedback, which can then be approximated by two latent feature matrices. However, the limitation of OCCF [Pan et al., 2008] is that taking unobserved user-item pairs as negative feedback may introduce errors. As for iMF [Hu et al., 2008], it requires auxiliary knowledge of confidence for each observed feedback, which may not be available in real applications.

Pairwise methods with relative preference assumptions Pairwise methods take implicit feedback as relative preferences rather than absolute ones, e.g., a user u is assumed to prefer an item i to an item j if the user-item pair (u, i) is observed, and (u, j) is not observed [Rendle et al., 2009]. The proposed algorithm, Bayesian personalized ranking (BPR) [Rendle et al., 2009], is the first method with such pairwise preference assumption for addressing the one-class collaborative filtering problem.

Due to the great success of pairwise methods in various one-class collaborative filtering problems, some new algorithms have been proposed to combine BPR with some auxiliary data, such as BPR with temporal information [Rendle et al., 2010], BPR with user-side social connections [Du et al., 2011], and BPR with item-side taxonomy [Kanagal et al., 2012], etc. There are also some work that extends BPR from two dimensions to three dimensions [Rendle and SchmidtThieme, 2010], or from one user-item matrix to multiple ones [Krohn-Grimberghe et al., 2012].

However, the limitation of pairwise methods can be attributed to the two fundamental assumptions made in BPR, namely individual pairwise assumption over two items and independence assumption between two users. Most followup works do not refine the fundamental assumptions, but just directly adopt the BPR criterion in their own applications. A recent algorithm [Pan and Chen, 2013] generalizes BPR via proposing a new assumption that an individual user is likely to prefer a set of observed items to a set of unobserved items.

Compared with the aforementioned works, our proposed group Bayesian personalized ranking (GBPR) method, is a novel algorithm in one-class collaborative filtering. In particular, GBPR inherits the merit of pairwise methods, and improves the two fundamental assumptions in BPR via introducing group preference. We summarize GBPR and the aforementioned related works in Table 1.

3 Background

In this section, we first give the problem definition, and then introduce the likelihood of pairwise preferences and the two fundamental assumptions made in BPR [Rendle et al., 2009].

3.1 ProblemDefinition

We use U tr = {u}nu=1 and I tr = {i}mi=1 to denote the sets of users and items, respectively. For each user u ∈ U tr , we have a set of items I tr u ⊆ I tr on which user u has expressed positive feedback, e.g., "like". Our goal is then to recommend each user u a personalized ranking list of items from I tr \I tr u . As mentioned before, this problem has been steadily receiving more attention, and usually called one-class collaborative filtering [Pan et al., 2008] or collaborative ranking with implicit feedback [Rendle et al., 2009].

3.2 Likelihood of Pairwise Preferences

In order to represent a user u's relative preference on two items i and j, Rendle et al. [Rendle et al., 2009] use a binary random variable δ((u, i) ≻ (u, j)) to denote whether user u prefers item i to item j or not. The function δ(z) is a binary indicator with δ(z) = 1 if the equation z is true, and δ(z) = 0 otherwise. This representation is usually called a user's pairwise preference and has dominated in one-class collaborative filtering tasks in recent studies [Rendle et al., 2009; Du et al., 2011; Kanagal et al., 2012].

For a typical user u, in order to calculate the overall likelihood of pairwise preferences (LPP) among all items, Bernoulli distribution over the binary random variable δ((u, i) ≻ (u, j)) is used in [Rendle et al., 2009],

where (u, i) ≻ (u, j) denotes that user u prefers item i to item j.

3.3 Bayesian Personalized Ranking

The two fundamental assumptions adopted by the method Bayesian personalized ranking (BPR) [Rendle et al., 2009] are:

1. Assumption of individual pairwise preference over two items. It assumes that a user u prefers an item i to an item j, (u, i) ≻ (u, j), if the user-item pair (u, i) is observed and (u, j) is not observed. With this assumption, LPP(u) can be simplified to BPR(u) [Rendle et al., 2009],

where i ∈ I tr u means that the user-item pair (u, i) is observed, and j ∈ I tr \I tr u means that the user-item pair (u, j) is not observed.

2. Assumption of independence among users. It assumes that the joint likelihood of pairwise preferences of two users, u and w, can be decomposed as BPR(u,w) = BPR(u)BPR(w), which means that the likelihood of pairwise preferences of user u is independent of that of user w. With this assumption, the overall likelihood among the users can be represented as follows [Rendle et al., 2009],

However, the above two assumptions may not always hold in real applications. First, a user u may potentially prefer an item j to an item i, though the user u has expressed positive feedback on item i instead of on item j. For example, John may like Prince of Egypt more than Forrest Gump though we have only observed positive feedback on the latter yet. Second, two users, u and w, may be correlated, and their joint likelihood can not be decomposed into two independent likelihoods.

4 Our Solution

4.1 Group Bayesian Personalized Ranking

As a response to the possible violations of the two fundamental assumptions made in BPR [Rendle et al., 2009], we propose a new assumption and introduce richer interactions among users via group preference. And for this reason, we call our assumption group Bayesian personalized ranking (GBPR). In the following, we first describe two definitions before introducing our new assumption.

Definition (Individual Preference) The individual preference is a preference score of a user on an item. For example, the individual preference of user u on item i is denoted as ˆ rui . Definition (Group Preference) The group preference is an overall preference score of a group of users on an item. For example, the group preference of users from group G on item i can be estimated from individual preferences, ˆ rGi = 1 |G| ∑w∈G ˆ rwi. Note that our primary goal is to recommend items for a single user, not for a group of users [Amer-Yahia et al., 2009].

We assume that the group preference of G ⊆ U tr i on an item i is more likely to be stronger than the individual preference of user u on item j, if the user-item pair (u, i) is observed and the user-item pair (u, j) is not observed. The group pairwise preference can then be written conceptually,

where G ⊆ U tr i and u ∈ G. We illustrate our assumption of group pairwise preference via a toy example in Figure 1. Our assumption can be interpreted from two aspects,

• For items, it is more likely to be true if user u can find some other users' support on his pairwise preference on item i and item j. This is reflected by the replacement of the individual pairwise relationship (u, i) ≻ (u, j) with a new one (G, i) ≻ (u, j) that involves the group preference.
• For users, it is natural to introduce interactions and collaborations among users who are all with positive feedback on a specific item, since that implies common interests of those users. This is reflected in the group of like-minded users, G ⊆ U tr i , who share the same positive feedback to item i.

To explicitly study the unified effect of group preference and individual preference, we combine them linearly,

where ˆ rGui = ρˆ rGi + (1 - ρ)ˆ rui is the fused preference of group preference ˆ rGi and individual preference ˆ rui. Note that 0 ≤ ρ ≤ 1 is a tradeoff parameter used to fuse the two preferences, which can be determined via empirically testing a validation set.

With this assumption, we have a new criterion called group Bayesian personalized ranking (GBPR) for user u,

where G ⊆ U tr i is a user group, and item i is observed by user u and item j is not observed. For any two users, u and w, the joint likelihood can then be approximated via multiplication, GBPR(u,w) ≈ GBPR(u)GBPR(w), since the user correlations have been introduced via the user group G already. More specifically, for any two users u and w who have same positive feedback to an item i, the corresponding user groups G(u, i) ⊆ U tr i and G(w, i) ⊆ U tr i are likely to be overlapped, G(u, i) ∩ G(w, i) ̸= ∅. Then, we have the following overall likelihood for all users and all items,

where G ⊆ U tr i .

Following [Rendle et al., 2009], we use σ(ˆ rGui - ˆ ruj) = 1 1+exp(-ˆ rGui+ˆ ruj) to approximate the probability Pr(ˆ rGui > ˆ ruj), and have Pr(ˆ rGui > ˆ ruj)[1 - Pr(ˆ ruj > ˆ rGui)] = σ(ˆ rGui - ˆ ruj )[1 - σ(ˆ ruj - ˆ rGui)] = σ2 (ˆ rGui - ˆ ruj). Finally, we reach the objective function of our GBPR,

where Θ = {Uu· ∈ R1×d , Vi· ∈ R1×d , bi ∈ R, u ∈ U tr , i ∈ I tr } is a set of model parameters to be learned, lnGBPR = ∑u∈U tr ∑i∈I tr u ∑j∈I tr \I tr u 2 ln σ(ˆ rGui - ˆ ruj) is the log-likelihood of GBPR, R(Θ) = ∑u∈U tr ∑i∈I tr u ∑j∈I tr \I tr u [αw ∑w∈G ‖Uw·‖2 + αv‖Vi·‖2 + αv‖Vj·‖2 + βv‖bi‖2 + βv‖bj‖2 ] is the regularization term used to avoid overfitting, and G ⊆ U tr i is a group of like-minded users who share the same positive feedback to item i. We show the graphical model of GBPR in Figure 2, where the individual preference is generated via ˆ rui = Uu·V T i· +bi, ˆ ruj = Uu·V T j· +bj, and group preference ˆ rGi = ¯UG·V T i· + bi with ¯UG· = ∑w∈G Uw·/|G|. The main difference between GBPR and BPR [Rendle et al., 2009] is the first term in Eq.(4), which introduces richer interactions among users via the user group G, and as a consequence relax the two fundamental assumptions made in BPR [Rendle et al., 2009].

Therefore, once we have learned the model parameters Θ, we can predict the preference of user u on item j via ˆ ruj = Uu·V T j· + bj, which can then be used to generate a personalized ranking list for user u via picking up the top-k items with largest preference scores.

4.2 Learning the GBPR

We follow the widely used stochastic gradient descent (SGD) algorithm to optimize the objective function in Eq.(4). We go one step beyond SGD, and randomly sample a subset of like-minded users to construct the user group G. For each randomly sampled record, it includes a user u, an item i, an item j, and a user group G, where u ∈ G. The tentative objective function can be written as f(G, u, i, j) = - ln σ(ˆ rGui - ˆ ruj )+ αu 2 ∑w∈G ‖Uw·‖2 + αv 2 ‖Vi·‖2 + αv 2 ‖Vj·‖2 + βv 2 ‖bi‖2 + βv 2 ‖bj‖2 = ln[1 + exp(-ˆ rGui;uj)] + αu 2 ∑w∈G ‖Uw·‖2 + αv 2 ‖Vi·‖2 + αv 2 ‖Vj·‖2 + βv 2 ‖bi‖2 + βv 2 ‖bj‖2 , where ˆ rGui;uj =

ˆ rGui - ˆ ruj is the difference between the fused preference ˆ rGui and individual preference ˆ ruj .

We then have the gradients of the user-specific parameters w.r.t. the tentative objective function f(G, u, i, j),

and the gradients of the item-specific parameters,

where ∂f(G,u,i,j) ∂ˆ rGui;uj = - exp(-ˆ rGui;uj ) 1+exp(-ˆ rGui;uj) = - 1 1+exp(ˆ rGui;uj ) , and w ∈ G. With the above gradients, we can update the model parameters as follows,

where θ can be Uw·, w ∈ G, Vi·, Vj·, bi or bj , and γ > 0 is the learning rate. Note that when G = {u} or ρ = 0, GBPR is reduced to BPR [Rendle et al., 2009], which does not explicitly incorporate interactions among like-minded users.

The complete steps to learn the model parameters are depicted in Figure 3. The time complexity of the update rule in Eq.(5) is O(|G|d), where |G| is the size of user group, and d is the number of latent features. The total time complexity is then O(Tn|G|d), where T is the number of iterations and n is the number of users. We can see that introducing interactions in GBPR does not increase the time complexity much, because |G| is usually small, e.g., |G| ≤ 5 in our experiments. For predicting a user's preference on an item, the time complexity is O(d), which is the same as that of BPR. Thus,

Input: Training data TR = {(u, i)} of observed feedback and the size of user group |G|. Output: The learned model parameters Θ = {Uu·, Vi·, bi·, u ∈ U tr , i ∈ I tr }, where Uu· is the userspecific latent feature vector of user u, Vi· is the itemspecific latent feature vector of item i, and bi is the bias of item i. For t1 = 1, . . . , T . For t2 = 1, . . . , n. Step 1. Randomly pick a user u ∈ U tr . Step 2. Randomly pick an item i ∈ I tr u . Step 3. Randomly pick an item j ∈ I tr \I tr u . Step 4. Randomly pick |G| - 1 users from U tr i \{u} to form the user group G. Step 5. Calculate ∂f(G,u,i,j) ∂ˆ rGui;uj and ¯UG·. Step 6. Update Uw·, w ∈ G via Eq.(5). Step 7. Update Vi· via Eq.(5). Step 8. Update Vj· via Eq.(5). Step 9. Update bi via Eq.(5). Step 10. Update bj via Eq.(5). End End

GBPR can be comparable to the seminal work BPR [Rendle et al., 2009] in terms of efficiency. In the experiments, we mainly assess whether GBPR would be more accurate than BPR.

5 Experimental Results

5.1 Datasets

We use four real-world datasets in our empirical studies, including MovieLens100K 2 , MovieLens1M, UserTag [Pan et al., 2008] and a subset of Netflix. MovieLens100K contains 100, 000 ratings assigned by 943 users on 1, 682 movies, MovieLens1M contains 1, 000, 209 ratings assigned by 6, 040 users on 3, 952 movies, and UserTag contains 246, 436 user-tag pairs from 3, 000 users and 2, 000 tags. We randomly sample 5, 000 users from the user pool and 5, 000 items from the item pool of the Netflix dataset, and obtain 282, 474 ratings by those 5, 000 users on those 5, 000 items. We call this subset of Netflix dataset Netflix5K5K. We use "item" to denote movie (for MovieLens100K, MovieLens1M and Netflix5K5K) or tag (for UserTag). For MovieLens100K, MovieLens10M and Netflix5K5K, we take a pre-processing step [Sindhwani et al., 2009], which only keeps the ratings larger than 3 as the observed positive feedback (to simulate the one-class feedback).

For all four datasets, we randomly sample half of the observed user-item pairs as training data, and the rest as test data; we then randomly take 1 user-item pair for each user from the training data to construct a validation set. We repeat the above procedure for three times, so we have three copies of training data and test data. The final datasets used in the experiments are shown in Table 2. The experimental results are averaged over the performance on those three copies of test data.

2 http://www.grouplens.org/node/73

5.2 EvaluationMetrics

Because users usually only check a few top-ranked items [Chen and Pu, 2011], we use top-k evaluation metrics to study the recommendation performance, including top-k results of precision, recall, F1, NDCG and 1-call [Chen and Karger, 2006]. Since BPR [Rendle et al., 2009] optimizes the AUC criterion, we also include it in our evaluation. For each evaluation metric, we first calculate the performance for each user from the test data, and then obtain the averaged performance over all users.

5.3 Baselines and Parameter Settings

We use two popular baseline algorithms in our experiments, PopRank and BPR [Rendle et al., 2009]. PopRank is a basic algorithm in one-class collaborative filtering, which ranks the items according to their popularity in the training data. BPR [Rendle et al., 2009] is a seminal work for this problem and is also a very strong baseline, which is shown to be much better than two well-known pointwise methods [Du et al., 2011], i.e., iMF [Hu et al., 2008] and OCCF [Pan et al., 2008]. In this paper, we extend BPR via introducing richer interactions, and thus, we concentrate our empirical study on comparisons between BPR and our GBPR, which are both implemented in the same code framework as shown in Figure 3.

For all experiments, the tradeoff parameters are searched as αu = αv = βv ∈ {0.001, 0.01, 0.1} and ρ ∈ {0.2, 0.4, 0.6, 0.8, 1}, and the iteration number is chosen from T ∈ {1000, 10000, 100000}. The NDCG@5 performance on the validation data is used to select the best parameters αu, αv, βv and ρ, and the best iteration number T for both BPR and GBPR. The learning rate in BPR and GBPR is fixed as γ = 0.01. The initial value of Uu·, Vi·, bi in BPR and GBPR are set the same as in [Pan et al., 2012]. For the user group G in GBPR, we first fix the size as |G| = 3, and then change it as |G| ∈ {1, 2, 3, 4, 5} in order to study the effect of different levels of interactions as introduced in our proposed GBPR algorithm. Note that when ρ = 0 or |G| = 1, GBPR reduces to BPR.

5.4 Summary of Experimental Results

The recommendation performance of GBPR and other baselines are shown in Table 3, from which we can have the following observations,

1. both BPR and GBPR are much better than the PopRank algorithm, which demonstrates the effectiveness of pairwise preference assumptions, and
2. GBPR further improves BPR on all evaluation metrics on all four datasets, which shows the effect of the injected interactions among users via group preference.

We can thus see that the assumption that combines pairwise preference and group preference in GBPR is indeed more effective than that of simple pairwise preference assumed in BPR [Rendle et al., 2009].

To have a deep understanding of the effect of group preference in GBPR, we adjust the group size |G| ∈ {1, 2, 3, 4, 5} and show the results of P re@5, NDCG@5 and AUC in Figure 4. The performance on Rec@5, F1@5 and 1-call@5 are similar, so they are not included for the sake of saving space. From Figure 4, we can see that using a relatively larger user group (e.g., |G| = 3 or 4) improves the recommendation performance on all four datasets. This can be explained by the effect of introducing the user group G for modeling the pairwise preference in Eq.(2) and learning the model parameters in Eq.(5).

6 Conclusions and FutureWork

In this paper, we study the one-class collaborative filtering problem and design a novel algorithm called group Bayesian personalized ranking (GBPR). GBPR introduces richer interactions among users in order to improve the individual and independence assumptions as made in Bayesian personalized ranking (BPR) [Rendle et al., 2009], a seminal work for addressing this problem. GBPR is comparable to BPR in terms of time complexity. Experimental results on four real-world datasets show that GBPR can recommend items more accurately than BPR regarding various evaluation metrics.

For future works, we are interested in extending GBPR via (1) optimizing the user group construction process, such as incorporating time, location, taxonomy and other possible contexture information to refine the like-minded user groups, and (2) adaptively changing group size for different segmentations of users and items during the learning process.

Acknowledgement

We thank the support of Hong Kong RGC under the project ECS/HKBU211912.