Cross-Domain Collaborative Filtering over Time

1 Introduction

In recommender systems, most collaborative filtering (CF) techniques infer users' preferences based on their historical ratings. Memory-based methods [Resnick et al., 1994] find K-nearest neighbors who have similar historical interests with the active user. Model-based methods [Hofmann, 1999; Si and Jin, 2003; Porteous et al., 2008] learn preference models for the users who have similar historical interests. Recommendations can thus be made based on the many aspects of user interests which were collected during a long time period.

However, in real-world scenarios, user interests are not static and may drift over time since they are continuously affected by moods, contexts, and pop culture trends. For example, a user recently under great working pressure may prefer comedies to relax him/herself, while he/she used to prefer suspenseful crime and thriller movies. The second example is that a user's interest is very likely to drift to sweet family movies when she is going to have a baby, though she has watched many horror movies before. Another example is that, although many people don't like animations, they may still have interests in emerging 3-D animations because of the fantastic 3-D visual effects. These observations show that, although many aspects of user interests can be found based on users' historical ratings, at a certain time slice, one user's interest may only focus on one or a couple of aspects. Thus, the static CF methods built on the entire historical ratings are inadequate to capture user-interest drift. In order to track user interests and create comprehensive user profiles such that different recommendation strategies can be used for consistenttaste users and changing-taste users, a CF method that can model user interests over time is required.

Recently, researchers have observed the underlying temporal dynamics in CF and some temporal and evolutionary CF methods have been reported [Koren, 2009; Liu et al., 2010; Xiong et al., 2010]. However, these methods do not target explicitly modeling user-interest drift. Their temporal features/components cannot be used for interpreting user interests. In order to explicitly model user-interest distribution over items, one possible approach is to use probabilistic topic models [Steyvers and Griffiths, 2007], which can model user (document) interests (topics) over items (words). But in this paper, we are given a more complex problem setting which involves a series of temporal domains. Two questions can thus be raised immediately: 1) what components in a rating matrix can be shared across CF temporal domains? and 2) how to model drifting user-interest components over time?

In this paper, we consider modeling user-interest drift over time based on the assumption that each user has multiple counterparts across temporal domains and the counterparts of successive temporal domains are closely related. We adopt the cross-domain CF framework [Li et al., 2009] to share the static group-level rating matrix across temporal domains. The group-level rating matrix is a compressed rating pattern representation whose element can be viewed as an expected rating provided by a user prototype on an item prototype, while each real user/item is a convex combination of these prototypes. This answers the first question and the details are introduced in Section 3. In the group-level rating matrix, each user prototype (group) has a set of expected ratings on item prototypes (groups), which indeed reflect the interests of user groups over item groups. Since a real user is a convex combination of the user prototypes, we can easily obtain the individual users' interests over item groups. By modeling the relatedness of user-group memberships between successive temporal domains, we can capture user-interest drift. The derived method is based on a Bayesian latent factor model which can be inferred using collapsed Gibbs sampling. This answers the second question and the details are introduced in Section 4. The experimental results show that our method can achieve state-of-the-art recommendation performance, compared with the well-known TimeSVD++ [Koren, 2009]. Moreover, our method can explicitly track and visualize user-interest drift over time.

2 Problem Formulation

We are given an N × M rating matrix X, each element Xij ∈ {1, . . . ,R} denotes a rating provided by user ui on item vj , where {1, . . . ,R} are rating scales. Besides, Xij is also associated with a time-stamp. We split the whole time span of ratings into T time slices and let the matrix Y with the same size of X denote the corresponding time slice indices of ratings, where Yij ∈ {1, . . . , T}. We call these time slices temporal domains. Each temporal domain comprises a fraction of the entire rating data, we denote by X(t) the ratings in the tth temporal domain, and X = {X(1) , . . . ,X(T) }.

Through the whole time span of ratings, there are only N users and M items. However, as we argued in Section 1, the users in different temporal domains may have different interests and their interests can drift over temporal domains. Thus, we let each user ui have T counterparts in T temporal domains, denoted by {u(1) i , . . . , u(T) i }. One can simply understand this manipulation as that we have M ∗ T users. The key point is that each series of T counterparts for a certain user are temporally related. Similarly, we also let each item vj have T counterparts {v(1) j , . . . , v(T) j } since items may also have slight character drift over time.

