Privileged Matrix Factorization for Collaborative Filtering

1 Introduction

Recommendation systems are valuable for both providers and customers in many fields such as e-commerce, social media and entertainment. For customers, an efficient recommender system helps to narrow down the set of choices, discover new things and explore various options. For providers, a trustable recommendation to customers can increase sales or click through rates, offer personalized service and create opportunities for promotion.

The huge demand for online shopping has encouraged plentiful works to exploit users' ratings on products and hence make predictions of their future intent. Given a rating matrix composed by users' preferences on various items, recommender systems aim to predict a user's preferences on the items that are not consumed. Content-based filtering and collaborative filtering methods are two popular methods for recommender systems and have achieved prominent performance in the past. Content-based methods [Pazzani and Billsus, 2007] make a recommendation according to a user's past interests by matching up this user's perferences with the item features. On the other hand, the rooted observation for collaborative filering is that similar users have similar interests on the same item, and colaborative filtering methods [Lee et al., 2012] recommend items to users that are liked by their "similar" users based on the preference connections, which can be discovered by the collaborative filtering model. Lowrank matrix factorization is one of the most popular collaborative filtering algorithms. The sparse rating matrix is factorized into the product of two low-rank matrices, user matrix and item matrix respectively, and the missing ratings are estimated by a dot product of a user vector and an item vector.

One of the main challenges in current recommendation tasks is the data sparsity, for instance, in the Amazon review dataset [Mcauley, 2013], up to 99.9% of ratings are missing. In order to enhance performance, many recommender systems start to pay attention to auxiliary information accompanying the ratings. Thesedays, a lot of online review systems contain users' reviews of an item along with its ratings, for example in Amazon review system, users are encouraged to write down their comments about the product they have purchased from this website and give an overall rating at the same time. A user might give a product lower rating because of its high price, and explains why his overall ratings are different from a spendthrift user who focuses very little on the price of products. The users' opinion might be expressed in their reviews such as "so high price!".

The powerfulness of text-based side information has been exploited by several state-of-the-art methods. Hidden factor as topics (HFT) [Mcauley, 2013] modeled multinomial topic distributions of review comments by Latent Dirichlet Allocation and casts rating prediction as a matrix factorization problem while topic distribution variables are linked to user vector or item vector. BoWLF [Almahairi et al., 2015] used a bag of words to represent review comments and maximized joint probabilities of these words along with minimizing prediction error of matrix factorization model for collaborative prediction. While HFT used a topic distribution to describe all reviews from an item or user, BoWLF explore representative word distributions for reviews from different items. Overall, both of them use item vectors to represent topic distributions or word distributions of reviews from an item.

Existing matrix factorization based methods commendably utilize the review information for collaborative filtering, however, an obvious deficiency is that they explore review comments to describe either users or items, but ignore the phenomenon that review comments are simultaneously associated with both users and items. In practice, different users may have distinct comments on same items, meanwhile, different items can receive disparate comments from the same user. Thus it is necessary to maximize the values of review comments in collaborative filtering from both user and item aspects.

In this paper, we propose privileged matrix factorization method (PriMF for short) that utilizes extra information in the learning of both user and item vectors for collaborative filtering. We take the review comments as privileged information which are corresponding to rating values. After representing each review as a feature vector in privileged feature space, we learn a privileged function on these feature vectors that describe the discrepancies between predictions and groundtruth ratings. By minimizing the prediction error and the discrepancies depicted by the privileged function, the proposed PriMF benefits the learning of latent factors for both users and items. Experiments on five real datasets show the effectiveness of proposed privileged matrix factorization method.

In Section 2, we discuss related works. We introduce the formalization of our method in Section 3, and give the optimization procedure in Section 4. Empirical verifications are presented in Section 5, followed by conclusions in Section 6.

2 RelatedWork

Recommender systems can be generally classified into two types: content-based filtering [Pazzani and Billsus, 2007] and collaborative filtering (CF). Content-based filtering algorithms recommend items to users according to their previous interests. Specifically, a rating is estimated by matching up item features according to users' preferences. Collaborative filtering alligns with the assumption that users who share similar interests on an item in the past are more likely to hold similar opnions on other items compared with a randomly chosen user.

