DCG (Discounted Cumulative Gain)

Discounted cumulative gain (DCG) scores a ranked list by adding up the relevance of its items while discounting the items that appear lower in the list. Earlier positions count more, so moving a relevant item up raises the score. The measure comes from Järvelin and Kekäläinen (2002), one of the references cited for the metric in scikit-learn’s documentation for ndcg_score.

Definition

Following Wang et al. (2013), DCG over the top \(n\) positions is \(\sum_{r=1}^{n} G(y_{(r)})\,D(r)\), where \(y_{(r)}\) is the relevance of the item at rank \(r\), \(G\) is a monotone increasing gain function, and \(D\) is a discount. The paper notes that the logarithmic discount \(1/\log(1+r)\) dominates the literature and applications, and that a Zipfian discount \(1/r\) also appears. With a base-2 logarithm the score at cutoff \(K\) is \(\mathrm{DCG@K} = \sum_{r=1}^{K} G(y_r)/\log_2(r+1)\). The discounts for ranks 1 to 5 are 1, 0.631, 0.5, 0.431, and 0.387.

Two gain conventions

• Linear gain, \(G(y) = y\). Per its documentation, scikit-learn sums the true scores in the order given by the predicted scores after applying a logarithmic discount.
• Exponential gain, \(G(y) = 2^{y} – 1\), which Wang et al. give as an example of a gain function. It rewards highly relevant items more strongly.

The two conventions produce different numbers for the same ranking, so a DCG or NDCG value is only comparable with values computed under the same convention. The Regression and Ranking Metrics article notes that some implementations use \(2^{y}-1\) and that the convention should be checked before scores are compared.

A worked example

These labels are hypothetical. A list of five items has relevance grades 3, 2, 3, 0, 1 at ranks 1 to 5.

Linear DCG@5 is 3.000 + 1.262 + 1.500 + 0 + 0.387 = 6.149. With exponential gains of 7, 3, 7, 0, and 1, DCG@5 is 12.780.

Reading the number

• DCG is not bounded by 1. It grows with the cutoff, the number of relevant items, and the scale of the grades, so values from different queries or settings are not directly comparable. NDCG divides by the best achievable DCG to address that.
• Relevance grades should be nonnegative.
• Tie handling differs between implementations. Scikit-learn averages tied scores by default and offers an option to assume there are no ties, so identical scores can give different values in different libraries.
• The score is only as meaningful as the labels. See Relevance in Recommender Systems for where labels come from and what missing labels mean.

References:

• Wang et al., A Theoretical Analysis of NDCG Type Ranking Measures, arXiv:1304.6480
• scikit-learn documentation, ndcg_score