Learning from User Interactions with Rankings: A Unification of the Field

Harrie Oosterhuis

TL;DR

This thesis proposes a unified framework for Learning to Rank (LTR) that bridges the gap between online and counterfactual methods, leveraging user click data. It introduces novel algorithms that are effective in both online and counterfactual settings, offering a more robust and efficient approach to optimizing ranking systems.

What Problem Does This Paper Address?

Traditional supervised Learning to Rank (LTR) relies on expert annotations to train ranking models. However, obtaining these annotations is expensive, time-consuming, and can be ethically problematic (e.g., for personal documents). Furthermore, expert judgments may not always align with actual user preferences. To overcome these limitations, researchers have turned to learning from user interactions, primarily clicks. The challenge here is that clicks are influenced not only by user preferences but also by the ranking itself (e.g., position bias, item-selection bias). This thesis aims to unify different families of LTR methods that learn from user clicks, addressing the biases inherent in this data and developing a single, robust approach for both online (where the system actively influences user interactions) and counterfactual (where the system learns from historical, passively collected data) settings.

Methods

The thesis introduces several novel methods and frameworks:

  • Pairwise Preference Multileaving (PPM): For online evaluation, PPM is a multileaving algorithm that infers pairwise item preferences from clicks. It's proven to be both "considerate" (maintaining user experience) and "fidelity" (unbiased in unambiguous cases), outperforming existing methods in scalability and sensitivity.
  • Pairwise Differentiable Gradient Descent (PDGD): This is a novel online LTR algorithm that learns from inferred pairwise preferences without relying on model sampling or explicit online evaluation. PDGD is differentiable, allowing it to optimize non-linear models like neural networks, and is shown to be unbiased w.r.t. user preferences, achieving significant improvements in learning speed and convergence over existing methods.
  • Policy-Aware Estimator: For counterfactual LTR, this estimator corrects for item-selection bias in top-k rankings by considering the logging policy. It's shown to be unbiased even with limited top-k feedback and is unaffected by the choice of k.
  • GENSPEC (Generalization and Specialization): This framework combines robust feature-based generalization with specialized tabular models for counterfactual LTR. It uses high-confidence bounds to safely choose between a general policy and specialized policies per context (e.g., per query), achieving high performance on specialized contexts while maintaining robustness on unseen ones.
  • Logging-Policy Optimization Algorithm (LogOpt): This method optimizes the logging policy to minimize the variance of counterfactual estimates, turning counterfactual evaluation into an efficient online approach. It's shown to be unbiased and as efficient as interleaving methods.
  • Intervention-Aware Estimator: This is a novel counterfactual estimator that corrects for position bias, trust bias, and item-selection bias, crucially also accounting for the effect of online interventions (changes in the logging policy). This estimator bridges the gap between online and counterfactual LTR, showing significant benefits from online interventions.

Datasets

The paper utilizes several publicly available LTR datasets for experiments:

  • Yahoo! Webscope [17]: Contains 29,921 queries, ~24 documents per query, 700 features, and 5-grade relevance annotations.
  • MSLR-WEB30K [95] and MSLR-WEB10K: Derived from Bing search logs, these datasets have 30,000 (or 10,000 for WEB10K) queries, ~125 documents per query, 136 features, and 5-grade relevance annotations.
  • Istella [27]: A large dataset with 33,118 queries, ~315 documents per query, 220 features, and 5-grade relevance annotations.
  • MQ2007 and MQ2008 [95]: Based on the Million Query Track, these datasets have 1,700 and 800 queries respectively, with 46 features and 3-grade relevance annotations.

No new benchmarks were introduced; the focus was on evaluating existing and novel methods on established datasets.

Key Insights and Ideas

  • Unification is Possible: The thesis strongly argues that the divide between online and counterfactual LTR is artificial. By designing methods that can operate in both settings (e.g., the intervention-aware estimator), we can achieve superior performance and efficiency.
  • Counterfactual LTR's Theoretical Strength: Counterfactual methods, despite their stricter assumptions about user behavior, offer stronger theoretical guarantees (e.g., convergence) compared to online methods, which often rely on empirical results and have weaker theoretical backing.
  • The Power of Interventions: Online interventions (actively changing the logging policy) can significantly boost the data-efficiency and performance of counterfactual methods, turning them into highly effective online learners.
  • Beyond Simple Clicks: While clicks are a primary signal, future work could explore incorporating other user interaction signals for richer preference learning.
  • Specialization vs. Generalization: GENSPEC demonstrates that these two seemingly opposing concepts can be effectively combined, allowing for high performance in specific contexts while maintaining robustness across all contexts.

