MRLR: Multi-level Representation Learning for Personalized Ranking in Recommendation

1 Introduction

Recommendation is a fundamental task on the Web to mitigate the information overload problem [Su and Khoshgoftaar, 2009]. Recently, representation learning (RL) has attracted a considerable amount of interest from various domains, with recommender systems being no exception [Grbovic et al., 2015; Liang et al., 2016; Vasile et al., 2016; Covington et al., 2016; Barkan and Koenigstein, 2016]. The popularization of RL in recommendation can be mainly attributed to the word embedding techniques (e.g. CBOW and Skip-gram [Mikolov et al., 2013a; 2013b]) originated from the natural language processing (NLP) domain. Word embedding generally refers to the low-dimensional distributed representation of words [Bengio et al., 2003], capturing syntactical and semantic relationships among words. The fast development of RL has enabled a series of methods for NLP tasks, among which the most significant are the extensions of word embedding to learn textual representations in different levels of granularity (e.g. document or paragraph RL [Le and Mikolov, 2014]), so as to help capture richer relationships between words and paragraphs or documents.

In recommendation, RL is used to capture local relationships between items, thus being called item embedding. Item embedding learns low-dimensional item representation by modeling item co-occurrence in individual user's interaction record, thus boosting recommendation accuracy. While it helps learn better item representation, item embedding alone (e.g. Item2Vec [Barkan and Koenigstein, 2016], CoFactor [Liang et al., 2016], Meta-Prod2Vec [Vasile et al., 2016]) does not allow for personalized recommendation. Inspired by document RL (e.g. PV-DM [Le and Mikolov, 2014]), an important branch of work explores the potential of item embedding in personalized recommendation by learning representations for both users and items - as documents and words respectively in NLP (e.g. User2Vec [Grbovic et al., 2015]).

∗The first two authors contribute equally.

We argue that the potential of RL for recommendation has not been fully exploited. Two major aspects have been largely neglected: 1) recommendation is essentially a personalized ranking problem, while existing RL methods only model it as a rating prediction problem; 2) existing methods all ignore the possible multi-level organizations of items for uncovering fine-grained item relationships in recommendation (similar as word-paragraph-document in NLP), which could in turn help achieve better personalized ranking performance.

Personalized Ranking. It has proven that recommendation is better modeled as a personalized ranking problem [Weimer et al., 2007; Rendle et al., 2009]. Existing RL methods, however, optimize towards predicting user preferences over individual items (i.e. rating prediction), instead of predicting user preferences over a list of items (i.e. personalized ranking).

We therefore advocate for a RL method specifically designed for personalized ranking. It is however non-trivial to adapt item embedding to personalized ranking. The original item embedding method only learns from item co-occurrence relationships, whereas for personalized ranking the method has to learn from user-specific lists of items ranked w.r.t. user preferences. We hence first extend the original embedding method to a more generic Bayesian framework, under which we then fuse the likelihood function of user-specific pairwise item ranking. This unified framework can then learn user and item embedding from both item co-occurrence relationships and user-specific ranked lists of items, benefiting from user and item RL while reaching the goal of personalized ranking.

Multi-level RL. To fully exploit RL for better recommendation, we further extend the personalized ranking framework to multi-level RL, so as to capture fine-grained item relationships. Our method is inspired by paragraphs in NLP as the intermediate level of word organization between individual words and documents. Intuitively, each paragraph conveys a key message, and all the words in the paragraph helps support such message. Analogously , we introduce item categories as the intermediate level of item organization between individual items and items rated by the same user, since items with the same category often share similar characteristics. For example, online products are often described by categories as metadata such as clothing, books, electronics, and so on.

Our unified Bayesian framework therefore facilitates multi-level RL by combining RL in all the three levels (i.e. individual item, item category, and user). Although item category has recently been intensively studied [He et al., 2016; Yang et al., 2016], we are the first to investigate it from the perspective of multi-level RL, which enables our framework to capture the relationships of items in local context (i.e. item co-occurrence relationships), in the same category, and in user-specific ranked item list.

