NDCG

Normalised Discounted Cumulative Gain (NDCG) is a metric used to evaluate the quality of ranked lists produced by search engines and recommender systems. It measures how well the items at the top of a list match their graded relevance to a given query or user.

The standard DCG at rank k is defined as DCG_k = sum_{i=1}^k (2^{rel_i} - 1) / log2(i + 1), where rel_i is the graded relevance of the item at position i. The term (2^{rel_i} - 1) is a gain function that rewards higher-relevance items, and the logarithmic discount reflects the decreasing importance of items lower in the ranking. Variants may use different gain functions, but the log2(i+1) denominator is common.

IDCG_k is the ideal DCG for the same set of items, obtained by sorting them in nonincreasing order of relevance and computing DCG on that ideal ranking. NDCG_k is then DCG_k divided by IDCG_k, yielding a score in the range [0, 1], where 1 corresponds to a perfect ranking at the top-k.

NDCG is widely used because it accommodates graded relevance and accounts for position bias. It is typically reported as NDCG@k for various cutoffs and averaged over queries. Practical considerations include the need for reliable relevance judgments, sensitivity to the chosen relevance scale and gain function, and handling of ties or incomplete rankings.