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

Summary

The submission studies the identifiability problem of unbiased learning to rank (ULTR) - given a dataset of implicit feedback, whether the true relevance can be identified or not. By treating each bias configuration as a node, and the shared input feature vector for the edges, the relevance model is identifiable if and only if the graph is connected. Then two methods are proposed to try to address the issues (making the graph connected). Experiments are conducted on two synthetic datasets and an offline dataset, where it shows that using the two methods to change data can improve the performance of a naive baseline.

Strengths

It is interesting to study the identifiability problem of unbiased learning to rank from the graph connectivity perspective, though the reviewer is not convinced that this is "the first work" to study the identifiability issue given existing work on coupling / confounding, etc. The major novelty seems to be the graph view. The proposed two methods are easy to understand. The authors do acknowledge the caveats of the proposed methods (one being not very practical and one may propagate errors). The paper is overall clearly written.

Weaknesses

Overall the paper is not satisfactory in term of theories or experiments. Though the theorems look interesting at first glance, the reviewer feels they are generally not very solid or practical after a closer look at them. A major issue is the reviewer feels the submission has self-contradictions in several places. So there are two scenarios in practice: 1) there are a lot of data, and the bias factor space is small. This is the a common case in practice and people are just fine without worrying about identifiability. The analysis and methods in this paper mostly do not apply since the graph is small and likely connected. 2) There are a lot of bias factors and the graph is more likely to be not connected. The paper mainly argues about this scenario. So far so good and it is ok to focus on 2). However, by closing look at each theorem, all of them are questionable and some look contradictory to the focus/motivation: Theorem1: while the trend of using more bias factors is the trend is debatable (especially given existing work showing the coupling / confounding effect), the trend to enrich x is clear. Many real-world applications have personalized feature vectors - then the graph is not likely to be connected even with a small number of bias factors. The paper does not concern this perspective, also, people are fine working with ULTR with such datasets. This questions the value of the proposed framework - one should also note that the condition is only a sufficient condition. Theorem 2: The assumptions are too strong to make meaningful value from this theorem. The reviewer understands this is to show a simplified “estimate”, but still the value is quite limited for this highly practical field. Theorem 3: There’s self-contradiction with the motivation of the paper. As discussed, the paper mainly concerns large bias factor space. However, this theorem assumes that each (input feature , bias factor) pair need to sample N observations from a Bernoulli distribution, and the theorem is based on “N is sufficiently large”. How can this be meaningful under the scenario the paper is concerned with? Theorem 4: The error bound is only shown to merge two subgraphs. Again, the paper is concerned with large bias factor space and the number of subgraphs could be be high - what is the error bound for the entire merge process? Will the errors propagate to meaningless values? Showing error bound only for merging two subgraphs looks quite limited. There are also several places in the paper that also look contradictory, e.g. when it argues about the benefit of node intervention, “It should be noted that K is typically smaller the the number of positions (assuming that positions are the sole bias factor)” - the reviewer is confused about such claims. If the paper is concerned with such scenario, then there’s probably no need to worry about the identifiability issue. On the experiments part, the evaluation is weak. The major issue is, the proposed methods are only shown to improve the very basic baseline. The authors argue that the methods are agnostic to the actual algorithm and “aptly represents the current research” - the reviewer strongly disagrees - to show the proposed method is really meaningful, it needs to show that they can help more sensible baselines. For example, will they help state-of-the-art ULTR methods? If not, why would people care? This is important since the proposed two methods have clear caveats (the node intervention method is not very practical, the node merging method is likely to introduce errors).

Questions

See questions above.

Rating

3: reject, not good enough

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

1 poor

Presentation

3 good

Contribution

2 fair

Summary

This paper delves into the identifiability issue of the ranking model within the context of unbiased learning to rank (ULTR). Previous studies have established the model's unbiasedness, assuming perfect fits for both clicks and the observation model, inadvertently overlooking the identifiability challenge at its core. Motivated by this, the article investigates the conditions necessary to recover identifiability, primarily in the context of scale transformation. The authors formalize the identifiability challenge as a graph connectivity test problem. Based on it, they further propose two methods, namely node intervention and node merging, to tackle this problem for empirical applications.