Original Contributions. Overall, we contribute a multi-level RL method for personalized ranking based recommendation (MRLR). To the best of our knowledge, we are the first to adopt RL for personalized ranking; meanwhile, we design multi-level RL to capture fine-grained item relationships by leveraging category RL as the intermediate level RL between item RL and user RL, thus to further enhance recommendation performance. Extensive validation on multiple realworld datasets shows that MRLR can consistently outperform state-of-the-art methods, resulting in a 5.18% lift in AUC.

2 RelatedWork

Rating prediction vs. personalized ranking

Recommendation is typically formulated as either a rating prediction problem or a personalized ranking one [Weimer et al., 2007; Steck, 2013]. Personalized ranking has proven to be more direct and efficient than rating prediction, as most recommendations in real-world scenarios are presented in a ranked item list. In general, the rating prediction based algorithms estimate user preferences towards individual items as absolute scores, based on which items are ordered and recommended to users. Typical methods include probabilistic matrix factorization (PMF) [Mnih and Salakhutdinov, 2007], tensor factorization (TF) [Karatzoglou et al., 2010] and factorization machine (FM) [Rendle, 2010]. In contrast, ranking based algorithms directly optimize towards learning users' preferences as personalized ranking on a set of items. Typical methods include CofiRank [Weimer et al., 2007], BPR [Rendle et al., 2009], CLiMF [Shi et al., 2012].

Latent factor model vs. representation learning

State-of-the-art methods for recommendation are dominated by the latent factor model (LFM) [Shi et al., 2014], which maps the high-dimensional user-item interaction matrix to low-dimensional latent user and item matrices. LFM based methods include all the representative rating prediction and ranking based methods mentioned above; in addition, many other effective methods fall into this category, such as NMF [Lee and Seung, 2001], CMF [Singh and Gordon, 2008], SVDFeature [Chen et al., 2012] and SVD++ [Koren, 2008]. While these methods leverage global statistical information of user-item interaction data, they cannot capture fine-grained regularities in the latent factors [Pennington et al., 2014].

Recently, representation learning (RL) based methods have drawnmuch attention. In contrast to LFMbasedmethods, RL based approaches have shown to be highly effective in capturing local item relationships by modeling item co-occurrence in individual user's interaction record [Grbovic et al., 2015; Barkan and Koenigstein, 2016; Liang et al., 2016]. These methods are mostly inspired by the word embedding techniques, which can be traced back to the classical neural network language model [Bengio et al., 2003], and the recent breakthrough of Word2Vec techniques, including CBOW and Skip-gram [Mikolov et al., 2013a; 2013b]).

Representation learning in recommendation

Several RL based methods have been proposed to date. For example, Barkan and Koenigstein [2016] propose a neural item embedding model (Item2Vec) for collaborative filtering, which is capable of inferring item-to-item relationships. Vasile et al. [2016] extend Item2Vec to a more generic model by utilizing side-information to help compute the lowdimensional embeddings of items. However, they all fail to provide personalized recommendation, as embedding techniques are only used to learn better item representation. Several studies extend RL for personalization. Grbovic et al. [2015] first introduce the User2Vec model, which simultaneously learns representations of items and users by considering the user as a "global context". Liang et al. [2016] propose the CoFactor model, which jointly decomposes the user-item interaction matrix and the item-item co-occurrence matrix - equivalent to item embedding [Levy and Goldberg, 2014] - with shared item latent factors. However, all these methods model recommendation as a rating prediction problem.

In contrast, we propose a RL based method by formulating recommendation as personalized ranking. Furthermore, we consider multi-level RL, which can capture fine-grained item relationships in multi-level item organizations, to fully exploit RL for better personalized ranking performance.

3 The ProposedMRLR Framework

This section first formalizes recommendation as a personalized ranking problem, and then presents the multi-level RL framework (MRLR) to achieve the goal of personalized ranking, followed by the model learning methods.

3.1 ProblemFormulation and Objective Function

Suppose we have m users U = {u1, u2, . . . , um}, and n items I = {v1, v2, . . . , vn}. We use the binary user feedback matrix R ∈ Rm×n . If the interaction (rating) from up to vi is observed, indicating up prefers vi, then Rpi = 1; otherwise 0. I + up is the set of items that user up prefers. Dr ={(up, vi, vj)|up ∈ U, vi ∈ I + up , vj ∈ I\I + up } is the set of user-specific ranking triples indicating up prefers vi to vj , where I\I + up denotes the set of items that up has no interaction with. Dc={(up, vi, vk)|up ∈ U, vi, vk ∈ I + up } is the set of item co-rated triples indicating up prefers both vi and vk. For each user, we aim to provide a personalized ranking list of items that she has not interacted with.

