Source-linked AI summary
A General Framework for Counterfactual Learning-to-Rank
Aman Agarwal, Kenta Takatsu, Ivan Zaitsev, Thorsten Joachims
TL;DR
Implicit feedback is plentiful but presentation bias can distort learning-to-rank, and earlier counterfactual guarantees covered a narrower setting. This paper generalizes counterfactual training to additive metrics and deep models, then reports improved DCG for its methods over existing rankers.
Problem
Naively treating clicks as relevance signals can distort learning because result position affects whether users see and click them.
Source: §1 · p. 1Method
The paper develops propensity-weighted counterfactual LTR with a hinge-loss upper bound, instantiating SVM PropDCG with CCP and Deep PropDCG with stochastic gradient descent.
Source: §1 · p. 1, §4 · p. 3, §4.1 · p. 4Results
SVM PropDCG outperforms SVM PropRank and LambdaRank on DCG, and Deep PropDCG further improves DCG over SVM PropDCG.
Source: §1 · p. 2, §5.2 · p. 7, §6 · p. 9Takeaways & Limitations
The reported results support using the counterfactual approach to train non-linear ranking functions and improve DCG beyond the linear SVM PropDCG method.
Source: §1 · p. 2, §6 · p. 9Whether the framework yields efficient and effective methods for other ranking metrics or can train non-differentiable models such as tree-based rankers remains open.
Source: §6 · p. 9
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The paper extends counterfactual learning-to-rank beyond linear models and average rank to additive ranking metrics and deep models. It develops two DCG-optimizing methods and reports improved performance over existing rankers.
1 INTRODUCTION
- The framework extends counterfactual LTR to additive metrics and non-linear deep models, using propensity-weighted ERM and a hinge-loss bound for monotone rank weights.The bound supports gradient-based learning for a broad class of models.Source: §1 · p. 1
- SVM PropDCG optimizes a DCG bound for linear rankers using CCP, whose convex subproblems can be solved with a fast SVM solver.The subproblems are quadratic programs, and convergence was typically reached within three to five iterations.Source: §1 · pp. 1–2
- Deep PropDCG optimizes a DCG bound with stochastic gradient descent for deep networks that share weights across candidate documents for a query.The reported neural-network results improve DCG further than SVM PropDCG.Source: §1 · p. 2
- SVM PropDCG and Deep PropDCG outperform SVM PropRank and LambdaRank on DCG, with Deep PropDCG further improving on SVM PropDCG.SVM PropDCG is also reported robust to bias, noise, and propensity-model misspecification.Source: §1 · p. 2
2 RELATED WORK
Prior work addresses bias in implicit feedback with click models and counterfactual methods, while other approaches optimize smoothed ranking metrics in supervised settings. This paper's approach is positioned as a way to directly optimize target metrics and accommodate varied network architectures.
2 RELATED WORK
- Cascade click models infer preferences from clicked and skipped documents, while other models use repeated queries to infer latent relevance from clicks.The counterfactual framework [15] avoids repeat queries and latent-variable inference while directly incorporating click feedback.Source: §2 · p. 2
- Inverse propensity score weighting has been used in survey sampling, causal inference, whole-page optimization, IR evaluation [25], and recommender evaluation [17] [26].Related work also applies propensity weighting to selection bias from discarding queries without clicks.Source: §2 · p. 2
- Joint propensity estimation and ranking methods [2] require an accurate relevance model, while separating propensity estimation from ranker training permits choosing the target metric independently.The passage continues this point by stating that target-metric choice is independent of the propensity-estimation step.Source: §2 · p. 2
- Table 1 presents some popular linearly decomposable IR metrics directly optimizable by Propensity-Weighted ERM, and defines λ(r) as the rank-weighting function.In full-information supervised learning, SoftRank and others use smoothed ranking metrics; SoftRank's expected metric over rankings induced by normally distributed scores has O(n3) dependence on documents per query. By contrast, the paper uses an upper bound amenable to efficient Convex Concave Procedure optimization and adaptable to nonlinear ranking functions via deep networks.Source: Table 1 · p. 2, §2 · p. 2
- The paper proposes a training criterion rather than a specific neural architecture, aiming to support unbiased implicit-feedback training across many architectures.The related-work discussion notes prior neural learning-to-rank architectures.Source: §2 · p. 2
3 UNBIASED ESTIMATION OF RANK-BASED IR METRICS
This section defines additive ranking metrics and the risk of a ranking system, then addresses unobserved relevance in implicit feedback. It uses inverse propensity weighting to estimate metric loss from observed positive feedback under a positivity condition.
3 UNBIASED ESTIMATION OF RANK-BASED IR METRICS
- Additive ranking metrics sum document relevance weighted by rank, with average rank and DCG as examples of rank-weight choices.The weighting function may depend on rank; the paper uses negative values where needed to express the metric as a risk to minimize.Source: §3 · pp. 2–3
- A ranking system maps each query instance to a ranking, and its overall risk aggregates individual ranking losses over the query distribution.The risk can represent expected DCG.Source: §3 · p. 3
- Because missing clicks may reflect either irrelevance or lack of observation, the method models which relevance values are revealed and defines their observation propensity.Propensities are generally unknown and must be estimated using a user-behavior model.Source: §3 · p. 3
- Inverse propensity weighting yields an unbiased metric-loss estimate when every relevant result has a positive observation propensity.The estimator sums only over observed, positive feedback, so it need not distinguish an unclicked result that was irrelevant from one that was not observed.Source: §3 · p. 3
4 UNBIASED EMPIRICAL RISK MINIMIZATION FOR LTR
The section turns propensity-weighted empirical risk minimization into a theoretically justified, tractable framework for additive ranking metrics, including DCG. It develops a linear SVM method optimized with CCP and a deep-network method trained with stochastic gradient descent.
4 UNBIASED EMPIRICAL RISK MINIMIZATION FOR LTR
- The propensity-weighted risk estimate is unbiased and, under standard uniform convergence conditions, yields consistency: with enough data, learning finds the best system in the hypothesis class.A hinge-loss upper bound makes the objective continuous and subdifferentiable for rank-based metrics with monotonically increasing rank weights.Source: §4 · pp. 3–4
4.1 SVM PropDCG
- SVM PropDCG optimizes a DCG bound for linear scoring functions using CCP, which solves a convex quadratic program at each iteration.The subproblems have the form of generalized Ranking SVM and can use the fast SVM PropRank solver; CCP converges to a local optimum.Source: §4.1 · pp. 4–5
- Kernelizing SVM PropDCG is computationally challenging because its kernel matrix scales with the square of the total number of candidates across training examples.This motivates the paper’s alternative route to nonlinear ranking functions: deep networks.Source: §4.1 · p. 5
4.2 Deep PropDCG
- Deep PropDCG replaces the linear scorer with a neural network and applies shared network weights to candidate documents, combining clicked-versus-other hinge losses before applying the rank-weighting function.The framework is agnostic to network architecture; its training objective is subdifferentiable when the weighting function is differentiable, and query-level SGD gives unbiased gradient estimates without alternating approximations.Source: §4.2 · pp. 5–6
5 EMPIRICAL EVALUATION
The evaluation compares counterfactual methods with conventional rankers, tests robustness to feedback and propensity-model conditions, and examines whether nonlinear models improve DCG. It uses synthetic clicks from two ranking benchmarks, with validation based on an IPS DCG estimate and final evaluation on fully labeled test data.
5 EMPIRICAL EVALUATION
- The evaluation asks whether direct DCG optimization improves over baseline rankers, whether the approach is robust to noisy feedback, bias severity, and propensity-model misspecification, and whether Deep PropDCG improves on linear SVM PropDCG.The SVM PropDCG–SVM PropRank comparison is designed to isolate direct DCG optimization because both are linear SVMs using the same software machinery.Source: §5 · p. 6
5.1 Setup
- Synthetic click data were generated from Yahoo Learning to Rank Challenge and LETOR4.0; MQ2007 and MQ2008 training sets were combined, with MQ2008 validation and test sets used for those benchmarks.Clicks were simulated with a position-based model; higher η means stronger position bias, and irrelevant-document clicks added noise.Source: §5.1 · p. 6
- Models were selected using validation clicks and an IPS estimate of DCG, then evaluated on binarized fully labeled test data that was not used for training or validation.The experiments repeated training runs six times and report average performance with standard deviations.Source: §5.1 · p. 6
5.2 How do SVM PropDCG and Deep PropDCG compare against baselines?
The evaluation compares counterfactual rankers with conventional baselines, and Deep PropDCG achieves the best results on both benchmarks. The figures cover test-set DCG and average-rank performance, including performance under increasing presentation bias.
5.2 How do SVM PropDCG and Deep PropDCG compare against baselines?
- The evaluation compares counterfactual methods with conventional ERM baselines, including LambdaRank, a tree-based ranker trained with clicks as relevance labels.LambdaRank's learning rate and number of leaves were tuned on validation data.Source: §5.2 · pp. 6–7
- Figures 2–4 report test-set average DCG or average-rank performance for SVM PropDCG and SVM PropRank, including results as presentation bias increases.Figure 4 covers training sets of 45K and 225K examples with ϵ− = 0.Source: Figure 2 · p. 7, Figure 3 · p. 7, Figure 4 · p. 7
- Deep PropDCG achieves the best results on both benchmarks, using a two-layer neural network ranker.The authors conjecture that more sophisticated network architectures can further improve performance.Source: §5.2 · p. 7
5.3 How does ranking performance scale with training set size?
With more click data, both counterfactual rankers improve in test-set DCG, and SVM PropDCG performs substantially better than SVM PropRank on that metric. Their average-rank comparison is closer and changes with training-set size.
5.3 How does ranking performance scale with training set size?
- The learning curves use click data with η = 1 and ϵ− = 0.1; small-dataset results are averaged over three draws.The curves also show the production ranker and an SVM skyline trained on the full-information training set.Source: §5.3 · p. 7
- SVM PropDCG performs substantially better than SVM PropRank in maximizing test-set DCG as click-data volume increases.Both methods improve with increasing amounts of click data.Source: §5.3 · p. 7
- For average rank, the methods perform comparably: SVM PropDCG is slightly better with less data, while SVM PropRank is better with more.The authors conjecture that DCG weights limit variance in SVM PropDCG, consistent with the observed trend.Source: §5.3 · p. 7
5.4 How much presentation bias can be tolerated?
SVM PropDCG is at least as robust as SVM PropRank to increasing presentation bias and noise in the reported tests. Both methods’ DCG performance degrades as noise increases.
5.4 How much presentation bias can be tolerated?
- The bias-severity test varies η, with higher values producing click propensities more skewed toward top positions.The reported DCG comparison uses two training-set sizes that differ by a factor of five and has ϵ− = 0.Source: §5.4 · pp. 7–8
- SVM PropDCG is at least as robust as SVM PropRank to presentation-bias severity, and SVM PropRank degrades more at high bias.Increasing training data fivefold improves both methods’ performance, which the authors attribute to variance reduction.Source: §5.4 · pp. 7–8
5.5 How robust is SVM PropDCG to noise?
- As noise ϵ− increases from 0 to 0.3, both methods’ DCG performance degrades; there is no evidence SVM PropDCG is less robust.At ϵ− = 0.3, 59.8% of clicks are on irrelevant documents.Source: §5.5 · p. 8, Figure 5 · p. 8
5.6 How robust is SVM PropDCG to misspecified propensities?
SVM PropDCG is at least as robust as SVM PropRank to propensity misspecification, although both degrade considerably in the high-bias regime when small propensities are underestimated. Its CCP objective typically converges in three to five iterations and tracks the training DCG estimate.
5.6 How robust is SVM PropDCG to misspecified propensities?
- The misspecification evaluation addresses the practical setting where propensities must be estimated and are subject to modeling assumptions.The test data uses η = 1, while the learning propensities are misspecified according to η on the x-axis.Source: §5.6 · p. 8
- SVM PropDCG is at least as robust as SVM PropRank to misspecified propensities and performs better when misspecification underestimates them.Both methods degrade considerably in the high-bias regime when small propensities are underestimated.Source: §5.6 · p. 8
5.7 How well does the CCP converge?
- CCP repeatedly solves convex subproblems using the SVM PropRank solver until the SVM PropDCG objective converges.Because only the quadratic-program coefficients change, the optimizer can be warm-started and the data need not be reloaded in later iterations.Source: §5.7 · p. 8
- The CCP objective usually converges in 3–5 iterations, and its progress is well-tracked by the training DCG estimate.This pattern was also observed for other training-data amounts.Source: §5.7 · p. 8
5.8 When does the non-linear model improve over the linear model?
Deep PropDCG improves DCG over linear SVM PropDCG with enough training data, while the linear model performs better with small amounts. The section explores this comparison using a simple neural network, rather than focusing on a particular deep architecture.
5.8 When does the non-linear model improve over the linear model?
- The comparison tests whether neural nonlinearity can improve on SVM PropDCG, which the authors describe as robust across bias and noise levels.The section frames the neural-network experiment as a possible further performance improvement.Source: §5.8 · p. 8
- Figure 7 tracks objective value and training-set DCG across CCP iterations for different regularization constants C.The caption specifies n = 17K, η = 1, and ϵ− = 0.1.Source: Figure 7 · p. 9
- The experiment uses a two-layer neural network with 200 hidden units and sigmoid activation, while specialized deep architectures are expected to improve performance further.The authors emphasize that the paper's focus is a novel training objective, not a specific deep architecture.Source: §5.8 · pp. 8–9
- With enough training data, Deep PropDCG achieves improved DCG over linear SVM PropDCG, but the linear model performs better with small amounts.The passage attributes the small-data result to linear models' greater robustness to overfitting.Source: §5.8 · p. 9, Figure 8 · p. 9
- Deep PropDCG uses default hyperparameters, whereas SVM PropDCG hyperparameters were optimized on the validation set.The Deep PropDCG settings were held fixed across training-data amounts, and no other settings were tried.Source: §5.8 · p. 9
6 CONCLUSION
The paper generalizes counterfactual learning-to-rank to additive IR metrics and nonlinear deep models, then develops SVM PropDCG and Deep PropDCG for optimizing DCG. It reports improved DCG over SVM PropRank, robustness and efficient optimization for SVM PropDCG, and further improvement with Deep PropDCG; other metrics and model types remain open questions.
6 CONCLUSION
- The framework covers a broad class of additive IR metrics and nonlinear deep network models.The conclusion identifies other ranking metrics and non-ranking settings as directions for further work.Source: §6 · p. 9
- SVM PropDCG optimizes DCG via CCP, while Deep PropDCG uses stochastic gradient descent; empirically, SVM PropDCG outperforms SVM PropRank and Deep PropDCG improves DCG further.The conclusion also reports SVM PropDCG's robustness to presentation bias, noise, and propensity misspecification, and says it can be optimized efficiently.Source: §6 · p. 9
- Efficient methods for other ranking metrics, applications beyond ranking, and training non-differentiable models such as tree-based rankers remain open questions.The conclusion gives full-page optimization and browsing-based retrieval as examples of settings beyond ranking.Source: §6 · p. 9