Hierarchical Bayesian Matrix Factorization with Side Information

1 Introduction

Matrix factorization refers to a method for uncovering a lowrank latent structure of data, approximating the data matrix as a product of two factor matrices. Matrix factorization is popular for collaborative prediction, where unknown ratings are predicted by user and item factor matrices which are determined to approximate a user-item matrix as their product [Rennie and Srebro, 2005; Salakhutdinov and Mnih, 2008b; Lim and Teh, 2007; Raiko et al., 2007; Tak´acs et al., 2009; Koren et al., 2009; Singh and Gordon, 2010].

Suppose that X ∈ RI×J is a user-item rating matrix, the (i, j )-entry of which, Xij, represents the rating of user i on item j. Matrix factorization determines factor matrices U = [u1, . . . , uI] ∈ RK×I and V = [v1, . . . , vJ] ∈ RK×J (where K denotes the dimension of latent space), to approximate the rating matrix X by U ⊤V :

A popular approach is to minimize the regularized squared error loss defined as

where Ω is a set of indices of observed entries in X, and λ is the regularization parameter. Although this works even on large-scale datasets [Tak´acs et al., 2009; Koren et al., 2009], it is prone to overfitting on the training data and require careful tuning of regularization parameter and the number of optimization steps.

Bayesian treatment of matrix factorization successfully alleviates the overfitting problem by integrating out all model parameter, thus allowing for complex models to be learned without requiring much parameter tuning [Lim and Teh, 2007; Raiko et al., 2007; Salakhutdinov and Mnih, 2008a; Yoo and Choi, 2011; 2012; Kim and Choi, 2013]. In practice, however, Bayesian matrix factorization still suffers from cold-start problem, where inferences are required for users or items about which a sufficient number of ratings are not gathered. The cold-start problem commonly occurs in practical recommendation system based on collaborative prediction because new users or items are continuously added into the system. Moreover users usually do not rate unpopular items, thus these items will be fixed in long-tail part for a long time but for effective recommendation. To resolve the cold-start problem, it is crucial to use side information, such as user demographic information and item content information.

In this paper we present a method for Bayesian matrix factorization with side information, to handle cold-start problems. To this end, we place Gaussian-Wishart priors on mean vectors and precision matrices of Gaussian user and item factor matrices, such that mean of each prior distribution is regressed on corresponding side information. We develop variational inference algorithms to approximately compute posterior distributions over user and item factor matrices. In addition, we provide Bayesian Cram´er-Rao Bound for our model, showing that the hierarchical Bayesian matrix factorization with side information improves the reconstruction over the standard Bayesian matrix factorization where the side information is not used. Experiments on MovieLens data demonstrate the useful behavior of our model in the case of coldstart problems.

2 RelatedWork

We briefly review several matrix factorization models which incorporates side information. Suppose that side information is given in the form of feature matrices F = [f1, ..., fI] ∈ RDu×I and G= [g1, ..., gJ] ∈ RDv×J , where fi and gj are feature vector related with user i and item j respectively.

Matrix co-factorization is one one of efficient ways to exploit the side information. Matrix co-factorization jointly decomposes multiple data matrices, where each deposition is coupled by sharing some factor matrices [Singh and Gordon, 2008]. For example, rating matrix X, user side information matrix F and item side information matrix G are jointly decomposed as

where factor matrices U and V are shared in the first two and last two decompositions, respectively and EF , EX , EG represents Gaussian noise which reflect uncertainties. Recently Bayesian treatment of matrix co-factorization was developed, where the inference was performed using a sampling method [Singh and Gordon, 2010] or the variational method [Yoo and Choi, 2011; 2012].

In contrast to matrix co-factorization model, Regressionbased Latent Factor Model (RLFM) [Agarwal and Chen, 2009] assumes that the user and item factor matrices are generated from the side information via linear regression,

and then rating matrix X is generated by (1). More precisely, RLFM place isotropic Gaussian priors on user and item factor matrices U and V where mean of each prior is regressed on corresponding side information (see Figure 1-(b)),

Baseysian matrix factorization with side information (BMFSI), proposed in [Proteous et al., 2010], also utilizes side information via regression but it is differentiated from RLFM. In BMFSI model, the regression coefficient and side information are augmented in factor matrices such that the rating matrix X is estimated by the sum of the collaborative prediction part and regression part against side information:

Moreover BMFSI utilizes user-item specific features such as N ratings for item j, given by N nearest-neighborhoods of user i, which is not considered in matrix co-factorization and RLFM.

3 Model and Inference

In this section we present our hierarchical Bayesian modeling for matrix factorization which utilizes side information and explain how to our model brides Bayesian matrix factorization (BMF) [Salakhutdinov and Mnih, 2008a] and RLFM. We develop a variational inference algorithm to approximately compute the posterior distributions over factor matrices and provide rating prediction procedures for hold-out and fold-in cases also in the variational inference framework.

3.1 Hierarchical BayesianModeling

The graphical model representing our hierarchical Bayesian matrix factorization with side information (HBMFSI) is shown in Figure 1-(c). At first, the observed data Xij is assumed to be generated by a sum of inner product of latent factors, bias terms regressed on the feature vectors, and noise:

for (i, j ) ∈ Ω, where Ω is a set of indices of observe entries in X. The uncertainty in the model is absorbed by the noise Eij which is assumed to be Gaussian, i.e., Eij ∼ N(Eij | 0, ρ-1 ) where ρ is the precision (the inverse of variance). Thus, the likelihood is given by

The prior distributions over factor matrices U and V are assumed to be Gaussian:

where Θu = {{mi}Ii=1 ,Λu} and Θv = {{nj}Jj=1 ,Λv}. We further place Gaussian-Wishart priors on the Θu = {{mi}Ii=1 , Λu} and Θv = {{nj}Jj=1 , Λv}:

and finally place Gaussian priors on regression coefficient matrices A ∈ RDu×K , B ∈ RDv×K and vectors a0 ∈ RDu , b0 ∈ RDv :

The marginal log-likelihood log

where Jensen's inequality was used to obtain the variational lower-bound F(q) and q(Z ) is variational distribution that is assumed to be factorized:

Variational posterior distributions q∗ (·), are determined by maximizing variational lower-bound F(q), leading to

where the expectation is taken with respect to the variational distributions over all variables excluding Z. Variational posterior distributions and corresponding updating equations for all latent variables Z ∈ Z are summarized in Table 1.

We use the empirical Bayes estimation to update hyperparameters {ρ, m0, n0, T 0u , T u, T 0v , Tv}. Setting derivatives of the variational lower-bound F(q) to zero yields the updating equations for hyperparameters:

where

and

where the precision matrices Tu, T 0u ∈ RDu×Du and T 0v , Tv ∈ RDv×Dv are assumed to be diagonal.

In standard BMF (Figure1-(a)), means of the GaussianWishart priors, m and n, are shared for all users and items and they generated from the non-informative constant vectors, m0 and n0, which are trivially set to zero. However our HBMFSI places individual means for Gaussian-Wishart priors, {mi}Ii=1 and {nj}Jj=1 , by associating with corresponding side information via regression:

Note that HBMFSI can be reduced to RLFM (Figure 1-(b)) if we marginalize out {mi}Ii=1 and {nj}Jj=1 by using the property of the linear Gaussian model. After marginalization, the conditional distributions over factor matrices U and V become

where γ = γ0/(γ0 + 1). These conditional distributions are equivalent to priors over factor matrices in RLFM (4, 5), provided that m0 = n0 = 0 and precision matrices, Λu and Λv, are set to isotropic.

3.2 Variational Inference

We approximately computes posterior distributions over factor matrices by maximizing a lower-bound on the marginal

and where Z is the set of latent variables defined in (20). We approximate the predictive distribution (34) by maximizing a lower-bound on marginal log-posterior p(xi+|X):

Variational distribution ˜ q(ui+ , Z ) is assumed to be factorized:

where ˜ q∗ (Z ) is fixed to the pre-trained variational distribution in Table 1. For given pre-fixed ˜ q∗ (Z ), the optimal variational posterior ˜ q∗ (ui+) maximizing (35) is computed with single update,

yielding to Gaussian distribution such that

where

for d = 1, . . . ,Du and

for d = 1, . . . , Dv.

3.3 Prediction

We consider two kinds of prediction tasks in the collaborative filtering: hold-out prediction and fold-in prediction. In the hold-out prediction, we aim to predict a missing entry Xio ,j o in the rating matrix X, where (io , j o ) /∈ Ω. To do this, we simply make use of the posterior means of each variable:

In the fold-in prediction, we want to predict the rating value of a new user or new item. We assume that a user i+ is newly added into the system and some rating entries xi+ made by the user i+ are available. Then the prediction of an unknown entry of the user i+ can be made similarly to (32):

where 〈ui+〉 is a mean of the predictive distribution over a new factor ui+ given xi+, which can be defined by

Thus the prediction of unknown rating entry of the new user, Xi+,j can be made based on (33) and (38):

The aforementioned prediction method can be similarly applied to predict missing ratings in the presence of a new item.

4 Bayesian Cram´er-Rao Bound

Motivated by [Yoo and Choi, 2011], we provide Bayesian Cram´er-Rao Bound for our model, showing that our HMBFSI improves the reconstruction over the standard BMF where the side information is not used.

The Bayesian Cram´er-Rao bound or Posterior Cram´er-Rao bound places a lower bound on the variance of any parametric estimator [Tichavsky et al., 1998], as the inverse of the Fisher information matrix F, which is written by,

where θ(x) is the estimate of the θ. Each element of the Fisher information matrix is defined by

where p(x, θ) is the joint probability between the observations and the parameters. The benefit of using BCRB over classical Cram´er-Rao bound is that the BCRB is known to provide a lower bound on the variance of any parametric estimators, even for the unbiased ones [Tichavsky et al., 1998].

To compute the BCRB for HBMFSI, we rearrange the factor matrices and other parameters to be a vector form:

Each element of the Fisher information matrix is computed as (42). The second derivatives of the log joint probability with respect to elements of factor matrices are given by