More specifically, our goal is to design a unified multilevel RL framework (MRLR) to learn user and item embeddings from both item co-rated relationships and user-specific ranked lists of items, thus to benefit from user and item RL, as well as to reach the goal of personalized ranking. We define the objective function of MRLR using a Bayesian framework, maximizing the following posterior probability,

where Θ is the set of parameters in MRLR, D is the observed data. It is proportional to maximizing the likelihood of the observed triples given the embeddings, i.e., P(D|Θ). We define the likelihood function as the joint probability of item co-rated triples and user-specific ranking triples, i.e., P(Dc,Dr|Θ). Assuming the item co-rated triples and userspecific ranking triples are conditionally independent, the joint probability is then reformulated as follows:

where P ((up, vi, vk)|Θ), P ((up, vi, vj )|Θ) denote the conditional probability of item co-rated triples and user-specific ranking triples, respectively. Hence, the MRLR framework seamlessly fuses the two components: (1) item co-rated triples for better user and item embedding; (2) user-specific ranking triples for personalized ranking. Besides, through multi-level RL, MRLR can fully exploit RL from a multilevel item organization, i.e., items in user-specific ranked list, items in a same category, and individual items, to capture fine-grained item relationships for better recommendation.

3.2 Modeling User and ItemEmbedding

For each user up and item vi ∈ I + up , the Skip-gram method [Mikolov et al., 2013a; 2013b] aims at predicting the probability of item vk ∈ I, (i ̸= k) also preferred by up, i.e. P(vk|vi), which is calculated by the softmax function:

where vi, vk, vg are embeddings of items vi, vk, vg. To allow for personalization, we model user up's preference towards item vk by a similar softmax function:

where up denotes the user embedding of up.

We now model the item co-rated triples P((up, vi, vk)|Θ). It should properly accommodate both the item co-rated relationships (Eq.3), and personalization (Eq.4). Instead of directly optimizing P((up, vi, vk)|Θ), we optimize the conditional probability P(vk|(up, vi),Θ), P(vi|(up, vk),Θ) and P(up|(vi, vk),Θ). Since we aim to recommend items to given users, we do not need to model P(up|(vi, vk), Θ). We take P(vk|(up, vi)Θ) for example. Inspired by document RL in NLP [Le and Mikolov, 2014], the user and item embeddings up, vi are summed as the new condition to predict the probability of vk rated by up, given by,

where α1 +α2 = 1.0; exp(α1uTp v′k +α2vT i v′k ) aims to take into account both the personalized aspect by the term uTp v′k , and item co-rated relationships by the term vT i v′k . We model P(vi|(up, vk), Θ) in a similar way.

3.3 Modeling Personalized Ranking

We now proceed to model the user-specific ranking triples P((up, vi, vj)|Θ), to achieve the goal of personalized ranking. Similarly, we optimize the conditional probability of P((vj, vi)|up,Θ) and P(up|(vj, vi),Θ) instead of P((up, vi, vj)|Θ). As our goal is to recommend items, we only consider P ((vj , vi)|up, Θ), which involves a user's preference over a pair of items. Based on Eq.4, we further deduce a user's preference on a pair of items. As the triple (up, vi, vj ) indicates that up prefers vi to vj, it means that for up, we should maximize the probability that vi is preferred by up but vj is not favored by up. We denote such probability by P ((¬vj , vi)|up, Θ), which is defined as below:

where the term exp(uTp v′i - uTp v′j ) denotes the preference difference of user up towards items vi and vj.

3.4 ModelingMulti-level ItemOrganization

We further consider multi-level granularity of item organizations to capture fine-grained item relationships. Specifically, we introduce item category as the intermediate level between items in the same user-specific ranked list and individual items. The rationale behind is that items in a same category generally share similar characteristics.

To integrate the influence of item category for better recommendation, we extend our framework to multi-level RL. The item embedding is thus reformulated as,

