MPMA: Mixture Probabilistic Matrix Approximation for Collaborative Filtering

1 Introduction

Collaborative filtering (CF) methods have achieved great success in today's recommender systems, among which matrix approximation (MA) is one of the most popular techniques. In MA-based CF methods, both users and items are characterized by vectors of latent factors inferred from the user-item rating matrix, and these latent factors are used to make rating predictions [Adomavicius and Tuzhilin, 2005;

⇤Chao Chen and Dongsheng Li contributed equally to this work.

Su and Khoshgoftaar, 2009]. Most existing MA-based methods [Srebro et al., 2004; Salakhutdinov and Mnih, 2007; Koren, 2008] rely on globally optimized user/item latent factors to produce recommendations. However, in many realworld applications, if we take the globally optimized latent factors as "common interests", then subsets of users may share "unique interests" that are not covered by the "common interests" [Xu et al., 2012]. Therefore, if MA methods only consider the "common interests" without considering "unique interests", the recommendations may not be optimal for the "unique" subset of each user. As pointed out by Koren et al. [2008], MA models can effectively estimate overall structures that relate simultaneously to most or all items, but they perform poorly at detecting strong associations among a small set of items.

Recently, matrix clustering [Xu et al., 2012; Lee et al., 2013] and community detection [Zhang et al., 2013] methods have been proposed to discover the localized relationships among subsets of users/items. In these methods, local user/item latent factors are trained within clusters/communities, and then recommendations are produced by local models. However, these methods often rely on only local models and fail to incorporate the global latent factors in recommendation, which may compromise recommendation quality due to insufficient data in local clusters or communities [Chen et al., 2015]. In summary, MA-based CF methods only relying on either global latent factors or local latent factors alone compromise recommendation accuracy. Therefore, there is need to design new MA-based CF methods which can incorporate both global latent factors and local latent factors.

In this paper, we developed a new method to model each user/item using local and global latent factors to capture both localized relationships in user-item subgroups and common associations among all users and items. Following multitask feature learning techniques [Evgeniou and Pontil, 2007; Ando and Zhang, 2005], we share global user/item latent factors across user-item subgroups, so that the local latent factors can be trained without suffering from insufficient data issue. In a Bayesian perspective, the proposed mixture probabilistic matrix approximation (MPMA) method assumes every user-item rating can be depicted by a Gaussian mixture model containing three components: (1) a global model that captures the global latent factors of all users and items, (2) a user-based local model that captures the local latent factors of the corresponding subset of users, and (3) an item-based local model that captures the local latent factors of the corresponding subset of items. In MPMA, a new optimization problem is first defined and solved to obtain the global/local latent factors for each user/item. A pipeline-based learning method is proposed to train the user/item latent factors in parallel. Finally, recommendation scores are generated by combining the scores from different components of the mixture model. The proposed MPMA method is evaluated using two real-world datasets (MovieLens and Netflix), and the experimental results demonstrate that MPMA achieves better recommendation accuracy than five state-of-the-art MA-based CF methods while achieving good efficiency.

2 RelatedWork

Recommender systems have become increasingly popular in recent years, aiming to provide personalized recommendations for products that suit users' tastes [Adomavicius and Tuzhilin, 2005]. Among existing recommender solutions, collaborative filtering (CF) is widely used for simplicity of implementation and high quality of recommendation. Early CF algorithms focus on memory-based approaches, such as userbased [Herlocker et al., 1999] and item-based [Sarwar et al., 2001] methods, which make rating predictions based on similarities between users/items. However, these approaches suffer from the data sparsity problem, because the user/item similarities cannot be calculated accurately without sufficient ratings.

