Diversified Utility Maximization for Recommendations Azin Ashkan ∗ , Branislav Kveton ∗ , Shlomo Berkovsky ∗∗ , Zheng Wen ∗ ∗ Technicolor, United States {azin.ashkan,branislav.kveton,zheng.wen}@technicolor.com ∗∗ CSIRO, Australia shlomo.berkovsky@csiro.au ABSTRACT 2. DIVERSIFIED UTILITY MAXIMIZATION Consider the problem of recommending items to a group of users The main idea of our approach is to maximize utility weighted by subject to the diversity of their tastes. The goal is to recommend a diversity and cover each increase in diversity by the item with the list of items, such that the interests of each user are covered. We highest possible utility. The increase in diversity can be viewed as cast this problem as maximizing a diversified utility function of the the probability that a user chooses the item, in the sense that items group, the optimal solution of which can be found greedily. We that are similar to the previously recommended items are less likely conduct a user study in order to evaluate the performance of the to be chosen. When the item is chosen, we would like to maximize proposed method. Evaluation results show that our method repre- the satisfaction of the user, i.e., the utility of the choice. Formally, sents an effective strategy compared to various settings in which a our optimization problem is given by: convex combination of utility and diversity is maximized. L X A∗ = arg max gA (ak )w(ak ), (2) A k=1 1. INTRODUCTION It is often the case that multiple users share a single account with where A = (a1 , . . . , aL ) is an ordered set of L items that we also an online recommender, e.g., family members may share the same call a list, and gA ∈ (R+ )L is a vector of gains in diversity, where: account with a movie recommendation service on their TV. The use gA (ak ) = f (Ak ) − f (Ak−1 ) (3) of a single account by multiple users poses a challenge in providing recommendations satisfying the spectrum of their tastes. One so- is the gain associated with choosing item ak after choosing items lution to this problem is to recommend a list of diverse movies, in in Ak−1 . The sets Ak and Ak−1 are the first k and k − 1 items in order to cover a range of tastes and increase user satisfaction. How- list A, respectively. We refer to our approach as diversified utility ever, there exists a tradeoff between increasing the list diversity and maximization (DUM), since our objective is to maximize the utility maintaining the utility of the results [4]. weighted by the increases in diversity. Let E be the ground set of L recommendable items and w(e) For a general function f , the problem in Equation 2 is NP-hard. be the utility of item e ∈ E. The goal is to recommend a subset However, when f is submodular, the problem can be solved opti- of items S ⊆ E with the highest utility and diversity for users. A mally by a greedy algorithm [2]. The items are ordered in decreas- common approach to diversified ranking is based on the notion of ing order of utility, A∗ = (a∗1 , . . . , a∗L ), where w(a∗1 ) ≥ . . . ≥ maximal marginal relevance (MMR) [1]. In this approach, utility and w(a∗L ), and they are added to the recommended list in this order. diversity are represented by two independent metrics, and marginal When gA∗ (a∗k ) > 0, item a∗k is added to the list. Otherwise, the relevance is a convex combination of these metrics: item is not added because it does not contribute to the diversity of the list. SMMR = arg max (1 − λ)w(S) + λf (S), (1) The above solution is meaningful when the length of the recom- S⊆E:|S|=K mended list, i.e., the number of non-zero entries in gA∗ , can be controlled. This is possible for a range of submodular functions. where K is the cardinality of S, λ ∈ [0, 1] is a parameter that bal- One such function is: ances the importance of utility and diversity, and w(S) is the sum ( ) of utilities of all items in S. The utility w is a modular function X X of S, whereas the diversity f is typically a submodular function of f (S) = min 1{item e covers topic t} , Nt . (4) t∈T e∈S S. Under these assumptions, the objective in Equation 1 is sub- modular in S. Therefore, a (1 − 1/e)-approximation to the optimal Here, T is a set of topics and Nt is an integer threshold for a topic solution can be computed greedily [3]. t. ForPthis f , the recommendation list is guaranteed to contain at In this paper, we consider a different objective function, the op- most t∈T Nt items, such that each topic t is covered by at least timal solution of which can be found greedily. Our objective is to Nt most relevant items in this topic. maximize the utility of recommending a list of items to a group of users subject to the diversity of their tastes. Items with high utility are expected to be included in the list as long as they have a con- 3. USER STUDY tribution to the diversity of the list. The utility remains the primary We conduct a user study in the movie recommendation domain. concern, but it is subjected to maintaining the diversity. The ground set E are 1, 000 most popular movies on IMDb1 . The utility w(e) of a movie e is approximated by its overall popularity, i.e., the number of people who rated e. Copyright is held by the author/owner(s). RecSys 2014 Poster 1 Proceedings, October 6–10, 2014, Foster City, Silicon Valley, USA. http://www.imdb.com – The Internet Movie Database. Table 1: An example scenario where DUM outperforms MMR. DUM MMR (λ = 2/3) MMR (λ = 1/3) MMR (λ = 0.01) The Dark Knight action Zombieland horror action The Dark Knight action The Dark Knight action LOTR 1 action From Dusk Till Dawn horror action LOTR 1 action LOTR 1 action The Matrix action Dawn of the Dead horror action The Matrix action The Matrix action Inception action Resident Evil horror action Inception action Inception action The Shining horror The Dark Knight action LOTR 2 action LOTR 2 action Alien horror LOTR 1 action The Dark Knight Rises action The Dark Knight Rises action Psycho horror The Matrix action LOTR 3 action LOTR 3 action Shaun of the Dead horror Inception action The Shining horror Avatar action 100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0% DUM λ=2/3 λ=1/3 λ=0.01 Bob and Alice Bob or Alice Neither Figure 2: The percentage of times for each method when the recommendation results were suitable for: both Bob and Alice, only Bob or only Alice, and neither Bob nor Alice. example, for action and horror movies, is shown in Table 1. MMR cannot solve this problem well for the following reasons. When Figure 1: An example questionnaire from the user study. We λ is large, MMR first chooses most diverse movies that are both ac- show only two lists out of four. tion and horror movies. These movies are less popular than horror movies that are not action. As a result, the list is only considered as Our study consists of a set of tasks. In each task, we ask a Me- a good representation of action movies, but not of horror movies. chanical Turk2 worker to consider a situation, where Bob and Alice On the other hand, when λ is small, MMR tends to choose mostly ac- go for a vacation and can take several movies with them. Bob and tion movies, because these movies happen to be more popular than Alice prefer two different movie genres. The workers are asked to horror movies. So the list is again a good representation of action rate four lists of movies, based on how these movies are appropriate movies only. for Bob and Alice. An example questionnaire is shown in Figure 1. One list is generated  by DUM. The other three lists are generated by MMR, with λ ∈ 23 , 13 , 0.01 . The length of all four lists is 4. CONCLUSION identical, and they are shown in random order to avoid position We propose a method to maximize the utility of recommended bias. Each task has different movie genres t1 and t2 preferred by items subject to the diversity of users’ tastes. This method guaran- Bob and Alice. We generate one task for each pair of 18 most tees that movies in the recommendation list cover various aspects of popular genres on IMDb and assign each task to three workers. user tastes with high utility items. We conduct a user study showing Thus, we obtain 3 × 153 = 459 ratings for each of the four lists. the effectiveness of our method compared to models that maximize In each task, the diversity function f is defined as in Equation 4. a convex combination of utility and diversity. In the future, we plan The topics are T = {t1 , t2 } and Nt1 = Nt2 = 4. For this set- to apply DUM to other domains, such as document summarization ting, DUM recommends between four to eight movies such that each and Web search result diversification. We also plan to extend our genre is covered by at least four movies. The functions w and f are study to groups of more than two users and evaluate the perfor- normalized such that the maximum gain in each function is 1. mance of DUM for various combinations of genres. On average, workers spent 57.39 seconds on each task, i.e., 14.35 seconds for a list of at most 8 movies, which is reasonable to judge 5. REFERENCES whether the list covers two genres. The results of the study are [1] J. Carbonell and J. Goldstein. The use of MMR, diversity reported in Figure 2. The workers considered the lists generated based reranking for reordering documents and producing by DUM to be suitable for both Bob and Alice in 74.5% of cases. summaries. In SIGIR, pp. 335–336, 1998. This ratio is significantly higher than those of MMR with λ = 32 and [2] J. Edmonds. Submodular functions, matroids, and certain λ = 13 . The absolute improvement with respect to the best baseline, polyhedra. In Combinatorial Optimization, pp. 11–26, 2001. MMR with λ = 23 , is 9.6%, while the relative improvement is 14.8%. [3] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis It is worth to note that in 70 combinations of t1 and t2 (45.8% of of approximations for maximizing submodular set functions - cases), all three workers unanimously rated DUM as appropriate for I. Mathematical Programming, 14(1):265–294, 1978. both Bob and Alice. [4] T. Zhou, Z. Kuscsik, J. Liu, M. Medo, J. R. Wakeling, and Y. Since DUM did not dominate the MMR baselines across the board, Zhang. Solving the apparent diversity-accuracy dilemma of it is important to identify cases, where it performs well. One such recommender systems. National Academy of Sciences, 2 107(10):4511–4515, 2010. http://www.mturk.com – Amazon Mechanical Turk.