An information-theoretic framework for learning models of instance-independent label noise
Authors: Xia Huang
Kai Fong Ernest Chong
Venue:  (2021)
Keywords: label noise
noise transition matrix
entropy
information theory
local intrinsic dimensionality

Abstract: Given a dataset $\mathcal{D}$ with label noise, how do we learn its underlying noise model? If we assume that the label noise is instance-independent, then the noise model can be represented by a noise transition matrix $Q_{\mathcal{D}}$. Recent work has shown that even without further information about any instances with correct labels, or further assumptions on the distribution of the label noise, it is still possible to estimate $Q_{\mathcal{D}}$ while simultaneously learning a classifier from $\mathcal{D}$. However, this presupposes that a good estimate of $Q_{\mathcal{D}}$ requires an accurate classifier. In this paper, we show that high classification accuracy is actually not required for estimating $Q_{\mathcal{D}}$ well. We shall introduce an information-theoretic-based framework for estimating $Q_{\mathcal{D}}$ solely from $\mathcal{D}$ (without additional information or assumptions). At the heart of our framework is a discriminator that predicts whether an input dataset has maximum Shannon entropy, which shall be used on multiple new datasets $\hat{\mathcal{D}}$ synthesized from $\mathcal{D}$ via the insertion of additional label noise. We prove that our estimator for $Q_{\mathcal{D}}$ is statistically consistent, in terms of dataset size, and the number of intermediate datasets $\hat{\mathcal{D}}$ synthesized from $\mathcal{D}$. As a concrete realization of our framework, we shall incorporate local intrinsic dimensionality (LID) into the discriminator, and we show experimentally that with our LID-based discriminator, the estimation error for $Q_{\mathcal{D}}$ can be significantly reduced. We achieved average Kullback--Leibler loss reduction from $0.27$ to $0.17$ for $40\%$ anchor-like samples removal when evaluated on the CIFAR10 with symmetric noise. Although no clean subset of $\mathcal{D}$ is required for our framework to work, we show that our framework can also take advantage of clean data to improve upon existing estimation methods.

Under review as a conference paper at ICLR 2021
AN INFORMATION-THEOREIC FRAMEWORK FOR LEARNING MODELS OF INSTANCE-INDEPEDDENY LA- BEL NOISE
Anonymous authors Paper under double-blind review
ABSTRACT
Given dataset D with label noise, how do we learn its underlying noise model? If we assume that the label noise is inaane--ndeeeneett, then the noise model can be represented by a noise transition matrix Qp. Recent work has shown that even without further information about any instances with correct labels, or further assumptions on the distribution of the label noise, it is still possible to estimate QD while simultaneously learning classifier from D. However, this presupposes that good estimate of QD requires an accurate classifier. In this paper. we show that high classification accuracy is actually not required for estimating Qp well. We shall introduce an -otemattioo--horeetic. solely from D (without additional information or assumptions). At the heart our framework is discriminator that predicts whether an input dataset has maximum Shannon entropy, which shall be used multiple new datasets D synthesized from D via the insertion of additional label noise. We prove that our estimator for Qd is statistically consistent, in terms of dataset size, and the number of intermediate datasets D synthesized from D. As a concrete realization of our framework, we shall incorporate local intrinsic dimensionality (LID) into the discriminator, and we show experimentally that with our LID-based discriminator, the estimation eтror for QD can be significantly reduced. We achieved average Kullback Leibler (KL) loss reduction from 0.27 0.17 for 40% anchor-like samples removal when evaluated on CIFAR10 10 with symmetric noise. Although no clean subset of D is required for our framework to work, we show that our framework can also take advantage of clean data to improve upon existing estimation methods.
framework for estimating QD
INTRODUCTION
Real-world datasets are inherently noisy. Although there are numerous existing methods for learning classifiers in the presence of label noise (e.g. Han et al. (2018); Hendryeks al. (2018); Natarajan ct al. (2013); Tanaka et al.] (2018)), there is still a gap between empirical success and theoretical understanding of conditions required for these methods work. For instance-indppende
label noise, all methods with theoretical performance guarantees require a good estimation of the noise transition matrix as a key indispensable step (Cheng et al. 2017 [iidal et al. 2016 Patrini et al. 2017]] Thekumparampil et al. [2018] Xia et al. (2019). Recall that for any dataset D with label noise, we can associate to it noise transifion matrix QD. whose entries
conditional probabilities p(y]=) that randomly selected instance of 'D has the given label y. under the condition that its correct label is 2. Many algorithms for estimating QD either require that small clean subset Delean of D is provided (Liu & Tao 2015 Scott 2015). or assume that the noise model is a mixture model (Ramaswamy al. [016)] Yu al. 2018), where least some anchor points are known for every component. Here, "anchor points" refer to datapoints belonging to exactly one component of the mixture model almost surely (cf. Vandermeulen et al. (2019), while "clean" " refers to instances with correct labels.
Recently, it was shown that the knowledge of anchor points Delean is not required for estimating Qp. The proposed approach, known as T-Revision (Xia et al. 2019), learns a classifier from D and simultaneously identifies micho--like instances in D, which are used iteratively to estimate Qp. which in turn is used to improve the classifier. Hence for T-Revision, a good estimation for Q is inextricably tied to learning classifier with high classification accuracy. In this paper, propose

---

Under review as a conference paper at ICLR 2021
framework for estimating QD solely from D, without requiring anchor points, clean subset, anchor-like instances. In particular, we show that high classification accuracy is not required for a good estimation of QD. Our framework is able to robustly estimate QD at all noise levels, even in extreme scenarios where anchor points are removed from DD or where 'D is imbalanced.
Our key starting point is that Shannon entropy and other related information -theoretic concepts can be defined analogously for datasets with label noise. Suppose we have a discriminator that takes any dataset D' as its input, and gives binary output that predicts whether D' has maximum entropy. Given D. a dataset with label noise, we shall synthesize multiple new datasets D by inserting additional label noise into D, using different noise levels for different label classes. Intuitively, the more label noise that 'D initially has, the lower the minimum amount of additional label noise we need to insert into to reach near-maximum entropy. We show that among those datasets D that are predicted by & to have maximum entropy, their associated levels of additional label noise can be used to compute a single estimate for Qp. Our estimator is statistically consistent: We prove that by repeating this method, the average of the estimates would converge to the true QD.
As a concrete realization of this idea, we shall construct & using the notion of Local Intrinsic Dimensionality (LID) (Houle 2013 2017a|b) Intuitively, the LID computed at a feature vector is an approximation of the dimension of a smooth manifold containing v that would "best" fit the distribution D in the vicinity of v. LID plays fundamental role in important 2018 breakthrough in noise detection (Ma et al. 2018c), wherein it was empirically shown that sequences of LID scores could be used to distinguish clean datasets from datasets with label noise. Roughly speaking, the training data for & consists of LID sequences that correspond to multiple datasets synthesized from D. In particular, we show that & can be trained without needing any clean data. Since we are optimizing the predictive accuracy of Φ, rather than optimizing the classification accuracy for D, we also do not require state-of-the-as architectures. For example, in our experiments on the CIFAR- 10 dataset (Krizhevsky et al., 2009), we found that LID sequences generated by training on shallow "vanilla" convolutional neural networks (CNNs), were sufficient for training
Our contributions are summarized as follows:
framework for estimating the noise transition matrix of any dataset DD with cestance-indepencee label noise. We do not make any assumptions on the structure of the noise transition matrix.
We introduce an -nformation-thheorticc-
We prove that noise transition matrix estimator is consistent. This is the first-ever estimator that is proven to be consistent without needing to optimize classification accuracy. Notably, our consistency proof does not require anchor points, clean subset, or any anchor-like instances.
We construct an LID-basee -bsdd discriminator & and show experimentally that training a shallow CNN generate LID sequences is sufficient for obtaining high predictive accuracy for t. Using our LIID-basd discriminator 4 our proposed estimator outperforms the state-of-the-art methods, especially in the case when anchor-like instances are removed from D.
Given access to a clean subset Deleann we show that our method can be used to further improve existing competitive estimation methods.
2 PROPOSED INFORMATION- FRAMEWORK
Our framework hinges on a simple yet crucial observation: Datasets with different label noise levels have different entropies. Although the entropy of any given dataset D is (initially) unknown to us, we do know, crucially, that complete uniformly random relabeling of D would yield a new dataset with muximum entropy (which we call "baseline datasets"), and we can easily generate multiple such datasets. We could also use partial relabelings to generate a spectrum of new datasets whose entropies range from the entropy of D. to the maximum possible entropy. We call them "a-increment datasets", where a is a parameter that we control. The minimum value amin for a, such that an a-increment dataset reaches maximum entropy, would depend the original entropy of D. See Fig. for a visualization of the spectrum of entropies for a-increemnt datasets and baseline datasets.
Our main idea is to train a discriminator & that recognizes datasets with maximum entropy, and then use & to determine this minimum value amin- Once this value is estimated, we are then able to estimate QD. Specific realizations of our framework correspond to specific designs for $. An
2

---

Under review as a conference paper at ICLR 2021
intact CIFAR-10 Symmetric 20%
Symmetric 50%
Symmetric 80%
Pairwise 45%
random seed:
4096
235
4096
235
4096
235
4096
235
0.75
0.60
0.60
0.854
0.45
0.30
0.877
baseline (maximum
0.15
entropy)
0.00
A visualization of the entropy maximization process. We illustrate the noise transition matrices of DILNs as heat maps. The intact CIFAR-10 dataset is used as the underlying clean dataset, and four noise models are considered (symmetric 20%/50%/88% noise and pairwise 45% noise), which are shown here as four pairs of columns. The first four rows depict heat maps for a-increment DILNs, where a (a..... a.) for four values 0.0, 0.6, 0.854, 0.877. The last row depicts heat maps for baseline DILNs, which have expected maximum entropy. Note that the minimum value amin for a, such that a discriminator would find a-increment DILNS "indistinguishable" from baseline DILNs, would depend on the base noise model that the a-increment DILN is derived from. From this figure, we are able to infer, for example, that for symmetric noise models, amin = 0.877 for base noise level 50%, while in contrast, amin & 0.854 for base noise level 80%. In general, different noise levels correspond to different minimum values for a.
Figure 1:
.........
illustration of our framework using LID-based discriminators is given Fig. 2 details on LID-based discriminators can be found in Section 3 and will be further elaborated in the appendix.
Throughout this paper, given any discrete random variables X,Y, we shall write px (x(x) and pxly (xly( mean Pr(X- 2) and Pr(X- x| = y) respectively. We assume that the reader is familiar with the basics of information theory; see Cover & Thomas 2012) for an excellent introduction.
2.1 ENTROPY OF DATASETS WITH LABEL NOISE
Given D a dataset with instance-inde instance-independent label noise (DILN), let be its set of all label classes. and let Y (resp. Z) be the given (resp. correct) label of randomly selected instance X of D For convenience, we say that D a DILN with noise model (Y (Y)Z;A) The noise transition matrix of D is matrix QD whose (i, entry is R. py Py 2(,5)) i). We shall define the entropy of D by
H(D) = ΣpZ(i) pZ(i)
Σ
D log q..5"
D
SEA
JEA
Notice that (D) is precisely the conditional entropy Y given Z. (We use the convention that 0 log 0 = 0.) Hence, it is easy to prove that 0 < H(D) S log [A]. In particular, H(D) 0 if and only if every pair of instances D in the same class have the same given labels. Note also that D has maximum entropy log [A] if and only if every entry of QD equals | (i.e. the given labels of D are completely noisy). Thus, (D) could interpreted as a measure of the label noise level of D.
'Every datapoint of 2> is pair (x, y). where x is an instance, and y is its given label, which may differ from the correct label associated to x. Note that 2 is function of X. and Y is random function of Z. By instonce-indepente lahel noise, mean that Pr(Y 7/ 2, X x) Pr(Y y 2). A more particular, DIIN includes its noise model.
detailed treatment of DILNS be found in Appendix

---

Under review as a conference paper at ICLR 2021
airplane
automoblie
4st ...
921
deer
average
Qo
A dalaset with unknown label By injecting
The final estimate Op computed es the average of all intermeciatte estimalles
it,, synthesize different new datasels and generate LID secuences from them. Here used CIFAR-10 for visualization.
63
Each dotted box represents discriminator trained collection of LID sequences, ublained via randon seeus. UD sequee wes sledd from each randurm seed ane depicted a plot. The three plots shown represent collect vely the training data for single discriminator. Each wall-trained discriminator produces single internediate estimate.
An overview of the proposed intormation-thhoreee framework, using LID-based discrimi- nators as a concrete example. Given an input dataset with instance-independent label noise, several collections of new datasets are synthesized from D. These synthesized datasets are "derived" via different partial relabelings (and hence have different entropies). The synthesized datasets in each collection are further processed to create training data for a single discriminator. In this illustration, LID sequences from the synthesized datasets become training data for each discriminator, Every discriminator generates single intermediate estimate for the noise transition matrix Qp. The final estimate is computed as the mean of all intermediate estimates.
Figure 2:
A derived DILN of 'D shall mean a DILN D' with noise model Z for some Y' independent of Z, such that both D, D' have the same underlying of instances, given in the same sequential order. For example, DD' could be "derived" from D by inserting additional ietance-independee label noise, in which case D' can be interpreted partial relabeling of D. For convenience, we say that DD' is Y' derived DILN of DD
2.2 SYNTHESIS OF NEW DATASETS FROM D
Let D be DILN with noise model (Y|2;A) Without loss of generality, assume A = (l....,kk assume that D has N instances, and write QD = ( The correct labels for the instances fixed and unknown to us, hence all entries of QD fixed constants with unknown values. Our goal is to estimate Qd. As alluded to earlier, we shall be synthesizing two types of datasets from D.
The first type is what call baseline dataset, described follows: Let 2 be random dataset obtained from D by replacing the given label of each instance of 'D by label chosen uniformly at random from A. Hence D is random DILN with expected entropy log & (i.e. maximum entropy), which we shall denote by D Dmax = E(D] The noise transition matrix Q= = [Q'ylisijss
D is random matrix whose entries Q¹,, = (1 + Fi.s)) are random variables, where each "error" Fi is random variable with mean 0. Any observed D is called baseline DILN of D.
The second type is what we call an a-increment dataset, where a (a1...., ag) is a vector whose entries satisfy select uniformly at random o; x 100% of the instances with given label i, and reassign each selected given label to one of the remaining k 1 classes, chosen uniformly random. Hence D. is random DILN, and its noise transition matrix QD. = [Q"g]isissk is random matrix whose entries
og for all i. Let D, be obtained from D follows: For each 1 < i k
0i = =1, -g))
Σ a, - (1 BXy) (for all 1 S i < k) 1SECk [f)
(1)
are random variables, where each "error" EYg is a random variable with mean 0. Any observed D, called a-increment DILN of D.
4

---

Under review as a conference paper at ICLR 2021
2.3 UNDERLYING INTUITION FOR DISTINGUISHING BASELINE DILNS
Suppose we have a discriminator & that is able to predict whether an input DILN is a baseline DILN of D. We could try, as input to p, a-increment DILN D' of D for different values of a. For any given a, we could try, as input to O multiple observed values of the random DILN Da- Intuitively, the values of a for which "most" of the observed values for D. are predicted by & be baseline DILNs, give non-trivial information about QD. In this subsection, we explain the underlying intuition for how & can be trained, without requiring any knowledge of the correct labels Z.
Let Do be a bascline DILN, and let D De be a-increment DILNs for =a a.))...,,a (()) respectively. Intuitively, if (1)), a (0) cover a sufficiently wide range of vectors, then most of the DILNs among 1i..... De, would have entropies that are not near maximum entropy and hence would (in principle) be distinguishable from baseline DILNS. Ideally, we would want to train a discriminator & using baseline DILNS as "positive" data, and a-increment DILNS as "unlabeled" data, via some pusitive-unlabele data (i.e. where each DILN is a single datapoint for training 4) may not necessarily be a good representation for the training data. Hence, we introduce the notion of a separable random function g. where effectively, we shall use g to generate the training data for + (by applying g on the DILN).
learning algorithm. However. having entire datasets as training
Our definition for the "separabilityy" of relies on (a suitable analog of) the asymptotic equipartition property (AEP) from information theory, which is a key ingredient proving Shannon's 's channel coding theorem. This AEP can be interpreted as a rigorous formulation of the idea that "typical" sequence of observed values for r i.i.d. random variables would belong to a tiny fraction of all possible sequences of observed values, when is sufficiently large. This notion of "typicality" can be explained with the example of flipping biased coins. Suppose we have two coins, with probabilities 0.1 and 0.6 respectively, for getting heads. Toss each coin total of r times, and record the corresponding sequence of outcomes. Now repeat the process multiple times to get multiple sequences, each of length If is sufficiently large, then with high probability, a randomly selected sequence for the first (resp. second) coin would have heads for x 0.1 (resp. & 0.6) of the outcomes; such sequences form only a vanishingly small fraction of all possible sequences. Hence, if we repeatedly generate these sequences, then with high probability, we would be able to distinguish our two coins.
We define g to be an -vauue random function. If (Po) is invoked r times, then we get a randomly generated sequence of length r, where each entry is a vector in Rd; this resulting output sequence shall be treated as a single datapoint in the "positive" class, for training क. Analogously, for each 1 < i < f, we shall invoke ((D,) total of r times, and treat the resulting output sequence (of length r) to be a single "unlabeled" datapoint for training Q. We repeat this process to generate our training data for O. If r is sufficiently large, then with high probability, each output sequence (datapoint for Φ) would be a typical sequence, whose statistics is based on the input DILN. Informally, we define g to be "separable" if distinct DILNs have distinguishable typical sequences for sufficiently large
2.4 DISCRIMINATORS FOR D AND ESTIMATORS FOR QD
We now formalize our intuition presented in Section 2.3 Let D [D] be the set of all derived DILNs of D, and let 1[[D] be the set of all possible underlying datasets for D (D) (i.e. we throw away information about the associated noise models). For notational ease, DILN D' could be an element of either O(D) or I(D).. Every D' [D is uniquely determined by its sequence of given labels (J1,..., ,,,,, which we call the labeling of D'. We think of (y1..... .N)
relabeling of D. generated from some (possibly unknown) noise model A)). Hence, Li(D] is a finite set of size &N Formally, random derived DILN of 'D is discrete random variable V D (D) I(D) defined on some distribution on (D) We shall also define a map fmatri with domain DDD). given by D' + QD.
A discriminator for D is a prediction model & that takes any D' in S(D as its input and gives score & (D') in [0, 1). which could be interpreted as the likelihood that D' is a baseline DILN of D. We say that DD is predicted "positive" if @<D')= 2 0.5, and predicted "negative" otherwise. Let + denote the subset of L(DD) on which 4 predicts positive.
What is a "typical" value of fmania D Notice that all AN possible relabelings of DD could occur as the labeling of a randomly generated bascline DILN of D, so the set of possible outcomes for fmarix (D) is the entire set of all possible noise transition matrices. Intuitivelyy, we know for example that the
5

