PaperlayerView exact revision on arXiv

Source-linked AI summary

Unbiased Learning to Rank with Unbiased Propensity Estimation

Qingyao Ai, Keping Bi, Cheng Luo, Jiafeng Guo, W. Bruce Croft

arXiv:1804.05938v2cs.IR

TL;DR

Biased clicks make direct ranking training unreliable, and existing propensity estimation is separated from ranker learning. DLA jointly learns both models from raw clicks without offline parameter estimation or online result randomization, and its models significantly outperform randomized unbiased-learning and click-model baselines.

  • Problem

    Biased click data confound document relevance with presentation bias, while existing methods separately estimate propensity models using user randomization or offline procedures.

  • Method

    DLA jointly learns an unbiased ranking model and an unbiased propensity model directly from raw user clicks.

  • Results

    DLA significantly outperformed unbiased learning-to-rank algorithms based on result randomization and models trained with click-model relevance signals.

  • Takeaways & Limitations

    Jointly learning propensity and ranking models provides an automatic unbiased learning-to-rank framework applicable to online learning without result randomization.

Abstract

from arXiv · show

Learning to rank with biased click data is a well-known challenge. A variety of methods has been explored to debias click data for learning to rank such as click models, result interleaving and, more recently, the unbiased learning-to-rank framework based on inverse propensity weighting. Despite their differences, most existing studies separate the estimation of click bias (namely the \textit{propensity model}) from the learning of ranking algorithms. To estimate click propensities, they either conduct online result randomization, which can negatively affect the user experience, or offline parameter estimation, which has special requirements for click data and is optimized for objectives (e.g. click likelihood) that are not directly related to the ranking performance of the system. In this work, we address those problems by unifying the learning of propensity models and ranking models. We find that the problem of estimating a propensity model from click data is a dual problem of unbiased learning to rank. Based on this observation, we propose a Dual Learning Algorithm (DLA) that jointly learns an unbiased ranker and an \textit{unbiased propensity model}. DLA is an automatic unbiased learning-to-rank framework as it directly learns unbiased ranking models from biased click data without any preprocessing. It can adapt to the change of bias distributions and is applicable to online learning. Our empirical experiments with synthetic and real-world data show that the models trained with DLA significantly outperformed the unbiased learning-to-rank algorithms based on result randomization and the models trained with relevance signals extracted by click models.

W. Bruce Croft CICS, UMass Amherst

This paper was authored by Qingyao Ai, Keping Bi, Cheng Luo, Jiafeng Guo, and W. Bruce Croft. It appeared at SIGIR ’18 in 2018.

  • The paper is titled “Unbiased Learning to Rank with Unbiased Propensity Estimation.”
  • Qingyao Ai, Keping Bi, Cheng Luo, Jiafeng Guo, and W. Bruce Croft authored the paper.
  • The work appeared in SIGIR ’18, held July 8–12, 2018, in Ann Arbor, MI, USA.

1 INTRODUCTION

The introduction motivates learning from biased clicks and identifies limitations in separately estimating click bias and training rankers. It presents DLA as a joint, automatic approach using raw clicks without randomization or offline parameter estimation.

  • Large-scale, high-quality relevance judgments remain expensive or impossible, making user clicks an attractive training source despite their bias.
  • Position-biased clicks can make naive ranking models optimize result-page order rather than document relevance.
  • Click models estimate relevance from browsing assumptions, but are less suitable for tail queries and are optimized separately from ranking performance.
  • Result interleaving provides online feedback but introduces non-deterministic rankings that may hurt user experience.
  • Existing unbiased learning-to-rank methods require separate click-bias experiments, including result randomization that can affect users and requires separate system training.
  • DLA jointly learns propensity and ranking models from raw clicks, without result randomization or offline experiments, and is intended for production and online learning.

2 RELATED WORK

