Promoting Diversity in Recommendation by Entropy Regularizer

1 Introduction

Recommender system has become an important information filtering tool to provide people with items (e.g. movie, online app) they appreciate [1, 4, 2, 18]. Different from another famous information filtering task search engine, one of the challenges of recommender system is that we do not exactly know what users needs. What recommender systems do is to anticipate users' interests according to existing data. On this point, many recommendation techniques [9, 10, 15, 23] rank the objects based on overlap between users's past activities, i.e., items are recommended to a user based on the similar items this user has selected and other users with similar patterns of selected items. This strategy however will lead to a large potential risk as the recommended lists become more and more narrowing popular or over-specified. Users may become bored with the low amount of information of recommendation lists. Taking movie recommendation for example, a user that has rated the movie Godfather five stars may obtain a recommendation list containing all the other Godfather sequels. Though the user probably appreciates the Godfather sequels, usually this recommended set is not satisfying, since the user can hardly get expected information.

To increase information of recommendation results, most previous proposals consider defining diversity by semantic information (including the genre or directors of a movie, the authors of a book, etc.). An intuitive idea is formulating distance between a pair of items by their attributes and maximizing the sum of distance of a set. However, these semantic diversification has two main drawbacks. First, there may be lack of such semantic information. Second, it maybe unreliable to define diversity based on given semantic information. For example, movies of the same directors/actors are not necessarily similar. In this paper we construct a novel entropy regularizer to capture the notion of diversity for a recommended subset. Entropy regularizer is different from existing diversity-promoting techniques in that it is not based on traditional pairwise distance between elements in subset, but defined on the feature space of the overall subset.

The entropy regularizer has several good properties. First, the entropy regularizer is maximized when the set of itemfeature vectors are orthogonal, and is minimized when the vectors are linearly dependent, which intuitively captures diversity of a set of feature vectors. Second, the entropy regularizer satisfies non-decreasing monotonicity and submodularity, such that when combined with a modular rating function, we get a monotone submodular objective function. There exists efficient greedy approximation algorithm for monotone submodular function maximization, such that the recommendation set is theoretically guaranteed to be a constant-factor approximation of the optimal solution.

In this paper, we make the following contributions: (i) we formulate the diversity promoting recommendation task as a linear combination of the rating function and the entropy regularizer; (ii) we discuss the properties of the entropy regularizer, and provide theoretical proof; (iii) we construct greedy algorithm to maximize the objective set function subject to a cardinality constraint, and discuss the approximate rate; (iv) we conduct experiments on real dataset, and show that compared to state-of-the-art baselines, our approach significantly improves the performance of top-K prediction [6]. Our approach reaches a tradeoff between enhancing the the personalization of individual user intent and increasing the information of recommendation set.

2 RelatedWork

The importance of result diversification in recommendation systems has been recognized recently [8, 26]. There exist two main challenges to address the problem of diversity promoting recommendation. The first one is how to define diversity in objective function, and the other one is how to design effective and efficient algorithm to find the optimal solution.

The earlier work [27] proposed to define a similarity metric based on a taxonomy-based classification. The similarity is used to compute an intra-list similarity metric to determine the overall diversity of the recommended set. The authors provide a heuristic post-processing algorithm to increase the diversity of top-N recommendation list. As we discussed in the introduction, taxonomy information is not always available, even worse it is not always reliable to determine the similarity of two items. Several proposals [25, 24, 3] define diversity based on feature space of items. Typically, the diversity of a given set is defined as the sum of distance between items in the set. These proposals differ on the algorithms, which generally fall into two classes: greedy heuristics, where the recommendation list is constructed one-by-one by maximizing a given distance function at each step; refinement heuristics, where an initial relevant item set is first provided and then refined by a series of actions that forms the final recommendation set. While the objective functions of these proposals are set function, in that the objective seeks for a set which maximize the value of the objective set function, almost all heuristic algorithms can not guarantee a theoretical bound on the solution.

We argue that the separate consideration of definition of diversity and the design of algorithm is suboptimal, which is an obstacle to design a principled algorithm. In this paper, we construct diversity promoting regularizer using a carefully chosen entropy function based on feature space. The entropy regularizer, on one hand quantifies the expected value of information contained in the given set of items, which describes the notion of diversity in principle manner, on the other hand satisfies submodularity and monotonicity such that there exists a provable approximation algorithm with a bound that guarantees the found recommendation set is almost as good as the optimal solution.

