Predictive Collaborative Filtering with Side Information

1 Introduction

Item-based recommender systems aim to recommend new items to a target user based on the user's previous recommendation activities (e.g., previous purchases, ratings, or clicks) [Sarwar et al., 2001; Blei et al., 2003; Deshpande and Karypis, 2004; Ostuni et al., 2013]. Recommending a ranked list of new items, which may be very attractive to the user but have not been observed in the user's previous recommendation activities, can encourage additional purchase or visits, which is very important in real application scenarios. Recommender systems have been popularly studied due to their important impacts in E-commerce platforms such as Amazon and eBay, social networks such as Facebook and LinkedIn, and search engines such as Google and Bing [Ricci et al.,

2011]. A variety of works have been developed in the literature to address different recommender systems such as movie recommendations [Park and Pennock, 2007; Koren, 2008; Rendle et al., 2009; Kabbur et al., 2013], book recommendations [Ning and Karypis, 2012], music recommendations [Ning and Karypis, 2011], advert recommendations [Stern et al., 2009], news recommendations [Pan et al., 2008] and channel/program recommendations [Hu et al., 2008].

There are many different recommendation approaches, including content filtering-based approaches [Mooney and Roy, 2000; Pazzani and Billsus, 2007] and collaborative filtering-based approaches [Sarwar et al., 2001; Deshpande and Karypis, 2004; Hofmann, 2003]. The content filteringbased approaches make recommendations to a target user by only using this particular user's profile information (e.g., previous recommendation activities), while the collaborative filtering-based approaches also exploit other users' profile information. Usually, these recommender systems work on the user-item recommendation matrix and generate a list of top-N potential interesting items with the highest recommendation scores for each target user from the user's non-recommended item pool. They typically retrieve relevant interesting items for target users by only using users' history recommendation activities on items, but ignoring the existing valuable side information such as the reviews for books, or the plots for the movies, which limits their recommendation capacity and performance.

In this paper, we propose a novel predictive collaborative filtering approach to generate a list of top-N items with the highest recommendation scores for each target user. The proposed approach exploits the item-based side information in addition to the conventional user-item recommendation matrix. To be more specific, it automatically identifies the recommendation scores for non-recommended items via lowrank aggregation over the users' already-recommended items to recover the full recommendation matrix for all items. Simultaneously, it incorporates the item-based side information as an item-feature matrix and trains a regularized linear regression model to predict the recommendation scores from the item features for each user. We formulate this simultaneous user-item matrix self-recovering and predictive regression model training process as a joint low-rank constrained minimization problem, and derive an efficient analytical solution for it. To evaluate the proposed approach, we conduct a set of experiments on a number of real world Amazon datasets with recommendation items such as books, beauty products, etc. The experimental results demonstrate that the proposed approach is very effective and efficient in producing top-N recommender systems, and achieves superior recommendation performance than the comparison methods.

2 RelatedWork

A variety of works have been developed in the literature to address item-based recommender systems. We provide a brief review below on the most related collaborative filtering approaches and side information assisted approaches.

Collaborative filtering approaches make recommendations by using both the target user's previous recommendation activities and other users' history behaviors [Su and Khoshgoftaar, 2009], which include two groups of methods, neighborhood-based methods [Sarwar et al., 2001; Deshpande and Karypis, 2004; Kabbur et al., 2013] and latent factor-based methods [Blei et al., 2003; Hofmann, 2003; Rennie and Srebro, 2005; Salakhutdinov et al., 2007; Weimer et al., 2007; Koren et al., 2009; Cremonesi et al., 2010; Sindhwani et al., 2010].

Neighborhood-based collaborative filtering methods make recommendations by exploiting similarities among items within the user-item recommendation matrix. Once item-item similarities are computed, the prediction on a new item for a user is obtained by considering the particular user's past recommendation activities on similar items. For example, the work in [Sarwar et al., 2001] proposed to use similarityweighted sum prediction to recommend new items for a target user. In order to measure the item-item similarities, various similarity schemes have been investigated, including cosine similarity, correlation similarity, adjusted cosine similarity [Sarwar et al., 2001], and conditional probability similarity [Deshpande and Karypis, 2004].

