Bayesian Probabilistic Multi-Topic Matrix Factorization for Rating Prediction

1 Introduction

Nowadays, recommender systems have played a more and more important role in e-commerce services. A typical task for personalized recommendation is rating prediction which predicts the rating of a user on a given item based on her historical data. Various methods have been proposed in the literature of rating prediction, especially the matrix factorization technique (MF) [Koren et al., 2009]. MF projects users and items into a latent low-dimensional space. Further, the missing entries in the original matrix can be recovered using the dot product between user and item latent vectors. MF has been shown to perform well in many real systems and competitions, such as Netflix Prize and KDD Cup 2011 Recommending Music Items.

⇤Corresponding author

Recently, local matrix factorization [Lee et al., 2013] has been shown to be more effective than the traditional MF. The original matrix is divided into several smaller submatrices, in which we can exploit local structures for better low-rank approximation. In each submatrix, the standardMF technique is applied to generate submatrix-specific latent vectors for both users and items. Typically, these submatrices are obtained using cluster techniques. By combining the results frommultiple local MFs, the original matrix R is reconstructed by a set of K low-rank submatrices ¶R(1) ↪R(2) ↪ ▷▷▷↪R(K) ♦ with the corresponding weight matrices ¶L(1) ↪ L(2) ↪ ▷▷▷↪ L(K) ♦:

where Zum = PKk=1 L(k) um is the normalizer and L(k) um indicates the weight for the entry R(k) um in the submatrix R(k) . Two key issues of such a submatrix-ensemble method are (1) how to generate the submatices and (2) how to set the ensemble weights for submatrices. Several attempts have been made to address these two points, using random sampling [Mackey et al., 2011], extending anchor points with nearest neighbors [Lee et al., 2013; 2014] or co-clustering based matrix partition [Chen et al., 2015].

Although these studies have improved over tradition MF to some extent, there is lack of a more principled approach to characterize the local matrix factorization. By reviewing previous studies [Mackey et al., 2011; Lee et al., 2013; 2014; Chen et al., 2015], we have two important observations: (1) Each submatrix can be considered as a local cluster of users and items; (2) A user or an item has multiple latent representations in different submatrices. Inspired by these two observations, we propose a novel Bayesian Probabilistic MultiTopic Matrix Factorization model (BPMTMF) for rating prediction. Our model consists of two parts, namely modeling the rated items and modeling the ratings. For the first part, we treat the set of the rated items by a user as a document, and latent topic models are employed to "cluster" items as topics, which is a multinomial distribution over the set of items. Subsequently, a user has a distribution (i.e., topical distribution) over the set of topics. Based on such topics, we further set topic-specific latent vectors for both users and items. We integrate the above two parts in a full Bayesian approach. The final prediction by our model is an ensemble of the results generated from the topic-specific latent vectors in each topic. Our model characterizes the core ideas in Eq. 1 in a Bayesian probabilistic way: each topic can be considered as a cluster. Using a multi-topic latent representation, our model is more powerful to reflect the complex characteristics for users and items in rating prediction. Another important merit of using topics is that our approach has a better model interpretability. Since topic models are effective to discover coherent topical semantics [Blei et al., 2003], the derived topics in our model also group the items that are highly correlated together. In this way, a topic will be more coherent than what have been obtained in previous studies [Mackey et al., 2011; Lee et al., 2013; 2014; Chen et al., 2015]. With topics as contextual information, we can analyze how the rating preference of a user varies in different topical contexts.

Our work presents a Bayesian formulation of local matrix factorization for the first time, which elegantly combines topic models with probabilistic matrix factorization models. By using topics as clusters, our approach has a better model interpretability. Extensive experiments on large real-world datasets demonstrate the effectiveness of the proposed model compared with several competitive baselines.

2 RelatedWork

In this section, we review the related work.

Matrix Factorization. MF [Paterek, 2007; Mnih and Salakhutdinov, 2007; Koren et al., 2009] is an important kind of model-based collaborative-filtering methods. MF constructs low-rank approximation by projecting users and items into a latent low-dimensional space. Further, Probabilistic Matrix Factorization (PMF) has been proposed by using the Gaussian distribution to model observed ratings with zero-mean spherical Gaussian priors. In essence, PMF can be considered as a probabilistic realization of Regularized Singular Value Decomposition. Further, Salakhutdinov and Mnih [Salakhutdinov and Mnih, 2008] presented a full Bayesian formulation of PMF. As the extensions of MF, biased MF and SVD++ have been proposed in [Koren et al., 2009]. Biased MF incorporates both user bias and item bias, while SVD++ uses implicit feedback to improve user preference modeling.