Recently, matrix approximation-based CF methods have been proposed to alleviate the data sparsity issue. Billsus et al. [1998] first introduced SVD to the domain of collaborative filtering. Later on, a maximum-margin matrix factorization (MMMF) method was proposed by Srebro et al. [2004]. Salakhutdinov et al. [2007] first proposed a probabilistic matrix factorization (PMF) method, and later constructed BPMF - a Bayesian extension of PMF method [Salakhutdinov and Mnih, 2008]. Koren et al. [2008] pointed out that these models are generally effective at estimating overall structure that relates simultaneously to most or all items, but perform poorly at detecting strong associations among a small set of closely related items. To address this issue, recent work adopted matrix clustering techniques [Xu et al., 2012] and community detection methods [Zhang et al., 2013] to find user/item clusters with strong correlations to improve recommendation accuracy. Mackey et al. [2011] and Lee et al. [2013] followed divide-and-conquer methodology, which divides the MA task into smaller subproblems, solves these subproblems in parallel, and then combines the recommendations of sub-models to achieve better accuracy. However, these methods mainly focus on ratings inside clusters and ignore the majority of user ratings outside clusters. Since training data are often insufficient in the detected clusters, the performance of local models may degrade due to severe overfitting [Chen et al., 2015]. Figure 1 summarizes these two types of MA models in (a) and (b), respectively.

The objective of this work is to unify localized relationships in user-item subgroups and common associations among all users and items to improve the recommendation accuracy. The most related existing works are Collective Matrix Factorization (CMF) [Singh and Gordon, 2008] and Group-Sparse Matrix Factorization (GSMF) [Yuan et al., 2014]. CMF shares parameters among factors when decomposing multiple matrices represented for multiple relations to learn different type of user behaviors. And GSMF uses group sparsity regularization to automatically transfer information among multiple types of behaviors. Different from previous works, the proposed work only utilizes rating matrix without requiring additional information and directly models each user/item by global (common) and local (private) features, and then shares global features across multiple tasks. We illustrate this idea in Figure 1 (c), where we can see, items for users in R1 are modeled by both global features ˜ V and local features V (1) , and the global user features ˜U (1) and ˜U (2) are shared across multiple tasks. Notably, the proposed MPMA method can learn multiple related tasks simultaneously, since multi-task feature learning has been empirically and theoretically proved to often significantly improve model performance relative to learning each task independently [Evgeniou and Pontil, 2007; Ando and Zhang, 2005]. For better understanding, we introduce the proposed MPMA method in a Bayesian perspective.

3 Mixture Probabilistic Matrix Approximation

This section first formulates the MPMA problem. The method for learning user/item feature vectors in the mixture model of MPMA is then described. Finally, the rating prediction method based on the mixture model is presented in detail.

3.1 ProblemFormulation

Let's first introduce the notations used in this paper. Upper case letters, such as R, U, and V , denote matrices. For matrix R 2 Rm⇥n , we denote Ri· as the i-th row vector, R·j as the j-th column vector, and Rij as the entry in the i-th row and j-th column. In addition, the Frobenius norm is adopted in this paper, which is defined as ♣♣R♣♣2 := Pmi=1 Pnj=1 R2 ij .

MPMA assumes that each user/item is modeled by two levels of latent factors: (1) global latent factors shared across all users/items, and (2) local latent factors shared within subsets of users/items. Furthermore, as shown in Figure 2, we introduce a new mixture feature vector model. In this model, each user i (item j) is characterized by a global feature vector ˜Ui·( ˜ V·j) and a local feature vector U (t) i· (V (s) ·j ). Meanwhile, each rating Rij is also described by the mixture model with latent variables Z, which consists of local user model N(Rij♣ ˜Ui·V (s) ·j ↪ σ2 1 I) (left), local item model N(Rij♣U (t) i· ˜ V·j ↪ σ2 3 I) (right), and global model N (Rij ♣ ˜Ui· ˜ V·j ↪ σ2 2 I) (middle).

To discover user-item subgroups sharing similar unique interests, many existing clustering techniques or community detection methods can be adopted, such as K-means++ method [Arthur and Vassilvitskii, 2007], and Bregman Coclustering method [Banerjee et al., 2007], etc. Without losing any generality, we assume that users are divided into g groups, and the rating matrix of the t-th user group is denoted as R(t) U (t 2 [1↪ g]). Similarly, items are divided into f groups, and the rating matrix of the s-th item group is denoted as R(s) V (s 2 [1↪ f]). For each user-item pair (i↪ j), we assume user i is in the t-th user group and item j is in the sth item group. Then, the conditional distributions of the three corresponding components (as illustrated in Figure 2) can be defined by three Gaussian models, as follows:

where ˜Ui· ( ˜ V·j) is the global feature vector of the i-th user (j-th item), and similarly, U (t) i· (V (s) ·j ) is the local feature vector of the i-th user (j-th item) for the t-th user group (s-th item group). Following the idea of probabilistic matrix factorization (PMF) [Salakhutdinov and Mnih, 2007], zero-mean spherical Gaussian priors are placed on all user and item feature vectors. Thus, each global/local feature matrix can be modeled as follows:

where σ2 · denotes the co-variance matrix of each random variable and I denotes the identity matrix. Then, the log of the posterior distribution over the user and item features is given by

where C is a constant that does not depend on the parameters. Unfortunately, it is very difficult to directly maximize the log-posterior in Equation (8). Therefore, we try to find an approximate solution via maximizing the lower bound of Equation (8). Based on Jensen's inequality, the lower bound of Equation (8) can be obtained as follows:

where Iij is an indicator function. Iij = 1 if user i rates item j in the training data, and Iij = 0 otherwise. Then, applying Equations (1) to (7) in Equation (9), the optimization objective becomes:

To maximize the objective function defined in (10), it is equivalent to minimize the sum of squared error loss function with quadratic regularization terms as follows:

where ↵s = (⇡1σ2 )◁(⇡2σ2 (s) ) and βt = (⇡3σ2 )◁(⇡2σ2 (t) ) are the weights for local models by giving the weight of global model to 1. Moreover, λ1 = [(⇡1 + ⇡2)σ2 2 ]◁(⇡2σ2˜U ), λ2 = [(⇡2 + ⇡3)σ2 2 ]◁(⇡2σ2˜ V ), λ3 = (⇡1σ2 2 )◁(⇡2σ2˜ V ) and λ4 = (⇡3σ2 2 )◁(⇡2σ2˜U ) are the regularization parameters.

Based on Equations (11) to (14), the key characteristics of MPMA are summarized as follows:

• The terms in Equation (11) are the same as the optimization objective of standard SVD method, which ensure that the learned ˜U and ˜ V can accurately estimate the overall structure and avoid overfitting in user/item feature vectors.
• The terms in Equation (12) and Equation (13) can help learn local latent factors based on the global latent factors ˜U and ˜ V , and parameters ↵s and βt can be employed to control the contribution of individual user/item clusters. Meanwhile, the global latent factors will be updated during the optimization of local latent factors, so that the global latent factors of MPMA will be different from those in standard SVD method.
• The standard SVD method can be viewed as a special case of MPMA by setting all ↵s = βt = 0. More specifically, we refer to the model with only local user features as u-MPMA, the model with only local item features as i-MPMA, and the one with both of them as MPMA. Empirical study shows both u-MPMA and i-MPMA can improve recommendation accuracy and MPMA achieves better improvement of recommendation accuracy than u-MPMA and i-MPMA.

3.2 Optimization Algorithm

After defining the optimization objective, we present how to solve the optimization problem in this section. As shown by Srebro et al. [2003], the problem defined in Equations (11) to (14) is a difficult non-convex optimization problem, because the introduced weights lead to significant changes in the critical point structure. To tackle this problem, we develop a stochastic gradient descent (SGD) based method.

In SGD, we first compute the partial derivatives of parameters, and then iteratively update the parameters until convergence. The partial derivatives of the loss function with respect to global features ˜U and ˜ V can be computed as follows:

The partial derivatives of local feature vectors U (t) and V (s) are given by

Compared with standard matrix approximation based methods, the proposed method requires more computation time due to the extra local features. However, we can see that the parameter update stream consists of two processing stages: S1) updating global feature vectors and S2) updating local feature vectors. If the S1 stage is performed on a submatrix which has no overlapping rows and columns with the submatrix that S2 stage is performed, then we can construct a pipeline to perform S1 and S2 in parallel.

The detailed pipeline-based learning method is presented in Algorithm 1. In line 7 and 8, S1 and S2 can run in parallel, so that the overall training time of MPMA can be reduced. Note that following the training data scheduling method in [Recht and R´e, 2013], we can set up more computing threads in Algorithm 1 to further improve the training efficiency.