While collaborative filtering has become one of the most used recommendation approaches, it has two important subclasses: memory-based and model-based approaches [Lee et al., 2012]. Memory-based methods [Sarwar et al., 2001] make use of the rating matrix and make recommendations by the relationship between the queried user and item and the known ratings. Model-based filering algorithms fit a parametric model to the sparse rating matrix and then issue recommendations using the fitted model. For example, Bayesian networks [Su and Khoshgoftaar, 2006; Miyahara and Pazzani, 2002] train a Bayesian classifier based on the given rating matrix, and clustering-based methods [Wang et al., 2015] split the set of users or items on the given rating matrix thus taking them as basis for future predictions. Recently, low-rank matrix factorization methods are successfully applied into recommender systems [Rennie and Srebro, 2005;

Salakhutdinov and Mnih, 2011]. Under the low-rank assumption, a rating matrix can be expressed as a product of two low-rank matrices [Liu and Tao, 2016]. By fitting the two low-rank matrices to the given ratings, prediction of a user's interests on a new item can be made by multiplying corresponding user vector and item vector. Other recommerder approaches leverage rating data and side information to enhance performance [Shi et al., 2014] .

Inductive matrix completion (IMC) is a typical example of using side infromation for collaborative filtering. It was initially proposed and analyzed by [Jain and Dhillon, 2013]. With both user information and item properties at hand such as MovieLens, the main idea is to fit the rating matrix by corresponding user's feature vector and item's feature vector along with an underlying unknown matix. IMC has been applied to multi-label, multi-class learning and semi-supervised clustering problems. By taking a multi-label or multi-class learning as a collaborative filtering problem in which the known labels compose a label matrix, the label predictions are now equivalent to predicting the missing entries in the label matrix based on the given label information and sample features[Xu et al., 2016]. Semi-supervised clustering can be taken as a collaborative filtering as well. Given a set of objects to be clustered and some known clusters of these objects, any two objects' relationship (in or not in the same cluster) can be encoded in a pairwise similarity matrix. Taking object featuer vectors as side information, the clustering task thus is accomplished by a IMC model [Yi et al., 2013].

The side information applied in recommender systems varies. Item features such as "title" and "genre" as side information are employed in [Tso and Schmidt-Thieme, 2006]; and user features such as "gender", "age" and "occupation" are used in [Kim et al., 2016; Agarwal and Chen, 2009; Park et al., 2013] on MovieLens datasets. The movie plots as item features are applied in [Ning and Karypis, 2012] which can be fetched from IMDB. Other researchers explore customized side information, such as "date" and users' previous rating history [Porteous et al., 2010] in Netflix prize dataset, and "clicks", "views", number of ads [Menon et al., 2011] in Yahoo! traffic stream data. Another interesting side information is the user's tags on items which implies connections between users and items [Saha et al., 2015; Fern´andez-Tob´ıas and Cantador, 2014; Bao et al., 2012]. In social networks, neighbors of a user are usually provided. Given a trust network connecting each user and its trustees, some user-based collaborrative filtering methods generate predictions by aggregating the ratings of a user's trustees [Massa and Avesani, 2007].

Despite the various types of side information discussed above, thesedays, more and more attention is paid to review texts that are often accompanied with the ratings. Observing the rich information in the review text, there are severeal efforts that try to improve rating prediction by incorporating these information into latent factor methods. [Mcauley, 2013] modeled the rating prediction problem as matrix factorization. To link the latent dimension of user vectors (or item vectors) to the number of hidden topics, the topic distribution variable one user's reviews is represented by the user vector through softmax normalization. [Ling et al., 2014] proposes a combined approach of content-based and collaborative filtering which harness information from ratings and reviews together. [Almahairi et al., 2015] presents a distributed Bag-ofWords method which infers probability distribution of BoW by affine transformation on item representation with softmax normalization.

3 PrivilegedMatrix Completion

In this section, we give the formalization of our method and discuss its intuitions in detail.

3.1 Problem Statement

Considering a database composed of (user, item, rating) tuples from n users' preferences on m items, this database can be compactly denoted as a preference matrix R, which is usually sparse. The elements in the matrix R represent corresponding user's liking of the item. In real applications, the values are usually integer ratings settled in [1,L]. A recommender system manages to predict a user's preference of an unconsumed item which corresponds an unseen entry in the rating matrix R.

3.2 PrivilegedMatrix Factorization

