Cross-Domain Collaborative Filtering via Bilinear Multilevel Analysis

1 Introduction

In the era of Web 2.0, searching for what we want and then finding what we really need from a huge amount of online information became a daunting task. As a result, various recommender systems have been proposed to alleviate the information overload problem. As the core component of a recommender system, collaborative filtering (CF) techniques have been widely studied in recent years. In particular, matrix factorization (MF) based latent factor models [Koren, et al., 2009, Weston, et al., 2012] have become dominant in current CF approaches, where MF rates the user i's preference to item j according to the interaction of the user-factor vector and the item factor using the inner product, i.e., . However, most of the real world data follows the power law, i.e., the majority of users are only associated with a very few items. Therefore, insufficient data has become the major barrier for CF methods including MF, and it leads to two big challenges to the CF: the cold-start and data sparsity issues [Su and Khoshgoftaar, 2009].

To address these issues, the cross-domain collaborative filtering (CDCF) approach, which leverage data from multiple

3 Dept of CEE 4 Dept of EE jiewang guzhiping @stanford.edu @stiei.edu.cn

domains, is becoming an emerging research topic [Li, 2011]. An early neighborhood based CDCF (N-CDCF) method was introduced in [Berkovsky, et al., 2007], but it can easily fail to find similar users or items when data is very sparse. It is possible to directly apply matrix factorization (MF) to CDCF (MF-CDCF) by concatenating the rating matrix of each domain. However, this method may not work properly for the cross-domain scenario. These drawbacks are revealed in an example using two domains Book and Music as depicted in Figure 1 (a). Empirically, the factors affecting users' preferences for books are different from those affecting users' preferences for music. Therefore, due to such heterogeneities between book factors and music factors, it generally fails to find good estimates for that can simultaneously measure both the preferences for books and music.

Recently, Pan, et al. [2010] proposed a transfer learning based MF (TLMF) for CDCF. They assume the existence of an auxiliary domain with dense user data so that knowledge learned in this domain can be transferred to the target domain. However, it is often impossible to find such a dense data domain realistically since the rating matrix is sparse for the majority of users in most domains where the power law pervades. To surmount this barrier, a more reasonable solution is to leverage the complementary data from multiple domains. Collective matrix factorization (CMF) [Singh and Gordon, 2008] is able to leverage data from multiple domains by coupling the rating matrix of each domain along the common user dimension. However, all these models may still encounter a special cold-start problem when a user is new to the target domain. As shown in Figure 1 (b), the user-factor vectors for users are co-determined by the feedback in auxiliary and target domains. If no data is available for user i in the target domain (marked with a red box), the user-factor vector will have to be simply determined by the user preference data in the auxiliary domain. If such is directly transferred to the target domain and interacts with heterogeneous item factors to measure user preferences, it may yield a poor prediction. We call this issue as the "blind-transfer". Recall that the data associated with the majority of users are insufficient and even absent, so the above approaches commonly suffer from such blind-transfer issues for realistic online data. For current MF approaches, the rating to an item is fully determined by user factors, i.e., . Due to this reason, current MF models cannot relieve themselves of the blind-transfer issue, especially when the data is extremely sparse.

In this paper, we address the "blind-transfer" issue from a new perspective. The basic assumption here is that the ratings for items are determined not only by personal factors but also by domain and community effects. Let's take an example to illustrate this hypothesis. We argue it is possible to predict a general rating for iPhone 5 based only on general market factors, even without any user's feedback. Moreover, the users in different communities often provide biased ratings contrary to each other, for instance, trendspotters may give higher ratings (positive bias) to iPhone 5 whereas IT engineers may give lower ones (negative bias). Such communityspecific bias is associated with the underlying community characteristics. As to a specific user, a personalized bias is given to the general rating , where can be divided into two parts, and repectively. The is determined by domain-independent user factors that may correlate to personal status, e.g. age, position, income, whereas the is determined by domain-specific user factors, e.g., a user may prefer expensive phones but cheap clothes. With all that in mind, the personal rating of an item can be expressed as , i.e., the determinants of a personalized rating is governed by a multilevel factor model apart from flat individual factor models. Hence even when the user data is absent in some domain, is still available to give an acceptably accurate rating. Therefore, the proposed multilevel factor model is more complete and robust than the traditional individual-only factor models.

