Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper characterizes the identifiability of the label noise transition matrix for the generic case at the instance level based on Kruskal’s identifiability results. The main contribution is that it finds three separate independent and identically distributed (i.i.d.) noisy labels (random variables) are both necessary and sufficient for instance-level identifiability and the disentangled features help with identifiability.
strength_and_weaknesses: --Strength--
1. It characterizes the identifiability of the label noise transition matrix for the generic case at the instance level.

--Weakness--
1. The importance and necessity of studying the label noise transition matrix's identifiability are unclear. Additionally, why is it important to consider the instance-dependent label noise case? 
2. This paper lacks experiments to verify the importance of characterizing the identifiability of the label noise transition matrix at the instance level.
3. The format of the cited paper is not proper and seems to lack brackets.
4. Although the authors find that three separate independent and identically distributed (i.i.d.) noisy labels (random variables) are both necessary and sufficient for instance-level identifiability, are these noise types sufficient to describe the real label noise?
clarity,_quality,_novelty_and_reproducibility: Clarity: Poor 
Quality: Poor
Novelty: Good
Reproducibility: Not sure
summary_of_the_review: This paper characterizes the identifiability of the label noise transition matrix for the generic case at the instance level based on Kruskal’s identifiability results. However, this paper is not well written and some points are not well explained, especially the importance of studying the identifiability and the use of the proposed theorem in this paper. Therefore, this paper is marginally below the acceptance threshold.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies identifiability of label noise transition matrix T(X), which plays a crucial role in learning with noisy labels. Most of the works assume access to it or rely on some methods to estimate it. Understanding when such a noise matrix is identifiable is an important aspect of the problem. The paper considers instance dependent noise transition matrices and show the necessity of multiple noisy labels in identifying the noise transition matrix at the instance level. Their analysis builds on top of Kruskal's identifiability results.  Their analysis also sheds light on the successes of SOTA methods and how additional assumptions helped them alleviate the requirement of multiple noisy labels. They also provide empirical evidence to show that disentangled features are helpful in the identification task. 
strength_and_weaknesses: Strengths:
Identifiability of T(X) at the instance level is an important and challenging problem. The paper's results tell that we would need three conditionally independent and informative noisy labels to identify it. The results have practical implications on various settings e.g. crowdsourcing etc. where multiple noisy labels are acquired and then aggregated to obtain ground truth labels. Some of their results verify the empirical success of existing approaches from the identifiability perspective.  They empirically show the possibility of learning disentangled features to help identify the noise transition matrix.

Questions/Weaknesses:
Are there any assumptions on the noise levels? In particular do the results in theorem 5 hold for arbitrary noise level? How does the cardinality(size) of label space play a role here -- looks like the problem will be harder as the label space grows? How do the results compare against prior works like Liu et al. (2020); Zhu et al. (2021c); Zhang et al. (2014).
clarity,_quality,_novelty_and_reproducibility: Most of the paper is clear and well-written. The paper is of good quality and gives novel results. Source code is provided and sufficient details are given for reproducibility. 

summary_of_the_review: The paper gives several insightful results on identifiability of label noise transition matrix and these results have practical implications. More clarity on the setup and results can provided to make the better.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: -This paper studies the identifiability conditions of the noise transition matrix in instance-dependent label noise learning. The authors draw interesting connections between this problem with the Kruskal’s identifiability results and provide conditions to guarantee the identifiability of the instance-dependent noise transition matrix. They also show some existing works can be explained by their findings and some empirical results demonstrating disentangled features help identify the noise transition matrix.
strength_and_weaknesses: Pros:

-Existing results on the identifiability of noise transition matrix mainly focus on the class-dependent instance-independent label noise. This paper considers this identifiability problem in the instance-dependent noise setting. They show that given three noisy labels the identifiability of an instance-dependent noise transition matrix can be guaranteed.

Cons:

-**The most important definition is unclear.** In the definition of identifiability of transition matrix $T(x)$, only $\theta(x)$ appears, it is not clear where the hidden variables $Y$ (unobserved) and $\tilde{Y}$ (observed) are. It also seems that the notation $\theta(X)$ is redundant, definition 2 can be explained directly using $P_{T(X)}$, as in $\theta(X)=(T(X), P(Y\mid X))$ the prior $P(Y\mid X)$ is not really a parameter (adding this makes me very confused at first glance). What is the statistical model in definition 2, given the current definition I think it should be $P_{\theta(x)}$, can we interpret it as a probability distribution over a probability? Then should definition 2 be put as $P_{\theta(x)}$ is identifiable if $\theta(x)\neq\theta’(x)$, $P_{\theta(x)}\neq P_{\theta’(x)}$? Also, why the label permutation appears in definition 2? Due to this condition, the notion is not identifiability to me.

-**The most important theorem is not rigorously proved.** In the identifiability condition (Theorem 5) proof for necessity, the authors **only prove the binary label noise case and directly drop the noise dependency on the instance**, but the paper claims a multi-class setting and the identifiability condition is both necessary and sufficient. At least this should be made clear in the main paper!! A natural question is can this necessity proof be extendable to the multi-class instance-dependent noise case?

clarity,_quality,_novelty_and_reproducibility: -Clarity: the paper is well structured and flows smoothly, but some unclear points regarding the most important identifiability definition of the transition matrix T should be clarified.

-Quality: the paper studies the identifiability conditions of the transition matrix in instance-dependent label noise learning and draws connections to many existing works on this problem, my biggest concern on this is the proof for necessity in Theorem 5. The paper would be stronger if this can be improved.

-Novelty: the paper draws interesting connections between the identifiability of the transition matrix in label noise learning and Kruskal’s identifiability results which is novel to me.

