## Sudden Death:

## A New Way to Compare Recommendation Diversification

Derek Bridge derek.bridge@insight-centre.org Insight Centre for Data Analytics University College Cork, Ireland

Mesut Kaya mesut.kaya@insight-centre.org Insight Centre for Data Analytics University College Cork, Ireland

Pablo Castells pablo.castells@uam.es Universidad Aut´ ononoma de Madrid Madrid, Spain

## ABSTRACT

This paper describes problems with the current way we compare the diversity of different recommendation lists in offline experiments. We illustrate the problems with a case study. We propose the Sudden Death score as a new and better way of making these comparisons.

## KEYWORDS

Diversity; offline evaluation

## 1 INTRODUCTION

Recommendations should not only be relevant; a set of recommendations should often also be diverse. A number of algorithms exist that diversify their topN recommendation lists; a number of metrics exist that measure diversity.

But when comparing algorithms, especially in offline evaluations, there are at least two problems.

The first problem is that the comparison may not be fair. A recommender that seeks to diversify may use an objective function that is the same as, or closely related to, the metric used to measure diversity. This metric will tend to favour this recommender.

The second problem is that we are usually not interested in diversity for its own sake, although this is what most of the diversity metrics measure. The recommendations in the topN must still be relevant to the user. Checking this in the results of offline experiments becomes more challenging because we now have a multiobjective evaluation.

In this short paper, we propose a new scoring method for comparing algorithms. It is not specific to diversity but it is inspired by the idea that diversification is supposed to make it more likely that the user finds an item that satisfies her.

In Section 2, we illustrate the problems that we have presented above. In Section 3, we give a definition of the Sudden Death score and we illustrate its use. In Section 4, we make concluding remarks.

## 2 A CASE STUDY

We illustrate the two problems by comparing four algorithms using three diversity metrics and three relevance metrics on a single

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).

REVEAL '19, Copenhagen, Denmark

© 2019 Copyright held by the owner/author(s). xxx-x-xxxx-xxxx-x/xx/xx...$15.00 DOI: xx.xxxx/xxxxxxx.xxxxxxx

dataset. Of course, if our goal were to find the 'best' algorithm, we would use more datasets. But our purpose is simply to motivate the need for a better way of comparing algorithms.

We use the MovieLens 1 Million dataset. 1

The algorithms we compare are MMR, xQuAD and SPAD. They greedily re-rank the recommendations made by a baseline recommender, for which we use Matrix Factorization (MF). In these algorithms, the baseline recommender produces a set of recommended items, RS , for user u . For each recommended item i in RS , it also produces a score, s ( u i , ) , that estimates the relevance of recommended item i to user u . Then, the greedy algorithm re-ranks RS by iteratively inserting into ordered result list RL the item i from RS that maximizes a function, f obj ( i , RL ) :

$$f _ { o b j } ( i, R L ) = ( 1 - \lambda ) s ( u, i ) + \lambda \text{div} ( i, R L ) \text{ \quad \ \ } ( 1 )$$

where div ( i , RL ) is the marginal gain in diversity after inserting item i into the list of already-selected items RL . In this objective function, the trade-off between relevance and diversity is controlled by a parameter λ (0 ≤ λ ≤ 1). MMR, xQuAD and SPAD differ in their definitions of diversity, div ( i , RL ) .

In MMR, div ( i , RL ) is the maximum of the distances between i and the items already selected [1]:

$$\text{div} ( i, R L ) = \max _ { j \in R L } \text{dist} ( i, j )$$

The distance between items i and j , dist ( i , j ) , is most often calculated from item features (such as movie genres or book categories).

xQuAD and SPAD are intent-aware diversification methods [7]. They try to achieve coverage of the user's different interests, as revealed by the user's profile. More specifically, a user u 's interests are formulated as a probability distribution p a u ( | ) over a set of aspects a ∈ A . Then, diversity is defined as follows:

$$\text{div} ( i, R L ) = \sum _ { a \in \mathcal { A } } [ p ( a | u ) p ( i | u, a ) \prod _ { j \in R L } ( 1 - p ( j | u, a ) ) ] \quad ( 3 )$$