To model the above hierarchical factors, we employ the multilevel analysis theory, also referred to as the hierarchical linear model, or the mixed model [Goldstein, et al., 2007, Snijders and Bosker, 2011]. Further, we propose a novel MF model that seamlessly integrates multilevel analysis theory. As MF is a bilinear model, our model is named the Bi-Linear Multilevel Analysis (BLMA).

The main contributions of this paper include:

• ♥ We propose an innovative approach to determine the personalized ratings via a multilevel factor model, which is more complete and robust than the classical flat factor models, especially when data is sparse.
• ♥ We provide a novel CDCF model, the BLMA, which integrates multilevel analysis theory to the MF model.
• ♥ We apply Bayesian inference using parallel Gibbs sampling to learn parameters of the BLMA.
• ♥ We empirically evaluate our approach and other stateof-the-art approaches on a real-world data set. The results demonstrate the superiority of our approach.

2 Problem Formulation

Our solution for the CDCF problem, which has a hierarchical structure, is depicted in Figure 2. In this paper, we use to denote domains, , and to index the communities within domain , . Communities can be defined dedicatedly or discovered from data. Users are indexed by , for , and in each domain, a user only belongs to a community. is used to index items for each domain, for . The ratings (observed data) are denoted as , where indexes each observation, i.e., the rating that user gave to item of domain . We use to denote all indices associated with community in domain and similarly we have , , and etc.

In Figure 2, it can be observed that users are nested within communities within domains. This is a typical usage scenario of multilevel analysis [Goldstein, et al., 2007, Snijders and Bosker, 2011]. In particular, it is natural to employ the nested random effects model [Rabe-Hesketh and Skrondal, 2008] to analyze such a nested structure as given by Eq. (2), where , , are used to model the nested effects. More specifically, represents the fixed effects for domain (Level-3), user belongs to the community (Level-2) in domain , and the random effects of this community are denoted as , and stands for the domain-specific random effects of user (Level-1).

Moreover, since users are associated with multiple domains in a CDCF problem, in Eq. (2) is used to model such cross-domain user factors. In fact, the has the exact counterpart in multilevel analysis, namely the crossed random effects model [Raudenbush, 1993, Rabe-Hesketh and Skrondal, 2008]. Also, in Eq. (1), is the mean rating of domain and stands for the random effects for item and is the error associated with each observation. Here, the bilinear term formally represents the multilevel effect over items as discussed previously. Since this model contains both fixed and random effects, it is called a mixed (effects) model in multilevel analysis.

Then, one question that needs to be answered is whether to use fixed or random effects for domain, community and user level respectively. In practice, there is no definite criteria for determining whether fixed or random effects should be used, but some useful discussion can be found in several research papers [Gelman and Hill, 2006, Rabe-Hesketh and Skrondal, 2008]. Here, users can be viewed as a sample from a population since more new users may join, and the number of communities may also change with user growth. So the effects of users and communities are treated as random. In contrast, the effects of a domain do not change with users, i.e., the same for all users, so it is modeled as fixed effects.

3 Bayesian Bilinear Multilevel Analysis

3.1 Model

For the model given by Eq. (1), if we treat as a known vector to serve as the covariates, then Eq. (1) is reduced to a linear mixed model (LMM). Alternatively, if is treated as known covariates, Eq. (1) becomes a linear random effects model. Now let us move from the right side to the left side of Eq. (1), so the reformed equation is given by:

Immediately, we find that the mixed effects and the random effects in Eq. (5) exactly correspond to dimensional user and item factor vector in the MF. That is, we can seamlessly bridge multilevel analysis to the MF. Hence we call Eq. (1) the Bilinear Multilevel Analysis (BLMA), because the bilinear terms and are unknown and needs to be learned as classical MF models.

In this paper, we formalize the BLMA using a Bayesian probabilistic model. The corresponding graphical representation of this model is illustrated in Figure 3. Accordingly, the conditional distribution over the observed data (cf. Eq. (1)) can be easily written as:

For Bayesian analysis of multilevel models, broadly speaking, two types of prior distributions are available: (a) uninformative; (b) informative [Browne, 1998, Goldstein, et al., 2007]. The uniform prior is a commonly used uninformative prior for fixed effects, i.e., for the domain effects . In practice, it can be approximated as , where is very large. For random effects, informative priors should be placed on variance parameters. The inverse gamma prior, , with small , is often placed on scalar variance while the inverse Wishart prior, , is used for variance matrix [Browne, 1998, Browne and Draper, 2006]. In this paper, without loss of generality, we set for and for all . Then, the priors for the variance parameters w.r.t. the random effects, , , , and error , can be given as follows:

Obviously, this model lends itself to a full Bayesian analysis by a Markov Chain Monte Carlo (MCMC) method.

3.2 Inference

MCMC methods aim to generate samples from a joint posterior of all unknown parameters . In the BLMA, represents fixed/random effects and variances. Directly sampling all parameters in from the joint posterior is intractable in the BLMA because the product of two random variables, , does not belong to any distribution in general. Fortunately, the Gibbs sampler can approximate the joint posterior by sampling each variable in in turn, conditioned on other variables with current values. Best of all, the Gibbs sampling algorithm for the BLMA is nearly identical to that for the LMM, since the BLMA is reduced to the LMM when sampling conditioning on , and vice versa.

Referring to the Gibbs samplers for the LMM [Browne, 1998, Browne and Draper, 2000, Goldstein, et al., 2007], we design a parallel sampling algorithm for the BLMA below:

Algorithm 1: Parallel Gibbs sampling scheme for the BLMA

• ♥ Draw samples for as LMM when is given and acts as the covariates.
• For , sample the domain effects in parallel:

1. For , sample the community effects in parallel for each domain :

1. For , sample the global user effects in parallel:

1. For , sample the domain-specific user effects in parallel for each domain :

• ♥ Draw samples for as the LMM when is given and acts as the covariates.
• For , sample the item effects in parallel for each domain :

Note that appropriate initial values can fairly speed up the convergence of MCMC methods. For the BLMA, we may use a MF method, such as the BPMF [Salakhutdinov and Mnih, 2008], to generate initial values, and , w.r.t. items for each domain . Then, using as the covariates for the LMM, we can initialize by the likelihood estimates [Browne and Draper, 2006, Goldstein, et al., 2007].

3.3 Prediction

After the burn-in period, MCMC methods can predict missing ratings, , in terms of the predictive posterior mean, . This mean is often computed by the Monte Carlo approximation from S samples:

where the mean w.r.t. each sample is obtained according to Eq. (6), and the effects and are sampled from the Markov chain by Eq. (8) ~ (12).

Noted that the domain-specific effects do not exist if user is new in domain , we can simply let it be the population mean of user factors, that is (cf. Eq. (3)), or the community sample mean, namely , where returns all non-cold-start users from 's community.

3.4 Discussions

So far we have presented the prediction method for the BLMA, now we can formally explain why the BLMA can work and how it avoids the blind-transfer issue in the CDCF.

In the BLMA, the domain effects is regressed from the data for all items (cf. Eq. (8)) in a domain, so , gives the general rating to item , which is fixed for all users. The community effects is estimated according to the ratings given by the users in this community (cf. Eq. (9)), so provides the community-specific bias. As to the user level, is estimated from user's feedbacks over all domains (cf. Eq. (11)), so gives the bias based on a user's global preference. is estimated from user's feedbacks in a domain (cf. Eq. (10)), so gives the bias according to domain-specific preferences. Hence provides a multilevel effects based rating predictor as given by Eq. (13).

It has been demonstrated that leveraging social links [Ma, et al., 2008] or neighborhood data [Koren, 2008] can significantly improve prediction performance. Here, the BLMA goes a step further, it models not only the community effects to correlate users but also the other effects of domains and individuals to discover similarities. Such multilevel effects are particularly useful when individual user data is insufficient. If we remove the domain effects , community effects , and domain-specific user effects from Eq. (2), the BLMA degenerates to the CMF where only the flat singlelevel user factors are modeled. Obviously, simply using is vulnerable to the heterogeneity issue as discussed at the beginning. In comparison, the domain effects and the community effects enable the BLMA to more efficiently tackle issues of domain heterogeneity and data sparsity.

Another point of concern is the membership of community. These memberships can be directly assigned according to real-world memberships. For example, fan clubs for cars and groups for games are two types of easily retrieved memberships from two different domains. If such ready-made memberships are not available, we can discover them from data [Fortunato, 2010]. In this paper, we only consider a user belonging to a single community within a domain, but the multiple membership can also be dealt with easily by assigning different weights [Browne, et al., 2001].

4 Related Work

We propose to solve the CDCF problem by using the BLMA, which can be regarded as an approach that couples multilevel analysis with MF. Hence, the applications of multilevel analysis and MF based approaches for CDCF are the two most relevant research areas.