Unlike the neighborhood-based methods, which directly employ the user-item recommendation matrix for prediction, the latent factor-based collaborative filtering methods first identify a set of latent factors for users and items respectively. They then train a prediction model on the latent space to make recommendations. In order to identify the latent factors, a variety of models have been employed, including the pure singular value decomposition (PureSVD) method [Cremonesi et al., 2010], the Gaussian probabilistic latent semantic analysis method [Hofmann, 2003], the latent Dirichlet allocation method [Blei et al., 2003], the matrix factorization method [Koren et al., 2009], the maximum margin matrix factorization methods [Rennie and Srebro, 2005; Weimer et al., 2007], the pairwise comparison method [Rendle et al., 2009], the restricted Boltzmann machines [Salakhutdinov et al., 2007], and the weighted non-negative matrix factorization method [Sindhwani et al., 2010].

In addition to these two groups, some other collaborative filtering recommender systems have also been developed in the literature [Koren, 2008; Ning and Karypis, 2011; Shi et al., 2012]. Koren (2008) proposed an asymmetricSVD based hybrid approach to address recommendation problems, which combines the similarity-based neighborhood method and the latent factor-based method together for recommendations. Ning and Karypis (2011) proposed a sparse linear method to address top-N recommendation problems, which computes the recommendation score on a non-purchased/non-recommended item for a target user using sparse aggregation of purchased/recommended items of the particular user. Shi et al. (2012) proposed a collaborative less-is-more filtering approach, which maximizes the mean reciprocal rank to address recommendation problems in social networks.

Different from collaborative filtering approaches, which only exploit previous recommendation activities in user-item matrix, side information assisted approaches also exploit additional meta-data information (e.g., product reviews, film plots, etc) to recommend new items for a target user [Stern et al., 2009; Gunawardana and Meek, 2009; de Campos et al., 2010; Ning and Karypis, 2012]. Stern et al. (2009) proposed to use both user meta-data such as a user's job, age, gender and id, and item meta-data such as a movie's genre and id. They represented these meta-data as feature vectors for the users and items respectively and incorporated the meta-data information into the collaborative filtering recommender system. The work in [Gunawardana and Meek, 2009] incorporated both the user-item recommendation information and the item meta-data into a unified Boltzmann machine to form a hybrid recommender system. Similarly, the work in [de Campos et al., 2010] developed a hybrid recommender system based on Bayesian networks over user nodes, item nodes, and item-feature nodes. The approach propagates content-based information from recommended items to nonrecommended items via the item-feature nodes, and propagates collaborative-based information via item nodes. Ning and Karypis (2012) proposed to incorporate item-based side information into the sparse linear method [Ning and Karypis, 2011] to learn the aggregation coefficient matrix and address top-N recommendation problems, which has demonstrated superior performance over conventional recommender systems without side information. Different from these previous methods, our proposed approach performs a joint predictive recovery of the user-item matrix for top-N recommendations by integrating the partially observed user-item matrix and the item-based side information such as reviews in a discriminative and mutually complementary manner.

A few recent works [Bao et al., 2014; McAuley and Leskovec, 2013; Xu et al., 2014] have exploited user reviews for building recommender systems, while [Chen et al., 2015] provides a survey of such recent attempts. However most of these methods require the reviews to be directly associated with the user ratings, while our approach treats reviews as side information and can exploit reviews from auxiliary resources that have no direct relationships with the target users.

3 Proposed Approach

In this section, we present the proposed predictive collaborative filtering approach for item-based top-N recommender systems. We assume an observed item-user recommendation matrix Y 2 Rn⇥t , which contains the observed recommendation (or purchase) activities of t users over n product items. In this matrix, an observed entry Yij (with an indicator value 1 or a positive recommendation score) indicates the i-th product item has been recommended (or purchased) by the j-th user, while an unobserved entry Yij = 0 only indicates an unknown relationship between the j-th user and the i-th product item, i.e., the recommendation (or purchase) action of the jth user over the i-th item has not been observed in the user's past recommendation activities, but it is possible that the j-th user can be interested in the i-th item. As item-based side information in the form of product reviews for E-commerce applications or film plots for movie recommendations exists in many application domains, we take the item-based side information into account as well. In particular, we assume there is an item-feature matrix X 2 Rn⇥d , whose each row contains a feature vector for the corresponding product item and presents the item-based side information. We aim to automatically identify the most promising interesting product items, in particular the top-N items, for each target user from his non-recommended items by using both the observed itemuser recommendation matrix Y and the item-feature matrix X. Below we first present a matrix self-completion component based on the item-user recommendation matrix, and then incorporate the predictions from the item-feature matrix to form a joint prediction model. We finally derive a convenient analytical solution for the proposed joint learning method.