Local Matrix Factorization. Recently, several studies focus on using the ensemble of submatrices for better lowrank approximation, including DFC [Mackey et al., 2011], LLORMA [Lee et al., 2013; 2014], ACCAMS [Beutel et al., 2015] and WEMAREC [Chen et al., 2015]. These methods partition the original matrix into several smaller submatrices, and a local MF is applied to each submatrix individually. The final predictions are obtained using the ensemble of multiple local MFs. Typically, clustering-based techniques with heuristic adaptations are used for submatrix generation. We give a brief review of these studies. Mackey et al. [Mackey et al., 2011] introduces a Divide-Factor-Combine (DFC) framework, in which the expensive task of matrix factorization is randomly divided into smaller subproblems. LLORMA [Lee et al., 2013; 2014] uses a non-parametric kernel smoothing method to search nearest neighbors; WEMAREC [Chen et al., 2015] employs Bregman co-clustering [Dhillon et al., 2003] techniques to partition the original matrix; ACCAMS adopts an additive co-clustering approach [Shan and Banerjee, 2008] to derive sub-matrices and predict the ratings using a Gaussian distribution. Our work is highly built on the above studies, however, we propose to use probabilistic topic models to create "soft" clusters, further develop a full Bayesian model by integrating topic models with probabilistic MF.

Matrix Factorization with Topic Models. In the literature, researchers have made several attempts to combine topic models with MF, including CTM [Wang and Blei, 2011], HFT [McAuley and Leskovec, 2013], and ETF [Zhang et al., 2014]. However, these methods mainly aim to incorporate ratings into topic models, and focus on combining the merits from both kinds of models. Typically, a single MF component is used, which is not suitable for local MF.

3 Bayesian Probabilistic Multi-Topic Matrix Factorization

In this section, we present our model BPMTMF for rating prediction. A glossary of notations used in the paper are listed in Table 1. In what follows, we denote matrices by bold capital letters. Superscripts, such as in P(k) , denote different topics' matrices for different superscripts; Subscripts on matrices denote the indices of data. For example, Rum denotes the entry in the u-th row and m-th column of the k-th topic matrix.

3.1 The ProposedModel

Our main idea is to construct clusters over items using topic models, and predict the rating using the ensemble of multiple topic-specific probabilistic matrix factorizations. Hence, our model consists of two parts: modeling the rated items and modeling the ratings.

Modeling the Rated Items. To model rated items, we adopt a similar approach following standard topic models (e.g., Latent Dirichlet Allocation [Blei et al., 2003]) by making the following analogy: an item is considered as a word token while the set of rated items by a user is considered as a document. In this way, a topic (i.e., item topic) is defined as a multinomial distribution over the set of items. Let φk denote the k-th topic and φk↪m denote the probability of the m-th item in the k-th topic. Given a set of K topics, the user preference is modeled as a multinomial distribution over them. Let ✓u denote the topical distribution of the u-th user and ✓u↪k denote the probability of the k-th topic in the topical distribution of the u-th user. We employ symmetric Dirichlet priors Dir(↵) and Dir(β) (with the hyper-parameters of ↵ and β) on ✓ and φ respectively. The topic modeling is used to generate the set of rated items for users as follows

where a pair hu↪mi indicates that the u-th user has rated the m-th item. Eq. 2 enumerates all such pairs in the dataset.

Modeling the Ratings. To model ratings, topics are considered as contextual information, further a user or item is associated with a topic-specific latent vector for each topic. Let P(k) u 2 RD (or Q(k) m 2 RD ) denote the topic-specific latent vector for the u-th user (or the m-th item) w.r.t. the k-th topic. We assume that a user will reflect different rating behaviors in varying topical contexts, and an item will show different rated patterns by users in varying topical contexts. For example, a user is a fan of "Star War", who is likely to give high ratings to the movies of "Star Wars Episodes" but low ratings to other action movies. Note that simply incorporating a categorical bias like in [Mirbakhsh and Ling, 2013; Hu et al., 2014] will not solve the issue in the above example, since the user give both high and low ratings in the same "Action" category. Our model tries to capture the personal impact of topical contexts on users' rating process. To draw topic-specific latent vectors, we employ Gaussian-Wishart priors on latent vectors P(k) and Q(k) with the parameters of (k) P = ¶θ(k) P ↪⇤(k) P ♦ and (k) Q = ¶θ(k) Q ↪⇤(k) Q ♦ as follows:

