A Framework for Recommending Relevant and Diverse Items

1 Introduction

In traditional recommendation systems, a few top items are recommended to users. The traditional approaches to this top-k recommendation problem focus on the relevance of results only: they make use of some standard recommendation algorithm that computes the relevance score of each item with regard to the user individually then just return the top-k items with the highest relevance scores. However, many recent studies have shown theoretically and empirically that it is beneficial to take the diversity of results into account as well [Zhang and Hurley, 2008; Zhou et al., 2010; Qin and Zhu, 2013], particularly when different users with diverse interest. Recommending a diverse set of the most relevant items is more likely to ensure that all potential needs of a given user are satisfied. So finding the best set of top-k items for a given user is of crucial importance to recommendation systems.

In order to resolve the user interest ambiguity and avoid the redundancy in the recommendation itemset, a number of diversification techniques [Zhang and Hurley, 2008; Zhou et al., 2010; Qin and Zhu, 2013; Ashkan et al., 2015] have been designed which optimize the top-k items collectively, in terms of both relevance and diversity. Most of these former work, e.g., Entropy Regularized [Qin and Zhu, 2013], defines some objective functions to tradeoff between maximizing relevance and maximizing diversity. Although the work of [Qin and Zhu, 2013] also coined the diversity promotion problem as a submodular function maximization problem with a theoretical guarantee, the intuition behind the diversification term using the entropy of rating of recommended items is not sound. Furthermore, the coverage of user's interest is not explicitly taken into account.

In this paper, we first develop an alternative framework for recommending relevant and diverse items. We formalize the problem as finding a top-k items which maximizes a linear combination of the relevance of the item, the coverage of the user's interest, and diversity between them. We detail three instantiations of the proposed framework. Due to the NPhardness of the proposed problems, we employ greedy search algorithm with theoretical approximation guarantee of factor for each optimization problem. For one specific case (Case 2 in Section 4), we give a more detailed theoretical analysis and prove the submodularity of the proposed objective function. Compared to the previous approach taking advantage the submodular property of the optimization objective [Qin and Zhu, 2013], the proposed approach significantly improves not only the precision (i.e., the quality of the final result set) but also the diversity between the recommended items. The advantages of our new approach over the existing ones are confirmed by extensive experiments on MovieLens dataset. Our contributions can be summarized as follows:

1. We formalize item recommendation as a combinatorial optimization problem which combines the relevance of items, coverage of the user's interest and diversity between items.
2. We detail the framework under three cases. Based on the theoretical analysis, we design efficient greedy algorithms to get the near optimal solutions for those NPhard problems.
3. We conduct extensive experiments on MovieLens dataset, which include performance comparisons with state-of-the-art methods. The experimental results demonstrate the effectiveness of our proposed solutions in terms of precision and diversity.

The rest of the paper is organized as follows. The related work is presented in Section 2. Then the latent matrix factorization and submodular function maximization is reviewed in Section 3. Section 4 is devoted to the formulation of the proposed framework and the algorithms. Experimental evaluation using real data are shown in Section 5. We conclude with future work in Section 6.

2 RelatedWork

The Collaborative Filtering (CF) which establishes the connection between users and items is commonly used in recommendation systems. Two popular approaches are the neighborhood models (user or item based) [X.Su and Khoshgoftaar, 2009] and the latent matrix factorization methods, e.g. Regression- Based Latent Factor Model [Agarwal and Chen, 2009], Probabilistic Matrix Factorization [Salakhutdinov and Mnih, 2008], and Singular Value Decomposition [Koren and Bell, 2011]. In this paper, we diversify items recommended by singular value decomposition.

In recent year, there has been some work on diversifying the recommendation lists to increase users satisfactions. These works can be classified into two categories based on the way how diversity is measured: content-based and temporalbased.

In content-based diversification, which is known as an instance of p-dispersion problem [Drosou and Pitoura, 2010]. Most of the content-based recommendation diversification methods so far are attributes based. In [Ziegler et al., 2005], the diversity of recommendation lists is increased through maximizing the topic attribute difference between items. In [Yu et al., 2009], item explanation is employed to measure the distance between items to achieve diversification instead of item attributes. The work of [Noia et al., 2014] focuses on modeling users' inclination toward selecting diverse items, where diversity is computed by means of content-based item attributes. This modeling is exploited to re-rank the list of Top-N items predicted by a recommendation algorithm, in order to foster diversity in the final ranking. And the state-ofart conditional differential entropy h(rS♣r⌦↪ V ) is employed in [Qin and Zhu, 2013] as a diversity regularizer. However the entropy measures the average uncertainty of ratings, rS, which might not characterize the diversity between items.