Strengths

1. The topic is interesting and important both theoretically and empirically; 2. The methods of graph connectivity are novel to me; 3. This paper is well-written.

Weaknesses

1. Experiments are weak and not very convincing, since it has very little baseline (see Q1 below for more details); 2. Theorem 3 is straightforward and does not seem useful; the conditions required by Theorems 2 and 4 are stringent (see Q2 below for more details).

Questions

I have two main concerns: **Q1.** In the experiment, there are only two weak baselines. In addition, there are lack of details about the two baselines. However, this article mentions a lot of related works but does not include them as part of the baselines for comparison empirically. This is inconsistent with the requirements in this area of ULTR. Could you add some cutting-edge ULTR methods as baselines? **Q2.** In terms of the theoretical results. >(1) Theorem 2 is a very simple case (… $x$ and $t$ are selected independently and uniformly …). Thus, it is not sufficient to write it as a Theorem; it might be more appropriate to write it as a Proposition. > (2) Theorem 3 is simple and straightforward (just by the central limit theorem) and does not seem useful. Could you clarify the purpose and use of Theorem 3? Also, it is not sufficient to write it as a Theorem; it might be more appropriate to write it as a Lemma. > (3) The condition required in Theorem 4, "A disconnected IG consists of two connected components G1 and G2" is strong and difficult to fulfill in practice. **In fact, the soundness of Theorems 3 and 4 is very critical to this paper.** Here are the two main reasons: (a) The graph is always disconnected in practice, and will suffer from identifiability problems; (b) To recover the identifiability, we always need node intervention and node merging to recover the connected graph for empirical applications. Thus, the rationality of these two proposed algorithms (node intervention and node merging) becomes critical. Regrettably, Theorems 3 and 4 are slightly weak, which seriously undermines the contribution of this paper.

Rating

5: marginally below the acceptance threshold

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Ethics concerns

NA

Summary

The paper investigates the problem of position bias in the task of Unbiased Learning to Rank. It first introduces the widespread concern of biased user logs and the consequent appriximation error in most of the commonly used ranking models. With a clear problem setup and definition of identifiability, the author states the conditions under which the true relevances can be extracted from click data. Particularly, the paper converts the identifiability problem into a graph connectivity problem. Based on the connectivity problem, the authors further come up two new approaches to deal with “unidentifiable” datasets and optimize the ranking models using structures of the graph. Experiments are conducted to prove the validity of the graph conversion, the performance of new approaches, and the application to the real-world datasets.

Strengths

S1: As one of its major contributions, this paper tansfers the identifiability of a ULTR task to the connectivity of a graph constructed based on the dataset. This equivalence is useful in that tasks related to a graph usually have more efficient computations, nicer properties, and more intuition-based understandings. The work also allows for more explainability in the field of ULTR and thus simplifies difficult questions. S2: This paper proposes two novel methods, node intervention and node merging, to bridge the “unidentifiability gap” by utilizing the graph properties. These two methods are theoretically supported and empirically verified.

Weaknesses

W1: Since the theory of this paper relies heavily on the examination hypothesis, the graph-equivalence idea is not generalizeable to other general hypotheses on the dataset. W2: Since the methods are still propensity-based, there are a plethora of such ranking models. It would be fair game if the paper uses such methods as baselines to strengthen the validity of the proposed methods. W3: When choosing the bias factors, we can choose either fewer factors, which makes the graph more likely to be connected, or more factors, which accounts for more bias but poses a more disconnected graph. It would be great if there is any discussion on the tradeoff and the corresponding performance of the two proposed methods. In addition, assume that each feature x and bias factor t are independently and uniformly chosen to construct the dataset D is nearly impossible in practice.

Questions