-Reproducibility: good.
summary_of_the_review: -The paper studies the challenging problem of identifying transition matrix in instance-dependent label noise setting and provides interesting results on identifiability conditions based on Kruskal’s identifiability results, but the unclear parts of the identifiability definition should be clarified and more theoretical analysis is needed.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the identifiability of the label noise transition matrix $T(X)$ for instance-dependent noises. By applying Kruskal's identifiability results to the label noise case, the authors have shown that three independent noisy labels for each instance are sufficient and necessary for identifying the transition matrix. Since three independent noisy labels could be a somewhat strong requirement, the paper has also discussed the identifiability of T(X) in the cases when $P(Y\vert X)$ enjoys clustering properties or the representations of the feature are disentangled and informative.

strength_and_weaknesses: ### Strength
- The paper provides a sufficient and necessary condition for learning with instance-dependent noise. Although the main theorem (Theorem 5) seems a direct application of Kruskal's identifiability results, to me, it is still an interesting and novel view for understanding the identifiability of the label noise learning problem.
- Experiments are conducted to show that the disentangled features help identify the transition matrix.

### Weaknesses
My main concern about the paper is the significance of the theorems presented in Section 5 and the clarity of the presentation.
- about the significance: In Section 5, the authors attempt to show that the requirement on three independent noisy labels can be relaxed by considering the smoothness of clusterability of the features. But, I am confused by some parts of the statement, and it is unclear how the proposed theorems could relate to the goal of relaxing multiple noisy labels.
	- About Definition 5: Definition 5 introduces the 2-NN clustrability. It is unclear to me how the clustrability could help to reduce the requirement of multiple noisy labels. It seems that we still need two additional conditions to ensure the identifiability: (1) the 2-nearest neighbors (NN) of $X$ shares the same transition matrix with $X$. (2) the noisy label of X and its 2-NN should be independent. It is unclear how easy it is to meet these conditions in practice. It seems that these conditions are somewhat equal to the three independent noisy label requirements in the proposed example (see below).
	- About the example in Theorem 6: the authors prove Theorem 6 by showing that the same instance $X$ will appear three times, and thus $X$ is the 2-NN of itself. It is unclear to me how the condition on the independence of the noisy labels could be satisfied in such a case. If the independent condition is true, it seems that we still need three independent nosy labels for the same $X$.

	- About Theorem 8 and Theorem 9: At first glance, the theorem shows that we only need 1 noisy label to ensure the identifiability of $T(X)$ when the representations of X are disentangled and informative. But it is unclear to me what is role of the disentangled feature plays in the theorems. It seems that, by the Kruskal's identifiability results, one can directly show $P(Y\vert X)$ is identifiable with the disentangled and informative representations only (please correct me if I am wrong). In such a case, there is no need to identify the noise transition matrix, which makes the requirement for disentangled and informative representations seem very strong.
- about the clarity of presentation:
	- This paper has introduced many notations, which makes it hard to follow. To me, some of them are somewhat redundant. For example, the notation of $P_\theta$ is seldomly used in the rest parts.
	- Section 3.1 has spent much space introducing the MPE problem. It is unclear how the MPE problem is related to the main focus of the paper presented in Section 4 and Section 5. I think it would be better for the authors to make this point clear.

### Minor points:
- It would be better to use \citep instead of \citet, if the cited paper does not appear as a component of the sentence.
- Page 6: the third line of the proof sketch, there is an additional "." after $Y\in\\{1,2,\dots,K\\}$.
- Page 6, first sentence in Section 5: focuses--> focus
- Definition 5: since $Y$ is a random variable,I think it would be better to write the condition as $P(Y \vert X) = P(Y_1 \vert X) =P(Y_2 \vert X)$ to avoid potential misunderstanding.
- Figure 2:"Grey"--> "Grey color"

clarity,_quality,_novelty_and_reproducibility: - Clarity & quality: some parts of the paper are unclear (please see the weakness part above for more details).
- Novelty: It is an interesting view to understand the identifiability of the noise transition matrix by using the Kruskal's identifiability results.
- Reproducibility: the paper has provided the code and complete proofs for the theorems. 

summary_of_the_review: This paper has provided a sufficient and necessary condition for the identifiability of the noise transition matrix (in Section 4). Although the result seems a direct application of the Kruskal's identifiability results, it is still novel and interesting for me from the view of learning with noisy labels. My main concern about the paper is the significance of the theorems and the clarity of some statements. Overall, I think the flaws overweight the merits of this paper, and it falls into the borderline cases.

===post-rebuttal===
After reading the author's feedback and other reviews, I do find this paper has some interesting parts. But, as also mentioned by other reviewers, the clarity of this paper should be further improved, especially on the definition and the motivations of examples in Section 4. To me, the paper still needs a non-trivial revision before publication. Therefore, I tend to reject this paper.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary:
This paper shows the identifiability condition of the noise transition matrix in the instance-dependent noise setup.

Strength:
Using Kruskal's results to investigate the identifiability of label noise is novel and interesting. The result that disentangled features help  identify the noise transition matrix in the instance-dependent noise setup is valuable.

Weakness:
The clarity of the current manuscript is low and the reviewers were confused with the notation. Also, the justification of the 2-NN idea still requires more discussion to be broadly acceptable to the readers. 

justification_for_why_not_higher_score: Thanks for the responses to the reviewers' questions, which clarified some of the concerns they had in their initial reviews. This paper investigates the important problem of identifying the noise transition matrix as a function of instances. The obtained condition through Kruskal's results is interesting. Overall, I found the result of this paper worth publishing, but through the thorough discussions between the authors and reviewers, I must say that the current manuscript requires non-trivial major revision to clarify the presentation of the results. Therefore, I cannot recommend the current manuscript for acceptance.
Decision: Reject