There are works to use temporal information for recommendation diversification, e.g. [Lathia et al., 2010] examines the temporal characteristics of item rating patterns to increase recommendation diversity, and [Zhao et al., 2012] increases temporal diversity with product purchase intervals. [Nguyen et al., 2014] studies the "filter bubble" effect, which describe the potential for online personalization to effectively isolate people from a diversity of viewpoints or content, in terms of content diversity at the individual level and exposes users to a slightly narrowed set of items over time.

Besides diversifying the recommendation lists, the aggregate diversity is also introduced in works such as [Yin et al., 2012; Niemann and Wolpers, 2013; Adomavicius and Kwon, 2012]. They treat diversity of item as the aggregate or equivalently average dissimilarity of all pairs of items in the recommended set.

3 Preliminary

Before diving into the proposed framework, we introduce the latent matrix factorization method and submodular function maximization, which our framework and the proposed algorithms are based on.

3.1 Latent Matrix Factorization

Matrix factorization models [Koren et al., 2009] are the most pervasive method employed in recommendation systems, which map both users and items to a joint latent factor space of some dimensionality D, such that user-item interactions are modeled as inner products in that space. Accordingly, each user u is associated with a vector pu 2 RD , and each item i is associated with a vector qi 2 RD . For a given user u, the components of pu measure the extent of interest the user has on the corresponding factors. For a given item i, the components of qi measure the extent to which the item possesses those factors. The resulting dot product, pu · qi, captures the interaction between user u and item i - the user's overall interest in the item's characteristics. This approximates user u's rating of item i, which is denoted by rui, leading to the estimation

To learn the factor vectors (pu and qi), the regularized squared error is minimized on the itemset with known ratings (training set):

Here, R is the set of the (u↪ i) pairs for which rui is known (the training set). The parameters can be learned through stochastic gradient descent optimization method [Koren et al., 2009].

3.2 Submodular FunctionMaximization

