NDCG, MRR & Ranking Metrics

Why Standard Classification Metrics Fail on Rankings

Accuracy and Precision treat all predictions equally regardless of position.

In search engines and recommendation systems, position matters immensely:

• Placing a relevant item at Rank 1 is a massive win.
• Placing that same relevant item at Rank 20 (on page 2 of search results) means $99%$ of users will never see it!

Ranking Metrics score ordered lists by penalizing relevant items placed lower in rank results.

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ 1. MRR (Reciprocal Rank) │ 2. MAP (Mean Avg Prec)   │ 3. NDCG (Norm Discounted)│
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Evaluates rank of FIRST  │ Evaluates binary relevance│ Evaluates MULTI-LEVEL    │
│ relevant item. Single    │ across multiple relevant │ relevance (0=Bad, 3=Great)│
│ target search queries!   │ items in ranked lists.   │ Industry Gold Standard!  │
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

1. Mean Reciprocal Rank (MRR)

Evaluates the Reciprocal Rank of the first relevant item across $Q$ queries:

$$\text{MRR} = \frac{1}{|Q|} \sum_{i=1}^{|Q|} \frac{1}{\text{rank}_i}$$

• If first relevant item is at Rank 1 $\implies 1 / 1 = 1.0$.
• If first relevant item is at Rank 2 $\implies 1 / 2 = 0.5$.
• If first relevant item is at Rank 5 $\implies 1 / 5 = 0.2$.

Use Case: Navigational search (e.g. searching for "Login page" or "Python docs").

2. Mean Average Precision (MAP@K)

Evaluates binary relevance ($1$ or $0$) across multiple relevant items in top-$K$ results:

$$\text{AP@K} = \frac{\sum_{k=1}^K \text{Precision}@k \cdot \text{rel}(k)}{|\text{Total Relevant Items}|}$$

$$\text{MAP@K} = \frac{1}{|Q|} \sum_{i=1}^{|Q|} \text{AP@K}_i$$

Use Case: E-commerce search where multiple products are relevant.

3. Normalized Discounted Cumulative Gain (NDCG@K)

NDCG is the industry gold standard metric for search and recommendation systems.

Unlike MRR and MAP (which assume binary $0/1$ relevance), NDCG supports Multi-Level Graded Relevance (e.g. $0 = \text{Irrelevant}, 1 = \text{Fair}, 2 = \text{Good}, 3 = \text{Perfect}$).

Step 1: Cumulative Gain (CG@K)

$$\text{CG}@K = \sum_{i=1}^K r_i$$

Step 2: Discounted Cumulative Gain (DCG@K)

Applies Logarithmic Position Discounting (penalizing relevant items placed lower in the list):

$$\text{DCG}@K = \sum_{i=1}^K \frac{2^{r_i} - 1}{\log_2(i + 1)}$$

Step 3: Normalization (NDCG@K)

Divide actual DCG@K by Ideal DCG@K (IDCG@K) (the maximum possible DCG achieved if items were sorted in perfect descending relevance order):

$$\text{NDCG}@K = \frac{\text{DCG}@K}{\text{IDCG}@K}$$

$\text{NDCG}@K$ outputs a normalized score between $0.0$ and $1.0$.

Summary Comparison Matrix

Say this out loud

Ranking metrics evaluate ordered recommendation lists. MRR measures the reciprocal rank 1 over rank of the first relevant item. MAP averages precision across multiple binary relevant items. NDCG is the gold standard for multi level graded relevance, discounting item relevance logarithmically based on rank position and normalizing against ideal sorting.

Followups to expect

1. What is Hit Rate@K (HR@K)? The fraction of test users for whom at least one ground-truth positive item appears anywhere within the top-K recommendation list ($1$ if hit, $0$ if miss).
2. Why is logarithmic discounting used in DCG? Logarithmic discounting $\frac{1}{\log_2(i+1)}$ reflects human eye tracking research showing that user attention drops rapidly between rank 1 and 5, and flattens out past rank 10.