Submodular fucntions have roots in economics, game theory, and computational optimization. Recently, submodular functions have started attracting attentions in many practical computer science fields, such as machine learning [20], data mining [12, 20] and natural language processing communities [14]. The most recent work is document summarization, where the authors studied a class of submodualar function to select sentences which meet the requirements of both representativeness and diversity. Different from previous work, we introduce entropy as the measurement of diversity. Our definition of diversity and our algorithm to find the best subset over all possible subsets can also be applied in other work such as topic diversification tasks in information retrieval.

3 Submodular Functions

In this section, we give some background on submodularity [7]. Submodularity can be viewed as a discrete analog to convexity [16] in continuous optimization. Like convexity functions, submodularity functions also arise in many applications, and lead to nice theory results and efficient optimization algorithms.

Suppose we are given a finite set of items V = {v1, . . . , vn}, the ground set 2V denotes the set of all subsets of V . A function f : 2V → R returns a real value for any subset S ⊆ V .

Definition 1. A set function f : 2V → R is submodular if, for any subset S, T ⊆ V ,

Meanwhile, for any subset S ⊆ T ⊆ V \v, the submodularity of a set function f : 2V → R is also equivalent to: f(S + v) - f(S) ≥ f(T + v) - f(T). There are mainly two types of Submodular functions: monotone and non-monotone. A submodular function is monotone, if for any subset S ⊆ T ⊆ V , f(S) ≤ f(T). In this paper, we will focus on the monotone submodular functions.

Definition 2. A set function f : 2V →R is called modular if for any sub set S, T ⊆ V ,

Modular set functions, which also satisfy submodularity according to definition 1, are a class of simple set functions. By induction, we can get f(S) = f(∅) + ∑v∈S f({v}). If we identify every subset of S with its incidence vector, modular functions will correspond to linear functions. In practice, modular set functions are less useful than the more general submodular ones, but in this paper, our rating function derived by probability matrix factorization is a modular set function.

4 Promoting Diversity in Recommendation

In this work, we consider the task of recommendation as choosing the best set of items for a user, coupled with the desire to choose as "diverse" items as possible. We formulate this task as a combinatorial optimization problem in the following.

Problem 1. Suppose there are M distinct items, for K > 0, find a set S ⊆ [M]1 such that

where R(S) measures the quality of recommendation set, g(S) is the diversity promoting regularizer and λ > 0 is the regularization constant.

In the rest of this section, we construct R(S) and g(S) in principled way. We will also show that both R(S) and g(S) are submodular and non-decreasing. These properties enable us to design an efficient approximation algorithm for the optimization problem Eq. 1.

1 [M] is shorthand for {1, . . . ,M}.

4.1 Probablistic matrix factorization

Our construction for R(S) and g(S) will use deep properties of probabilistic matrix factorization (PMF) model [22]. Therefore, in this part, we briefly review the assumptions and learning algorithms of PMF. Let rij denote the rating of user i for item j, and R = {rij} ∈ RN×M denote the rating matrix, where N is the number of users. PMF is a Bayesian method for modeling these ratings by deriving a low-rank approximation of the rating matrix:

where U ∈ RD×N is the user preference matrix and V ∈ RD×M denotes the item feature matrix. We can further write U = [u1, . . . , uN] and V = [v1, . . . , vM]. Now, for each i ∈ [N], vector ui ∈ RD represents the D-dimensional latent preference vector of user i, and for each j ∈ [M], vj ∈ RD denotes the D-dimensional latent feature vector of item j.

More specifically, PMF places Gaussian priors on U,V and E:

The rating rij of user i on item j is then modeled as:

Given a collection of observations Φ ⊆ [N] × [M], we can estimate U and V by maximizing the following joint likelihood using gradient descent algorithm:

where C is a constant that does not dependent on the parameters or hyper-parameters.

Predictive distribution of ratings

In real-world recommendation scenario, we often assume that the item feature matrix V is reliably estimated by learning a PMF model. But for each specific user, the point estimation of preference vector u is often not reliable, since there is no sufficient rating information for one user. Bayesian approach is a promising solution for this issue: we integrate out the user preference vector u to take into account the uncertainty of u. In other words, without estimating u, we can compute the conditional distribution of the ratings of a user, which is often termed as predictive distribution in Bayesian literature, based on the estimated item feature matrix V and the known ratings of the user.

