Improving Top-N Recommendation with Heterogeneous Loss

1 Introduction

In the era of Internet, online shopping has become a close part of people's daily life. To facilitate consumers' online shopping experience, help consumers to find their interested items from the huge amount of online items and hence encourage online item purchases, effective top-N commercial recommendation systems, which suggest a small list of items that best match each consumer's taste from the large amount of product items, have become increasingly important. TopN recommendation systems automatically predict the recommendation scores over each item in the whole product item pool for each consumer, and recommend the items with high scores to the consumers. They can be widely used in many real world applications. For example, Amazon.com has a huge amount of online products, while consumers may not know all the special items they would like. A top-N recommendation system, which can effectively suggest a set of personalized selected products for each consumer, can significantly increase the user-item purchase probability. Similarly, Netflix Inc. has thousands of online movies and TV shows, a personalized recommendation for users can help them to find the videos they may like. Yahoo! and Apple Itunes have millions of musics, Top-N recommendation systems can help users to find the musics they may like and provide a recommendation list to each user. In summary, an effective topN personalized recommendation system can have significant real world commercial impacts.

Many methods have been developed in the literature to build top-N recommendation systems [Ricci et al., 2011]. One classical technique is collaborative filtering (CF) [Schafer et al., 2007; Su and Khoshgoftaar, 2009], which models the relationships between users and the correlations between items to identify new user-items relationship scores. Two main types of collaborative filtering methods include neighborhood-based CF [Sarwar et al., 2000; 2001; Deshpande and Karypis, 2004; Verstrepen and Goethals, 2014] and model-based CF [Rennie and Srebro, 2005; Rendle et al., 2009; Cremonesi et al., 2010; Sindhwani et al., 2010; Hu et al., 2008; Shi et al., 2012; Liu and Aberer, 2014]. Standard model-based CF methods perform matrix factorization to complete the missing recommendation entries, which exploits the low-dimensional subspace representations of the users and items [Hu et al., 2008; Weimer et al., 2008; Yun et al., 2014b]. Besides CF, sparse aggregation methods that exploit the linear correlations between items have also been explored in a few works [Ning and Karypis, 2011; Cheng et al., 2014; Kabbur et al., 2013; Christakopoulou and Karypis, 2014] to improve top-N recommendation performance. These methods have mainly pursued recommendation score recovery by minimizing the pointwise comparison loss between the reconstructed user-item matrix and the observed incomplete user-item matrix.

Recently, pairwise ranking methods that directly capture users' pairwise preference structures on product items have demonstrated good performance for top-N recommendation [Weimer et al., 2008; Steck, 2010; Chen and Pan, 2013; Aiolli, 2014; Park et al., 2015]. These methods have explored different ranking losses as the optimization targets, including the normalized discounted cumulative gain [Weimer et al., 2008], the AUC scores [Aiolli, 2014] and the max-margin loss [Park et al., 2015]. Nevertheless, different types of losses have different strengths in producing the missing recommendation scores. The pointwise losses enforce the entrywise consistency between the reconstructed recommendation matrix and the original matrix, while the pairwise ranking losses enforce the preference structure consistency. Majority of the existing methods however have focused on using a uniform type of recovery loss, which limits their abilities of integrating the complementary strengths of different types of losses.

In this paper, we propose a novel personalized top-N recommendation approach that uses a combined heterogeneous loss function based on linear self-recovery models. The heterogeneous loss integrates the strengths of pairwise ranking loss and pointwise recovery loss to enforce both entrywise consistency and preference structure consistency between the recommendation recovery and the observations, which leads to improved recommendation predictions. We formulate the learning problem with this heterogeneous loss as a constrained convex minimization problem and develop a projected stochastic gradient descent optimization algorithm to solve it. The proposed approach is evaluated on a set of personalized top-N recommendation tasks. The experimental results show the proposed approach outperforms a number of state-of-the-art methods on top-N recommendation.

2 RelatedWorks

Existing top-N recommendation methods have mostly focused on minimizing a uniform type of recommendation recovery loss to predict the recommendation scores. Based on the type of the losses, these recommendation systems can be categories into two main groups. The first group exploits pointwise comparison losses and the second group exploits pairwise ranking losses.