where ⌫ (k) 0 is the degrees of freedom of Wishart distribution W(k) , W(k) 0 is the scale matrix 2 RN⇥N for user (or 2 RM⇥M for item) and (k) 0 = ¶θ(k) 0 ↪ ⌫ (k) 0 ↪W(k) 0 ♦ for the k-th topic. Given the k-th topic, a rating Rum is generated according to a Gaussian distribution

1. For each topic k = 1↪ ▷▷▷↪K,
2. Draw a multinomial distribution φk ⇠ Dir(β)
3. Draw the hyperparameters of the topic-specific user and item latent vectors P( (k) P ♣ (k) 0 ) and P( (k) Q ♣ (k) 0 )
4. For each itemm= 1↪ ▷▷▷↪M,
5. For each topic k = 1,...,K, draw the topic-specific item latent vector Q(k) m ⇠ P(Q(k) m ♣ (k) Q )
6. For each user u = 1↪ ▷▷▷↪N,
7. Draw ✓u ⇠Dir(↵)
8. For each topic k = 1↪ ▷▷▷↪K, draw the topic-specific user latent vector P(k) u ⇠ P(P(k) u ♣ (k) P )
9. For each rated itemm by u
10. Draw a topic z ⇠ Disc(✓u)
11. Draw the rating Rum ⇠ N(Rum♣P(z) u >Q(z) m ↪ σ2 z )
12. Drawm⇠Disc(φz)

Figure 1: The generative process of the BPMTMF model.

where the mean and variance are set to P(k) u >Q(k) m and σ2 k respectively.

The Final Model. Our proposed model, called BPMTMF, integrates the above two components, i.e., the modeling of rated items (Eq. 2) and the modeling of ratings (Eq. 4), in a full Bayesian approach. We present the generative process of BPMTMF in Fig. 1. We use item topics to connect these two components, i.e., using topic-specific latent vectors. The generative story can be described as follows. When the u-th user wants to rate the m-th item, she first draws a topic assignment of z according to her topical distribution ✓u. Then the m-th item is generated using φz. Finally the rating is generated based on the latent vectors P(k) u andQ(k) m corresponding to the k-th topic. Given the hyper-parameters, the likelihood over all ratings is as below

Note that setting topic-specific latent vectors itself will increase the hazard of overfitting, while our Bayesian approach is effective to control the model complexity via using hyperpriors. Although we incorporate more hyper-parameters, as shown in BPMF [Salakhutdinov and Mnih, 2008] and our empirical results, the performance is relatively insensitive to the selection of hyper-parameters.

3.2 Model Learning with a Collapsed Gibbs Sampler

In our model, the parameters (or variables) to learn are listed as follows: users' topical distributions ¶✓u♦, item topics ¶φk♦, users' latent vectors ¶P(k) u ♦ and items' latent vectors ¶Q(k) m ♦. Our task is to learn the parameters ¶✓↪ φ↪P↪Q♦ to maximize the likelihood of observing rating matrix R. It is difficult to directly optimize such an objective function due to the complex coupling of parameters and hidden variables. We adopt the commonly used Gibbs sampling algorithm [Andrieu et al., 2003] for both inference and parameter learning. In each iteration, we alternatively infer topic assignments and update the topic-specific latent factors ¶P(k) u ♦ and ¶Q(k) m ♦. When the algorithm converges, we can estimate ¶✓u♦ and ¶φk♦ using the topical assignments.

Inferring Topic Assignments. Fixing all topic-specific latent vectors and the hyper-parameters, we can derive the conditional distribution for a data entry i = hu↪ mi as below

where nku denotes the number of items rated by the u-th user with the k-th topic, nkm denotes the number of users who rate the m-th item with the k-th topic, and the rating Rum is generated by the probability of N(Rum♣P(k) u >Q(k) m ↪ σ2 k ) using the latent vectors corresponding to the k-th topic. Actually, the sampling equation is similar to the derivations for standard LDA models in [Heinrich, 2005] except that we incorporated the generation of ratings.

Updating Topic-specific Latent Vectors. The process of updating topic-specific latent factors is similar to the original Bayesian Probabilistic Matrix Factorization (BPMF) [Salakhutdinov and Mnih, 2008]. The difference lies in that we assume the topic assignment for each rated item is given, then the updating is performed on the corresponding topic-specific latent vectors. The conditional distribution over users' topic-specific latent vectors P(k) u is a Gaussian distribution:

in which we have

where I(k) um is an indicator value which is equal to 1 only when the topic assignment zu↪m = k. We can learn items' latent vectors ¶Q(k) m ♦ similarly, which are omitted here.

The Overall Learning Algorithm. In Alg. 1, we present the overall Gibbs sampling learning algorithm [Andrieu et al., 2003] for the BPMTMF model. At the beginning, we use BPMF to initialize topic-specific latent vectors P and Q. In each iteration, we first sample the topic assignments for all the observed data entries, then update P and Q with topic assignments fixed. After burn-in periods, we can estimate the parameters of ¶✓u♦ and ¶φk♦ using a simple counting method for each iterative

where nku , nju , nkm and nkh are the counts defined in Eq. 6.

Computational Complexity Analysis. Let S be the total number of non-zero observations in R, and nku↪· = Pm I(k) um defined in Eq. 10. In an iteration, the running time for updating topic assignments is roughly O(KDS). For updating users' latent vectors, the cost mainly comes from the computation of PMm=1 (Q(k) m Q(k) m >)I(k) um (Eq. 8) and the matrix inverse for ⇤(k) u ⇤ (Eq. 9), which take the costs of O(D2n(k) u↪· ) and O(D3 ) respectively. Here, we assume that it requires O(D3 ) time for the RD⇥D matrix inversion even though more efficient algorithms exist [Hu et al., 2008]. Hence, updating ⇤(k) u ⇤ and θ(k) u ⇤ takes a cost of O(D3 +D2n(k) u↪· ). Enumerating N users and K topics, it takes a cost of O(D3KN+ D2S) with S = Pu↪k nku↪· . Similarly, updating items' latent vectors takes a cost of O(D3KM+D2S). To sum the above parts, the cost of an iteration is O(DKS +D2S +D3KN + D3KM).

3.3 Rating Predictions

When all the parameters of BPMTMF are learnt, we can use the following formula for rating prediction

where ˆRum is the predicted value for Rum. The above prediction uses only a single Gibbs sample, which can be simply extended to average the results from multiple samples.

Connections with Previous Studies. Eq. 1 presents a general formulation for previous studies on non-probabilistic local matrix factorization [Mackey et al., 2011; Lee et al., 2013; Chen et al., 2015]. Interestingly, our prediction formula

(Eq. 11) has a close connection with Eq. 1. Given a pair of hu↪mi, we can have the corresponding mappings: P(k) u >Q(k) m ! ˆR(k) um indicating the predicted value for Rum in the k-th "cluster", ✓u↪k ·φm↪k ! L(k) um indicating the weight for ˆR(k) um, and PKk0=1 ✓u↪k0 · φm↪k0 ! Zum playing the role of the normalizer. With such an analogy, our formula can be considered as a probabilistic realization of previous nonprobabilistic methods: a cluster in Eq. 1 is essentially a topic in our approach. Such a connection sheds lights on that previous studies can be explained in a probabilistic way with more deep theoretical analysis and extensions.

4 Experiments and Analysis

4.1 Experimental Setup

Datasets. We evaluate themodels on the two publicly available movie datasets Movielens 1 and Netflix 2 described in Table 2. We randomly split the data into training set and testing set with the ratio 9 : 1. The final results are reported by the average of five such runs.

Evaluation Metrics. We adopt the commonly used Root Mean Square Error (RMSE) to evaluate the predictive accuracy, defined by:

where Ntest is the number of ratings in test set. A smaller value of RMSE indicates a better performance.

Comparison Methods. We compare the proposed BPMTMF with following baselines.

• ÷ DFC [Mackey et al., 2011]: divides a large-scale matrix factorization task into smaller subproblems, and uses the techniques from randomized matrix approximation to combine the subproblem solutions.
• ÷ LLORMA [Lee et al., 2013]: uses non-parametric kernel smoothing to develop local low-rank approximation and aggregate several submatices into unified matrix approximation.
• ÷ WEMAREC [Chen et al., 2015]: constructs submatrices via partitional co-clustering and proposes a submatrixbased weighting strategy to predict the final ratings.
• ÷ PMTMF: As a direct comparison of our Bayesian approach, we also implement a non-Bayesian Probabilistic Multi-Topic Matrix Factorization, which does not have any prior parameters. Expectation-Maximization algorithm is employed for optimization.

