Sparse Bayesian Content-Aware Collaborative Filtering for Implicit Feedback

1 Introduction

Recommender systems provide users with personalized recommendations for items (e.g., products and services), hopefully suiting their unique needs. In the past years, they have been used for functions like increasing sales in ecommerce and clicking rates on websites, and improving general visitor satisfaction, and thus are attracting a lot of attention from academia and industry [Linden et al., 2003; Adomavicius and Tuzhilin, 2005; Koren, 2008]. Typically, these systems profile users and items from the implicitly or explicitly generated data and recommend user the most related items. Due to the large amount of implicit feedback, such as views, listening, or visiting behaviors, and the specific characteristics of lacking substantial evidence on which items that users dislike (i.e., negative items), recommendation for implicit feedback datasets has already become an important research direction [Hu et al., 2008; Pan et al., 2008; Rendle et al., 2009; Gopalan et al., 2015].

The popularity of social media makes the availability of a large amount of user-generated content and user information, playing an important part in addressing the coldstart problems in recommendation. Although much effort has been devoted to incorporating content into recommendation, such as LibFM [Rendle, 2012], MatchBox [Stern et al., 2009], regression-based latent factor model [Agarwal and Chen, 2009] and MF-EFS [Koenigstein and Paquet, 2013], they are mainly designed for explicit feedback. Although recommendation for implicit feedback has been integrated with topic modeling for incorporating items' textcontent [Wang and Blei, 2011; Gopalan et al., 2014], there is still no general framework tailored to implicit feedback to take any type of features. Applying the previously developed general algorithms for explicit feedback requires randomly sampling negative items from missing entries in the useritem matrix for better learning efficiency. However, such a strategy is empirically sub-optimal, compared to treating all missing entries as negative but assigning them a lower confidence, according to [Wang and Blei, 2011; Lian et al., 2014; Liu et al., 2014]. The varying confidence for negative and positive preference can also be modeled by a two stage process recommendation model, according to [Gopalan et al., 2015], the first of which appropriately fit the volume of user activity, i.e., budget. However, their evaluation doesn't indicate a strong advantage on implicit feedback. Another alternative modeling approach for varying confidence is to leverage ranking-based factorization algorithms, especially optimizing metrics at the top positions [Weston et al., 2010]. Nevertheless, it does not perform as well as expected empirically according to our evaluation results, and even suffered from computation issues [Li et al., 2015].

Due to the effectiveness and efficiency of [Hu et al., 2008], we propose a content-aware collaborative filtering framework tailored to implicit feedback based on their algorithm. It can incorporate any kind of content of users and items at the same time of both steering clear of negative sampling and modeling the varying confidence. It takes a user-item preference matrix, a user-feature matrix (e.g., gender, age) and an item-feature matrix (e.g., categories, descriptions) as input and maps each user, each item, and each feature of both users and items into a joint latent space. This framework can exploit gradient descent for parameter learning, but suffers from timeconsuming search (e.g., grid search) for the learning rate and the regularization coefficients.

To address this issue, we first present an equivalent but more generalized probabilistic generative model for implicit feedback, where both latent factors and hyperparameters (i.e., regularization coefficients) are considered hidden variables. Based on this model, we develop a scalable optimization algorithm for jointly learning latent factors and hyperparameters. Due to the adaptive update of hyperparameters, automatic relevance determination and even feature selection for content is naturally embedded in this framework according to the sparse Bayesian learning framework [Tipping, 2001]. This also leads to another distinguishing characteristic compared to Libfm, svdfeature [Chen et al., 2012] and et al., in addition to steering clear of negative sampling based on a highly efficient learning algorithm.

The proposed algorithm is then evaluated on three different implicit feedback datasets and compared with several stateof-the-art content-aware recommendation algorithms, including Libfm and svdfeature. Convincing experimental results indicate that the proposed algorithm is not only capable of pruning non-informative features, but also best tailored to content-aware recommendation for implicit feedback.

2 Preliminary

2.1 Matrix Factorization for Implicit Feedback