Formally, for a given user, we denote the set of rated items of the user as Ω ⊆ [M] and the set of unrated items as ¯Ω. Without loss of generality, consider a set of unrated items S ⊆ ¯Ω, rS = {ri : i ∈ S} denotes the rating of items in S, we are interested in the predictive distribution Pr(rS|rΩ, V), where rΩ = {ri : i ∈ Ω} denotes the known ratings.

We start from deriving the posterior distribution of ratings r ∈ RM for a particular user. Given the item feature matrix V, we integrate out the user's preference vector u, and then we have

e

where the second line follows the self conjugacy property of Gaussian distribution, and Σ ≜ σ2uVT V is the covariance matrix of items. Then, by Eq. 4, the joint distribution of rS and rΩ is given by:

where ΣAB ∈ R|A|×|B| denotes sub-matrix of Σ that consists of rows and columns indexed by A and B respectively. The desired predictive distribution of rS is given by:

4.2 Rating function

We define rating function R(S) as the sum of offset expected rating of items in set S. Intuitively, R(S) encourages to select items with high expected rating. Formally,

e

where c ≤ minω∈ ¯Ω E[rω|rΩ,V], which is an offset constant that does not depend on S, can be computed in the preprocessing step. Here, the role of c is to ensure R({ω}) ≥ 0 for all ω ∈ ¯Ω, and therefore make R itself a monotone nondecreasing set function. In addition, note that R(S) exactly matches the deduction of definition 2, i.e. a modular set function can be rewritten as f(S) = f(∅) + ∑v∈S f({v}), when every subset of S is identified by its incidence vector. Hence, the rating function R(S) satisfies modularity. In this way, we have successfully constructed a rating function R(S) that is both modular and non-decreasing.

4.3 Entropy regularizer

There is no unique way to define diversity of an item set S. Intuitively, the diversity promoting function should be high if the items in S are very dissimilar with each other and vice versa. Since each item j is represented by its feature vector vj , it is natural to quantify such similarity based on these feature vectors. Principally, for a set of vectors, they are most dissimilar if these vectors are orthogonal, and are most similar when they are linear dependent. In addition, we seek to find the most informative unrated items, which implies the criterion measuring the posterior uncertainty of the ratings. Following this insight, we tap into the notion of entropy of a set of random rating variables.

e

e

As we have shown before, the posterior of rS is multivariate Gaussian distribution. The differential entropy of multivariate Gaussian random variables is a function of the determinant of the covariance matrix:

where ΣS is given by Eq. 5.

We call the set function

as entropy regularizer. From information theoretical viewpoint, our definition of the entropy regularizer g(S) quantifies the uncertainty of the set of ratings rS given observations of rated items rΩ. If the items in S are dissimilar from each other, and meanwhile these items are dissimilar from rated items Ω, the uncertainty about the ratings of rS should be high. From this perspective, our choice of g(S) matches the intuition of a diversity promoting regularizer.

We can establish similar intuitions of g(S) using a geometric interpretation. Recall that each item ω can be characterized by its item feature vector vω in PMF model. Naturally, two arbitrary items ω1, ω2 are most dissimilar if their feature vectors are orthogonal vTω1 vω2 = 0 and therefor implies a high diversity. In fact, we can show that g(S) is maximized if the item feature vectors of items in S are orthogonal to each other and the feature vectors of rated items. Formally, we have the following result.

Lemma 1. Without loss of generality, assume that spectral norm (maximum singular value) of VS is bounded by ‖VS‖ ≤ θ. Then, we have

where the equality holds when VTS VS = θ2 I and VTS VΩ = 0.

We have shown that g(S) is an appropriate notion of diversity. Next, we will show that g(S) is both submodular and non-decreasing based on mild assumptions.

Proofs of all results are given in the appendix.

Submodularity. We can show that the entropy regularizer g(S) is a submodular set function. By definition, it suffices to show that g(A ∪ {ω}) - g(A) ≥ g(B ∪ {ω}) - g(B) for all A ⊆ B ⊆ ¯Ω. Using the definition of g(S), this is equivalent to h(rω|rA, rΩ,V) ≥ h(rω|rB, rΩ,V). The last inequality is the well-known "information never hurts" bound [17]. Hence, we have the following result.

