Metrics for evaluating ranking algorithms

Question

I'm interested in looking at several different metrics for ranking algorithms - there are a few listed on the Learning to Rank wikipedia page, including:

• Mean average precision (MAP);

• DCG and NDCG;

• Precision@n, NDCG@n, where "@n" denotes that the metrics are evaluated only on top n documents;

• Mean reciprocal rank;

• Kendall's tau

• Spearman's Rho

• Expected reciprocal rank

• Yandex's pfound

but it isn't clear to me what are the advantages/disadvantages of each or when you may choose one over another (or what it would mean if one algorithm outperformed another on NDGC but was worse when evaluated with MAP).

Is there anywhere I can go to learn more about these questions?

Answer 1

I am actually looking for the same answer, however I should be able to at least partially answer your question.

All of the metrics that you have mentioned have different traits and, unfortunately, the one you should pick depends on what you actually would like to measure. Here are some things that it would be worth to have in mind:

• Spearman's rho metric penalises errors at the top of the list with the same weight as mismatches on the bottom, so in most cases this is not the metric to use for evaluating rankings
• DCG & NDCG are one of the few metrics that take into account the non-binary utility function, so you can describe how useful is a record and not whether it's useful.
• DCG & NDCG have fixed weighs for positions, so a document in a given position has always the same gain and discount independently of the documents shown above it
• You usually would prefer NDCG over DCG, because it normalises the value by the number of relevant documents
• MAP is supposed to be a classic and a 'go-to' metric for this problem and it seems to be a standard in the field.
• (N)DCG should be always computed for a fixed amount of records (@k), because it has a long tail (lots of irrelevant records at the end of the ranking highly bias the metric). This doesn't apply to MAP.
• Mean Reciprocal Rank only marks the position of the first relevant document, so if you care about as many relevant docs as possible to be high on the list, then this should not be your choice
• Kendall's tau only handles binary utility function, it also should be computed @k (similar to NDCG)

Valuable resources:

• Victor Lavrenko lecture on YouTube - it's only a link to the MAP vs NDCG episode, but the whole lecture includes much more (including Kendall's Tau). You should definitely check it out, great lecture!
• ERR paper

Can't post more links, because of the fresh account :) If anybody has some more remarks or ideas, I would be happy to hear them as well!

Answer 2

In many cases where you apply ranking algorithms (e.g. Google search, Amazon product recommendation) you have hundreds and thousands of results. The user only wants to watch at the top ~20 or so. So the rest is completely irrelevant.

To phrase it clearly: Only the top $k$ elements are relevant

If this is true for your application, then this has direct implications on the metric:

1. You only need to look at the top $k$ ranked items and the top $k$ items of the ground truth ranking.
2. The order of those potentially $2k$ items might be relevant or not - but for sure the order of all other items is irrelevant.

Three relevant metrics are top-k accuracy, precision@k and recall@k. The $k$ depends on your application. For all of them, for the ranking-queries you evaluate, the total number of relevant items should be above $k$.

Top-k classification accuracy for ranking

For the ground truth, it might be hard to define an order. And if you only distinguish relevant / not relevant, then you are actually in a classification case!

Top-n accuracy is a metric for classification. See What is the definition of Top-n accuracy?.

$$\text{top-k accuracy} = \frac{\text{how often was at least one relevant element within the top-k of a ranking query?}}{\text{ranking queries}}$$

So you let the ranking algorithm predict $k$ elements and see if it contains at least one relevant item.

I like this very much because it is so easy to interpret. $k$ comes from a business requirement (probably $k \in [5, 20]$), then you can say how often the users will be happy.

Downside of this: If you still care about the order within the $k$ items, you have to find another metric.

Precision@k

$$\text{Precision@k} = \frac{\text{number of relevant items within the top-k}}{k} \in [0, 1], \text{ higher is better}$$

What it tells you:

• if it is high -> Much of what you show to the user is relevant to them
• if it is low -> You waste your users time. Much of what you show them, is not relevant to them

Recall@k

$$\text{Recall@k} = \frac{\text{number of relevant items within the top-k}}{\text{total number of relevant items}} \in [0, 1], \text{ higher is better}$$

What it means:

• If it is high: You show what you have! You give them all the relevant items.
• If it is low: Compared with the total amount of relevant items, k is small / the relevant items within the top k is small. Due to this, recall@k alone might be not so meaningful. If it is combined with a high precision@k, then increasing k might make sense.

Answer 3

I recently had to choose a metric for evaluating multilabel ranking algorithms and got to this subject, which was really helpful. Here are some additions to stpk's answer, which were helpful for making a choice.

• MAP can be adapted to multilabel problems, at the cost of an approximation
• MAP does not need to be computed at k but the multilabel version might not be adapted when the negative class is preponderant
• MAP and (N)DCG can both be rewritten as weigthed average of ranked relevance values

---

Details

Let us focus on average precision (AP) as mean average precision (MAP) is just an average of APs on several queries. AP is properly defined on binary data as the area under precision-recall curve, which can be rewritten as the average of the precisions at each positive items. (see the wikipedia article on MAP) A possible approximation is to define it as the average of the precisions at each item. Sadly, we lose the nice property that the negative examples ranked at the end of the list have no impact on the value of AP. (This is particularly sad when it comes to evaluating a search engine, with far more negative examples than positive examples. A possible workaround is to subsample the negative examples, at the cost of other downsides, e.g. the queries with more positive items will become equally difficult to the queries with few positive examples.)

On the other hand, this approximation has the nice property that it generalizes well to the multilabel case. Indeed, in the binary case, the precision at position k can be also interpreted as the average relevance before position k, where the relevance of a positive example is 1, and the relevance of a negative example is 0. This definition extends quite naturally to the case where there are more than two different levels of relevance. In this case, AP can also be defined as the mean of the averages of the relevances at each position.

This expression is the one chosen by the speaker of the video cited by stpk in their answer. He shows in this video that the AP can be rewritten as a weighted mean of the relevances, the weight of the $k$-th element in the ranking being

$$w_k^{AP} = \frac{1}{K}\log(\frac{K}{k})$$

where $K$ is the number of items to rank. Now we have this expression, we can compare it to the DCG. Indeed, DCG is also a weighted average of the ranked relevances, the weights being:

$$w_k^{DCG} = \frac{1}{\log(k+1)}$$

From these two expressions, we can deduce that - AP weighs the documents from 1 to 0. - DCG weighs the documents independently from the total number of documents.

In both cases, if there are much more irrelevant examples than relevant examples, the total weight of the positive can be negligible. For AP, a workaround is to subsample the negative samples, but I'm not sure how to choose the proportion of subsampling, as well as whether to make it dependent on the query or on the number of positive documents. For DCG, we can cut it at k, but the same kind of questions arise.

I'd be happy to hear more about this, if anybody here worked on the subject.