Identifiability of Label Noise Transition Matrix 
Authors: Yang Liu
Hao Cheng
Kun Zhang
Venue: Submitted to ICLR 2023 (2023)
Keywords: identifiability
label noise transition matrix
noisy labels

Abstract: The noise transition matrix plays a central role in the problem of learning with noisy labels. Among many other reasons, a large number of existing solutions rely on access to it. Identifying and estimating the transition matrix without ground truth labels is a critical and challenging task.  When label noise transition depends on each instance, the problem of identifying the instance-dependent noise transition matrix becomes substantially more challenging. Despite recent works proposing solutions for learning from instance-dependent noisy labels, the field lacks a unified understanding of when such a problem remains identifiable. The goal of this paper is to characterize the identifiability of the label noise transition matrix.  Building on Kruskal's identifiability results, we show the necessity of multiple noisy labels in identifying the noise transition matrix for the generic case at the instance level. We further instantiate the results to 
relate to the successes of the state-of-the-art solutions and how additional assumptions alleviated the requirement of multiple noisy labels. Our result also reveals that disentangled features are helpful in the above identification task and we provide empirical evidence.  

Under review as a conference paper at ICLR 2023
IDENTIFLABILITY OF LABEL NOISE TRANSITION MATRIX
Anonymous authors Paper under double-blind review
ABSTRACT
The noise transition matrix plays a central role in the problem of learning with noisy labels. Among many other reasons, large number of existing solutions rely on access to it. Identifying and estimating the transition matrix without ground truth labels is critical and challenging task. When label noise transition depends on each instance, the problem of identifying the instance- restance-eependent noise transition matrix becomes substantially more challenging. Despite recent works proposing solutions for learning from instance-dependens noisy labels, the field lacks a unified understanding of when such a problem remains identifiable. The goal of this paper is to characterize the identifiability of the label noise transition matrix. Building on Kruskal's identifiability results, we show the necessity of multiple noisy labels in identifying the noise transition matrix for the generic case at the instance level. We further instantiate the results to relate the successes of the satte-of-the-ars solutions and how additional assumptions alleviated the requirement of multiple noisy labels. Our result also reveals that disentangled features are helpful in the above identification task and provide empirical evidence.
INTRODUCTION
The literature of learning with noisy labels concerns the scenario when the observed labels Y can differ from the true one Y. The noise transition matrix T(X), defined as the transition probability from Y to Y given X, plays a central role in this problem. Among many other benefits, the know Ingwledge of T(X) has demonstrated its use in performing either risk (Natarajan et al.
2013 Patrini al. 2017a), or label (Patrini et al. 2017a). or constraint corrections ( (Wang et al. 202 la) In beyond, also finds applications
ranking small loss samples (Han et al. 2020) and detecting corrupted samples (Zuu et al. 2021a). On the other hand, applying the wrong transition matrix T(X) can lead to number of issues. The literature has well-documented evidence that a wrongly inferred transition matrix can lead to performance drops (Natarajan al. 2013] Liu & Wang Xia et al. 2019 Zhu et al.) 2021c), and false sense of fairness (Wang et al. 20222021 Liu & Wang). Knowing whether a ) identifiable not helps understand if the underlying noisy learning problem is indeed learnable.
Prior works have documented challenges in estimating the noise transition matrices when the quality
of available training information remains unclear. For instance, in (Zhu al. [022)) the authors show that when the quality of representations dropped, the estimation error in 7(X) increases significantly
(Figure therein). Other previous references have documented these challenges too (Xia et 2019 We have also provided experiments to validate the argument in Appendix C.4
The earlier results have focused on class- but not instance-depeendet transition matrix T(X) T [PP(Y Y|Y k)]k.. VX. The literature has provided discussions of the identifiability of T under the mixture proportion estimation setup (Scott 2015), and has identified a reducibility condition for inferring the inverse noise rate. Later works have developed a sequence of solutions to estimate T' under variety of assumptions, including irreducibility (Scott) 22055). anchor points (Liu & Tao Xia et al. 20199] Yao et al. (020a)), scparability (Cheng et al. (020)), rankability (Northoutt)
2016
et al.
2017 2021), redundant labels/tensor (Liu et al.) 2020 Traganitis al. 2018 Zhang et al.
2014
clusterability (Zhu et al. 2021c), among others (Zhang et al. 2021 Li et al. 2021).
Recent study (Wei al. 2021 has empirically shown that the above class- dependent model is not precise in capturing the real-world noise patterns, but rather real human-leve noise follows an instance-dependent model. Intuitively, the instance X encodes the difficulties in generating the label

---

Under review as a conference paper at ICLR 2023
for it. This more realistic, flexible and powerful noise model helps characterize the challenges. We observe a recent surge of different solutions towards solving the instance-dependeee label noise problem (Cheng et al. 2020; Xia et al. 2020b; Cheng et al.) 2021a Yao et al., (02I). Some of the results took on the problem of estimating T(X), while the others proposed solutions to learn directly from settancedeeeedeett noisy labels. We will survey these results in Section [.T] The question of identifying and estimating '"' becomes much trickier when the noise transition matrix is instance- deneedeed.. The potentially complicated dependency between X and T(X) renders it even less clear whether solving this problem is viable or not.
Despite the above successes, there lacks a unified understanding of when this learning from instance- dependent noisy label problem is indeed identifiable and therefore learnable. The mixture of different observations calls for the need for demystifying: (1) Under what conditions are the noise transition matrices T(X) identifiable? (2) When and why do the existing solutions work when handling the dependent label noise? (3) When T(X) ) is not identifiable, what can we do to improve its identifiability? Providing answers to these questions will be the primary focus of this paper. The main contributions of this paper are to characterize the identifiability of instance- restance-dependent label noise, use them to provide evidences to the success of existing solutions and point out possible directions to improve. Among other findings, some highlights of the paper are 1. We find many existing solutions have deep connection to the celebrated Kruskal's identifiability results that date back to the 1970s [Kruskal 1976] 1.77). 2. Three separate independent and identically distributed (i.i.d.) noisy labels (random variables) are both necessary and sufficient for instance-level identifiability. This observation echoes the previous successes of developing tensor-based approaches for identifying the hidden models. 3. Disentangled features help with identifiability. Our paper will proceed as will
follows. Section 2 andd 3 will present our formulation and the highly relevant preliminaries. Section provides characterizations of the identifiability at the instance level and lays the foundations for our discussions. Section
5 extends the discussion to different instantiations that help us provide evidences to the success of existing solutions. Section 6 provides some empirical observations.
1.1 RELATED WORKS
In the literature of learning with label noise, major set of works focus on designing risk-consistent methods, i.c.. performing empirical risk minimization (ERM) with specially designed loss functions on noisy distributions leads to the same minimizer as if performing ERM over the corresponding unobservable clean distribution. The noise transition matrix is a crucial component for implementing risk-consistent methods, e.g., loss correction (Patrini et al.] 2017b), loss reweighting (Liu & Tao 2015), label correction (Xiao al., 2015) and unbiased loss (Natarajan et al., 2013). A number of solutions were proposed to estimate this transition matrix for class-dependent label noise, which we have discussed in the introduction. To handle instance-dependent noise, recent solutions include estimating local transition matrices for different groups of data (Xia et al. 2020b), using confidence scores to revise transition matrices (Berthon et al. 2020). and using clusterability of the data (Zhu et al. 2021ch. More recent works have used the causal knowledge to improve the estimation (Yao et al. 2021). and the deep neural network to estimate the transition matrix defined between the noisy label and the Bayes optimal label (Yang et al., [002]) Other works chose focus on the learning from instance-dependent label noise directly, without explicitly estimating the transition matrix (Zuu
al. 2021b Cheng al. 202 la Berthon et al. 2021 Xia al. 2020a Li al. 2020).
The identifiability issue with label noise has been discussed in the literature, despite not being formally treated. Relevant us is the identifiability results studied in the Mixture Proportion Estimation setting (Scott) 2013: Yao et al.] 2020b; Menon et al. (015)). We'd like to note that the identifiability was defined for the inverse noise rate, which differs from our focus on the noise transition matrix T. To our best knowledge, we are not aware of other works that specifically address the identifiability of T(X), particularly for an instance-dependent label noise setting. Highly relevant to us is the Kruskal's 's identifiability results (Kruskal 1976 1977, Sidiropoulos & Bro| 2000 Allman et al. 2009). which reveals a sufficient condition for identifying a parametric model that links a hidden variable to set of observed ones. Kruskal's 's early results were developed under the context of tensor, which later proves to be a powerful tool for learning latent variable models (Sidiropoulos et al., 2017
Zhang
al. 2014 Anandkumar et al. 2014).
2

---