By splitting one user into T counterparts and modeling each counterpart separately, we can also capture different user interests in different temporal domains. However, in realworld scenarios, the rating data in each temporal domain for a certain user are very sparse. Learning a model for u(t) i merely based on X(t) is a big challenge. As we have observed that the user counterparts of successive temporal domains should be closely related, we resort to sharing rating knowledge across temporal domains for addressing the sparsity problem in individual temporal domains.

3 A Framework for Temporal-Domain CF

Looking from macroscopic view, the interest distribution of the large user population should be consistent over time. Although we have shown that individual users may have interest drift from time to time, the overall interest distribution of the whole user population should remain stable since different users' interest drift can be counterbalanced (i.e., some users' interests drift from A to B while some others' drift from B to A). Thus, the user-interest distributions over items in different temporal domains are similar. In other words, if we group users based on their interests, the user groups (prototypes) in different temporal domains should be same.

The above observation implies that, we can share the group-level rating knowledge across temporal domains while let the user-specific components drift over time and constrained by the temporal relatedness. This problem setting fits the cross-domain CF framework, i.e., rating-matrix generative model (RMGM) [Li et al., 2009]. In RMGM, a grouplevel rating matrix B is learned from and shared across multiple related CF domains. Each element Bkl denotes the expected rating provided by user prototype k on item prototype l. Putting our problem in this framework, the temporal domains are related domains, and a group-level rating matrix B is shared across temporal domains. In addition, we also impose dependence for successive user/item components such that temporal relatedness of user-interest drift also can be captured. Our framework is illustrated in Figure 1.

In our temporal domain setting, a user counterpart u(t) i is a convex combination of the K user prototypes and has a discrete distribution (membership) over K user groups, which is denoted by p(t) i and ∑k p(t) i [k] = 1. Similarly, an item counterpart v(t) j also has a membership over L item groups, denoted by q(t) j . Then a rating in X(t) can be predicted by

It is worth noting that the group-level rating matrix B is shared across all the T temporal domains while user/itemgroup memberships, p(t) i and q(t) j , are domain-dependent. Thus far, we should address the following two problems:

1. Learn the shared group-level rating matrix B based on all the ratings fromT temporal domains.
2. Learn the user/item-group memberships, p(t) i and q(t) j , in each temporal domain and impose temporal relatedness for memberships in successive temporal domains.

Given B (static over temporal domains) and p(t) i (drifting over temporal domains), we can then predict user ui's interest over item groups at temporal domain t and track the drift over time. We address these two problems in Section 4.

4 Algorithm

4.1 Collaborative Filtering based on Bi-LDA

Bi-LDA [Porteous et al., 2008] is a Bayesian latent factor model for matrix tri-factorization: ˆX = PBQ⊤, where B is a two-sided low-rank representation of X, P and Q are membership matrices, where P1 = 1 and Q1 = 1

In collaborative filtering, given an N × M rating matrix X, Bi-LDA can be used for co-clustering users and items by assigning each rating with a pair of latent factors (z U , z I ) (i.e., the indices of the associated user/item groups). The coclustering result gives a K × L group-level rating matrix B, an N × K user-group membership matrix P, and an M × L item-group membership matrix Q.

Bi-LDA is a generative model, where the ratings in X can be generated in the following generative process:

1. For user-item joint group (k, l), choose Φkl ∼ Dirichlet(β);
2. For user ui, choose pi ∼Dirichlet(αU );
3. For item vj, choose qj ∼Dirichlet(αI );
4. For ratingXij
5. Choose a user group z U ij ∼Multinomial(pi)
6. Choose an item group z I ij ∼Multinomial(qj)
7. Choose a ratingXij ∼Multinomial(ΦzU ij zI ij )