Codebook Transfer [Li, et al., 2009] assumes some clusterlevel rating patterns, which are represented by a codebook, can be found between the rating matrices in two related domains. The Rating-Matrix Generative Model [Li, et al., 2009] extends this idea with a probabilistic model to solve collective transfer learning problems. In reality, there are many cold-start users for most domains. Therefore, it is always out of the question to seek common patterns among domains without user data. The Coordinate System Transfer [Pan, et al., 2010] learns the user-factor matrix from an auxiliary rating matrix in the first step, and then generates the userfactor matrix for the target domain based on , with the regularization of penalizing the divergence between and . As pointed out at the beginning, this approach will run into the blind-transfer issue for cold-start users. Therefore, all the above approaches are not applicable to the CDCF problem over multiple domains as studied in this paper.

Although the CMF [Singh and Gordon, 2008] can address the CDCF problem over multiple domains by coupling the common user dimension, it still suffers from the blind-transfer issue. Moreover, CMF uses a set of weights to trade off the loss of the fitting rating matrix from each domain. However, searching an optimal combination of weights to tune the prediction performance is a heuristic and computationally expensive task. In comparison, the BLMA applies Bayesian analysis to assign priors on all variables and learns them by Gibbs sampling. In fact, we have shown that the BLMA can be reduced to the flat Bayesian CMF [Singh and Gordon, 2012] by removing all high level group effects.

The multilevel analysis [Snijders and Bosker, 2011] is a popular statistic model theory, which has been widely studied and applied to many areas, including economics, education, sociology, biology, health, and beyond [Raudenbush, 1993, Gelman and Hill, 2006, Goldstein, et al., 2007, Rabe-Hesketh and Skrondal, 2008]. The BLMA brings multilevel analysis from the traditional linear world to the bilinear world and brings multilevel effects to the MF instead of the traditional individual factors. Being an integrated approach with more robust models for tackling complex data sets, the BLMA is proposed for applications beyond the CDCF problem.

5 Experiments

The experiments were conducted on a real-world dataset, that is, the ratings for Amazon products. We evaluated the prediction performance using the BLMA and other state-of-the-art approaches to demonstrate the superiority of our model.

5.1 Data Preparation

The dataset was crawled from the publicly available Amazon website, where it contains 1,555,170 users and 1-5 scaled ratings over 548,552 different products covering four domains: 393,558 books, 103,144 music CDs, 19,828 DVDs and 26,132 VHS video tapes [Leskovec, et al., 2007]. Obviously, these domains are different but there are some common user factors to affect preferences across these domains, so this dataset is highly suitable for testing the CDCF algorithms.

We filtered out users who have rated at least 50 books or 30 music CDs so that there are enough observations to be split in various proportions of training and testing data for our evaluation. Finally, 2,505 users were selected, and in addition we retrieved all items rated by these users in these four domains and set aside top K rated items for each domain respectively. We use to denote this extracted data set. Table 1 shows the statistics of . In this experiment, we evaluated the prediction performance by using Book and Music CD as the testing domains respectively. Accordingly, we constructed a set of different training/testing sets as follows.

• ♥ Sparse data cases: We constructed two different sparsities of training sets by respectively holding out 80% and 25% of ratings for the Book domain from , when testing the prediction over books. The hold-out data serves as the ground truth for testing. Likewise, we constructed two other training sets when testing the prediction over music CDs by respectively holding out 80% and 25% of ratings for the Music CD domain from .
• ♥ Cold-start cases: To simulate the cold-start cases, we constructed two training sets by randomly selecting half of users and holding out all their data from the Book and the Music CD domains respectively.

5.2 Metrics and Comparative Methods

The Mean Absolute Error (MAE) is the most widely used evaluation metric to measure the prediction quality for collaborative filtering. In Eq. (14), denotes the true rating user gave to item , is the predicted rating, and is the number of ratings in the testing set.

In this experiment, a group of state-of-the-art methods for the CDCF problem are given by:

