Intervention Harvesting for Context-Dependent Examination-Bias Estimation

Zhichong Fang, Aman Agarwal, Thorsten Joachims

TL;DR

Learning-to-rank systems heavily rely on click data, but clicks are notoriously biased by a result's position. This paper introduces the Contextual Position-Based Model (CPBM) to estimate examination bias based on specific query and user contexts, rather than just rank. To train it without degrading the user experience via random result swapping, the authors propose an "AllPairs" estimator that cleverly harvests natural variations in historical logs from past A/B tests.

What Problem Does This Paper Address?

In search engines and recommender systems, implicit feedback (like clicks) is abundant but biased. A user is much more likely to click the #1 result than the #10 result, simply because they examine the top of the page first—not necessarily because the #1 result is better. To fix this, researchers use Inverse Propensity Scoring (IPS), which weights clicks by the inverse of the probability that the user actually examined that position.

Traditionally, this examination probability is estimated using a Position-Based Model (PBM), which assumes that the examination drop-off curve is identical for all queries. But human behavior isn't that uniform. A user typing a highly specific navigational query might only look at the first result, while a user doing exploratory research might scroll through page two. Furthermore, estimating these biases accurately usually requires "swap interventions" (randomly swapping the order of search results to see how clicks change), which actively hurts the user's search experience. This paper tackles both limitations: it models context-dependent bias and estimates it without disruptive interventions.

Methods

The authors propose two major contributions: a new model and a new way to train it.

  1. Contextual Position-Based Model (CPBM): Instead of a single propensity score for each rank, the CPBM calculates examination probability based on both the rank $k$ and a context vector $x$. This context can include query features (e.g., query length, use of boolean operators) and user features.
  2. Intervention Harvesting with the AllPairs Estimator: To avoid randomizing search results, the authors exploit "implicit interventions" already present in system logs. If a search engine runs an A/B test with two different ranking algorithms, Algorithm A might place Document 1 at rank 1, while Algorithm B places it at rank 3. This natural variation acts as a free intervention, controlling for the document's actual relevance.
  3. Neural Network Architecture: The AllPairs estimator uses these harvested interventions to train two Multi-Layer Perceptrons (MLPs) via a weighted cross-entropy objective. One MLP predicts the context-dependent examination propensity, and the other predicts the average relevance of documents at a given position for that context.

Datasets

  • ArXiv Full-Text Search: A real-world dataset of 138,600 queries and 112,000 clicks collected from the ArXiv search engine. The authors ran actual swap interventions to establish a "gold standard" propensity curve, and used parallel A/B test data to evaluate their intervention harvesting approach.
  • Yahoo Learning-To-Rank Challenge (Set 1): Used for semi-synthetic experiments. The authors trained two different SVM-Rank models to generate synthetic click logs, allowing them to rigorously test the robustness, data efficiency, and downstream ranking performance of their estimator against known ground truths.

Key Insights and Ideas

  • Context absolutely matters: The ArXiv experiments proved that propensity curves vary significantly by query type. "Complex" queries (using boolean operators like AND/OR) showed a much steeper drop-off in examination at lower ranks compared to "simple" queries.
  • You don't need to ruin UX to get unbiased data: The intervention harvesting technique successfully matched the accuracy of explicit swap interventions. By just looking at how different historical rankers treated the same documents, systems can learn complex bias models for free.
  • Relevance modeling can be lightweight: Generative click models usually fail because they try to learn the exact relevance of every single query-document pair—a massive task. Because the AllPairs estimator uses interventions to control for specific document relevance, its neural network only needs to learn how average relevance changes with context, which is vastly easier to optimize.

Key Results

  • Massive Error Reduction: On the Yahoo LTR dataset, the CPBM reduced the relative error of propensity estimates by 64.6% compared to the standard PBM baseline (dropping from 0.478 to 0.169).
  • Better Downstream Ranking: When the CPBM's propensity scores were plugged into an unbiased learning-to-rank algorithm (Propensity SVM-Rank), the resulting ranking performance (AvgRank) closely matched the theoretical gold standard (a model trained with perfect, oracle propensities).
  • High Data Efficiency: The CPBM doesn't need millions of logs to work. In the synthetic experiments, the model's relative error plummeted and asymptoted after only about 5,700 training queries.

Limitations and Future Work

  • Relevance Model Impact: The authors noted that adding the context-dependent average relevance MLP only provided a mild improvement (a 0.02 decrease in error) over using simple, context-independent parameters. This suggests the relevance model might be over-engineered for the task.
  • Future Architectures: The current CPBM outputs a vector of propensities for all positions at once. The authors suggest future work could explore Recurrent Neural Networks (RNNs) to better model the sequential, top-down nature of how users actually scan results, or embedding the rank position directly as an input feature to the network.

Summary updated

Abstract

Accurate estimates of examination bias are crucial for unbiased learning-to-rank from implicit feedback in search engines and recommender systems, since they enable the use of Inverse Propensity Score (IPS) weighting techniques to address selection biases and missing data. Unfortunately, existing examination-bias estimators are limited to the Position-Based Model (PBM), where the examination bias may only depend on the rank of the document. To overcome this limitation, we propose a Contextual Position-Based Model (CPBM) where the examination bias may also depend on a context vector describing the query and the user. Furthermore, we propose an effective estimator for the CPBM based on intervention harvesting. A key feature of the estimator is that it does not require disruptive interventions but merely exploits natural variation resulting from the use of multiple historic ranking functions. Real-world experiments on the ArXiv search engine and semi-synthetic experiments on the Yahoo Learning-To-Rank dataset demonstrate the superior effectiveness and robustness of the new approach.
BibTeX
@inproceedings{fang2019intervention,
  author = {Zhichong Fang and Aman Agarwal and Thorsten Joachims},
  title = {{Intervention Harvesting for Context-Dependent Examination-Bias Estimation}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2019},
  doi = {10.1145/3331184.3331238},
}

Loading related content...

Figure