where Φ is a K×L×R tensor and Φkl is the rating-scale mixing proportion of user-item joint group (k, l) over {1, . . . , R} (i.e., ∑Rr=1 Φkl[r] = 1); pi is the membership of user ui over K user groups and qj is the membership of item vj over L item groups (i.e., ∑k pi[k] = 1 and ∑l qj[l] = 1); the ith row in P is p⊤i and the jth row in Q is q⊤j .

We can use the collapsed Gibbs sampler for inferring the latent variables z = {zU , zI }, where zU = {z U ij }(N,M) (i,j)=(1,1) and zI = {z I ij }(N,M) (i,j)=(1,1) . Here we directly gives the conditional distribution for each latent variable pair (z U ij , z I ij )

where n¬(ij) klr denotes the counter of all the ratings which fall in the cell (k, l, r), except for Xij . Similar definitions are applicable for the other counters in (2) and (7).

We can predict a rating in X by ˆXij = p⊤i Bqj , where

B is the group-level rating matrix and pi is the user-group membership of user ui over K user groups.

4.2 Cross-Domain CF Over Time

As we have shown at the end of Section 3, our goal is to learn a group-level rating matrix B shared across temporal domains and p(t) i for user ui's user-groupmembership at temporal domain t, for i = {1, . . . , N} and t = {1, . . . , T}. If we simply view the counterparts of each user as different users, we can directly use Bi-LDA to simultaneously model T rating matrices {X(1) , . . . ,X(T) } within the cross-domain CF framework [Li et al., 2009]. The result by doing so is that we can still learn B and {P(1) , . . . ,P(T) }, but the user-group memberships of a certain user's counterparts over temporal domains will have no relatedness. Besides, in this case, since the rating knowledge can not be transferred by explicitly connecting user counterparts of successive temporal domains, the data sparsity problem may become even severe.

To build the relatedness of a user's counterparts in successive temporal domains, we can impose dependence on usergroup memberships of the successive counterparts. Given that our base algorithm is Bi-LDA which is a Bayesian model, a straightforward method for feeding knowledge is to use priors. We adopt a simple strategy that can transfer the usergroup membership knowledge of user counterpart u(t-1) i to u(t) i . That is to draw p(t) i from a Dirichlet prior parametrized by p(t-1) i , i.e., p(t) i ∼ Dirichlet(p(t-1) i ). However, since membership vector is normalized (i.e., ∑k p(t) i [k] = 1, p(t) i [k] ≤ 1), which can make the prior distribution highly concentrated on few components. To avoid this, we introduce a weighting parameter λ to scale the prior

The intuition of λp(t-1) i and λq(t-1) j can be interpreted as the prior observed counts of ratings in K user groups before any rating from current temporal domain is observed [Steyvers and Griffiths, 2007; Wei et al., 2007]. Due to the changes of the priors for generating user/item-group memberships, the conditional distribution (2) is changed accordingly

where the counters nikt and njlt get an additional temporal dimension. Note that the first term remains the same as that in (2) since the group-level rating matrix B is independent of time and shared across temporal domains. So in the crosstemporal-domain setting, B can still be constructed by using (3). While user/item-group memberships for user/item counterparts over temporal domains are constructed differently

The main idea of the proposed approximation inference strategy for CF across temporal domains is straightforward. We name it rating-matrix generative model over time (RMGM-OT), which comprises the following two alternating steps:

• Step 1 [Cross-Domain CF] Perform one epoch of Gibbs sampling over {X(1) , . . . ,X(T)} using (7) by viewing all the user/item counterparts as different users/items (i.e., RMGM over temporal domains). Go to Step 2.

Step 2 [Time-Dependent Priors Update] After an epoch of Gibbs sampling, update {P(1) , . . . ,P(T)} and {Q(1) , . . . ,Q(T)} using (8) and (9), respectively. These will be the user/item-group membership priors for the next Gibbs sampling epoch. Go to Step 1.

In the first Gibbs sampling epoch, the user/item-group membership prior parameters are initialized as αU and αI . The prior for the mixing proportion of rating scales of user-item joint group is set to β through all the Gibbs sampling epoches. In practice, the Gibbs sampler converges after hundreds of epoches. After inference, we can construct B using (3), and predict the rating X(t) ij , which is provided by user ui on item vj in temporal domain t, by using (1).

