PaperlayerView exact revision on arXiv

Source-linked AI summary

Unbiased Learning-to-Rank with Biased Feedback

Thorsten Joachims, Adith Swaminathan, Tobias Schnabel

arXiv:1608.04468v1cs.IRcs.LG

TL;DR

The paper addresses bias in implicit-feedback LTR, especially position bias that makes clicks unreliable training signals. It develops counterfactual propensity-weighted ERM and shows robustness in synthetic tests and substantially improved retrieval on an operational search engine.

  • Problem

    Implicit-feedback clicks are abundant but biased by presentation order, while conventional click-model relevance inference often requires repeated queries.

  • Method

    The paper uses counterfactual estimation to derive propensity-weighted ERM, with click models assigning propensities to clicked results in hindsight.

  • Results

    The method is robust to selection bias, noise, and propensity-model misspecification, and real-world experiments show substantial retrieval improvements.

  • Takeaways & Limitations

    Propensity SVM-Rank can learn ranking functions from observational implicit feedback without requiring repeated queries or routine ranking randomization.

  • Takeaways & Limitations

    Small datasets can favor Naive SVM-Rank because propensity weighting increases variance; propensity clipping trades bias for variance.

Abstract

from arXiv · show

Implicit feedback (e.g., clicks, dwell times, etc.) is an abundant source of data in human-interactive systems. While implicit feedback has many advantages (e.g., it is inexpensive to collect, user centric, and timely), its inherent biases are a key obstacle to its effective use. For example, position bias in search rankings strongly influences how many clicks a result receives, so that directly using click data as a training signal in Learning-to-Rank (LTR) methods yields sub-optimal results. To overcome this bias problem, we present a counterfactual inference framework that provides the theoretical basis for unbiased LTR via Empirical Risk Minimization despite biased data. Using this framework, we derive a Propensity-Weighted Ranking SVM for discriminative learning from implicit feedback, where click models take the role of the propensity estimator. In contrast to most conventional approaches to de-bias the data using click models, this allows training of ranking functions even in settings where queries do not repeat. Beyond the theoretical support, we show empirically that the proposed learning method is highly effective in dealing with biases, that it is robust to noise and propensity model misspecification, and that it scales efficiently. We also demonstrate the real-world applicability of our approach on an operational search engine, where it substantially improves retrieval performance.

1. INTRODUCTION

Implicit feedback offers an inexpensive alternative to costly expert annotations, but clicks are distorted by presentation order and conventional debiasing methods have important constraints. The paper proposes a counterfactual, propensity-weighted approach that learns from observational feedback without requiring repeated queries or ranking randomization during normal data collection.

  • Expert relevance annotations are costly and often infeasible for applications such as personal collection and intranet search.
  • Treating clicks as relevance labels is severely biased because presentation order strongly influences where users click.
  • Clicked-versus-skipped preferences capture mainly preferences opposing the presented order, causing biased training that can reverse rankings without heuristics.
  • Click models account for position and context bias, but reliable relevance inference typically requires repeated queries, which is unrealistic for many settings and tail queries.
  • The paper develops unbiased counterfactual risk estimation and Propensity SVM-Rank, using click models for hindsight propensities rather than aggregate relevance judgments.
  • Synthetic and operational-search-engine evaluations find robustness to bias, noise, and propensity misspecification, alongside substantially improved retrieval performance.

2. RELATED WORK

Related work handles biased implicit feedback either by interpreting observational data with user-behavior models or by intervening during feedback collection. The paper builds on inverse propensity scoring and randomized interventions while extending propensity weighting to broader sources of selection bias.

  • Bias-handling methods divide into observational approaches that interpret fixed feedback and intervention approaches that seek less biased feedback through presented rankings.
  • Cascade and other click models explain user behavior and support learning preferences between skipped and clicked documents.
  • Randomized documents, adjacent swaps, and interleaving provide unbiased relevances, pairwise preferences, or reliable comparisons between rankers.
  • The paper uses inverse propensity scoring with rank-swapping interventions to estimate relative position propensities while limiting performance impact.
  • Its key extension is using click-model propensities to correct position, trust, contextual, popularity, and related selection biases.

