Learning Discriminative Recommendation Systems with Side Information

1 Introduction

Top-N recommendation systems automatically predict the missing recommendation scores over the set of product items for each consumer, and recommend a short list of N items with highest scores to each consumer. With the increasing popularity of online shopping, effective top-N commercial recommendation systems become of great importance in helping consumers to find their interested items and hence encouraging online item purchases. For example, a top-N recommendation system can effectively help consumers to find their potential interested products from Amazon.com and buy them online, and help users to find movies that best match their interests on Netflix. In such real world application domains, effective top-N recommendation systems can make significant commercial impacts.

Many algorithms have been developed in the literature to build top-N recommendation systems [Ricci et al., 2011].

Yuhong Guo

School of Computer Science Carleton University, Ottawa, Canada yuhong.guo@carleton.ca

Most of them use a user-item rating matrix to build the recommendation models. A classical technique is collaborative filtering (CF) [Schafer et al., 2007], which models the relationships between users and the correlations between items to identify new user-items relationship scores. Ranking methods have also demonstrated good performance for top-N recommendations [Weimer et al., 2008; Steck, 2010; Chen and Pan, 2013; Aiolli, 2014; Park et al., 2015]. In addition to CF and ranking, sparse aggregation methods that exploit linear correlations between items have been explored in a few works to improve top-N recommendation performance [Ning and Karypis, 2011; Cheng et al., 2014; Kabbur et al., 2013; Christakopoulou and Karypis, 2014]. Nevertheless, all these methods focus solely on the user-item rating (or purchase) matrix, without exploring any additional information.

In many applications, in addition to the user-item rating or purchase matrix, item-based side information such as product reviews, book reviews, item comments, and movie plots can be easily collected from the Internet. This abundant itembased information can be used for recommendation systems. The work in [Mooney and Roy, 2000] used book titles, reviews, and comments as item features; the work in [Melville et al., 2002] used item contents to enrich the sparse rating matrix. These recommendation systems however either only focus on user profiles or item contents without fully considering the user-item rating matrix or simply use item contents to preprocess the sparse rating matrix to produce small improvements. Moreover, they have not addressed the top-N recommendation problems. A recent work [Ning and Karypis, 2012] incorporated item-based side information to improve top-N recommender systems, which however assumes that user-item matrix and item-based side information matrix are reproduced by the same linear aggregation model and does not exploit the discriminative power of the side information.

In this paper, we propose a joint discriminative prediction model that exploits both the partially observed user-item recommendation (rating/purchase) matrix and the item-based side information such as item contents (product reviews and movie plots) to build top-N recommendation systems. The item information used in this work can be viewed as descriptions of the items and hence can produce feature representation vectors for the items. We propose a novel component that predicts the user-item recommendation (purchase) scores discriminatively from the item features with linear regression models, and integrate this component together with an aggregation model on the user-item matrix to jointly predict the unknown user-item recommendation scores. The joint prediction of the recommendation scores from both information sources is expected to increase the performance of topN recommendation systems. We formulate this joint prediction model as a convex minimization problem, which can be solved using a projected gradient descent algorithm. We evaluate the proposed approach by conducting experiments on several real world datasets. The experimental results show that the proposed approach can outperform both popular topN recommendation methods that only use user-item matrix and state-of-the-art algorithms that exploit additional side information. Moreover, our empirical study also reveals an interesting observation: the discriminative prediction component that predicts the recommendation scores from the item features (i.e., side information) contributes to most of the recommendation capacity of our joint prediction model, and the prediction component itself already outperforms other comparison methods. This observation encourages researchers to explore prediction models for building top-N recommendation systems.

2 RelatedWork

In this section, we review related works, including standard top-N recommendation systems and recent recommendation approaches that exploit item-based side information.

Collaborative filtering (CF) technology is widely used in top-N recommendation systems. CF methods, which explore the purchase history of all the users, relationships between the users and correlations between the items, can be divided into two types, neighborhood-based CF and modelbased CF. Neighborhood-based CF methods exploit similarities between all the items and users to make recommendations [Deshpande and Karypis, 2004; Verstrepen and Goethals, 2014]. Model-based CF methods learn latent factors for users and items to reconstruct the user-item matrix. For example, the work in [Cremonesi et al., 2010] developed a singular value decomposition (SVD) method to directly learn latent user factors and item factors. Though simple, this method has good performance for top-N recommendations. In [Hu et al., 2008; Sindhwani et al., 2010], a weighted regularized matrix factorization (WRMF) model is formulated to learn the latent factors based on implicit user-item feedbacks. The work in [Shi et al., 2012b] proposed to learn the latent factors by directly maximizing the mean reciprocal rank. The work in [Liu and Aberer, 2014] addressed top-N recommendation in dynamic situations.