Under review as a conference paper at ICLR 2023
2 FORMULATION
We use (X, Y) to denote a supervised data in the form of (feature, label) drawn from an unknown distribution over X x Y. We consider K-class classification problem where the label Y {1, 2......, .... K} with K 2 2. In our setup, we do not observe the clean true label Y, but rather a noisy one, denoting by Y. The generation of Y follows the following transition matrix: T T(X) == [P(Ý = j|Y i, , T(X) is a K x K matrix with its (i,5) entry being P(Y = = i, X).
To define identifiability, we will denote by 12 an observation space. We first define identifiability for a general parametric space O Denote the distribution induced by the parameter 0 E e of statistical model on the observation space f2 as Po (Kruskal 1976; Allman et al. 2009). To give an example, for fixed X (when consider instance-level identifiability), and 12 is simply the outcome space for its associated noisy label Y. i... of a possible transition matrix TX) and the hidden prior of P(Y which we use to denote the conditional probability distribution of Y given X. Po is then the distribution (probability density function) [X) Later in Section 4 when we introduce three noisy labels Y1, Y2, Y3 for each X, Po is the joint distribution P(Y1, Y2, Xx) Identifiability defines as follows:
K} }. In this case, each 0 is the combination
Definition 1 (Identifiabilltty). The parameter 0 (statistical model) is identifiable Pf + Po. 40 + 0'. We define identifiability for the task of learning with noisy labels for an X. Denote by ((X) := {T(X), x)), Fo(x) is the distribution (probability density function) over S2 defined by the noise transition matrix T(X) ) and the prior P To emphasize, Ω is not necessarily the observation space of the noisy label Y only. The exploration of an effective S2 will be one of the focuses.
Definition 2 (Identifiability of T(X)). For a given X, T(X) is identifiable if P((x) + (x) for (() * (X))), up to label permutation.
Label permutation relabels the label space, e.g., 1 + 2, 2 + 1, and the rows in T(X) will swap. Allowing for label permutation would mean that our results allow the high noise rate regime. For instance, for binary classification problem, an 80% noise rate would correspond to counterfactual 20% one. Finding either model would regarded as being identifiable. In practice, further restriction such noise rate should not exceed 50% can help remove one of the two cases.
3 PRELIMINARY
In this section, we will introduce two highly relevant results on Mixture Proportion Estimation (MPE) (Scott 2015) and Kruskal's 's identifiability result (Kruskal 1976 1977).
3.1 PRELIMINARY RESULTS USING IRREDUCIBILITY AND ANCHOR POINTS
The problem of learning from noisy labels ties closely another problem called Mixture Proportion Estimation (MPE) (Scott) 2015), which concerns the following problem: let F, J, H be distributions
defined over Hilbert space Z. The three relate to each other as follows: F (1 (1- x=*x* >=J + x² H. The
identifiability problem concerns the ability to identify the mixture proportion x* from only observing F and H. The following identifiability result has been established:
Proposition 1. (Blnchhrd et al. 2010 K* is identifiable if is irreducible with respect to H. that J can not be written as J = =
F), where 0 S Y S 1, and F' is another distribution.
Later, the anchor point condition (Yoo al. (020b). stronger requirement
established:
Proposition 2. (Yao et al. 20206) K" is identifiable if there exists a subset S C Z such that O, where J(S), (S) denote the probabilities of S measured by J, H.
H(S) > 0, but J(S)
H(S
The above set S is called an anchor set. A sequence of follow-up works have emphasized the necessity
of anchor points in identifying a class-dependent transition matrix (Xia et al. 2019 Li et al. 2021).
Prior work has established the connection between the MPE problem and the learning from noisy label one (Yao et al. 2020b) for the identifiability of an inverse noise rate P(Y|)) but not the noise transition T(X). We reproduce the discussion and fill in the gap. The discussion and results are for the flass-dependen but not instance-dependens label noise, i..., T(X) = T (P Y, X) = P(Y|Y)), and for binary classification problem. To follow the convention, we assume Y (11,+11. There
3

---

Under review as a conference paper at ICLR 2023
two things we need to do: (1) State the noisy label problem an MPE one; and (2) show that the identifiability of Æ² is equivalent to the identifiability of T. We start with the first thing above. We want to acknowledge that this equivalence appeared before in (Yao et al.] 2020b; Menon et al.) 2015). We reproduce it here make our paper self- Denote by # P(Y 1 + = P(Y = +1 -1 and f- -- #
I-R-
Lemma 1. P(XI - P) = +1) relate to P(X = -1), = +1) as follows:
P(XI = 11 = k- P(X = +1) P =
(1)
F[X = +1) = Ā+ P(X = (1- (EXI)) +11
(2)
Now = P() -1) correspond to the observed mixture distribution F, H, while P(X = +1) and P(X = -1) are the two unobserved Js. ã- # correspond to the mixture proportion K". This has established the learning with noisy label problem as two MPE problems corresponding for the two associated distributions P(X Y = -1), P(X +1). Therefore to formally establish the equivalence between identifying x* and T, we will only need to establish the equivalence between identifying #- 7 and identifying T. Denote by e. == P(( =1|
+1),e_ == PY +1|Y -1) which determine the T for the binary case. We then have: Theorem 3. Identifying { is equivalent with identifying (+_.
The above theorem concludes the same irreducibility and anchor point conditions proposed under MPE also apply to identifying noise transition matrix T. This conclusion aligns with previous successes in estimating class-dependent noise transition matrix when the anchor point conditions satisfied (Liu & Tao 2016 Xia al. 2019 Li et al. (021). The above result has limitations. Notably, the result focuses on two mixed distributions, leading to the binary classification setup in the noisy learning setting. The authors did not find an easy extension to the multi-class classification problem. Secondly, the translation to the noisy learning problem requires the noise transition matrix to stay the same for a distribution of X (e.g., P(X +1)), instead of providing instance-level understanding for each X.
3.2 KRUSKAL'S IDENTIFIABILITY RESULT
Our results build on the Kruskal's identifiability result (ruuskal 1976 1977). The setup is as follows: suppose that there is an unobserved variable Z that takes values in K-sized discrete domain {1,2..., r3. Z has a non-degenerate prior P(Z = i) > 0. Instead of observing Z, we observe variables {0,},-
Each O, has a finite state space {1, 2, ..., ...,,} with cardinality 1s., Let M, be a matrix of size X Ki. which j-th row is simply [P(O0;
1 j)...., P(O, = .g 7 = j)]- In this case, [M1 .2.. .... Mp] and PlZ- = i) are the hidden parameters that control the generation of observations together, these form our 0. We now introduce the Kruskal rank of matrix, which plays a central role in Kruskal's identifiability results.
Definition 3 (Kruskal rank). (Kruskal 1976-1 1977) For a matrix M, the Kruskal rank of M is the largest number I such that every set of rows of M are linearly independent.
In this paper, we will use Kr(M) to denote the Kruskal rank of matrix M. To give an example,
1
Kr(M) = 1. This because [1, 0] and [2, 0, 0) are linearly dependent. We first reproduce the following theorem:
M-
0
2
Theorem 4. (Kruskal 1976 1977 Sidiropoulos & Bro 2000) The parameters M,, 1, I,... p are identifiable, up to label permutation, if,
Kr(M)) 2 2r +p-1
(3)
The result for 3 was first established in Kruskal 1977) demonstrating the power of a three-way
tensor, and then it was shown in (Sidiropoulos Bro 2000) that the proof extends to general p. The proof builds on showing that different parameter 0 leads to different stacking of Ms: [M M,] For example, when p = 3, [M, M2, Ms] := Σ m X m m forms the tensor of the observations, where m k - 1, 3 is the k-th column of M,.
'There exists other definition that checks columns. Results would he symmetrical.
4

---