3. FULL-INFO LEARNING TO RANK

Full-information LTR assumes known document relevances for sampled queries and uses them to compute ranking risk. ERM methods such as SVM-Rank optimize empirical risk, while expert judgments remain expensive and introduce pooling and intent-aggregation limitations.

  • Full-information LTR assumes known relevances for all documents associated with sampled queries and uses them to compute ranking loss.
  • ERM selects a ranking system by optimizing empirical risk, typically with regularization to control overfitting.
  • SVM-Rank is used as a representative LTR algorithm following the ERM strategy.
  • Expert judgments are expensive and often infeasible, including for personal collection search.
  • Pooling reduces judging effort but introduces bias when unjudged documents are assumed irrelevant.
  • Aggregating judgments across intents sharing a query string can make appropriate relevance assignment challenging.

4. PARTIAL-INFO LEARNING TO RANK

Partial-information LTR addresses relevance signals that are selectively revealed by user interaction and therefore distorted by presentation bias. The paper models observation propensities, applies inverse propensity scoring, and obtains unbiased empirical risk suitable for ERM under mild conditions.

  • User-specific query instances allow implicit feedback to reflect each user's relevance judgment and contextual information need.
  • Implicit feedback is not missing completely at random: presentation bias makes higher-ranked results more likely to reveal relevance signals.
  • The counterfactual model represents true relevances, partially observed relevance vectors, and observation propensities conditioned on query, ranking, and relevance.
  • Inverse propensity scoring estimates the loss of a new ranking from partially observed feedback, provided relevant results have positive observation propensity.
  • Only clicked relevant results contribute to the estimator, so computability and unbiasedness require propensities to depend on observable information.
  • Averaging IPS estimates across query instances defines propensity-weighted empirical risk for learning.
  • E[ R_hat_IPS(S)] = R(S), and the estimator converges to true risk as sample size grows when propensities are bounded away from zero.
  • With capacity control, consistent empirical risk yields consistent ERM, which finds the best system in the hypothesis class given enough training data.

5. FEEDBACK PROPENSITY MODELS

The paper models click propensities from examination and click behavior, then uses inverse propensity scoring to support unbiased learning from observational feedback. The framework remains consistent under specified click noise, estimates position propensities through rank-swapping interventions, and can extend beyond the basic position model.

  • Position-Based Propensity Model: The propensity model factors clicks into examination probability by rank and click probability conditional on relevance and examination.The basic examination model represents presentation bias with rank-specific examination probabilities.
  • Position-Based Propensity Model: Under the noise-free model, clicks on examined results are synonymous with relevance, allowing examination to serve as the observation process.This yields Q(oi(y)|xi, ¯yi, ri) ≡ P(ei(y)|rank(y|¯yi)).
  • Position-Based Propensity Model: IPS produces an unbiased risk estimate under the position-based model when every rank has positive propensity, without requiring explicit negative judgments.The estimator only needs observation indicators for clicked, relevant results.
  • Position-Based Propensity Model: Unlike prior click-model approaches, the model de-biases individual observed judgments for ERM rather than estimating average relevance from repeated queries.This enables the framework to use observational feedback without relying on repeated instances of the same query.
  • Incorporating Click Noise: With click noise, IPS risk estimates may be biased for true relevance, but their expected ordering remains aligned with true risk, preserving the risk minimizer.The paper therefore characterizes propensity-weighted ERM as consistent for finding a best-ranking function under the specified noise model.
  • Propensity Estimation: Rank-swapping interventions estimate relative examination propensities, while requiring only a positive multiplicative scale and affecting less data than uniform randomization.Swapping a landmark rank with other ranks makes clickthrough rates proportional to the rank-specific parameters.
  • Alternative Feedback Propensity Models: The basic click propensity model is intentionally simple, but it can incorporate trust, saliency, alternative click models, and feedback beyond binary clicks.The ERM framework also applies to explicit ratings, where observation is fully known.

6. PROPENSITY-WEIGHTED SVM-RANK