In standard BMF where side information is not used, if we set m0, n0 to zero vector and W0 to an identity matrix as in [Salakhutdinov and Mnih, 2008a], the most of the expectation above second derivatives are vanished and only nonzero values come from the differentiating with the same parameter,

hence the Fisher information matrix becomes diagonal.

The Fisher information matrix of HBMFSI is also diagonal but larger than (44) because of extra term involved with side information,

hence has lower BCRB (the inverse of the fisher information matrix) and also lower reconstruction error [Yoo and Choi, 2011].

5 Numerical Experiments

We evaluated the proposed HBMFSI for the collaborative prediction problem in both warm-start and cold-start situations, and compared the performance with that of BMF [Salakhutdinov and Mnih, 2008a], BMCF [Yoo and Choi, 2012], BMFSI [Proteous et al., 2010] and RLFM [Agarwal and Chen, 2009] to show the benefit of the HBMFSI.

Datasets: We conducted experiments on two MovieLens datasets: MovieLens-100K, which consists of 100K ratings with 943 users and 1682 movies, and MovieLens-1M, which consisits of 1M ratings with 6040 users and 3706 movies. MovieLens datasets provide side information for both users and items. The user information which consists of the user's age, gender and occupation was encoded into a binary valued vector with length 28. Similarity, the item information which consists of the 18 category of movie genre was ecoded into a binary valued vector with length 18. Ratings were normalized to be zero-mean.

Evaluation Metris: The performance of the collaborative predction algorithm was evaluated in terms of the widely used root mean squared error (RMSE) defined by RMSE = √ 1N ∑Ni=1 (xi - ˆxi)2 , and mean absolute error (MAE) defined by MAE = 1N ∑Ni=1 |xi - ˆxi|, where N is the total number of test data points, xi and ˆxi are the true rating and predcited rating of the i-th test data, respectively.

Model Training: Because each model was trained by different inferece algortihm such as Markov Chain Mornte Carlo (BMF, BMFSI), Monte Carlo Expectation Maximization (RLFM), and the variational method (BMCF, HBMFSI), it is difficult to directly compare the effectiveness of the modeling for side information. For this reason, we decided to train all models by the variational method. We set the latent dimension K to 10 (compare to the Netflix data, relatively small K is sufficient for MovieLens datasets), and hyperparameters of Gaussian-Wishart priors to ν0 = K, γ0 = 1 andW0 = I.

Warm-start Performance: Firstly we investigate the predictive performance on the common warm-start situation with MovieLens-1M data. The data is randomly split around 50% taring and 50% test. Experiments are repeated ten times, and we report their averages and standard deviations in Table 2. We confirmed that HBMFSI outperforms other methods in terms of both MAE and RMSE. Interestingly, BMFSI and BMCF showed slightly worse performance than BMF, even though side information is utilized. In the case of BMFSI, similar result was reported in [Proteous et al., 2010], where movie metadata which extracted from Wikipedia (e.g. movie director, actors, languages) do not improve performance measured by RMSE in Netflix Prize data.

Cold-start Performance: Next we investigate the predictive performance on the cold-start situation with MovieLens100K data. We considered the cold-start problems which can occur in the hold-out prediction (prediction of missing ratings of the existing users) and also in the fold-in prediction (prediction of unknown ratings of the new users).

In the case of hold-out prediction, we randomly select 20% ratings as the test data and train each model on ten taring sets, which consist of 10%, 20%,. . .,100% of the remained ratings. In the case of fold-in prediction, we randomly divide the users into two sets: a test set containing 20% of the users and training set containing the rest of the users. First each model is trained on all ratings by the training users. For each of the test users we train the model varying with the number of given ratings from 0 to 20 according to the procedure outlined in Section 3.3. Experiments are repeated ten times for both hold-out and fold-in predictions.

Figure 2 shows that HBMFSI outperforms BMF both in hold-out and fold-in prediction. Especially HBMFSI significantly improves the performance in fold-in prediction which reflects practical cold-start situation more than hold-out prediction. Experimental results also showed that side information modeling used in RLFM and HBMFSI, where side information is used to modeling the means of priors over factor matrices is more efficient to utilize side information than other methods including BMCF and BMFSI. Finally HBMFSI showed slightly better performance than RLFM, which is a special case of our model.

6 Conclusions

We have presented hierarchical Bayesian matrix factorization with side information, to handle cold-start problems. We used side information to properly regularize user and item factor matrices by placing Gaussian-Wishart priors on mean vectors and precision matrices of Gaussian user and item factor matrices, such that mean of each prior distribution is regressed on corresponding side information. We developed variational inference algorithms to approximately compute posterior distributions over user and item factor matrices. In addition, we provided Bayesian Cram´er-Rao Bound for our model, showing that the hierarchical Bayesian matrix factorization with side information improves the reconstruction over the standard Bayesian matrix factorization where the side information is not used. Experiments on MovieLens data demonstrated the useful behavior of our model in the case of coldstart and also warm-start problems.

7 Acknowledgments

This work was supported by National Research Foundation (NRF) of Korea (2012-0005032), NIPA ITRC Support Program (NIPA-2013-H0301-13-3002), POSTECH Rising Star Program, and NRF World Class University Program (R3110100).