In the rest of the paper, we use 1 to denote a column vector of all 1s, while assuming the size of the column vector can be inferred from the context. We use In to denote an identity matrix with size n. For any matrix X, kXkF denotes its Frobenius norm, and X denotes its pseudo-inverse.

3.1 A Joint PredictionModel

Given the past recommendation/purchase activities in the observed item-user recommendation matrix Y , the recommendation score on a non-recommended/non-purchased item vi for a user uj can be calculated as a linear aggregation of the items that have already been recommended/purchased by uj , that is, e Yij = w>Y:j , where Y:j denotes the j-th column of Y . Such a linear recovery model can be built for all items with e Y:j = WY:j, while the linear functions have to be learned from the statistical item aggregation relationships existed in the observed data for all the users. This leads to a matrix selfrecovery (self-completion) formulation e Y = WY , where W is an n⇥n linear aggregation coefficient matrix that is shared across all the t users. A meaningful matrix self-recovery should automatically complete the unobserved recommendation scores in the matrix without affecting much the observed recommendation scores. We hence enforce the self-recovered item-user matrix to maximally preserve the original matrix values and formulate the self-recovery model as the following learning problem

To avoid the trivial solution of setting W as an identity matrix, we assume the coefficient matrix W should be low rank and encode this low rank property using a rank constraint with a hyperparameter λ. This low rank property can also allow the model to implicitly exploit the latent low-dimensional representations of the items.

In addition to the item-user recommendation matrix Y , we also have explicit item-based side information available as an item-feature matrix X, where each item feature vector describes the properties of a given product item. Note that this product item side information is common to all users. But different users may have different tastes over the same product item. The recommendation scores of each user over the set of product items depend on the properties of the product items. Hence we propose to predict the recommendation score of each user over a product item from the feature vector of this product item. In particular, we can use a linear regression model, fj(x) = x>q + b, for the j-th user to predict his or her recommendation score y from the item feature vector x. Given the observed item-feature matrix X and the recovered item-user recommendation matrix e Y , the linear regression model fj for the j-th user can be trained on the data by minimizing a least squares regression loss kXq+b1- e Y:j k2 over the model parameters q and b. Thus the linear regression model is specifically tailored to the j-th user and can help to capture user-specific preferences of the product items when making recommendations. For all the t users, we will train t linear regression models from the data by minimizing the following regularized least squares loss function

where Q 2 Rd⇥t and b 2 Rt are the model parameters for the t linear regression models, such that fj(x) = x>Q:j +bj for the j-th user.

Since e Y = WY is a self-recovered matrix via Eq. (1), by integrating the recommendation matrix recovery in Eq. (1) and the linear regression model training in Eq. (2) together, we formulate a joint recommendation prediction model as follows to perform joint recommendation score prediction in a mutually complementary manner

where β and γ are the trade-off parameters. By solving this joint minimization problem, we expect to integrate both the existing recommendation activity information and the itembased side information to predict the recommendation scores of each user over his or her non-recommended/non-purchased items. The top-N recommendations for a user uj can be produced by sorting uj's non-recommended/non-purchased items in a decreasing order based on their predicted recommendation scores.

3.2 Learning Algorithm

The learning problem in Eq. (3) is a joint minimization problem over both the linear regression model parameters ¶Q↪ b♦ and the linear aggregation coefficient matrix W. We first perform minimization over the linear regression model parameters assuming fixed W, which produces the following closedform solutions for Q and b,

Algorithm 1 Learning Algorithm

Procedure:

1. Compute auxiliary matrices F and S with Eq. (7)
2. Perform singular value decomposition over F and Y , compute PF↪L and PY↪R, and let M = PF↪LSPY↪R.

where H = In - 1n 11> is a centering matrix.

1. Compute a solutionW ⇤ using Eq. (9), and set e Y ⇤ =W ⇤Y .