Q1: In the real world, the dataset is mostly sparse and thus there might be a large number of connected components in IG. How much does the performance of the two methods deteriote with the increasing sparsity? Is there a systematic way to deal with that issue? Q2: In the node merging method, the costs between nodes are computed based on the their deterministic features X_t. However, how is it guaranteed that the features reflect their true similarity? For example, we may use document rank as a bias factor when only considering the position bias. But it turns out that the user may notice the documents in the order of: the first several documents (since they’re most noticeable), the last several documents on this page (since users may scroll down), and then documents in the middle. In the more complex settings of several factors, it’s even less obvious which nodes are similar to each other. Is it possible to make the features not deterministic but rather learned throughout multi-task learning? Q3: In the application of the method, the dataset is mostly online and continuously taking in new data points. How does the proposed method handle the updates efficiently? For example, if two nodes (bias factors) with similar features are already merged but the new datapoints from the user creates an edge between them, is there a way to efficiently deal with this?

Rating

6: marginally above the acceptance threshold

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Summary

In this paper, the authors explore if or when the true relevance can be recovered from click data. Overall, it is a solid paper. My concern lies in whether and how can this approach apply to the existing unbiased learning-to-rank framework that developed from the examination hypothesis. Or, how the proposed framework incorporates current ranking models. Also, it would be better to compare this work against more recently proposed existing unbiased learning-to-rank algorithms. Overall, I give a weak rejection. If the authors would clarify the above concerns, I will be happy to raise my score.

Strengths

1. It is an interesting and important topic to investigate when the true relevance can be recovered from click data. 2. I like the theoretical analysis in this paper (i.e., Sections 3 and 4). 3. They have conducted experiments on Yahoo! and Istella-S datasets, verifying the performance of the proposed model.

Weaknesses

1. It lacks recently proposed methods as the baselines. 2. It would be interesting to discuss the difference between the proposed method and the existing approaches based on the examination hypothesis. 3. For an unbiased learning-to-rank algorithm, there is always a ranking algorithm base. It is not clear how the proposed model incorporates the existing ranking models.

Questions

It is essential to evaluate if or when the true relevance can be recovered from click data. I like this idea very much. However, in the context of unbiased learning-to-rank, there should be a ranking function (often referred to as biased), and then the core goal of unbiased learning-to-rank is to build a debiasing method that can be incorporated into the biased ranking models. After reading this paper multiple times, I consider that it is not clear how this approach can be applied to existing ranking models. Also, in the experiment part, the authors only compare no debias and a simple examine hypothesis method. I highly recommend the authors compare and discuss the connections to existing unbiased learning-to-rank algorithms such as “Unbiased Learning to Rank with Unbiased Propensity Estimation” and “An Unbiased Pairwise Learning-to-Rank Algorithm”. Therefore, I would like to give a weak rejection. If the authors would clarify the above concerns, I will be happy to raise my score.

Rating

5: marginally below the acceptance threshold

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Ethics concerns

NA

General response by Authors