Modeling User-Interest Drift

With B and {P(1) , . . . ,P(T)}, we can finally model userinterest drift over time. The group-level rating matrix B reflects each user prototype's interest over item groups, while p(t) i is the user-groupmembership for user ui at temporal domain t. Thus, the user-interest component of user ui at temporal domain t should be B⊤p(t) i . By constructing all the user-interest components in T temporal domains for user ui, we can track user ui's interest drift over time

where Di is an L × T interest-drift matrix for user ui over T temporal domains. Each column in Di can be interpreted as the expected ratings provided by user ui on all the L item groups at temporal domain t. If we list some top items in each item group, we can intuitively find which kinds of items that a user may like most at certain time slices.

5 RelatedWork

The proposed method is based on the latent factor model (LFM). The first well-known work which applied LFM for collaborative filtering is probabilistic Latent Semantic Analysis (pLSA) [Hofmann, 1999]. Later, the LFMs with two sets of latent variables, associated to users and items respectively, were also proposed for CF [Si and Jin, 2003; Porteous et al., 2008]. Recently, many Bayesian extensions of pLSA [Steyvers and Griffiths, 2007] have been extensively adopted for CF, including Bi-LDA [Porteous et al., 2008], which is used as the base algorithm in our method.

Our work is also related to temporal and evolutionary CF methods. The most well-known work in this line is TimeSVD++ [Koren, 2009], in which a user/item feature is a combination of one static component and one time-dependent component. Online evolutionary CF [Liu et al., 2010] is memory-based and able to run in incremental mode. [Xiong et al., 2010] views temporal domain as a third dimension and use tensor factorization to factorize the temporal components. [Khoshneshin and Street, 2010] dynamically assigns users/items to different clusters based on evolutionary co-clustering. However, the temporal features/components in these methods cannot be interpreted for user interests.

Another related topic is transfer learning. We have shown in Section 3 that the proposed method is within the crossdomain CF framework [Li et al., 2009] in which a grouplevel rating matrix is shared. Moreover, we impose temporal dependence on user/item memberships such that temporal knowledge can be taken into account. Our method can combine rating data from multiple domains and simultaneously learn model for each domain by sharing parameters, so it fits the multi-task learning setting [Pan and Yang, 2010]. [Zheng et al., 2008] also consider knowledge transfer over temporal domains, but it is based on hidden Markov models.

Finally, our work is related to user-interest tracking in CF. Few works have been reported in this line. [Ma et al., 2007] is one such work but it is a hybrid CF method using content information. To the best of our knowledge, the proposed method is the first work that can explicitly model user-interest drift over item groups in collaborative filtering.

6 Experiments

6.1 Data Preparing

We use the Netflix 1 prize data set in our experiments. The entire data set comprises over 100 million ratings provided by ∼480,000 users on ∼17,000 movies between 1999 and 2005. Each rating is associated with a time-stamp. In order to vividly demonstrate the drifting of user interests over time, we conduct the following data preprocessing steps:

1. We discard the ratings before 2002 and split the remaining time span (Jan 2002 - Dec 2005) into 16 equal time slices. Each time slice corresponds to exact three months. Then, we replace the original time-stamp of each rating with the time-slice index in {1, . . . , 16}.
2. We only consider the users who registered in Netflix before 2002 and were still active in 2005 (based on the time-stamps of their first/last rating). We further select the users who have more than 100 ratings in total and have at least 15 ratings in 4 time slices. As a result, we obtain 6784 users for our experiments.
3. We only consider the movies which were imported into Netflix before 2002. We further select the movies whose associated ratings are more than 50. As a result, we obtain 3287 movies in our experiments.

After data pruning, we obtain a 6784 × 3287 rating matrix whose elements are associated to 16 time slices (temporal domains). We pick the first 4 temporal domains for validation and the remaining 12 temporal domains for evaluation.

1 www.netflix.com

6.2 Evaluation Protocol

