Loading...

Rank-Aware Top-N Metrics

Course video 6 of 20

Recommender Systems: Evaluation and Metrics

University of Minnesota

Course 3 of 5 in the Recommender Systems Specialization

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.

Taught By

Michael D. Ekstrand
Assistant Professor
Joseph A Konstan
Distinguished McKnight Professor and Distinguished University Teaching Professor

Transcript

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.

About Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play