Weimer et.al [Weimer et al., 2008] considered the top-N recommendation problem as a ranking problem, and used maximum margin matrix factorization to optimize ranking scores instead of rating scores. Following this work, a number of methods have been developed in this direction. The authors of [Rendle et al., 2009] proposed a Bayesian personalized ranking optimization method for item recommendation with matrix factorization. The work in [Steck, 2010] addressed top-N item recommendation in the non-random missing situation by optimizing the metric of area under top-N curve. The work in [Chen and Pan, 2013] assumed that a user's preference is on a set of products instead of only one, and proposed to learn pairwise preferences over item-sets. The work in [Aiolli, 2014] focused on implicit feedbacks where preferences are given in the form of binary ratings, and proposed to optimize the ranking score within a margin maximization paradigm. The authors of [Park et al., 2015] developed a large-scale optimization algorithm for ranking based matrix completion.

In addition to collaborative filtering and ranking methods, a few sparse linear aggregation methods have recently been developed in the literature. The work in [Ning and Karypis, 2011] proposed a novel sparse linear method (SLIM) to perform top-N recommendation. It learns a sparse aggregation coefficient matrix for items by solving an ℓ1-norm and ℓ2norm regularized optimization problem, and aggregates the user purchase/rating profiles to produce the top-N recommendations. The work in [Kabbur et al., 2013] developed a factored item similarity model to tackle the situation where useritem matrix is very sparse and the SLIM method may fail to capture the item-item similarity. It learns the similarity matrix as the product of two low dimensional latent factor matrices and overcomes the sparsity problem. The work in [Cheng et al., 2014] proposed a low rank SLIM method to improve SLIM, which adds a nuclear norm constraint to enforce a low rank aggregation matrix. The methods in [Christakopoulou and Karypis, 2014] extend item pairwise similarities to higher orders, and capture more information with high order item correlations to better reconstruct the user-itemmatrix. In [Sedhain et al., 2016], the authors exploit user-user similarities instead of item-item similarities to produce recommender systems based on linear logistic regression.

Instead of only focusing on the user-item matrix, a few works in the literature have incorporated contextual information [Zheng et al., 2014; Shi et al., 2012a], user social networks [Yang et al., 2012], and information from linked open data [Ostuni et al., 2013] to improve recommendation performance. Moreover, a number of methods have used more easily obtained item-based information to design recommendation systems. For example, the work in [Mooney and Roy, 2000] used a Bayesian learning algorithm to build a content-based recommender system based on the item-based features, without using the user-item recommendation matrix. The work in [Melville et al., 2002] used item contents to pre-process the sparse rating matrix to overcome the sparsity of user-item purchase matrix. These two methods though are not designed for top-N recommendations, they verified the usefulness of item contents for item recommendation systems. More recently, the authors of [Ning and Karypis, 2012] proposed a collective SLIM (cSLIM) method to incorporate item-based side information such as the reviews of the items into the SLIM to improve top-N recommender systems. This method assumes that user-item purchase matrix and itembased side information matrix are reproduced by the same sparse linear aggregation matrix, which is a very strong assumption in many real applications. The work in [Zhao et al., 2016] incorporated side informaiton into low-rank collaborative filtering. A few recent works [Bao et al., 2014;

McAuley and Leskovec, 2013; Xu et al., 2014] have also exploited user reviews for building recommender systems. However these methods require the reviews to be directly associated with the user ratings, while our approach can exploit reviews from auxiliary resources that have no direct relationships with the target users.

3 Proposed Approach

In this section, we present a novel joint prediction model to produce personalized top-N recommendation systems. We assume an item purchase matrix Y = {0, 1}n×t over n product items and t users is given, where Yij = 1 indicates an observed purchase relationship between the i-th product item and the j-th user while Yij = 0 indicates an unknown relationship between them. Note that an unobserved entry does not mean that the corresponding user is not interested in the particular product item. It only shows that the purchase record is not observed in the given user's past purchase history. The recommendation system will predict the unobserved entries and recommend to each user the top-N items with highest prediction scores from the unobserved item pool. We also assume the existence of item-based side information, which could be in the form of product reviews for ecommerce applications or film plots for movie recommendations. Different from some literature works [Bao et al., 2014; Xu et al., 2014] that exploited product reviews to build direct relationships between the considered users and products, we only require reviews provided as "side-information", which have no assumed connections to the target group of users. For simplicity, we assume the side-information will be presented as an item-feature matrix X ∈ Rn×d , whose each row contains features for a product item. We will use both X and Y to jointly recover an item-user recommendation matrix ̂ Y , which contains the predicted recommendation scores for all product items. We then can produce the top-N most interesting items for each target user based on the predicted scores.

