CoChat
Sign Up
PreprintCited by 351Information Retrieval and Search BehaviorRecommender Systems and TechniquesGame Theory and Voting Systems

A Theoretical Analysis of NDCG Type Ranking Measures

Open access
Wang, Yining, Wang, Liwei, Li, Yuanzhi, He, Di, Liu, Tie-Yan, Chen, Wei·2013·arXiv
DOI 10.48550/arxiv.1304.6480arXiv 1304.6480
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1304.6480

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 34

  1. [2][2] A. Al-Maskari, M. Sanderson, and P. Clough. The relationship between IR effectiveness measures and user satisfaction. In SIGIR , pages 773-774, 2007. -
  2. [3][3] J. Aslam, E. Yilmaz, and V. Pavlu. The maximum entropy method for analyzing retrieval measures. In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval , pages 27-34. ACM, 2005. -
  3. [5][5] M. Balcan, N. Bansal, A. Beygelzimer, D. Coppersmith, J. Langford, and G. Sorkin. Robust reductions from ranking to classification. Machine learning , 72(1):139-153, 2008. -
  4. [6][6] P. Bartlett, M. Jordan, and J. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association , 101(473):138-156, 2006. -
  5. [7][7] D. Buffoni, C. Calauzenes, P. Gallinari, and N. Usunier. Learning scoring functions with order-preserving losses and standardized supervision. In Proceedings of the 28th International Conference on Machine Learning , 2011. -
  6. [8][8] C. Burges, R. Ragno, and Q. V. Le. Learning to rank with nonsmooth cost functions. In Advances in Neural Information Processing Systems 19: Proceedings of the 2006 Conference , volume 19, page 193. The MIT Press, 2007. -
  7. [9][9] C. Calauz` enes, N. Usunier, and P. Gallinari. On the (non-)existence of convex, calibrated surrogate losses for ranking. In P. Bartlett, F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Advances in Neural Information Processing Systems 25 , pages 197-205. 2012. -
  8. [10][10] Z. Cao, T. Qin, T. Liu, M. Tsai, and H. Li. Learning to rank: from pairwise approach to listwise approach. In ICML , pages 129-136, 2007. -
  9. [11][11] O. Chapelle, D. Metlzer, Y. Zhang, and P. Grinspan. Expected reciprocal rank for graded relevance. In Proceedings of the 18th ACM conference on Information and knowledge management , pages 621-630. ACM, 2009. -
  10. [12][12] S. J. Cl´ emen¸ con and N. Vayatis. Empirical performance maximization for linear rank statistics. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems 21 , pages 305-312. 2009. -
  11. [13][13] S. Clemen¸ con, G. Lugosi, and N. Vayatis. Ranking and empirical minimization of U-statistics. The Annals of Statistics , 36(2):844-874, 2008. -
  12. [14][14] D. Cossock and T. Zhang. Statistical analysis of bayes optimal subset ranking. Information Theory, IEEE Transactions on , 54(11):5140-5154, 2008. -
  13. [15][15] K. Crammer and Y. Singer. Pranking with ranking. In Advances in Neural Information Processing Systems , 2002. -
  14. [16][16] W. Croft, D. Metzler, and T. Strohman. Search engines: Information retrieval in practice . Addison-Wesley, 2010. -
  15. [17][17] J. Duchi, L. Mackey, and M. Jordan. On the consistency of ranking algorithms. In Proceedings of the 27th International Conference on Machine Learning , pages 327-334, 2010. -
  16. [18][18] Y. Freund, R. Iyer, R. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences. The Journal of Machine Learning Research , 4:933-969, 2003. -
  17. [19][19] J. H´ ajek, Z. ˇ Sid´ ak, and P. Sen. Theory of rank tests . Academic press New York, 1967. -
  18. [20][20] R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. Advances in Neural Information Processing Systems , pages 115-132, 1999. -
  19. [21][21] K. J¨ arvelin and J. Kek¨ al¨ ainen. IR evaluation methods for retrieving highly relevant documents. In Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval , pages 41-48. ACM, 2000. -
  20. [22][22] K. J¨ arvelin and J. Kek¨ al¨ ainen. Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems (TOIS) , 20(4):422-446, 2002. -
  21. [23][23] T. Joachims. Optimizing search engines using clickthrough data. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining , pages 133142. ACM, 2002. -
  22. [24][24] E. Kanoulas and J. A. Aslam. Empirical justification of the gain and discount function for NDCG. In Proceedings of the 18th ACM conference on Information and knowledge management , pages 611-620. ACM, 2009. -
  23. [26][26] R. Nallapati. Discriminative models for information retrieval. In Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval , pages 64-71. ACM, 2004. -
  24. [27][27] P. Ravikumar, A. Tewari, and E. Yang. On NDCG consistency of listwise ranking methods. In Proceedings of 14th International Conference on Artificial Intelligence and Statistics, AISTATS , 2011. -
  25. [28][28] C. Rudin. The p-norm push: A simple convex ranking algorithm that concentrates at the top of the list. The Journal of Machine Learning Research , 10:2233-2271, 2009. -
  26. [29][29] T. Sakai. Evaluating evaluation metrics based on the bootstrap. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval , pages 525-532. ACM, 2006. -
  27. [31][31] A. Tewari and P. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research , 8:1007-1025, 2007. -
  28. [32][32] A. Turpin and F. Scholer. User performance versus precision measures for simple search tasks. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval , pages 11-18. ACM, 2006. -
  29. [33][33] H. Valizadegan, R. Jin, R. Zhang, and J. Mao. Learning to rank by optimizing NDCG measure. Advances in Neural Information Processing Systems , 22:1883-1891, 2009. -
  30. [34][34] E. Voorhees. Evaluation by highly relevant documents. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval , pages 74-82. ACM, 2001. -
  31. [35][35] F. Xia, T. Liu, J. Wang, W. Zhang, and H. Li. Listwise approach to learning to rank: theory and algorithm. In Proceedings of the 25th international conference on Machine learning , pages 1192-1199. ACM, 2008. -
  32. [36][36] Y. Yue, T. Finley, F. Radlinski, and T. Joachims. A support vector method for optimizing average precision. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval , pages 271-278. ACM, 2007. -
  33. [37][37] T. Zhang. Statistical analysis of some multi-category large margin classification methods. The Journal of Machine Learning Research , 5:1225-1251, 2004. -
  34. [38][38] T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. Annals of Statistics , pages 56-85, 2004.

Cited by

Sorted by citations

Authors
Wang, Y., Wang, L., Li, Y., He, D., Liu, T.-Y., & Chen, W.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2013
Pages
25-54
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1304.6480
arXiv
1304.6480
OpenAlex
W2131676173
Cited by
351
References
0
Citations by year
2026: 2 · 2025: 19 · 2024: 25 · 2023: 34 · 2022: 28 · 2021: 52 · 2020: 39 · 2019: 47 · 2018: 36 · 2017: 12 · 2016: 21 · 2015: 17 · 2014: 15 · 2013: 4
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • Conference on Learning Theory
Topics
  • Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
  • Physical Sciences › Computer Science › Information Systems › Recommender Systems and Techniques
  • Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
Keywords
NDCG, discount function, convergence to 1, web search ranking

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review