Under review as a conference paper at ICLR 2023
4
INSTANCE-LEVEL IDENTIFIABILITY
This section will characterize the identifiability of (XX) at the instance level.
4.1 SINGLE NOISY LABEL MIGHT NOT BE SUFFICIENT
At first sight, it is impossible identify P(K Y X) from only observing IP ) unless X
satisfies the anchor point definition that PY k|X) for certain k: since P((IX)
P(Y)Y,X) P(Y different combinations of (X) can lead to the same IP PY(
More specifically, consider the following example:
Example 1. Suppose we have a binary classification problem with T(X) =
ex) e- ex) [
(x) 1 1- ex)+ Note that using chain rule (probability) we have
= P0==+1177 = PP = +1/8 = x), (),x)(PP) PPY = +1|X) + PP--
= -1, P(Y = -1(x)
= e1 (X)) -P(Y P- +1|x) +
c
= (xx)
Consider cases: (1): P-Y
= ex)
(X) (X)=
0.3 and (2): P(Y +1|X)
0.7, (X) = 0.1, e- (X)= 0.233. Both cases will return the same PP = +1 0.7.
Is then the anchor point requirement necessary for identifying T(X) at the instance level? The discussion in the rest of this section departs from the classical single noisy label setting.
4.2 THE NECESSITY OF MULTIPLE NOISY LABELS
Setups We assume for each instance X, we will have conditionally independent (given X, Y) and identically distributed noisy labels Yi, ..., Y, generated according to T(X). Let's assume for now we potentially have these labels. Later in this section, we discuss when having multiple redundant labels are possible, and connect to existing solutions in the literature in the next section. For each instance x, denote by Kx I K the number of non-degenerated label classes & such that P(Y = k|X)= > O. W.l.o.g,, let assume the non-degenerate classes are simply {1, Kx}.
Before we formally present the results for having multiple conditionally independent noisy labels, we offer intuitions. The reason behind this identifiability result ties close to latent class model (Clogg) 1995) and tensor decomposition (Anandkumar et al. 2014). When the p noisy labels are conditionally independent given X and Y, we will have the joint distribution written as: PY,,, Y2, ..., Y, X) = P(K/Y, X) That is, the joint distribution of noisy labels can be encoded in a much smaller parameter space! In our setup, when assume the i..dd Y,, i 1, 2..,.... p generated according to the same transition matrix T(X), the parameter space is fixed and determined by the size of T(X). Yet, when we increase the observation space IP(Y,, Y2,.., Y,IY, becomes richer to help us identify T(X). We now define an informative noisy label.
Definition 4. For a given (X,Y) Y), we call their noisy label Y informative if (Tnn) = Kx-
Definition 4 requires the Kx rows of T(X) are linearly independent. When the observation space for Y is the same as Y (therefore T(X) is squared matrix), i.c.. the true label Y has full support on the entire label space, then the requirement is stating that T(X) is of full rank, which is already assumed in the literature- - e.g., loss correction (Natarajan al. 2013 Patrini al., 2017a) would require the matrix has an inverse T-1 (X)), which is equivalent to T(X) being full rank. In particular, it was required e4 (X) + e (X)
in (Natarajan al. 2013), which can be easily shown to imply T(X) is full rank. But we don't 't remove the possibility that T ((X) is not a squared matrix and Kx can be much smaller than the entire label space. Our first identifiability result states as follows:
Theorem 5. With i...d. noisy labels, three informative noisy labels Yi, Y2, Ys (p 3) are both sufficient and necessary to identify T(X) when Kx 2 2.
Note that Kx 2 is easily satisfied as long as there exists uncertainty in PX
P We clarify that we will require knowing P( this requirement may appear weird when only one noisy lahel is sampled. But in practice, there are tools available to regress the posterior function P(YIX) for each X.
5

---

Under review as a conference paper at ICLR 2023
Proof sketch. We provide the key steps of the proof. The full proof can be found in the supplemental material. We first prove sufficiency. We first relate our problem setting to the setup of Kruskal's s identifiability scenario: Y E {1.2. Kx). corresponds to the unobserved hidden variable Z. P(Y i) corresponds to the prior of this hidden variable. Each Y,, I,... observation Oz. K; is then simply the cardinality of the noisy label space, K. In the context of this theorem, p = 3. corresponds to the three noisy labels we have. Each Y; corresponds to an observation matrix M, M. k] = P(O; A Z = j) = P(Y; = k|Y = X). Therefore, by definition of M2, M3 and T(X), ). they all equal to T (X)): M, = ( 1,2,3. When T(X) has a rank Kx, we know immediately that all rows in M1. M2, M3 are independent. Therefore, the Kruskal ranks satisfy (r(M)) Kr(M2) = (rxM = Kx. Checking the condition in Theorem 4 we easily
..... P corresponds to the
verify (r(M)) + Kr(M2) + Kr = 3Kx 2 2Kx 2. Calling Theorem proves the sufficiency.
To prove necessity. we need to prove less than 3 informative labels will not suffice to guarantee identifiability. The idea is to show that the two different sets of parameters T(X) can lead to the same joint distribution PYY,. Y2|X), We leave the detailed constructions to the supplemental material. O
The above result points out that to ensure identifiability of T(X) at the instance level, we would need three conditionally independent and informative noisy labels. This result coincides with a couple of recent works that promote the use of three redundant labels (Liu et al. 2020: (Zhu al. 2021c] Zhang et al. 2014). Per our theorem, these two proposed solutions have a more profound connection to the identifiaiility of hidden parametric models, and three labels are not only algorithmically sufficiently, but also necessary. This result also echoes the power of tensor (stacking third order information) in uncovering hidden models ( (Traganitis et al. 2018 Zhang et al. 2014). Particularly relevant to us is (Zhang al. 2014) where it was shown spectral EM approach that uses three noisy labels suffices to identify the noise transition matrix of labels. We want to highlight that our proof and results establish both the necessity and sufficiency for having three informative noisy labels, independent from the specific algorithms developed. Another note we want to add is that our main inquiry is on establishing the conditions for identifying T T'X). instead of proposing algorithms estimate T (X).
The crowdsourcing community has been largely focusing on soliciting more than one label from crowdsourced workers, yet the learning from noisy label literature has primarily focused on learning from single one. One of the primary motivations of crowdsourcing multiple noisy labels is indeed to aggregate them into a cleaner one (Liu et al.) 2012] Karger et al. [20TT] Liu & Liu 2015), which serves as pre-processing step towards solving the noisy learning problem. Nonetheless, our result demonstrates the other significance of having multiple labels they help the learner identify the underlying true noise transition parameters.
5 INSTANTIATIONS AND PRACTICAL IMPLICATIONS OF OUR RESULTS
Most of the learning with noisy label solutions focus on the case of using a single label and have observed empirical successes. In this section, we provide extensions of our results to cover of state- of-the-art learning with noisy label methods, together with specific assumptions over X, T(X) [P((]Y,,)) etc. We show that results can easily extend to these specific instantiations that successfully avoided the requirements of having multiple noisy labels for each X. The high-level intuition for Section i. to leverage the smoothness and clusterability of the nearest neighbor Xs so that their noisy labels will jointly serve as the multiple noisy labels for the local group. Section 5.2 andd555. build on the notion that if T(X) is the same for a group of Xs, each group can then be treated as one "instance" and "disentangled" version of X will become observation variables that serve the similar role of the additionally required noisy labels.
5.1
LEVERAGING SMOOTHNESS AND CLUSTERABILITY OF X
We start with a discussion using the smoothness and clusterability of X. Recent results have explored the clusterability of Xs (Zhu al. 2021c; Bahri et al. 2020) to infer the noise transition matrix:
Definition 5. The 2-NN clusterability requires each X and its two nearest neighbors X1 share the same true label Y, that is Y Y = Yg, and T (X) = T(x1) = T(x2).
This definition helps us remove the requirment for multiple noisy labels per each X: one can view it as for each X, borrowing the noisy labels from its 2-NN, we have three independent noisy labels Y, Yi, Y2, all from the same Y. This smoothness clusterability condition allows to apply our

---

Under review as a conference paper at ICLR 2023
identifiabilitty results when one believes the T(X) stays the same for the 2-NN nearest neighborhood X1, But, when does an instance X and its 2-NN X1, X2 share the same true label? This requirement seems strange at the first sight: as long as (XY]X), (Y1 IPY, [X, ) are not degenerate (being either O or for different label classes), there always seems to be a positive probability that the realized Y * Y1, no matter how close X and 11 are. Nonetheless, the 2-NN requirement seems hold empirically: according to (Zhu et al. 2021c) (Table 3 therein), when using feature extractor built using the clean label, more than 99% of the instance satisfies the 2-NN condition. Even when using a weaker feature extractor, the ratio is mostly always in or close to the 80% range.
The following data generation process for an unstructured discrete domain of classification problems (Feldman [020 Liu (021)) helps us justify the 2-NN requirement. The intuition is that when Xs are informative and sufficiently discriminative, the similar Xs are going to enjoy the same true label.
Let À (Ai, .A.,...... )n denote the priors for each X E X.
For each X X, sample quantity qx independently and uniformly from the set A.
The resulting probability mass function of X is given by D(X) Exex
4x
A total of N Xs are observed. Denote by X1, X2 X's two nearest neighbors.
Each (X, x1,X)) forms a triplet if || - XiI, || - X|| fall below a threshold (closeness).
A single for the tuple X1, X2) draws from
X2).
Based on Y, we further observe three Y, Yi, Y/ according to P(Ý, 91, P11).
The above data-generation process captures the correlation among Xs that are really close. We prove the above data generation process satisfies the 2-NN clusterability requirement with high probability.
Theorem 6. When N is large enough such that N > 4xxxx each X and its two nearest neighbor X1,X2 satisfy the 2-NN clusterability.
minx 9x w.p. al least 1 - Nexp(( (2N),
Smoothness conditions in semi-supervised learning This above discussion also ties closely to the smoothness requirements in semi-supervised learning (Zhu et al.] 2003 Zhu 2005), where the neighborhood Xs can provide and propagate label information in each local neighborhood of Xs. Indeed, this idea echoes the co-teaching solution (Tiang al., 2018 Han et al. 2018 in the literature of learning with noisy labels, where a teacher/mentor network is trained to provide artificially generated noisy labels to supervise the training of the student network. Our identifiability result, to certain degree, implies that the addition of the additional noisy supervision improves the chance for identifying T(X). (Jiang et al. 2018 8 Han al. 2018 counting the noisy label itself, and the "teacher" supervision, there are two such noisy supervision labels. This observation raises an interesting question: since our result emphasized three labels, does adding an additional teacher network for an additional supervision help? This question merits empirical verification.
5.2 LEVERAGING SMOOTHNESS AND CLUSTERABILTY OF T(X)
We show that another "smoothness" assumption of T(X) introduces new observation variables for us to identify T(X). In Figure [ we define variable G = 2, .... [G} to denote the group membership for each X. Consider scenario that X can be grouped into | groups such that each group of Xs share the same T(X): T(X1) = T(22)
if X1,X2 X2 share the same group membership. We observe Y.
Figure 1:
Graph for
This type of grouping has been observed in the literature:
Y, Grey color in- dicates observable variables.
Class-dependent T X) = PP YY), single group VXs.
Noise clusterability The noise transition estimator proposed in (Zhu et al., 2021ch was primarily developed for class-dependent but not instance-dependent T()). Nonetheless, a noise clusterability definition is introduced therein to allow the approach to be applied Under noise clusterability, using clustering algorithms can help separate the dataset into local ones.
mnstance-dependen noise.
Group-dependent T(X) Recent results have also studied the case that the data X can be grouped using additional information (Wang et al.] 2001a]] a Liu & Wangl Waan et al.) 20216). For instance, (Wang al. 2021a Liu & Wang) consider the setting where the data be grouped by the associated
7