Given the rating matrix R, the common assumption is that R is low-rank and a matrix factorization method fits R with a low-rank matrix X = UV ⊤. To predict ordinal values of R with real-valued X, a set of thresholds {θ1, ..., θL-1} are needed. In the hard-margin settings, X would be required as:

where θ0 and θL are -∞ and +∞ respectively. The hard-margin setting is often known to be powerless in nonseparable case. Therefore to tame this problem, slack variables ξij are introduced, and Eq. (1) is relaxed to

To avoid the predictions that cross rating-boundaries, not only two immediate constraints Xij ≤ θRij - 1 and Xij ≥ θRij-1 +1 are penalized, but also Xij ≤ θl -1, ∀l > Rij and Xij ≥ θl + 1, ∀l < Rij. By introducing indicating variable T :

Eq. (2) is reformulated to the following compact form:

We denote Φ = {U, V } as the variable set and R(Φ) as the regularization term on variables in Φ to control the model complexity. Under the above constraints in Eq. (3), the optimization problem is formulated as:

Observing that a rating indicating the user's preference is often accompanyed with a review text, it is believed that a piece of comment text contains rich information about the user's opinions on an item. In real world, it is obvious that people need less training data when they learn a new task than that needed by training a machine on the same task. The rooted reason behind this phenomenon is that we are taught by teachers usually. A teacher has the experience on this task and has her own trained system in her mind. Although she cannot transfer her decision mechanism directly into your brain, she can teach you by generating privileged information that reflects her belief in the development of this mechanism. For example, when it comes to predict a user's preference over two movie genres like "comedy" and "thriller", the training data are two movies with genre "comedy|drama" and "drama|thriller" and both movies are rated as 5. In this case, matrix factorization model might be confused at the ratings. But from the comments that "A great comedy for family time" and "I don't like the kind of plots, but Thomas's acting is exciting", it is more confident to conclude that this consumer prefers "comedy" more than "thriller". This is exactly the role that we think the review comments can play in the training process. It reflects a user's thoughts in the decision procedure, and thus explain discrepancies between predictions and ground truth ratings.

Review information is from a different resource compared to rating data and lies in another feature space. The feature vector which is denoted as Zij corresponds to rating Rij. Now we consider a rating prediction problem based on the quaternions (user, item, rating, review). Considering review texts as privileged information of corresponding ratings, the privileged function is defined as φ(Zij,w, b) = wZij + b, w ∈ Rd . To ease the presentation, we append the bias term b to the end of the weight vector w and still denote it as w, w ← [w, b]. Similarly, we append 1 to the end of every feature vector as Zij ← [Zij , 1]. The slack variables in Problem (4) can be reformulated as ξij = φ(Zij , w), ∀(Xij , Zij ). Since we can learn different privileged functions for different items, we use W to denote coefficient variables in φ.

Adding W to the variable set Φ = {U, V, W}, R(Φ) takes the form as:

Our objective function thus can be written as:

where [y]+ = max{0, y}.

The variable ξij in Problem (4) is introduced to represent slacks triggered by rating data that are not linearly separable. With privileged information in hand, the slacks in nonseparable situation can be learned by a correcting function that is dependent on the additional information and has low VC dimension. This learning paradigm is firstly applied to support vector machine in classification problem [Vapnik and Vashist, 2009; Vapnik and Izmailov, 2015] and then extended to various applications [Yang et al., 2016]. In collaborative filtering, this slack margin can be triggered by various possibilities, such as users' special appetite on an item that is not consistent with item features, or users' sudden change in one criterion for rating. And it is even possible that rating data is corrupted when it is collected. Therefore, one linear correcting function φ(Zij,W) is not representative enough for correcting the non-linearly separable ratings.

To reinforce the model's tolerance to outliers or noises, we represent ξij in Problem (4) by a linear privileged function and a tolerance term ζij. The final model takes the form:

Thus the offsets for hard-margins in Problem (4) are splited into a discrepancy term represented by privileged function and a tolerance term that allow the existence of outliers. The above problem is equavelent to the following problem:

where h(u) is the hinge loss and it can be, for example, h(u) = max{0, 1 - u}.

After Problem (8) is addressed, we get the optimal solution of Problem (8) that Φ∗ = {U ∗ , V ∗ ,W ∗ , θ∗ }. Denote X∗ = U ∗V ∗T , we infer the ratings of each item as:

where R∗ is the optimal output of our algorithm.

4 OptimizationMethods

