In this course you will learn how to evaluate recommender systems. You will gain familiarity with several families of metrics, including ones to measure prediction accuracy, rank accuracy, decision-support, and other factors such as diversity, product coverage, and serendipity. You will learn how different metrics relate to different user goals and business goals. You will also learn how to rigorously conduct offline evaluations (i.e., how to prepare and sample data, and how to aggregate results). And you will learn about online (experimental) evaluation. At the completion of this course you will have the tools you need to compare different recommender system alternatives for a wide variety of uses.
Rank-Aware Top-N Metrics
Loading...
From the course by University of Minnesota
Recommender Systems: Evaluation and Metrics
109 ratings
From the lesson
Basic Prediction and Recommendation Metrics
Meet the Instructors
Michael D. EkstrandAssistant Professor
Dept. of Computer Science, Boise State University
Joseph A KonstanDistinguished McKnight Professor and Distinguished University Teaching Professor
Computer Science and Engineering
Welcome back.
In this video, we're going to be talking about a family of Top-N
metrics that are aware of the rank,
the position within the recommendation list in which the good items appear.
So we've seen a couple of families of metrics so far.
One looks at how accurate rating predictions are,
how close the predictive rating is to the rating that the user provided.
And we've looked at metrics that look at how
good the recommender is at finding things.
For example, the precision metric that looks at the fraction of the recommended
items that the user is actually going to like.
In this video, we're going to look at these metrics that take into account
where in the recommendation list the items are.
And another way of thinking about this
is how good the recommender is at modeling relative preference.
The prediction accuracy metrics look at whether the recommender
can accurately model the fact that I like The Iron Giant.
The decision support metrics look at whether or
not the recommender recommends movies I like, like The Iron Giant.
But these metrics are going to look at,
does it put The Iron Giant high on the list?
And does it model whether I like The Iron Giant better or
worse, than Big Hero 6, in a way that's consistent with my actual preference.
There are two families of these rank accuracy metrics and
they have different requirements for the input data that they use.
One set of metrics is going to require binary relevance judgment.
These metrics are based on binary relevance,
like the decision support metrics that we saw.
They need a notion of whether or not an item is good, and
they will use that in conjunction with the ranking.
The utility based metrics need a measure of absolute or
relative goodness of an item.
Then you'd be able, not just okay, is The Iron Giant good?
But, how good is The Iron Giant?
Or is it better or worse than Frozen?
The first metric we're going to look at is mean reciprocal rank.
This is a very simple rank metric.
It asks the question, where is the first relevant item?
So you've given me a list of 10, 20 recommendations.
How far down the list do I have to go to find an item that the user likes?
Now this does need binary relevance judgements.
We need to know whether or not the user likes the item.
The way we compute it is for each user we generate a list of recommendations.
We find the rank of the first relevant recommendation.
We start from one, so the recommendation to the top of the list has rank 1.
We then compute the reciprocal rank, 1 over the rank.
And that's the reciprocal rank measure that operates per user.
The mean reciprocal rank performance of the whole system is just taking the mean
over the set of users of the reciprocal rank achieved for each user.
If there are no relevant items,
then we basically treat the rank of the first relevant item as infinity, so
the reciprocal rank achieved for that user is zero.
To see this in action, let's consider a list of recommendations.
We have A, B, C, D.
Now, let's say that B is the first one that the user likes.
We don't care about C and D.
We found the first one the user likes, B.
So the rank k
sub B = 2.
So the reciprocal rank is 1/2.
If A was a relevant item, If A was
a relevant item, then the reciprocal rank would be a perfect score of one.
And it decreases as we go further on down the list.
So if C is the first relevant item, it's going to be one third.
If D, it's going to be one fourth.
So we see that it decreases.
We also see that the further we get down the list, the less
it decreases by pushing the next relevant item or
the first relevant item one spot further down the list.
So, we have a progression of 1, 1/2, 1/3,
1/4, and we can see that the penalty for
pushing the item further down the list gets smaller and smaller.
So here we have a penalty of 1/2, here we've got a penalty of 1/6,
we have a penalty of 1/12.
So, this models the idea that in the first part of the list,
users are going to be pretty sensitive to where things are.
First, second, third, this makes a big difference.
It doesn't much make a difference if it's 57 or 58.
It's pretty far down the list.
So, the penalty for getting worse decreases as the relevant
recommendations get pushed further down the list.
So, mean reciprocal rank is a very simple metric.
Easy to compute, easy to understand what it means.
It also very clearly models targeted search or recommendation tasks,
where the user wants a particular thing.
And how quickly they can find the thing that they want
is what we're wanting to capture in the evaluation.
So, you can see it used in information retrieval, where we're wanting to find out
when the user types in A job, a compile error, for example.
And they want to find a solution to that error.
It doesn't really matter if there are 5, 10, 50 solutions.
If the first one is good and is pretty close to the top of the list,
mean reciprocal rank captures that kind of a task very concisely.
It's less clearly appropriate for general recommendation scenarios, but it still
is very worthwhile metric for evaluating the performance of our recommenders.
We can envision a scenario like a movie recommender
suggesting what movie you want to stream tonight.
You're going to go down the list and find the first one you want to watch.
Mean reciprocal rank is a credible metric for
that kind of a recommendation scenario.
The next one we're going to look at is average precision.
So the precision metric that we talked about earlier asks,
what fraction of recommendations are good?
So we've got five recommendations, ten recommendations.
That of ten recommendations, six of them are relevant,
then we've achieved a precision of 0.6.
This has a couple of issues.
One, it only works and is comparable with a fixed list size.
Also, it treats all errors the same.
So, in our ten item list, getting the first item wrong
is penalized exactly the same as getting the tenth item wrong.
But users are going to pay more attention again to the top of the list.
It's the whole idea of rank aware evaluation metrics.
So we want to emphasize when we're measuring our recommender,
its accuracy at the top of this recommendation list.
And average precision modifies precision to do just that.
What it does is for each user, we compute an average precision.
And the way that's computed is that for
each relevant item, we compute the precision of the list through that item.
And then we take the average of these different precision
values to get the average precision of the recommendations for that user.
So let's see an example of this.
So again, if we have our recommendations A, B, C, D, E, and
let's say this one's good and
this one's bad, and good, good, bad.
So A is the first good recommendation.
So we're going to compute the precision, Which is 1.
Find a good item.
C is the next good item.
So we're going to say that precision, there's two out of the three items so
far that are good, so we're going to say the precision equals 2/3.
The D is the next relevant item, and its precision three of four are good.
So its precision is going to be P = 3/4.
So then we're going to take the average of these three precisions.
So 1 + 2/3 + 3/4,
all over 3, is the average precision
of this recommendation list.
What happens is whether or not A is relevant is counted three times.
It affects the first precision, the second precision, and the third precision.
Whether or not B is relevant and
C irrelevant, that only affects two of the precision values.
So, the recommender is only penalized twice for
getting B wrong, so we count the precision of the first
item more than we count the precision of the later items,
which captures again our intuition that users pay more attention or
are more affected by the relevance and the accuracy of
the recommendations that appear at the top of the recommendation list.
Once we have the average precision for each user, we average it over
all the users that we're evaluating our recommender for and
we get the mean average precision, or MAP.
Some additional metrics are looking at the rank correlation,
correlation of the recommendations.
If we have a way of ranking items for a user, we might have ratings,
we might have a set of pairwise preferences.
Then we can compare the order that the system produces to
the order if we ranked them by user's preference.
One way of doing this is to use the Spearman correlation, and
Spearman is a rank version of the Pearson correlation.
What it is, is it's a Pearson correction over item ranks.
So we assign each item its rank values.
If items are tied, then we average the ranks of all of the tied items and
assign that average rank to all items that are ranked in that position.
And then we just compute the Pearson correlation of these rank values and
that gives us a Spearman correlation, and it tells us how aligned two rankings are.
One major problem with it though, is that it punishes all misorderings or
inconsistencies equally.
If it swaps 1 and 3, if it swaps 11 and 13,
those are equally bad in Spearman's view.
So, what we want to do is weight things at the top of the list more heavily.
Again, the same thing were trying to do with mean reciprocal rank,
with mean average precision,
we want to place more emphasis on how good the recommender is at the top of the list.
Discounted cumulative gain is a way of doing this.
What it does is it looks at the utility of the item at each position in the list.
So, when we have ratings, this can be the rating assigned to that value,
five, three, two, whatever, if we have unary or binary data we can use
utilities of one for good items and zero for irrelevant items.
And then we discount this utility or gain by position in the list.
So we place more emphasis on
the items at the top of the list and then we normalize by
comparing the discounted cumulative gain of the list the recommender produced
versus the discounted cumulative gain of a perfect recommendation list.
If it ordered it in order from greatest to least utility, what DCG would it achieve?
And what we get is a measure called Normalized Discounted Cumulative Gain,
which effectively measures the fraction of utility that it's possible
to achieve that the recommender actually received.
So the formula for this looks like the discounted cumulative gain,
is the utility, which I'm just modeling for now as a rating value,
over the discount and then we sum it up over all of the items.
And the discount, if i is the position,
the standard discount is a logarithmic discounting.
So items one and two get a discount of one, and
then as the item is greater than two, we use the log of that rank for our discount.
You can use other discounts.
One that's been used is based on a half-life decay that has a probabilistic
model that at some point, say five, the probability that the user
that the user would click the item goes to 0.5.
But log base 2 discounting is the most common application
of discounted cumulative gain.
To see this in action, let's consider a short recommendation list,
A, B, C ,D, where the user rates A, 4, B, 3, C, 0, and D, 5.
So then our DCG for this is going to be
4/1 + 3/1 +
0/1.58 + 5/2,
which is equal to 9.5.
The perfect DCG, DCG perfect,
Is equal to 5/1 because for the perfect one, we're considering,
what if we put five, four, three, these best ones, at the top, in order?
So 5/1 + 4/1 +
3/1.58 + 0,
which is equal to 10.9.
And so then the nDCG is equal to 9.5/10.9.
So we have our achieved discounted cumulative gain
divided by our possible discounted cumulative gain,
results in a final metric value of 0.872.
So we've achieved 87% of the possible discounted cumulative gain by using
this recommendation list.
So compute the nDCG for each user's list, then we can average those over the users
to get an estimate of the system's overall performance.
As I said log based discounting is very common, for
a log base b, we don't discount items one through b, because
the logarithm of one is zero, which results in a division by zero.
So, we just say the first b items get the same rank of one.
There's also a good theoretical basis for
doing a half-life discounting with an exponential decay function.
Because we can think of users as being exponentially less likely to
click each successive items.
They're most likely to click the first, less likely to click the second.
So what we do is we set a half-life, this half-life alpha,
which is the rank where the user has a 50% probability of clicking the item.
And this lets us measure the expected utility of the list that's been provided.
Different users have different ratings, different possible gains.
This is why we have to do the normalization.
So we get this normalization by the best achievable gain,
where a perfect score is one, so achieved all the possible gain.
Another metric we can look at is the fraction of concordant pairs.
What fraction of pairs of items are in the correct relative order?
This tests the pairwise accuracy of the recommender.
We can also adapt these metrics to measure rank effectiveness.
So with Top-N recommendation often what we're doing,
is we're telling the recommender, give me items from the universe, and
then we're measuring for the ones we know the relevance of.
We're going to talk more in detail about this in a later video, but we can say just
rank them the items for which we have relevance judgements, and we
can test whether that rank is consistent with the user's relevance judgements.
So there's several different metrics we can use to measure a recommender's
ability to order items.
nDCG and MAP are increasingly common in the recommenders' systems literature.
Mean reciprocal rank is showing up in the recommenders' systems literature.
It's also used a fair amount in information retrieval.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
