An Alternative Cross Entropy Loss for Learning-to-Rank

Sebastian Bruch

TL;DR

This paper introduces XENDCG, a novel cross-entropy loss function for learning-to-rank (LTR) that is theoretically sound and demonstrably a convex bound on NDCG, a crucial ranking metric. XENDCG not only matches but often surpasses the performance of state-of-the-art LTR methods like LambdaMART, particularly in scenarios with noisy data or limited ensemble size.

What Problem Does This Paper Address?

Learning-to-rank (LTR) algorithms are essential for tasks like web search and recommendation systems, aiming to order items by relevance. While "listwise" LTR methods, which consider entire lists of items at once, have shown empirical success, they often lack theoretical grounding. Existing listwise losses are typically heuristic or only loosely related to ranking metrics like NDCG (Normalized Discounted Cumulative Gain). This theoretical gap hinders understanding and limits progress, as it's unclear why these methods work or how to improve them systematically. The paper aims to bridge this gap by proposing a theoretically sound LTR loss function that directly relates to NDCG.

Methods

The core contribution is the XENDCG loss function. It's a modification of the ListNet loss, which uses cross-entropy between probability distributions derived from relevance labels and predicted scores. The key innovation in XENDCG lies in how it constructs the probability distribution from the scores. This seemingly minor change leads to significant theoretical advantages:

  • Theoretical Soundness: XENDCG is proven to be a convex upper-bound on a translated and log-transformed version of negative NDCG. This means minimizing XENDCG directly encourages better NDCG scores.
  • Consistency with NDCG: Under common conditions in information retrieval (e.g., graded relevance or single clicks per query), XENDCG is shown to be "NDCG-consistent," meaning the optimal solution for the loss function is also optimal for NDCG.
  • Approximation of Inverse Hessian: For optimization with gradient boosting machines (which often use second-order methods), the paper addresses the singularity of the Hessian for XENDCG by introducing a small epsilon. They then develop a method to approximate the inverse Hessian, enabling efficient training.
  • XENDCGMART: The authors implement XENDCG within a Gradient Boosted Regression Tree framework, creating a model they call XENDCGMART.

Datasets

The paper uses two publicly available benchmark datasets for learning-to-rank:

  • MSLR Web30K: Contains approximately 30,000 examples with an average of 120 documents per example and 136 features.
  • Yahoo! Learning to Rank Challenge Set 1: Similar in size to Web30K, but with an average of 24 documents per example and 519 features.

Both datasets feature graded relevance labels (0-4). The authors split these datasets into training, validation, and test sets and repeat experiments 100 times to ensure robust evaluation.

Key Insights and Ideas

  • Bridging Theory and Practice: The most significant insight is the creation of a listwise loss function (XENDCG) that is not only empirically effective but also theoretically grounded in its relationship to NDCG. This is a major step towards understanding and improving LTR algorithms.
  • The Power of a Small Change: A subtle modification to the score-to-probability mapping in ListNet dramatically improves its theoretical properties, highlighting the sensitivity of LTR loss functions to their formulation.
  • Robustness to Noise: XENDCG demonstrates superior robustness to noisy relevance labels and augmented document lists compared to AMART. This is crucial for real-world applications where data is often imperfect.
  • Efficiency with Fewer Trees: XENDCGMART shows faster convergence and better performance with smaller ensembles (fewer trees) than AMART, making it more suitable for latency-sensitive applications.
  • Complexity and Document Count: The theoretical analysis reveals that AMART's complexity (Lipschitz constant) scales with the number of documents per query ($m$), while XENDCG's does not. This explains why XENDCG might generalize better in scenarios with many documents.

Key Results

  • Ranking Quality: XENDCGMART consistently outperformed ListNet and achieved statistically significant improvements over AMART on both Web30K and Yahoo! datasets across NDCG@5 and NDCG@10 metrics. For example, on Web30K, XENDCGMART achieved NDCG@10 of 77.84%, compared to AMART's 77.49% and ListNet's 76.52%.
  • Convergence: Figure 1 shows that XENDCGMART achieved higher NDCG@5 on validation sets earlier in the training process (with fewer trees) compared to AMART.
  • Robustness to Noise: In experiments with augmented document lists (simulating more negative documents) and perturbed relevance labels, AMART's performance degraded more significantly than XENDCGMART's as noise levels increased. This was particularly evident in the simulated click data experiments.

Limitations and Future Work

  • The Role of 'y': The paper acknowledges that the parameter 'y' in the XENDCG formulation plays a role in its theoretical properties. While they sampled 'y' uniformly for experiments, a more detailed examination of its effect and strategies for optimizing it, especially within boosting, is suggested for future work.
  • Online Learning: Given XENDCG's robustness to noise, exploring its application in an online learning setting is proposed.
  • Further Theoretical Analysis: The authors suggest further investigation into the bounds and consistency of XENDCG, particularly how they are affected by the 'y' parameter and boosting.

Summary updated

Abstract

Listwise learning-to-rank methods form a powerful class of ranking algorithms that are widely adopted in applications such as information retrieval. These algorithms learn to rank a set of items by optimizing a loss that is a function of the entire set -- as a surrogate to a typically non-differentiable ranking metric. Despite their empirical success, existing listwise methods are based on heuristics and remain theoretically ill-understood. In particular, none of the empirically successful loss functions are related to ranking metrics. In this work, we propose a cross entropy-based learning-to-rank loss function that is theoretically sound, is a convex bound on NDCG -- a popular ranking metric -- and is consistent with NDCG under learning scenarios common in information retrieval. Furthermore, empirical evaluation of an implementation of the proposed method with gradient boosting machines on benchmark learning-to-rank datasets demonstrates the superiority of our proposed formulation over existing algorithms in quality and robustness.
BibTeX
@inproceedings{bruch2019alternative,
  author = {Sebastian Bruch},
  title = {{An Alternative Cross Entropy Loss for Learning-to-Rank}},
  booktitle = {The Web Conference},
  year = {2019},
  url = {https://openreview.net/forum?id=nPBkq2zdoOe},
}
Figure