The paper instantiates propensity-weighted learning-to-rank as Propensity SVM-Rank, extending SVM-Rank with click-propensity information. It learns a linear query-document scoring function efficiently using propensity-scored clicked examples and IPS weights.

  • Method: Propensity-weighted LTR is instantiated as a concrete learning method based on SVM-Rank.The authors conjecture that analogous propensity-weighted versions of other LTR methods may also be derived.
  • Training Data: Each clicked query-result pair supplies a training example weighted by its estimated click propensity, alongside the query’s candidate result set.Candidate sets typically contain a few hundred documents selected by a stage-one ranker.
  • Scoring Function: Propensity SVM-Rank learns a linear scoring function f(x, y) = w·φ(x, y) for ranking query-result pairs.The feature vector describes the match between a query and a result.
  • Optimization: The optimization extends the conventional SVM-Rank objective with propensity-weighted slack constraints and regularization.The parameter C controls regularization and is typically selected by cross-validation.
  • Optimization: A one-slack formulation enables efficient quadratic-program optimization, implemented by modifying SVM-Rank to include IPS weights 1/qj.The evaluation compares this method with Naive SVM-Rank, which sets all propensities uniformly.

7. EMPIRICAL EVALUATION

Synthetic experiments vary click-data size, presentation bias, click noise, and propensity misspecification, then test the method on live search traffic. Propensity SVM-Rank benefits from more data and generally outperforms naive bias-ignoring training, with small-data variance and conservative misspecification as important qualifications.

  • Experimental design: The evaluation combines synthetic click-data experiments spanning bias, noise, and propensity misspecification with online interleaving experiments on an operational search engine.Synthetic data are derived from the Yahoo Learning to Rank corpus, while the real-world evaluation uses click logs from live traffic.
  • Training-set size: Propensity SVM-Rank approaches full-information Ranking SVM performance as click-data volume increases, whereas Naive SVM-Rank remains essentially flat.The naive method’s error is dominated by asymptotic bias, while propensity weighting leaves finite-sample variance that decreases with more data.
  • Presentation bias: Inverse propensity weighting is beneficial under substantial presentation bias, and five times more training data further improves Propensity SVM-Rank but not Naive SVM-Rank.The comparison varies η using n = 45K and n = 225K.
  • Click noise: As click noise rises to ϵ− = 0.3, with 59.8% of clicks on irrelevant documents, Propensity SVM-Rank increasingly outperforms Naive SVM-Rank.The unbiased empirical-risk estimate also allows Propensity SVM-Rank to benefit from additional data.
  • Propensity misspecification: Propensity SVM-Rank improves over naive training with conservative propensity misspecification, but underestimating small propensities can be harmful.Overestimating small propensities occurs when η < 1, while underestimation occurs when η > 1; clipping can provide a similar conservative adjustment.
  • Real-world experiment: Online interleaving experiments find that Propensity SVM-Rank significantly outperforms both the production ranker and Naive SVM-Rank on real click-log data.Reported two-tailed binomial sign-test values are p = 0.001 versus Prod and p = 0.006 versus Naive SVM-Rank.

8. CONCLUSIONS

The paper presents a theoretically sound framework for learning-to-rank under biased feedback and reports robustness across several distortions plus substantial retrieval improvements in live search.

  • The approach combines counterfactual modeling with propensity-weighted empirical risk minimization for learning-to-rank.
  • The resulting Propensity-Weighted Ranking SVM is robust to selection biases, noise, and model misspecification.
  • The live search-engine experiments show substantial retrieval improvements without heuristic or manual interventions during learning.

9. FUTURE RESEARCH

The paper identifies broader uses for propensity-weighted ERM, including general counterfactual LTR theory and bias correction for offline information-retrieval evaluation.

  • 9. FUTURE RESEARCH: The general counterfactual LTR model identifies components needed for learning under biased feedback and motivates improved propensity models.
  • 9. FUTURE RESEARCH: Propensity-weighted ERM could extend beyond Ranking SVM to pointwise and possibly listwise learning-to-rank methods.
  • 9. FUTURE RESEARCH: In manually annotated collections, propensity weighting may eliminate pooling bias because judgment sampling provides known, design-controlled propensities.
  • 9. FUTURE RESEARCH: Click-model propensities may improve the correlation between click-based metrics such as click-DCG and test-set DCG.
Loading 1608.04468v1…