We randomly extract 20% ratings from the evaluation data set for training (density 0.9%) while the remaining ratings are used for test. This procedure is repeated for 5 times and all the reported results in Figure 2 and Table 2 are the average performance over 5 trials. The performance evaluation metric we adopt in our experiments is the root mean squared error (RMSE): √∑i∈S (ri - ˆ ri)2 /|S|, where S denotes the set of test ratings, ri is the ground truth and ˆ ri is the predicted rating. A smaller value of RMSE indicates a better performance.

6.3 Parameter Selection

We simply set the hyper-parameters of the Dirichlet priors, αU , αI , and β, to 1, according to [Porteous et al., 2008].

The numbers of user and item groups, K and L, are selected in {20, 50, 100} and the results are in Table 1. We find that the performance reduces gradually as K and L become larger. This result may be caused by model overfitting if the latent dimensions are too many. We set K = 20 and L = 20.

Another parameter λ is used for tuning the concentration of the Dirichlet priors. We select λ in {0.1, 1, 10, 100, 1000} and report the results in Table 1. We find that the performance increases gradually until λ = 100 and then reduces a little, which implies λ is a tradeoff parameter: A larger λ will feed more knowledge of domain t - 1 to domain t and smooth P(t) and Q(t) in all temporal domains, but it may discard too much rating knowledge of the current domain t; while a smaller λ will make the model of domain t emphasize the data in domain t and absorb less knowledge from domain t - 1, but it may lead to model overfitting. We set λ = 100.

6.4 Performance Comparison

We compare the performance of the following methods: 1) Weighted low-rank approximations (WLRA) [Srebro and Jaakkola, 2003], 2) Bi-LDA [Porteous et al., 2008], 3) TimeSVD++ [Koren, 2009] (temporal), and 4) our method RMGM-OT (temporal). WLRA is an effective yet simple method which is broadly adopted as a baseline. Bi-LDA is the non-temporal version of our method. TimeSVD++ is the state-of-the-art temporal CF technique and can thus be the baseline of temporal CF methods.

Figure 2 and Table 2 report the comparison results on the evaluation data set. In Figure 2, we calculate RMSE in each temporal domain and plot the performance curves of the compared methods. We find that the four methods have similar performance in the first 6 temporal domains and widen the difference in the last 6 temporal domains. The curves of Bi-LDA and RMGM-OT are very similar. TimeSVD++ performs a little worse than our method on this data set. The overall performance over all 12 temporal domains in Table 2 also gives the same result, i.e., Bi-LDA and RMGM-OT have the best performance. The experimental results show that our method can achieve state-of-the-art performance.

6.5 User-Interest Drift Analysis

Finally, we visualize the RMGM-OT learning results to show that the proposed method can indeed capture users' interest drift over temporal domains. In Figure 3, we plot some usergroup membership components P⊤ = [p(1) , . . . , p(12) ] (upper row, each subplot shows a P⊤) and the corresponding user-interest components D = [B⊤p(1) , . . . ,B⊤p(12) ] (bottom row, each subplot shows a D). From these plots, we can investigate how user switch their user groups from time to time and change their interests over movie groups accordingly. For example, the second user switches his/her group membership between user groups 13 and 16. When he/she belongs more to user group 13, he/she would show more interest in movie group 5. The third user spans three user groups. When he/she belongs more to user group 17, he/she would show a broad interest in most movie groups.

We can also observe that, a user's user-group memberships in successive temporal domains are smooth. In other words, users don't switch their groups frequently. This phenomenon should be the result of the imposed dependence between successive user-group memberships (5).

7 Conclusion

In this paper, we proposed a cross-domain CF method over temporal domains, in which each user has multiple counterparts over temporal domains and successive counterparts are closely related. We adopted the cross-domain CF framework to share the static group-level rating matrix across temporal domains while let user-group memberships drift slightly between successive temporal domains. The derived method is based on a latent factor model. The experimental results have shown that our method can not only achieve state-of-the-art recommendation performance but also explicitly track and visualize user-interest drift over time.

8 Acknowledgments

This work was supported by Australian Research Council's Discovery Project (No. DP1093762) and Future Fellowship (No. FT100100971), the National 973 Program of China (Nos. 2010CB327906 and 2009CB326203), and the NSF of China (Nos. 60873178 and 60828005).