where p i u ( | , a ) is the probability of choosing an item i from a set of candidate recommendations RS , produced by a conventional recommender algorithm, given an aspect a and user u .

In xQuAD, the aspects are given by item features [7]. In SPAD, aspects are subprofiles, which are mined from the items that the user likes [6].

In the results shown in the rest of this paper, the methodology we adopt for training, for testing and for the setting of hyperparameter values is the same as the one described in [6].

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00419v1-figure-d620aeb5-511e-4c37-9a10-95714dec4c1b.jpg)

Figure 1: Different diversity metrics for different values of N .

Figure 2: Different relevance metrics for different values of N .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00419v1-figure-66ba2c1e-9f31-420f-a9a3-ba102bba0ccc.jpg)

Figure 3: Precision vs. diversity for different values of λ . Dotted lines show the performance of the MF baseline.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00419v1-figure-a9b89ade-9e5d-4f43-b034-588083c14120.jpg)

## 2.1 Measuring diversity

Just as there are several ways of measuring diversity within the objective function of a greedy re-ranking algorithm, there are several ways of measuring the diversity of a list of recommendations, L , for evaluation purposes.

Intra-List Diversity (ILD) is a popular diversity metric; it computes the average pairwise distances of items in a recommendation set [8]:

1 https://grouplens.org/datasets/movielens/1m/

$$\i L D ( L ) = \frac { 2 } { | L | ( | L | - 1 ) } \sum _ { i \in L } \sum _ { j \in L, j \neq i } \text{dist} ( i, j ) \text{ \quad \ } ( 4 )$$

ILD may favour an algorithm like MMR [1], since ILD is close to what MMR optimizes. This is confirmed in Figure 1a.

α -nDCG is a newer diversity metric [3]. It measures coverage and relevance of aspects, A :

$$\alpha \text{-nDCG} ( L ) = \frac { 1 } { a \text{IDCG} } \sum _ { i \in L } \left [ \frac { 1 } { \log _ { 2 } ( \text{rank} ( i, L ) + 1 ) } \sum _ { a \in \mathcal { A } } \left [ \frac { 1 } { \log _ { 2 } ( \text{rank} ( i, L ) + 1 ) } \right ] \right ] \right ] \text{$(5)$} \right ] \text{$R$} \text{$evan$} \text{$how$} \\ \text{where} \, a \text{IDCG} is the highest possible value of $\alpha$-nDCG$ where the $pone$} \\ \text{recommendation set is made of ideally diversified relevant items, $w$} \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdot \, \cdots$$

 where aIDCG is the highest possible value of α -nDCG where the recommendation set is made of ideally diversified relevant items, L is the set of recommended items (of size N ), rank ( i , L ) is the position of i in L , and rel ( i | u a , ) is 1 if item i has aspect a and is relevant to user u but 0 otherwise. α is the parameter that controls the penalty for redundancy. We use α = 0 5, as in [7]. Most com-. monly, aspects are item features. To make this explicit,, we will write α -nDCG F . Clearly, this metric favours xQuAD; and this is confirmed in Figure 1b.

In [5], we modified α -nDCG to produce a variant that we will denote by α -nDCG S , which defines aspects in terms of subprofiles. This metric favours SPAD, as confirmed by Figure 1c.

The three plots in Figure 1 illustrate the first of the two problems that we presented in Section 1. Experiments that use just one diversity metric are not fair because each metric tends to favour certain recommenders. Researchers who want to make a fairer comparison end up using multiple measures and then trying, usually informally, to identify the algorithm that is most robust across those multiple measures. This is not easy to do, since there is unlikely to be a single outright winner. A sports analogy here might be that researchers try to see which recommenders perform best both when playing at home and when playing away! When a metric favours a recommender, this is like playing at home; when a metric favours other recommenders, this is like playing away. The difference is that, for soccer, for example, we have a simple and agreed way of combining the outcomes of home and away matches to obtain the points we award to each team. We have no equivalent way of combining the outcomes of different metrics.

## 2.2 Measuring the relevance-diversity trade-off

