Source-linked AI summary
Estimating Position Bias without Intrusive Interventions
Aman Agarwal, Ivan Zaitsev, Xuanhui Wang, Cheng Li, Marc Najork, Thorsten Joachims
TL;DR
Presentation bias makes implicit feedback an unreliable relevance signal, while counterfactual LTR requires accurate observation propensities. The paper estimates them by harvesting interventions from multiple historic rankers and combining them with the AllPairs estimator. It reports superior propensity estimation across real-world systems and robustness across simulated settings.
Problem
Presentation bias confounds relevance in implicit feedback, and counterfactual LTR requires observation propensities that must be estimated from user behavior.
Method
Intervention Harvesting uses historic logs from multiple ranking functions, while AllPairs combines the resulting intervention data for propensity estimation under the PBM.
Results
The method provides superior propensity estimation in two real-world search systems and remains robust across a wide range of simulated settings.
Takeaways & Limitations
Historic logs from multiple rankers can support consistent PBM propensity estimation without manual judgments, disruptive interventions, relevance models, or repeated queries.
Takeaways & Limitations
The approach estimates relative propensities under the Position-Based Propensity Model rather than unrestricted propensity curves.
Abstract
from arXiv · showhide
Presentation bias is one of the key challenges when learning from implicit feedback in search engines, as it confounds the relevance signal. While it was recently shown how counterfactual learning-to-rank (LTR) approaches \cite{Joachims/etal/17a} can provably overcome presentation bias when observation propensities are known, it remains to show how to effectively estimate these propensities. In this paper, we propose the first method for producing consistent propensity estimates without manual relevance judgments, disruptive interventions, or restrictive relevance modeling assumptions. First, we show how to harvest a specific type of intervention data from historic feedback logs of multiple different ranking functions, and show that this data is sufficient for consistent propensity estimation in the position-based model. Second, we propose a new extremum estimator that makes effective use of this data. In an empirical evaluation, we find that the new estimator provides superior propensity estimates in two real-world systems -- Arxiv Full-text Search and Google Drive Search. Beyond these two points, we find that the method is robust to a wide range of settings in simulation studies.
1 INTRODUCTION
The paper addresses presentation bias in implicit-feedback LTR by estimating position propensities from historic logs of multiple ranking functions. Its Intervention Harvesting approach and AllPairs estimator avoid manual judgments, disruptive interventions, restrictive relevance models, and repeated queries while achieving accurate, efficient estimates.
- 1 INTRODUCTION: The approach targets presentation bias because higher-ranked results are more likely to be discovered, confounding clicks with relevance.
- 1 INTRODUCTION: AllPairs combines intervention data from multiple ranking functions to estimate relative position propensities without intrusive online swaps or a relevance model.The method controls for relevance through naturally occurring rank differences and aggregates them for statistical efficiency.
- 1 INTRODUCTION: Intervention Harvesting uses historic feedback from different ranking functions as a natural intervention for controlling differences in result relevance across positions.
- 1 INTRODUCTION: AllPairs remains effective when rankers are similar, recovering global relative propensities even when most rank changes are small.
2 RELATED WORK
Prior work addresses biased click feedback through counterfactual methods, randomization, regression-based EM, and click models. This paper instead uses interventional techniques with the PBM while avoiding explicit relevance modeling and intrusive interventions.
- 2 RELATED WORK: Counterfactual LTR can be unbiased and consistent with biased feedback, but it requires estimating user-behavior propensities for IPS weighting.
- 2 RELATED WORK: Existing propensity estimators rely on randomization, minimally invasive interventions, or regression-based EM with relevance-model assumptions.
- 2 RELATED WORK: The paper controls for relevance explicitly without a relevance model while avoiding intrusive interventions.
- 2 RELATED WORK: Although the method is based on the PBM, it uses interventional techniques to infer propensities rather than generative modeling to infer relevance.
3 HARVESTING INTERVENTIONS
The paper harvests intervention data from historic logs of multiple ranking functions to estimate position propensities without repeating queries or imposing disruptive online swaps. Under a query-assignment condition, these interventional sets control for unobserved relevance and support consistent propensity estimation.
- Harvesting interventions: Historic logs from multiple ranking functions provide intervention data without requiring queries to occur multiple times.Interventional sets contain query-document pairs that different rankers place at different positions; only one factual outcome is observed, while the alternative is counterfactual.
- Swap interventions: Under the position-based model, randomly swapping a result between positions makes equal expected relevance isolate differences in examination probability.Swap interventions compare clicks when a result remains at position 1 with clicks after moving it to position k, so click-rate changes reflect examination differences.
- Swap interventions: Relative propensities can be estimated consistently from click-rate ratios as the sample size grows, and analogous estimates apply to any pair of positions.The randomized swap experiment provides a direct route to relative propensity estimation, but it can substantially degrade retrieval performance.
- Harvesting interventions: The method requires ranker assignment to be independent of the query distribution, a condition typically satisfied by randomized A/B tests.For sequential production rankers, temporal covariate shift must be considered because different rankers may receive different types of queries.
- Interventional sets: Interventional sets use ranker-induced position changes to control for unobserved relevance information when estimating propensities.For each position pair, the sets include cases where different ranking functions assign the same document to either position, while other placements are excluded.
4 PROPENSITY ESTIMATORS FOR INTERVENTIONAL SETS
The section introduces local and global estimators for relative propensities from interventional sets, culminating in AllPairs, which integrates information across all such sets.
- Local Estimators: PivotOne adapts the explicit Swap(1,k) estimator to interventional sets S1,k, while AdjacentChain uses a chain of adjacent-position comparisons.Both local estimators are consistent under mild conditions when each relevant interventional set has non-zero support.
- Global AllPairs Estimator: AllPairs addresses the local estimators’ limited information use by integrating data from every interventional set.It is designed as a global extremum estimator resembling a maximum-likelihood objective over all interventional sets.
- Local Estimators: The interventional click-count quantities have expectations proportional to click-through rates under the PBM, supporting consistent estimation under non-zero support.The relevant click counts concentrate to their expectations under the stated mild conditions.
- Global AllPairs Estimator: AllPairs estimates position propensities jointly with normalized pairwise relevance quantities using a weighted cross-entropy objective.The optimization uses O(M^2) variables, and normalized propensities are obtained as p_hat_k/p_hat_1 after discarding the relevance matrix.
5 EMPIRICAL EVALUATION
The evaluation combines real-world experiments on Arxiv Full-Text Search and Google Drive Search with simulations spanning varied settings such as ranker similarity.
- Evaluation Design: The evaluation uses two real-world search systems and simulation studies to assess practical effectiveness and behavior across varied settings.The simulations vary settings including the similarity of the ranking functions.
5.1 Real-World Evaluation: Arxiv Full-Text Search
The Arxiv evaluation compares AllPairs intervention harvesting with swap-based gold standards using concurrently collected feedback, finding similar propensity curves and tighter confidence intervals for AllPairs.
- Experimental Setup: The experiment used three ranking functions and constructed interventional sets across positions 1 through 21 from non-intervened rankings.The other half of incoming queries was assigned to a uniformly selected ranking function without further intervention.
- Experimental Setup: The gold-standard condition randomly swapped rank 1 with rank k for k from 1 to 21 on half of the assigned queries.The swap experiment used ranking functions selected uniformly at random and produced the reference estimates.
- Experimental Setup: About 53,000 queries and 25,600 clicks were collected concurrently, split approximately evenly between swap and intervention-harvesting conditions.The concurrent collection was intended to avoid confounding from shifts in the query distribution.
- Results: AllPairs mostly lies within the gold-standard curve’s 95% confidence interval while producing substantially tighter intervals.This indicates lower uncertainty for AllPairs at the same query volume, alongside avoiding swap interventions.
- Results: Only 7.39% of documents received the same rank from all three rankers, so about 93% contributed to an interventional set for AllPairs.The ranking functions had similar ranking accuracy but frequently assigned documents to different positions.
5.2 Real-World Evaluation: Google Drive Search
On Google Drive Search, Intervention Harvesting with AllPairs closely matches gold-standard propensity estimates despite limited ranker differences, outperforming regression EM and naive CTR estimates.
- Intervention Harvesting: The Google Drive A/B test assigned users to production ranker f1 or new ranker f2, producing interventional sets for AllPairs across the top five positions.The service displays at most five results per query and logs each displayed result with its position.
- Results: AllPairs estimates closely resemble the gold-standard swap experiment and outperform regression EM and naive CTR estimates on Google Drive.The experiment collected 877,689 queries; the gold-standard data came from a different time and ranking function.
- Results: The two rankers had identical top-five rankings for 75.26% of queries, while 74.5% of results remained at the same rank among differing rankings.Thus, Google Drive supplied relatively limited intervention data compared with substantially different rankers.
5.3 Robustness Analysis: Yahoo LTR Challenge
Synthetic Yahoo LTR experiments show that AllPairs recovers true propensities and remains effective across data volume, ranker similarity, noise, steepness, and logging imbalance, though extreme settings increase error.
- True Propensity Recovery: AllPairs perfectly recovers the true propensity curve in the default synthetic experiment.The experiment uses Yahoo LTR data with known propensities and reports 99% confidence intervals from repeated simulations.
- Convergence: AllPairs provides good estimates with modest data, while AdjacentChain requires at least one order of magnitude more data to achieve the same MSE.PivotOne was explored but typically performed worse than AdjacentChain.
- Ranker Similarity: AllPairs remains robust as rankers become increasingly similar, although error rises when rankers are extremely similar or dissimilar.Identical rankers yield no harvested intervention data, while highly dissimilar rankers can produce interventions beyond the estimated top 10 positions.
- Data Conditions: AllPairs substantially improves over AdjacentChain across varying training-set sizes and remains robust to imbalanced log volumes between rankers.The imbalance experiment keeps total data fixed at 119,664 queries.
- Noise and Propensity Shape: AllPairs estimates remain stable across levels of click noise, but both estimators show sharply higher MSE when the propensity curve becomes steep.Steep curves create small propensities, large inverse propensities, and sparse clicks at lower ranks.
6 CONCLUSION
The paper introduces Intervention Harvesting and the AllPairs estimator for consistent PBM propensity estimation from historic logs without intrusive interventions, relevance models, or repeated queries.
- Contribution: Intervention Harvesting uses multiple historic rankers to generate interventional data under mild assumptions.The approach controls for relevance differences between positions using feedback from different ranking functions.
- Contribution: AllPairs combines harvested intervention data and provides superior propensity-estimation accuracy to existing local estimators across a wide range of settings.The method does not require intrusive interventions, a relevance model, or repeated queries.