NDCG (Normalized Discounted Cumulative Gain)

Normalized discounted cumulative gain (NDCG) divides the DCG of a ranked list by the DCG of the best possible ordering of the evaluation’s full set of judged candidate items, cut off at the same rank. A relevant item missing from the returned list therefore lowers the score, because the ideal ordering still includes it. With nonnegative relevance grades and at least one relevant item, the result lies between 0 and 1. Wang et al. (2013) define it as DCG divided by the ideal DCG, the DCG value of the best ranking.

A worked example

These labels are hypothetical. The list has relevance grades 3, 2, 3, 0, 1 at ranks 1 to 5, so linear DCG@5 is 6.149. The best ordering of the same five judged items is 3, 3, 2, 1, 0, whose DCG@5 is 6.324. NDCG@5 is 6.149 / 6.324 = 0.972. With exponential gains the same ranking has DCG@5 of 12.780, the ideal is 13.347, and NDCG@5 is 0.957. The same ranking receives 0.972 or 0.957 depending on the gain convention.

The single-target case

When each user has exactly one held-out relevant item at rank \(r\), the ideal DCG is 1 and NDCG@K is \(1/\log_2(r+1)\) if \(r \le K\) and 0 otherwise. At K = 10, rank 1 scores 1, rank 3 scores 0.5, and rank 11 scores 0. The Recommender Systems article uses this form, and He et al. (2017) report HR@K and NDCG@K with the test item ranked among 100 sampled items the user had not interacted with, truncating the list at 10. Scores are averaged over users.

What has to be fixed before comparing scores

• Gain convention. Linear or exponential, as above.
• Cutoff K. NDCG@5 and NDCG@10 are different measures.
• Candidate set. In the recommender systems article, an SVD model scored 0.1226 when ranked against the full eligible pool and 0.4058 when ranked against 100 uniformly sampled distractors. Removing competing items cannot push a fixed target down, so a sampled score can exceed the full-pool score for an unchanged model.
• Queries with no relevant items. The ideal DCG is zero, so the ratio is undefined. The protocol has to say whether such queries are skipped or scored as zero.
• Ties. Scikit-learn averages tied scores by default; see scikit-learn’s documentation for ndcg_score.

What NDCG does not say

NDCG rewards an ordering relative to the best ordering of the labeled items. It says nothing about unlabeled items, which is why missing labels matter. Hit rate records only whether the target appears in the top K, while NDCG also rewards an earlier position. Averages over users can hide how the scores are distributed. A difference between two models is also an estimate, so its uncertainty needs reporting before a ranking of models is trusted; Confidence Intervals and Comparing Models: Uncertainty and Significance discuss this.

References:

• Wang et al., A Theoretical Analysis of NDCG Type Ranking Measures, arXiv:1304.6480
• scikit-learn documentation, ndcg_score
• He et al., Neural Collaborative Filtering (WWW 2017), arXiv:1708.05031