As we said before, we do not desire diversity in a topN for its own sake. We care about relevance too. Of course, there are many ways to measure the relevance of a set of recommendation. In Figure 2, we show three of them: the precision, the mean reciprocal rank (MRR) and 1-call. Precision and MRR are well-known; we have more to say about 1-call in Section 4.

This leads us to the second problem that we identified in Section 1. To identify the best algorithm requires researchers to look jointly at relevance graphs and diversity graphs. This can be made easier, perhaps, by combining them. In the plots shown in Figure 3, for example, we show the three different measures of diversity (vertical axis) against precision (horizontal axis). In the plots in Figure 3, we are fixing N = 10 and we are varying λ (Eq. 1).

Each subfigure in Figure 3 is divided into four by the dotted lines that plot the precision and diversity values of the MF baseline. When, for a given value of λ , a re-ranking algorithm improves both precision and diversity over the baseline, for example, it appears as a point in the top-right quadrant. In our case study, SPAD appears to be the best of the three algorithms on this dataset: for most values of λ it outperforms MF in both precision and diversity.

But even this is misleading! It assumes that precision and diversity are equally important. If this is not the case, then these simple plots cannot be used.

Researchers could define metrics that combine measures of relevance and diversity but this still leaves the problem of knowing how much weight this combined metric should give to each component.

With this case study, we have illustrated the problems faced by researchers who wish to compare the offline performances of recommenders that diversify their result sets. In the next section, we offer a new scoring method for comparing these algorithms.

## 3 SUDDEN DEATH SCORE

We introduce the Sudden Death score, a new way of comparing recommenders, whether they diversify or not: user by user, it rewards the algorithms that score hits earliest in the topN .

Let U be the set of users. Let rel u be test set items that are relevant to user u ∈ U ; for example, in MovieLens, rel u can be test set items that u has rated 4 or 5. Let Algs be the set of recommender algorithms to be compared. Let RL u a N , , be the ordered list of the topN recommendations that algorithm a ∈ Algs makes to user u ∈ U . For a given user u , an algorithm a scores a hit at position i if any of the first i members of RL u a N , , are in rel u : hit ( i , u a N , , ) is true iff RL u a N , , [ : i ] ∩ rel u is non-empty. For user u , SD ( u a , ) is 1 iff no other algorithm in Algs has an earlier hit.

$$\overset { \sim } { \sim } & \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \ \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \	 \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \quad \ \rightharpoonup \$$

(6)

SD ( a ) , the Sudden Death score of algorithm a is the average of SD ( u a , ) across all users; see also Algorithm 1.

The analogy with sudden death tie-breakers in sports such as badminton, fencing, golf, judo and volleyball should be clear: play stops in the tie-break period of the game as soon as one team is ahead.

There are similarities between the Sudden Death score, which is for offline evaluation, and the framework for online evaluation described in, e.g [4]. In their framework, users choose recommendations from either a single recommendation list that has been created by interleaving the results of multiple recommender systems or from multiple recommendation lists. No actual metrics are defined in [4] but one option is to reward a system if it places the item chosen by the user earlier in its recommendation list.

Figure 4 plots Sudden Death for different values for N for the samealgorithms we used in the previous section. In Figure 4, SPAD is the 'winner' across all value of N . Of course, we cannot generalize from this to other datasets. For example, although we do not show the details here, in comparison with the same algorithms (MMR, xQuAD and MF), when SD scores are compared on the LibraryThing dataset, SPAD is knocked into second place by xQuAD.

## Algorithm 1 Sudden Death

Input: U , Algs , N Output: SD ( a ) for each a ∈ Algs 1: for a ∈ Algs do SD ( a ) ← 0 2: for u ∈ U do 3: for a ∈ Algs do h a ← 0 4: i ← 1 5: while i &lt; N do 6: for a 7: if h a = 1 for any a ∈ Algs then 8: break 9: i ← i + 1 10: for a ∈ Algs do SD ( a ) ← SD ( a ) + h a

a ∈ Algs do h ← 1 if hit ( i , u a N , , ) = true

11: return SD ( a )/| U | for all a ∈ Algs