Matrix factorization for implicit feedback operates a useritem preference matrix R 2 ¶0↪ 1♦M⇥N , including M users and N items. Each entry ri↪j 2 R indicates whether the entry is observed or not, where i and j are reserved for indexing users and items, respectively. In matrix factorization, users and items are represented in a joint latent space of dimension K: user i is represented by a latent vector si 2 RK and item j by a latent vector tj 2 RK . We form the predicting preference of user i for item j with an inner product, i.e., ˆ ri↪j = s0i tj .

Due to the lack of negative preference in implicit feedback, matrix factorization in this case needs to either sample pseudo-negative items for each user from missing entries in the user-item matrix [Pan et al., 2008; Rendle et al., 2009] or treat the data as an indication of positive and negative preference with vastly varying confidence [Hu et al., 2008]. Due to empirically observed superiority, we focus on the latter algorithm [Lian et al., 2014; Liu et al., 2014], which minimizes the weighted squared loss with a regularized term:

where λ is a regularization coefficient and wi↪j indicates the confidence of user preference, i.e.,

where β is a tuning parameter satisfying β ≫ 1, so that the confidence of the observed entries are much larger than the missing ones.

However, such a matrix factorization will fail in the coldstart problem. A general solution is to integrate collaborative filtering with content-based filtering [Pazzani, 1999] and has been yielded by some popular content-aware collaborative filtering frameworks, such as LibFM, MatchBox, and SVDFeature. However, they mainly target explicit feedback datasets, which include both positively and negatively preferred samples. Feeding implicit feedback into them is presumed to be suboptimal, due to the empirically observed superiority of the above algorithm for implicit feedback. This thus motivates us to develop a general content-aware collaborative filtering framework tailored to implicit feedback.

2.2 Content-Aware Collaborative Filtering for Implicit Feedback

In content-aware collaborative filtering frameworks, in addition to users and items, their features are also represented as latent vectors in the joint latent space [Stern et al., 2009; Chen et al., 2012; Rendle, 2012]. Assuming users have F features and items have L features, the predicting preference of a user i for an item j is then formulated as ˆ ri↪j = (si +U0xi)0 (tj +V0yj), where U 2 RF⇥K is a latent matrix of user features and V 2 RL⇥K is a latent matrix of item features.

If the ids of both users and items are also considered features and encapsulated into ¶˜xi♦ and ¶˜yj♦, the predicting preference is simplified as ˆ ri↪j = ˜x0i ˜U˜V0 ˜yj, where ˜U 2 R(M+F )⇥K is obtained by concatenating ¶si♦ and U by rows ( ˜V shares a similar meaning). Then, as proposed in [Lian et al., 2015], the objective function is formulated as:

Although we can use gradient descent directly for optimization w.r.t ˜U and ˜V, it is more appealing to apply alternative least square due to the removal of the tuned learning rate. However, by simple algebra, we find the analytic solutions of latent vectors of different features are coupled and thus unable to compute efficiently. By rewriting the objective function, according to [Lian et al., 2015], the overall optimization can be split into two stages, i.e.,

The first stage learns summed latent vectors (i.e., pi , ˜U0 ˜xi and qj , ˜V0 ˜yj); the second stage learns the feature latent matrices, U and V. Both stages have analytical solutions.

3 Sparse Bayesian Content-Aware Collaborative Filtering for Implicit Feedback

Although user/item content can be incorporated by the above framework, it suffers from the following three problems. First, when deriving the analytical solution for the feature latent matrix, we discover the disadvantage of only using a single regularization coefficient λ. Second, the regularization parameters should be tuned carefully, otherwise this approach is prone to overfitting. Third, the relevance of different features should be differentiated from each other, and even some of them are fully irrelevant and should be discarded. To address these shortcomings, we introduce a sparse Bayesian learning algorithm, which places priors on the hyperparameters so that they can be learned directly without manually tuning. Due to the adaptive update of hyperparameters, automatic feature selection is naturally embedded within this framework.

3.1 Generative Model

