Normalized Discounted Cumulative Gain (NDCG) Measure

Context:
- It can (typically) be used as an Ranking Performance Measure, such as an IR perf. measure.
- It can be calculated by an NDCG Calculation System, such as [1].
- …
Counter-Example(s):
See: Cumulative Gain, Ranked-Output Performance Measure.

References

http://en.wikipedia.org/wiki/Discounted_cumulative_gain#Normalized_DCG
- QUOTE: 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 [math]\displaystyle{ p }[/math] should be normalized across queries. This is done by sorting documents of a result list by relevance, producing the maximum possible DCG till position [math]\displaystyle{ p }[/math], also called Ideal DCG till that position. For a query, the normalized discounted cumulative gain, or nDCG, is computed as: :[math]\displaystyle{ \mathrm{nDCG_{p}} = \frac{DCG_{p}}{IDCG{p}} }[/math] The nDCG values for all queries can be averaged to obtain a measure of the average performance of a search engine's ranking algorithm. Note that in a perfect ranking algorithm, the [math]\displaystyle{ DCG_p }[/math] will be the same as the [math]\displaystyle{ IDCG_p }[/math] producing an nDCG of 1.0. 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.

(Wang, Jin, & Chang, 2010) ⇒ Fengxia Wang, Huixia Jin, and Xiao Chang. (2010). “Relevance Vector Ranking for Information Retrieval.” In: Journal of Convergence Information Technology, 5(9).
- QUOTE: The normalized discounted cumulative gain (NDCG) (Kekäläinen, 2005) is adopted as a performance measure, which takes the form [math]\displaystyle{ NDGC@k = N(k) \bullet \sum^{k}_{j=1}\frac{2^{r(j)}-1}{log(1+j)} }[/math] where [math]\displaystyle{ N(k) }[/math] is the NDCG at [math]\displaystyle{ k }[/math] of ideal ranking list. It is used as a normalization factor of the NDCG at [math]\displaystyle{ k }[/math] in the ranking list of prediction results.

(Manning et al., 2008) ⇒ Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. (2008). “Introduction to Information Retrieval." Cambridge University Press. ISBN:0521865719.
- QUOTE: A final approach that has seen increasing adoption, especially when employed with machine learning approaches to ranking svm-ranking is measures of cumulative gain , and in particular normalized discounted cumulative gain (NDCG). NDCG is designed for situations of non-binary notions of relevance (cf. Section 8.5.1). Like precision at $k$, it is evaluated over some number $k$ of top search results. For a set of queries $Q$, let $R(j,d)$ be the relevance score assessors gave to document $d$ for query $j$. Then, [math]\displaystyle{ \mbox{NDCG}(Q, k) = \frac{1}{\vert Q\vert} \sum_{j=1}^{\vert Q\vert} Z_{kj} \sum_{m=1}^{k} \frac{2^{R(j,m)}-1}{\log_2(1+m)}, (44) }[/math] where [math]\displaystyle{ Z_{kj} }[/math] is a normalization factor calculated to make it so that a perfect ranking's NDCG at $k$ for query $j$ is 1. For queries for which $k' < k$ documents are retrieved, the last summation is done up to $k'$.

(Järvelin et al., 2002) ⇒ Kalervo Järvelin, and Jaana Kekäläinen. (2002). “Cumulated Gain-based Evaluation of IR Techniques.” In: ACM Transactions on Information Systems (ACM TOIS), 20(4). doi:10.1145/582415.582418
- QUOTE: Furthermore, the normalized nCG and nDCG measures support evaluation.
  * They represent performance as relative to the ideal based on a known (possibly large) recall base of graded relevance judgments.
  * The performance differences between IR techniques are also normalized in relation to the ideal thereby supporting the analysis of performance differences.