Identifiability Matters: Revealing the Hidden Recoverable Condition in Unbiased Learning to Rank

Mouxiang Chen, Chenghao Liu, Zemin Liu, Zhuo Li, Jianling Sun

Abstract

Unbiased Learning to Rank (ULTR) aims to train unbiased ranking models from biased click logs, by explicitly modeling a generation process for user behavior and fitting click data based on examination hypothesis. Previous research found empirically that the true latent relevance is mostly recoverable through click fitting. However, we demonstrate that this is not always achievable, resulting in a significant reduction in ranking performance. This research investigates the conditions under which relevance can be recovered from click data in the first principle. We initially characterize a ranking model as identifiable if it can recover the true relevance up to a scaling transformation, a criterion sufficient for the pairwise ranking objective. Subsequently, we investigate an equivalent condition for identifiability, articulated as a graph connectivity test problem: the recovery of relevance is feasible if and only if the identifiability graph (IG), derived from the underlying structure of the dataset, is connected. The presence of a disconnected IG may lead to degenerate cases and suboptimal ranking performance. To tackle this challenge, we introduce two methods, namely node intervention and node merging, designed to modify the dataset and restore the connectivity of the IG. Empirical results derived from a simulated dataset and two real-world LTR benchmark datasets not only validate our proposed theory but also demonstrate the effectiveness of our methods in alleviating data bias when the relevance model is unidentifiable.

Introduction: The Challenge of Biased Clicks

In modern information retrieval, click logs serve as a primary source of training data for ranking models due to their abundance and low cost. However, these logs are inherently biased; users are significantly more likely to click on top-ranked results regardless of their actual relevance—a phenomenon known as position bias.

To address this, Unbiased Learning to Rank (ULTR) methods typically employ the examination hypothesis. This hypothesis posits that a click occurs only if a user both observes a document and finds it relevant: $$P(\text{click}) = P(\text{observation} \mid \text{bias factors}) \times P(\text{relevance} \mid \text{ranking features})$$

While the field has long assumed that fitting click data accurately implies successful de-biasing, this paper demonstrates that such recovery is not guaranteed. A model can fit click data perfectly while failing to recover the true relevance, a state defined as being unidentifiable.

Theoretical Framework: The Identifiability Graph

The authors provide a first-principles theoretical framework to determine when relevance can be recovered. They introduce the Identifiability Graph (IG), where nodes represent "bias factors" (such as specific positions or user contexts). An edge is established between two nodes if the same document or feature set appears under both bias factors within the dataset.

The Identifiability Graph (IG) maps relationships between bias factors and document features. Connectivity in this graph is the necessary condition for recovering true relevance.

The core contribution is Theorem 1 (The Connectivity Condition): Relevance is identifiable (recoverable up to a scaling factor) if and only if the IG is connected. If the graph fragments into multiple "islands" (connected components), the model cannot distinguish between relevance and bias across those disparate groups, leading to degenerate ranking performance. This "sparsity trap" is particularly dangerous as models incorporate more complex features or contexts, which naturally fragments the data.

Restoring Identifiability: Node Intervention and Merging

To combat unidentifiability, the authors propose two distinct strategies:

  1. Node Intervention (Online): This method actively modifies data collection. By strategically swapping a minimal number of documents between different positions or contexts, the system "bridges" the islands in the IG. The authors use a Minimum Spanning Tree (MST) approach to ensure connectivity with the least possible impact on user experience.
  2. Node Merging (Offline): This model-agnostic approach is used when data collection cannot be changed. It forces the model to treat similar bias factors (e.g., adjacent positions like 9 and 10) as having identical observation probabilities. This effectively merges nodes in the IG, restoring connectivity at the cost of a small approximation error.

Key Results and Empirical Validation

The theory was validated using synthetic data, standard benchmarks (Yahoo! LETOR, Istella-S), and real-world click logs (TianGong-ST).

Empirical results showing (a) the performance drop in ranking accuracy (nDCG@10) when the graph is disconnected (K > 1) and (b) the effectiveness of Node Intervention (NI) and Node Merging (NM) in restoring relevance recovery (MCC).

As shown in the results, ranking performance is essentially binary based on connectivity. When the IG is connected ($K=1$), models achieve near-perfect relevance recovery. However, as soon as $K > 1$, performance (nDCG@10) becomes unstable and significantly lower, regardless of the volume of data collected. Furthermore, the proposed Node Intervention (NI) and Node Merging (NM) methods successfully restore high correlation with true relevance (MCC), even in highly disconnected scenarios.

Analysis of the real-world TianGong-ST dataset revealed nearly 3,000 disconnected components when accounting for vertical types and positions, suggesting that unidentifiability is a pervasive issue in industrial ranking systems.

Conclusion

This research highlights that identifiability is a critical, yet often overlooked, prerequisite for unbiased learning. By monitoring the connectivity of the Identifiability Graph, practitioners can diagnose potential failures in de-biasing and apply intervention or merging techniques to ensure their ranking models remain accurate and robust against extreme data bias.

Summary updated

Abstract

Unbiased Learning to Rank (ULTR) aims to train unbiased ranking models from biased click logs, by explicitly modeling a generation process for user behavior and fitting click data based on examination hypothesis. Previous research found empirically that the true latent relevance is mostly recoverable through click fitting. However, we demonstrate that this is not always achievable, resulting in a significant reduction in ranking performance. This research investigates the conditions under which relevance can be recovered from click data in the first principle. We initially characterize a ranking model as identifiable if it can recover the true relevance up to a scaling transformation, a criterion sufficient for the pairwise ranking objective. Subsequently, we investigate an equivalent condition for identifiability, articulated as a graph connectivity test problem: the recovery of relevance is feasible if and only if the identifiability graph (IG), derived from the underlying structure of the dataset, is connected. The presence of a disconnected IG may lead to degenerate cases and suboptimal ranking performance. To tackle this challenge, we introduce two methods, namely node intervention and node merging, designed to modify the dataset and restore the connectivity of the IG. Empirical results derived from a simulated dataset and two real-world LTR benchmark datasets not only validate our proposed theory but also demonstrate the effectiveness of our methods in alleviating data bias when the relevance model is unidentifiable.
BibTeX
@inproceedings{chen2024identifiability,
  author = {Mouxiang Chen and Chenghao Liu and Zemin Liu and Zhuo Li and Jianling Sun},
  title = {{Identifiability Matters: Revealing the Hidden Recoverable Condition in Unbiased Learning to Rank}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=JU3xHh1vWw},
}
Figure