Before introducing a sparse Baysian learning algorithm, we first generalize the above content-aware collaborative filtering framework as a probabilistic generative model. In particular, the preference ri↪j of the matrix R is independently generated by Gaussian distributions,

The prior distributions over the user/item latent factors are assumed to be Gaussian:

where λP and λQ are both precisions of Gaussian distributions, determining the importance of user/item features in learning interaction between users and items. On these two precisions, we place a Gamma distribution prior with shape a and rate b, to capture prior knowledge of feature importance. For convenience, we assume that λP and λQ are distributed over a logarithmic scale, as suggested in [Tipping, 2001].

The prior distributions over the latent matrix of user/item features are assumed to be matrix normal, conjugate priors:

↵U 2 RF+↪↵V 2 RL+ are vectors of non-negative hyperparameters governing the prior precision for each dimension of the feature latent matrix. Matrix normal distribution is a generalization of the multivariate normal distribution to matrixvalued random variables and described by a row based variance ⌃R and a column based variance ⌃C in addition to mean. The second order central moments of matrix normal distribution can be represented as E[(z - θ)(z - θ)0 ] = ⌃Rtr(⌃C) and E[(z - θ)0 (z - θ)] = ⌃Ctr(⌃R). Here, we don't explicitly place independent Gamma prior on ↵U and ↵V , since the improper prior (shape and rate parameter approaching to zero) could incur the maximal sparsity.

Due to the conjugation, we can directly marginalize them out, leading to matrix normal distributed user/item latent factors with zero mean and a content-dependent covariance. For example, the marginal distribution over user latent factors P has the following form:

where ⌃P = λ-1 P IM +XA-1 U X0 and AU = diag(↵U). In other words, the content information actually constrains the similarity of latent factors between users and between items. Therefore, if the content of two users/items is similar, in terms of a metric related to their normalized dot product, their latent factors should also be proximal in the latent space. However, different from previous work [Zhou et al., 2012], which assumed content-based similarity between users or between items is given in advance and thus independent to this generative model, this similarity metric is adaptive with the update of the parameter ↵U and naturally embeds the capability of feature selection. For example, when the prior precision ↵fU for the f th feature of user content increasingly approaches to infinity, its contribution in ⌃P (i.e., measuring the contentbased similarity) becomes smaller until it is fully neglected. Below, we will study how to learn hyperparameters under the framework of evidence maximization or type II maximum likelihood in addition to deriving the update formula of latent factors of users/items and their features. For convenience, we denote ¶P↪ Q↪ ↵U ↪ ↵V ↪ λP ↪ λQ♦ as ⇥ to learn.

3.2 Parameter Learning

Based on the generative model, combining Eq (7) and Eq (2) with prior distributions of λP and λQ, we can derive the following objective function:

Since each parameter for minimizing L(⇥) cannot be obtained in a closed form given other fixed, it is possible to directly exploit gradient descent based alternative least square for parameter learning, but it suffers from the difficulty of selecting an appropriate learning rate.

For the sake of learning parameters more efficiently and encouraging a sparse solution of the feature latent factors, we resort to Bayesian Occam's razor [MacKay, 1992], to obtain iterative re-estimation for the parameters and the hyperparameters. Bayesian Occam's razor approximates the evidence, e.g., Pr(P♣↵U↪ λP ) by Pr(P♣UMP↪ λP )Pr(UMP♣↵U)∆U. Since U follows the matrix normal distribution, such an approximation has an extract form. In particular, the extract form can be obtained by noting that

and expressing ♣⌃P ♣ as, using the matrix inversion lemma,

where ⌃-1 U = (λPX0X + AU) and UMP = λP⌃UX0P. Substituting Eq (9) and Eq (10) into Eq (8), and applying alternative least square for optimization, we can get update equations of each parameter in the set ⇥.

Below, we only study how to update user-related parameters because of the symmetry of the updating rules between user-related parameters (P↪ ↵U ↪ λP ) and item-related parameters (Q↪↵V ↪ λQ). In particular, computing the gradient of L(⇥) w.r.t pi and setting them to zero, we can obtain,