Algorithm 1 Efficient Pipeline-based Learning Algorithm

• Input: Rating matrices R for all users and items, R(s) U (s 2 [1↪ g]) for each user group, and R(t) V (t 2 [1↪ f]) for each item group. ↵s↪ βt↪ λ are parameters in the mixture model, and r is the rank for MA.
• 1: //building model
• 2: Randomly initialize ˜U 2 Rm⇥r , U (s) 2 Rm⇥r (s 2 [1↪ g]), ˜ V 2 Rr⇥n and V (t) 2 Rr⇥n (t 2 [1↪ f]);
• 3: while not converged do
• 4: Choose i 6= i0 2 [1↪ g] and j 6= j 0 2 [1↪ f];
• 6: //Update in parallel:
• 5: R(i↪j) = R(i) U \R(j) V , R(i0 ↪j 0 ) = R(i0 ) U \R(j 0 ) V ;
• 7: S1: update ˜U and ˜ V w.r.t. R(i0 ↪j 0 ) by Eq. (15)(16);
• 8: S2: update U (i) and V (j) w.r.t. R(i↪j) by Eq. (17)(18);
• 9: end while

Output: ( ˜U↪ ˜ V ↪ U (1) ↪ ▷ ▷ ▷ ↪ U (g) ↪ V (1) ↪ ▷ ▷ ▷ ↪ V (f) )

3.3 Rating Prediction

In MPMA, each user-item rating is characterized by a mixture model, so that we can estimate the "weight" of each component in the mixture model - ⇡k and then apply the mixture

#RowCluster × #ColumnCluster

#RowCluster × #ColumnCluster

Figure 4: Performance of local cluster-based constraints with different rank r ranging in [10↪ 100] on MovieLens 1M (left) and MovieLens 10M (right).

components to predict user-item ratings. The hidden parameters ⇡k (k 2 [1↪ 3]) can be obtained with the EM method as follows:

E-step:

M-step:

where Fk denotes the user and item features for the k-th component in the mixture model. After obtaining ⇡k, we can use the mean of mixture model to estimate the missing rating of user i on item j as follows:

where user i (item j) belongs to the t-th user group (s-th item group).

4 Experimental Results

This section evaluates the proposed MPMA method on three well-known datasets which have been widely used for evaluating recommendation algorithms - 1) MovieLens 1M (⇠106 ratings of 6↪ 040 users on 3↪ 706 items), 2) MovieLens 10M (⇠107 ratings of 69↪ 878 users on 10↪ 677 items), and 3) Netflix (⇠108 ratings of 480↪ 189 users on 17↪ 770 items). The root mean square error (RMSE) is adopted as the evaluation metric for recommendation accuracy, which can be computed as q 1 ♣T♣ P(u↪i)2T (ˆRui -Rui)2 , where T denotes the set of ratings in test data and ♣T♣ is the number of ratings in test data.

4.1 Sensitivity Analysis

In this study, we evaluate how the recommendation accuracy of MPMA varies with different parameter settings on MovieLens (1M) and MovieLens (10M) datasets, i.e., the number of clusters and rank.

Accuracy vs. Clustering methods

Figure 3 analyzes the impact of different clustering methods with different numbers of row and column clusters f and g on MovieLens (1M) and MovieLens (10M) respectively, where we use three commonly-used and typical clustering method: K-means++(KmP) method [Arthur and Vassilvitskii, 2007], Balanced clustering(BaC) method [Banerjee and Ghosh, 2002], and Bregman Co-clustering(BrC) method [Banerjee et al., 2007]. Note that, MPMA method is orthogonal to clustering algorithms, so other clustering methods can also be adopted in MPMA. In Figure 3, the cases of 1 ⇥ 2 and 2 ⇥ 1 clusterings are not considered, because those two cases are i-MPMA and u-MPMA, respectively, and the results will be presented in Figure 4.

