Metrics for evaluating ranking algorithms

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).

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:

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!

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.