where Wi = diag([wi↪1↪ · · · ↪wi↪N]) and ri is the ith row of the preference matrix R. Thus, given Q fixed, the update of latent factor for each user is independent to other users, making it straightforward to update the latent factors for all users in parallel. Similarly, deriving the gradient of L(⇥) with respect to λP and ↵fU , and setting them to zero, we can obtain the updating formulas for them,

where ufMP represents the f th row of user feature latent matrix UMP and γ fU = 1 - ↵fU ⌃f↪f U , which is suggested in MacKay fixed-point update rules [MacKay, 1992]. The latter quantity γ fU ranges from zero to one, measuring how welldetermined its corresponding parameter uf by the user content. The γ fU of all user features are concatenated as a vector, then γU = diag(I - ⌃UAU) = λPdiag(⌃UX0X). The overall algorithm is given in Algorithm 1.

Due to tr(P0⌃-1 P P)  tr(λP (P-XU)0 (P-XU)) + tr(U0AUU) according to Eq (9), the derived updating rules actually optimize an upper bound of Eq (8) with an additional parameter U, which replaces the left-hand side of the inequality with the right-hand side. Thus, the convergence of the updating rules can be guaranteed according to the convergence study of alternative least square [Grippo and Sciandrone, 2000] and the convergence study of sparse Bayesian learning [Wipf and Rao, 2004].

3.3 Complexity Analysis

Applying the trick used in [Hu et al., 2008], the overall cost of computing user/item latent factors is O(kRk0K2 + (M + N)K3 ). Due to the independence of computation among different users/items, the actual cost can be reduced based on simple task parallel techniques. The total time complexity for computing UMP and VMP is O((kXk0 +kYk0)K#iter) since we can apply any iterative algorithm, such as conjugate gradient descent, for linear equations system, where #iter is the maximum number of iterations for convergence. The major cost in this algorithm is to compute the γU and γV , which requires O((kXk0F + kYk0L)#iter) in the worst case in total since it also involves solving linear equations system. In practical, the time complexity also depends on the sparse pattern of the feature matrices in addition to the number of non-zero entries, thus it is hard to determine time complexity exactly, but it is obvious that the algorithmwill be much more efficient when the feature matrices have special sparse structures. For the sake of more efficient parameter learning, we suggest performing dimension reduction, such as SVD and LDA, before feeding the feature matrices.

Algorithm 1: Sparse Bayesian Collaborative Filtering

Input : rating matrix R, dimension K of latent space, user feature matrix X, item feature matrix Y, confidence β for observed events, shape a and rate b of gamma prior

Output: user latent factor P and item latent factor Q

• 1 Initialize UMP, VMP with zero, and randomly initialize P and Q;

2 repeat

3 Update each user's latent factor based on Eq (11);

4 Update each item's latent factor similar to Eq (11);

5

6

7

8

repeat

Compute UMP and γU ;

Update λP based on Eq (12);

Update ↵U based on Eq (13);

9 until ↵U and λP is convergent;

10

11

12

13

repeat

Compute VMP and γV ;

Update λQ similar to Eq (12);

Update ↵V similar to Eq (13);

• 14 until ↵V and λQ is convergent; 15 until L(⇥) is convergent;

3.4 Induced Sparsity

In the case of the above setting, feature selection is naturally embedded in this framework. Let's inspect this property below, studying the marginal prior distribution over user feature factor U after marginalizing over the precision ↵U (↵U ⇠ Qf Ga(↵fU ♣c↪ d)). After an integral computation, we observe it follows an independent multivariate Student's t distribution, i.e. Pr(U♣c↪ d) = Qf T2c(uf ♣0↪ dc IK). This distribution is proportional to Qf ♣uf ♣-K 2 when c and d approach zero, encouraging a row-wise sparsity on U.

However, instead of marginalizing over U, the marginalization over the hyperparameters is not consistent with the proposed optimization algorithm. To this end, based on [Wipf and Nagarajan, 2008], we seek a tight upper bound of log ♣⌃P ♣ based on the concavity with respect to ↵-1 U = [1◁↵1U ↪ · · · ↪ 1◁↵FU ]. In particular, we can get

where g⇤ (z) is the concave conjugate of log ♣⌃P ♣ w.r.t ↵-1 U . Combining it with the upper bound of tr(P0⌃-1 P P), and optimizing over ↵U first, we can get ↵fU = pzf◁♣uf ♣ exactly. At this moment, tr(U0AUU), a part of the upper bound of tr(P0⌃-1 P P), can be rewritten as Pf pzf ♣uf ♣2. When all zf equal to one, it is just an `2↪1 norm for U. Since this procedure also optimizes over a variational parameter zfU , it actually corresponds to an adaptive `2↪1 regularization.

4 Experiments

We evaluated our model on three tasks, which recommends locations on location-based social networks, articles on researcher communities, and music on online music searching and browsing services. For the first task, we used self-crawled human mobility data from Jiepang, a Chinese location-based social network, and collected users' profiles from Sina Weibo (China's Twitter), since Jiepang users can log in with Weibo accounts. For the latter two tasks, we used public datasets, that is, the CiteULike dataset used in [Wang and Blei, 2011] and the Last.fm provided by [Celma, 2010], respectively. In these three datasets except CiteULike, we filtered items on which fewer than 10 users having actions (check-in, listening) and filtered users who have actions on fewer than 10 items. The CitULike dataset was kept unchanged to directly compare our model with the algorithm of [Wang and Blei, 2011]. The statistics after filtering are shown in Table 1. Based on three datasets, we performed 5-fold cross validation. For every user, we evenly split their user-item pairs into 5 folds. For each fold, we trained a model on other folds of data and tested it on the within-fold items for each user.