We can see from the results that MPMA with BaC method can outperform MPMA with both KmP and BrC methods in recommendation accuracy in all cases. This is because both of KmP and BrC methods will often produce one or a few large sparse clusters, which has been proved to be harder to provide personal recommendations [Su and Khoshgoftaar, 2009]. In addition, we can see that the accuracies of all methods decrease as f and g increase. This is due to the fact that each co-cluster contains less user-item ratings as the number of user/item clusters increases, resulting in insufficient data for model training.

Accuracy vs. Latent factors

As shown in Figure 4, the proposed u-MPMA (with local user features) and i-MPMA (with local item features) methods can both outperform the classic RSVD method on all ranks. This indicates that both local user features and local item features can help improve the recommendation accuracy. Moreover, the proposed MPMA method, which adopts both local user features and local item features, outperforms all other three methods (RSVD, u-MPMA, and i-MPMA) with all ranks. This indicates that the benefits of local user features and local item features are orthogonal, and thus should be both adopted in collaborative filtering.

Accuracy vs. Rank

Figure 4 also studies the effect of local user/item features with rank r ranging in [10↪ 100] on both the MovieLens (1M) and MovieLens (10M) datasets. As shown in the results, higher ranks will lead to better accuracy when r increases from 10 to 100, and the results get stable when r is larger than 50. But the recommendation accuracy of RSVD decreases slightly as r increases, which means large ranks will cause overfitting on RSVD. But in the proposed method, overfitting is not observed even when rank r is as large as 100, which indicates that the introduced local features can increase robustness of the proposed method.

Efficiency vs. Rank

Figure 5 compares the computation efficiency of RSVD method and MPMA method with different ranks. We can see from the results that MPMA achieves comparable efficiency with RSVD with the help of the pipeline-based learning framework (Algorithm 1), although MPMA has to learn many more local features. Note that, more pipelines can be set to further enhance efficiency by dividing more user/item groups. This demonstrates that MPMA can achieve good scalability on large datasets.

4.2 Performance Comparison

In this study, we compare the recommendation accuracy of the proposed method against five state-of-the-art matrix approximation basedCFmethods: NMF [Lee and Seung, 2001], MPMA 0.7712 ◦ 0.0002 0.8139 ◦ 0.0003

RSVD [Paterek, 2007], BPMF [Salakhutdinov and Mnih, 2008], APG [Toh and Yun, 2010] and GSMF [Yuan et al., 2014]. We emphasize the comparison between MPMA and GSMF, because GSMF is the latest work related to the proposed MPMA method and empirically proves to be better than CMF [Singh and Gordon, 2008].

In the following experiments, all results are presented by averaging the results over five different random train/test splits with the ratio of 9:1. For the proposed method, we set rank r = 100 and f ⇥g as 2⇥2, learning rate v = 0▷001. For the parameters from Equation 11 to 14, we set all ↵ and β values to 1 due to the hardness of estimating all σ values, and set all λ values to 0.06 for L2-regularization. Optimal parameters of the compared methods are chosen from their papers.

As we can see from Table 1, MPMA significantly outperforms all the other five matrix approximation based CF methods on both datasets. Compared with NMP, RSVD, BPMF, APG and GSMF, the main reasons that the proposed MPMA method can make more accurate recommendations are 1) local latent factors are adopted by MPMA to better understand user interests and 2) a mixture model is adopted to combine both local predictions and global predictions to achieve more accurate predictions.

5 Conclusion

Existing matrix approximation based collaborative filtering methods rely on either global latent factors or local latent factors of users and items, and cannot provide optimal user/item modelling and the most accurate recommendations. In this paper, a mixture probabilistic matrix approximation (MPMA) method is proposed, which unifies global latent factors and local latent factors of users and items by a Gaussian mixture model to improve recommendation accuracy. Experimental study on real-world datasets demonstrates that the proposed MPMA method can outperform five state-of-theart MA-based collaborative filtering methods in recommendation accuracy. Furthermore, the proposed MPMA method can be trained by a pipeline-based method, so that it is scalable on large datasets.

Acknowledgement

This work was supported in part by the National Natural Science Foundation of China under Grant No. 61233016, and the National Science Foundation of USA under Grant Nos. 0954157, 1251257, 1334351, and 1442971.