A General Framework for Counterfactual Learning-to-Rank

Aman Agarwal, Kenta Takatsu, Ivan Zaitsev, Thorsten Joachims

TL;DR

This paper introduces a general framework for learning to rank (LTR) from implicit user feedback (like clicks) that overcomes presentation bias. It extends previous work to handle a wider range of ranking metrics (like DCG) and allows for non-linear ranking models (like deep networks), leading to improved performance over existing methods.

What Problem Does This Paper Address?

Information retrieval systems often rely on implicit user feedback, such as clicks or dwell times, to learn how to rank search results. However, this feedback is inherently biased: a result's position in the ranking strongly influences whether it gets clicked. Naively using this biased data leads to suboptimal ranking performance. While previous work has addressed this "presentation bias" for specific LTR metrics and linear models, this paper tackles the broader challenge of developing a unified, theoretically sound framework that can handle a wider class of ranking metrics and more complex, non-linear ranking models like deep neural networks.

Methods

The core of the paper is a counterfactual inference framework that uses Inverse Propensity Score (IPS) weighting. This technique re-weights the observed feedback data to correct for the bias introduced by the presentation order.

Key methodological contributions include:

  • Generalization of Counterfactual LTR: The framework is extended to optimize a broad class of linearly decomposable additive ranking metrics, which includes metrics like Discounted Cumulative Gain (DCG) beyond the previously supported Average Rank.
  • Subdifferentiable Relaxation: For gradient-based optimization, the paper derives a subdifferentiable relaxation for propensity-weighted rank-based metrics.
  • SVM PropDCG: A new learning method that optimizes a bound on DCG using a linear scoring function. This method uses the Convex Concave Procedure (CCP) to find a local optimum for the non-convex optimization problem.
  • Deep PropDCG: This method extends the framework to non-linear scoring functions implemented as deep neural networks. It uses stochastic gradient descent (SGD) to train the network, leveraging the subdifferentiable objective.

Datasets

The paper uses two benchmark datasets for evaluation:

  • Yahoo Learning to Rank Challenge corpus: A standard dataset for LTR research.
  • LETOR4.0: This includes MQ2007 and MQ2008 corpora. For consistency and reproducibility, the MQ2007 and MQ2008 training sets are combined, and MQ2008 is used for validation and testing.

The click data used for training and evaluation is synthetically generated from these full-information datasets by simulating a position-based click model. This allows for controlled experiments with varying levels of presentation bias and noise.

Key Insights and Ideas

  • Unified Framework for Bias Correction: The paper provides a significant theoretical step towards a general solution for learning from biased implicit feedback across various ranking metrics and model types.
  • DCG Optimization is Key: Directly optimizing DCG (or similar metrics) leads to better performance than optimizing Average Rank, especially in the presence of presentation bias.
  • CCP for Non-Convexity: The Convex Concave Procedure is an effective way to handle the non-convex optimization problems that arise when optimizing metrics like DCG with linear models.
  • Deep Networks Leverage the Framework: The counterfactual framework is not limited to linear models; it can effectively train deep neural networks for LTR, further boosting performance.
  • Implicit Variance Control: The DCG weighting in SVM PropDCG appears to offer implicit variance control, making it more robust than SVM PropRank in certain scenarios, particularly with smaller datasets.

Key Results

  • SVM PropDCG outperforms SVM PropRank: On both Yahoo and LETOR4.0 datasets, SVM PropDCG achieved significantly better DCG performance than SVM PropRank, demonstrating the benefit of directly optimizing DCG.
  • Deep PropDCG shows further improvement: The deep network version, Deep PropDCG, further improved DCG performance over SVM PropDCG, especially with sufficient training data.
  • Robustness to Bias and Noise: SVM PropDCG showed comparable or better robustness to presentation bias severity, noise, and propensity model misspecification compared to SVM PropRank.
  • Efficient CCP Convergence: The CCP optimization for SVM PropDCG typically converged within 3-5 iterations, indicating practical efficiency.
  • LambdaRank Comparison: Both SVM PropDCG and Deep PropDCG outperformed LambdaRank in terms of DCG.

Limitations and Future Work

  • Non-linear Model Performance: While Deep PropDCG showed improvement, the paper used a simple two-layer network. The authors conjecture that more sophisticated deep architectures could yield even better results.
  • Hyperparameter Tuning: The Deep PropDCG experiments used default parameters, suggesting that further tuning could enhance its performance.
  • Generalizability to Other Metrics: The paper's framework is general, but developing efficient and effective methods for other ranking metrics remains an open question.
  • Beyond Ranking: The counterfactual learning approach might be applicable to other domains like full-page optimization or browsing-based retrieval.
  • Non-Differentiable Models: Extending the counterfactual framework to non-differentiable ranking models (e.g., tree-based models) is a future research direction.

Summary updated

Abstract

Implicit feedback (e.g., click, dwell time) is an attractive source of training data for Learning-to-Rank, but its naive use leads to learning results that are distorted by presentation bias. For the special case of optimizing average rank for linear ranking functions, however, the recently developed SVM-PropRank method has shown that counterfactual inference techniques can be used to provably overcome the distorting effect of presentation bias. Going beyond this special case, this paper provides a general and theoretically rigorous framework for counterfactual learning-to-rank that enables unbiased training for a broad class of additive ranking metrics (e.g., Discounted Cumulative Gain (DCG)) as well as a broad class of models (e.g., deep networks). Specifically, we derive a relaxation for propensity-weighted rank-based metrics which is subdifferentiable and thus suitable for gradient-based optimization. We demonstrate the effectiveness of this general approach by instantiating two new learning methods. One is a new type of unbiased SVM that optimizes DCG - called SVM PropDCG - and we show how the resulting optimization problem can be solved via the Convex Concave Procedure (CCP). The other is Deep PropDCG, where the ranking function can be an arbitrary deep network. In addition to the theoretical support, we empirically find that SVM PropDCG significantly outperforms existing linear rankers in terms of DCG. Moreover, the ability to train non-linear ranking functions via Deep PropDCG further improves performance.
BibTeX
@inproceedings{agarwal2019general,
  author = {Aman Agarwal and Kenta Takatsu and Ivan Zaitsev and Thorsten Joachims},
  title = {{A General Framework for Counterfactual Learning-to-Rank}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2019},
  doi = {10.1145/3331184.3331202},
}
Figure