4.1 Metric

We evaluated the recommendation algorithms on sets of heldout observed entries. Presenting each user with the top k candidate items sorted by their predicting preference, we assessed recommendation performance by two widely used metrics, recall@k and precision@k [Wang and Blei, 2011]:

where Su(k) is the collection of top k recommended items for a user u and Vu is the set of the observed entries for her.

4.2 Competing Algorithms

We compared our model, named SBICCF, with the following five competing baselines on these three recommendation tasks. SBICCF was configured by manually tuning the confidence β of positive feedback. For location and article recommendation, β = 30; for music recommendation, β = 1. We can see that the latter β is much smaller than others, probably due to much higher density of the dataset.

1) Libfm [Rendle, 2012], supports classification and regression tasks, but requires drawing negative examples when being applied for recommendation on implicit feedback. We chose a MCMC-based training algorithm for avoiding manually tuning parameters. Based on empirical results, we used the regression task and sampled 10 times more negative items than positive ones for each user out of efficiency concern.

1. svdfeature [Chen et al., 2012], also requires negative item sampling but optimizes a ranking-based loss function. It doesn't support MCMC-based training algorithms but only leverages stochastic gradient descent, thus we should manually tune the regularization coefficients and the learning rate. We followed the same sampling strategy as Libfm.
2. HBF [Gopalan et al., 2015], a hierarchical Poisson-based matrix factorization, roots from non-negative matrix factorization, but places gamma priors on user/item factors. We used the source code in Github and followed the default settings for parameters.
3. WARP [Weston et al., 2010], a ranking-based matrix factorization, tries to optimize precision at the top position. We used a python package developed by Mendeley [Levy and Jack, 2013], where the parameters have been manually tuned. 5) ICF, a basis of SBICCF, without any feature provided, will illustrate the effect of features.

CTR [Wang and Blei, 2011] was also used for the comparison on article recommendation, but it was only designed for combining LDA-based topic modeling with ICF. Thus CTR cannot be considered a baseline of the other two tasks. Since the dataset for article recommendation was the same as CTR, we followed the same settings suggested in the paper. The dimension K of latent space was set to 200 in this case. However, in the other two tasks, K was set to 50.

4.3 Results and Discussions

The overall experimental results of these three tasks are shown in Figure 1. We have the following observations.

