05 Cumulative gain (normalized, discounted) (NDCG)

Normalized discounted cumulative gain (NDCG) is an evaluation metric for ranking models. NDCG provides a measure of ranking quality, under the assumption that it is especially important to rank the most relevant documents near the top. By comparison, average precision rewards correct ordering without explicitly privileging the ordering at higher rankings over the ordering at lower rankings.

NDCG is a refinement of discounted cumulative gain (DCG), which in turn refines cumulative gain (CG). We shall define each in turn.

Cumulative gain (CG)

Let be the relevance score of the -th document, given in the range . Then the cumulative gain at rank (also called “graded precision at ”) is given as

Notice that CG does not depend on the relative ordering within the first documents in the ranking. It is also more difficult to interpret than precision@k, which shares this limitation. Hence, raw CG is rarely used in practice.

Discounted cumulative gain (DCG)

Discounted cumulative gain reduces the contribution of lower-ranked documents, such that the highest rankings have the largest impact on the metric. It is given as

A key limitation of DCG is that it depends implicitly on the non-discounted cumulative gain for a given query. That is, if query A has many highly relevant documents, and query B has only one highly relevant document, then their respective DCG values for the same will differ. To correct this limitation, DCG may be normalized by an ideal CG.

Normalized discounted cumulative gain (NDCG)

Given a known ground-truth ordering, it is possible to compute an ideal discounted cumulative gain up to rank . Then NDCG can be given as

NDCG can be compared across any two queries, making it a useful measure of overall ranking model performance.