Hi, My name is Farzad Eskandanian and I am presenting the work that I’ve done in collaboration
with my advisor Dr. Bamshad Mobasher at DePaul university.
This work is about generating recommendations that are both accurate and diverse, and it
relies on stable matching to achieve that goal.
First, I’ll give you a quick background about the problem and the reasons why we need
to consider diversity into recommendations.
In past few years, we’ve seen a lot of works in the domain of recommender systems that
their goal is to improve accuracy of recommendations.
The training data used in these works is mostly from users interacting with items in online
systems for example by rating them.
But, most of the times in the process of gathering this data, the items are not selected at random,
meaning users are mostly rate items that are popular and popular items are not that many,
compared to the total number of items, as you can see in the figure.
This results in small portion of items receiving more than 90% of the feedbacks.
Measuring accuracy using the biased data favors the popular items. And since, we have a long
list of items that are not popular, this results in recommending only small portion of all
the items in the catalog. This is also known as the problem of fairness
of exposure where popular items have more chance of appearing in the recommendation
lists.
If we only recommend popular items, the measure of accuracy does not show any problems. And
still we see high accuracy, even though there is no diversity in recommendations.
So, that’s why we need to consider metrics beyond accuracy for evaluation that are based
on the concepts like diversity or novelty.
But also note that both relevance of items to the users' interest and diversity of items
in the recommendation lists are equally important. So we need to measure both accuracy and diversity
of recommendations.
The challenge is that these two objectives are incompatible with each other and increasing
diversity will result in loss in accuracy.
So, the main research question is how to deal with the trade-off between accuracy and diversity?
The notion of diversity that we are interested in, is called aggregate diversity. If you
look at the items in all of the recommendation lists for all the users, aggregate diversity
is about how uniformly the items are distributed to users.
So, we have two objectives that we have clearly defined: first is accuracy and the second
one is aggregate diversity.
Many existing algorithms have been developed to increase accuracy. So we can use the recommendations
from those methods for the first objective and re-rank those recommendations in order
to increase diversity.
In other words, we need to develop re-ranking algorithms with the objective of maximizing
diversity with minimum loss in accuracy.
This is challenging because: First, we mentioned that the training data
is mostly concentrated on popular items. and Secondly, for those niche items with few
feedback data, it is very hard to separate noise from information.
That’s why increasing diversity is likely to reduce accuracy.
To solve this problem we’ve transformed the recommendation problem into a bipartite
graph with users on one side an items on the other side and edges in this graph represent
recommendations.
To include the two objectives that we mentioned, we consider two utilities for each part of
the graph.
User-side utility is the same as personalization or accuracy.
And for the item-side, the utility of an item is defined as being exposed or recommended
to a specific set of users that the item should be delivered. This notion is similar to the
targeted advertising.
This indicates the preference of items in term of which users they prefer their product
to be exposed to by recommendations.
Note that maximizing the average utility of item-side increases diversity.
So, then the goal is to find a bipartite graph or matching that maximizes utilities of both
users and items.
We define utilities based on ranking preferences. So, for user-side utility, each user expresses
her preference in terms of a rank list of items.
And for item-side, utilities are defined as ranking of users.
In other words, everyone has a rank list of the other side for themselves.
Besides, the ranking preferences we need to specify some constraints, because we do not
want to recommend everything to everyone. There is a limitation to the number of items
that is normal to recommend and Also, we want to limit the exposure of each item so that
we do not recommend an item more than a certain number of times.
Utilities and constraints, together, define our main objective which is finding a matching
that maximizes user and item utilities subject to their constraints.
So, the matching assigns items to user’s recommendation lists and the challenge is
to distribute these items such that when we limit the number times each item can be recommended
the loss in accuracy is minimum.
So far, I have formalized the problem and now I am going to talk about the solution.
Our problem is the extension of Stable Matching problem.
So, in stable matching or stable marriage problem, we are given two sets; one for men
and the other for women and each person has ranked members of the other sex in order of
preference. They want to be paired and marry together
such that no two people of opposite sex would both rather have each other than their current
partners. When there are no such pairs of people, the
set of marriages is stable.
Gale-Shapely algorithm is known method that finds the stable matching in polynomial time
and has many real-world applications. While the stable marriage problem needs a
one-to-one matching, there is another version of this algorithm that works for the college
admission problem which is known as the Deferred acceptance algorithm and requires one-to-many
matching to be found. Meaning each college can be matched with many students.
The mechanism in all of these methods are similar and it consists of a series of propose
and rejections.
In the context of our problem, a many-to-many matching is required because each user should
be matched with many items and also each item should be matched with many users.
The mechanism used in the deferred acceptance algorithm is interesting mostly because it
is very intuitive and easy to understand. We’ll see this in the next slide.
So, here is how this method works. The Input data consists of two ranking preferences
for users and items, and two constraints for each side.
We start by setting S sub u, the set of selected items for user u to empty.
Then there is the main condition for the main loop of the algorithm. we actually start counting
our algorithm’s steps from this point as labeled in the flow-chart.
So, step 1, selects a user that has less than k items assigned to him in the matching mu.
At first round, mu is empty so, it requires many iterations for this condition to become
false. Next we select user u that made the previous
condition true and try to find the item that is preferred the most by this user and call
it item i. We add this item to the set of matching for
user u and also to the set of items selected by this user.
At step 3, we look at the item-side preferences and make sure that item i that has just assigned
to u has not been assigned more than its cap. If not, we do nothing for that item, and we
go back to the step 1. Otherwise, at step 4, we reject the user that
is least preferred by item i. and we remove that user from the matching set mu.
And we go back to step 1 and repeat this process until all the users are matched with exactly
k items.
In the longer version of the paper that is available on Arxiv we've proved and showed
that the same characteristics that are true about the Deferred acceptance algorithm is
also true about MMDA. The first one makes sure that MMDA always
finds a stable matching. The second one is about the user-optimality
of MMDA. Since we start from user preferences and actually users actively select the items
in contrast to the item-side that items impose their preferences in terms of rejections,
the algorithm favors users more and so MMDA finds a stable matching that is user-optimal.
In order to test the effectiveness of our method, we ran several experiments using three
datasets. MovieLens 1M which is widely known and used in recommender systems. Also, we
used two Amazon datasets in the domain of movies and books.
A basic summary of these datasets are shown in the table.
As we mentioned earlier our approach is a re-ranking one and so for the initial recommendations,
we used two methods: Non-negative matrix factorization and user-based kNN.
We generated 3000 recommendations for each user from these methods and use them in the
re-ranking methods to find the top-10 items.
To compare our method with previous works that re-rank the recommendation with the goal
of increasing accuracy and diversity we used two successful methods:
Bayesian re-ranking that is proposed by Saul Vargas
and Bi-criteria optimization using network flow that was presented at KDD 2017.
We use two metrics for evaluation. Precision@10 for accuracy and Gini-index for aggregate
diversity.
In this slide we show the results for our method for using Amazon Movies dataset.
In all of our experiments, since the data about item utilities were not available, we
used an implicit approach which is recommending users to items and use the scores generated
from that process to indicate the ranking preferences of items.
Figure 1 shows the results in terms of user and item utilities at each iteration of the
MMDA. At first few iterations you can see that the utilities are very small and this
is because there are many rejections by items that reduces the utility of both sides. But
as items distribute more evenly over recommendation lists the utilities become larger. Also, because
MMDA is user-optimal at each iteration the utility of users are greater than for items.
Figure 2 shows the utility of both sides for various constraints in terms of item caps.
Again since MMDA is user-optimal when we relax the constraint the utility of user-side dominates.
The main purpose of item cap is shown in figure 3, where the trade-off between accuracy and
gini-index is shown. Smaller gini-index values indicate more diversity. So, item caps, let
MMDA be flexible in dealing with accuracy-diversity tradeoff to the extreme degree of 100% or
perfect diversity which is the uniform distribution of items in the recommendation lists. For
cap equal to 11 we have reached the perfect diversity by loosing only 3% accuracy.
To the best of our knowledge no other algorithm is capable of reaching perfect diversity with
this amount of loss in accuracy. And this is one of the main advantages of this method.
These are the results for MovieLens dataset and we compared our method to the baselines
that we introduced earlier.
Since we are interested in the balance between accuracy and diversity we plotted the best
result in terms of average between Precision and inverse of Gini-index. As you can see
MMDA outperforms the other methods with a large margin.
In the line plot on the right, you can see that all the methods start from the orange
dot which is the base recommendation and as they increase gini-index the precision decreases.
We have highlighted the optimal or desired solution by the green region on the upper
right corner of the plot. MMDA does not perform better than NetFlow for higher precision values
but for high diversity values it has much lower precision loss.
Here we show the results for Amazon movies dataset.
For this dataset, our method performs much better than the baselines as you can see it
in both figures.
The results for the third dataset is available in the paper.
To conclude, we discussed the importance of maximizing both diversity and accuracy.
Also, we formalized the problem as a two-sided system with two ranking utilities for users
and items.
And, we argued that maximizing both utilities, increases aggregate diversity with small loss
in accuracy.
As a solution we generalized the known deferred acceptance algorithm for the case of many-to-many
matching and adapted that method into the context of recommendation.
Also, we ran several experiments to show the effectiveness of our method in terms of both
accuracy and diversity.
Results based on three datasets show that MMDA outperforms the baseline methods.
And that’s it. Thank for watching my presentation.