Figure 4: Sudden Death scores for different values of N

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00419v1-figure-81d0528b-52b0-4650-8c83-1e88ee173f8c.jpg)

## 4 CONCLUDING REMARKS

The Sudden Death score tries to capture the idea that diversification should make it more likely that the user finds an item that satisfies her. It recognizes that diversification is not simply about creating a topN with a mix, e.g., of genres; it is about promoting relevant items into the topN to make user satisfaction more likely.

One concern might be that it seems very similar to relevance measures such as precision and MRR, which also reward algorithms for hits and, in some cases, for earlier hits. But Figure 2 shows that they are different: although here SPAD is always the best, they rank MF, MMR and xQuAD differently depending on N .

In fact, the Sudden Death score is perhaps most similar to Chen et al. 's 1-call metric (Figure 2c), which counts how many users get at least one relevant item in the topN [2]. Although 1-call comes from Information Retrieval, Chen et al. also partly motivate 1-call by diversity principles: they see diversity as a means to avoid full absence of relevance, even if it means giving up some probability of achieving full relevance. The Sudden Death score can be seen as a more rank-sensitive version of principles similar to those that underlie 1-call. More specifically, the Sudden Death score and 1call metric show different outcomes in our case study: the Sudden Death discriminates better between SPAD and the its competitors, even though the system ranking is similar overall similar (as one would also expect given the connections between the principles behind the two).

But there is a more fundamental difference too. Precision, MRR and 1-call are performance estimates. We compute them to get an estimate of how well a model will perform on future unseen data. The Sudden Death score is not a performance estimate. Its purpose is only for comparing systems. Indeed, unlike precision, MRRand 1-call, the Sudden Death score will change depending on the algorithms we compare against. For example, xQuAD will have a particular Sudden Death score when it is compared to just SPAD but a different Sudden Death score if it is compared simultaneously to SPAD and MMR. It follows that the Sudden Death score does not replace precision, MRR or 1-call; it supplements them.

## ACKNOWLEDGMENTS

This paper emanates from research supported by a grant from Science Foundation Ireland (Grant Number SFI/12/RC/2289), which is co-funded under the European Regional Development Fund.

## REFERENCES

- [1] Jaime Carbonell and Jade Goldstein. 1998. The Use of MMR, Diversity-based Reranking for Reordering Documents and Producing Summaries. In 21st ACM SIGIR International Conference on Research and Development in Information Retrieval . ACM, 335-336.
- [2] Harr Chen and David R. Karger. 2006. Less is More: Probabilistic Models for Retrieving Fewer Relevant Documents. In 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval . 429-436.
- [3] Charles L A Clarke, Maheedhar Kolla, Gordon V Cormack, Olga Vechtomova, Azin Ashkan, Stefan B¨ttcher, and Ian MacKinnon. 2008. u Novelty and diversity in information retrieval evaluation. In 31st ACM SIGIR International Conference on Research and Development in Information Retrieval . 659-666.
- [4] Conor Hayes and P´ adraig Cunningham. 2002. An on-line evaluation framework for recommender systems . Technical Report. Trinity College Dublin, Department of Computer Science.
- [5] Mesut Kaya and Dereek Bridge. 2019. A Comparison of Calibrated and IntentAware Recommendations. In 13th ACM Conference on Recommender Systems .
- [6] Mesut Kaya and Derek Bridge. 2019. Subprofile-aware diversification of recommendations. User Modeling and User-Adapted Interaction (2019).
- [7] Sa´ ul Vargas Sandoval. 2015. Novelty and Diversity Evaluation and Enhancement in Recommender Systems . Ph.D. Dissertation. Universidad Aut´noma de Madrid. o
- [8] Cai-Nicolas Ziegler, Sean M McNee, Joseph A Konstan, and Georg Lausen. 2005. Improving recommendation lists through topic diversification. In 14th International Conference on World Wide Web . 22-32.
Derek Bridge Mesut Kaya Pablo Castells
Sudden Death: A New Way to Compare Recommendation Diversification
This paper describes problems with the current way we compare the diversity
of different recommendation lists in offline experiments. We illustrate the
problems with a case study. We propose the Sudden Death score as a new and
better way of making these comparisons.