Source-linked AI summary
A Theoretical Analysis of NDCG Type Ranking Measures
Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Tie-Yan Liu, Wei Chen
TL;DR
Ranking measures are central but their theoretical properties, especially for NDCG, have been limited despite extensive empirical study. The paper analyzes NDCG asymptotically, introduces consistent distinguishability, characterizes feasible discount decay, and studies NDCG@k. It finds that logarithmic NDCG converges to 1 while still consistently distinguishing substantially different ranking functions, with 1/r separating discount regimes.
Problem
The paper addresses the limited theoretical understanding of widely used NDCG measures and the need to evaluate ranking functions reliably.
Method
The paper theoretically analyzes NDCG asymptotics, defines consistent distinguishability, characterizes discount functions by decay rate, and studies NDCG@k choices.
Results
Logarithmic NDCG converges to 1 for every ranking function but consistently distinguishes every pair of substantially different ranking functions; 1/r is a critical discount-decay point.
Takeaways & Limitations
NDCG remains a theoretically useful ranking measure despite its numerical convergence, while discount decay and cutoff selection determine distinguishability properties.
Takeaways & Limitations
The paper cannot prove consistent distinguishability for Zipfian discount and suspects it may lack strong distinguishability power.
Abstract
from arXiv · showhide
A central problem in ranking is to design a ranking measure for evaluation of ranking functions. In this paper we study, from a theoretical perspective, the widely used Normalized Discounted Cumulative Gain (NDCG)-type ranking measures. Although there are extensive empirical studies of NDCG, little is known about its theoretical properties. We first show that, whatever the ranking function is, the standard NDCG which adopts a logarithmic discount, converges to 1 as the number of items to rank goes to infinity. On the first sight, this result is very surprising. It seems to imply that NDCG cannot differentiate good and bad ranking functions, contradicting to the empirical success of NDCG in many applications. In order to have a deeper understanding of ranking measures in general, we propose a notion referred to as consistent distinguishability. This notion captures the intuition that a ranking measure should have such a property: For every pair of substantially different ranking functions, the ranking measure can decide which one is better in a consistent manner on almost all datasets. We show that NDCG with logarithmic discount has consistent distinguishability although it converges to the same limit for all ranking functions. We next characterize the set of all feasible discount functions for NDCG according to the concept of consistent distinguishability. Specifically we show that whether NDCG has consistent distinguishability depends on how fast the discount decays, and 1/r is a critical point. We then turn to the cut-off version of NDCG, i.e., NDCG@k. We analyze the distinguishability of NDCG@k for various choices of k and the discount functions. Experimental results on real Web search datasets agree well with the theory.
1 Introduction
The paper develops a theoretical account of NDCG, motivated by the difficulty of evaluating ranking functions and limited theory behind widely used empirical measures. It shows that logarithmic NDCG converges numerically to 1 yet can still distinguish substantially different ranking functions, and characterizes discount and cutoff choices through this property.
- Ranking evaluation is difficult because a measure must order n! possible results, and no single measure is optimal for every application.
- NDCG is prominent in Web search because it supports graded relevance and discounts lower-ranked documents, reflecting users’ greater interest in top results.
- Prior NDCG research was mainly empirical, leaving theoretical questions about its asymptotic behavior and feasible discount functions.
- 1.1 Our Results: Standard logarithmic NDCG converges to 1 for every ranking function as the number of ranked items grows, creating an apparent numerical scaling problem.The paper notes that this issue may matter for large datasets such as Web search.
- 1.1 Our Results: Consistent distinguishability requires a ranking measure to consistently identify the better member of each pair of substantially different ranking functions on almost all datasets.
- 1.1 Our Results: Despite convergence to 1, standard NDCG consistently distinguishes every pair of substantially different ranking functions when numerical scaling is ignored.
- 1.1 Our Results: The decay rate determines feasibility: 1/r is critical, slower decay supports strong consistent distinguishability, while substantially faster decay lacks it and does not converge.
- 1.1 Our Results: The theory explains the slow-decay-plus-hard-cutoff design of NDCG@k and analyzes how its cutoff k should depend on dataset size.
2 Preliminaries
The paper formalizes ranking functions, datasets, discounts, and NDCG, then introduces canonical scoring functions to analyze ranking behavior asymptotically.
- A ranking function scores objects in X and orders them according to their scores.
- Datasets S_n contain i.i.d. object–relevance pairs drawn from an underlying distribution over X × Y.
- NDCG normalizes discounted cumulative gain, where DCG weights ranked-item relevance by a decreasing rank discount and normalization uses the best ranking’s DCG.
- The standard discount is D(r) = 1/log(1+r), with the logarithm base irrelevant because normalization cancels constant scaling.
- NDCG depends only on ranking order: score-preserving transformations produce identical NDCG values on every dataset.
- The canonical version of a ranking function preserves its order while transforming scores so that the canonical score has a uniform distribution on [0, 1].
3 Main Results
The main results show that NDCG’s asymptotic distinguishability depends critically on discount decay and cutoff growth, despite standard NDCG converging to 1 for every ranking function.
- 3.1 Standard NDCG: Standard NDCG converges almost surely to 1 for every ranking function as the number of ranked objects grows.
- 3.1 Standard NDCG: Despite the common limit, standard NDCG consistently distinguishes substantially different ranking functions under the paper’s conditions.
- 3.2 Characterization of Feasible Discount Functions: For D(r) = r^-β, the limit can reflect a correlation involving relevance conditional on canonical rank, enabling some distinction between ranking functions.
- 3.2 Characterization of Feasible Discount Functions: For polynomial discount D(r) = r^-β with β ∈ (0, 1), NDCG often converges to different limits for different ranking functions.
- 3.2 Characterization of Feasible Discount Functions: Zipfian discount D(r) = r^-1 yields a limit determined only by top-ranked performance, while lower-ranked relevance does not affect that limit.
- 3.2 Characterization of Feasible Discount Functions: The Zipfian case remains theoretically unresolved for strong consistent distinguishability, whereas discounts decaying faster than r^-(1+ε) lack convergence and consistent distinguishability.
- 3.3 Cut-off Versions of NDCG: For NDCG@k with k = o(n), the limit matches Zipfian NDCG, and its distinguishability power is likewise unclear.
- 3.3 Cut-off Versions of NDCG: For NDCG@k with k = cn, logarithmic and polynomial discounts retain consistent distinguishability under their corresponding conditions.
4 Experimental Results
Experiments on real Web search data broadly agree with the theory: discount choice determines convergence and distinguishability, while NDCG@k can separate ranking functions.
- Dataset and measures: The experiments use click-through logs from 40 independent queries, each containing 5000 documents labeled by click-count thresholds.Documents receive relevance labels 2, 1, or 0 according to whether they have more than 1000, 100–1000, or fewer than 100 clicks.
- Standard NDCG: Standard logarithmic NDCG produces nearly identical values that appear to converge to one limit, yet distinguishes the ranking functions when examined closely.The enlarged plot reveals separation despite the close overall trajectories.
- Alternative discounts: NDCG with feasible discount D(r) = r^-1/2 appears to converge to different limits and distinguishes the three ranking functions well.This behavior matches the reported theory for feasible discounts.
- Alternative discounts: NDCG with too-fast decay D(r) = 2^-r fails to distinguish the ranking functions well and is likely nonconvergent.The randomly chosen function has a score similar to RankSVM and ListNet.
- NDCG@k: NDCG@k with k = n/5 distinguishes the ranking functions, unlike standard logarithmic NDCG, which converges to the same limit.For k = cn, the cutoff measure can converge to different limits for different ranking functions.
A Proof of Theorem 2: the Key Lemmas
The proof establishes distinguishability by comparing NDCG expectations with pseudo-expectations, then controlling their empirical deviations under regularity assumptions.
- Definitions and setup: Definition 4 formalizes distinguishability in expectation as eventual, consistent ordering of two ranking functions by the measure.The comparison must hold for all sufficiently large sample sizes.
- Theorem 14: Theorem 14 concludes that standard logarithmic NDCG consistently distinguishes every pair whose conditional-relevance functions differ almost everywhere.The theorem first establishes distinguishability in expectation and, under the stated regularity condition, with high probability.
- Key lemmas: Lemma 2 bounds the difference between a ranking function’s expected NDCG and its pseudo-expectation.This makes the pseudo-expectation a useful approximation to the expected measure.
- Key lemmas: Lemma 3 shows that essentially different ranking functions have pseudo-expectations separated by a larger amount than the approximation error.The separation is nonzero unless the relevant conditional-relevance functions agree almost everywhere.
- Key lemmas: Under Holder continuity, Lemma 4 shows that empirical NDCG is close to its pseudo-expectation with high probability.This probabilistic concentration upgrades expected distinguishability to consistent distinguishability.
B Proofs of the Key Lemmas in Appendix A
The appendix proves the key lemmas through asymptotic bounds, order-statistic concentration, smoothness control, and separation of pseudo-expectations.
- Proof structure: The proof framework reduces the main theorem to three key lemmas and supporting technical claims.The lemmas address approximation, separation, and concentration components of the argument.
- Approximation bounds: The DCG analysis bounds normalization and approximation terms using logarithmic-integral asymptotics and expansions of the discount-related expressions.The resulting bound controls the difference between expected NDCG and pseudo-expectation.
- Pseudo-expectation separation: Separation follows by expanding the relevant difference in logarithmic moments and using completeness of the polynomial basis in the transformed L2 space.Unless the conditional-relevance difference vanishes almost everywhere, some moment is nonzero.
- Concentration: Order-statistic concentration controls the ranked scores because transformed ranking values are order statistics of uniformly distributed variables.Chernoff bounds and a union bound provide simultaneous control over ranks.
- Concentration: Holder continuity transfers rank-order concentration into control of conditional relevance, while Hoeffding’s inequality bounds the remaining weighted-sum fluctuation.The argument combines these bounds to prove the final concentration lemma.
C Proof of the Technical Claims in Appendix B
The technical appendix supplies the analytic and probabilistic ingredients used in the key-lemma proofs, including integral identities, basis completeness, and concentration inequalities.
- Technical claims: The technical claims are introduced as auxiliary results for proving the three key lemmas.They support both asymptotic estimates and probabilistic bounds.
- Probabilistic tools: Chernoff bounds control the number of relevant examples and the uniform order statistics appearing after ranking.The order-statistic argument treats transformed scores as uniformly distributed samples.
- Analytic bounds: Integration by parts and gamma-function identities provide the estimates needed for logarithmic integral terms.The appendix uses these identities in bounding the technical expressions.
- Concentration bounds: Monotonicity of the discount and its derivative, together with Hoeffding’s inequality, bounds the remaining weighted ranking fluctuations.The resulting estimates complete the technical proof chain.
- Functional analysis: Completeness of Laguerre polynomials implies that vanishing logarithmic moments force the function to vanish almost everywhere.This establishes the nondegeneracy needed for pseudo-expectation separation.
D Proof of the Convergence Theorems
The proofs establish convergence behavior for logarithmic, polynomial, and faster-decaying discounts. In particular, standard NDCG converges almost surely to 1, while sufficiently fast decay prevents convergence and distinguishability.
- Standard NDCG converges to 1 almost surely for every ranking function.The proof uses i.i.d. samples, a Chernoff bound, and the Borel–Cantelli lemma.
- Theorem 3 is proved from Lemma 5 and limiting calculations for a polynomial discount D(r) = r−β.Lemma 5 assumes p = Pr(Y = 1) > 0 and continuity of yf(s).
- The proof for D(r) = r−β uses that the discount and the magnitude of its derivative are monotone decreasing.This extends the relevant claim because r−β satisfies both properties.
- For discounts that decay substantially faster than r−1, NDCG does not converge and cannot strictly distinguish any pair of ranking functions with high probability.The proof constructs overlapping ranking-measure outcomes with at least constant probability.
- Theorem 6 is established first for binary labels Y = {0, 1}, with the extension to other label sets described as straightforward.The argument considers probabilities of top-ranked elements sharing label 1 or label 0.
E Proof of Distinguishability for NDCG with r−β (β ∈(0, 1)) Discount
The proof shows that NDCG with discount D(r) = r−β, for β ∈ (0, 1), has distinguishability. It uses lemmas under continuity or Hölder-continuity assumptions and a simple pseudo-expectation form.
- NDCG with D(r) = r−β, 0 < β < 1, has the power of distinguishability.The theorem follows from Lemmas 6 and 7.
- The polynomial-discount proof is simpler than the logarithmic-discount proof because its pseudo-expectation has a simple form.When the first condition is nonzero, the two NDCG values converge to different limits; otherwise, the proof uses the second condition and two lemmas.
- A related lemma also treats merely continuous yf(s), rather than requiring Hölder continuity.The proof modifies an earlier claim using continuity near the endpoint and the behavior of ∆y.
- Lemma 7 assumes p = Pr(Y = 1) > 0 and that yf(s) is Hölder continuous with constants α > 0 and C > 0.These assumptions support the distinguishability argument for D(r) = r−β.