where Cvi is the set of categories that vi belongs to; |Cvi | is the size of Cvi ; cl is the embedding for category cl. By replacing the item embedding in Eq.5 and 6, the category RL can adapt item embedding, serving as the intermediate level RL. MRLR can now capture fine-grained relationships of items in local context (i.e., item co-rated relationships), in the same category, and in user-specific ranked item list.

3.5 Model Learning

Optimizing our MRLR framework is proportional to minimizing the negative log-likelihood function, given by,

Algorithm 1: The optimization of MRLR

Input: R, C, λΘ, α, γ, d, iter 1 Initialize Θ = {u, v, c} with small values; 2 Randomly sample (up, vi, vj) for Dr; // Negative sampling procedure 3 foreach (up, vi, vk) ∈ Dc, and (up, vi, vj) ∈ Dr do 4 DrawN negative instances from the distribution P(Dc ) ; 5 DrawN negative instances from the distribution P(Dr ) ; // Parameter update 6 for t = 1; t ≤ iter; t ++ do 7 foreach (up, vi, vk) ∈ Dc, and (up, vi, vj) ∈ Dr do 8 u(t) p ←u(t-1) p -γ∇J(up) ; 9 v(t) ← v(t-1) - γ∇J (v), v={vi, vj , vk, vg , vh} ; 10 for l = 1; l ≤ |Cv|; l ++ do 11 c(t) l ← c(t-1) l -γ∇J(cl) ; 12 if J has converged then 13 break;

where Ω(Θ) is the regularizer to prevent over-fitting, and λΘ is the regularization coefficient. To solve the optimization problem, we apply the stochastic gradient descent (SGD) method to the objective function J .

Approximation of softmax function

It is impractical to directly adopt the softmax functions P (vk|(up, vi), Θ), P (vi|(up, vk), Θ) and P ((¬vj , vi)|up, Θ) to optimize our framework, since the cost of computing the denominators of these functions is proportional to the total number of items (n), which is considerably huge in realworld applications. To accelerate the speed, we adopt negative sampling proposed in [Mikolov et al., 2013b]. Take P (vk|(up, vi), Θ) as an example, which can be approximated via negative sampling as follows:

where σ(x) = 1/(1 + exp(-x)) is the sigmoid function; Dc = Dr is the opposite triple set of Dc ; P(Dc ) is a function randomly sampling instances from Dc . N is the number of negative instances to be drawn per positive instance. The idea behind negative sampling is that we want to maximize the similarity between vk and (up, vi) and minimize the similarity between a randomly sampled item vg and (up, vi). In this way, we can approximately maximize P (vk|(up, vi), Θ).

Similarly, P (vi|(up, vk), Θ), P ((¬vj , vi)|up, Θ) are also approximated via negative sampling. One issue we should deal with is that computing the numerators of the softmax function P((¬vj, vi)|up,Θ) is also very expensive, as we have at least O(mn ∗ min(|I + u1 |, · · · , |I + um |)) training triples in Dr, where |I + um | is the size of I + um . We thus randomly sample userspecific ranking triples instead of using all the triples. The optimization process is shown in Algorithm 1, which is mainly composed of two steps, i.e., negative sampling (line 3-5), and parameter update (line 6-13).

Complexity analysis