We do not use traditional MF methods [Mnih and Salakhutdinov, 2007; Koren et al., 2009] as baselines here, since previous studies [Mackey et al., 2011; Lee et al., 2013; Chen et al., 2015] have shown that the above local MF methods have outperformed the traditional MF methods. We implement our methods PMTMF and BPMTMF based on librec toolkit [Guo et al., 2015].

Parameter Setting. Following [Chen et al., 2015; Lee et al., 2013], the number of dimensions for latent vectors, i.e., D, is set to 20 for all the methods. For BPMTMF and PMTMF, we empirically set the number of topics K to 20; Following [Griffiths and Steyvers, 2004], ↵ and β are set to 50 K and 0▷01 respectively. Following [Salakhutdinov and Mnih, 2008], we initialize θ(k) 0 = 0, ⌫ (k) 0 = D, W(k) 0 to the identity matrix and variance σ2 k = 2. As indicated in [Salakhutdinov and Mnih, 2008], the predictive accuracy becomes relatively stable when the iteration number is larger than 150 for BPMF. Hence, for BPMTMF, we discard 200 iterations for burn-in, and run another 150 iterations for sampling. The other parameters for baselines are set to the reported optimal values in the original papers since we have similar experimental setup.

4.2 Results and Analysis

Performance Comparison for Rating Prediction. We present the performance of the comparison methods for rating prediction in Table 4. Among all the baseline methods, the recently proposed WEMAREC performs best. WEMAREC adopts a partitional co-clustering method for submatrix generation, representing the state-of-art for local MF. Then we examine the performance of our proposed methods, namely PMTMF and BPMTMF. We can observe that PMTMF is only slightly worse than the best baseline WEMAREC. It indicates that our probabilistic realization of local MF (i.e., PMTMF) can achieve very good performance compared with previous local MF methods. Further, the Bayesian model BPMTMF is substantially better than PMTMF and WEMAREC, which shows the effectiveness of the Bayesian approach. Note that the difference between PMTMF and BPMTMF is that BPMTMF implements PMTMF in a full Bayesian approach. Hence, to explain why BPMTMF improves over PMTMF, an important reason is that a Bayesian model is more effective to control the model complexity. Compared to the baseline methods, BPMTMF provides a more principled solution to both submatrix generation and weight setting in a joint model. It benefits from the Bayesian approach that fewer efforts are required in parameter selection due to the incorporation of hyper-priors. As a comparison, WEMAREC needs to set the co-clustering parameter and combine weights with more care.

Cluster Analysis. Besides performance improvement, another merit of our proposed model is that we characterize clusters as topics, which is likely to have more coherent semantics. To see this, we construct a qualitative analysis for the clustering results. Among the baselines, DFC adopts a randomized method for submatrix generation, and WEMAREC tends to produce very small submatrices, hence both are not suitable for clustering analysis. We select LLORMA as a comparison for BPMTMF. In MoiveLens dataset, a movie is attached with a set of movie genre labels. We first run both LLORMA and BPMTMF to produce a set of clusters (or topics). Given a learnt cluster (or topic), we assign a

⇥ Toy Story

movie genre label with the most number of occurrences in the labels of its ten top representative items. Table 3 presents the two sample clusters generated by LLORMA and BPMTMF. We can observe that BPMTMF is able to generate more coherent clusters, i.e., topics. With coherent topical semantics, it provides a more interpretable latent representation for users and items.

Impact of the Topic Number. An important parameter in BPMTMF is the number of topics (i.e., K), since we set topic-specific latent representations corresponding to each topic. We vary K in the interval [5↪ 45] with a gap of 5, and report the RMSE performance of BPMTMF in Fig. 2. We can observe that the performance achieves the best when 15  K  25. We also incorporate the performance of BPMF as a comparison, which is a special case of our model BPMTMF when K = 1. The performance when K ≥ 5 is substantially better than that of K = 1. By combining the analysis for Table 3, we can see using multi-topic MF is effective to capture the complex characteristics of users and items, further improve the performance of rating prediction.

5 Conclusion

In this paper, we present a Bayesian formulation of local matrix factorization. Our approach elegantly integrates probabilistic matrix factorization with topic models in a joint model. We have also shown that there is a close connection between our model and previous non-probabilistic methods. Our model is more powerful to reflect the complex characteristics for users and items in rating prediction, and further enhances the model interpretability. Extensive experiments on large real-world datasets demonstrate the effectiveness of the proposed model.

Acknowledgments This work was partially supported by NSFC grants (No. 61321064, 61472141, 61502502), Shanghai Knowledge Service Platform Project(No. ZF1213) and Beijing Natural Science Foundation (No. 4162032).