Discounted cumulative gain (DCG) is a measure of ranking quality in information retrieval.
NDCG is often used to measure effectiveness of search engine algorithms and related applications.
[1] NDCG is DCG normalized by the maximum possible DCG of the result set when ranked from highest to lowest gain, thus adjusting for the different numbers of relevant results for different queries.
DCG is a refinement of a simpler measure, Cumulative Gain (CG).
The value computed with the CG function is unaffected by changes in the ordering of search results.
Based on the two assumptions made above about the usefulness of search results, (N)DCG is usually preferred over CG.
The premise of DCG is that highly relevant documents appearing lower in a search result list should be penalized, as the graded relevance value is reduced logarithmically proportional to the position of the result.
But Wang et al. (2013)[2] gave theoretical guarantee for using the logarithmic reduction factor in Normalized DCG (NDCG).
The authors show that for every pair of substantially different ranking functions, the NDCG can decide which one is better in a consistent manner.
An alternative formulation of DCG[4] places stronger emphasis on retrieving relevant documents: The latter formula is commonly used in industrial applications including major web search companies[5] and data science competition platforms such as Kaggle.
Note that Croft et al. (2010) and Burges et al. (2005) present the second DCG with a log of base e, while both versions of DCG above use a log of base 2.
Convex and smooth approximations to DCG have also been developed, for use as an objective function in gradient based learning methods.
[7] Search result lists vary in length depending on the query.
Comparing a search engine's performance from one query to the next cannot be consistently achieved using DCG alone, so the cumulative gain at each position for a chosen value of
represents the list of relevant documents (ordered by their relevance) in the corpus up to position p. The nDCG values for all queries can be averaged to obtain a measure of the average performance of a search engine's ranking algorithm.
All nDCG calculations are then relative values on the interval 0.0 to 1.0 and so are cross-query comparable.
The main difficulty encountered in using nDCG is the unavailability of an ideal ordering of results when only partial relevance feedback is available.
The Cumulative Gain of this search result listing is: Changing the order of any two documents does not affect the CG measure.
DCG is used to emphasize highly relevant documents appearing early in the result list.
Using the logarithmic scale for reduction, the DCG for each result in order is: So the
results in a reduced DCG because a less relevant document is placed higher in the ranking; that is, a more relevant document is discounted more by being placed in a lower rank.
To normalize DCG values, an ideal ordering for the given query is needed.