Lemma 2. The set function g(S) is submodular.

Monotonicity. In general, the differential entropy of set of random variables is not necessarily monotone. Fortunately, however, we can show g(S) is monotone for most parameter settings of PMF used in practical scenario. Formally, we have the following result.

Lemma 3. If σ2 e ≥ (2πe)-1 , the set function g(S) is monotone.

Recall that σ2 e is the prior belief of variance of noise on the ratings rij as defined in Eq. 3. The typical parameter setting of σe is σ2 e ← 1.0 and is much larger than the required threshold (2πe)-1 ≈ 0.0586 [22]. Therefore, g(S) is a monotone set function under the usual settings of σe.

5 Algorithm

The optimization problem of Eq. 1 is NP-hard [13]. In this section, we describe an efficient approximation algorithm with a provable guarantee by utilizing the submodular and non-decreasing properties of f(S) constructed in the previous section.

Our algorithm is greedy, in that it chooses items in sequence and selects the next item which provides the maximum increase in f(S). Formally, suppose we have already chosen a set of items S where |S| < K, our goal is to greedily select next item ω which maximizes:

Using the results of predictive distribution of rω in Eq. 5, Algorithm 1 shows our approximation algorithm for solving optimization problem Eq. 1.

Input: item feature matrix V; existing ratings rΩ. Output: item selection S.

Algorithm 1: Approximation algorithm for Eq. 1

Complexity analysis. The time complexity of Algorithm 1 is O(K(|Ω| +K)3 ), which is acceptable in real-world settings, since the number of rated items of a single user |Ω| is often very limited.

Approximation ratio. Combining the fact that g(S) is submodular and R(S) is modular, we have the objective function f(S) is also submodular by the closure property of submodularity. Nemhauser et al.[21] proved that for maximizing a nondecreasing submodular set function, the performance guarantee of greedy algorithm is (1-1/e)OP T , where OP T is the value of optimal solution of Eq. 1. Nemhauseretal's theorem can be stated formally as following.

Theorem 1. Under the assumption of Lemma 3, Algorithm 1 is guaranteed to find a set S of k items satisfying

where OPT = max|S∗ |≤K f(S∗ ) is the value of optimal solution.

6 Evaluation

In this section, we conduct several experiments to evaluate the quality of our diversity promoting recommendation.

6.1 Dataset

The MovieLens dataset consists of 1,000,209 ratings for 3900 movies by 6040 users of homonym online movie recommender service [19]. All users are selected randomly, and each of them has rated at least 20 movies. The element of the dataset is represented by a tuple: ti,j = (ui, vj, ri,j), where ui denotes userID, vj denotes movieID, and ri,j, which is an integer score between 1 and 5, denotes the rating of user i for movie j (higher score indicates higher preference).

6.2 Performance of top-K prediction

Following the work [25], we split the dataset into a training dataset and a test dataset. The training dataset was used to train the PMF model, such that we can get the item feature matrix. For each user profile Pu in test dataset, we further select 0.5|Pu| movies at random as profile test set Tu, where |Pu| denotes the size of the profile. Then the profile test set Tu, i.e. 50% of the user profile, is removed. The reminder of profile Pu is used to make a top-K prediction for user u.

Metrics

We use precision to measure the quality of our proposed approach. Suppose we recommend K sized set Su to user u, the precision is defined as:

where U denotes the set of all tested user.

Note that we do not aim to predict the ratings of movie, but to make a more satisfying top-K recommendation [11]. Hence, precision is more appropriate metric rather than the the Mean Absolute Error (MAE) metrics.

Baselines

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

1. PMF: Standard probabilistic matrix factorization without diversity promoting entropy regularizer. PMF is considered as the state-of-the-art recommendation technique. Specifically, we seek to find a set satisfying:

which is equal to maximizing the rating function defined in Eq. 6.

1. PMF+MMR: Maximal marginal relevance [5] is proposed to reduce redundancy while maintaining relevance

in the field of document summarization. More specifically, MMR sequentially chooses item using the following criteria

where rωi is the estimated rating of item ωi 2 , ˆ S is the subset of items already selected, λ is a parameter specifying the trade-off between rating score and diversity, and sim(·, ·) is similarity measure between two items. Without loss of generality, based on the result of PMF model, we specify sim(·, ·) as the cosine similarity between the item feature vectors. The MMR algorithm intuitively selects an item that maximizes the MMR objective function until a given cardinality constraint is met, i.e. | ˆ S| ≤ K. Note that though MMR is widely used in information retrieval and document summarization, this heuristic method is not theoretically justified.

