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