Discounted cumulative gain

Discounted cumulative gain (DCG) is a measure of ranking quality in information retrieval. It is often normalized so that it is comparable across queries, giving Normalized DCG (nDCG or NDCG). NDCG is often used to measure effectiveness of search engine algorithms and related applications. Using a graded relevance scale of documents in a search-engine result set, DCG sums the usefulness, or gain, of the results discounted by their position in the result list. 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.

Two assumptions are made in using DCG and its related measures.

DCG is a refinement of a simpler measure, Cumulative Gain (CG). Cumulative Gain is the sum of the graded relevance values of all results in a search result list. CG does not take into account the rank (position) of a result in the result list. The CG at a particular rank position ${\displaystyle p}$ is defined as:

Where ${\displaystyle rel_{i}}$ is the graded relevance of the result at position ${\displaystyle i}$.

The value computed with the CG function is unaffected by changes in the ordering of search results. That is, moving a highly relevant document ${\displaystyle d_{i}}$ above a higher ranked, less relevant, document ${\displaystyle d_{j}}$ does not change the computed value for CG (assuming ${\displaystyle i,j\leq p}$). Based on the two assumptions made above about the usefulness of search results, (N)DCG is usually preferred over CG. Cumulative Gain is sometimes called Graded Precision.

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.

The usual formula of DCG accumulated at a particular rank position ${\displaystyle p}$ is defined as:

Until 2013, there was no theoretically sound justification for using a logarithmic reduction factor other than the fact that it produces a smooth reduction. But Wang et al. (2013) 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.