NDCG

#interview #retrieval #evaluation

NDCG (Normalized Discounted Cumulative Gain) is the default ranking metric. Listwise Ranking optimizes it directly. One of the Retrieval Metrics.
Built up in 3 steps, each fixing the last one's flaw:

1. CG (Cumulative Gain)

Sum the relevance of the top-K items.
Flaw: ignores position. The top item and the last item count the same, but order is the whole point.

2. DCG (Discounted CG)

Divide each item's relevance by a discount that grows with position, so rank 1 counts full, rank 10 counts less.

DCG

$D C G @ K = \sum_{i = 1}^{K} \frac{r e l_{i}}{\log_{2} (i + 1)}$

Flaw: raw value depends on the query. A query with many relevant items has a naturally higher DCG, so you cannot compare or average across queries.

3. NDCG (Normalized DCG)

Divide DCG by the ideal DCG (IDCG = DCG of the best possible ordering).

NDCG

$N D C G @ K = \frac{D C G @ K}{I D C G @ K}$

Now in [0, 1]: 1 = perfect ranking, comparable across queries.

Why NDCG is the default

Rewards putting relevant items high (position-discounted).
Supports graded relevance (0/1/2/3, not just relevant/not).
Normalized, so you can average over queries.
Contrast: Mean Reciprocal Rank (MRR) only cares about the first relevant item; MAP handles binary relevance; NDCG handles graded relevance + position. For binary top-K, see Precision@K and Recall@K.

References