The computational time is mainly taken by evaluating the objective function J and updating the related variables. The time to compute J is O(d|Dc| + d|Dr|), where d is the dimension of embeddings, and |Dc|, |Dr| are the sizes of item co-rated triples and user-specific ranking triples, respectively. For all gradients ∇J(up),∇J(vi),∇J(cl), the computational time are O(d|Dc| + d|Dr|), O(d|Dc| + d|Dr|) and O(d(|Dc| + |Dr|)|Cvi |), respectively. |Cvi | is generally no larger than 10 in real-world applications [Yang et al., 2016]. Hence, the overall computational complexity is (#iteration∗ O(d|Dc| + d|Dr|)). Specifically, |Dc| ≤ mq(q - 1)/2, where q = max (|I + u1 |, · · · , |I + um |). In real-world, q is typically small (e.g., power-law distribution). For Dr, as illustrated before, we adopt the random sampling method to reduce its number. To sum up, MRLR is scalable to large datasets.

4 Experiments and Results

4.1 Experimental Setup

Datasets. We adopt the Amazon Web store data [McAuley et al., 2015], which contains a series of datasets from various domains (e.g., clothing, electronics). To evaluate the effectiveness of MRLR, we choose four datasets, including Clothing, Electronics, Sports, Home. Besides user-item interactions, the datasets also include the categories that each item belongs to. We uniformly sample the datasets, to balance their sizes in the same order of magnitude for cross-dataset comparison. Table 1 reports the statistics of the datasets.

Comparison Methods. We compare with seven state-ofthe-art algorithms, 1) PMF [Mnih and Salakhutdinov, 2007]: probabilistic matrix factorization; 2) BPR [Rendle et al., 2009]: Bayesian personalized ranking; 3) FM [Rendle, 2010]: factorization machine fusing item category. We only compare with FM, as it generally outperforms other LFM based methods; 4) Item2Vec [Barkan and Koenigstein, 2016]: item embedding based method; 5) Meta-Prod2Vec [Vasile et al., 2016]: fuses item category based on Item2Vec; 6) CoFactor [Liang et al., 2016]: jointly factorizes rating and item co-rated matrices; 7) User2Vec [Grbovic et al., 2015]: considers the user as a global context while learning item embedding; Besides, four variants of our framework are compared, a) RL: RL model only considering user and item embedding ; b) PR: personalized ranking model; c) RLR: the RL model combining a) and b); d) MRLR: multi-level RL model with multi-level item organizations based on c).

Evaluation. Standard 5-fold cross validation is adopted to evaluate all the methods. The Area Under the ROC Curve (AUC) is used as the evaluation metric. Larger AUC indicates better recommendation performance.

Parameter Settings. We empirically find out the optimal parameter settings for all method. We set d = 10. We apply a grid search in {0.001, 0.01, 0.1, 1.0} for the learning rate γ, λΘ and 1/2-way regularization of FM, and a grid search in {1, 5, 10, 20, 50} for the number of negative instances N.

4.2 Results of MRLR

Results of Variants. The performance of our four variants is depicted by Figure 1. RLR outperforms both PR and RL by 3.54% and 1.42% in AUC respectively (both significant, Paired t-test with p-value < .01), showing the effectiveness of both representation learning and personalized ranking. MRLR combining RLR with multi-level item organizations, performs the best among the four variants - with 1.12% lift in AUC compared to RLR (p-value < .01), indicating the benefit of considering fine-grained item relationships.

Impacts of Parameter α. Parameters α1, α2 control the importance of personalization and item co-occurrence relationships as shown in Eq.5. α3 controls the effect of item category for adapting item embedding as shown in Eq.7. We apply a grid search ranging from 0 to 1 with step 0.1 to investigate their impacts. As α1 + α2 = 1, we only study the impacts of α1, α3, and we fix one and vary the other each time. The results are described by Figure 2. For the four datasets, as α1 varies from small to large, the performance first increases then decreases, with the maximum reached at around 0.8. This indicates that user preferences play an important role in item recommendation. In terms of α3, we observe that the optimal settings range from 0.1 to 0.2, denoting a substantial contribution of item category in recommendation. The similarity in performance variation across α1, α3 values on the four datasets demonstrates the robustness of MRLR.

Visualization of Embeddings. MRLR framework can generate meaningful embeddings that help interpret recommendation results. To show this, we visualize the embeddings of users, items and categories learnt by MRLR in a two dimensional space using t-SNE [Maaten and Hinton, 2008]. Figure 3 illustrates the results of two examples in the Clothing dataset. For conciseness, we do not visualize the other datasets, however, similar observations as below can be obtained: 1) the rated items and the recommended items are generally clustered. This indicates certain similarity among the rated items and the recommended items to the same user. 2) each cluster is located at the side of the user, and the user is represented as an endpoint of these clusters, indicating that user preference can be manifested as the direction along which the rated items are clustered. This suggests that the recommendations are determined by both rated items and user preferences. Finally, we note that the categories of recommended items are overlapped with those of the rated items. For instance, for the user in the right plot the overlapped category is Shirts, indicating user preference over shirts. For the user in the left plot the overlapped categories are Athletic, Fashion Sneakers, and Sandals, indicating that the user has a more diverse set of preferences. These observations show that MRLR can capture meaningful item relationships in multiple levels of item organizations - individual items, items in the same category, and items rated by the same user.