---

Under review as a conference paper at ICLR 2023
"sensitive information", c.g., by age, gender, or race. Then the noise transition matrix remains the same for X's that come from each group.
By this grouping. X becomes informative observations for each hidden Y and will fulfill the requirement of observing additional noisy labels. We now define a disentangled feature and an informative feature: Denote by R(X) E R a learned representation for X. Denote by R& the random variable for R, ( = 2, .., d². For simplicity of the analysis.
assume each R, has finite observation space R, with cardinality [R,] = nij Define M, for each R, as M, k] = P(R, = R.[&||Y j), where in above [.[k] denotes the k-th element in R,
Definition 6 (Disentangled R). R. disentangled if (R are conditional independent given Y. Definition 7 (Informative features). R; is informative if its Kruskal rank is at least 2: Kr(M;) 2 2. Assuming each X can be transformed into set of disentangled features R. we prove:
Theorem 7. For Xs in given group E G. with a single informative noisy label, T(X) is identifialle if the number of disentangled and informative features d' satisfy that d" 2 K.
This result points out a new observation that even when we have a single noisy label, given a sufficient number of disentangled and informative features, the noise transition matrix T is indeed identifiable. without requiring either multiple noisy labels, or the anchor point condition. The above result aligns with recent discussions of neural network being able to disentangle features (Higgins al. 2018 Steenbrugge et al. 2018) proves to be a helpful property. We establish that having disentangled feature helps identify T(X). The required number of disentangled features grows linearly in K. When relaxing the unique identifiability to generic identifiability, i.e., the identifiability scenario has measure zero (Allman et al. 2009), the above theorem can be further extended to requiring
d" 2 [log2 - where KG = maxxeG Kx. Details are deferred to Appendix (Theorem 10). Note that the existence of disentangled X does not imply that we will be able to directly infer P(Y F(TX) which will help complete the learning task directly. But rather, it is indeed possible to further identify the structure [P( (from unobserved to observed) but this is an identifiability problem defined on much higher space.
When disentangled features are not given, how do we disentangle X using only noisy labels to benefit from our results? In Section 6 we will test the effectiveness of a sulf-supe representation learning approach that takes the side information relative to true label Y but operates independently from noisy labels. This result implies when the noise rate is high such that Y starts to become uninformative, dropping the noisy labels and focusing on obtaining the disentangled features helps with the identifiability of T(X). This observation also helps explain successes in applying semi- Nguyen et al. 2019) and self-supervised learning 2021 to handle noisy labels.
supervised (Cheng et al. 202 Li al. 2020
(Cheng et al. 2021b] Zheltonozhski et al.
2022 Ghosh & Lan
5.3 SMOOTHNESS AND CLUSTERABILITY OF T(X) WITH UNKNOWN GROUPINGS
In practice, we often do not know the groupings of that share the same T(X), nor do we have a clear power (e.g., the noise clusterability condition) to separate the data into different groups. In reality, different from Figure [ the group membership can often remain hidden, if additional knowledge of the data is solicited, leading to a situation in Figure 2 It is non-trivial task to jointly infer the group membership with T(X). We first show that mixing the group membership can lead to non-negligible estimation errors. Suppose that there are two groups of X, each having a noise transition matrix Ti (X)). T2)X). Suppose we ended up estimating one T'()) for both groups mistakenly. We then have:
Figure 2: Graph with unob- served G. Grey color indi- cates ohservable variables.
Theorem 8. Any estimator T* (X) will incur at least the following estimation error:
- -
+ (1T2(X) - -X" 2 (1/V2) -TxX))l
(4)
The above result shows the necessity of identifying as well. Now we present our positive result on the identifiability when G is hidden too: Re-number the combined space of G Y as We are going to reuse the definition of M4, for each disentangled feature RG: Define the "Kruskal matrix" for each R; as M, k] TP R. R, [ x Y j).
}
By mapping (G = 1,
GG 1, = 2) (G= Gl, Y0 K) IG]K.
8

---

Under review as a conference paper at ICLR 2023
Theorem 9. For Xs in given group 9 E G. with a single informative noisy label, T(X) is identifiable if the number of disentangled and informative features d' satisfy that d' 2 2 1. When we have unknown groups of noise, the requirement of the number of informative and disentan- gled features grows linearly in [G*. We now relate to the literature that implicitly groups X's. We will use X' to denote the space of all possible Xs.
Part-dependent label noise (Xia al., 2020b) discusses part- dert-dependent label noise model where each T(X) can decompose into a linear combination of p parts: T(X) = " (x) T, The motivation of the above model is each X can be viewed as a combination of multiple different sub-parts, and each of them has a certain difficulty being labeled. The hope is that the parameter space (XX) can reduce the dependency between X and T(X). Denote W := {w(X) X E X To put into our result, G| [W|. If W has much smaller space than X,, the condition specified in Theorem would be more likely be satisfied.
DNN approach (Yang et al. 2021) proposes using a deep neural network to encode the dependency between X and (X)... with the only difference being that T (X) is defined as the transition between Y and the Bayes optimal label y*. Define: DNN == {DNN (X) X): X E X}. Similarly, in analogy to our results in Theorem 9 with replacing the hidden variable Y to Y*, |G] will be determined by [DNN]. So long as the DNN can identify the patterns in T(X) and compress the space of DNN(X) as compared to X, the identifiability becomes easier to achieve.
The causal approach (Yao et al. 202I) proposed improving the identifiability by exploring the causal structure. With causal inference, one can identify a more representative and compressed X for each X such that P\ Y, X, X)= = IP XX) Denote & := (X X + X E X3, and |G] = (x).
SOME EMPIRICAL EVIDENCE: DISENTANGLED FEATURES
Most of our results above verified the empirical success of existing approaches from the identifiabil- ity's 's perspective and we refer the interested reader to the detailed experiments in the corresponding references. We now empirically show the possibility of learning disentangled features to help identify the noise transition matrix. We consider three types of encoders that are used to generate features. The first encoder is pre-trained by cross-entropy (CE) loss via a weakly supervised manner which is generally adopted in FW (Patrini et al., 2017b) and HOC (Zhu et al. (021c). However, since the training data noisy, is hard to guarantee that features are disentangled this is our bascline. The second encoder is pre-trained by SimCLR (Chen et al.) 2020) via a self- self-supervised manner. It is shown that the features trained by SimCLR are partly disentangled on some simple augmentation features such as rotation and colorization (Wang et al.) (201cc). The third encoder is trained by IPIRM (Wang) jet al. 2021c) via self-supervised manner which can generate fully disentangled features. After training these three encoders, we fix the encoder and generate features from raw samples to estimate the noise transition matrix using HOC estimator (Zhu et al. 2021c). We evaluate the performance via absolute estimation error defined below: emr = =E Σ [T. - T/al/K². 100, where Î is the estimated noise transition matrix, T is the real noise- transsttanitiion matrix, K is the number of classes in the dataset, which is also the size of the transition matrix. The overall experiments are shown in Table We observe that the estimation error decreases as features become more disentangled which supports our analyses. We defer the details, more experiments, well experiments on comparing training performances using disentangled features, to the supplementary material.
Table 1: Comparison of estimation error for different types of features on CIFAR-10. 10. Each experiment is run 3 times and mean + std is reported. asymm.. asymmetric label noise; inst.: instance-dependee label noise. Numbers noise rates. All the encoders are from ResNet50 backbone.
Feature Type
asymm. 0.3
asymm. 0.4
inst. 0.4
inst, 0.5
inst.
Supervse
14.51 0.4
15.2 : 0.02
8.39 - 0.05
6.91
0.06
6.18 1 0.15
SimCLR
4.42 + 0.01
4.41 1 0.01
2.91
- 0.02
2.55 0.04
2.64 1 0.03
IPIRM
3.73 1 0.02
3.74 1 0.01
2.47 1 0.03
2.20 + 0.02
2.37 1: 0.06
Concluding remarks This paper characterizes the identifiability of instance-level label noise transition matrix. We connect the problem to the celebrated Kruskal's 's identifiability result and present necessary and sufficient condition for the instance-level identifiability. We extend and instantiate our results to practical settings to explain the successes of existing solutions. We show the importance of disentangled and informative features for identifying the noise transition matrix.

---

Under review as a conference paper at ICLR 2023
7 ETHICAL STATEMENT
We are not aware of negative societal consequence of applying our results. But at multiple places of the work, we state the limitations of the setup not mislead readers into misunderstanding our claims. For instance, we discussed the situation when we will have multiple noisy labels and our focus on discretized features. In Section 5.2, we clearly stated our requirement of the disentangled and informative features.
REPRODUCIBILITY STATEMENT
We include the following checklist for the purpose of reproducibility:
1. Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We present the complete proofs in the appendix and have added detailed explanations.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We submitted experiment details in the appendix and the implementations the supplementary materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
REFERENCES
Elizabeth S Allman, Catherine Matias, and John A Rhodes. Identifiability of parameters in latent structure models with many observed variables. The Annals of Statistics, 37(6A))3099-311 2009.
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of machine learning research, 15: 2773-2832, 2014.
10