Related work divides biased-feedback methods into debiasing clicks before ranking and directly learning unbiased rankers. The paper reviews click models, randomized feedback methods, and inverse-propensity approaches.

  • Approaches to biased feedback either extract reliable relevance signals from clicks or directly learn unbiased rankers.
  • Click models represent user browsing behavior to separate relevance from click bias, but depend on behavioral assumptions and repeated observations.
  • Randomized ranked lists can reveal preferences between swapped documents, supporting online ranking-model training.
  • Result interleaving is not popular in practice because it can hurt ranking quality and introduce non-determinism into search engines.
  • Unbiased learning to rank estimates examination propensity through randomization and uses it to construct an unbiased ranking loss.

3 UNBIASED LEARNING TO RANK

Unbiased learning to rank corrects click-based losses with inverse propensity weighting so ranking can approach training with true relevance labels. The paper presents randomization-based propensity estimation and motivates jointly learning both models.

  • 3 UNBIASED LEARNING TO RANK: The unbiased learning-to-rank framework debiases click-based loss functions so the ranking model can converge toward one trained with true relevance labels.
  • 3 UNBIASED LEARNING TO RANK: Clicks are inexpensive but affected by presentation, trust, and position bias, so they must be debiased before ranking training.
  • 3.1 Inverse Propensity Weighting: Inverse propensity weighting uses a counterfactual model to remove click bias when optimizing ranking systems.
  • 3.1 Inverse Propensity Weighting: IPW computes loss only for documents that are both observed and relevant, avoiding assumptions about why a document was not clicked.
  • 3.1 Inverse Propensity Weighting: The click-trained ranking model with IPW converges to the model trained with true relevance labels, making the framework unbiased.
  • 3.2 Randomization-based Estimation: The key quantity is the propensity model P(o_x^q = 1|π_q), which this work assumes depends only on document position.
  • 3.2 Randomization-based Estimation: Result randomization shuffles documents and collects clicks across positions to estimate position-based propensities.
  • 3.2 Randomization-based Estimation: Because randomization can harm user experience and requires separate, time-consuming experiments, the paper proposes learning ranking and propensity models jointly from clicks.

4 OUR APPROACH

The paper formulates propensity estimation as the dual of unbiased learning to rank and proposes DLA, which jointly learns ranking and propensity models from click data. Its analysis describes the probability-based losses, iterative optimization, and convergence relationship between the two models.

  • Dual Learning Algorithm: DLA jointly learns an unbiased ranking model and propensity model from click data by solving unbiased learning-to-rank and propensity-estimation problems simultaneously.The method computes ranking and examination probabilities, losses, and parameter updates for both models in repeated batches.
  • Unbiased Propensity Estimation: The propensity model is learned with an inverse-relevance-weighted loss that is an unbiased estimate of its target loss.The paper applies inverse propensity-weighting logic symmetrically to propensity estimation.
  • Unbiased Propensity Estimation: Propensity estimation targets P(oxq = 1|πq), whereas unbiased learning to rank targets P(rxq = 1|πq), making the two estimation problems dual.Clicks require both observation and perceived relevance, so each model supplies information needed by the other.
  • Dual Learning Algorithm: Softmax-based cross entropy converts ranking and propensity scores into probability distributions used for relevance and propensity estimation.The approach uses list-wise losses because click-based pointwise losses observe only clicked, observed, and relevant documents.
  • Dual Learning Algorithm: The softmax assumption requires examination probabilities across ranked positions to sum to 1, although training remains effective when relative proportions are correct.The paper states that the predicted relevance and propensity values affect unbiased learning mainly through their relative proportions.
  • Convergence Analysis: With a fixed ranking model, the propensity loss is concave and converges to its global minimum; jointly, better unbiasedness in one model improves the other.The convergence analysis connects the quality of the ranker and propensity estimator through their inverse-weight relationships.

5 EXPERIMENTAL SETUP