---

Under review as a conference paper at ICLR 2021
identity matrix is "non-typical value for fmarix (D), even though its occurrence is possible. We shall adapt the notion of typical sets from information theory to capture this intuition of "typicality". Definition 2.1. Given V random derived DILN of D. let Vi, 1/2... be infinite sequence of i.i.d. random derived DILNs of D, with the same distribution as V.
(i) For any e > and integer n. 2 1, the n-fold e-typical set of is defined to be the set (T) (V) consisting of all sequences (Pi,.... Dr) M[D" of observed values of Vi...., : Vn, with the property
B[H(V)) - 1
Σ H(D.) S B[H(V)) +e. 13t5n
(ii) Consider an arbitrary function [[[] - Rd. Note that each gVV)) is an -valud random variable. For any > O and integer n 2 1, the n-fold e-rypical set of (V) is defined to be
the set A (g(V) consisting of all sequences (u,...., E Rd x ... x Rd = Rd of
observed vectors of (96))....99(4 with the property
B[g(V)] =1d
1
Σ IStSn
u ElgV)
Remark 2.2. Given (non-random) derived DILN D' Df and an -valued random function g, could treat ((D)) equivalently as a composition of a random derived DILN of with an -vauue (non-random) function. Hence for any > 0 and integer n 2 1, in view of Definition 2. the notion of an n-fold E-typical set of (D') is well-defined.
Definition 2.3. Let Do L(D), and let g be an -vlludee random function on L(D). We say that g is Do-separable if for every E > 0, 5 > 0, and every Dj E 11[D] satisfying (Do) - HD > 8, there exists some sufficiently large n such that A!*) (DD)) and A (()) (g(:)) are disjoint typical sets. We say that is separable if is Du- Du-separable for all Du E SI[D).
Definition 2.4. Let > 0, let Do E 1[[],, and let g be a Do-separable Rd-val random function on L(D) We say that discriminator Φ for D is trained n-fold on (Do, g) with threshold B, if
Φ (D' E 1[[ AlT (g(Do) n AST (g(D")) + 0}
Definition 2.5. An a-sequence for D is a (finite or infinite) sequence (a .?.)...) of distinct vec- tors in [0, == that satisfies (6) < ()) (coordinate- wise inequality) for all i < j. An a-sequence is called valid if it is (possibly finite) subsequence of an infinite a-sequence (2 a..)..... whose set of elements 1,2 is a dense subset of [o, -
Our estimator for QD relies on the existence of separable random function g on [[D] Once we find such a g. we can then train multiple discriminators & using multiple randomly generated baseline DILNS of D, get multiple intermediate estimates for QD. We each discriminator t to find suitable a E [0. 1] such that gives a high score for "typical" o-increeent DILN of D. We shall then use this value a to compute an intermediate estimate for QD. The average of these intermediate estimates is our final estimate QD for QD; see Algorithm | More details are found in Appendix B
Theorem 2.6. Let Q be the final averaged output matrix from Algorithm 1 which takes as its inputs integers r, m, n,, E 2 1, threshold B3 > O. separable -valued random function S([,), and valid a-sequence Q (1) (f) ( for D. Then QD converges in probability to QD as co,
m x., n + 0c, E + oc, and N 00.
Co.
Informally, the input integers r, m, n, l can be interpreted as follows: E is the length of the input a-sequence; m is the number of baseline DILNs generated; is the length of the sequences that each discriminator & is trained on; and n is the number of observed values of D. (for some optimal a contained in the input a-sequence) that are predicted positive by $
Theorem 2.6 tells us that our estimator (i.e. Algorithm IT is consistent; see Corollary B. in the appendix for a more refined statement. Roughly speaking, our proof of Theorem 2..6 involves careful iterated use of typical sequences, and requires an analog of joint AEP for DILNs, as well as a notion of "transverse entropy"", which has no corresponding analog in the usual notion of entropy for random variables (see Appendix BII.. Although our consistency result requires the limit N + oo (recall that N is the number of instances in D), a careful analysis of our proof reveals that for fixed N (with r > oc, m + 20, n + 20, oo), we have an explicit upper bound on the estimation error of our estimator; see Corollary B.15 In the next section, shall introduce suitable candidate for g.

---

Under review as a conference paper at ICLR 2021
Algorithm 1 An overview for the general framework for estimating QD
Require: integers r, m, n, f 2 1.
Require: threshold | > 0,
separable -aalud random function on [
Require: . = (a!1)
a ( S [0, 1] a valid a-sequence for D.
1: Initialize empty list C.
2: for 1....7 do
3: Generate observed value D = =
4: for s 1..... do
5: Generate independent observed values Dat)) - D.,1, 8,2: ......... D(S).
6: Let Φ be discriminator trained r-fold on (D)) .g) with threshold B.
7: Compute s' = min S < l, there exists 1 I S such that D( $
8: if s' exists (i.e. s' well-defined) then
9: for t 1 1... do
10:
Generate observed values for random variables El,,, EY, (for all s k)
#[Note: F F are defined in QT. QDa.. respectively.]
11:
Solve system of linear equations Q = QD.,, (in the 122 variables B.j for 1 S i, S k)
#[Note: We substitute the generated observed values for Ei. EY, into QD = QD.,. #| Note: Unique solution to linear system exists almost surely; more details in Appendix B.2 if Unique solution to linear system exists then
12:
20a² + [ si.jsk. where {9:. = &i is the unique solution to the linear system.
Insert matrix Q into list L
14:
return mean of matrices in L (This our estimate QD for Qp.)
3 REALIZATION OF FRAMEWORK USING LID-BASED DISCRIMINATORS
A key challenge for realizing our framework is the construction of good discriminators. This requires a suitable separable random function g. The underlying intuition for we should have is that we want g to "separate" datasets with different noise levels. Appendix B.6 elaborates this intuition.
With this intuition in mind, we propose to use Local Intrinsic Dimensionality (LID) scores (Houle 2013 2017a b). The LID score is used in several applications (Amsaleg et al.) 2017 Von Brünken et al. 2015 Schubert & Gertz 2017). and it plays a fundamental role in a 2018 breakthrough in noise detection: possible determine whether dataset is clean has label noise, by considering LID sequences (Ma et al. 2018b), which are sequences of LID scores, cf. Amsaleg et al. (2015). In particular, it is possible for LID sequences to detect adversarial noise (Ma al. 2018a).
LID scores are assigned to every training epoch. As observed in Ma et al. (0018)) the LID score of model has an initial phase: It would start "high" and then generally decrease to a "low" value. Subsequently, its behavior depends on the amount of label noise in the dataset. In the absence of label noise, the LID score would remain low. If instead there "significant" label noise, then the LID score would rise (after its initial decrease). Thus, the presence of label noise in a dataset could in principle be detected by any sharp increase in the LID score during the training phase. In this paper, use LID sequences
proxy for measuring the entropy of the underlying dataset trained on.
Consider a neural network. N. Suppose D' E I(D], and let Xi...., X,v be the enumeration of all instances of D'. As we train our neural network on D', shall keep track of how the feature vectors of randomly selected instances evolve over the training epochs. Given an input instance x, the feature vector of x shall mean the output vector of the last hidden layer of N, given the input x; shall denote the feature vector of x in epoch j by wy (x), and we shall define Ωg =
Let 8, 8 2 1 be fixed integers. The LID score of single instance in epoch j is defined by
LID,(x;D)) =
(x)rr((x) log (x))
where r; rx(x) is the Euclidean distance between (x) and its i-th nearest neighbor in 2y. The LID score of D' in epoch j. denoted by L.ID, (D'), is the mean LID scores of s' randomly selected instances
7

---

Under review as a conference paper at ICLR 2021
in epoch j. If training is done over L epochs, then LID := LID sequence of D'' We then define the random function JLID : [[D + RR by D' + LID(D).
(.....III(()))) is the
An LID-based discriminator is discriminator & trained on LID sequences as its training data. For every synthesized baseline DILN D' of 'D. we shall invoke ILID (D') a total of r times, which yields r LID sequences that shall be considered "positive". For each D" of D, we similarly invoke OLID (D") a total of r times, which yields r LID sequences that shall be considered "unlabeled". Hence, we can generate training data for & consisting of "positive" samples and "unlabeled" samples. We could then use any positive-unlabel
[0. 1] and each a-increment DILN
learning algorithm to train Q.
CIFAR-I0
Sym-20% 20%
Sym-50% 50%%
Sym-80%
Sym (averaged)
AP Removal
0%%
40%
70%
0%
40%
70%
0%
40%
70%
0%
40%%
70%
S-model
0.0225
0.0427
0.1381
0,4886
0.4014
0.3177
1,5650
1.3957
1.2215
0.6920
0.6133
0.5591
Forward
0,0865
0.2116
0.4999
0,0873
0.2490
0.2735
0.1617
0.1720
0,5589
0.1118
0.2109
0.4441
T-Revision
0.0869
0.2896
0.6206
0.1459
0.2425
0.3159
0,2303
0.2765
0.2267
0.1544
0.2695
0,3877
ours-1
0.0573
0.2171
0.2907
0.0268
0.1802
0.4927
0.1355
0.1022
0.1742
0.0732
0.1665
0.3192
MPEIA
0.8898
1,1730
1.4105
0.3322
0.5176
0,6085
0.0187
0.0394
0,0909
0.4136
0,5800
0,7033
ours-2
0.7133
0.8999
1.0454
0.2752
0.3987
0.4585
0.0121
0.0365
0.1225
0.3335
0.4450
0,5421
GLC 0.1966
0.3922
1.0522
0.1444
0.2783
0,8433
0.0598
0,0907
0.2365
0.1336
0.2537
0.7128
OUTS-3
0.1397
0.3282
1,1580
0.0992
0.2037
0,9991
0,0864
0,1012
0.2991
0.1084
0,2110
0.8187
Table I: Forward KL. loss comparisons for symmetric noise matrix estimations with CIFAR-10 as the underlying clean dataset. "AP" means anchor point. We removed anchor-like data up 70% in the same manner described in (Xia et al. 2019). An average loss reduction is achieved from 0.27 to 0.17 for 40% anchor-lik like instances removal when comparing with baselines not using clean samples. We also improved MPEIA and GLC by using their estimates as priors. Smaller loss values are bold-faced.
CIFAR TD
Pairwise 207%
Pairwise 45%
Parrwise S0%
Pairwise (averaged)
90% removal
hardest
casiest
hardest
casiest
80
hardest
casiest
80
hardest
casiest
S-model
0,3156
0.5568
0.5019
1,2443
122016
1.2104
2.6906
2,5212
2.6777
1,4355
1,4265
1,4633
Forward
0,0901
0.0982
0.1128
1.5657
1.0621
1.8904
8,2493
8.7039
9.1303
3.3017
3.2881
3.7112
T- Revission
0.0723
0.0870
0.1356
0.9283
0.6337
0.7656
5.7647
5.7378
5.2833
2,2551
2.1528
2.0615
curs-1
0.3644
0.5334
0.4093
0.8332
0.7364
0.7770
2.6957
1.8657
2.0011
1,2978
L,4522
1.0625
MPEIA
0.3854
0.5741
0.6139
0,5477
0.5814
0.5868
0.6006
0.6123
0.6507
0.5779
0.5893
0.6171
ours-2
0.3881
0,5499
0,4344
0.5528
0.5505
0.5751
0.6771
0.4924
0.4738
0.5393
0,5309
0.4944
GLC 0.2637
0,2545
0.2591
0.2752
0.2896
0.2666
0,2928
0.2588
0.2653
0.2772
0.2676
0,2637
ours-3 0.1967
0.3754
0.1867
0.3544
0.3294
0.3037
0.2015
0,2751
0.2169
0.2509
0.3266
0,2358
Table 2: Forward KL loss comparisons for pairwise noise transition matrix estimations with CIFAR- 10 as the underlying clean dataset. In the table, "no" means no sample removal, "hardest" and "easiest" mean 90% random sample removal from the hardest class, cat, and the easiest class, frog. We constantly perform the best for averaged noise levels. Smaller loss values are bold-faced.
4 EXPERIMENTS
Framework implementation details. Let ( (9) be a sequence of vectors in [0, 1]a Let ...., Do be a baseline DILN of D, and for each 1 S 8 S E, let D. be an -nccrmeet DILN of D. If Do, Di,..., Dr are synthesized using a common random seed s, then we say that (Do, D ....... ) a seed collection with seed 5 and a-sequence (a ...., (f)). In our experiments, we used fixed a-sequence Z, where each a = (a),..., .x) in 52 satisfies < 0.886 for all i for CIFAR-10 and a; S 0.916 for all i for Clothing IM. We trained each discriminator & on the LID sequences obtained from three different seed collections (called a "triple"), where two of them are used for training and the third is used for validation. Our LID-based discriminator is trained using positive- positive-unlabeled unlabeled bagging (Elkan& & Noto, 2008 Mordelet & Veri 2014), with decision trees as our sub-routine. We used 1000 decision trees. For each derived DILN, we generated 50 LID sequences to be used as training data. Once trained, our discriminator & assigns a score to each input DILN D' based on voting: Again, 50 LID sequences are generated for D'. Each LID sequence is predicted either positive or negative by Φ. and the total number of positive votes, divided by 50, is the final score assigned to D'. After training, if the validation recall is r 2 0.9, then the discriminator & would be further fine-tuned. Details on fine-tuning can be found in Appendix C.2.2
Datasets. We did experiments on CIFAR-10 (Kizhevsky et al. 2009 and Clothing IM (Xiao et al. 2015). CIFAR-10 10 has 50, 000 training and 10, 000 test images over 10 classes. We manually added
8

---

Under review as a conference paper at ICLR 2021
two types of instance- independent label noise: symmetric and pairwise, following the label flip settings in (Han et al. 2018). For symmetric noise, we used noise levels 20%, 50% and 80%, while for pairwise asymmetric noise, we used noise levels 20%, 45% and 80%. Clothing IM (Xiao et al., 2015) has around 1 million clothing images of 14 classes. The paper (Xiao et al.
2013) also provides
noisy subset, whose corresponding QD has been manually verified exactly. We estimate its QD based on this subset for real-life label noise scenario and refer this subset as "Clothing IM subset".
Methods. We compared our method with baselines: (i) S-model (Goldberger & Ben-Reuven 2016 which concatenates a neural network (NN) with an extra softmax layer; (ii) Forward (Patrini et al. 2017). which trains an NN and uses anchor-like instances to estimate Qp: (ii) T-Revision (Xi
et al. 2019), which finetunes QD concurrently with the training of its classifier; (iv) MPEIA Yu et al., 2018), which estimates mixture proportion by a fraction of D Delean. for QD: and (v) Gold
Loss Correction (GLC) (Hendrycks et al. (018)) which trains an NN on the noisy data. Then the trained NN computes softmax outputs of Pelean for Qp. S-model, Forward and T-Revision do not require Delean while MPEIA and GLC randomly selects 0.5% Delean from the whole dataset (in our paper). NN structure, training losses and training epochs can be found in Table ?? and Table 6 (in the appendix) for CIFAR-10 and Clothing I,, respectively. We used the same training hyper-pane parameters and data augmentation settings as given in PPatrini et al. (2017), except T-Revision, which follows the settings in Xia et al. (2019) for respective datasets. Ours-1 took similar approach as GLC without Delean to obtain prior (we call this prior "avg prior"). We first split the dataset into a 90% training set and 10% validation set randomly. We then train an NN to compute probability vectors of the whole noisy dataset. The probability vectors of the samples with label i from the epoch with the best validation accuracy is averaged the ith row of prior. Ours-2 (resp. ours-3) used MPEIA's (resp. GLC's) s) estimates as priors All values reported are averaged over at least 5 estimates.
Experimental Results. We now-normalized all estimates from the baselines then evaluated them using (forward) Kullback- Leibler (KL) los For CIFAR- 10's both symmetric and pairwise cases, even for 70% anchor-point removal or imbalanced class ratios, our method has the lowest losses for averaged noise levels, compared to all the baselines, and made improvements when MPEIA and GL.C are used as our priors. For Clothing IM, ours-1 has the lowest KL loss, 0, 0.4903, slightly better than T-Revision with a KL loss of 0.5262. S-model ranked the last. Among all methods that used 0.5% clean samples, ours-3 achieved the lowest loss, 0.5311, while its prior GLC has a loss of 0.5957.
Methods
S-model
Forward
T-Revision
ours-I
MPEIA
ours-2
GLC
ours-3
Forward KL loss
2.1189
1.1098
0.5262
0.4903
1.7408
1.8344
0.5957
0,5311
Table 3: Forward KL loss comparisons for Clothing M subset. Ours-1 has the lowest forward KL loss among all baseline models. When 0.5% Delean used, we (ours-3) improved GLC.
CONCLUDING REMARKS
This paper focuses on datasets with instance-independent label noise (DILNs), and tackles the problem of estimating the noise transition matrix QD of a DILN D. Our main algorithm is the first- ever estimator for QD that is proven to be consistent without needing to optimize the classification accuracy of a classifier trained on D. Notably, we do not require clean data or anchor-like instances, and we do not make any assumptions on the structure of Qp. Thus, a key "takeaway insight" is that QD could be accurately estimated in a wide range of scenarios, including possibly for classification tasks that are "inherently still difficult" to get high classification accuracies even without label noise.
Our consistent estimator is based on new information-theorree framework, in which we introduce the notion of entropy for DILNs. A key step in our approach is the training of discriminators to predict whether an input DILN has maximum entropy. Our proof of consistency relies crucially on the notion of "typicality" and the asymptotic equipartition property from information theory.
Both MPEIA and GLC inherently require Delean Since our method does not leverage clean data, it would not be fair to directly evaluate our method against them. Instead, ours-2 and ours-3 are intended to show that MPEIA and GLC can be enhanced with our method, without having to do further clean data amnotation/angmeetttion
'Ir Q = s (resp. Q = (ncslsssse is the estimated (resp. true) noise transition matrix for D, then the corresponding (forward) KT. loss is defined to he Σk P2()) E Zt.5 log (gLa//..))

---

Under review as a conference paper at ICLR 2021
REFERENCES
Laurent Amsaleg, Oussama Chelly, Teddy Furon, Stéphane Girard, Michael E Houle, Ken-ichi Kawarabayashi, and Michael Nett. Estimating local intrinsic dimensionality. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 29-38, 2015.
Laurent Amsaleg, James Bailey, Dominique Barbe, Sarah Erfani, Michael E. Houle, Vinh Nguyen, and Miloš Radovanović. The vulnerability of learning to adversarial perturbation increases with intrinsic dimensionality. In 2017 IEEE Workshop on Information Forensics and Security (WIFS), pp. 1-6. IEEE, 2017.
Jiacheng Cheng. Tongliang Liu, Kotagiri Ramamohanarao, and Dacheng Tao. Learning with bounded instance-and dabel-dependent label noise. stat, 1050:12, 2017.
Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012.
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 213-220, 2008.
Marylou Gabrié, Andre Manoel, Clément Luneau, jean barbier, Nicolas Macris, Florent Krzakala, and Lenka Zdeborová. Entropy and mutual information in models of deep neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.). Advances in Neural Information Processing Systems 31, pp. 1821-1831. Curran Associates, Inc., 2018. URL http::/tppppeeeeee nips cc/paper/ 7453-entropy and- wwt.-iiinoiiiioooo o -o-ooon---mmddeeooooooooo- of -wwpoddeee----ee-ppeeeeee--eeeee dee-----reeeeee----ee----------e works..
pdf
Jacob Goldberger and Ehud Ben-Reuven. Training deep neural-networks using noise adaptation layer. 2016.
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.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Dan Hendrycks, Mantas Mazeika, Duncan Wilson, and Kevin Gimpel. Using trusted data to train deep networks on labels corrupted by severe noise. In Advances in neural information processing systems, pp. 10456-10465, 2018.
M. E. Houle. Dimensionality, discriminability. density and distance distributions. In 2013 IEEE 13th International Conference on Data Mining Workshops, pp. 468 (68-473, Dec 2013. doi: 10. 109/ ICDMW.2013.139
Michael E. Houle. Local intrinsic dimensionality i: An extreme-value-thherrtie foundation for similarity applications. In Christian Beecks, Felix Borutta, Peer Kröger, and Thomas Seidl (eds.), Similarity Search and Applications, pp. 64-79, Cham, 7a.7a. Springer International Publishing.
Michael E. Houle. Local intrinsic dimensionality ii: Multivariate analysis and distributional support. In Christian Beecks, Felix Borutta, Peer Kröger, and Thomas Seidl (eds.), Similarity Search and Applications, pp. 80-95, Cham, 2017b. Springer International Publishing.
Ishan Jindal, Matthew Nokleby, and Xuewen Chen. Learning deep networks from noisy labels with dropout regularization. In 2016 IEEE 16th International Conference Data Mining (ICDM), pp. 967-972. IEEE, 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. JEEE Transactions pattern analysis and machine intelligence, 38(3) 461, 2015.
10

---

Under review as a conference paper at ICLR 2021
Xingjun Ma, Bo Li, Yisen Wang, Sarah M. Erfani, Sudanthi N. R. Wijewickrema, Michael E. Houle, Grant Schoenebeck, Dawn Song, and James Bailey. Characterizing adversarial subspaces using local intrinsic dimensionality.. In ICLR 2018, 2018a. htLl:tttp/a/xii// 02613
Xingjun Ma, Yisen Wang, Michael E. Houle, Shuo Zhou, Sarah Erfani, Shutao Xia, Sudanthi Wijewickrema, and James Bailey. Dimensionality-drive learning with noisy labels. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 3355-33664, Stockholmsmässan. Stockholm Sweden, 10-15 5 Jul 2018b. PMLR. BRLhttp://// http::///occeeeen.....o mlr press/ 1v80/mal88 1d.. html
Xingjun Ma, Yisen Wang, Michael E Houle. Shuo Zhou, Sarah Erfani, Shutao Xia, Sudanthi Wijew- ickrema, and James Bailey, Dimensionality-die -rivenn learning with noisy labels. In International Conference on Machine Learning, pp. 3355-3364, 18.
Fantine Mordelet and J-P Vert. A bagging to learn from positive and unlabeled examples. Pattern Recognition Letters, 37:201-209, 2014.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Advances in neural information processing systems. pp. 1204-1204, 2013.
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, 2017.
Michael D. Perlman. Jensen's inequality for a convex vector-valued function on an infinite- dimensional space. Journal of Multivariatee Analysis, 4(1):52 65, 1974. ISSN 0047-259X. doi: http://bbo.///000000000000000000
URL
Harish Ramaswamy, Clayton Scott, and Ambuj Tewari. Mixture proportion estimation via kernel embeddings of distributions. In International Conference Machine Learning, pp. 2052-2060, 2016.
Andrew Michael Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Bren- dan Daniel Tracey, and David Daniel Cox. On the information bottleneck theory of deep learning. In International Conference on Learning Representations, 2018. URL https //openreviens www.:eetffoooo meet/Forrm2idrry_MPGG--
Erich Schubert and Michael Gertz. Intrinsic t-stochastic neighbor embedding for visualization and outlier detection. In International Conference on Similarity Search and Applications, pp. 188-203. Springer, 2017.
Clayton Scott. A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In Artificial Intelligence and Statistics, pp. 838-846, 2015.
Ravid Shwartz-Ziv and Naftali Tishby. Opening the Black Box of Deep Neural Networks via Information. arXiv e-prints, art. 1rXiv:1703.00810 March 2017.
Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki, and Kiyoharu Aizawa. Joint optimization framework for learning with noisy labels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5552 5560, 2018
Kiran K Thekumparampil, Ashish Khetan, Zinan Lin, and Sewoong Oh. Robustness of conditional gans to noisy labels. In Advances in neural information processing systems, pp. 10271-10282, 2018.
N. Tishby and N. Zaslavsky. Deep learning and the information bottleneck principle. In 2015 IEEE Information Theory Workshop (ITW), pp. 1-5, 2015.
Robert Vandermeulen, Clayton D Scott, et al. An operator theoretic approach to nonparametric mixture models. The Annals Statistics, (7(5):774427333 2019.
11

---

Under review as a conference paper at ICLR 2021
Jonathan Von Brünken, Michael E Houle, and Arthur Zimek. Intrinsic dimensional outlier detection in high-diienniionl data. NII Technical Reports, 2015(3):1-2,, 2015.
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? In Advances in Neural Information Processing Systems, pp. 6835-6846, 2019.
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2691-2699, 2015.
Xiyu Yu, Tongliang Liu, Mingming Gong, Kayhan Batmanghelich, and Dacheng Tao. An efficient and provable approach for mixture proportion estimation using linear independence assumption. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 4480 4489. 2018.
12

---

Under review as a conference paper at ICLR 2021
APPENDIX
This appendix is organized as follows:
Section
gives detailed treatment of datasets with instance-independent label noise (DILNs).
Section
B
proves the consistency of our proposed estimator.
Section provides all the implementation details of our experiments.
Section
describes how our work relates to the information bottleneck theory for deep learning.
A A RIGOROUS FORMALISM FOR DILNS
A dataset DD is a set consisting of N ("instance", "given-label") pairs, If we enumerate these pairs by (X1,9) (X2, y2)..... (xN, )N), then D the set of pairs (xx,3:)) W:] Across all disciplines that deal with datasets, there is an implicit assumption that the instances of dataset are sampled from some "true" data distribution. Formally, each instance x is an observed value of some random variable Xume For classification tasks, given instance X
X, it is assumed that there is uniquely determined correct label Yx associated to this instance x. Hence, there is a function finee that assigns each instance x to its correct label V/x We assume that f Inee is completely deterministic and does not involve any randomness. If mme is a random variable representing the correct label of a random instance me. then Zime = f mue (X Because we are only given the datapoints of D, we typically consider the restriction of the domain of fmee to the instances of D; we denote this restricted function by fine- In the absence of label noise, the dataset becomes precisely D {(x,, Yx. JIsisN For such "noise- free"" datasets DD the goal of learning classifier from D is to obtain good approximation free for the function Sine
When instance- iestance-iddeeendent label noise is added to the dataset, there is random function fnois that is applied to the correct labels y/x of all instances x. This random function fnoise depends only on the input label z, and does not depend on which instance x this label is for. Similar to the case of only given the datapoints of D, again typically consider the restriction of
fuve. because the domain of fnose to the instances of D; we denote this restricted function by fooise- Assuming that this implies that fiise can be decomposed into
the set of all possible labels is A = {l....,,A k). .......,,, random variables Y1,..., .,, Ys. where each Y; is a discrete random variable taking on values in AA. The .......... py, (k)) would completely determine the distribution of Y, Thus, f is a function on A given by the map i + Y, This is random function that is completely determined by the set of all 2 probabilities (pv; whose (i. j)th entry equals py; (j) is precisely the noise transition matrix that we consider in our paper, which we have denoted by QD. Consequently, to "learn" model of this instance- indeeededdde label noise is to obtain a good approximation fuoise for f fuisee which is exactly the same as finding a good approximation Qo to the noise transition matrix QD.
set of probabilities (py, (1)....,
The k-by-k matrix Q = [
Our goal for this paper is to estimate the noise transition matrix Qa from a given dataset D. Thus, one of our main assertions for this paper, that "high classification accuracy is not required for estimating
QD well", can be interpreted as the assertion that we can find a good approximation fucise for f even if we are unable find good approximation for f a good approximation for f I Notice that for existing methods that "learn in the presence of label noise", their underlying goal is to find a good approximation for either fuke or the composite map /niiee r In contrast, our goal is to find good approximation for [D P
Given DD a dataset with instance-independen label noise (DILN), let X be a random variable representing an instance of D selected uniformly at random (notice that X A X.me), let 2 := fP (X). and let Y == f (2). By definition, fii is completely determined by the conditional distribution of Y given 2, and the set of all possible labels A; in particular, 12i does not depend on X or JPD This explains why the noise model associated to 'D is denoted by (Y) In our paper, we have
'Of course, the purpose for learning a classifier from D is to learn a good representation for f fimes and we can only do so given the dataset D. If the underlying distribution of D is not a "good representation" of the distribution of X mee then any approximation to fir matter how accurate, will not approximate f fine well. Henceforth, we assume that D has "good underlying representation" for the distribution of X X.me-
13

---

Under review as a conference paper at ICLR 2021
defined DILN to be set. It is the set D {(x,, vilhisgN which also has associated noise model (A).
Strictly speaking, DILN should be defined as triple (D,Y A), since we also include the information about the noise model Y A) as part of the definition of the DILN. However, for the purpose of this paper, abuse notation (slightly) and assume that DILN D includes its associated noise model. To avoid ambiguity, the set consisting of all ("instance". "given-label") pairs (x,, y:) shall be called the underlying dataset of D, and each such (xi, wk) pair shall be called datapoint D. Of course, we are implicitly assuming that the instances x.,..., X are sampled from some "true" distribution (i.e. the distribution of Xuee), but do not need any information involving Xuue beyond this implicit assumption.
B PROOF OF CONSISTENCY OF PROPOSED ESTIMATOR FOR QD
The goal for this section is to prove Theorem 2.6 i.c. that our proposed estimator for QD is consistent; see Theorem B.14 for a precise (equivalent) formulation of Theorem 2.6 Our consistency proof is essentially iterated application of suitable analogs of the asymptotic equipartition property (AEP) theorem from information theory. In particular, we will prove a joint AEP theorem for DILNs; see Theorem B.3 The proof of Theorem B.14 requires some preparation, so we shall first prove several related results in Sections B. B.3 before we present Theorem 14 in Section B.4
Throughout, let D be DILN with noise model (Y A). Without loss of generality, assume that A = .l...., }} satisfies k 2 2, assume that D has N instances, and write QD = [æ.]lısksk. If [x
100 is any sequence of random variables, then write "X, _"+ 1² to mean that "X, converges in probability to μ². Here, could be a scalar or a random variable.
B. JOINT ASYMPTOTIC EQUIPARTITION PROPERTY FOR DILNS
Recall that in Definition 2.1 we introduced the notion of "n-fold e-typical sets" for random derived DILNs. We will also need to define jointly typical sets for random derived DILNs. This involves what we shall call "transverse entropy", which has no corresponding analog in the usual notion of entropy for random variables.
Definition B.1. Let D'' and D" be derived DILNs of D. The transverse entropy of DD' and D is |
H(D' A D") = - -E (i) Σ
D" Fi
log
- D"
1i. I.
EEA JEA
(Recall: We the convention that 0 0og 0 0.)
Definition B.2. Let V and W be random derived DILNS of D. Let V1, V2,... (resp. W1, W2... be an infinite sequence of i..d. random derived DILNS of D with the same distribution as (resp. W). For any the set !! (V, W) consisting of all sequences (ID)..., D,), (Di..... D()) E S[D]" x D(D of observed values of Vi,..., Vn, W1..... Wn. with the following properties:
and integer 2 1, the n-fold jointly E-typical set of and W is defined to be
E[H(V)] - E
H(D)) E[H(V)) +
(3)
t=1
"
B[H(W)) - - Σ
H(D)) s E[H(W)) +
(4)
n
t=1
"
E AW] -
Σ
H(D, A D E(H(V W)] +
(5)
In particular, notice that the restriction of A(d) (V, W) C "ID"" x DD to the first (resp. second) D[D]" component is a subset of the n-fold e-typical set of V (resp. W).
Theorem B.3 (cf. Cover & Thomas (2012) Thm. 7.6.1)). Let V and W be random derived DILNs DD Let V1, Vz,... .. (resp. W,, W2,... ..) be infinite sequence of i.i.d. random derived DILNS of
14

---

Under review as a conference paper at ICLR 2021
D with the same distribution V (resp. W). and suppose that D1, D/2 Di.... (resp. Dí, D2 is corresponding sequence of observed values. Then for any E > 0.
lim Pr ((D))..., (D. E = 72-000
A
Proof. Consider an arbitrary (DD)..... Da), (D....., DDD) E A (V, W'. By the weak law of large numbers, - (D)) converges in probability to [V). Hence, given any 0, there exists an integer such that for all integers n1.
Pr ((D)) -[[[[V]]] 2
(6)
By a similar argument, we also infer that given any & > 0, there exists an integer n2 2 1 such that for all integers n > ng.
Pr (HH (H
n
H(D)))
(E|H(H)) 26) 3'
(7)
and there exists integer ny such that for all integers 113.
Pr (1 n2
n H(D ( Σ
EV wi] 2 S E
(8)
Therefore, for all integers 2 max(n1, n2, na). the probability of the union of the events in (6. and 8 must be at most E, which proves our assertion.
For the rest of this subsection, let Do 1[[D,, and g be De-separable valuue random function
on _ Recall that for 3 >> 0, discriminator & for ' is said to be trained r-fold on (Do g) with threshold B. if the set of positive predictions for & is
+- (D' E [([ A5' n AgT + 0}.
Definition B.4. Let 8' > 0, 3 > 0, let r 2 be an integer, and suppose is a discriminator for DD that is trained r-fold on (Do. g) with threshold 3. We say that 4 is 8' -ufffffice if every D' E [[[] satisfying H (Do A D < 8' is predicted positive, i... D' E'E 4+
Lemma B.5. For every B, 8 > O, there a sufficiently large integer r3,5 2 1 such that for all integers 2 rp.ó, if 4 is discriminator for D that is trained n-fold (Do, with threshold B, then the following implication holds:
E - ( - H
Proof. Consider any D2 E U that satisfies (D))) - (D:)) > 6. Since is De-separable, it
follows from Definition 2.3 that there an integer 33, such that A()) (g((P) n A (m) (g(D)))
D. for all integers 2 B3 For each 3 and 6, define
r3,6 = max(r Dj 3,8 E Z: D2 E [[D), H(D:)) > 8).
In particular, Tp,s is well-defined, since 1[[D is finite (of size 1-N).
Now, for any n 2 T3,5, suppose that & is trained n-fold on (Do, with threshold 3. By Definition 2.4 this means that o+ (D' U[D:: A ( (A + OJ. By the definition of ra.s.
thus have Age (g(D))) n A Agt) (o(D)) = @ for all D' satisfying (D)) HD')) > 8, which then proves the assertion.
Lemma B.6. Let < < 1, and let h: [0, k 1] + R be a function given by
hxx)= = k- (1 = log (1 -1==)) + } (1 + x)) log( + x).
(9)
Then h(x) is strictly increasing. and h(s) > 0. Moreover, í = min(p(()): 00 and if HHHDD (D) 2 log k <)((),, then lg. b s for all 1 < i, < k.
15

---

Under review as a conference paper at ICLR 2021
Proof. First of all, we check that the derivative of h(x)) is
1 h'(x) = k
log 1 - x
1-11 11 = log( 1 + x)]
k: log
+
which satisfies (x) for 0 < x < h 1. (Recall that 2 by assumption.) Thus, h(()) is strictly increasing on the closed interval [0, k 1]. In particular, e > 0 implies that h(c) > h(0) 0.
Henceforth, assume Ç > and suppose on the contrary that there exists some S lu. jo S such that 1i E. > Let o {1 E,) for all S S k, and assume without loss of generality that Iio.jo (1 EJo) for some E E. This implies that
Σ
D log Viois
Σ
+11 e2) log (1 +
1SiSk j#10
1Sjsk
j#
= Σ
e1
Σ 111 E5) log (1 + +
s5isk
15isk
j7j0
3730
Since Σ/= E, = 0, and since the map + - log x is concave, it follows from Jensen's 's inequality
(see Cover & Thomas (2012 Thm. 2.6.2)) that
Σ
D Bans log Abort
Σ
E1
530 A-1
log (1
k-1
Eio
(10)
ISiSk 17
1SjSk j#30
Note also that
D Po
D log Pio.jo
-1 Ejo log [/ egu)
(1 Ego) log k (1 + 10) log(1 + tz))-
(11)
Summing (10p and 11
gives us
Σ
D Poor log Hin \
Σ (1+ (1+ log 1-l (1
Gin k-I
log (1 1-1 1 (1, log(1 Eej))
18isk
1sisk
log k 2 (1
Ein k-I
log (1
$ (1 + Ejo) log(1 + E00)
log - h((so))-
(12)
Note that u = 1 + E < implies Ejo < k: - 1, and recall that 1 > by assumption, hence
ME50)) > h(e)) > 0. It then follows from (12) that
Σ
Poou log : S log k MeSo) log k: Me) < log k:
18igk
Note also that for all < i < & satisfying f io. Jensen's inequality yields
Σ
R D
log 2 s log k.
15J5k
Thus,
H = Σ pz(()
Ti log R.. log k: (h(E)
(13)
j=1
Since 1
contradicts the condition that HDD) log k <h(E),, we conclude that no such in J0 exist, therefore H(D) > log k Ch(s) implies
4 for all 1 < i, k.
n
16

---

Under review as a conference paper at ICLR 2021
B.2 JOINT ASYMPTOTIC EQUIPARTITION PROPERTY FOR DILN MATRICES
Let Mala ( IJ) be the set of all row-stochastic k-by-k matrices. For convenience, random matrix shall henceforth mean Mat & ((0, 1])-valued random variable, i.c. we omit the qualifier "row- stochastic" from "random row-stochastic matrix". Let [+] denote the matrix in Mat (00, 0, 1]) whose h2 entries are all equal }.- We shall also use -| kxt denote norm on Matexa 1)). All subsequent results still hold for any norm on Mataxa<(00 1]); only certain constants in continuity arguments would change with a different norm. For concreteness, we shall work with the matrix
1-norm, i.e. |ا == saxisisk Ei=les G..l--
Proposition B.7. Let < S 1, and suppose that D(1), D(()) are derived DILNS of D. If
Ç = min (pz (i) : I E k} > O, and if 1 - HD(()) 2 log k -ch( (where h(x) is defined
as in ),, then
Σ 2Dw) [kllxx S.
(14)
Proof. Define the function oz Matxxx (10, 1I) + R by
k Σ pz(1) i=1
C.j log Ci.j
Note that = =(D')) for any derived DILN D' of DD Note also that d is concave function, so by generalized Jensen's 's inequality (see)Perlmeg Perlman (1744))
log - (C((E) S
m H(D())
m
oz (Q(w)) S oz _Qni))
1 (- m
m
m
m
Consequently, writing Q = [9
(1)
for each s < m, follows from Lemma t.6that
igujsk
m
k
for all 1 S i,j S therefore (4] follows from the definition of the matrix 1-norm.
Next, we shall define several Matax4(0 ((0, val-ue functions. For every a = (ai..... as) E [], define the function f finerementt Mat 1]) x Matexa [0, 11) + Matex 11) by
(Iushsssse [Ets (Ewllsssss) + 9t - -a,) + Σ q (1+ Ei
(15)
IStck (
Define the random matrix E" E Ussskss where Eyy the random variable defined in ① Notice that by definition, ffnceement (Q,, F%) QD.
Next, let f Solve determined by the map (fi (Q. E) + Q. Note that to compute this map fealver we would need to solve a system of linear equations: Specifically, if Q = [ and & [ets) and if fox fieremeet (Q, E) the given matrix [ct,]lIs4.55R then Q can be computed by solving the system of 222 linear equations in the 2 variables {qi hisi.kk. given follows:
Mat ((0, 1)) Mat (10, 1)) + Matxx [0. 1)) be the function that is uniquely
Ci 91 aa)+
Σ ISiC T
00,04 1 (1 Es,)) (for ú,j S.Ji k).
In general, for any given matrix [cx.] (su))s if we sample from the distribution of E% then this system of linear equations has a unique solution almost surely. Consequently, f (1ag))sksgk. E%) well-defined almost surely.
Lemma B.8. Let let E [0, 1}4, and let n 2 1 be an integer.
17

---

Under review as a conference paper at ICLR 2021
Let Ey E..... be infinite sequence of i.i.d. random matrices with the same distribution E", and suppose that E = Et, Eyj = E..... is a corresponding sequence of observed values. Let D Do' .... be infinite sequence of i.i.d. random derived DILNs of D with the same distribution as Das and suppose that D D1, "h, -D,... a corresponding sequence of observed values.
For every integer 2 define QE, == -incrreeent E.). Then,
lim Pr (1 (QD - QQa)) <ε) =1.
<=)=1.
Proof. By the weak law of large numbers, and using the definitions of QD, and Qe we have +E= QD. "4, E(Qu, and //2 Ei= Qc _ E[QD,l, hence the assertion follows.
Theorem B.9. Let n, m 2 1 be integers, and let (a ..... "...,,,(m)) (m)) be sequence of m vectors in [0, 11 Assume that Ç = min > Let and define = 2 2x (where
h(x) is defined in (9)
Let Lei D ...., Dmm) E s(D) such that
log k-
H(D! S.
(16)
For every 1 J m. let E(("), EE .... be an infinite sequence of i.i.d. random matrices
with the same distribution as E" and suppose that E e(²) E. = c(1) is a corresponding sequence of observed values.
Let (D(2) ,.,,, ) E A(m) (Da.)...... (D (D(m),
D.m)) E A(n) (D (Daimi) be m sequences
such that for all 1 <
m
(H(D)))H((D!))
- H(D!!))) s
(17)
For every 15is S S m. define a 2 == S (9 (piin E. Then,
lim Pr (1( n-0
m
Σ ) - -2p < =1.
(18)
Proof.
First of all, note that (6 yields
m
log k
((D))) <8 =
m
thus it follows from Proposition B.7
that 1 Σ Upg. [ xxlll |l S $ By 16 and 17 we
infer that
log t
(DD
(1))
< 28 for all 1 sis n. So by similarly applying Proposition
B.7 we get 1 Σm Pp!s
11
S for all 1 <i
k
Thus, by triangle inequality,
m
(Onga) 2p() || S for all 1 s i S n, which implies
j=1
(Opp) - - SE.
(19)
Also, by Lemma B.8 we infer that
lim Pr (1)
1
Σ
pp!a Qg(0) -
<3) =1
(20)
18

---

Under review as a conference paper at ICLR 2021
where a000) increment (QD, ). Consequently, it follows from 19 and (20) that
lim Pr
(Dis: 2ctor)
< <2 1.
(21)
m
Note that by definition, faoivo (2 cl00, E(6)
faytt)
solve Jincrement (Qr (Q0,E()) ), ) = -Qp. Therefore,
by applying the multilinear function solve (- e(it) to each term in (21) we get 18 as desired.
B.3
ESTIMATION OF QD VIA TYPICAL SETS
Define the random matrix E' [E where Ey is the random variable defined in Given any observed value & = [eiglesigs for E", we shall write & + x to denote the
Section 2.2
matrix Si. + Hlisissk-
Lemma B.10. Let > O, and let n 2 1 be an integer.
Let E E/... be an infinite sequence of i.i.d. random matrices with the same distribution E', and suppose that Ej E E2 E is a corresponding sequence of observed values. Let DD D,...... be an infinite sequence of i.idd random derived DILN of D with the same distribution D, and suppose that Dj D1, D2 D2.... .. corresponding sequence of observed values.
Then,
lim Pr n-00c
(IH
a (eD.
Q2. -0% 1)) <<) =1.
Proof. By the weak law of large numbers, and using the definitions of QD, and E 1. have 1 D i= QD. 2, [[QT), and 1 Ei=i(ee (8) ", E[Qp]. hence the assertion follows.
By ussumption, our dataset D has N instances and k label classes. We shall define the gap of D to be gap(D) == log k E[H (D)). Notice that by the definition D. this gap(D) depends only on the values of N and k.
Lemma B.11. 0 < gDp(D)= S log k and Nim gap(D) = O.
Proof. By Jensen's inequality (see Cover & Thomas
2012 Thm. 2.6.2)). have E(H(D) S
(E) log ks hence gap(D) 2 0. Note that gap I log k. since H 2 0 for all DILNS D'. Finally, the limit lim gap(D) = 0 is a direct consequence of the weak law of large numbers.
The following theorem an extension of Theorem B.9 that takes into account predictions from discriminator for D. This extension involves the gap of D.
Theorem B.12. Let n, m,r 2 1 be integers, let (cx(1) ..... (m)) be a sequence of m vectors in
[0, 1] and assume that Ç := (pn() 1 S k] > 0. Let 3, 8, E' >> 0 be scalars satisfying gap(D) D) < < log k, 0 < < gDp(D), and e' == 2k (26) > 0, where h(x)) is defined in 9 Also, let be separable valued random function I(D)
Let Es...., Ey be sequence of i.i.d. random matrices with the same distribution as E', and suppose that E, .,...., Ey 3. is corresponding sequence of observed values.
For every 1 < j S m, let E EE Ed(( ....,E ,E!!s)) be a sequence of i.i.d. random matrices with
the same distribution E" and suppose E((i) =("(( EE!l ='h .... "...E""" E"( is corresponding sequence of observed values.
Amm) (m) (D), and for every 1 S suppose that & is discriminator for DD that is trained r-fold on (D() .9) with threshold B.
Let (D)), ...., D( (D(")
For every < m, suppose that (D(2) ....,, D..)) A(T) (D...) (0t
19

---

Under review as a conference paper at ICLR 2021
For every integer < S n, define Q,00) Sootve (E; E, E.
Then there exists sufficiently
large integer r8,6 such that for all r 2 1B,6.
lim Pr (1(
C ). Qu <2x') =1. 1.
(22)
Proof. The proof, although seemingly complicated, actually follows essentially from unraveling the relevant definitions. First of all, notice that
B[M - (D) - 8 gap(D) loog - 8,
which implies that for any (D) ,..., D(ml) E A (D), we have (by the definition of A!") (D) that
1 m m
log
H(D
S
(23)
For each S j & m, follows from Lemma B.5 that there exists some sufficiently large integer (() 99 2 1 such that for all r 2 '3,8
())
D' E 2- = - $
(24)
Let r3, == max : i m). and henceforth assume that every discriminator Φ is trained r-fold on (D(").) .)) with threshold B, for some 2 r3 For all S j & m and I i S n, note that
D(1) $5 by definition, hence 24 implies that (H(D( (D s 8, so in particular,
H(D -((()))(((??)) 5.
(25)
By definition, e' = 2k h (2)). This means that 5 = ch ). In particular, recall from Lemma t.6 that h(x) is strictly increasing (and hence bijective) function with domain [0, l: 1], note that h(k 1) log k and note that 26 < log& by assumption, so the inverse h- (22) (6 ) is well-defined.
Then for every 1 < < k. it follows from 23
25
and Theorem B.9 that
lim Pr (IK
m
n
solve (Qp(n, ((t(i)) QD < <E))= =1.
(26)
22+00
Note that by Lemma 1.10 have
m
lim Pr
Σ
(Qpl)
(+++)))
b)) <E)= =1. 1.
(27)
000
m n
E )((ii)) to each term in (77 this yields
Next, apply the multilinear function
foolve (-,
lim Pr
(1
1
S (ostve( (Qp.n, g((ii) - Soo (&) + E en.i))
<t))= =1 (28)
=1.
000000
Note that 0.00 = fali (E) + +. cm((i)) by definition, thus it follows from 26 and 28 that
lim Pr (1( n1
20l 25') 1.
(29)
+0000
20

---

Under review as a conference paper at ICLR 2021
B.4 PROOF OF THEOREM 2.6
Consider a valid a-sequence S2 (a(2), ..... (0) for D. By definition, this means S2 is a subsequence of an infinite sequence (a(4),(11_ ...) of distinct vectors in [0, 4=1>* (recall that & is the number of label classes), such that {a(+) ji=1 is dense subset of [o, x
1-11
Let 8 > For any fixed integer n 2 1, observe that
lim (() (D (Da:0) n 7000
AA
A())
(D) = A (D)
This implies that
A
(m) (D
(cc) A (n) (D)
lim
(30)
8-y00
|A!h) (D)
In contrast, for any fixed integer
2 1, Ef (m (D)] then
lim lim (D
(:0) 0 A
(D) 0.
This implies that
IA (D (o) n (n) (D)
A!
lim lim 200
0.
(31)
|A5 (m) (D)
Lemma B.13. Let B,E 0, let Do E A (D), iee Do is an E-typical baseline DILN of D, and let be Do-separable R -Vauud random function on 1[[D]. Let r Z 1 be an integer. let & be a discriminator for that is trained r-fold on (Do,g) with threshold B, and suppose that & is 8' -suffccient for some 8' > Let Z (1 a22)... ....) be a valid a-sequence for D. Then there exists some sufficiently large integer lo 2 1 such that for all integers 2 Lo, a randomly generated e E-typical (5) -nncrmemettt DILN of has non-zero probability of being predicted positive by &, i.e.
Pr (A (g(o)) (A('' (g(D')) + 0 E
> O.
(32)
Proof. Since & is 8' -'sffficieet,, we infer that 32 is true if there exists some D' E A (1)) (D (n) such that (Do A D') 8'. Clearly, H (Do A Do) 0 8', so it suffices to show that Du A (1) (D (
From 30 we conclude that Do E (1) (Da.)) is true if l sufficiently large.
Finally, we prove an equivalent (and rather long) reformulation of Theorem 2.6 from the main paper. Theorem B.14. Let n. r, l > be integers, let Ω = (a) (2) ....) be valid a-sequence for D. and assume that Ç == min isis k} > Let B, 8, E, >> be real scalars satisfying gap(D) < 8 < 2 log 0 < = S gap(D), and e' := 2k (26) > 0, where h(x) is defined in 99 Also, let be separable Rd valued random function I[D
Let (1) ..... (m)) be sequence i.i.d. random derived DIINs of 'D with the same distribution as D. and suppose we have observed values (
((1)
mi)) = =D(m).
For every 1 S E and S j S m, let DD1) 1 D (i)
D(1)
2 a(v),n be a sequence of i.i.d.
random derived DILNS of with the same distribution as D Dato. and suppose we have the observed values D(5)
(())) = Di1) D(J) = 5.2 a
( s...... D(J)
an D(5)
For every 1 م S m, suppose that 3 is discriminator for D that is trained r-fold on (D) .9) with threshold B. and suppose that every discriminator 4 is 8' sufficient for some 8' > 0. Then there exists some sufficiently large integer f,,8' 2 1 (which depends on and 8' such that for all integers El 2 lr,8, a randomly generated e-typical ( -incermme DILN of has non-zero probability of being predicted positive by 4 for all 1 < < Assume that the given integer & is sufficiently large, i.e. & 82 lr For every S j < m, define
best == min 8: 1 SS S e, there exists some S Sis S n. such that D(S) E $Φ7}.
(33)
Let 1 1 < j2 .... < Jm S m be all indices je such that best # -00. (By default, we define
min 0 = -c. Note that ml S m.)
21

---

Under review as a conference paper at ICLR 2021
For every i S m, let ET() ,...,,W! E(d) be sequence of i..d. random matrices with the same distribution as E", and suppose that we have the sequence of observed values E g( ..... Enn) gl
For every S j S m, let ET EE" ,..., ,...,En En(h) be a sequence of i.i.d. random matrices
with the same distribution as E" alory where s' == (i)
best and suppose we have the sequence of Ex( _!!(s)
observed values Fx(() -((()) F(l()) E2 cn
For every 1 S sis S n. and 1 S S m. define (.))) == Soolvo (E; + R. E. Then there exist sufficiently large integer r3, (depending on 3 and 8), corresponding sufficiently large integer E 2 (depending on g9 and 8'), such that for a fixed r = r3,8, and for all Lep,a.'s
lim m m=+00
lim Pr n--000
(I
Σ
m
Σ
QD|
< <26')
=1.
(34)
m'
i=1
Proof. First of all, for each Sj S m, Lemma B.13 says that there some sufficiently large integer loj such that for all & Eoy, randomly generated e-typical (19)) DILN of D has non-zero probability be in $5 Thus, we could set e, := max :1s S m}.
(1) For each S t m', define abett == aal'), where s' beat Observe that
(16)
(D (ce)
slr) ....... D
(te) sfor)
(n) (D .o) n (*))",
(35)
and if (D())
D Domil Am
(mm') (D), then Theorem B.12 yields
m
lim (11
),00) - Q2/ 22) =
(36)
n-000
m
By definition, each D (for isis n) is already contained in 1 D hence for 335 to be true, we only need to check that
(DLL)
EA (D (.)
72
best
Now, for any 1 S & S m', it follows from Theorem B.3 that there exists some sufficiently large integer nh such that for all integers n nig have
Pr ((DD)) ..... D(")),
(Dii) 1 beaa
(1)) D
E A!T
s. (37)
beat
Consequently, if m' 2 no. then
(1 m
lim Pr
)
Qb < 25' > 1
(38)
1=1
Finally, the choice of f, implies that Pr(s * -00) > 0, hence m' + 00 as m - co, therefore true.
(39h
Note that the matrix
m
a
Qo:=
Q.10)
m'
which appears in 33 is precisely the output matrix Algorithm corollaries.
I This gives the following two
Corollary B.15. Let 8' > O. Assume that the initial conditions (on r, m, n, e, 3.g) g) given in Algorithm I are satisfied. Assume ks > 2, assume that == min[pz(i) (i) < k) > O, and assume that the discriminator D is 8' --ssuficient for all 1 j S m. If (depending on 3) is sufficiently large, and if l (depending Q& from Algorithm satisfies
and 5' is sufficiently large, then the final output matrix
lim Pr (1Ω0--0ol < 4k h- 1--(2 (2g((())) ) n-000
lim 700
(39)
22

---

Under review as a conference paper at ICLR 2021
Proof. Following the notation of Theorem B.14 note that 2E' 4k 1 (22) (where h(x) is strictly increasing function defined in ()), and note also that gap(D), hence the assertion follows from Theorem B.14 by choosing arbitrarily close to gap(D).
Corollary B.16. Let 8' > O. Assume that the initial conditions (on т, m, n, E, 3,9, given in Algorithm]] 7 are satisfied. Assume 2 2, and assume that the discriminator Φ3 is 8' S'uffffccinnt for all S m. Also, assume that for every possible label E A (1,..... k), there is at least one instance D with i as its correct label. Ifr (depending on 3) is sufficiently large, and if & (depending on and ) is sufficiently large, then the final oulput matrix QD from Algorithm [ converges in probability QD as m oc, + 50, and N oC. (Here, is the number of instances D.)
Proof. This immediate from Corollary B.15 and Lemma B.11
B.5 PRECISE REFORMULATION OF PROPOSED ALGORITHM
In the previous few subsections, we have introduced new notation and terminology, so that we are able to give precise statement of our consistency result (Theorem B.14). Correspondingly, using our new notation and terminology, we shall also give, in this subsection, an equivalent reformulation of Algorithm] | from the main paper.
Algorithm 2 A precise formulation of algorithm to estimate Qp
Require: integers r, m, l 1.
Require: threshold 33 > 0, and a separable Rd-valued random function on 1(D)).
(9) S [0, 1] Require: Ω = (1)
k a valid a-sequence with vectors.
1: Initialize empty list L.
2: for = 11...... m do
3: Generate observed value D D(62
4: for s = 1...... do
5: Generate independent observed values Dat)) D(2)) D!22..... ..., .(()
6: Let Φ be discriminator trained r-fold on (D)) .g) with threshold 3
7: Compute s' := min(s: s: S < l, there exists 1 I S n such that D(u) E $
#[Note: s equals $ best in Theorem B.14 By default, min = -c.]
(5)
8:
if s' oo then
9:
for 1... do
Generate observed values for random matrices E' = E(T and Piln) E g(1(5) (3) Compute Q! sulve (E7)5) + + (
10:
#[Note: Computation of Q) involves solving system of k2 linear equations in k2 variables.] #[Note: Unique solution to linear system exists almost surely.]
if unique solution exists in computation of Q then
12:
13:
Insert matrix
Q into list C.
14: return mean of matrices in L (This is our estimate Qp for QD.)
B.6 How TO CHECK FOR SEPARABLE RANDOM FUNCTIONS?
Roughly speaking. Fig. 3 captures the intuition on how check experimentally whether a candidate vdavuleed random function on [[[ is approximately separable. Suppose D......, D.,, is sequence a-increment datasets for distinct vectors noise levels. Since is random function, we can repeatedly call g(Da,) to get sequence of vectors in Rd, say of length (i.e. each of the r entries is a vector). As elaborated in Section 2.3 these sequences of length which correspond to different values a,, are the datapoints for training discriminators; each sequence is a single datapoint for training a discriminator $. For our random function be separable, the datapoints (sequences) generated using particular value for should, with high probability, be distinguishable from datapoints (sequences) generated using different value for a. Using Fig. as example, notice that for each considered noise rate (corresponding
O1,..., ozg i.e. corresponding different
23

---

Under review as a conference paper at ICLR 2021
a aa==aa, (a)...,))) we have plotted a coordinate-wis sequences generated using a = (a......) a), where these sequences associated to Da are repeatedly generated using multiple random sceds. We call this coordinate- wise minimum-to toa-uummtt--miimummm range "hand". Now, notice that different bands, corresponding to different values for a, are already "visually separable" in our given plot. When we train a discriminator T on such sequences (datapoints), those sequences in the red band are treated as "positive" datapoints, while those sequences in the blue bands (of various blue hues) are treated as "unlabeled" datapoints. The goal for & is to identify which blue band is "most indistinguishable" from the red band, and then use the a: value corresponding to the identified blue band infer a single intermediate estimate of the noise transition matrix. For this idea to work, the blue bands (for different values of ()) should themselves be distinguishable (i.e. "separable") from each other. By "distinguishable.. we mean that a machine learning model (we used decision trees in our experiments) is able to distinguish (i.e. "separate") different blue bands. So informally, a candidate random function g is "separable" if sequences of g( are (with high probability) distinguishable for different values of a. Therefore, we have experimentally verified (see Fig. 3) that 9LID is a suitable function that is empirically (approximately) separable.
cottimmuuttt-mmmminn range of the entries for
B.7 STRIKING CONNECTIONS TO SHANNON'S S CODING THEOREM
The significance of our proposed information-theomm
framework is not our newly introduced notion H (D) of "the entropy of a DILN" per se, but rather the idea of how this notion H (D) is used to define typical sets of random derived DILNS of 'D (see Definition p. and correspondingly, how the idea of typical sets is used to define our notion of separable random functions (see Definition 2.3
Generally speaking, (D) is a compact notation that is very useful for us to define typical sets (of random derived DILNS of D) in Definition 2 This is very similar the scenario of defining typical sets of random variables, in the context of the asymptotic equipartition property (AEP) theorem; see, c.g. Chapter 3.1 in Cover& & Thomas (2012). Notice that the AEP theorem (Thm 3.1.1 in Cover & Thomas (2012) is essentially direct consequence of the weak law of large numbers. Its precise theorem statement, usually formulated in terms of the entropy of random variable, could equivalently be formulated without any mention of, or without any interpretation involving, the notion of information entropy. Similarly, the notion of "typical sets" of random variables makes sense in the general context of probability theory, without necessarily needing any chormatiin-tteoreti interpretation.
Intuitively, we should still think of "typical sets" of a random derived DILN of D as "typical" sequence of DILNs, where "typical" has a precise meaning in terms of our notion of the entropy of DILNs. Just like how typical sets (of random variables) theorem, our notion of typical sets of random derived DILNS of D are crucial for proving our consistency theorem. Just like how we should think of channel coding in terms of the entropy of random variables, we should also analogously think of label noise estimation in terms of the entropy of DILNs.
crucial for proving Shannon's 's coding
As we have initially described in Section 2.3, and subsequently detailed in Appendix | B.4 the notions of "typical sets" and (joint) AEP are crucial for proving our main consistency result Theorem 2.6 In fact, Theorem 2.6 be interpreted as an "inverse" analog of (one direction of) Shannon's channel coding theorem. Perhaps, the separable random function g. required as input to our estimator (Algorithm D is analogous to a (random) error-correction code in channel coding.
The idea of "seeparablltt"" for random functions could serve as a guide for the design of future estimators for QD. It is plausible (likely) that the convergence rate for our consistent estimator may depend on the choice of this separable random function g. Hence, building on the parallelism between separable functions and error-correction codes, we pose the following question: Could we obtain more efficient estimators for Qp by designing "better" separable functions for DILNs, analogous to how more efficient error-correction codes were designed to further improve communication over noisy channel?
We are excited by the interesting questions that naturally arise from this parallelism, especially concerning the design of new and "better" estimators for noise transition matrices and more general noise models, independent of classification accuracy.
24

---

In our experiments, we synthesized a-increment DILNS of DD using only "uniform" vectors i.e. every vector (*) in our a-sequence can be expressed as (s)) a, 1, for some 0 a < 1. (Here, 1, denotes the all-ones vector in R should be noted that our choice use only "uniform" vectors Under review as a conference paper at ICLR 2021
C IMPLEMENTATION DETAILS
Algorithm provided below describes in detail an explicit implementation our proposed framework to estimate QD. based on the use of LID-based discriminators. Broadly, there are three stages in our implementation, and correspondingly, we organize the rest of this section into the following three subsections:
Section
Gathering of LID sequences.
Section
Training of LID-basee discriminators.
Section
Final computation to estimate Qz.
Algorithm 3 Implementation details to estimate QD-
Require: D, a dataset with instance-independent label noise.
Require: Σ, a collection random seeds, with |Σ| 2 10.
Require: A valid a-sequence Q = (a(").....aa
#[Stage 1: Gathering of LID sequences]
1: for each random seed in do
2: for each a, in f2 do
3: Generate (t2 dg-increment DILN D...
4:
Generate L.DD sequences for D, from neural network.
#[Stage 2: Training of LID-based discriminators]
5: Consolidate all generated LID sequences (from all random seeds) for initial training of LID-based discriminators.
6: for each triple (i.e. three seed collections) do
7: Train discriminator & on triple to produce a recall r and a vote sequence.
8: Initialize a fine-tuning list F containing all the triples with recall r 2 0.9.
9: Refine list
10: Initialize empty list Q.
11: for each triple F
12: Fine-tune discriminator trained the triple.
13: the discriminator is well-trained (i.c. able to produce required recalls), then add it to Q.
14: if Q < 2 then
Add least 1 new random seed E. Go line 1.
16: else
#[Stage 3: Final computation to estimate Qp]
17:
Get prior.
18:
for each well-trained discriminator in Q do
Compute an intermediate estimate Q for each recall do
19:
20:
Compute the mean of intermediate estimates Q with the same recall.
21:
22:
Compute the mean Qp of all means of intermediate estimates.
23:
return QD (This is our final estimate for QD.)
C.I GATHERING OF LID SEQUENCES
for (*) is an implementation simplification, stemming from our limited computational resources. Ideally, with no computational constraints, having an a-sequence containing "non-uniform" vectors (s) (i.e. whose entries are distinct) could potentially improve the final estimate, albeit with a lot more trials.
For CIFAR-10, 10, a fixed a-sequence = (a())... ...., (9) is used throughout our experiments (i.e. Ω is fixed, consider various random seeds). We restricted every Ω to be of the form
25

---

Under review as a conference paper at ICLR 2021
(a....,aa) where the values of used given follows:
0%, 30%, 83%, 84%, 85%, 85.4%, 85.8%, 86%, 86.2%. 86.4%, 87.6%. 87.7%, 87.8%, 99, 88. 88.0% 88. 1%, 88 2%, 88.3%, 88.4%, 88.5%, 88.6%
For Clothing added extra 90.9%, 91.1%, 91.3%, 91.4%, 91.5%, 91.6%. Notice that these values for a are not uniformly spaced apart; rather, they are concentrated in the range (83%, 88.6%) (for Clothing [83%, 91.6%]. This is because high value of is typically required for the corresponding a-increment DILN of 'D to have near-maximum entropy, unless D already has a significantly high noise level, e.g. > 80%. (We define the noise level of D be the probability that randomly selected instance of 'D has a given label that differs from the correct label.) To accurately estimate the noise level of D, we recommend choosing finer a-sequence, if computational resources allow for it. However, as a compromise, we have opted to use the above set of values for a in our experiments.
C.1.1 TRAINING OF NEURAL NETWORKS
To generate LID sequences for the CIFAR-10 dataset KKrihhvsky et al. 2009), the following 12-layer convolutione convolutional neural network (CNN) is used]
Two convolutional layers with 64 out channels with filter size of 3-by-3 and padding of size 1, each followed by ReLU activation function. Max pooling of size of 2-by-2 is applied after the last ReLU activation function.
Two convolutional layers with 128 out channels with filter size of by 3 and padding of size 1, each followed by a ReLU activation function. Max pooling of size of 2-by-2 is applied after the last ReLU activation function.
Two convolutional layers with 196 out channels with filter size of by 3 and padding of size 1, each followed by a ReLU activation function. Max pooling of size of 2-by-2 is applied after the last ReLU activation function.
Output vectors are flattened.
Fully connected layer with 1024 (hidden) units, which is followed by a ReLU activation function.
Fully connected layer with 10 output units, whose weights are set be non-trainable (i.e. frozen).
The above model architectures are used when the dataset size is "relatively" big. When the size is small, for example, less than 40, 000 sample the LID sequences generated could be identical even the level of label noise present in the DILNS are not similar. For instance, in Fig. 3 the given datasets in both plots are clean, but the top plot corresponds to the intact CIFAR- 10 dataset with 50, 000 samples, while the bottom plot corresponds to a subset of the CIFAR-10 10 dataset with 70% anchor-like instances removed, i.c., with a total of 15, 000 samples.
For noise levels of 80% and 85%, the LID sequences in the top plot is still "visually separable" except from epoch 9 to epoch 17. In contrast, the LID sequences on the bottom plot for the same noise levels (80% and 85%) overlap with each other across almost all training epochs, until they become stagnant the 23rd epoch. We posit that such significant overlaps could vitiate the effectiveness of discriminator & in distinguishing baseline DILNs from non- non-baseline DILNs, when + is trained on such overlapping LID sequences.
Therefore, to further differentiate the LID sequences, we used the trials described as follows: (i) increase the number hidden units in the last fully connected (fc) layer, (ii) increase the number of
"Although this CNN is trained for the CIFAR-10 classification task, achieving high classification accuracy not our goal. Instead, our goal is gather LID sequences from the training phase. For example, given dataset with symmetric noise rate 50%, when 80% uniform a-vector is used, best test accuracy around 25%. While training baseline DILNs for LID sequences, the test accuracy is around 10%, which is equivalent to "random guessing" (since the labels in baseline DILNs are by definition chosen uniformly at random). Despite the seemingly low test accuracies, these LID sequences sufficient for T
training data for the discriminator
'In one of our trials, as part of our comparison with MPEIA, we used the CIFAR-10 10 dataset with 90% samples removed from one class. To gather L.ID sequences for the resulting smaller subset of CIFAR-10. -00 we used the same neural network model architecture as in the case when the dataset is intact.
26

---

Under review as a conference paper at ICLR 2021
convolutional layers, (iii) reduce the training batch size, (iv) fix the weight of the last fc layer, (v) do not use softmax and batchnorm; and (vi) do not use random crop during training. See Table 4 for adjustments made when smaller subset of the original dataset is used. Note that did not continue using 8192 hidden units in the last fc layer for CIFAR-10 with 70% anchor point removal. This is because if the batch size is small or if the number of hidden units in the last fe layer is increased, then the training time would increase significantly. Therefore, 4096 number of hidden units was used instead.
For Clothing I,, we used ImageNet-Pretraing ResNet-18 (PyTorch version). An fc layer with 512 hidden units is added fe layers in total) and the last fe layer is fixed without updating weights during training. We refer this model as "ResNet19".
Dataset
CIFAR-10
Amount of anchor-like instances removed
0%
40%
70%
Number of convolutional layers
6
Number of hidden units in the last fo layer
1024
8192
4096
Batch size
128
128
Table 4: A summary of the main differences while training CNN to generate LID sequences for CIFAR-10 10, when different amounts of anchor-like instances are removed.
For training, after normalization, random horizontal flip with probability 0.5 is applied for CIFAR-10 as part of data augmentation. The initial learning rate is 0.01, which is reduced to 0.001 at the 40th epoch for CIFAR-I0. We used stochastic gradient descent (SGD) with a momentum of 0.9 and weight decay of 10-4. Training is stopped at the 45th epoch for CIFAR-10.
For the Clothing M subset, images are first resized to 256X256. During training, images are randomly cropped to size 224X224 then random horizontal flip is applied with probability 0.5. During test time, images are first resized to 256X256, then centrally cropped to 224X224. For normalization, we used mean = [0.485, 0.456, 0.406] and std = [0.229, 0.224, 0.225] for the 3-channel RGB images. The initial learning rate is 0.001, which is reduced to 0.0001 at the 5th epoch. We used stochastic gradient descent (SGD) with momentum of 0.9 and a weight decay of 0.05. The model is trained for 6 epochs to gather LID sequences, with batch size 32.
In our experiments for all datasets, our computation of LID sequences follows the same process as given (Ma et al. 2018a), with the following exceptions:
1. To remove unwanted randomness in any LID sequences computed, we re-implemented their code in PyTorch. This ensures that any random function we invoke is completely determined by the selected random seed. The unwanted randomness in the original Keras implementation includes (although not limited to) randomized weight initializations and non-deterministic cuDNN nub-routines.
2. The weights in the last fully- oolly-connected (fc) layer of the neural network are fixed throughout training, so that all weights updated during backpropagation are used in the computation of LID sequences. (Recall that LID sequences are computed using the output vectors from the last hidden layer.)
3. In (Ma al., 2018a), 1280 samples are randomly selected from the whole dataset throughout the training epochs to compute one LID sequence. In contrast, we generated 50 random sets of 1280 sample indices to compute 50 LID sequences for +. each epoch, the LID scores are computed from the fixed samples.
C.1.2 COMPARISON OF NEURAL NETWORKS USED FOR CIFAR- AND CLOTHINGIN IM
To ensure a fair comparison, we chose the same backbone neural network architecture across all baseline methods, and we used a smaller architecture for our method. As far as possible, we tried to the same number of training epochs across all baseline methods. However, the different methods are rather distinct, and employ various techniques for their estimation of QD, such as the augmentation of the neural network architecture (e.g., one extra "distinguished" softmax layer for
27

---

Under review as a conference paper at ICLR 2021
S-model), schedule using multiple loss functions for training (e.g.. T-Revision uses 3 loss functions in total for training). For a more comprehensive overview of the subtle differences across the various methods, please Tables and 6 which explicitly specify the neural network architecture used, the usage of neural network, the type of loss functions, and the number of training epochs for different stages (including the computation of priors, if any).
(analogous) prior NN no. of training epochs (default loss:
main method NN no. of training epochs (default loss: crossentropy)
(analogous) prior NN structure
main method NN structure
CIFAR- 10
crossentropy)
ResNet18 (to initialize matrix) na
ResNet18 + softmax layer
S-model
20
100
Forward
ResNet18
120
ResNet18 (with
200 (reweight loss)
8 (to initialize matrix)
T-Revision
"slack variable"
component)
100 (revision loss)
12-layer CNN (6
ResNet18 (to oblain prior)
ours-
20
conv layers, to gather
45
LID sequences)
ResNet18 (ImageNet pretrained)
MPEIA
MPEIA doesn't 't use NN in its main method.
12-layer CNN (6
ours-2
We used MPEIA's estimate our prior.
conv layers, to gather
45
LID sequences)
GLCC
na
na
ResNet18
120
12-layer CNN (6
ours-3
We used GL.C's estimate as our prior.
conv layers, gather I.ID) sequences)
45
Table 5: Neural network (and its usage), training losses and training epochs of all the baselines for CIFAR-10. Some methods, S-model, T-Revision, ours-1, ours-2 and ours-3, require "prior model" to initialize noise transition matrices for formal estimation. While some method, T-Revision, trains NN with special losses in its main method.
(analogous) prior NN no. of training epochs (default loss: crossentropy)
main method NN no. of training epuchs (default loss: crossentropy)
Clothing subset
(analogous) prior NN (ImageNet pretrained)
main method NN (ImageNet pretrained)
ResNet50 initialize matrix)
ResNet50- softmax layer
S-model
10
10
Forward
na
ResNet50
10
ResNet50 (with
ResNet50 initialize matrix)
10 (reweight loss)
T-Revision
10
"slack variable"
+ 10 (revision loss)
component)
ResNet19 (to oblain prior)
ResNet19 (lo gather
ours-1
10
6
LID sequences)
ResNet50 (to
MPEIA
10
MPEIA doesn't use NN in its main method.
obtain features)
ResNet19 (to gather
ours-2
We used MPEIA's estimate as our prior.
6
LID sequences)
GLC
na
ResNet50
10
ResNet19 (to gather
o
used GLC's estimate as our prior.
L.ID sequences)
Table 6: Neural network (and its usage), training losses and training epochs of all the baselines for Clothing subset. Respective prior models and losses are summarized.
C.1.3 LID PLOTS
Fig. Bs is provided to show that LID sequences are effective in distinguishing datasets with different entropies. We used 4 clean datasets as the underlying dataset D: CIFAR-10 intact (top plot in Fig.
28

---

Under review as a conference paper at ICLR 2021
B) CIFAR-10 with 70% anchor-like data removal (bottom plot in Fig. For every a-increment DILN (shown in blue) or baseline DILN (shown in red) of D, we generated 5 such DILNs. The noise transition matrices are of symmetric form and the noise levels inserted are 0%, 60%, 80%, 85% and 87.8 37.8% (colored from the lightest blue to the darkest). We computed 50 LID sequences for each DILN, which corresponds to 50 datapoints in each epoch. To visualize the 50 sequences of DILN, only the maximum and the minimum scores are displayed for each epoch. For CIFAR- 10, this forms a band with 2 lines over the total 45 epochs. The same random seed used for all the plots.
C.2 TRAINING OF LID-BASED DISCRIMINATORS
Each LID-based discriminator & is trained using positive-unlabeled bagging (Elkan & Noto 2008 Mordelet & Vert 2014), with decision trees used as our sub-routine. We used 1, 000 trees and the number of unlabeled samples to draw and train each base estimator is 50.
C.2.1 INITIAL TRAINING
The LID sequences from a-increment DILNS are treated as unlabeled samples while those from baseline DILNs are treated as positive. For CIFAR-10 10, although the maximum noise level a, injected into D 88.6% to synthesize derived DILN of D, we used the LID sequences from a, up to 88.3% for initial training. It is recommended to reserve some LID sequences associated to the high value as during the initial training. The reason is that it could hard for a discriminator to get a good recall the positive samples (LID sequences from the baseline DILN) and large number of negative samples (LID sequences from DILNs with 0₂ > 0.883) are very similar. However, for Clothing IM, we did not reserve LID sequences with high a values, for the purpose of training ease. Recall that a a in-nnreemett DILNS and a baseline DILN from the same common random seed is collectively called "seed collection". Any three different seed collections called "triple", The discriminators would be trained on the LID sequences from all possible combinations of triples. In our experiments, we used least 10 random seeds for each matrix in CIFAR-10 10 and 20 random seeds for Clothing M. We do not use any augmentation or normalization of the LID sequences when training 4
trained discriminator & predicts whether an input LID sequence is similar to the LID sequences generated from baseline DILNs. If & assigns a score of > 0.5 to some LID sequence, then this LID sequence is predicted positive and one vote is assigned to its respective (*)) If the score is instead < 0.5, then 0 vote is assigned. The vote sum of (s) represents the number of LID sequences a discriminator "considers" to be baseline-L.ID--ee --w..--Deeseueeessaaakee.e The vote sum sequence of all the (() in the a-sequence is called a "vote sequence". A trained discriminator produces recall and vote sequence.
C.2.2 FINETUNING
After the initial training, all the triples come with their recalls and vote sequences. We only select those with recall above 0.9 and put them in list F for further fine-tuning, which indicates possibly well-trained discriminator and similar label distributions in both DILN Do (the baseline dataset) and D, (synthesized from D by injecting noise a.).
Triples with recall above 0.9 are added into a list J. and we would further refine the list for better Qo estimation. For CIFAR-10, if the total number of non-zero votes of all the triples in F before noise level 0.85 is above (for Clothing IM, the noise level threshold is 0.86, since Clothing I M has wider range of values), we use triples with low recall < 0.92 and abandon the remaining. Else, we use triples high recall > 0.98, Given that (for CIFAR- 10 only), if the number of non-zero votes from noise levels of 0.85 to 0.86 more than 4, only recall 0.98 used. The intuition is that if the presence of the number of non-zero votes before noise level 0.85 (or a, < 0.85) is not negligible (we say 2 4 in this paper), QD could potentially possess high noise level. as "significant" number of LID sequences from a, < 0.85 can be recognized as similar to the baseline's by Q. Experiments show that when D has high noise level, triples with low recall (S 0.92) can give better estimate while if D has low noise level, then high recall (2 0.98) is preferred. Therefore, based on recall above 0.9, further narrow down the range recalls of the triples to do fine-tuning. Let the new range of recalls be R.
29

---

Under review as a conference paper at ICLR 2021
We then re-consolidate the LID sequences with the range of a-sequence according to R to finetune Q. Re-consolidation of LID sequences is necessary, because different sets of recalls require different a-sequences to estimate QD. The higher the recall, the smaller the range of possible vectors we are allowed to use in the a-sequence. If an inappropriate o--equence is used, then the matrix QD could have illegal entries (i.e. with values 0 or > 1). During the initial training, for CIFAR-10, 10, consolidataed with a I 0.883, then select triples with recall above 0.9. For Clothing 1M, the maximum a used for initial training has noise rate 91.6%. Now with refinement, the range of recall is narrower, the respective range of LID sequences would have be adjusted for later fine-tuning.
LID sequences
With the re-consolidated LID sequences, we can fine-tune & for the same triple, T, for five times. Let the new recall during fine-tuning be 7 and the old recall in the initial training be 7. If for least times, we can stop fine-tuning, Else, we abandon this triple. And now the discriminator for T is considered well-trained, which comes together with r' and the new vote sequence. In the new vote sequence. the a, with the highest number of vote sum is denoted as top-voted a". and top-voted a' would be used for Qp estimation.
For each D. there shall be at least discriminators well-trained. Otherwise, more random seeds are required to synthesize DILNS of D, generate LIDs and train Tb
C.3 FINAL COMPUTATION TO ESTIMATE QD
C.3.1 PRIORS
To learn QD. a prior, P, is used to help define the structure of Qp. For CIFAR-IO, we used ResNet- 18 (He al. 2016) train 90% of the given noisy dataset for 20 epochs and validate on the 10% instances. For Clothing I M, we used ImageNet pretrained ResNet18 with an extra fc layer (512 hidden units) to train and validate it for 10 epochs. For respective datasets, the optimization procedure used are the same as given in (Patrini et al. 2017). The probabilities of the training instances from the softmax layer are recorded. The probabilities from the epoch with the highest validation accuracy is used to compute a prior. Let Yv,, i), be the j-th output from the neural network's 's softmax layer for some sample with label i, and let the set of samples with label be S,, i.e.
1 Σ (ynns
P.j =
S
RES.
C.3.2 FURTHER SIMPLIFICATIONS MODELING
Consider an arbitrary a E [0, 1] Recall that when we equate the random matrices QT = QD., we get the following equation for each entry:
(1 F. = (1 a3) + Σ 1
E (for all 1 S ú,j S k) (40)
15iCk (F)
To simplify computations in our estimation, for each row, we estimate only one entry b.j and the remaining entries shall be proportional to Ut.j according
prior. This reduces the estimation "burden" from 2 entries to k. The coordinate (i.j) is determined by the maximum entry's location of
Pi. the i-th row in the prior: j = argmax,, m Pi,m The entry qi is substituted with Σkjz PLR.
4.,)).
Next, estimate EX, and Ex,y. For D, let the binary random variable X,, be if the n-th sample has been assigned a wrong label. The total number of instances in is N. Hence, X,, is a Bernoulli random variable with parameter k-1 and the noise level in D is Mn X.
N = k-1 + E., where &
E is a random variable that approximates the relabeling process. By the central limit theorem, we X, is approximately normal with mean &
infer that ΣN n=1 N variable following standard normal distribution. Normalizing, we get:
k-1 k-1 and variance NE2
Let be a random
ΣN 1
X, N
k-1
D
k-1
k-1
NK
NR
30

---

Under review as a conference paper at ICLR 2021
Let the recall from the well-trained discriminator be r', where 7' = Pr(--0 S 2 8), or 1ー P(z I -0). From the standard normal distribution table, 0 can be found when is defined.
Therefore E. -- -0 R-1 We make a simplification that _ FE R E for all (i.j). Both random variables EY, and E. are assumed to follow multivariate normal distributions, with unknown parameters to us. To further simplify the estimation, we model both random variables with common random variable " "E". This simplification has been shown reasonable by experiments:
NE
Ei = -(k 1)
and
E = (k- - 2
Suppose R = {ri...., Tm)). For each S S let I, denote the set of all estimates with associated recall rs. Therefore, our final estimate for QD is:
II D
I2
D RELATION TO THE INFORMATION BOTTLENECK THEORY FOR DEEP LEARNING
The momentous work on the Information Bottleneck (IB) theory for deep learning (Tishyy & Zaslavsky 2015 Shwartz-Ziv & Tishby 2017) has spurred much interest and discussion; see (Gabrié et al. 2018) Saxe et al. 2018). A key aspect proposed by the IB theory that the training of a deep neural network (DNN) consists of two distinet phases: An "expansion" phase where the mutual information between layers increase, and a "compression" phase, where the mutual information between layers decrease. The notion of local intrinsic dimensionality (LID), which we used as an essential ingredient for a concrete realization of our proposed framework, was in part motivated by this theory. was reported in (Ma al. 2018c) that for their experiments on training DNNs, the LID scores of the training epochs also exhibits a similar two-phase phenomenon: An initial decrease in LID score, then either an increase in LID score or a stagnant LID score, depending on whether there is label noise not, respectively. As part of our experiments, we synthesized multiple datasets with varying entropy, and generated multiple LID sequences for each synthesized dataset. Although focus is the estimation of the noise transition matrices of datasets with instance- induuneedddeeeddentt label noise, a by-product sequences, some of which the two-phase phenomenon is not obvious. Notice that in Fig. included multiple plots of LID) sequences at various entropies, which may be independent interest other researchers (especially those directly working on the IB theory). A caveat is that LID scores are distinct from the mutual information between layers, but LID scores could still be interpreted as measure of model complexity, which presumably have close connections the generalizability of deep learning.
our work is that we observed a very wide spectrum of behavior for LID
have
31

---

Under review as a conference paper at ICLR 2021
The given dataset D: CIFAR-10 intact
27
22
12
2
3
11 13
19
21
27
29
35
37
43 45
noise rate 0% max
noise rate 0% min
noise rate 60% max
noise rate 60% min
noise rate 80% max
noise rate 80% min
noise rate 85% max
noise rate 85% min
noise rate 87.80% max
noise rate 87.80% min
baseline max
baseline min
The given dataset D: CIFAR-10 with 70% of anchor-like instances removed
27
17
5
7
11
13
15
17
19
21
23
25
27
29
31
35
37
39
43
45
noise rate 0% max
noise rate 0% min
noise rate 60% max
noise rate 60% min
noise rate 80% max
noise rate 80% min noise rate 87.80% max baseline min
noise rate 85% max
noise rate 85% min
noise rate 87.80% min
baseline max
Figure 3: LID sequences visualization for clean CIFAR-10 10 intact D (top plot) and clean CIFAR-10 with 70% of anchor-like instances removed as DD (bottom plot). The æ-axis represents epochs, and the y-axis represents individual LID scores (at each epoch). Notice that for each considered noise level a (corresponding to (a...., a)), we have coordinate-wist minimum-to to-toximmmm range of the entries sequences generated using (a (a..... a). where these sequences associated to D. are repeatedly generated using multiple random seeds. We call this coordinate- wise minimum-to- maximum range "band". Blue bands represent LID sequences associated to a-increment DILNs with noise levels 0%, 60%, 80%, 85% and 87.8% (from lightest blue to darkest blue). Red bands represent LID sequences associated to baseline DILNs.
32


Reviews:
[{"review_id": "jKQyMo3SdjK", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of learning the noise model in a classification problem. The basic setup is that\nX -> Z -> Y\nis a Markov chain, where X are the features/input to the classifier, Z is the true label, and Y is the observed noisy label. The term \"instance-independent label noise\" refers to the fact that the law of Y | Z doesn't depend on X. The goal is to learn the noise model, i.e. the transition kernel Z -> Y. \n\nI feel the writing clarity could be improved in places. The definition of DILN in the main text is confusing (does it include the noise model or not?) although the presentation in Appendix A is somewhat clearer. A lot of notation is introduced and it makes it difficult to read the main text -- for example the algorithm description depends on a \"valid alpha-sequence\" as input and this is not defined until the appendix. An informal definition in main text would be helpful.\n\nAs far as I understood the theorem statement, it says that if the algorithm is given as input a 'separable map' g then it is possible to learn the noise model, and the main difficulty to apply it is to construct an efficient separable map (which in practice, they attempt with decision trees + LID scores). It would be nice if the authors discuss the conditions under which such a separable map is guaranteed to exist. (And ideally, under which we could hope to find such a map.)\n\nOverall, I think there may be some interesting ideas in this paper, but I did not find the results to be very strong support for the claims made (see other notes below regarding the experiments). I also think the paper could benefit from clearer writing. So right now, I would tend towards rejection.\n\nOther notes:\n* The beginning of the paper suggests that the key contribution is to learn the noise model without needing to \"accurately\" learn a classifier X -> Z. However, if I understand right the final algorithm based off of \"Local Intrinsic Dimensionality\" (LID) scores requires training a 12-layer CNN to predict the label from X so it seems to be somewhat weak support for this claim? \n\n* I found the definition of f_{matrix} confusing. If U[D] indicates we throw away the information about the noise model, then what does the map f_{matrix} : D' |-> Q_{D'} mean, is Q_{D'} is still determined from D'? Is this a 'random map'?", "extra_scores": {}, "extra_text": {}}, {"review_id": "dwG5d1LF4ou", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of estimating instance-independent label noise. More formally, it is assumed that the true labels for any data point are modified based on a noise transition matrix, and the goal is to estimate this noise transition matrix. The paper proposed an information-theoretic approach for this task, the key idea behind which is to estimate if a particular dataset has maximum entropy with respect to the labels. This estimation problem is solved using a recent discovery that the training dynamics of a neural network can be used to infer the presence of label noise.\n\nStrengths:\n\n1. The problem of learning with instance-independent noise has received some attention from the community and could be of interest. \n2. The proposed information-theoretic framework is conceptually interesting, and also comes with some theoretical guarantees.\n\nWeaknesses:\n\n1. The paper does not show that the approach leads to better downstream neural networks in the presence of instance-independent noise. The current experiments only show that the approach can find better transition matrices Q in terms of KL divergence. Since this is simple, synthetic noise model this is not very convincing. The paper needs a much more thorough experimental evaluation to demonstrate that the approach can improve the state-of-the-art on downstream learning tasks. The experiments are also only done on CIFAR-10, whereas most of the related work considers at least a few other datasets.\n2. I also think that the setting needs to be motivated better. As can be seen in Table 1 and 2, MPEIA and GLC which need only 0.5% clean samples can actually do better than the proposed approach, which is this such a hard requirement? I also don’t find the ours-2 and ours-3 results convincing and a bit misleading, since we should then also consider combinations of other models.\n\nOverall, I am not in favor of acceptance because of the experimental evaluation not being convincing. However, the proposed algorithm is interesting and has potential, if the authors can build more on it in the future then it should make for a good paper.\n\nOther points: \n1. The discussion of “anchor points” and “mixture models” is quite unclear in the introduction.\n2. I found the discussion and notation in Section 2.3 to be a bit convoluted. I think there should be a much clearer description of the approach.\n\n--------Updates after author response--------\n\nI thank the authors for the detailed response and appreciate the additional experiment. However, I still believe that evaluation on downstream tasks is essential to demonstrate the superiority of the approach, and I unfortunately do not agree with the authors that it implicit that the approach will yield better downstream networks. Therefore, I cannot raise my score, but would encourage additional experimentation. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Cf0WieLsHhF", "reviewer": "AnonReviewer1", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "***\t\n\nSummary:\n\nThe paper aims to develop an information-theoretic framework for learning the underlying model from data with instance-independent label noises. It first formalizes the problem and relevant definitions with information measures, such as conditional entropy and conditional KL divergence, then argues that if the underlying model is well-separated, the proposed algorithm will be consistent in learning the noise-labeling matrix. At the heart of the algorithm is a discriminator being able to measure the labelings' noise level. A class of discriminators based on 'local intrinsic dimension (LID)' is then provided and evaluated empirically. The resulting algorithm performs well on the tested instances compared to existing ones. \n\n\n***\t\n\nReasons for score: \n\n \nOverall, I would like to give a weak reject. I like the idea of understanding and analyzing data models with label-independent noises through the lens of information theory. It is even better as such an idea leads to an improvement in practical applications. However, the paper is unsatisfiable in terms of writing and theoretical contribution. The authors may refer to the 'cons' below.\n\n\n***\t\n\nPros: \n\n \n1. The problem of learning models of instance-independent label noise is, by itself, an important and practical problem.\n\n2. The proposed framework and algorithm (Algorithm 1) are both general/flexible and work without additional structure assumptions on the noise transition matrix. Besides, the information-theoretic formulation is also natural for the following reason. A trained discriminator is used to infer how different the noise matrix is from a completely random matrix, namely, a matrix with all rows being uniform. By inserting user-designed noise and training multiple discriminators, one effectively probes the underlying matrix and, in the limit, obtains sufficient information for its recovery.\n\n3. This paper provides a useful estimator that performs well in practical experiments. In particular, it is shown that the proposed algorithm can be combined with prior ones to improve their efficiency/accuracy. \n\n \n***\t\n\nCons: \n \n1. I am concerned about the significance of the theoretical results. The major contribution is Theorem 2.5 on page 6, which states that the proposed algorithm is consistent in estimating the noise matrix. \n\n- It might be better to make the main theorem self-contained. Currently, the major assumptions appear at the beginning of Algorithm 1. \n\n- The paper suggests that its results hold under \"mild\" conditions on the discriminator. I believe this requires further clarification, especially on why these conditions are mild, given the existing literature. For example, the algorithm relies on the existence of a separable random function $g$ on $\\mathfrak U[\\mathcal D]$. I wonder if this condition can be checked in practice only by utilizing the data OR whether there is a practical scenario where this condition is automatically satisfied. Besides, how strong is this condition? Is such a condition satisfied by the random function $g_{\\text{LID}}$ used in the experiments? \n\n- The theoretical results show that the estimator is consistent if (nearly) all parameters tend to infinity, which doesn't seem practical. I don't see how this theoretical insight can guide the design of real estimators. \n\n \n2. I am also concerned about the writing of the paper due to the following reasons. \n\n- The notation is somewhat heavy, and I feel that more than half of the paper is introducing new definitions. Besides, there are few issues with those definitions/notation: 1) Notation introduced but merely used, e.g., the KL divergence between two derived DILNs on page 4; 2) Quantities undefined or defined after being used, e.g., in Definition 2.4 of a trained $n$-fold estimator,  what is $\\Phi^+$?  For another example, what is $E_{i,j}'$, referred to as \"error\" in the definition of $Q_{i,j}'$ on page 4? 3) For information-theoretical quantities, it might be better also (or just) presenting their standard forms, e.g., the key definitions $H(\\mathcal D)$ and $\\text{KL}(\\mathcal D'\\vert\\\\!\\vert \\mathcal D'')$ in Section 2.1 are basically $H(Y\\vert Z)$ and $\\text{KL}(Y'\\vert Z\\vert\\\\!\\vert Y''\\vert Z)$. Also, what is the novelty here then? \n\n- I would suggest adding more explanations about the theorem and algorithm. The paper currently spends lots of effort defining new quantities but much less in providing insights and intuitions about the algorithm and its guarantee. For example, after the heavy notation on page 5, the main algorithm is directly presented at the top of page 6, followed by its guarantee, Theorem 2.5. As the algorithm is nontrivial, it would be helpful to explain the logic and rationality. In particular, a critical definition, valid $\\alpha$-sequence, is postponed to the appendix, and I don't see why. Similar comments apply to the main theorem, as I mentioned in the last major point.  \n\nI hope that the authors can address (at least some of) the concerns/questions/suggestions stated above. Thanks.\n\n \n***\t", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the following model: The input to our classifier is the instance X which determines the label Z and we observe a noisy version of this label Y. The key assumption is that the label noise is independent of the instance, and the goal is to learn the channel from Z to Y. The main motivation is that generally algorithms that can handle instance-independent noise need to know the noise model. Thus the main contribution of this paper is to decouple the problem of learning the noise channel and the problem of learning a high-accuracy classifier. In particular they inject their own label noise and design a discriminator to test if the noise on the labels has maximum entropy. They show that their method is statistically consistent. Finally they complement this with synthetic experiments on CIFAR to show that their algorithm works. 

While the reviewers all found the ideas promising, they brought up a few deficiencies in this work which they hope could be improved in later versions. First, the writing is at times unclear and imprecise. For example, there are many places that could benefit from further discussion, particularly in terms of justifying why the assumptions are "mild" or not. Second, the experiments would be more compelling if there were an application where learning the noise model actually led to improved performance on some downstream application. Third, the approach crucially relies on having a separable map, which seems like a rather strong assumption. 
Decision: Reject