Results

We consider predicting different amount of movies, i.e. we recommend top-5, 10, 15, 20, 25, 30 movies to each user. For the parameter setting, when training the PMF model, we set the size of the latent space D = 80/100/120. Both of the baselines and our approach take the same setting. In addition, λ = 0.15 and λMMR = 0.15. In the next section, we will discuss the impact of parameter λ. The experimental results are shown in Table 1, where our approach is denoted as "PMF+MMR". As is obvious from the table, "PMF" provides the worst performance, "PMF+MMR" performances better, and our approach significantly outperforms both of them. This results indicate that diversity promoting methods (MMR and ER) help predict user preference, since users may like dissimilar movies that standard PMF cannot cover. Furthermore, compared with popular diversity promoting algorithm MMR, our entropy regularizer is more effective for capturing the notion of diversity. Moreover, for individual case of top-K prediction, where K = 5/10/15/20/25/30, "PMF+ER" on average improves the precision by 1.77%/2.60%/3.47%/4.04%/4.97%/5.51% relative to "PMF". This results indicates that as K increases, the diversity promoting regularizer plays more important role in predicting user preference.

6.3 Impact of parameter λ

In our model, the parameter λ balances rating and diversity. If λ = 0, the model seeks to find the movies with the highest rating, and if λ = +∞, the model seeks to find the most diverse movies. Figure 1 shows the impacts of λ on precision. We also plots the precision by baseline PMF as a control. Clearly, in every case of top-K prediction (i.e. K ∈ {5, 10, 20, 30}), PMF+ER outperforms PMF significantly. More remarkable, as λ increases, while the performance of PMF stay constant, the prediction precision by PMF+ER increases at first, but when the value of λ surpass a certain threshold, the precision begins to decrease. This phenomenon demonstrates that there is a tradeoff between enhancing the the personalization of users and increasing the information of recommendation set. We also see that in most cases, when λ ≈ 0.15, PMF+ER can achieve the best performance. Except the cases K = 5 and K = 10, where smaller value of λ is better. This is reasonable, since when we recommend less movies, users usually prefer movies more relevant, but when the amount of recommended items increase, the requirement of diverse begin to emerge.

2 Standard MMR use a similarity measure between a query and a candidate item to capture the notion of relevance. There is no explicit query for recommendation task, such that we consider replacing it with the estimated rating of an item.

7 Conclusion

In this paper, we (i) propose an entropy regularizer to capture the notion of diversity in recommendation, (ii)show the objective set function combined by the rating set function and the entropy regularizer satisfies submodularity, (iii) discuss the constraint by which the entropy regularizer will meet monotonicity, (iv) provide an approximation algorithm with (1-1/ e) theoretical bound. Our empirical results indicate entropy regularizer performs better than popular diversity promoting algorithm MMR, and improves the precision and recall of top-N prediction recommendation task.

Acknowledgments

This work is supported by China 973 Project No.2012CB316301.

Appendix

Proof of Lemma 1. By the defintion of g(S), it suffices to show

At this point, it is easy to check the equality holds if VTS VS = I and VTS VΩ = 0 and therefore ΣSS = σ2u I and ΣSΩ = 0 in this case. Now we upper bound the determinant by its spectral norm. Denote E = ΣSS + σ2 e I - ΣSΩ(ΣΩΩ + σ2 e I)-1ΣΩS. We have det(E) ≤ λmax(E)|S| , where λ1(E) is the maximum eigenvalue of E. We can bound λ1(E) by following

where the last inequality holds by the assumption on the spectral norm of ‖VS‖ ≤ θ. Combining the facts, it follows immediately that

Proof of Lemma 3. By definition of g and the property of Gaussian distribution, we have

where we have denoted A = S ∪Ω. Since rω is conditionally Gaussian distributed, we have

where the inequality holds since Σωω - ΣωA(ΣAA + σ2 e I)-1ΣAω is the Schur complement of positivie definitive matrix

and is therefore nonnegative.

Hence g(S ∪ {ω}) - g(S) > 0 since σ2 e > (2πe)-1 by assumption.