A function f : 2X ! R is submodular if for any S ✓ T ✓ X and i ◁2 T, f(S [ ¶i♦) - f(S) ≥ f(T [ ¶i♦) - f(T). In other words, submodular functions are characterized by the diminishing return property: the marginal gain of adding an element to a smaller subset of X is higher than that of adding it to a larger subset of X. We are often interested in finding a subset of with cardinality constraint ♣S♣  k that maximizes a submodular function, i.e., argmaxS f(S) [Krause and Golovin, 2012]. However this problem is in general NPhard, even for some simple submodular functions such as mutual information [Krause and Guestrin, 2005]. In recent years, submodular functions have been receiving much attention from the Artificial Intelligence community because of the insight about their approximate optimization [Wei et al., 2015; Vanchinathan et al., 2015]. The submodularity of the objective function provides a theoretical approximation guarantee of factor 1 - 1e for the (best-first) greedy search algorithm [Nemhauser et al., 1978]:

Theorem 1. Let f be a submodular, (monotone) nondecreasing set function and f(;) = 0. Then, the greedy (search) algorithm finds a set S (♣S♣ = k) such that

4 Proposed Approach

In this section, we give the main contribution of our work: formulating the item recommendation as a combinatorial optimization or search problem, which takes the relevance of items, the coverage of user's interest and diversity between items into account.

4.1 Diversification Framework

For a given user u and the itemset ⌦ that u rated, we aim to recommend the top-k relevant and diverse item subset S ✓ I ∩ ⌦ with the size constraint ♣S♣ = k. We leverage the estimated parameter through matrix factorization for the task. One possible strategy is to select the items which user u has interest and are similar to the highly rated ones. However, this simple idea does not account for similarity between the recommended items that could be redundant. Therefore, a natural objective is to maximize the sum of the relevance and dissimilarity of the recommended items which also explicitly takes user's interest into account. Formally, we recommend the itemset S ✓ I ∩⌦ (♣S♣ = k) which maximizes the following objective function:

where ↵ and β are the control parameters, and ♣♣qi - qj♣♣ is the Euclidean distance between item vectors qi and qj. The weight wj of item j can be set as 1 or wj = eγ-(rmax-ruj) . The intuition behind wj is that maybe the user is interested in some kinds (or type, genre) of items while the rated ones are with low quality. Therefore we could introduce the weight wj to quantify the "importance" of item j.

For ease of discussion, we use the notation f(S) = Pi2S pu · qi + ↵ Pj2⌦ wj maxi2S qi · qj and d(S) = Pi↪j2S ♣♣qi - qj♣♣. The term f(S) in function (2) is used to control the relevance of the selected items and the coverage of the user's interest which is achieve through tradeoff the similarity of recommended items to the rated items. The intuition behind Pj2⌦ wj maxi2S qi · qj is that we recommend the items qi 2 S similar to those rated by the given user (qj 2 ⌦) to cover the user's potential interest, which bears resemblance to item-based nearest neighbor methods. Furthermore, it can diversify the recommended items due to the return diminishing property as proved in the following subsection. The dispersion term d(S) in (2) is used to enhance the diversity within the recommended itemset S.

When both parameters ↵ and β are set to 0 (↵ = 0↪ β = 0), the objective function (2) is degenerated to the naive top-k item recommendation problem which just returns the items with the highest estimated rating. It is regarded as one of the baselines in the experimental evaluation. We detail other settings in the following subsections.

4.2 Case 1: ↵ = 0↪ β > 0

In this case, the objective function is sum of modular function (Pi2S pu · qi) and dispersion function (βd(S)). The intuition is that we recommend the items with highly estimated rating and with large distance between them. The Algorithm 1 Greedy Search for Modular-MaxSum Dispersion Input: The item matrix Q, the itemset ⌦ rated by u, and integer k

Output: Item subset S ✓ I ∩ ⌦ with ♣S♣ = k

• 1: S Φ;
• 2: for iter = 1 to iter < k◁2 do
• 3: (i↪ j) argmaxi0 ↪j 02I-S d0 (i0 ↪ j 0 )
• 5: end for
• 4: S S [ ¶i↪ j♦
• 6: if k is odd, add an arbitrary item to S
• 7: return S

optimization problem can be seen as a variant of Maximum Sum Dispersion problem [Hassin et al., 1997] which has been applied in diversifications such as search result diversification [Gollapudi and Sharma, 2009]. Generally, the maximum sum dispersion problem is NP-hard, therefore we resort to an approximation algorithm. In this paper, we employ a greedy algorithm of [Hassin et al., 1997] which is a 12 -approximation algorithm. The algorithm is outlined in Algorithm 1, where the distance measure is defined as d0 (i↪ j) = pu · qi + pu · qj + β♣♣qi - qj♣♣ which is metric thanks to the fact that the Euclidean distance ♣♣qi - qj♣♣ is a metric.

When setting β = 0, we have that g(S) = f(S). In this case, we aim to recommend the items with high rating and similar to the rated ones. However the optimization problem maxS:♣S♣K f(S) is also NP-hard, which can be reduced from facility location problem. Fortunately, the simple greedy hill-climbing heuristic mentioned in section 3.2 can be used to get an 1 - 1e approximation ratio thanks to the properties of function f(S) established in the following theorem.

Theorem 2. f(S) is monotonic and submodular.

Proof. For any S ✓ T and i ◁2 T ,

As all terms in the last expression are nonnegative, we know that f(S[¶i♦) ≥ f(S), i.e. the function f(S) is monotonic non-decreasing.

Similarly, we have

We know that maxl2S ql · qj  maxl2T ql · qj for each item j thanks to the fact that S ✓ T. It is followed that Pj2⌦ wj max¶0↪ qi · qj - maxl2S ql · qj♦ ≥

Algorithm 2 Greedy Search for Submodular Function Maximization

Input: The item matrix Q, the itemset ⌦ rated by u, and integer k

Output: Item subset S ✓ I ∩ ⌦ with ♣S♣ = k

• 1: S ¶argmaxi2I∩⌦ pu · qi♦;
• 3: i argmaxi02I-S pu · qi0 +↵ Pj2⌦ wj max¶0↪ qi0 · qj -maxl2S ql · qj♦
• 2: while ♣S♣ < k do
• 4: S S [ ¶i♦
• 6: return S
• 5: end while

Pj2⌦ wj max¶0↪ qi · qj - maxl2T ql · qj♦. Therefore we have that f(S [ ¶i♦) - f(S) ≥ f(T [ ¶i♦) - f(T), i.e. the function f(S) is submodular.

Note that although the explicit dispersion between the items is not considered in this case, the submodularity or diminishing property of f(S) can be used to diversify the selected items. The near optimal solution is presented in Algorithm 2, where the item maximizing pu · qi + ↵ Pj2⌦ wj max¶0↪ qi · qj -maxl2S ql · qj♦ is selected into S incrementally after the first item.

4.4 Case 3: ↵ > 0↪ β > 0

In this case, we enhance the diversity between recommended items through including the sum dispersion of items. The optimization problem maxS:♣S♣k g(S) is also NP-hard. Fortunately, the approximation algorithm proposed in [Borodin et al., 2012] can be employed in our solution. As stated in [Borodin et al., 2012], the approximation algorithm has 12 approximation ratio when the objective function is a linear combination of a submodular function and the sum of pairwise distance. We have proved the submodularity of function f(S) in the above case. Therefore the objective function proposed in this paper, g(S) = f(S)+βd(S), is a variant of the formulation developed in [Borodin et al., 2012].

To be specific, we denote d(S) = P¶i↪j♦:i↪j2S ♣♣qi - qj♣♣ and d(S↪ T ) = P¶i↪j♦:i2S↪j2T ♣♣qi -qj ♣♣ for any disjoint subsets S↪ T ✓ I. For any given subset S ✓ I and any item i 2 I -S, let di(S) = Pj2S ♣♣qi - qj♣♣ be the marginal gain on the distance, fi(S) = f(S [ ¶i♦) - f(S) be the marginal gain on the weight, and gi(S) = fi(S) + βdi(S) be the total marginal gain on the objective function. Let f 0 i (S) = 12 fi(S), and g0i (S) = f 0 i (S) + βdi(S). The final solution is presented in Algorithm 3.

5 Experiments

We evaluate our proposed method on real dataset (MovieLens dataset) compared to the current state-of-the-art diversification methods.

5.1 Data Set

The experiments are carried out on publicly available rating datasets, MovieLens dataset. It consists of 1,000,209 ratings Algorithm 3 Greedy Search for Submodular-MaxSum Dispersion Input: The item matrix Q, the itemset ⌦ rated by u, and integer k

Output: Item subset S ✓ I ∩ ⌦ with ♣S♣ = k

• 1: S φ;
• 2: while ♣S♣ < k do
• 4: S S [ ¶i♦
• 3: i argmaxi2I-S g0i (S)
• 5: end while
• 6: return S

for 3952 movies by 6040 users of homonym online movie recommender service. All users are selected randomly, and each of them has rated at least 20 movies. After the elimination of the cold-start movies (with less than 10 ratings), we still have 3385 movies and 6040 users. The element of the dataset is represented by a tuple: tu↪i = (u↪ i↪ ru↪i), where u denotes userID, i denotes movieID, and ru↪i, which is an integer score between 1 and 5, denotes the rating of user u for movie i (higher score indicates higher preference).

5.2 Baselines

In order to show the performance improvement of our approach, we compare our approach with the following baselines:

1. PMF: PMF is the standard probabilistic matrix factorization, which is considered as the state-of-art recommendation method. Specifically, we seek to find a set maximizes the following criteria:

which is the case that both ↵ and β are set to zero in our framework.

2. PMF+ER: Entropy Regularizer is proposed in [Qin and Zhu, 2013] to promote the diversity within the recommended itemset. More specifically, ER seeks to find a set maximizes following criteria

where R(S) = P!2S (E[r!♣r⌦↪ V ] - c) and g(S) = h(rS ♣r⌦↪ V ).

5.3 EvaluationMetrics

Following the work of [Zhang and Hurley, 2008; Qin and Zhu, 2013], we split the dataset into a training dataset YT and a test dataset YP by randomly assigning 50% of tuples in MovieLens to each set. The training dataset YT was used to train the PMF model, such that we can get the item vectors. And we define user profile Pu as the set of movies rated by u, and test user profile Tu is the 50% of Pu in test dataset YP . Let ♣Pu♣ and ♣Tu♣ denote the size of the profile.

We use two different metrics to measure the quality of the recommendation list: 1. Precision which is used to measure the accuracy of our proposed approach or the relevance of the recommended items. 2. The diversity between items recommended by diversification methods.

Formally, when a itemset Su with size ♣Su♣ = k is recommended to user u, the precision is measured as follows:

where U denotes the set of all users. Note that we do not aim to predict the ratings of movies, but to make a more satisfying top-k recommendation list [Qin and Zhu, 2013]. The precision is a more appropriate metric than the Mean Absolute Error (MAE).

To measure the average dissimilarity of all pairs of elements contained in Su, the diversity between items is defined as follows [Nguyen et al., 2014]:

where k = ♣Su♣, and d(i↪ j) = 1- qiqj kqikkqjk is the distance or dissimilarity between items i↪ j 2 Su.

5.4 Results

For the parameter setting, we set the dimensionality of the latent space D = 80◁100◁120 when training the PMF model. Both the baselines and our approach take the same settings, and we choose to use a learning rate of 20, regularization parameter of 0.1, and a momentum of 0.3. In addition, for "PMF+ER", we set λ = 1 which is the best result compared to other settings. While for our approach, we set ↵ = 0▷3 and β = 1▷5. We will examine the impact of parameters, ↵ and β in the next section.

The experimental comparisons between three methods in terms of Precision and Diversity are shown in Table 1 and 2, where our approach is labeled as "PMF+↵ + β". In those experiments, we vary the number of recommended items, i.e. we recommend top-5, 10, 15, 20, 25, 30 movies to each user. As excepted that PMF provides the worst performance. Our approach significantly outperforms both "PMF" and "PMR+ER". The results in Table 1 shows that the diversity promoting methods (both ER and β) can match the users' preference. As can be seen rom the Table 2, our method "PMF+↵+β" is more effective for capturing the notion of diversity between items compared to "PMF+ER". For individual case of top-k prediction, where k = 5◁10◁15◁20◁25◁30, our approach outperforms both baselines in terms of precision and diversity. The introduction of coverage of user's interest in our objective is beneficial to the promoting the precision and diversity compared to "PMR+ER". As we mentioned in Section 1, the diversity between item characteristic can not be captured by the entropy of the rating scores.

Impact of ↵ and β

In our approach, the parameter ↵ controls the matching with user's kind (or type, genre) interest and the coverage of the user's interest, and β controls the diversity. When ↵ = β = 0, the method is degenerated to find the movies with the highest rating. If ↵ = +1 and β = 0, the model seeks to find the movies that are most similar to user preferred kind (or type, genre). If ↵ = 0 and β = +1, the model seeks to find the most diverse movies. And if ↵ > 0 and β > 0, we will get a result which tradeoff between user's preferred kind, the coverage of user's interest and the diversity.

The impacts of ↵ and β on Precision and Diversity are shown in Figure 1 and 2 respectively. Here we also include the precision by baselines PMF and PMF+ER as a control. As can be seen that in every case of top-k prediction (i.e. k 2 10↪ 20↪ 30), PMF+↵+β outperforms PMF+ER and PMF in terms of both precision and diversity. More remarkable, as ↵ stays 0 and β increases, while the prediction precision by PMF+↵+β increases at first, then it decreases to steady and with little rebound sometimes. More interestingly, as ↵ varies between 0.1 and 0.5 and β increases, the prediction precision by PMF+↵+β increase at beginning, but when the value of β reaches a certain threshold, the precision begins to decrease. Compared with the case that ↵ = 0, when ↵ varies between 0.1 and 0.5, then precision increases then stays more smoothly. It is reasonable that the effectiveness is due to the coverage of the user's interest when ↵ > 0 and it has the marginal return diminishing property (submodularity). As for the prediction of diversity by PMF+↵+β, with the increase of β, it increases at first, and then it is stable. Comparing the case that ↵ = 0 and varies between 0.1 and 0.5, when ↵ stays 0, it is more diverse between items. It shows that there is a tradeoff between enhancing the personalization of user and increasing the information of recommendation.

6 Conclusion

In this paper, we propose a general framework to recommend relevant and diverse items. We detail the framework through studying three cases and providing theoretical analysis and designing approximation algorithms for these NPhard problems. Experimental results on MovieLens dataset demonstrate that our approach outperforms state-of-the-art techniques in terms of both accuracy and diversity. We leave the speedup of the diversification process as pointed out in [Ashkan et al., 2015] and introduction of more explicit user's interest distribution into our framework as the future work.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (NFSC) under Grants No. 61540002 and No. 61572135.