4.3 Comparative Results

Table 2 summarizes the performance of all comparison methods. Two views are considered: 'All Users' indicates all users are considered in the test data; while 'Cold Start' indicates only users with less than 5 ratings are involved in the test data. Several interesting findings are observed as follows.

Among the latent factor model based methods (PMF, BPR and FM), PMF performs the worst, as it is the basic rating prediction method without considering any auxiliary information. FM incorporates item category as auxiliary input, significantly outperforms PMF, indicating the effectiveness of item category for better recommendation. Interestingly, the performance of FM is worse than that of BPR. This verifies that personalized ranking is more effective than rating prediction in real-world recommendation scenarios.

The RL methods, including Item2Vec, MetaProd2Vec, CoFactor and User2Vec, generally perform better than latent factor based methods, despite being rating prediction models. This confirms that representation learning is more effective than latent factor models for recommendation. Among them, Item2Vec performs worse than MetaProd2Vec. This observation further confirms the previous conclusion that item category is useful to improve recommendation performance.

CoFactor and User2Vec consider personalization in addition to item embedding. CoFactor is equivalent to the CMF method as it simultaneously factorizes user-item and item-item co-occurrence matrices with shared item latent factors, while User2Vec adopts CBOW to integrate personalization. Theoretically, the performance of the two methods should be better than that of Item2Vec, since they can provide users with personalized item list. We empirically find that User2Vec outperforms CoFactor, but both are slightly worse than Item2Vec. However, our proposed variant RL with Skipgram outperforms Item2Vec, by 6.37% on average (Figure 1). Hence, we conjecture that considering personalization with Item2Vec helps improve recommendation performance, but CMF, CBOW are less effective than Skip-gram in incorporating item co-occurrence relationships with personalization.

Overall, compared with all the other methods, MRLR performs the best by learning user and item embeddings from a multi-level item organization, i.e., items in user-specific ranked list, items in the same category, and individual items. The improvements w.r.t. 'All User' and 'Cold Start' are 5.35%, 5.01% on average (both with p-value < .01), respectively. This implies that recommendation performance can be further enhanced by appropriately considering multi-level representation learning and personalized ranking.

Impacts of Data Sparsity. We further study the impacts of data sparsity on the recommendation performance. Figure 4 depicts the variation of performance of all methods on Clothing & Electronics when the percentage of training data size w.r.t. the overall data size increases from 50% to 90%. We observe that MRLR consistently outperforms other methods across all levels of data sparsity. Furthermore, the performance of MRLR with data sparsity at 60% is better than that of any of other methods with data sparsity at 90%. Such observations also hold in other datasets, showing that MRLR

can achieve better performance even with high data sparsity. Generalizability. To evaluate the generalizability of MRLR, we further collect data of Foursqure check-in performed over 3 weeks in 4 European capital cities (Amsterdam, London, Paris, Rome), published on Instagram (31,872 users perform 198,801 check-in at 41,387 locations that belong to 492 categories) and Twitter (18,522 users; 109,790 check-in; 38,855 locations; 482 categories). Figure 5 compares the performance of MRLR and the other methods. As in the previous setting, MRLR significantly outperforms (p-value < .01) the second best method MetaProd2Vec by 5.10% on 'All Users' and 5.62% on 'Cold Start'. These results show that MRLR can be effective in multiple recommendation tasks.

5 Conclusions

Representation learning (RL) has drawn much attention in recommendation, due to its effectiveness in capturing local item relationships. However, all existing RL based methods model recommendation as a rating prediction problem while recommendation is essentially a personalized ranking one. Besides, they all neglect multi-level organizations of items for fine-grained item relationships. Hence, this paper proposes a multi-level RL framework for personalized ranking - MRLR, which learns user and item embeddings from a multi-level item organization for better recommendation. MRLR, therefore, benefits from RL as well as achieves the goal of personalized ranking. Empirical validation on realworld datasets shows that MRLR significantly outperforms state-of-the-art algorithms.

Acknowledgements

This work is supported by the SIMTech-NTU Joint Laboratory on Complex Systems. This work is partially funded by the Social Urban Data Lab (SUDL) of the Amsterdam Institute for Advanced Metropolitan Solutions (AMS).