We thank the reviewers for their insightful comments and valuable feedbacks. We are delighted that all reviewers agree that our proposed identifiability framework is novel, interesting and important for the ULTR research. They agree that the paper is well-written (R tHmn and R CYAM) with interesting theoretical analysis (R 2rku and R tHmn). We appreciate the reviewers valuable suggestions and will incorporate all feedback into the final version of our work. In response to the reviewers' concerns, we have made revisions to the submission, which are indicated in red. Herein, we provide a summary of the key changes made in response to their feedback. - One common concern (R ggp4, R tHmn, R CYAM and R 2rku) is whether our proposed methods work well with state-of-the-art baselines. In the revision, **we show how our methods perform when used with three different types of ULTR optimization algorithms: DLA [1], Regression-EM [2] and Two-Tower [3] in Table 1**. The results we initially shared were combined with DLA, as explained in Appendix E.3. We highlight that many recent strong baselines are variants of these three types of ULTR algorithms with some difference in bias factor considerations, like [4] using *outliers* with Regression-EM, and [5] using *MTypes, Serphs, and Slipoff* with DLA. Here are some of the results we're reporting: | | MCC | nDCG@10 | | ------------------- | ----- | ------- | | No debias | 0.641 | 0.858 | | DLA | 0.738 | 0.900 | | + Node intervention | 1.000 | 1.000 | | + Node merging | 0.987 | 1.000 | | Regression-EM | 0.634 | 0.868 | | + Node intervention | 0.982 | 0.999 | | + Node merging | 0.975 | 1.000 | | Two-Tower | 0.892 | 0.961 | | + Node intervention | 1.000 | 1.000 | | + Node merging | 0.987 | 1.000 | Without a guarantee of identifiability, various ULTR algorithms can end up converging to poor relevance recovery. However, when our proposed methods ensure identifiability, they converge to accurately recover the relevance. This demonstrates the model-agnostic nature of our methods. - Another concern is the strong assumptions in our theoretical results (R tHmn, R ggp4 and R CYAM): - In Theorem 2, note that this theorem is not critical for our proposed method and the experiments we conducted. Its purpose is to provide an intuition of how "increasing bias factors or decreasing data can potentially lead to unidentifiability" in a simple scenario. We've verified this in a more complex and practical setting in Section 5.2. **To reduce its significance, we've renamed Theorem 2 to Corollary 1.** - In Theorem 3, we've discovered that the assumption "N is sufficiently large" is not necessary for our proposed method, as it's only used for applying the central limit theorem. **We have removed this unnecessary assumption and restructured the theorem to present only the variance term, which is all our method requires.** - For Theorem 4, its purpose is not to derive the error bound for node merging (apologies for the misleading name). Instead, it is used to illustrate the error when merging two components, providing a strong foundation for the below merging cost. **We have created another corollary in Appendix B.5 to give the true error bound for node merging.** We hope the above revision could address the concerns in experiments and theorems. In the following, we will address the concern of each Reviewer individually. [1] Unbiased learning to rank with unbiased propensity estimation. [2] Position bias estimation for unbiased learning to rank in personal search. [3] Pal: a position-bias aware learning framework for ctr prediction in live recommender systems. [4] On the impact of outlier bias on user clicks. [5] Multi-feature integration for perception-dependent examination-bias estimation.

We would like to summarize our contribution and revisions, and kindly ask for a reevaluation

Dear Reviewers and ACs, As the discussion is ending soon in the next hours, we're grateful for the helpful comments and smart suggestions from all reviewers. **We would really appreciate it if the reviewers (R tHmn, R CYAM and R 2rku) could reevaluate the reviews considering our follow-up experiments and theoretical revisions**. In the following, we would like to summarize the contribution and revisions of this paper again. **Contributions**: - ***Core contribution***: we address the identifiability for ULTR from a new perspective of graph connectivity. This perspective is ``interesting``, ``important`` and ``novel`` (*R ggp4, R tHmn, R CYAM*), ``useful``, ``have nicer properties``, ``more intuition-based understandings``, ``more explainability`` and ``able to simplify difficult questions`` (*R ggp4*), and also ``lay the foundation for future work`` (*our response to R ggp4*). - The proposed two methods to deal with unidentifiability issue based on this graph view are ``novel and effective`` (*R ggp4*), and ``easy to understand`` (*R CYAM*). - The proposed methods are supported by both ``interesting theoretical analysis`` (*R 2rku, R tHmn*) and ``the extensive experiments`` (*R 2rku*). The paper is well-written (*R tHmn, R CYAM*). **Weaknesses and revisions**: - The common concern (*R ggp4, R tHmn, R CYAM and R 2rku*) is whether our proposed methods work well with state-of-the-art baselines. In the revision, we show how our methods perform when used with three different types of ULTR optimization algorithms: DLA [1], Regression-EM [2] and Two-Tower [3] in Table 1. **This follow-up experiment has been approved by R ggp4**, which ``provides more solid practical support``. - Another concern is the strong assumptions in our theoretical results (*R tHmn, R ggp4 and R CYAM*). We make revisions to the theorems as follows. - Theorem 2: this theorem is not so significant and thus we **rename** it to Corollary 1. Also, we've verified its conclusion in a more complex and practical setting in the experiment. - Theorem 3: we **remove the unnecessary assumption** (*"N is sufficiently large"*) and restructure the theorem. - Theorem 4: we have **created another corollary** to give the true error bound for node merging. - Besides, we also conducted a thorough experiment for tuning the feature numbers, confirming that increasing the dimension of $X$ can indeed lead to potential unidentifiability issues (*our response to R CYAM*). We also tried our best to address any contradictory in the paper (*our response to R CYAM*). We would again like to thank all reviewers, and we hope that our changes adequately address the concerns. Sincerely, The authors