In the following, we present our optimization method. Let Ui∗ and Vj∗ denote the i-th and j-th row of U and V respectively. For simplicity, the independent variable of function h(u) is defined as ulij = T l ij (θjl - Xij) + [φ(Zij,W)]+. Taking derivatives w.r.t. U in Problem (8), we obtain:

and the partial derivative w.r.t. V is analogous. Define the indicator function 1(x) as 1 if x > 0 and 0 otherwise. The partial derivative with regard to wj is:

And the partial derivative w.r.t. θjl element-wisely is:

With these gradients in hand, we can turn to gradident descent methods for solving Problem (8).

For optimization of U, V,W, and θ we choose conjugate gradient descent method [Hager and Zhang, 2006]. For simplicity of presentation, we denote y as concatenated vector of variables U, V,W and θ, and denote g(y) = f(Φ, θ). We have the general form of conjugate gradient as

where ηt is a sequence of step sizes generated by a line search algorithm that can guarantee the decrease in objective function. pt is the descent direction genearted by the following rule:

and ▽gt is the abbreviation of ▽g(yt). τt is the conjugate gradient parameter and it is chosen to ensure the conjugacy between conjugate gradient directions.

Several options of τk can be used in conjugate gradient algorithm. Here we choose the Polak-Ribiere (PR+) method for calculating the CG update parameter:

Note that τt is chosen to ensure that pt is orthogonal to all previous search directions by a symmetric positive definite matrix. When two consecutive gradients are far away from orthogonal or conjugate directions are almost orthogonal to gradients, we restart the searching process by reset the exploration direction to the steepest descent direction. The restart condition takes the form: 〈▽gt,▽gt-1〉/〈▽gt,▽gt〉 ≥ ν or 〈pt+1,▽gt+1〉 ≥ 0. Here ν is set to 0.1 as recommended by [Nocedal andWright, 2006].

After selecting the search direction, strong Wolfe conditions [Nocedal and Wright, 2006] are applied to choose step size ηk that can guarantee sufficient decrease on objective function. The conditions take the form as:

A secant method is used to find the root of directional derivatives. The overall algorithm is summarized in Algorithm 1.

Due to the undifferentiability of standard hinge loss at zero point, the smooth hinge loss is adopted in this paper [Rennie and Srebro, 2005]:

The smooth hinge loss does not continously reward the correct predictions, meanwhile, it is differentiable at zero point.

Strong Wolfe conditions guarantee the proposed optimization to converge. However, due to the non-convexity of the objective function, the solution may fall into the local minima. In experiments we will repeat the training process several times to avoid spurious local minima.

5 Experiments

We verify the proposed method on five datasets from Amazon reviews [Mcauley, 2013]. These data were collected from Amazon website with the years spanning from 1998 to 2013. The five datasets refer to five category of products, watches,

Algorithm 1 Conjugate Gradient Method for Problem (8)

Input: R: Incomplete matrix, ϵ: stopping criteria, k: latent dimension, T : max iteration

Output: R∗ : the optimal approximation of R

• 1: Init: y0 = [U0(:); V0(:); θ0(:);W0];
• 2: eval: g0 = g(y0), ▽g0 = ▽g(y0);
• 3: set: p0 = -▽g0, t ← 0;
• 4: while t < T and ‖▽gt‖> ϵ do:
• 5: choose step size: ηt satisfies Cond. (16);
• 6: update yt+1 = yt + ηtpt;
• 7: eval: ▽gt+1;
• 8: get CG direction:

• 9: check restart condition: if 〈▽gk,▽gk-1〉 〈▽gk,▽gk〉 ≥ ν or 〈pt+1,▽gt+1〉 ≥ 0: reset: pt+1 = ▽gt+1; end if
• 10: end while
• 11: Return: R∗ predicted by Eq. 9.

musical instruments, industrial and scientific, gourmet foods and books. Every rating in the datasets is associated with a piece of review comment. The detailed information for these datasets are in Table 1.

5.1 Experiments Settings

We follow the settings used in [Mcauley, 2013; Almahairi et al., 2015]. For each dataset, 80% ratings are randomly selected for training and the remaining 20% are evenly splited into validation and test. The review information is only available in the trainning phase.

To extract feature vectors from reviews of different lengths, we adopt a neural network language model, Paragraph Vector [Le and Mikolov, 2014] for help. As an extension of Word Vector [Mikolov et al., 2013b; 2013a], it can preserve semantics of words as well.