---

Under review as a conference paper at ICLR 2023
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint 1rX.iv:907.020000 2019.
Dara Bahri, Heinrich Jiang, and Maya Gupta. Deep k-nn for noisy labels. In International Conference on Machine Learning, pp. 540-550. PMLR, 2020.
Antonin Berthon, Bo Han, Gang Niu, Tongliang Liu, and Masashi Sugiyama. Confidence scores make instance-dependent label-noise learning possible. arXiv preprint arXiv:2001.037. 2020.
Antonin Berthon, Bo Han, Gang Niu, Tongliang Liu, and Masashi Sugiyama. Contidence scores make instance mestance-dependent label-noise learning possible. In International Conference Machine Learning, pp. 225-836. PMLR, 2021.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Semi-supervised novelty detection. The Journal of Machine Learning Research, 11:2973-3009, 2010.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Hao Cheng, Zhaowei Zhu, Xingyu Li, Yifei Gong, Xing Sun, and Yang Liu. Learning with instance- dependent label noise: A sample sieve approach. In International Conference on Learning Representations, 2021a.
Hao Cheng, Zhaowei Zhu, Xing Sun, and Yang Liu. Demystifying how self-supervised features improve training from noisy labels. arXiv preprint arXiv:2110.0902 2021b.
Jiacheng Cheng, Tongliang Liu, Kotagiri Ramamohanarao, and Dacheng Tao. Learning with bounded instance-and label-dependent label noise. In Proceedings of the 37th International Conference on Machine Learning, ICML '20, 2020.
Clifford C Clogg. Latent class models. In Handbook of statistical modeling for the social and behavioral sciences, pp. 311-359. Springer, 1995.
Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pp. 954-959, 2020.
Aritra Ghosh and Andrew Lan. Contrastive learning improves model robustness under label noise. In Proceedings of the IEEF/CVF Conference Computer Vision and Puttern Recognition, pp. 2703-2708. 2021.
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Advances in neural information processing systems, pp. 8527-8537, 2018
Bo Han, Gang Niu, Xingrui Yu, Quamming Yao, Miao Xu, Ivor Tsang, and Masashi Sugiyama. Sigua: Forgetting may make learning with noisy labels more robust. In International Conference on Machine Learning, pp. 4006-4016 PMLR, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition. pp. 770-778, 2016.
Irina Higgins, David Amos, David Pfau, Sebastien Racaniere, Loic Matthey, Danilo Rezende, and Alexander Lerchner. Towards a definition of disentangled representations. arXiv preprint arXiv: arXiv:/812.022 1812.02230, 2018.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data- driven curriculum for very deep neural networks on corrupted labels. In International Conference on Machine Learning. pp. 2304-2313. PMLR, 2018.
David Karger, Sewoong Oh, and Devavrat Shah. Iterative learning for reliable crowdsourcing systems. In Advances in neural information processing systems, pp. 1953-1961, 2011.

---

Under review as a conference paper at ICLR 2023
Joseph B Kruskal. More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling. Psychometrika, 41(3):281-299) 1976.
Joseph B Kruskal. Three-way arrays: rank and uniqueness of trilinear decompositions, with applica- tion to arithmetic complexity and statistics. Linear algebra and its applications, 18(2)955-388 1977.
Junnan Li, Richard Socher, and Steven C.H. Hoi. Dividemix: Learning with noisy labels semi- supervised learning. In International Conference on Learning Representations, 2020. URL https://openrevial
net hetpaa/seeeeeeetteooooruoooooog
Xuefeng Li, Tongliang Liu, Bo Han, Gang Niu, and Masashi Sugiyama. Provably end-to-end label-noise learning without anchor points. arXiv preprint arXiv:2102.024000 2021.
Qiang Liu, Jian Peng, and Alexander T Ihler. Variational inference for crowdsourcing, Advances in neural information processing systems, 25:692-700, 2012.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions pattern analysis and machine intelligence, 38(3):447-466 2015.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on paltern analysis and machine intelligence, 3843)4447441, 2016.
Yang Liu. Understanding instance-level label noise: Disparate impacts and treatments, 2021.
Yang Liu and Mingyan Liu. An online learning approach to improving the quality of crowd-sourcing. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling Computer Systems, SIGMETRICS ' 15, pp. 217-230, New York, NY, USA, 2015. ACM. ISBN 978 1 1-0-----533-488666- doi: 10. 70.114557744844.77557774 URL http:://oii..... acm
org 1 14 15 212227774444224
Yang Liu and Jialu Wang. Can less be more? when increasing to--bllaaibinggg label noise rates considered beneficial. 21.
Yang Liu, Juntao Wang, and Yiling Chen. Surrogate scoring rules and a dominant truth serum. ACM EC, 2020.
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. Learning from corrupted binary labels via class-probability estimation. In International Conference on Machine Learning, pp. 125-134, 2015.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in neural information processing systems, pp. 1196-1200 1204, 2013.
Duc Tam Nguyen, Chaithanya Kumar Mummadi, Thi Phuong Nhung Ngo. Thi Hoai Phuong Nguyen, Laura Beggel, and Thomas Brox. Self: Learning to filter noisy labels with seff-ensembling. arXiv preprint ArXiv: 2019.
Curtis Northcutt, Lu Jiang, and Isaac Chuang. Confident learning: Estimating uncertainty in dataset labels. Journal of Artificial Intelligence Research, 70:1373-1411 1411, 2021.
Curtis G Northcutt, Tailin Wu, and Isaac L Chuang. Learning with confident examples: Rank pruning for robust classification with noisy labels. UAI, 2017.
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), July 2017a
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1944-1952, 2017b.
Clayton Scott. A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In AISTATS, 2015.
12

---