By plugging the solutions for the regression model parameters Q in Eq. (4) and b in Eq. (5) back into the objective function in Eq. (3), the joint learning problem in Eq. (3) can be equivalently reformulated into the following minimization problem over W ,

where A = (X>HX +βId)-1X>H and B = H (XA - In). By further introducing the following replacement matrices,

where O(n+d)⇥t denotes a (n + d) ⇥ t matrix with all 0s, the problem (6) can be rewritten as

Though the optimization problem in (8) is still a non-convex optimization problem due to the rank constraint, below we will derive a convenient analytical solution for it.

For matrix F , we denote its thin SVD as F = UF⌃F V > F . Two projections can be defined consequently as PF↪L := UF U > F and PF↪R := VFV > F . Similarly, we can define projections PY↪L and PY↪R for matrix Y . We then have the following theorem.

Theorem 1 For N 3 λ  rank(PF↪LSPY↪R), let M = PF↪LSPY↪R, then

is a solution to the minimization problem in (8), where the operation M(λ) extracts the truncation of M by setting all of its singular values as zeros except the λ largest ones, i.e.,

M = UM⌃MV > M ↪ M(λ) = UM b⌃M(λ)V > M ↪ (10) and b⌃M(λ) is the truncation of ⌃ by keeping only the largest λ diagonal values of ⌃ and setting all others as zeros. The solution is unique iff the λ-th and (λ + 1)-th largest singular values of M are different.

Theorem 1 was proved by Sondermann [Sondermann, 1986] and Friedland&Torokhti [Friedland and Torokhti, 2007]. It provides an analytical closed-form solution for our rank constrained minimization problem (8). The overall learning algorithm is summarized in Algorithm 1.

The complexity of Algorithm 1 is dominated by the three singular value decomposition operations on F↪ Y and M respectively. This leads to a computational complexity of O ((2n + d)n2 + min(n2 t↪ nt2 ) + min((2n + d)2 t↪ (2n + d)t2 )) for the proposed algorithm when a standard full SVD algorithm is used [Brand, 2006]. Moreover, based on the definitions of F and S in Eq.(7) and the definition of M in Theorem 1, it is easy to conclude that rank(F) = n and rank(M)  rank(S)=rank(Y ). The item-user recommendation matrix Y is typically low rank due to the existence of dependencies and correlations among the users' activities. Hence if r=rank(Y ), one could have r ⌧ min(n↪ t). In this case, the computational complexity of Algorithm 1 can be further reduced to O ((2n+d)n2 + r(3n+d)t) by using a fast SVD algorithm in [Brand, 2006].

After obtaining the solution W ⇤ in Eq. (9) for the coefficient matrix, we can get the recovered item-user recommendation matrix e Y ⇤ by setting e Y ⇤ = W ⇤Y , which contains the predicted recommendation scores for the originally non-recommended/non-purchased items of each user. We then perform top-N recommendation in the following way. For the j-th user, e Y ⇤ :j denotes his predicted recommendation scores over all the product items. We rank the scores for nonrecommended items in a non-increasing order and consider the first N items as the predicted recommendation items.

4 Experiments

In this section, we present our empirical evaluations and discussions of recommender systems on real-world datasets.

Datasets