Key Results

  • PDGD Outperforms DBGD: Pairwise Differentiable Gradient Descent (PDGD) consistently outperformed Dueling Bandit Gradient Descent (DBGD) in terms of learning speed, convergence, and final performance, especially for non-linear models.
  • PPM Scales Well: Pairwise Preference Multileaving (PPM) was shown to be effective and scalable for online evaluation, outperforming existing methods in sensitivity and maintaining performance with an increasing number of rankers.
  • Policy-Aware Estimator Handles Top-k: The policy-aware estimator effectively addresses item-selection bias in top-k rankings, achieving near-optimal performance regardless of k.
  • GENSPEC Combines Strengths: GENSPEC successfully combined the specialization of tabular models with the generalization of feature-based models, achieving high performance on specialized queries while remaining robust on unseen ones.
  • LogOpt Improves Counterfactual Evaluation: The Logging-Policy Optimization Algorithm (LogOpt) makes counterfactual evaluation more efficient by optimizing the logging policy, leading to faster convergence and unbiased estimates.
  • Intervention-Aware Estimator Unifies: The intervention-aware estimator proved effective in both online and counterfactual settings, significantly benefiting from online interventions and achieving state-of-the-art performance. It also demonstrated robustness to various biases.

Limitations and Future Work

  • Theoretical Guarantees for Online Methods: While online methods show strong empirical performance, their theoretical guarantees are often weak or non-existent, making their reliability in practice uncertain. Future work could focus on developing theoretical approaches to understand the limits and conditions for reliable application of online LTR methods.
  • Understanding PDGD's Limits: The thesis identified scenarios where PDGD's performance degrades when not run fully online. Further theoretical work is needed to understand these limitations and potentially correct them.
  • More Complex User Behavior Models: The current models often rely on simplified assumptions about user behavior. Future research could explore more complex models that incorporate richer interaction signals beyond clicks.
  • Complex Optimization Goals: While the thesis focused on relevance, future work could explore counterfactual LTR for optimizing more complex goals like diversity, fairness, or computational efficiency.
  • Real-World Evaluation: The majority of experiments were conducted using semi-synthetic data. Future work should focus on evaluating these methods in real-world applications with actual users.
  • Policy Estimation: The policy-aware estimator requires knowledge of the logging policy. Future work could investigate whether a policy estimated from logs is sufficient.

Summary updated

Abstract

Ranking systems form the basis for online search engines and recommendation services. They process large collections of items, for instance web pages or e-commerce products, and present the user with a small ordered selection. The goal of a ranking system is to help a user find the items they are looking for with the least amount of effort. Thus the rankings they produce should place the most relevant or preferred items at the top of the ranking. Learning to rank is a field within machine learning that covers methods which optimize ranking systems w.r.t. this goal. Traditional supervised learning to rank methods utilize expert-judgements to evaluate and learn, however, in many situations such judgements are impossible or infeasible to obtain. As a solution, methods have been introduced that perform learning to rank based on user clicks instead. The difficulty with clicks is that they are not only affected by user preferences, but also by what rankings were displayed. Therefore, these methods have to prevent being biased by other factors than user preference. This thesis concerns learning to rank methods based on user clicks and specifically aims to unify the different families of these methods. As a whole, the second part of this thesis proposes a framework that bridges many gaps between areas of online, counterfactual, and supervised learning to rank. It has taken approaches, previously considered independent, and unified them into a single methodology for widely applicable and effective learning to rank from user clicks.
BibTeX
@article{oosterhuis2020learning,
  author = {Harrie Oosterhuis},
  title = {{Learning from User Interactions with Rankings: A Unification of the Field}},
  journal = {SIGIR},
  year = {2020},
  doi = {10.1145/3483382.3483402},
}
Figure