• ♥ MF-SGD: The most well-known MF method for single domain CF by minimizing the squared error by stochastic gradient descent [Koren, et al., 2009]. It is simply run over the rating matrix of the testing domain.
• ♥ N-CDCF-U: The user-based neighborhood method as mentioned at the beginning. Here we use 10 closest users as the neighborhood.
• ♥ N-CDCF-I: The item-based neighborhood model. We use k=10 closest items as the neighborhood.
• ♥ MF-CDCF: The MF model described at the beginning. It is run over the concatenated rating matrix that mixes the items of four domains.
• ♥ CMF: It couples the rating matrices of four domains on the user dimension [Singh and Gordon, 2008].

Since this dataset does not explicitly provide memberships of communities, we have to generate communities from data for the BLMA. As the community detection algorithm is not the focus of this paper, we simply employ hierarchical clustering algorithm to generate 50 communities for each domain.

The similarity for the clustering algorithm is computed by:

where , denotes the number of items rated by both and [Koren, 2008], denotes the target domain, and denotes other domains. It assigns more weight to the similarity of the target domain so as to create the domain-specific communities.

The dimensionality of factors and hyper-parameters for all comparative methods are determined by cross validation. The improvement becomes not significant, and even decreases for some models, after the dimensionality is increased above 30.

5.3 Results

We first evaluated the prediction performance using the above constructed training/testing sets for sparse data cases. Table 2 reports the results of all comparative methods.

From Table 2, we can find that the CDCF methods achieve much better performance than the single-domain CF method, i.e., MF-SGD. Therein, our model, the BLMA, significantly outperforms all other comparative methods over all testing cases, and at least 18% improvement is achieved for any case comparing to MF-SGD, which illustrates that the BLMA can better capture the determining factors for predicting ratings even when the user data is not sufficient. The N-CDCF-U also achieves reasonable performance when the data is relative dense, i.e., the 75% training set, but its performance degenerates very rapidly when the data becomes sparser. It is because the neighborhood based method usually fails to find any global similarity among users when the data is sparse [Su and Khoshgoftaar, 2009]. For the MF based CDCF models, the CMF outperforms the MF-CDCF because the CMF provides an effective way to transfer knowledge between domains whereas the MF-CDCF simply aggregates all available data together, ignoring heterogeneities in different domains.

Then, we evaluated the prediction performance for coldstart cases. Figure 4 illustrates the results of all comparative methods. Once again, the BLMA models achieve better performance than other approaches. In this experiment, we find that the CMF lags much behind the BLMA. Although the CMF captures common user factors across all domains, it does not correlate users, nor does it model domain-specific factors. In cold-start cases, the CMF inevitably suffers from the blind-transfer issue. In comparison, the BLMA captures multilevel effects instead of just individual effects. Such design enables the BLMA leveraging the knowledge learned from the domain-level and the community-level data even when the individual-level data are not available. Specially, the BLMA-C (using the community mean cf. ¤ 3.3) outperforms the BLMA-P (using the population mean), which illustrates that leveraging neighbors' feedbacks can more effectively improve the accuracy when a user's data is absent.

Figure 5 (a) plots the sampled domain effects, , of all four domains, and the cosine similarities between each pair of are also provided in (b). The larger similarity may reflect the smaller domain heterogeneity to share knowledge. As to a specific effect , it is positive in some domains, which results in a larger item factor contributes more to the rating, i.e. . In contrast, is negative in other domains, so the larger (e.g. the price of an item) gives the more negative contribution to the rating, e.g., higher price may yield lower rating. Moreover, the random effects model is often used in the analysis of variance (ANOVA). Figure 5 (c) shows the sampled variances for community random effects, , of the Book and Music domain. A large variance for a community effect, , reflects users in different communities having quite different views to the item effect (e.g. the genre of music) whereas a small variance reflects very close views to over all communities.

6 Conclusions

In this paper, we propose the BLMA approach to solve the CDCF problem by employing a multilevel effects model to overcome the vulnerabilities of flat individual effects model in traditional MF approaches. The experimental results indicate that the BLMA can achieve much better performance than other state-of the-art models. Since the BLMA provides an integrated approach by coupling the multilevel analysis with the MF, we also expect it to become a general framework for new applications other than the CDCF problem.

Acknowledgement

This work is partially supported by Australian Research Council Discovery grant (DP130102691), Linkage grants (LP120100566 and LP100200774), China National Science Foundation (Granted Number 61073021, 61272438), Research Funds of Science and Technology Commission of Shanghai Municipality (Granted Number 11511500102, 12511502704), Cross Research Fund of Biomedical Engineering of Shanghai Jiaotong University (YG2011MS38).

--------

• *Jian Cao is the corresponding author