Diversity of recommendations

personalized recommendations #6

In the previous post we looked at how to start with the outcomes desired by product and work out objectives and corresponding metrics for the recommendation system from those. We also briefly alluded to metrics that promote the diversity of the results returned by the recommender system. In this post we will:

1. Discuss why diversity of results is important.

2. Explain a machine learning method of boosting diversity in recommendations.

3. Walk through an example of this method.

Fig 1: Example of diversity

Let’s explain diversity through a simple example in the image above. The recommendations on the right appear more diversified compared to the ones on left. List on right captures my three major interests: I watch basketball highlights, my kids watch Peppa Pig videos and (sometimes!) I watch ML lectures.

Why diversity? “the only free lunch”

Boosting the diversity of the actions has been a time tested approach to improving performance. In this article we are talking about diversity of results and the results shown are the actions the “recsys” can take to satisfy the user without knowing with certainty what the user was looking for.

Diversification of actions has been useful in other fields as well. In portfolio management, Nobel prize winner Harry Markowitz called diversification “the only free lunch in finance”. In autonomous driving, the IntentNet paper introduced a paradigm for predicting the behavior of agents while diversifying over the set of intents they could have and not just predicting the most likely path.

What is common to these approaches is that the prediction system is subject to variation in what the user, the environment or other actors might want to do.

While our prediction system tries to do a good job of modeling the intents of the unobserved environment, it needs to be humble and accept the possibility of mistakes / uncertainty in its prediction of the environment.

Diversity of a slate versus diversity across multiple visits of the user

Before we talk about how to implement diversity, we should recognize that there are two ways of adding diversity to recommendations.

1. Diversity of a single set of results
   For each visit of the user the recommendations shown could cover a number of interests that the user might had.

   

   Fig 2 : Diversity within a slate

   For instance, in the image above on the left the results are shown in a decreasing order of likelihood of the user clicking on them. The ranked list on the right chooses to show items from a different category than the ones already shown.

2. Diversity across multiple visits of the same user
   Imagine you have a user coming to your page fairly regularly, say at least once a day. You have some idea from past behavior of their interests but their interests are not narrow. In such a scenario you might want to add an element of exploration in each visit. You could add this exploration / noise in the ranking at an item level or also at a genre / category level (See image below).
   

   

   Fig 3: Diversity across visits of the same user

   If you are wondering why this might be better than Diversity in a slate, I encourage you to not try to compare them. These are just different ways to look at the problem and could be additive to your problem. One advantage of the second option is that it would reduce the cognitive load of the user. Instead of each result being very different the user can quickly browse and skip a topic if that is not what they are looking for.
   An overlapping concept with this form of diversity is impression demotion, a topic which we will cover in greater detail in future.

In this article though we are only concerning ourselves with diversity of a slate of recommendations.

System design of diversity boosting

In terms of system design, diversity boosting can be added at various stages:

Fig 4: System design for diversity boosting (multiple candidate generators, diversity boosted reranking)

1. Having multiple candidate generators. For instance, having a candidate generator that skews towards popular content and one that skews towards personal results ensures that we have a good set of results to diversify the slate.

2. After we have computed a ranking score for each result, we will rank items in a way that boosts for diversity (look at the second last step in the flow chart above)

In the rest of the article we will focus on a way to implement diversity boosted ranking.

Diversity boosted ranking using Maximal Marginal Relevance

The idea in this method, Maximal Marginal Relevance (MMR) is to iteratively select a recommendation from the yet unselected set of recommendations based on what maximizes adjusted relevance, i.e. relevance to the user - k * similarity to previously selected results.

1. For each item, set relevance(item) = Score from ranking model for that item.

2. For first K = 10 steps:
   Select the item with the highest (1-ß)*relevance - ß * Similarity(item, previously selected set)

3. Sort the remaining items in descending order of (1-ß)*relevance - ß * Similarity(item, previously selected set) and add them in this order to the final ranked list.

Example

Suppose we are using Maximal Marginal Relevance based ranking to rank items A1, A2, B1, B2, C where A1 is very similar to A2, like say A1 and A2 are NBA highlights videos, B1 and B2 are say very similar Peppa Pig videos and C is on a different topic.

The initial ranking scores are: {[A1, 1], [A2, 0.8], [B1, 0.6], [B2, 0.4], [C, 0.2]}.

If we rank purely based on score then the order would be: {A1, A2, B1, B2, C}.

However, using MMR the order is {A1, B1, C, A2, B2}. Let’s see how.

Fig 5: Showing how MMR woks. The first result chosen is the one with the highest ranking score (a.k.a. relevance)

As shown in the image above, the first item selected is A1.

Fig 6: Showing that MM based ranking diverges from simple ranking after the first item has been selected. In this case normal ranking would have chosen A2 since it has the second highest relevance. However, MMR chooses B1 in the second position.

After selecting A1 the similarity penalty of A2 becomes 1. Hence the Marginal Relevance of A2 is no longer the highest after A1. A1’s marginal relevance = (0.5 * 0.8) - (0.5 * 1) = -0.1

B1 is now the item with the highest Marginal Relevance. Hence the second item selected is B1.

Fig 7: Showing that MMR chooses C after A1 and B1 have been selected since it maximizes marginal relevance and not purely relevance.

Similarly after A1 and B1 are selected both A2 and B2 have a similarity penalty of 1. Now C is the item with the highest marginal relevance.

Continuing along this line, we will see that A2 and B2 will be selected. The final order is thus A1, B1, C, A2, B2.

Key takeaways

1. Diversity boosting is very likely to improve search / recommendation quality, especially when the user could have multiple intents or interests. (Increased CTR by 73% in an industrial recsys I am personally experienced with.)

2. There are advantages of adding diversity boosting in both retrieval and ranking.

3. To implement diversity boosted ranking, Maximal Marginal Relevance is an easy and very successful approach. This approach powers some of the most successful recommender systems today.

In a future post, we will cover other ways of implementing diversity boosted ranking.

Disclaimer: These are my personal opinions only. Any assumptions, opinions stated here are mine and not representative of my current or any prior employer(s).