Discounted Cumulative Gain (DCG) is one of the most popular metrics used for evaluation of ranking by any search engine. It is a measure of ranking quality. In information retrieval, it is often used to measure the effectiveness of web search engine.
It is based on the following assumptions:
- Highly relevant documents are more useful if appearing earlier in a search result.
- Highly relevant documents are more useful than marginally relevant documents which are better than non-relevant documents.
The formula for DCG goes as follows:
$$DCG_p = \sum_{i=1}^p \frac {rel_i} {log_2 (i+1)} = rel_1 + \sum_{i=2}^p \frac {rel_i} {log_2 (i+1)} \tag{1}$$
Where:
- i is the returned position of a document in the search result.
- $rel_i$ is the graded relevance of the document
- summation over p (number of results returned) hence, accumulated cumulative gain gives the performance metrics of the returned result.
DCG is derived from CG (Cumulative Gain), given by:
$$CG_p = \sum_{i=1}^p rel_i \tag{2}$$
From (2) it can be seen that $CG_p$ does not change for a change in the order of results. Thus to overcome this issue DCG was introduced. There is a different form of DCG, which is popular for placing a very high emphasis on retrieval of the documents. This version of DCG is given by:
$$DCG_p = \sum_{i=1}^p \frac {2^{rel_i} - 1} {log_2 (i+1)} \tag{3}$$
One obvious drawback of the DCG equation presented in (1) and (3) is that algorithms returning a different number of results cannot be compared effectively. This is because the higher the value of $p$ the higher the value of $DCG_p$ will be scaled to.
To overcome this issue, normalized DCG (nDCG) is proposed. It is given by,
$$nDCG_p = \frac {DCG_p} {IDCG_p}$$
where $IDCG_p$ is the Ideal $DCG_p$, given by,
$$IDCG_p = \sum_{i=1}^{|REL|} \frac {2^{rel_i} - 1} {log_2 (i+1)}$$
Where |REL| is the list of documents ordered by relevance in the corpus up to position p.
For a perfect ranking algorithm,
$$DCG_p = IDCG_p$$
Since the values of nDCG are scaled within the range [0,1], the cross-query comparison is possible using these metrics.
Drawbacks:
1. nDCG does not penalize the retrieval of bad documents in the result. This is fixable by adjusting the values of relevance attributed to documents.
2. nDCG does not penalize missing documents. This can be fixed by fixing the retrieval size and using the minimum score for the missing documents.
Refer this for seeing example calculations of nDCG.
Reference