Pointwise comparison methods. Many traditional top-N recommendation algorithms perform learning by minimizing the pointwise (entrywise) divergence of the reconstructed recommendation matrix from the original observation matrix. These include the collaborative filtering methods [Schafer et al., 2007; Su and Khoshgoftaar, 2009; Hu et al., 2008; Weimer et al., 2008; Yun et al., 2014b], and the sparse linear aggregation methods [Ning and Karypis, 2011; Cheng et al., 2014; Kabbur et al., 2013; Christakopoulou and Karypis, 2014]. For example, a weighted regularized matrix factorization (WRMF) model has been developed in [Hu et al., 2008], which minimizes the pointwise difference between the reconstructed matrix produced by the inner product of the user and item latent representations and the training matrix. Similarly, the work in [Yun et al., 2014b] enforces the pointwise similarity between the training matrix and reconstructed matrix. It uses a non-locking parallel computing algorithm to perform matrix completion. In [Ning and Karypis, 2011], a sparse linear method (SLIM) was proposed to recover the missing recommendation entries. It exploits the item-item correlations to reconstruct the incomplete recommendation matrix and minimizes the pointwise reconstruction loss between the reconstructed matrix and the input training matrix.

Pairwise ranking methods. Given a pair of items, a user naturally will prefer one to another, which forms the important pairwise preference structure of the recommendation data. The pointwise comparison methods however ignored this user personalized preference information. Recently, pairwise ranking methods are proposed to produce top-N recommendation systems by optimizing the preference structure consistency between the original matrix and the reconstructed recommendation matrix [Weimer et al., 2008; Steck, 2010; Chen and Pan, 2013; Aiolli, 2014; Park et al., 2015; Rendle et al., 2009]. Pairwise ranking methods treat training data as a set of triplet instances; for example, the triplet (i↪ j↪ k) is an instance that encodes the i-th user's preference to item j over item k. Different pairwise ranking losses have been exploited in these works. For example, the pairwise ranking methods in [Rendle et al., 2009; Aiolli, 2014] optimize AUC scores; the work in [Weimer et al., 2008] optimizes a normalized discounted cumulative gain; Yun et al. (2014a) explored the connection between the metric discounted cumulative gain and the binary classification to change the ranking problem into binary classification problems; Park et al. (2015) proposed a large-scale collaborative ranking method that exploits a max-margin hinge ranking loss to minimize the ranking risk in the reconstructed recommendation matrix. Nevertheless, these pairwise ranking methods ignored the entrywise consistency between the reconstructed matrix and the original matrix.

Different from all these existing methods, our proposed approach will perform top-N recommendations by optimizing a heterogeneous loss that integrates the strengths of both a pointwise comparison loss and a pairwise ranking loss.

3 Approach

In this section, we present a novel personalized top-N recommendation approach that minimizes a combined heterogeneous loss within a general learning framework. We assume a partially observed user-item recommendation/purchase matrix X 2 Rn⇥m over n users and m items is given. For implicit feedbacks, the recommendation/rating values are within ¶0↪ 1♦, where the entry Xij = 1 indicates a transaction or purchase record for the i-th user on the j-th item. The entry Xij = 0 on the other hand means either the i-th user never purchased the j-th item or the transaction record has been removed and need to be predicted. We aim to identify the most interesting items for each user from his unrecommended/unpurchased list of items. Below we first introduce the general learning framework for top-N recommendations and then instantiate it with novel objective losses. We finally present a stochastic gradient descent algorithm to solve the recommendation problem formulated.

3.1 AGeneral Learning Framework for Top-N Recommendation

Given the input user-item recommendation/purchase matrix X, a general framework for top-N recommendation performs learning by minimizing a regularized reconstruction loss function:

where bX denotes the reconstructed recommendation matrix with a parametric model with parameter matrix W, L(·) denotes a convex reconstruction loss function and R(·) denotes a regularization function. By substituting L(·) with different loss functions and employing different reconstruction models (denoted by the parameter W), many existing methods can be produced from this general framework as specific examples. For example, by using a matrix factorization model that reconstructs X as bX = UV > and a least squares pointwise loss function L(X↪ bX) = kX - bXk2F , we can produce the simple pure singular value decomposition based (PureSVD) matrix factorization method [Cremonesi et al., 2010] with proper constraints. Similarly, by reconstructing X with a linear aggregation model bX = XW > and using a least squares pointwise loss function L(·) and an integrated `2 and `1 norm regularization function R(W) = βkWk2F + λkWk1, the sparse linear method (SLIM) [Ning and Karypis, 2011] can be produced from the framework with additional proper constraints.

