Ranking metrics

Offline metrics compare a predicted order with the true relevance grades. Different metrics answer different questions. NDCG handles graded relevance. MRR fits queries with one right answer. Recall at k judges the candidate stage, before ranking. Most of the confusion comes from not knowing which question each metric answers.

DCG and NDCG

Discounted cumulative gain (DCG) adds up the gain of each result, with a discount for lower positions:

DCG@k = sum over i = 1..k of (2^rel_i − 1) / log2(i + 1)

The gain 2^rel − 1 makes highly relevant documents count much more than marginally relevant ones. The discount log2(i + 1) makes a result at rank 1 count more than the same result at rank 5.

NDCG divides by the best possible DCG, the ideal DCG (IDCG), which uses the grades sorted from highest to lowest. A perfect order scores 1, whatever the grades are.

Walking through one query

Five documents come back in the model's order, with true grades from 0 to 3:

The predicted DCG at 5 is:

i=1, rel=3:  (2³ − 1) / log2(2) = 7 / 1     = 7.000
i=2, rel=2:  (2² − 1) / log2(3) = 3 / 1.585 = 1.893
i=3, rel=0:  0 / log2(4)                    = 0
i=4, rel=1:  (2¹ − 1) / log2(5) = 1 / 2.322 = 0.431
i=5, rel=2:  (2² − 1) / log2(6) = 3 / 2.585 = 1.161

DCG@5 ≈ 10.484

The ideal order sorts the grades to 3, 2, 2, 1, 0. Its DCG is 7 + 1.893 + 1.500 + 0.431 + 0 ≈ 10.823. So:

NDCG@5 = 10.484 / 10.823 ≈ 0.969

The order is close to ideal. The loss comes from positions 3 and 5, where a grade-2 document sits below a grade-0 document.

MRR, MAP and recall at k

• MRR (mean reciprocal rank) finds the rank of the first relevant document, takes 1 / rank, and averages over queries. If the first relevant item is at rank 4, its score is 0.25. Use it when there is one right answer, such as navigation or question answering.
• MAP (mean average precision) works with binary relevance. It averages precision at each relevant position, then averages over queries. It rewards finding all the relevant items early.
• Recall at k is the share of all relevant items that appear in the top k. It judges candidate generation. The ranker is judged by NDCG or MRR.

Common mistakes

• Comparing numbers from different gain formulas. Some texts use a linear gain rel / log2(i + 1). Only compare scores computed the same way.
• Choosing a cutoff the user never sees. NDCG at 10 on a screen that shows 3 results measures the wrong thing. Match k to the UI.
• Judging the ranker with recall at 1,000. A ranker that shows 10 results should be judged on the top of its list.

Check yourself

1. Why divide DCG by IDCG? Answer: so a perfect order scores 1 for any query, and different queries become comparable.
2. What is the reciprocal rank if the first relevant document is at position 4? Answer: 1/4 = 0.25.

Key takeaways

• DCG discounts gains by position. NDCG divides by the ideal DCG so a perfect order scores 1.
• MRR suits a single right answer. MAP suits binary relevance with many relevant items.
• Recall at k judges retrieval. NDCG and MRR judge the ranker.
• Set k to match what the user sees.

Further learning

Next, see how a boosted-tree ranker optimizes NDCG directly in LambdaMART.