Consider the problem of recommending items to a group of users subject to the diversity of their tastes. The goal is to recommend a list of items, such that the interests of each user are covered. We cast this problem as maximizing a diversified utility function of the group, the optimal solution of which can be found greedily. We conduct a user study in order to evaluate the performance of the proposed method. Evaluation results show that our method represents an effective strategy compared to various settings in which a convex combination of utility and diversity is maximized.
It is often the case that multiple users share a single account with
an online recommender, e.g., family members may share the same
account with a movie recommendation service on their TV. The use
of a single account by multiple users poses a challenge in providing
recommendations satisfying the spectrum of their tastes. One
solution to this problem is to recommend a list of diverse movies, in
order to cover a range of tastes and increase user satisfaction.
However, there exists a tradeoff between increasing the list diversity and
maintaining the utility of the results [
Let E be the ground set of L recommendable items and w(e)
be the utility of item e 2 E. The goal is to recommend a subset
of items S E with the highest utility and diversity for users. A
common approach to diversified ranking is based on the notion of
maximal marginal relevance (MMR) [
SMMR = arg max (1
S E:jSj=K
)w(S) +
f (S);
(1)
where K is the cardinality of S, 2 [0; 1] is a parameter that
balances 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
of S, whereas the diversity f is typically a submodular function of
S. Under these assumptions, the objective in Equation 1 is
submodular in S. Therefore, a (1 1=e)-approximation to the optimal
solution can be computed greedily [
In this paper, we consider a different objective function, the optimal solution of which can be found greedily. Our objective is to 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 contribution to the diversity of the list. The utility remains the primary concern, but it is subjected to maintaining the diversity. 2.
DIVERSIFIED UTILITY MAXIMIZATION The main idea of our approach is to maximize utility weighted by diversity and cover each increase in diversity by the item with the highest possible utility. The increase in diversity can be viewed as the probability that a user chooses the item, in the sense that items that are similar to the previously recommended items are less likely to be chosen. When the item is chosen, we would like to maximize the satisfaction of the user, i.e., the utility of the choice. Formally, our optimization problem is given by: (2) (3) A
L = arg max X gA(ak)w(ak);
A
k=1 where A = (a1; : : : ; aL) is an ordered set of L items that we also call a list, and gA 2 (R+)L is a vector of gains in diversity, where: gA(ak) = f (Ak) f (Ak 1) is the gain associated with choosing item ak after choosing items in Ak 1. The sets Ak and Ak 1 are the first k and k 1 items in list A, respectively. We refer to our approach as diversified utility maximization (DUM), since our objective is to maximize the utility weighted by the increases in diversity.
For a general function f , the problem in Equation 2 is NP-hard.
However, when f is submodular, the problem can be solved
optimally by a greedy algorithm [
The above solution is meaningful when the length of the recommended list, i.e., the number of non-zero entries in gA , can be controlled. This is possible for a range of submodular functions. One such function is: f (S) = X min ( ) X 1fitem e covers topic tg ; Nt : (4) t2T
e2S Here, T is a set of topics and Nt is an integer threshold for a topic t. For this f , the recommendation list is guaranteed to contain at most P Nt items, such that each topic t is covered by at least Nt mostt2reTlevant items in this topic. 3.
We conduct a user study in the movie recommendation domain. 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.
DUM The Dark Knight LOTR 1 The Matrix Inception The Shining Alien Psycho Shaun of the Dead action action action action horror horror horror horror action action action action action action action horror action action action action action action action action
Our study consists of a set of tasks. In each task, we ask a Mechanical Turk2 worker to consider a situation, where Bob and Alice go for a vacation and can take several movies with them. Bob and Alice prefer two different movie genres. The workers are asked to rate four lists of movies, based on how these movies are appropriate 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 2 32 ; 31 ; 0:01 . The length of all four lists is identical, and they are shown in random order to avoid position bias. Each task has different movie genres t1 and t2 preferred by Bob and Alice. We generate one task for each pair of 18 most popular genres on IMDb and assign each task to three workers. Thus, we obtain 3 153 = 459 ratings for each of the four lists.
In each task, the diversity function f is defined as in Equation 4. The topics are T = ft1; t2g and Nt1 = Nt2 = 4. For this setting, DUM recommends between four to eight movies such that each genre is covered by at least four movies. The functions w and f are normalized such that the maximum gain in each function is 1.
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 whether the list covers two genres. The results of the study are reported in Figure 2. The workers considered the lists generated by DUM to be suitable for both Bob and Alice in 74.5% of cases. This ratio is significantly higher than those of MMR with = 23 and = 31 . The absolute improvement with respect to the best baseline, MMR with = 23 , is 9.6%, while the relative improvement is 14.8%. It is worth to note that in 70 combinations of t1 and t2 (45.8% of cases), all three workers unanimously rated DUM as appropriate for both Bob and Alice.
Since DUM did not dominate the MMR baselines across the board, it is important to identify cases, where it performs well. One such 2http://www.mturk.com – Amazon Mechanical Turk. 100% 90% 80% 70% 60% 50% 40% 30% 20% 10% 0%
λ=2/3 Bob and Alice
λ=1/3 Bob or Alice example, for action and horror movies, is shown in Table 1. MMR cannot solve this problem well for the following reasons. When is large, MMR first chooses most diverse movies that are both action and horror movies. These movies are less popular than horror movies that are not action. As a result, the list is only considered as a good representation of action movies, but not of horror movies. On the other hand, when is small, MMR tends to choose mostly action movies, because these movies happen to be more popular than horror movies. So the list is again a good representation of action movies only. 4.
We propose a method to maximize the utility of recommended items subject to the diversity of users’ tastes. This method guarantees that movies in the recommendation list cover various aspects of user tastes with high utility items. We conduct a user study showing the effectiveness of our method compared to models that maximize a convex combination of utility and diversity. In the future, we plan to apply DUM to other domains, such as document summarization and Web search result diversification. We also plan to extend our study to groups of more than two users and evaluate the performance of DUM for various combinations of genres.