Moreover, the state-of-the-art pairwise ranking methods can also be produced as specific examples from this framework. For example, given the set of preference triplets ⌦, by using a matrix factorization model to reconstruct X as bX = UV >, a max-margin hinge loss function Lrank(x) = max(0↪ 1 - x), and `2 norm regularizers on U and V , we can produce the large scale pairwise ranking method (AltSVM) in [Park et al., 2015] as below:

where Yijk is a function of X such that Yijk = 1 if user i prefers item j over item k in X and Yijk = -1 otherwise; k · kF denotes the matrix Frobenius norm; Ui denotes the i-th row of U and Vj denotes the j-th row of V .

Our proposed approach can be conveniently formulated within this general learning framework as well. We integrate two types of losses into a novel heterogeneous loss based on linear self-recovery models.

3.2 Novel Heterogeneous Loss

Pairwise ranking methods have demonstrated great top-N recommendation performance in the literature [Park et al., 2015]. However, with the matrix factorization reconstruction function, the scalable learning problem produced in Eq. (2) is a non-convex optimization problem. To introduce a convenient convex formulation with pairwise ranking losses, we propose to adopt a linear self-recovery model to reconstruct X. In particular, we use a linear reconstruction function bX = XW > with constraints W ≥ 0 and diag(W) = 0. This linear function exploits the statistical positive item-item correlations distributed among all the users to reconstruct the missing recommendation scores. The constraints are used to avoid trivial solutions. Then with a pairwise ranking loss function Lrank(·), we can formulate the following convex pairwise ranking problem to perform top-N recommendation:

Note for each user i, if he/she purchased item j but there is no purchase record for item k in the training matrix X, we say that user i prefers item j over item k and we have Xij > Xik. The set ⌦ in the formulation above contains all the triplets (i↪ j↪ k) where Xij > Xik. To maintain the same pairwise preference structure, we assume that if Xij > Xik in the original matrix X, one should also have bXij > bXik in the reconstructed matrix ˆX. The loss function Lrank(·) aims to encode the pairwise preference ranking divergence between the given matrix X and the reconstructed matrix bX. In our implementation, we use the max-margin hinge loss function as the ranking loss, i.e., Lrank(x) = max(0↪ 1-x). By minimizing such a ranking loss function, the model will increase the consistency of the pairwise preference ranking between the reconstructed matrix bX and the original matrix X. However, the consistency is only maintained at the pairwise relative level. It does not necessarily guarantee the good quality of pointwise reconstruction, which might consequently hamper the accurate inference of unseen pairwise relationships.

We nevertheless have an easy solution. The linear selfrecovery model bX = XW > naturally allows one to encode the pointwise recovery loss between the entries of the reconstructed matrix bX and the original matrix X, e.g., Lpoint(X↪ bX) = kX - bXk2F . Previous works [Ning and Karypis, 2011] have also demonstrated good top-N recommendation performance with a least squares pointwise recovery loss. Hence we propose to combine both the pairwise ranking loss and the pointwise recovery loss to produce a new heterogeneous loss function for top-N recommendation. Our learning problem with the heterogeneous loss function can be formulated as below:

The heterogeneous loss function used in this formulation integrates two different types of losses, and is expected to capture both the pointwise similarity discrepancy and the pairwise ranking consistency discrepancy to produce a better reconstruction matrix. Moreover, the learning problem (4) remains to be a convex optimization problem.

3.3 Optimization Algorithm

Due to the large size of the user-item matrix, standard gradient descent algorithms are not efficient for solving the minimization problem in (4). Moreover, though the learning problem is convex, the hinge loss function for pairwise ranking is non-differentiable and subgradients are typically needed. Hence in this work, we develop a projected stochastic gradient descent (SGD) algorithm to solve our target learning problem. The SGD technique has been widely used in recommendation systems with pairwise ranking [Rendle et al., 2009; Chen and Pan, 2013; Yun et al., 2014b], and it can also be extended to perform parallel computations [Zinkevich et al., 2011; Recht et al., 2011; Yun et al., 2014b].

With the pairwise ranking loss, we use the user-item-item triplet (i↪ j↪ k) instances for the stochastic gradient descent procedure. In each iteration, we randomly choose a triplet (i↪ j↪ k) 2 ⌦ and make a SGD update:

where ♣⌦j ♣ and ♣⌦k ♣ denote the number of comparisons in ⌦ that involve item j and item k respectively. L0rank (W > j ) and L0rank (W > k ) denote the derivations of Lrank(·) on W > j and W > k respectively, such that

if Xi(Wj - Wk)>  1 and L0rank (W > j ) = 0 otherwise. Similarly,

The ⌘ parameter in the SGD update is the stepsize of gradient descent. We used a fixed small stepsize value in our experiments. The overall learning algorithm is given in Algorithm 1.

Algorithm 1 Projected Stochastic Gradient Descent

Input: ↵ > 0↪ β > 0↪ ⌘ > 0; initialize W 0 as zeros. Set W = W 0

for iter = 1 to MaxIter do

1. Randomly select (i↪ j↪ k) 2 ⌦
2. Update Wj by using (5)
3. Project the updatedWj into the feasible set: Wj =max(Wj↪ 0), Wjj = 0;
4. Update Wk by using (6)
5. Project the updatedWk into the feasible set: Wk =max(Wk↪ 0), Wkk = 0;
6. if converge then break-out end if end for return W

4 Experimental Results

In this section, we first present the experimental setting and then report the empirical results.

4.1 Experimental Setup

Datasets. We used five datasets in our experiments: Yahoo! music ratings v1.0 dataset, Yahoo! movie ratings v1.0 dataset, MovieLens 100k (ml-100k) dataset, MovieLens 1M (ml-1m) dataset and Netflix dataset. Yahoo!Music contains ratings for songs, the ratings are supplied by users during normal interactions with Yahoo! Music services. Similarly, Yahoo!Movie contains ratings for different movies. In each dataset, we converted the entries with positive values to 1 and converted the user-item matrix to an implicit feedback matrix. Since the original rating matrix is sparse, for Yahoo! Movie and Yahoo! Music we kept the users with more than 20 ratings and items with more than 5 ratings. For ml-100k we used original implicit feedback matrix. For ml-1m and Netflix we used the same datasets as [Aiolli, 2014]. The statistic information of these datasets is reported in Table 1.

Evaluation Methods. For each dataset, we split it into a training set and a test set. For each user, we randomly selected ten feedbacks and placed them into the test set and the rest were used as training set. After training, a ranked list of top-N items can be returned for each user according to the reconstruction scores, which were compared to the test set for performance evaluation.

We used two standard performance metrics, the top-N prediction precision (Precision@N) and the mean average precision (MAP@N), to evaluate the test performance. The top-N prediction precision for the i-th user is defined as

where T denotes the test matrix and Pi denotes the index values of the top-N predicted items in the original matrix for the i-th user. The overall Precision@N value is computed as the average of Precision@N(i) over all users. MAP@N denotes the mean average precision of the top-N predictions. The average precision (AP) of the top-N prediction for the i-th user can be defined as

MAP@N can be computed as the mean of the average precision of the top-N predictions for all users, such that MAP@N= 1n PiAP@N(i).

In our experiment, we randomly split each dataset into training and test matrices for five times and report the average test results in terms of these two evaluation metrics.

Compared Methods. We compared the proposed method with four methods developed in the literature: WRMF [Hu et al., 2008], SLIM [Ning and Karypis, 2011], RobiRank [Yun et al., 2014a] and AltSVM [Park et al., 2015].

0▷220 ◦ 0▷002

0.1 0▷220◦0▷002

0▷220◦0▷002 0▷173◦0▷002

Parameters Selection. For the proposed method, we have two parameters, ↵ and β. We selected the weight control parameter ↵ from ¶10↪ 100↪ 1000↪ 5000↪ 10000♦ and selected the regularization parameter β from ¶0▷001↪ 0▷01↪ 0▷1↪ 1↪ 10↪ 100↪ 1000♦. For WRMF, the latent factor dimension f is selected from ¶10↪ 20↪ 50↪ 100↪ 200↪ 500↪ 1000♦ and the regularization parameter λ is selected from ¶0▷1↪ 1↪ 10↪ 100↪ 1000♦. For SLIM, `2 regularization parameter β is selected from ¶1↪ 10↪ 100↪ 200↪ 500↪ 1000♦ and `1 regularization parameter λ is selected from ¶0▷001↪ 0▷1↪ 1↪ 10♦. For RobiRank, the latent feature dimension f is selected from ¶10↪ 20↪ 50↪ 100↪ 200↪ 500↪ 1000♦ and the regularization parameter λ is selected from ¶1↪ 10↪ 100↪ 200↪ 500↪ 1000♦. AltSVM also has two similar parameters; the latent dimension is selected from ¶100↪ 200↪ 500↪ 1000♦ and the regularization parameter λ is selected from ¶100↪ 1000↪ 10000♦. For each approach, we report the best results and the correspond-

0▷173 ◦ 0▷002

0▷416 ◦ 0▷003

0▷173◦0▷002 0▷416◦0▷003

0▷416◦0▷003 0▷396◦0▷002

ing parameter settings.

4.2 Experimental Results

The selected parameter settings and the experimental results in terms of Precision@N and MAP@N with N 2 ¶5↪ 10♦ for all the comparison approaches are reported in Table 2. We can see that among the four comparison methods, ¶WRMF, SLIM, RobiRank and AltSVM♦, RobiRank has poor performance and it produces the most inferior results on four datasets, Yahoo!Music, Yahoo!Movie, Netflix and ml-1m. SLIM performs much better than RobiRank and it even outperforms RobiRank on the remaining dataset ml-100k across three measurements except Precision@10. The pairwise preference ranking method, AltSVM, produces the best results on Yahoo!Movie in terms of all the measurements among the four methods, and has similar performance as SLIM on other datasets. The WRMF method, which uses regularization control and applies

0▷396 ◦ 0▷002

0▷396 ◦ 0▷002

different weights for the entries, outperforms all the other three methods on both Yahoo!Music and Nexflix in terms of the four measurements. But it has poor performance on ml100k. Our proposed approach on the other hand outperforms all these four methods with remarkable margins on all the datasets across the four measurements. These results suggest the proposed approach is indeed an effective method for topN recommendation.

4.3 Parameter Sensitivity Analysis

We have also conducted parameter sensitivity analysis for the proposed method on Y ahoo!Movie and Y ahoo!Music datasets. First, we tested different ↵ values from ¶0↪ 10↪ 100↪ 1000↪ 5000↪ 104 ♦ by setting β to the fixed value used before. The experimental results are reported in Figure 1. We can see that for Yahoo!Movie dataset, the precision values increase when ↵ increases from 0 to 5000. When ↵ = 5000, the model performs the best. Similar results can be observed on Yahoo!Music dataset. According to our objective function in Eq. (4), if ↵ = 0, the model will only use the pairwise ranking loss and will not combine the pointwise recovery loss. On the other hand, if ↵ is too big, the contribution of the pairwise ranking loss can be diminished and the model will become a special version of the SLIM method. Our parameter analysis results suggest that we need a parameter in the middle to keep both types of losses, which indicates the two types of losses can complement each other. To further validate this, we have also compared our proposed approach to its variants that only use each individual loss. We call the variant that drops the pointwise recovery loss (↵ = 0) as pureRanking and the variant that drops the pairwise ranking loss as variant of SLIM. The comparison results are reported in Figure 2. We can see that the proposed approach with integrated heterogeneous loss outperforms both variants that only use a uniform type of loss component. This validated our algorithm design of using heterogeneous losses.

We also conducted parameter sensitivity analysis on the `2norm regularization parameter β. We fixed the value of ↵ as

5000 and choose β value from ¶0↪ 10-3 ↪ 1↪ 103 ↪ 106 ♦. The experiment results with different β values are reported in Figure 3. We can see that the top-N recommendation performance is not sensitive to the β values when β  1000.

5 Conclusion

In this paper, we proposed a novel personalized top-N recommendation approach that exploits novel heterogeneous loss functions based on linear self-recovery models. The heterogeneous loss integrates the strengths of both pairwise ranking loss and pointwise recovery loss to enforce both entrywise consistency and pairwise preference structure consistency between the reconstructed recommendation matrix and the original observation matrix. We formulated the training problem with the heterogeneous loss as a constrained convex minimization problem and develop a projected stochastic gradient descent optimization algorithm to solve it. The proposed approach was evaluated on a set of real world personalized topN recommendation tasks. The experimental results showed that the proposed approach not only outperforms its two variants that only used either the comparison recovery loss or the pairwise ranking loss, but also outperforms a number of stateof-the-art methods on top-N recommendation.