The size of the privileged feature vector is fixed to k = 10 which is consistent with the setting in HFT. The rank r of X is determined by cross validation. In the experiments, the optimum r on different datasets is around r = 50. Baseline methods have the similar parameter settings. The measurement used in the paper is mean square error (MSE):

Where R∗ is the optimal estimation of the ground truth rating matrix R and PΩ is the sampling operator.

5.2 Baseline Methods

We compare the proposed PriMF with four baseline methods.

• FM3F: Fast Maximum Margin Matrix Factorization [Rennie and Srebro, 2005] is a basic collaborative filtering model that minimizes the discrepancies between erroneous predictions and ground truth ratings.
• HFT: Hidden Factors as Topics [Mcauley, 2013] is a combined approach of matrix factorization and LDA. It models multinomial topic distributions by using either user factors or item factors which means that it takes all reviews by a particular item as a document or that by a particular user as a document and maximizes the joint probabilities of the text corpus.
• BoWLF: Bag-of-Words latent factor model [Almahairi et al., 2015] takes all reviews by an item as a document. For different document, the word distributions in the vocabulary are modeled by a weight matrix-vector product with the item correspondingly. By representing each review as a bag of words, BoWLF maximize the joint probabilities of document corpus by multiplying over all words in each document.
• LMLF: This is a recurrent neural network language model [Almahairi et al., 2015] that takes a sequence of words as input and preserve their order. It models different items to have their respective word distributions. The probability of current word conditioned on previous words is modeled by an affine transformation of a recurrent function and LSTM is adopted as its recurrent function module.

5.3 Evaluation Results

For both the comparative methods and PriMF, we randomly initialize the training for five times and select parameters that have lowest error on validation set. We select α, β and γ for PriMF from {10-5 , 10-4 , ..., 104 }. For baseline methods, parameters are validated in the recommended range in original papers. The averaged MSE and standard deviation on test sets are reported in Table 2.

PriMF achieves a remarkable improvement over FM3F after introducing privileged information and gains consistent improvement on other three methods. In general PriMF and comparative methods can all be classified into matrix factorization category and all of them make predictions by multiplying user vector and item vector respectively. The difference exists in the way of using reviews in the training phase. While HFT, BoWLF and LMLF model topic or word distributions of review contents by item vectors without considering user vectors, their performance sacrifices.

To test the performance of these approaches under different splits of data, we repeat random splits of data for five times and keep the percentage used in previous experiments. In every split, the collaborative filtering are trained on a different set of ratings and review comments. The parameters are chosen on the validation set and the performance of different approaches on test set are reported in Fig. 1. From Fig. 1, we find that the performance of each method under different splits varies dramatically, but the relative performance across five methods remains consistent. This observation indicates that the results tested under different splits of data are not straightforwardly comparable, but each single random split can be used to evaluate and select models as long as the split is kept the same for all evaluated methods.

5.4 Parameter Analysis

In this section, we analyze the influence of two hyperparameters α and β in optimization problem (8). α controls the weight of privileged function that models discrepancies between predictions and groundtruth values, while β constrains prediction loss. We report the performance of PriMF under different choices of α and β in Fig. 2. When α is fixed, we can choose the value of β from a large range that leads to consistent good performance of PriMF, and vice versa. We conclude that our method is stable with respect to different choices of parameters.

6 Conclusions

In this paper, we study a privileged matrix factorization method for collaborative filtering. We utilize review texts that are in companion with rating values to assist the learning of user and item factors. In contrast to existing approaches that use review texts to describe either user or item factors, we notice that a review comment is related to a pair of user and item concurrently, and utilize it in the learning of both user and item factors. We take review texts as privileged information for matrix factorization and express them as feature vector through a Paragraph Vector transformation. The discrepancies between predictions and ground truth ratings are modeled by a privileged function dependent on review vector. We testify our model on several challenging Amazon review datasets and achieve better performance. While the remarkable strength of our method is discussed above, the weakness shared with the other collaborative filtering methods is the implicit assumption on the complete review comments. In practice, not every rating comes with a piece of review comment. In the future, we are considering the scenario in which some reviews are missing which is a common issue as well.

Acknowledgments

This work is supported by Australian Research Council Projects FT-130101457, DP-140102164, LP-150100671.