We conducted experiments on five real-world Amazon datasets [McAuley and Leskovec, 2013], Beauty, Office, Sports&Outdoors, Gourmet Foods and Health, each of which corresponds to one category of Amazon products. For each category, the original dataset contains transactions between different product items and users, indicated with non-zero multivariate rating values. We converted the multivariate rating values to 1s and filtered those less popular product items and users that appeared less than three transactions to construct the item-user recommendation matrix. The statistic summary of the produced datasets is presented in Table 1. For each dataset, we present the number of items (#items), the number of users (#users), the number of transactions (#trns), the average number of transactions for each item (#rsize), the average number of transactions for each user (#csize) and the density value (#trns/(#users⇥#items)).

Item-based Side Information

For each dataset, we used the product reviews as the itembased side information for the product items. We extracted the unigram features from the review articles with stopwords being removed. We further selected the most frequent 5000 unigram features as the item features and represented each product item as a bag-of-word feature vector with termfrequency feature values (Ftf). We denote the recommender systems without item-based side information as Fno.

Comparison Approaches

We compared our proposed approach with the following approaches for recommender systems: (1) Pure Singular Value Decomposition (PureSVD), which is a baseline collaborative filtering method based on singular value decomposition [Cremonesi et al., 2010]; (2) Bayesian Personalized Ranking for matrix factorization (BPRMF), which exploits pairwise comparison [Rendle et al., 2009]; (3) Sparse Linear Model (SLIM), which learns a sparse coefficient matrix to induce recommendation scores [Ning and Karypis, 2011]; and (4) Collective Sparse Linear Model (cSLIM), which incorporates item-based side information into the SLIMmodel to generate the top-N recommendations [Ning and Karypis, 2012]. These methods address collaborative filtering from different aspects and have demonstrated effective performance in the literature.

Evaluation Criteria

We used the commonly used leave-one-out cross validation to evaluate the performance of each recommendation algorithm over five runs. For each run, we randomly chose one transaction for each user and put it into the test set. The training set is the masked item-user transaction matrix with the transactions of the test set removed. We ran each recommender system five times based on random partitions of the training and test sets. The evaluation is conducted on the top-N items recommended for each user by the recommender system. We set N=10 and used the following two criteria to evaluate the top-N recommendation performance: the Hit Rate (HR) and the Average Reciprocal Hit-Rank (ARHR) [Deshpande and Karypis, 2004],

where #users is the number of users, #hits is the number of users with the test item recommended in the top-N list, and pi is the position of the item in the top-N ranked list. Larger HR and ARHR values indicate better performance.

4.1 Experimental Results

We compared the five comparison methods (PureSVD, BPRMF, SLIM, cSLIM, Proposed) on the five datasets using the evaluation criteria presented above. The average comparison results for all these methods in terms of HR and ARHR are presented in Table 2. We can see that the baseline PureSVD method does not work well on all the datasets comparing to the other systems, which shows that the pure singular value decomposition-based collaborative filtering method is far from enough to develop a good recommender systemwithout using other information. The BPRMF and SLIM methods on the other hand work much better than the PureSVD method on all the datasets in both measurements. The cSLIMmethod, which utilizes item-based side information, outperforms PureSVD, BPRMF and SLIM across all cases except on Health in terms of ARHR. This shows that the item-based side information is useful for improving the recommendation performance. Our proposed approach on the other hand consistently produced the best results among all the comparison methods on all the five datasets in terms of both measurements. This demonstrates that our proposed approach provides an effective mechanism to integrate information from the item-user matrix and the item-based side information for producing top-N recommender systems.

Moreover, we also recorded the model learning time and the recommendation test time for all the comparison approaches in all these experiments. These running times are reported in Table 2 as well. We can see that with an analytical solution our proposed method is very efficient in learning. It significantly reduced the training time by comparing not only to the cSLIM method which also utilizes item-based side information, but also to SLIM and BPRMF that are not able to incorporate side information. On the datasets with larger recommendation matrices such as Gourmet Foods and Health, the differences between the model learning times of the proposed method and the cSLIM method are quite dramatic. Though the PureSVD method runs faster than our proposed approach, this baseline cannot exploit side information and produced very poor performance. Our proposed approach on the other hand maintains both efficiency and effectiveness. All these results demonstrate that the proposed approach is an effective and efficient state-of-the-art solution for top-N recommender systems.

4.2 IntegrationModel Study

To verify the effectiveness of the integration mechanism of the proposed joint model, we also compared the two individual components, the self-completion component and the sideinformation based prediction component, to the proposed joint model in terms of top-N recommendation performance. The comparison results in terms of HR and ARHR are reported in Table 3. We can see that the proposed joint model consistently outperforms both of the individual components. With each component alone, the model cannot achieve a state-of-the-art performance. This suggests that our proposed model provides an effective integration over the individual information sources.

5 Conclusion

In this paper, we presented a novel joint prediction approach that exploits both the conventional user-item recommendation matrix and the item-based side information in a complementary manner to generate top-N recommendations for target users. We formulated the simultaneous user-item matrix recovering and item-based linear regression model training process as a joint low-rank constrained minimization problem, and derived an analytical closed-form solution for it. We conducted a set of experiments on five real world Amazon datasets with different recommendation items. The experimental results demonstrated that the proposed approach is effective and efficient in producing top-N recommender systems, and outperforms the comparison methods.

Acknowledgments

This research was supported in part by NSF IIS-1422127.