By: Aboli Rawanhate, RIG Inc Intern Researcher

 

After watching a movie on Netflix, do you ever use the suggestions Netflix recommends for you to watch next? Likewise, if we buy a phone on Amazon, an offer may appear: “other people also bought”, screen guards; Would you like to do the same?” Have you ever wondered where these suggestions come from?

Algorithms used for recommending appropriate items to users are known as recommender systems for e.g. books to read on Kindle, ‘People you may know’ on LinkedIn, movies you should watch on Netflix, ‘Similar products’ or ‘People also bought this’ section on Amazon and many more.

In certain businesses, recommender systems are crucial as they may produce a large amount of revenue or serve as a method to differentiate themselves from rivals. The Recommendation System (RS) generates a top k list of recommended items for users based on the product or user similarity. It works by explicitly or implicitly gathering user-system interaction data and developing a preference model for the user. The question then becomes, won’t the user get bored watching the same recommendations every time he or she visits the webpage? To avoid this, we have introduced a concept known as dithering into the recommendations.

 

Why dithering?

When we search for something in a search engine, do we typically visit all the recommended pages? The answer is no. It has been observed that very few people will click on the next page or even scroll to the bottom of the screen to see more results.

Fig.1. Click-through rate vs. result position in ranking list

The click-through rate vs. result position in the ranking list for all recommendation results is shown in the graph above. If the first page displays 1 to 10 results from the recommendation list, and the top 100 recommendations are distributed as 10 per page in order of rating, most people will only look at the first 10 results. Only a small percentage of people will go to the second page, depicted in the figure between ranks 20 and 30. The following pages would be viewed by even fewer users, resulting in very low rates from rank 20 to 150. To avoid this, the recommendation system employs a dithering process.[1]

What is Dithering?

Dithering is a type of noise that is used to prevent large-scale patterns. This technique is used in recommendation systems to shuffle results from the recommendation list in order to present them with a new set of suggestions for each user visit. As a result, some of the items that are further down the list are brought to the front page for “freshness”.

Dithering is a technique for altering a recommendation list by introducing noise to the original ranking list. The main idea behind dithering is that if the recommender algorithm’s initial ranking list isn’t ideal, we can improve it by keeping more choices from the initial result and then use them for dithering.[1][2]

How does dithering function?

  1. To develop a preference model for the user, the recommender engine pulls data from the user’s profile or history of operations.
  2. The ranking score of those items that fit the user’s choice is calculated using a practical recommender algorithm (e.g., content-based recommendation).
  3. Random noise is added to the score.
  4. Top-n higher scoring items are saved to temporary storage, and the top-k are displayed to the user in the form of a recommendation list.
  5. The user replies with a domain-defined operation (e.g. clicking) at each step, then the ranking list is slightly altered once the user returns to the original page (e.g., refresh of web page): for instance, purposely including items on a list that have never been recommended before or reorganizing items farther down the list.

 

The system model of dithering:

The only difference between the traditional recommendation system and the dithering recommendation system is the presence of a dithering mechanism. See the system model diagram below.

Fig. 2. System model of dithering

1. Data Library:

There are three types of data libraries:

  1. User behavior(s) library: Records the interactions between user and the system such as purchasing history. It reflects the dynamic preference of users on the items.
  2. User attributes library: Stores users long-term interests
  3. Item attributes library: Stores the features of all items in the system. It can be used for matching the preference of the user. For example, storage and RAM can be phone features, so a user looking for 128Gb storage in phones should only include phones with 128Gb storage features.[1]

The data in the data library can be both structured and unstructured; however, unstructured data must normally be preprocessed before being used.

 

2. Recommender Engine:

When the data is ready, the recommender engine analyzes it and generates predictions about system users’ preferences. The recommender engine’s essential components are preference models and recommender algorithms. The vector space model is an example of a preference model; it represents a user’s choice through a list of keywords.

There are two types of recommender algorithms:

  1. A content-based recommendation algorithm computes the similarity between items and recommends the most similar items to the user.
  2. A collaborative filtering algorithm computes the similarity between users and recommends the items.[1]

 

3. Dithering Mechanism:

Three modules are included in the dithering mechanism, ranking list, temporary storage and dithering methods.

  1. Ranking list : The initial recommendation list generated by the recommender algorithm, which selects the top-n related items.
  2. Temporary storage: The temporary middle output results must be saved for subsequent dithering.
  3. Dithering methods: There are two types:
    1. Explicit dithering – For instance, the system’s content-based filtering algorithm proposes 10 relevant items to users. 10 more items will be saved as an extra list for the purpose of dithering. After that, dithering is applied by combining the two lists with some “noise”.
    2. Implicit Dithering: The system will compute the top-k most similar users to target users based on the users history and its interaction with the system. The items that these individuals prefer are then combined to create the final recommendation list.[1]

 

4. User Feedback:

The user’s activities on the recommendation list are logged as feedback for both the dithering mechanism and the recommender algorithm to improve upon.

  1. Explicit Feedback is feedback that reveals a user’s attitude regarding a service, examples include ratings and comments.
  2. Implicit Feedback is the recording of a user’s engagement with a service such as clicks and scrolls.[1]

 

How does it work?

There are two types of dithering:

1.   Relevance-based Dithering:

In relevance-based dithering, the algorithm takes the result list and generates a score that is the log of each result’s initial rank plus normally distributed random noise, then sorts the results by that score.


This method keeps the same items in the recommendation list but reorders them so that new items appear at the top of the list.[1][2]Where, ditherScore is the final score after dithering, Rank is the original ranking list, and β is the parameter which controls the size of dithering.

The implementation of relevance-based dithering in Python using sample data is shown below in Figure 3.

Fig.3. Implementation of relevance-based dithering in python

2. Collaborative Dithering: As with relevance-based dithering, collaborative dithering just reorders the initial fetched recommendation list but keeps the same elements, thus if the original recommendation does not pique the user’s attention, collaborative dithering is used to make sure that it does. The idea is to introduce an extra list for dithering so that the top-k list can be changed. It calculates the cosine similarity between all users and the target user, it then generates a recommendation list based on the top-n items that the top-k most similar users visit.[1]

 

Conclusion:

Dithering re-orders a list of suggestions by introducing random noise to the previous relevance-based ranking. The dithering model boosts the effectiveness of recommender systems. Relevance-based dithering provides an enhanced version to address the issue of a flawed recommendation list. The approach here is to add a different list to the recommendations to improve it. Furthermore, collaborative dithering deals with the case where the other list isn’t doing well, reorganizing the extra list and influencing the final recommendation list.

Dithering assists businesses to improve the engagement metrics like click-through rate and purchase rate of our recommendation engines. Dithering adds variety to a recommended list, ensuring that the user does not see the same top k recommendations each time. It detracts a bit from the quality of the recommendations, but the option to see items farther down the list more frequently makes it worthwhile and engaging.

References:

  1. https://doi.ieeecomputersociety.org/10.1109/ISPAN-FCST-ISCC.2017.61
  2. https://buildingrecommenders.wordpress.com/2015/11/11/dithering/#:~:text=The%20i dea%20behind%20dithering%20is,pages)%20to%20the%20first%20page.