First, the proposed algorithm, i.e., SBICCF, outperformed Libfm and svdfeature by a significant margin. This may arise from downweighting the negative preference compared with the positive preference and getting rid of negative sampling. Although svdfeature optimizes a ranking-based loss function and achieves the goal of downweighting negative preference, it doesn't directly target top-k based recommendation metrics. Besides, svdfeature always places the same regularization on the latent factor of items as their features, as shown in Eq (1), so that the regularization of latent factors of item features can not be well controlled.

Second, ICF was significantly better than WARP and HBF. This indicates ICF was still the best choice for collaborative filtering for implicit feedback, at least from the perspectives of the current empirical results. Although WARP directly optimizes the precision at the top position, it exploits the approximation techniques and never converges to the optimal solution. Moreover, it suffers from the computational issues, and becomes more severe with increasing predictive power, just as described in [Li et al., 2015]. Although HBF also downweights the effect of negative preference by an appropriate fit to user activity (i.e., the size of consumed items) so as to capture the diversity of users and the diversity of items, it was only slightly better than the model (i.e., BPF) without downweighting. In other words, their modeling approach didn't show the strong benefit of downweighting, i.e., the varying conference for positive and negative preference,

• (d) Location recommendation (precision)

(e) Article Recommendation (precision)

(f) Music Recommendation (precision)

Figure 1: Comparison among different models on three implicit feedback datasets.

which is slightly different from what has been concluded by [Hu et al., 2008]. However, we can still observe its superiority in some cases to other baselines.

Third, SBICCF was slightly better than CTR. The difference of SBICCF from CTR on article recommendation is that before the addition operation it also maps each topic into the latent space and adds them in the mapped space, i.e., (tj + V0✓j v.s. tj + ✓j). The linear mapping matrix V was learned for aligning topics with items, so that it may learn no more knowledge than the case without aligning, i.e., CTR. However, SPICCF is more general and flexible than CTR since there is no constraint that the number of topics should be the same as the dimension of the latent space.

Last, SBICCF was better than ICF when features were effective. For the tasks of location recommendation and article recommendation, we observed that features played a very important role in improving recommendation, especially for the long tail items. This is not only because SBICCF can determine the relevance automatically but also directly drop irreverent features. For example, in the case of location recommendation, categories such as "my home" and "private place" were determined as irrelevant and directly removed, probably because these categories didn't take any useful information. However, for article recommendation, we found that sparse Bayesian learning in this case almost didn't discover any irrelevant features but only learned the individual contribution of topics. This may be because dimension reduction was performed first so that lots of noises and information with small variances were discarded. For music recommendation, there was no significant improvement, probably due to only a small amount of available user profile information and high density of the Last.fm dataset. When there were sufficient training data for each user, their latent factor can be well learned.

5 Conclusion and FutureWork

In this paper, we proposed a sparse Bayesian content-aware collaborative filtering algorithm best tailored to implicit feedback, and developed a scalable optimization algorithm for jointly learning latent factors and hyperparameters. The developed model was not only capable of determining the relevance of each feature but also automatically tuning the regularization coefficients. In theory, we showed that the designed model was equivalent to imposing an adaptive `2↪1 norm on feature latent matrices; and in practical, we observed that it successfully pruned non-informative features. We evaluated the proposed model on three implicit feedback datasets, and showed its consistent superiority to several state-of-the-art content-aware recommendation algorithms.

However, in this framework, each dimension of latent space is assumed independent to each other. Modeling their correlation may lead to some advantages, as shown in [Salakhutdinov and Mnih, 2008], and this goal can be easily achieved based on matrix normal distributions. Although the developed algorithm is capable of pruning noninformative features, it doesn't directly measure the informativeness of each feature. Defining an appropriate metric for the informativeness of features will have significant and practical values, thus it will be studied in a future work.

Acknowledgments

This research was supported by grants from the Natural Science Foundation of China (61502077) and the Fundamental Research Funds for the Central Universities(ZYGX2014Z012, ZYGX2015KYQD018).