The experiments evaluate DLA on synthetic Yahoo! LETOR clicks and real-world commercial search logs. They compare ranking models trained without correction, with randomized lists, and with click-model relevance signals using relevance-based evaluation.

  • Experiment Design: The study uses simulation on Yahoo! LETOR and a real-world experiment based on ranked lists and clicks from a commercial Web search engine.These two settings examine DLA under synthetic and observed click data.
  • Simulation Experiment Setup: Yahoo! LETOR contains 29,921 queries, 710k documents, five-level relevance judgments, and 700 selected features for the simulation study.Synthetic clicks are generated from initial ranked lists and simulated user browsing.
  • Simulation Experiment Setup: The simulation compares NoCorrect and RandList baselines with Ranking SVM and DNN ranking models, producing four baseline configurations.RandList estimates examination propensity from randomly shuffled results and 2 million click sessions.
  • Simulation Experiment Setup: Simulation models are trained on synthetic clicks sampled on the fly, with Ranking SVM and DNN hyperparameters tuned across stated ranges.The DNN is implemented with TensorFlow, while the Ranking SVM parameter c is tuned from 20 to 200 and hidden units from 128 to 512.
  • Evaluation: Evaluation uses MAP, nDCG, and ERR for simulation, while a separate 100-query test set receives five-level judgments from professional assessors.nDCG and ERR are reported at ranks 1, 3, 5, and 10 in the simulation evaluation.
  • Real-World Experiment Setup: Real-world data include 3,449 sampled queries, 71,106 ranked lists, 333,813 documents, and 3,268,177 anonymized click sessions.The collection uses two weeks of search logs and removes ranked lists containing uncrawlable documents.
  • Real-World Experiment Setup: Because real-user randomization was unavailable, the real-world comparison uses DNNs trained with relevance signals extracted by UBM and DBN click models.The final click-model baselines use the same other training settings as the simulation experiments.

6 RESULTS AND ANALYSIS

Experiments compare DLA with result-randomization and click-model approaches under stable and changing click-bias conditions. DLA estimates propensity more robustly across bias shifts and achieves strong ranking performance without separate randomization or click-model preprocessing.

  • 6.1 Comparison with Result Randomization: DLA and RandList are compared in Oracle Mode, where presentation bias remains unchanged between randomization and model training.The evaluation includes Initial Ranker and Oracle DNN references.
  • 6.1 Comparison with Result Randomization: Approximately 3% ERR@10 improvements were observed for Ranking SVM and DNN with RandList over models trained on raw clicks.These improvements demonstrate the effectiveness of inverse propensity weighting with result-randomization estimates.
  • 6.1 Comparison with Result Randomization: DLA performed similarly to or better than RandList for bias correction and was significantly better than other baselines, approaching the Oracle DNN.DLA achieved this without result randomization.
  • 6.1 Comparison with Result Randomization: When η differed from the randomization setting, RandList could under- or overestimate presentation bias and sometimes perform worse than NoCorrect.For η > 1, RandList remained better than NoCorrect but its relative improvement decreased; for η < 1, it performed worse than NoCorrect.
  • 6.1 Comparison with Result Randomization: RandList’s propensity MSE was small only at η = 1, whereas DLA’s MSE remained small across η values.The results indicate that DLA better approaches true presentation bias despite changes in η.
  • 6.2 Comparison with Click Models: DLA significantly outperformed DBN and UBM, achieving more than 10% improvement over both in ERR@10.The comparison used ranking models trained with DLA or click-model signals on real click data.
  • 6.2 Comparison with Click Models: Joint learning supports end-to-end optimization because click-likelihood optimization does not necessarily produce the best bias-correction model for unbiased ranking.In the experiments, DBN-trained rankers performed better than UBM-trained rankers despite UBM being better for click simulation.

7 CONCLUSION AND FUTURE WORK

The paper presents DLA as an automatic framework that jointly learns unbiased propensity and ranking models, with experiments supporting its effectiveness. It also identifies ranker quality as an important limitation for propensity estimation.

  • DLA jointly learns unbiased propensity models and ranking models from user clicks without offline parameter estimation or online result randomization.
  • The experiments characterize DLA as a theoretically principled and empirically effective framework for unbiased learning to rank.
  • Jointly learning propensity models and ranking models is identified as a fruitful direction for learning to rank with biased training signals.
  • DLA performance may be poor when the best available ranker has poor performance because propensity estimation depends on ranking-model quality.
Loading 1804.05938v2…