Under review as a conference paper at ICLR 2023
Nicholas D Sidiropoulos and Rasmus Bro. On the uniqueness of multilinear decomposition of n-way arrays. Journal of chemometrics, 14(3):229- 2299 2000.
Nicholas D Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E Papalexakis. and Christos Faloutsos. Tensor decomposition for signal processing and machine learning. 1EEE Transactions on Signal Processing. 63(3))335113358, 2017.
Xander Steenbrugge, Sam Leroux, Tim Verbelen, and Bart Dhoedt. Improving generalization for ab- stract reasoning tasks using disentangled feature representations. arXiv preprint arXiv:1811.04785 2018.
Panagiotis A Traganitis, Alba Pages- Zamora, and Georgios B Giannakis, Blind multiclass ensemble classification. IEEE Transactions on Signal Processing, 66 66(18):4777-4752, 2018.
Aaron Van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv e-prints, pp. arXiv-1807, 2018.
Jialu Wang, Yang Liu, and Caleb Levy. Fair classification with group-dependent label noise. In Proceedings of the 2021 ACM Conference on Fairness, Accountabiliry, and Transparency, FAceT 21, pp. 526-536, New York, NY, USA, 2021a. Association for Computing Machinery. ISBN 470349938. doi: 10. 1145/3442188..445591 3442188. 3445915
Qizhou Wang, Jiangehao Yao, Chen Gong, Tongliang Liu, Mingming Gong, Hongxia Yang, and Bo Han. Learning with group noise. arXiv preprint (.Xix:2003.0944: 2021b.
Tan Wang, Zhongqi Yue, Jianqiang Huang, Qianru Sun, and Hanwang Zhang. Self-supervised learning disentangled group representation as feature. Advances in Neural Information Processing Systems, 34, 2021c
Hongxin Wei, Lei Feng, Xiangyu Chen, and Bo An. Combating noisy labels by agreement: A joint training method with co-regularization. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 13726-13735, 2020.
Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: A study using real-world human annotations. arXiv preprint 10Xiv:2110.12088, 2021.
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? Advances in Neural Information Processing Systems, 32, 2019.
Xiaobo Xia, Tongliang Liu, Bo Han, Chen Gong, Nannan Wang, Zongyuan Ge, and Yi Chang. Robust carly-learning: Hindering the memorization of noisy labels. International Conference Learning Representations, 2020a.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang. Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance-dependent label noise. Advances in Neural Information Processing Systems, 33:7597-7610, 2020b.
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 2691- 2015.
Shuo Yang, Erkun Yang. Bo Han, Yang Liu, Min Xu, Gang Niu, and Tongliang Liu. Estimating instance -eeaanceddeendeent label-noise transition matrix using dnns. arXiv preprint 2rXiv:2105.1300 2021.
Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Jiankang Deng, Gang Niu, and Masashi Sugiyama. Dual t: Reducing estimation error for transition matrix in label-noise learning. arXiv preprint arXiv:2006. 07805, 2020a.
13

---

Under review as a conference paper at ICLR 2023
Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Gang Niu, Masashi Sugiyama, and Dacheng Tao. Towards mixture proportion estimation without irreducibility. arXiv preprint arXiv:2002.03673, 2020b.
Yu Yao, Tongliang Liu, Mingming Gong, Bo Han, Gang Niu, and Kun Zhang. Instance-dependent label-noise learning under a structural causal model. Advances in Neural Information Processing Systems, 34, 2021.
Yivan Zhang. Gang Niu, and Masashi Sugiyama. Learning noise transition matrix from only noisy labels via total variation regularization. arXiv preprint wrXiv:2102.02444 2021.
Yuchen Zhang, Xi Chen, Dengyong Zhou, and Michael I Jordan. Spectral methods meet A provably optimal algorithm for crowdsourcing. Advances in neural information processing systems, 27, 2014.
Evgenii Zheltomozhskii, Chaim Baskin, Avi Mendelson, Alex M Bronstein, and Or Litany. Contrast divide: Self-supervised pre-training for learning with noisy labels. In Proceedings the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 1657-1667, 2022.
Xiaojin Zhu. Semi-supervised learning with graphs. Carnegie Mellon University, 2005.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference Machine learning (ICMI-03), pp- 912-919, 2003.
Zhaowei Zhu, Zihao Dong, Hao Cheng, and Yang Liu. A good representation detects noisy labels. arXiv preprint arXiv:21 2021a.
Zhaowei Zhu, Tongliang Liu, and Yang Liu. A second-order approach to learning with instance- dependent label noise. CVPR, 2021b.
Zhaowei Zhu, Yiwen Song, and Yang Liu. Clusterability alternative anchor points when learning with noisy labels. ICML, 2021c
Zhaowei Zhu, Jialu Wang, and Yang Liu. Beyond images: Label noise transition matrix estimation for tasks with lower-quality features. arXiv preprint 2220::220..01273, 2022.
14

---

Under review as a conference paper at ICLR 2023
APPENDIX: IDENTIFIABILITY OF LABEL NOISE TRANSITION MATRIX
The Appendix organized in the following way: Section A the Theorems in the main paper; Section D provides more discussions generic identifiabiity; Section C provides more experiments on learning with noisy labels w.z.t disentangled features and elaborates the detailed experimental settings in the paper.
A OMITTED PROOFS
PROOF FOR LEMMA
1
Proof. Using Bayes rule we easily obtain
P(X = +1) P(X(Y = +1) PP(Y ++18 +1) +P(XYY= = - P(Y = -1f = +1)
(5)
The equality is due to the fact that Y and X are assumed be independent given Y. Similarly:
P(X = -1) = P(X = +1) IP(Y = +1 = =-1) +P(X|Y- -1) P(Y - -1)
(6)
Since both P(X = +1), -1) are unknown, solving Eqn.
5 and 6
we further have
-1) ズー PP + +1 オ_) P(X Y =
(7)
F(XIÝ=+1) =11 - = -1) (1- P(X|Y = +1).
(8)
L
PROOF FOR THEOREM 3
Proof. Further from __, 7. we can solve and derive т_ š- (1-#++
T4 I- establishing
(-(-==-)
1-#_*
the equivalence between identifying #_ with identifying -,, nT. Next show that identifying т_, n is equivalent with identifying (-+
We first show identifying ; suffices to identify fe+, e_ To this,
P(Ý = +1|Y = 1) P(Y = -1/8 = +1)P(Ý- = +1)
PPY =
And:
PPY = --1) 11 = TP(Y = -11 = - = = = -1)
The derivation for P(p -1/ =+1) is entirely symmetric. Since we directly observe IP(Y
- 1)), P( = +1), with identifying F(Y = +11Ý = -1) = - Y +1), we can identify
P(Ý = -1) P(V = - = +1)
Next show that to identify e- it is necessary to identify ( n ). Suppose not: unable to identify n n; but are able to identify (e+,e_). This implies that there exists another pair -",, # { } such that (denote by p = P(Ý +1))
P(Ý +1 = -1)
(9)
π4P + (1 - TT)
(10)
11 (1-
15

---

Under review as a conference paper at ICLR 2023
TT- T--1- -D)
P(Y = - = -11=+++
(11)
(1 T }p + T- (1 P)
T' (1 p)
(12)
(1 - TTP T
By dividing T+, 44. in both the numerator and denominator in Eqn.
(9 and 10
we conclude that
π
x²
(13)
While from Eqn.
11
and
we conclude
π
44
(14)
From Eqn. 13 and (4)
we have
(1 オー ) (1 TT_ ---
(15)
(1 - (1 πT )
(16)
Taking the difference and re-arrange terms we prove
T + n. = -4 + T'
From Eqn. 13 again, taking - on both side we have
(17)
This proves π4 = -4.. Similarly we have T²_ but this contradicts the assumption that [4] is different pair.
PROOF FOR THEOREM 5
Proof. We first prove sufficiency. We first relate our problem setting to the setup of Kruskal's identifiability scenario: Y E 21, Kx} corresponds to the unobserved hidden variable Z. P(Y i) corresponds to the prior of this hidden variable. Each Y,, i 1, .... corresponds to the observation O, K₁ then simply the cardinality of the noisy label space, the context this theorem, 3, corresponding to the three noisy labels we have.
Each y; corresponds to an observation matrix M₁:
Mij,A k] -P(O; = k|Z = j) = P(Ý = =
Therefore, by definition of M2, M3 and T(X), they all equal to T(X): M, = i When T(X) has rank Kx, we know immediately that all rows M1, M2, M3 are linearly independent. Therefore, the Kruskal ranks satisfy
Kr(M)) Kr(M2) Kr(M)) Kx
Checking the condition in Theorem 4 we easily verify
Kr(M)) Kr(M2) + Kr(Ms) 3Kx 2 2Kx +2
Calling Theorem proves the sufficiency.
Now prove necessity. To prove so, allowed focus on the binary case, where
T(X) [ ['=-)))))) (x)_(x) (x)
(x) [x)
Note in above, for simplicity we drop e-, dependency in X. We need to prove less than informative labels will not suffice to guarantee identifiability. The idea to show that the two different set of parameters e-,e+ can lead to the same joint distribution PPY,, P X)
The case with single label is already proved by Example Now consider two noisy labels y, P, We first claim the following three quantities fully capture the information provided by Y1, Y2:
16

---

Under review as a conference paper at ICLR 2023
Posterior: P(Y -1|X)
Positive Consensus: P(V = y22 = +1|X)
Negative Consensus: P(Y1 Y2- = -
This is because other statisties in Vi, X2 can be reproduced using combinations of the three
quantities above:
P(2; = - = 1 - P(2 = =
P(2: +1,Y2 -| IP( +1/X) - = +1|x),
P( -1,222 = =+|X)+ - -Y;
But PP(; - +1|X) = P( - +1[X), since the two noisy labels are identically distributed. The
above three quantities led three equations that depend on e_: denote by 7 == P(Y +1)
Next we prove the following system of equations:
P(Y = +1|X) = y (1- (1-
P( = + = (1- + 71
P(ý =Y2 = 7 c
e1-
To see this:
P( = Y2 = +1|X)
=P(Ýi = Y2 = +1, Y = +1
+ +P( =Yn +1,Y -
=P(Y = =Y2 /===1|y =+1,X) P(Y = +1
+ P(Ý; = = P(Y = -
=7. (1 (1-))²+(1-7)))
The last equality uses the fact that Y1, 822 are conditional independent given Y, so
P((; Y/2 = +1 +1 = X) =
P(Y: = ++1/y = +1, IP(22 = +1,x=+
P(Ý: Y/2 + = -I,
P(Y; +1|Y = -), P(Y
+1|Y -11XX
We can similarly derive for P(2 = Y.2 -1|x).
Now we show the above equations do not identify e For instance, it is straightforward to verify that both of the solutions below satisfy the equations (up to numerical errors, exact solution exists but in complicated forms):
= 0.7, 6+ = 0.2, e_ = 0.2
= 0.8, e 0.242, e = 0.07
The above example proves that two informative noisy labels are insufficient guarantee identifiability.
For completeness we provide rationals for the multi-class case too. The idea is to show that the complete information returned by the single noisy label and two noisy labels do not always guarantee a unique solution.
For the first order information:
IP
x| =
Σ
IPYY k)) -P( = i|y = X)
KE|K]
Σ
P(Y k|X) (x)(
kE|K]
17

---

Under review as a conference paper at ICLR 2023
Enumerating all is, there are K equations, written in matrix form as:
P (T(X)) PP
where P is the vector form for - - 1 = ; P(Y K|X) and P is the one for
P(Y = k[)).
For the second order information
P(Y i, j|x)
Σ
P(Y = k[x) PP(; = i|Y =
j/y = X)
kE|K]
Σ
P(Y k[x) (X) (X)
kE|K]
Enumerating pairs of (i,j) we have K equations, written in matrix form as:
C (T(X)) A TX()
where in above C' is a K K matrix with the (i.j)-th entry being P( i,Yo -|x); is diagonal matrix with Aa = IP(Y = klX).
Notice that
Σ P(Y = -i =]]x) IP(Y =
and
PYPY= = xIX Tx((X) (xx()== ME[K]
Σ P(Y - -x,)) Tr(())
KE[K]
know that for every K equations from the second order information, there is at least one redundant equation. That is to conclude that we have at most K + K2 K = K2 independent equations. K² K unknown variables. So the
Nonetheless, have K(P(Y k|X)) (T equations are under-determined. Therefore we conclude for the general K, there exists cases two labels will not define unique solution. For instance, for K = 3, two sets of parameter settings will return us the same observed distribution for two labels:
easily find the following
Parameter setting 1:
0.6
0.2
0.2
[P-YY = P()) = [0.35, 0.33,.03) T(X)
0.175
0.65
0.175
0.15
0.15
0.7
Parameter setting 2:
0.65
0.175
0.175
[P(Y = - 3[X]] = [0.31, 0.31,,.34,0.333 0.35), T(X),
0.175
0.65
0.175
00.175
0.175
0.65
Similar examples can be obtained by searching through the solutions space of the equations.
PROOF FOR THEOREM 6
Proof. In the unstructured model, we first show that, with large N, with high probability, each X's will present at least 3 times. Denote by Nx the number of times X appears in the dataset. Then
N Nx
Σ 1[x 1=1
X], [[Nx] = qx N
(18)
ExEx 4x
When N is large enough such that N inequality we have
ExEx ax minx qx
have E[Nx] > 4. Then using Hoeffding
P(Nx 33 exp(-2N)
18

---

Under review as a conference paper at ICLR 2023
Using union bound (across N samples), it implies that with probability at least Nerppp-p22 -2N), Nx 2 3, XX:
PINx >
= 3 s 3X) < - Nerp(-2N)
(19)
This further implies that with probability at least 1 - N (erp(-22 we have Xi = X2 X for each X: Their distance clearly falling below the closeness threshold e. Therefore they will share the same true label.
Note that we are not imagining the exact same data appearing three times, but rather that three different data that happen to have the same pattern X that appeared three times ([2]). For instance, these three Xs can correspond to three independent users trying to apply for credit card and ending up having the same application profiles (e.g., age, salary range, education level etc); it can also be three similar cat images ended up with the same encoding of the features.
PROOF FOR THEOREM 7
Proof. The d' features and the noisy label Y jointly give us d' + independent observations. Denote by K2 maxxeg Kx. In Kruskal's setup, Y E {1, ..., .?) will then correspond. to the unobserved hidden variable Z. If the noisy label is informative we know that Kr(T(XX) = K s K.
Then checking Kruskal's condition we have:
(r(T(X)) Σ Kr(M) 2 K2 +2. d' 2 KG + K2 + d' = 2Kg + +
Calling Theorem we establish the identifiability.
PROOF FOR THEOREM g
Proof. By definition
[1(( = ΣΣ (ilii - -
(20)
Easy to show that
- (X)]] +173((X) (X)Il
(i. - T(..)))
ΣΣ
(T2(i, (()
[Tlii - + +
ΣΣ (Teli - J1)
Σ Σ
- T(i.)) + (Tz
(Dropping the cross prosuct term which is positive)
19

---

Under review as a conference paper at ICLR 2023
Then prove that
[Ti - T (X)lle + (XT2(X)) T (X)Ile
Tili. Ti + Tell.31) 2
+ [ali..]] Ti T2li, 5] 2
2
2
(minimum distance is at half)
Ti j] T2(
2
2
ΣΣ
[Tili,g] - )2)
V2
(xx)]l
V2
PROOF FOR THEOREM 9
Proof. The proof is straightforward by checking Kruskal's identifiability condition:
Kr(T(X)) Σ
( 2 -1 = K + d' +1
Note |G|-K -KI-Kin is the size of space for the unobserved variable (GY renumbered as 21, G]
B GENERIC IDENTIFIBIILITY
We provide a bit more detail for the discussion on generic identifiability left in Section 5.2 Theorem 10. With single informative noisy label, T(X) is generically identifiable for each group g E G if the number of disentangled feature d' satisfies that d' 2 [log2 2k and T; 2
Proof. We first reproduce relevant theorem in Allman et al.
2009
Theorem 11. Allman et al. 2009) When = (3 independently observations), the model parameters generically identifiable, up to label permutation, if min K2g k1) + min( (K2, n2) + min K2 Ka) 2 2Kg + 2
(21)
Based on the above theorem have the following identifiability result:
Grouping d' features evenly into two groups, each corresponding to meta variable/fcature:
d'
R
Rr X;
R j=dī+1
II
t=1
Denote feature dimensions of each group di, dz:
2
2 logg
2k +1
2K* + 1
(22)
T=1
Similarly 7 Kx+2 2
Denote by Mf. Mn the two observation matrices for the grouped variables
Mí P(R; R$ [ j), = 1,2.
Then:
2K +1
Kr(T(X)) + Kr(M;) Kr(M))) > 1
=2K + +
2
which again satisfied the identifiability condition specified in Theorem 4
20

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Key Steps of HOC
1: Input: Noisy dataset: D = {(In, ) IEEM, with disentangled features. //Find 2-NN using similarity function Sim(2,, 2").
2: With 1 Sim ) as the distance metrie:
{Hn. Mns Mn2), Vn) + Get Get2NN(D);
//Count first-, second, and third-order consensus patterns:
3: (al1), af3) c.3)) + Count eeq (gn. Ir. ), Vn))
//Solve equations:
4: Find T such that match the counts cll1,, el..).
C MORE EXPERIMENTS
In this section, we elaborate the detailed experiment setting and perform more experiments w.r.f. disentangled features.
C.I EXPERIMENT SETTING FOR TABLE
Label Noise Generation The label noise of each instance characterized by (iş(X) P(Ý j| Y i). In this paper, consider two types of label noise: asymmetric label noise (Han cet al. 2018 Wei et al. 2020) and instance-dependent label noise (Cheng et al. 202 la Zhu et al. 2021bp. For asymmetric label noise, T(X) T. each clean label is randomly flipped to its adjacent label w.p. c, where e is the noise rate, i.c., Ta = c. Tis + 12 = 1, (i + 1)x == i mod K K+1, 1. For instance-dependent label noise, the generation of noisy labels also depends the features. We follow CORES (Cheng et al. (021a) to generate instance-dependent label noise. The generation process is detailed Algorithm 2 With these definitions, asymm./inst. in Table [ denotes sssymmetric/inssane--eeeee
label noise with noise rate e.
Model pre-training. The network structures of all the three encoders in Table are ResNet50 (He et al. 2016). Note that the encoders which generate features to estimate transition matrix can prained on different dataset. For example, HOC (Zhu et al., (021c) utilizes ImageNet pre-traine pre-trained encoders to generate features for CIFAR. Thus, following the pipeline of disentangled feature generation (Wang et al.) (021c). we pre-train all the three encoders on CIFAR 100 dataset and generate feature for CIFAR TO to estimate transition matrix. The first encoder is trained under 0.1 symmetric label noise rate to simulate the weakly-supervised features while the second and third encoder is trained via self-supervised learning (SSL). Recall the goal of SSL is to learn good representation without accessing labels. In this paper, we adopt SimCLR (Chen et al. 2020) and IPIRM (Wang et al. 2021c) to perform SSL pre-training. SimCLR, a representative work on SSL literature, learns a good represention based on InfoNCE loss (Van den Oord et al.) 2018).
However, it is shown that the features learned by SimCLR are only partly disentangled on some simple augmentation features such as rotation and colorization (Wang er al.) 2021c). Thus IPIRM proposes learning algorithm that embeds InfoNCE loss into IRM (Invariant Risk Minimization) framework (Arjovsky et al. 2019) to learn fully disentangled features. We train SimCLR model and IPIRM model by referring official codebase IPIRM The pre-trained models, as well as evaluation code are all released in the supplementary material.
Key steps of HOC
Estimation error of Transition matrix. After training these three encoders, we fix the encoder and generate features from raw samples to estimate the noise transition matrix using Global HOC estimator ZZhu et al. 2021c). The parram-paraettes for estimating transition matrix are consistent with official implementation of H optimizer: Adam, learning rate: 0.1, number iterations: 1500. After training, we evaluate the performance via absolute estimation error defined below:
ΣK
Σ
[ Ti.l
em
100,
K2
hhttss//gthub.co//WaggcC httpss//ggttih..om//CCCCCAAAAAA
21

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Instance- Label Noise Generation
Input:
1: Clean examples (Zn, Yn Un)==1 Noise rate: E; Size of feature: S; Number of classes: K.
Iteration:
2: Sample instance flip rates to. from the truncated normal distribution (e, 0.12, [o. 1));
3: Sample W RSK from the standard normal distribution (N,
for n
1 to N do
4:
p Zn W
I/ Generate instance dependent flip rates. The size of p is x K.
5:
Pv. = 00
I/ Only consider entries different from the true label Let gn be the probability of getting wrong label
6:
p On softmax(p)
7:
Pv. = 1- On // Keep clean w.p. 1 Qn
8:
Randomly choose label from the label space noisy label th according to p;
end for Output:
9: Noisy examples (zi, Dn)am1
Table 2: Comparison of test accuracy CIFARIO by using the estimated transition matrix.
Methods
inst. 0.3
inst. 0.4
inst. 0.5
inst. 0.6
FW (SimCLR)
66.61
65.82
64.51
62.81
FW (IPIRM)
73.24
72.54
71.33
69.42
Table 3: Comparison of test accuracy CIFAR100 by using different DNN initialization.
Methods
inst. 0.3
inst. 0.4
inst. 0.5
inst. 0.6
CE (random init)
43.47
35.17
27.07
18.25
CE (SimCLR init)
58.95
49.7
36.87
25.07
CE (IPIRM init)
64.92
56.18
43.75
30.36
where f' is the estimated noise transition matrix, T is the real noise-transition matrix, K is the number of classes in the dataset.
C.2 TRAINING PERFORMANCE USING ESTIMATED TRANSITION MATRIX
We can further use the estimated transition matrix to perform forward loss correction (FW) (Patrini et al., (017b). Table 2 records the performance of FW by using the estimated transition matrix of SimCLR and IPIRM. The paper-parameters for all the experiments in Table 2 are the same: optimizer: SGD, training epochs: 100, learning rate: 0.1 for first 50 epochs and 0.01 for last 50 epochs, batch-size: 256. From the results, we can observe that the test accuracy increases as features become disentangled.
C.3 INITIALIZING DNN USING DISENTANGLED FEATURES
Except for estimating transition matrix, we can directly use disentangled features to perform training on noisy dataset. Table 3 shows the effect using disentangled features as DNN initialization on CIFAR100. The typer--arametee From the results, We can observe that even with vanilla Cross Entropy loss, the disentangled features still beneficial to the performance.
for all the experiments in Table are consistent with Table 2
22

---

Under review as a conference paper at ICLR 2023
Table 4: Comparison of test accuracy CIFARIO by using different transition matrix.
CE
FW with 7
FW with 72
FW with 73
Test accuracy
79.34
82.62
81.65
78.13
C.4 VERIFYING THE IMPORTANCE OF CHARACTERIZING THE IDENTIFIABILITY OF THE LABEL NOISE TRANSITION MATRIX
C.4.1 CIFARIO EXPERIMENT
Our first experiment show that when estimated transition matrices is far from the ground-truth matrix, it may make model perform worse even compared to the baseline (vanilla training with Cross Entropy).
Experiment setting: The training framework with transition matrix is followed from FW (Patrini et al., 2017b). The dataset is CIFARIO and the network structure is ResNet34, The arper-paramttrss follows: batchsize (64), learning rate (0.1 for first 50 epochs and 0.01 for last 50 epochs), optimizer (SGD). For a randomly selected set instances (0% the population), we generate noisy labels using the following transition matrix:
0.9
0.011
0.011
0.011
0.011
0.011
0.011
0.011
0.011
0.011
0.019
0.82
0.019
0.019
0.019
0.019
0.019
0.019
0.019
0.019
0.028
0.028
0.74
0.028
0.028
0.028
0.028
0.028
0.028
0.028
0.037
0.037
0.037
0.66
0.037
0.037
0.037
0.037
0.037
0.037
0.045
0.045
0.045
0.045
0.58
0.045
0.045
0.045
0.045
0.045
T P("
0.054
0.054
0.054
0.054
0.054
0.51
0.054
0.054
0.054
0.054
0.063
0.063
0.063
0.063
0.063
0.063
0.43
0.063
0.063
0.063
0.071
0.071
0.071
0.071
0.071
0.071
0.071
0.35
0.071
0.071
0.08
0.08
0.08
0.08
0.08
0.08
0.08
0.08
0.27
0.08
0.088
0.088
0.088
0.088
0.088
0.088
0.088
0.088
0.088
0.2
The above transition matrix 7' is uniform off-diagonal with diagonals evenly spaced over [0.9, 0.2].
which is the ground-truth -atun transition matrix in our setting. The remaining unselected instances will enjoy a T = O.
We perform experiments using the following three uniform off-diagonal transition matrix with forward loss correction (Patrini et al. 2017b):
Ti with diagonals evenly spaced over [0.9, 0.2]
T2 with all diagonals 0.4.
T's with diagonals evenly spaced over [0.2, 0.9]
where T; is the ground-truth transition matrix while T3 is far from the ground-truth. The results listed Table
It can be observed that when using Ts, the performance is worse than vanilla training with Cross Entropy, suggesting the importance of identifying and estimating the noise transition matrix.
C.4.2 GAUSSIAN EXPERIMENT
Our second experiment is to show that in some settings, the transition matrix is hard to estimate correctly, which suggests the importance identifiability. Consider a simple setting for binary classification and set of instances generated according to the following setups:
-X 3)) where N denotes Gaussian distribution with mean 0 and variance 3.
PPY = 1|x) sigmoid(X) Ite-x
23

---

Under review as a conference paper at ICLR 2023
Table 5: Comparison of test accuracy for CE and FW.
CE
FW with estimated transition matrix
Test accuracy
83.22
83.31
We generate X and Y following the above procedure and define the ground-truth transition matrix for generating Y from Y. Our goal is to examine whether we can
0.9 0.1
T = Y, =
0.2
0.8
estimate the correct transition matrix using (X,Y). Y).
Experiment setting: The training framework for estimating transition matrix is followed from FW
(Patrini et al. 2017b). We randomly sample 5000 (I, y) pairs from the data generating procedure
and using T P(
0.9
0.1
generate Y from Y. The network structure is simple 0.8
0.2
FCN (fully connected network tructure) with one hidden layer (10 nodes) and ReLU activation. The hyper-parannn parameeassssssss are follows: learning rate (0.01 for 100 epochs ), optimizer (SGD). We perform the experiments with 30 runs and record the average performance in Table 5
From Table 5 we can see that FW has very little gain compared vanilla Cross Entropy training. We then calculate the average estimated transition matrix:
0.983
0.017
Peatimated
0.008
0.992
We find that T eattmaatdd is nearly as the same the identity matrix, suggesting that in this setting, FW is hard to estimate noise transition matrix correctly and contributes less to the performance.
0.6
0.2
0.2
[P(Y = P(X),P( = 2(X), = =3|)] = [0.35, 0.35, 0.3), T(X) =
0.175
0.65
0.175
0.15
0.15
0.7
24


Reviews:
[{"review_id": "oKBh4gnf_Z", "reviewer": "Reviewer_4T3g", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "Pros:\n\n-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.\n\nCons:\n\n-**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.\n\n-**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?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Se6DwP0Az8", "reviewer": "Reviewer_GkBx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "strength_and_weaknesses": "Strengths:\nIdentifiability 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.\n\nQuestions/Weaknesses:\nAre 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).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NtqTpcMzL7J", "reviewer": "Reviewer_G5Yr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "--Strength--\n1. It characterizes the identifiability of the label noise transition matrix for the generic case at the instance level.\n\n--Weakness--\n1. 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? \n2. This paper lacks experiments to verify the importance of characterizing the identifiability of the label noise transition matrix at the instance level.\n3. The format of the cited paper is not proper and seems to lack brackets.\n4. 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?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "59BWhv4j__", "reviewer": "Reviewer_14GL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n", "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.\n\n===post-rebuttal===\nAfter 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.", "strength_and_weaknesses": "### Strength\n- 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.\n- Experiments are conducted to show that the disentangled features help identify the transition matrix.\n\n### Weaknesses\nMy main concern about the paper is the significance of the theorems presented in Section 5 and the clarity of the presentation.\n- 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.\n\t- 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).\n\t- 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$.\n\n\t- 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.\n- about the clarity of presentation:\n\t- 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.\n\t- 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.\n\n### Minor points:\n- It would be better to use \\citep instead of \\citet, if the cited paper does not appear as a component of the sentence.\n- Page 6: the third line of the proof sketch, there is an additional \".\" after $Y\\in\\\\{1,2,\\dots,K\\\\}$.\n- Page 6, first sentence in Section 5: focuses--> focus\n- 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.\n- Figure 2:\"Grey\"--> \"Grey color\"\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject