Normalized Discounted Cumulative Gain (NDCG) Measure

(Redirected from NDCG)
Jump to navigation Jump to search

A Normalized Discounted Cumulative Gain (NDCG) Measure is normalized version of a discounted cumulative gain measure that can account for differently sized output ranked lists.




    • 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.



  • (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'$.