A Theoretical Analysis of NDCG Type Ranking Measures

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.

COLT 2013

Cited by in corpus (37)

• The Emerging Trends of Multi-Label Learning
• Progresses and Challenges in Link Prediction
• Post Processing Recommender Systems with Knowledge Graphs for Recency, Popularity, and Diversity of Explanations
• DivGraphPointer: A Graph Pointer Network for Extracting Diverse Keyphrases
• BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models
• Adaptive Nonnegative Matrix Factorization and Measure Comparisons for Recommender Systems
• Cold Start Similar Artists Ranking with Gravity-Inspired Graph Autoencoders
• TranS^3: A Transformer-based Framework for Unifying Code Summarization and Code Search
• Image-Question-Answer Synergistic Network for Visual Dialog
• Do Offline Metrics Predict Online Performance in Recommender Systems?
• Large-scale Collaborative Filtering with Product Embeddings
• Learning to Collaborate in Multi-Module Recommendation via Multi-Agent Reinforcement Learning without Communication
• Leveraging Social Foci for Information Seeking in Social Media
• Be In The Know: Connecting News Articles to Relevant Twitter Conversations
• Regulating Group Exposure for Item Providers in Recommendation
• Multi-Aggregator Time-Warping Heterogeneous Graph Neural Network for Personalized Micro-Video Recommendation
• EmbeddingVis: A Visual Analytics Approach to Comparative Network Embedding Inspection
• Domain-to-Domain Translation Model for Recommender System
• JIM: Joint Influence Modeling for Collective Search Behavior
• Research Progress of News Recommendation Methods
• Deeply Supervised Semantic Model for Click-Through Rate Prediction in Sponsored Search
• Revisiting the problem of audio-based hit song prediction using convolutional neural networks
• Not all Embeddings are created Equal: Extracting Entity-specific Substructures for RDF Graph Embedding
• Polestar: An Intelligent, Efficient and National-Wide Public Transportation Routing Engine
• Variational Inference for Category Recommendation in E-Commerce platforms
• Keyword Aware Influential Community Search in Large Attributed Graphs
• Hawkes Process Multi-armed Bandits for Disaster Search and Rescue
• BanditMF: Multi-Armed Bandit Based Matrix Factorization Recommender System
• Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints
• Least Square Calibration for Peer Review
• UNICS: Multilingual Code Search via Unified Pseudocode and Contrastive Transfer Learning
• Data-Driven Relevance Judgments for Ranking Evaluation
• Adaptively Weighted Top-N Recommendation for Organ Matching
• Applications of Generative Adversarial Models in Visual Search Reformulation
• ReSCo-CC: Unsupervised Identification of Key Disinformation Sentences
• Learning Similarity between Movie Characters and Its Potential Implications on Understanding Human Experiences
• A scale invariant ranking function for learning-to-rank: a real-world use case