In the rest of the paper, we will use 1 to denote a column vector of all 1s, assuming the size of the column vector can be inferred from the context. We use I to denote an identity matrix; use ‖X‖F to denote the Frobenius norm of matrix X; use X:j to denote the j-th column and Xij to denote the (i, j)-th entry of matrix X respectively.

3.1 A Joint PredictionModel

We aim to predict the unobserved recommendation entries in the item-user matrix by exploiting both the given item-user matrix and the item-based side information matrix. The proposed joint recommendation prediction model hence has two components, a self-recovery component that recovers a full item-user recommendation matrix ̂ Y from Y and a linear regression prediction component that predicts ̂ Y from the itembased side information matrix X. We will first describe each component below and then present the joint model.

Self-Recovery of the Recommendation Matrix

Given the partially observed item-user recommendation matrix Y , we propose to automatically recover the full recommendation matrix ̂ Y and fill the recommendation scores in the unobserved entries of Y by aggregating the existing item-user recommendations. Specifically, we assume an unobserved recommendation score for the j-th user on the i-th item, Yij, can be calculated as a nonnegative linear aggregation of the observed item recommendations for the j-th user; that is

for w ≥ 0. Such a linear recovery model can be built for any items, ̂ Y:j = WY:j. The principal behind the linear recovery models is that one assumes the items chosen by the same user have nonnegative linear correlation patterns. Assuming the same linear aggregation pattern for each item is shared across different users, we then have a matrix self-recovery formulation ̂ Y = WY with W ≥ 0, where W is an n × n linear aggregation coefficient matrix that is shared across all the t users. The matrix self-recovery aims to recover the unobserved recommendation entries without affecting much the observed recommendation scores. Hence, to pursue a meaningful matrix self-recovery we should minimize the changes of the recovered matrix ̂ Y from the pre-given item-user recommendation matrix Y . Moreover, to avoid the trivial solution of setting W as an identity matrix, we enforce the diagonal of W to be zeros. This leads to the following matrix self-recovery problem:

The constraints force each entry to be recovered from the other entries for the same user and hence encourage the statistical discovery of consistent item aggregation models across all the users. Moreover, with this constrained learning problem, the observed entries of the recommendation matrix Y may not be exactly maintained in the recovered matrix WY . To overcome this problem, we simply combine the original observed entries and the recovered unobserved entries together to form our final recovered item-user recommendation matrix ̂ Y ; that is, we set ̂ Y = Y + (WY ) ◦ (1 - Y ), where ◦ denotes the Hadamard product operator.

Discriminative Prediction from the Side Information

Given the item-based side information expressed as an itemfeature matrix X, where each feature vector describes the properties of a given product item, we propose to learn a prediction model from the item-feature matrix X to predict the user ratings. Our intuition is that though the item-based side information is common to all the users, different parts of the item properties may correspond to the interests of different users. That is, different users may have different tastes, reflected by the recommendation scores or purchase activities, over the same item, which can be related to the different features or feature subsets of the item. We hence assume the recommendation scores/purchase activities of each user over the set of product items can depend on the properties of items, and propose to predict the recommendation scores 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) = xT q + b, for the j-th user to predict his recommendation score y for the item described with feature vector x. Given the observed item-feature matrix X and the recovered item-user recommendation matrix ̂ Y , the linear regression model fj for the j-th user can be trained by minimizing a least squares regression loss ||Xq + b1 - ̂ Y:,j||2 over the model parameters q and b. For all the t users, we will then train t linear regression models by minimizing the following regularized least squares loss function

where Q ∈ Rd×t and b ∈ Rt are the parameters for the t linear regression models, the regularization term over Q is used to avoid over-fitting. When ̂ Y is unknown, these linear regression models will contribute to the prediction of the unknown entries of ̂ Y . This prediction component is a novel component, which is fundamentally different from the previous methods in the literature by predicting the recommendation scores directly from the item-based side information.

Integration Model

With the bridge equation ̂ Y = Y +(WY )◦(1-Y ), finally we can integrate the two components presented above, the recommendation matrix self-recovery component (i.e., Eq.(1)) and the linear regression prediction component (i.e., Eq.(2)), into the following joint matrix prediction model:

where the trade-off parameter γ is introduced to balance the contribution of the two components. This joint model integrates information from both the partially observed item-user recommendation/purchase matrix Y and the item-feature matrix X, and is expected to further improve top-N recommendation systems.

In terms of learning a linear aggregation model to reconstruct the item-user matrix. our proposed method is related to the SLIM method and the cSLIM method developed in the literature. However, SLIM does not exploit side information, while cSLIM exploits the item-based side information with the same aggregation matrix W used for the matrix self-recovery. Our proposed approach is significantly different from these two methods in exploiting the item-based side information with linear regression models and integrating the two components via joint predictions.

3.2 Optimization Algorithm

The learning problem we formulated in Eq.(3) is a joint convex minimization problem over two sets of parameters, the linear regression model parameters {Q, b} and the linear aggregation coefficient matrix W. For a fixed coefficient matrix W, the minimization problem in Eq.(3) over Q and b becomes a standard linear regression problem, which has the following closed-form solution:

Algorithm 1 Projected Gradient Descent Algorithm

Input: X, Y , parameters β > 0, γ > 0.

Initialize W as zeros.

while not converged do

1. find an optimal step size τ ∗ ∈ [0, 1] with line search

2. gradient descent: W = W - τ ∗∇f(W)

1. project onto feasible set:

W =max(W, 0), diag(W) = 0

end while

where H = I - 1n 11⊤ is a centering matrix. By plugging these solutions back into the objective function of Eq.(3), we can reformulate Eq.(3) equivalently into the following minimization problem over W :

where A = (XT HX + βI)-1XT H and B = H(XA - I). This remains to be a linear constrained convex minimization problem. We next develop a projected gradient descent algorithm to solve it.

Let f(W) denote the objective function of Eq.(6). The projected gradient descent algorithm will iteratively minimize f(W) subjecting to the constraints. In each iteration, given the current W, the gradient of the objective function can be computed as:

With this gradient, it will first take a gradient descent step over W and then project the newW into the feasible set defined by the constraints. The overall algorithm is described in Algorithm 1, where the step size parameter τ for the gradient descent is determined using a standard backtracking line search:

4 Experiment

We conducted experiments on a few real world datasets. In this section, we will first describe the experimental setup and then present experimental results and discussions.

4.1 Experimental Setup

We used the real world Amazon user rating and product review data for five categories of products, Beauty, Office, Sports& Outdoors, Health and Gourmet Foods, to conduct experiments. For each category, the original dataset we downloaded contains the ratings of the users over the products and the product reviews. Following [Ning and Karypis, 2011; 2012], we converted the rating values to 1s and produced implicit feedback matrices to use. The initial implicit feedback matrices are extremely sparse. We selected the top ten thousand items based on the number of purchases for each item, and then selected the top four thousands of users to use. We further preprocessed the datasets by selecting users with at least 3 purchases and filtering the items without any purchases. Finally we obtained five item-user matrices.

For each item-user purchase (feedback) matrix produced, we used the product reviews as the item-based side information. The reviews are given in plain text and we preprocessed each item review in the following way. We first extracted unigram features from the review articles, and then removed the stop words and selected the top 5000 frequent unigram features as the item features. Finally each product item is represented as a bag-of-word feature vector in terms of these 5000 unigram features. We used the term-frequency feature values as the item-feature data.

ComparisonMethods We compared our proposed method with the following methods for top-N recommendation systems: (1) Pure Singular Value Decomposition (pureSVD) [Cremonesi et al., 2010]. This method performs singular value decomposition directly on the item-user purchase matrix, and reconstructs the matrix with the top subsets of singular vectors. (2) Weighted Regularized Matrix Factorization (WRMF) [Hu et al., 2008]. WRMF extracts the latent factors for the users and items by performing weighted regularized matrix factorization. The reconstructed item-user matrix based on the extracted factors is then used for top-N recommendations. (3) Sparse Linear Method (SLIM) [Ning and Karypis, 2011]. SLIM learns an item-item aggregation sparse coefficient matrix by minimizing a constrained reconstruction loss. It uses the coefficient matrix to reconstruct the item-user purchase matrix. (4) Collective SLIM (cSLIM) [Ning and Karypis, 2012]. cSLIM incorporates side information into the SLIM model by enforcing the item-feature matrix to share the same aggregation matrix with the item-user matrix. (5) Inductive Matrix Completion (IMC) [Jain and Dhillon, 2013]. IMC is a state-of-art matrix completion method that exploits side information. We applied it to produce top-N recommendation systems.

