Efficient Exploration of Gradient Space for Online Learning to Rank

Huazheng Wang, Ramsey Langley, Sonwoo Kim, Eric McCord-Snook, Hongning Wang

This paper, presented at SIGIR 2018, tackles a fundamental bottleneck in Online Learning to Rank (OL2R): the inefficiency of exploring high-dimensional gradient spaces using random sampling.

TL;DR

The authors propose Null Space Gradient Descent (NSGD), an algorithm that accelerates online learning by avoiding previously failed gradient directions and focusing on rankers that are easily distinguishable by the current query. By shrinking the search space and maximizing the utility of every user interaction, NSGD achieves significantly faster convergence and higher ranking quality than traditional methods.

What Problem Does This Paper Address?

Online Learning to Rank (OL2R) allows search engines to learn directly from user interactions (like clicks) rather than relying solely on expensive, static, manual labels. Most OL2R algorithms follow a "dueling bandit" approach: they take the current ranker, perturb it in a random direction to create a candidate, and then "interleave" the results of both to see which one the user prefers.

However, this approach has two major flaws:

  1. The Haystack Problem: In high-dimensional feature spaces, a purely random "nudge" is unlikely to find a better ranking direction. Algorithms often waste time re-exploring directions that have already proven to be poor.
  2. The "Tie" Problem: Often, the current ranker and the candidate ranker produce the exact same document ordering for a specific query. When this happens, user clicks can't distinguish between them, leading to a "tie" and a wasted learning opportunity.

Methods

The authors introduce Null Space Gradient Descent (NSGD), which incorporates three novel strategies:

  • Null Space Exploration: The algorithm maintains a history of "bad" gradients (directions that failed to improve the ranker). It then restricts its search to the null space of these gradients—essentially looking only in directions that are mathematically orthogonal to known failures. This prevents the model from repeating past mistakes.
  • Context-Dependent Preselection (CDP): Instead of just picking any random direction in the null space, NSGD generates several candidates and selects the one most likely to produce a different ranking for the current query. This ensures that the subsequent user test is sensitive enough to actually provide a clear winner.
  • History-Dependent Tie Breaking: If a tie still occurs during a live test, NSGD doesn't just flip a coin. It looks back at "difficult" historical queries where the rankers might have behaved differently and uses recorded clicks from those sessions to break the tie.

Datasets

The researchers evaluated NSGD using the LETOR 3.0 and 4.0 benchmark collections, specifically:

  • MQ2007 and MQ2008: Large-scale datasets from the Million Query track at TREC.
  • TD2003, NP2003, and HP2003: Datasets representing different search tasks (topic distillation, named page finding, and homepage finding).

To simulate user behavior, they employed the Cascade Click Model with three profiles: Perfect (users always click relevant results), Navigational (users stop after finding one good result), and Informational (users are noisier and may click irrelevant results).

Key Insights and Ideas

  • Negative Knowledge is Power: In high-dimensional optimization, knowing where not to look is just as valuable as knowing where to look. By treating poorly performing gradients as constraints, the search space collapses into a much more manageable subspace.
  • Differentiability is a Prerequisite for Learning: An interleaved test is only useful if the two rankers actually disagree. By forcing the algorithm to propose "differentiable" candidates based on the current query's document features, the authors ensure that user feedback is almost always informative.
  • Exploiting "Difficult" Queries: Not all queries are equally good at distinguishing rankers. By identifying and reusing "difficult" queries for tie-breaking, the algorithm gains a "stress test" mechanism that standard OL2R lacks.

Key Results

  • Rapid Convergence: NSGD reached high ranking performance (measured by NDCG) much faster than baselines. For example, on the MQ2007 dataset with noisy "informational" users, NSGD achieved in 200 iterations what the previous state-of-the-art (MGD) required 800 iterations to reach.
  • Higher Quality at Early Stages: Because it avoids bad directions, NSGD provides better search results to users much earlier in the learning process, which is critical for maintaining user satisfaction in real-world systems.
  • Robustness to Noise: NSGD showed a much lower standard deviation in performance compared to other methods, suggesting it is less prone to the "erratic" updates that often plague stochastic gradient descent in online settings.

Limitations and Future Work

  • Theoretical Bias: While empirically successful, the authors note that the theoretical properties of sampling from a null space—specifically whether it maintains a low-bias estimation of the true gradient—require further study.
  • The "Offline Gap": While NSGD outperforms other online methods, it still doesn't quite reach the performance of "offline" models trained on perfect manual labels (like LambdaRank). The authors suggest that hybrid models combining offline pre-training with NSGD's online refinement could be a promising path.
  • Session-Awareness: The current model treats every query as independent. Future work could extend this to consider multi-step search sessions where user intent evolves over several queries.

Summary updated

Abstract

Online learning to rank (OL2R) optimizes the utility of returned search results based on implicit feedback gathered directly from users. In this paper, we accelerate the online learning process by efficient exploration in the gradient space. Our algorithm, named as Null Space Gradient Descent, reduces the exploration space to only the null space of recent poorly performing gradients. This prevents the algorithm from repeatedly exploring directions that have been discouraged by the most recent interactions with users. To improve sensitivity of the resulting interleaved test, we selectively construct candidate rankers to maximize the chance that they can be differentiated by candidate ranking documents in the current query; and we use historically difficult queries to identify the best ranker when tie occurs in comparing the rankers. Extensive experimental comparisons with the state-of-the-art OL2R algorithms on several public benchmarks confirmed the effectiveness of our proposal algorithm, especially in its fast learning convergence and promising ranking quality at an early stage.
BibTeX
@inproceedings{wang2018efficient,
  author = {Huazheng Wang and Ramsey Langley and Sonwoo Kim and Eric McCord-Snook and Hongning Wang},
  title = {{Efficient Exploration of Gradient Space for Online Learning to Rank}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2018},
  url = {https://openreview.net/forum?id=S1NVmUZ_-B},
}

Loading related content...

Figure