Evaluation Metrics We evaluated our proposed method and the comparison methods using 5-fold Leave-One-OutCross-Validation. For each fold, the dataset is divided into a training set and a testing set: We randomly chose one transaction for each user and placed it to the test set, and the rest is used as training set. The training set is used to perform training. Then a ranked list of top N items are generated from the unobserved items for each user according to their scores in the reconstructed item-user matrix. The test results are produced by comparing the selected top N items for each user to his observed test set item. If there is a match between the test set item and the top N items, it is counted as one hit. The default N value used in our experiments is 10. We used two measurements to evaluate the test results: Hit Rate(HR) and the Average Reciprocal Hit Rate (ARHR) [Deshpande and Karypis, 2004], which are defined as

The params columns contain the parameter setting for each approach. PureSVD has one parameter f, indicating the number of latent factors. WRMF has two parameters, the regularization parameter λ and the latent factor dimension f. SLIM has two parameters, the ℓ2 and ℓ1 norm regularization parameters β and λ. Beyond β and λ, cSLIM has an additional side information weight parameter α. IMC has two parameters, hidden dimension f and regularization parameter λ. The proposed method has two trade-off parameters, β and γ.

where #users is the total number of users, #hits is the number of hits in the top-N recommendations across all users, and pi is the position of the test item in the ranked recommendation list for the i-th hit. ARHR is a weighted version of HR, which takes the ranking position of the test item in the top-N recommendation list into account.

4.2 Comparison Results

We compared the five comparison methods (pureSVD, WRMF, SLIM, cSLIM and IMC) with the proposed approach on the five Amazon datasets using the evaluation metrics HR and ARHR. The average results and standard deviations for all the methods are reported in Table 1. We can see that within the three methods that do not exploit side information, SLIM outperforms the other two methods, pureSVD and WRMF. By using the item-based side information, cSLIM consistently outperforms all the three methods that do not exploit side information across all the datasets, and IMC outperforms the three methods on four out of the five datasets. This suggests that side information is useful, which is consistent with the results reported in [Ning and Karypis, 2012]. However, the improvements produced by cSLIM and IMC over the other three methods, especially over SLIM, are relatively small. Our proposed approach on the other hand consistently outperforms all the five comparison methods across all the datasets. The improvements achieved by our approach are notably large. For example, on Office, the proposed approach outperforms cSLIM by 6.4% and 4.0% in terms of HR and ARHR respectively, and outperforms IMC by 6.7% and 3.9% in terms of HR and ARHR respectively. Theses results demonstrate that our proposed approach provides an effective mechanism for exploiting the item-based side information to improve top-N recommendation systems.

4.3 Component-Wise Study

The proposed approach integrates two components, the selfrecovery component and the linear regression prediction component, together to jointly perform item-user matrix reconstruction. How does each component contribute to the final top-N recommendation? Which component is more important? To answer these questions, we conducted another set of experiments to compare the proposed approach with its two individual components. The linear prediction component based on the side information can be obtained by simply setting γ = 0 in the proposed objective function Eq.(3) to drop the self-recovery component. The self-recovery component on item-user purchase matrix can be obtained by dropping the linear regression models from Eq.(3). This component can be viewed as a variant of the SLIM method without the regularization terms on W.

We compared the two components with the proposed joint model on all the five datasets. The comparison results are reported in Table 2. We can see that the performance of the prediction component with side information outperforms the self-recovery component with only purchase matrix with large margins across all the datasets. By comparing the results in both Table 1 and Table 2, we can see that the linear prediction component even consistently outperforms the most effective comparison methods, cSLIM and IMC, across all the datasets. This suggests that our novel prediction component that uses linear regression models to predict the item-user recommendation scores from the item-based side information is very effective. Nevertheless, our proposed approach that integrates the two components together consistently outperforms each individual component, which suggests the two components contain complementary information and our proposed model can effectively capture such information to improve top-N recommendation performance.

5 Conclusion

In this paper, we proposed a novel joint discriminative prediction model for personalized top-N recommendations. The proposed model integrates information from the standard item-user purchase matrix with a linear aggregation matrix and from the auxiliary item-feature matrix with linear regression models to predict the unobserved recommendation entries. We formulated this method as a joint convex optimization problem and solved it using a projected gradient descent algorithm. We conducted experiments on five real world Amazon datasets, and the proposed approach outperforms a number of top-N recommendation methods developed in the literature. Moreover, the experimental results also demonstrated the efficacy of the novel linear regression prediction component of the proposed model, which suggests it is effective to exploit the item-based side information in a discriminative way and encourages researchers to explore prediction models for building top-N recommendation systems.

Acknowledgments

This research was supported in part by the Canada Research Chairs program.