Robustness to Label Noise Depends on the Shape of the Noise Distribution
Authors: Diane Oyen
Michal Kucer
Nick Hengartner
Har Simrat Singh
Venue: NeurIPS 2022 Accept (2022)
Keywords: label noise
classification
robustness

Abstract: Machine learning classifiers have been demonstrated, both empirically and theoretically, to be robust to label noise under certain conditions --- notably the typical assumption is that label noise is independent of the features given the class label. We provide a theoretical framework that generalizes beyond this typical assumption by modeling label noise as a distribution over feature space. We show that both the scale and the \emph{shape} of the noise distribution influence the posterior likelihood; and the shape of the noise distribution has a stronger impact on classification performance if the noise is concentrated in feature space where the decision boundary can be moved. For the special case of uniform label noise (independent of features and the class label), we show that the Bayes optimal classifier for $c$ classes is robust to label noise until the ratio of noisy samples goes above $\frac{c-1}{c}$ (e.g. 90\% for 10 classes), which we call the \emph{tipping point}. However, for the special case of class-dependent label noise (independent of features given the class label), the tipping point can be as low as 50\%. Most importantly, we show that when the noise distribution targets decision boundaries (label noise is directly dependent on feature space), classification robustness can drop off even at a small scale of noise. Even when evaluating recent label-noise mitigation methods we see reduced accuracy when label noise is dependent on features. These findings explain why machine learning often handles label noise well if the noise distribution is uniform in feature-space; yet it also points to the difficulty of overcoming label noise when it is concentrated in a region of feature space where a decision boundary can move. 

Robustness to Label Noise Depends on the Shape of the Noise Distribution
Diane Oyen
Michal Kucer
Los Alamos National Lab doyen@lanl.0 gov
Los Alamos National Lab
Nick Hengartner Los Alamos National Lab
Har Simrat Singh Los Alamos National Lab
Abstract
Machine learning classifiers have been demonstrated, both empirically and theoret- ically, to be robust to label noise under certain conditions notably the typical assumption is that label noise is independent of the features given the class label. We provide a theoretical framework that generalizes beyond this typical assumption by modeling label noise distribution over feature space. We show that both the scale and the shape of the noise distribution influence the posterior likelihood; and the shape of the noise distribution has stronger impact on classification perfor- mance if the noise is concentrated in feature space where the decision boundary of uniform label noise (independent of features and the class label), we show that the Bayes optimal classifier for classes is robust label noise until the ratio of noisy samples goes above e-1 (e.g. 90% for 10 classes), which we call the tipping point. However, for the special case of class-dependent label noise (independent of features given the class label), the tipping point can be as low 50%. Most importantly, we show that when the noise distribution targets decision boundaries (label noise is directly dependent feature space), classification robustness can drop off even at a small scale of noise. Even when evaluating recent label-noise mitigation methods we see reduced accuracy when label noise is dependent on features. These findings explain why machine learning often handles label noise well the noise distribution is uniform in feature-space yet also points to the difficulty of overcoming label noise when it concentrated region of feature space where a decision boundary can move.
can be moved. For the special
Introduction
An open question machine learning is how the quality of training data, especially the labels, affects the learned model [2] [ 22 24). As an example shown in Figure we imagine a classification task for detecting cancer based on observed biomarkers. The generative model assumes that there is a hidden variable, called Y denoting whether a person actually has cancer not. Depending on the state of Y* biomarkers can be observed, denoted distribution r ~ P] The goal of machine learning (ML) is to predict the presence of cancer given the biomarkers - yet to train and evaluate the MI. model, we have diagnoses, (v), which may not always be correct (y * y" for some samples). The question of label uncertainty is thus: What happens when the observed labels, y, do not match the hidden true labels y"? Our theory concludes that the answer depends on the shape of the noisy distribution | with respect to feature space.
feature vector z, drawn from some
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

Example
P(Y RApp
Goal:
label moves
Learn
y
Data: By y
y
* DDisease (cancer
not not__cntta cancer)
prr = y/M!
p(Y = nip
closer
p(y" x))
C Observed biomarkers
y=0
y=1
L
y
y Diagnosis (cancer or not cancer)
(a) Model of label noise
(b) Effect of label flip
Figure 1: Model of label noise
(a) No noise
(b) Uniform 20% noise
(c) Class-dependent noise
(d) Resampling noise
(e) Resampling inverse
(f) Gap min
(g) Gap max
Figure 2: Scatterplot of 2- 2-dimensional 10-class (classes color and shape coded) Gaussian data. (a) original data without label noise; and with 20% label flip noise for various types of label noise distributions: (b) uniform, (c) class-dependent, and (d)-(g) feature-dependent.
Empirical research suggests that ML is often able generalize beyond label noise injected training data to make accurate predictions, particularly when the noisy label is sampled independently of
the features and the true label, i.c. P[Y X, Y] P[Y] 2 22 24 25 This is a remarkable
finding considering how messy such data appears, as shown in Fig. 26 However, this robustness label noise drops significantly when these approaches test their findings by synthesizing label noise with the assumption that the noise is independent of the features given the true class label, i.e. P[Y]X, Y"] P] other words, for given class, all samples that class are equally likely to have the same erroneous label, demonstrated in Fig. 2c We theoretically analyze the posterior likelihood
true class given noisy training labels to demonstrate that both of these types of label noise (uniform and class-dependent) behave similarly but with very different tipping points of noise level beyond which the true labels are not recoverable.
While the assumption of label noise being independent of features is convenient for generating noisy samples B realistically, we expect that label noise occurs when the features are ambiguous; such as when contradictory biomarkers are observed an oncology patient, or when an image be classified is blurry. In other words, XXY] Y"] o P Figs. Zdland] 2f show data generated with two noise distributions such that label noise most likely to occur in regions class boundaries; while Figs. and and 2g show data where label flips are most likely to occur far from true class boundaries. Our theory and empirical work demonstrate that feature-dependent label flips that create noisy class boundaries far from the true class boundaries have the most negative impact on classification accuracy, even at levels label noise much lower than the tipping points seen in uniform and class-dependent label noise.
28 is not clear that it is an appropriate assumption 24] More
naturee-space that are near

---

We demonstrate theoretically and empirically that classification is generally robust to uniform and classddependent label noise until the scale of the noise exceeds a threshold that depends on the "spread" of the noise distribution; but that beyond this tipping point, classification accuracy declines rapidly. Yet, we also demonstrate that such robustness to label noise is misleading; because our introduction of feature-dependent label noise shows that classification accuracy can be lowered significantly even for small amounts of label noise. We evaluate, for the first time, the damaging effect of feature-dependent label noise on recent strategies for mitigating label noise. We conclude that the shape of the label noise distribution with respect to feature space a significant factor in label noise robustness. Our theoretical findings should guide future theoretical and empirical work on label noise to focus studies on the most informative combinations of noise scale and shape; saving significant computational effort while improving the research community's ability to gain insight about how label noise affects learned models.
2 Preliminaries
2.1 Problem Statement
We consider the problem of label noise in which, for given data sample, (X, Y*); for some fraction of samples, the true labels y E (1....,() c) are replaced with incorrect (noisy) labels Y. The fraction of noisy samples is called the noise level. The typical paradigm for modelling such noise is using label flips 16 [2], where for each sample, there is some probability that the true label will be flipped an incorrect label. Which label it flips to is typically modelled in one of two ways: 1) uniform noise (also known as symmetrie label noise): each incorrect class is equally likely; or 2) class-dependent noise (also known as asymmetric label noise) in which some classes are more likely than others for a given true class. In the case of class-dependent noise, the noise function is typically represented as a x c label transition matrix describing the probably of a transition from Y* to Y. The number of non-zero off off-diagonal elements in each row of this matrix (or inversely, the sparsity) characterizes the spread of the noise distribution uniform, but the lower the sparsity, the further from uniform the distribution is.
[13. In other words, when spread is c- - 1, the noise distribution is
2.2 Related Work
Several methods have been developed to improve classifier robustness to noisy labels during training. CleanLab removes noisy samples from training [13. Methods like CoTeaching weight the samples infers the true label [4]. MentorNet uses a teacher- student learning approach 77. MixUp interpolates pairs of examples and their labels 28). SoftLabels
[5.21]] Approximate expectation-maxtte
treats the labels as learnable parameters [24]. Symmetric cross-entropy (SCE) uses robust loss function (25). Similar to our paper, 3 evaluates robustness of existing approaches to label noise. Chen et al. 2 shows that the noisy test accuracy is quadratic function of the noise level for the case of uniform label noise. Yet, none of these approaches are yet evaluated on feature-dependent noise.
A few papers argue for the need to consider feature-dependent label noise, but they do not evaluate Notably, two papers replace the label-fiip paradigm with real-world webly-labeles noise (which is likely feature-dependent) [8] [10. but simultancously induce a domain shift which makes analysis challenging; and the dependence on the features is unknown.
their approaches in this setting 4 24
3 Theory
We show that the estimation of the true conditional distribution |[X depends on the level of noise, as well as the shape of the noise. We define the classification problem of classes with label flips; and examine different types of label noise: uniform, class-dependent, and feature-dependent. Proofs are given in the Supplement.
3.1 Problem Definition: Classification with Label Flips
In a classification problem with e classes, we are given an n-sample of pairs (X, E Rd x {1...., c), with joint distribution determined by
fx P[X dx =k], and P\Y k] =
(I)
3

---

for each & E fl......c).
c). We want to estimate the clean posterior:
mi(()) - PlY" x x|
Rather than observing y*, we observe the noisy label with probability = (x:) where Di=1 T): (x) In other words, Y|У", X is multinomial distributed such that 1 - T/s (a) is the probability of label flip and each Me (x) influences which noisy label, i, may be
chosen. The impact of label noise is that the estimate of the noisy posterior is
mx(x) - PLY k|X x]
Σ na (a (z)m)
3.2 Uniform Label Noise
Classifiers are generally robust uniform label noise up tipping point, has been well- demonstrated empirically.
Definition 3.1 (Uniform noise) For a classification problem with e classes, given the scale of label noise, 0 S the distribution of noisy labels is constant such that:
C, for = k Vi E [L.... cf s.f. i +
(4)
Plugging the Definition 3.1 into the noisy posterior Eq (3); the noisy posterior under uniform noise is:
mx(z) mī(x)
CC c-1 m (=)))
Lemma 3.2 (Noisy accuracy) Given noisy train and test samples according to Definition 3. the noisy test accuracy of a Bayes optimal classifier is quadratic with respect to the noise level
[[[[[arg
max max (z) = Y k] m (
2
CE
c-1
Corollary 3.2.1
Given noisy train and test samples according to Definition 3.1 the minimum noisy
accuracy of occurs at c-1
Fig plots the quadratic of Eq (6) which shows that models trained noisy data will at first decrease in accuracy as tested on noisy labels, but then begin to fit the label noise rather than the true labels as the fraction of noisy labels increases beyond the minimizing point.
Theorem 3.3 (Clean accuracy) Given noisy train samples according Desinition 3.1 and clean test samples, the clean test accuracy of Bayes optimal classifier is logistic with respect to the noise level
E [[[([arg max = k) k]
m
1 1 bo (2m) 1)
where b is an arbitrary base of the exponent used in the softmax approximation to the argmax. The larger the value of b, the closer to the true maximum function.
Corollary 3.3.1 Given noisy train samples according to Definition 3.1 and clean test samples, clean
accuracy drops to
mi
For a dataset like ImageNet with 1000 classes, the clean accuracy would only drop off See Fig 3
when the noise level is above 99.9%. This finding is consistent with empirical studies [17] showing that deep learning models are robust to this type of label noise; particularly when there are large numbers of classes.

---

0.6
Clises
044
02
10
00
60
02
0.1
66
60
16
30
02
0/1
0.
1.0
(a) Noisy accuracy, Eq
6
(b) Clean accuracy, Eq
Figure 3: Theoretical accuracy of predicting noisy clean labels for uniform label noise (with
m 0.9 and b )
3.3 Class-Dependent Flips
We consider the special case of class class-dependent label noise that is also well-demonstrated empirically. Often, this class-dependent noise is defined such that 7/: for several We refer to the number of non-zero elements as the spread of the class-dependent noise function. In the least-spread case, Mjk = e for some j E e} \ {K} while Tiki = 0 for all other values
cI, {k, j..
Definition 3.4 (Class-dependent noise) For a classification problem with classes, given the scale of label noise, 0 S e < 1, and spread of noisy label distribution, S S c- 1; the distribution of noisy labels constant within each class le E cl].
1 1,
for bri=k
7ki
tais
Vi (l,...,cc of {k} and Eiÿa |Aall 8 and Eier k Uki =
(8)
Plugging Definition 3.4 into the noisy posterior Eq (3) we see that the noisy posterior under class- dependent noise depends on the spread, rather than the total number of classes:
c(s + (1-ds+t1)
mx(x) mx(x)
Lemma 3.5 (Noisy accuracy) Given noisy train and test samples according Definition 3.4 the noisy test accuracy of a Bayes optimal classifier is quadratic with respect to the noise level c and spread s:
mf (1-
c(s
E c(s 1(s+
[]a[[arg max ma (z)) = Y k]
(10)
Theorem 3.6 (Clean accuracy) Given noisy train samples according to Definition 3.4 and clean test samples, the clean test accuracy of Bayes optimal classifier is logistic with respect to the noise level
B[[([arg max max k) k)
m
(11)
(2m
1)
Class-dependent noise impacts classification accuracy in a similar way to uniform noise; however, tipping-point in class-dependent noise controlled by the spread rather than by total number of classes. Thus, even for large number of classes, the tipping point can be low 1/2.
3.4 Feature-Dependent Label Noise
We consider the more general paradigm of feature-dependee label noise which has not received much attention either theoretically or empirically. Consider the simplest feature-dependent label-flip scenario where single sample (X x, Y* k) for some fixed with true label l will have noise introduced as (X = x, j) for some j E (1....,c). No matter which noisy label j appears, the posterior likelihood of the noisy data will be reduced to (x(x) (1 p(x))m while the
5

---

posterior likelihood of the incorrect label will increase to my(x) [0m(2) + p())m)(a). In the Bayes optimal classifier, classification errors occur when:
(x)
(2(
(12)
for true label k for given point æ. Therefore, for a fixed x, the label-flip Y = that would have the most impact classification (the greatest increase of the right-hand side of the inequality) is
j arg
max te
m;(r)
(13)
An immediate consequence of this observation is that worst-case label noise is a function æ; therefore any evaluation of label noise (empirical or theoretical) that does not depend on features is optimistic.
Now, consider which samples, i.e. the shape of Makk (a), would have the most impact on clean classification accuracy. By re-arranging Eq (12). we see that the ratio my (x)/ max;g(1..... my (a) defines the optimal classification boundaries. By targeting label flips on samples z where this ratio is high, new (noisy) classification boundary can be created; as illustrated in Fig. lb
Claim 3.7 (Worst-case noise) For a classification problem with classes, the samples, I, that have the greatest impact on clean label prediction are those that maximize the ratio between the likelihood of the true class to the likelihood of the most-likels incorrect class:
for i = k
[k((z) x
max PLY 10
(14)
[|j = arg maxişeh P|Y = i/s]], vi E (l,...,cc {K}
3.5 Discussion of theoretical results
Relationship to existing theory known that label noise is not generally distinguishable from
other label uncertainty (such as class overlap) [19 20 Various approaches provide guarantees of label
noise identification through constraints on m (x) including "purity" of classes [1] 15 19 20
Other methods provide guarantees on robust learning given constraints on the level of label noise
14 26), or level noise in classification 2 13,, or only for binary classification [12), or restricted
to generalized linear models P1I In contrast, we consider the unconstrained problem to analyze the effect of label flips for any noise level and feature-dependent noise. Rather than proving guarantees about effectiveness of models under constraints; show that when such constraints do not hold, classification degrades suddenly- not gracefully.
Setting mi 1 in our Corollary 3.2.1 yields the special case given in Corollary 1.1 of (2). Our
generalization beyond the perfect classifiers (defined in our notation as mx(x) = m = 1) assumed in (2] is important because if we apply our result to the problem of identifying noisy labels (as presented in (2); then we see that the accuracy of predicting noisy labels is a function of (z)
iee. accurate prediction of label noise depends on the features even when label noise is independent of the features.
Implications The standard assumption of label noise being independent of features can lead to overly-optimistic findings on the robustness classification algorithms. We can see that if label noise is applied uniformly randomly in feature space (even if is non-uniform across classes), then even as the noisy likelihood begins to decrease, classification accuracy remains high until the likelihood estimate decreases below the tipping point.
4 Synthetic Data Experiments
The theory is validated empirically on synthetic data for which |[Y*[X] and P X] are known. Data is 2-d Gaussian with up to 10 classes, with some classes overlapping and others easily-separable as shown in Fig. 2a We also empirically evaluate 5-d Gaussian data with up to 50 classes. All code will be made available open-source.
For uniform noise, we sample y Mik according to Eq. 4 for varying numbers of classes, e E {2, 4, 6, 8, 9, 10), and noise ratio, E 0.......... 0.9, 1). For class-dependent noise, we sample

---

Noise name
mikk (2)
(k)
Uniform-x
-1-
x PLY 20
Resampling
x
PlY kt/z]]
PlY = =]
InverseResampling
PlY k([z]]
PlY = -
GapMin
P|Y*=k|']
=ell arg maxişR P\Y = i|]]]
max344 P[V==
GapMax
x maxjsa -=(x==]]]
-|y-=M|z]
= cī == arg max P(yx=
Table 1: Types of feature-dependet noise.
302
100
10
52
23
1.3
0.00
0.25
n0 leve
0.50
0.75
1:00
0.00
0.25
50.00 leam
0.50
0.75
1.00
(a) 2d noisy test
(b) 2d clean test
(c) 5d noisy test
(d) 5d clean test
Figure 4: Deep learning results on synthetic data with uniform noise.
y ~ Thk according Eq. for varying numbers of classes, c (2 6, 10); noise ratio, E (0,0.1, 0.9, 13: and spread E {1, 2. For feature-dependent noise, we sample in five different ways as summarized in Table (1) For uniform-x, the probability of a given sample flipping is constant: (x) = E; while the choice of label to flip to is proportional to the likely incorrect label: Mky (z) x P|y*=j- =j(z].
(2) For resampling noise, Takk (I) PIY k|æ]] in other words, samples that are least likely in a true class are the most likely to flip. (3) For inverse resampling,
=
mes (x)) xx PlY k|x]- i.e., samples with the highest likelihood the true class are most likely
P[Y-=A[s)
to flip. (4) For minimum--ee gap noise, 7akk (z) X maxjaa -| that the samples nearest decision P|Y'=j|=] so
boundaries are the most likely to flip. (5) For maximum max noise, Tak (z) x
max -|y
that the samples farthest from decision boundaries are the most likely to flip.
There are 100 samples per class in the training set and 100 samples per class in the test set. The feature matrices Xamin and X are the same across all trials. The corresponding noisy label vectors Y Yuiin and Y are sampled for each combination of noise settings. We also evaluate the accuracy of the held-out clean test labels Yie.. The noise level e varies from neural network with 2 hidden layers is trained; and further details of the architecture is given in the Supplement. The model trained times starting from different random seed; with the mean and standard deviation of the accuracies reported.
in 0.1 increments. A
Results Affirming existing results 2 222, and our theoretical analysis, the similarity of Figure to the theoretical expectation of Fig. is striking. The neural network is robust to uniform label noise up to point, where that tipping point depends on the number of classes. Figure gives insight into what is happening during training. We see by the very low accuracies on the noisy test labels that the model is not able fit the noise from this uninformative noise distribution. Yet, there is enough signal still in the data to learn the patterns that generalize to the clean test set. Beyond the tipping
100
100
100
accuracy
75
accuracy
75
accuracy
75
25
25
25
10
0.25
0.75
0.25
0.75
0.25
0.75
noise level
noise le
noise level
(a) Spread
(b) Spread= =2
(c) Spread
Figure 5: Deep learning results on synthetic 2D data with class-dependent noise.
7

---

1.0
140
180
EROITON papres
reaapii
guore
0.4
0.4
0.5
0.4 Inbled lovel
1.0
nobe loval
Intldd lonal
(a)
(b) c 6
(c) c = 10
Figure Deep learning results on synthetic 2D data with feature-dependent noise.
120
160
screedi pipres
aD
pigerie
nasa tovel
(a) CleanLab
(b) CoTeaching
Figure 7: Label noise mitigation methods on synthetic 2D data with 10 classes.
point (the minimizing point in the quadratic function of the noisy accuracy), the neural network begins fitting the noise instead of the true signal, and the clean accuracy drops off steeply.
Results on dlassdeependent noise as shown in Figure 5 also affirm existing results [3 25 28 and
theoretical analysis. We that the tipping point depends the spread rather than the total number of classes in the classification task. The most harmful dlas-dependent noise occurs with specific erroneous label, the tipping point
spread=1, that is when labels from given class flip occurs when the noise level is 0.5.
With the introduction of feature-dependeer label noise seen in Fig. 6 we see that the neural network is not always robust even low levels label noise. particular, the worst-case label noise, GapMax, of Claim 3.7 significantly lowers classification accuracy Interestingly, the classification accuracy from uniform-x noise is statistically indistinguishable from class-dependent noise; indicating that the dependence of (x) on is important.
0.1 and 0.2.
Fig. 7 highlights the clean test accuracy of two label-noise mitigation methods: CleanLab 13 and CoaTeaching [5]. More methods are detailed in the Supplement. At e = 0.1 both strategies improve
results compard with the baseline of Fig. 6cc But for higher levels of e, CleanLab has little effect while CoTeaching performs worse than baseline.
Table 2: CIFARIO clean accuracy. Highest accuracy for each noise setting is highlighted.
0.2
0.4
0.6
0.8
noise
Baseline
63.49
66.88
35.26
48.70)
15.28
CleanLab
88.41
88.89
88.87
83,39
86.27
86.66
21.74
73.06
81.73
4.51
7.96
50.69
MixUp
90.62
90.45
90.69
77.77
86,33
85.01
12.27
64.29
76.02
5.16
4.59
28.16
Teachhnng
87.23
67.79
71.21
50.17
8.91
SCE
86.21
86.62
87.38
57.42
82.71
84.23
15.53
42.86
63.47
10.68
6.26
15.90
Feature noise
Baseline
76.92
77.43
78.73
59.86
60.84
63.72
35.89
39.49
40.70
16.81
16.87
17.55
ClcanLab
88.56
88.47
88.55
82.47
84.30
86.03
32.06
56.90
76.04
22.10
22.58
26.37
MixUp
88,70
89.85
76.14
78.30
82.48
41.75
53.59
60.15
10.96
13.08
25.43
Co- Teaching
87.15
87.24
88.01
64.04
67.77
70.50
28.76
35.09
46.70
12.41
14.23
17.68
SCE
87.26
87.65
87.39
74.71
77.70
83.68
23.97
33.65
66.98
18.81
17.03
15.52

---

Table 3: CIFAR100 clean accuracy. Highest accuracy for each noise setting is highlighted.
0.2 8
0.4
0.6
0.8
Class noise
5
Baseline
57.20
42.24
45.49
47.81
24.32
34.17
10.37
10.63
CleanLab
51.27
52.79
53.59
32.84
40.95
45 35.06
9.11
16.36
30.30
3.83
4.10
6.60
Up
64,79
65.18
65.68
50.65
57.35
$8.27
18.64
34.07
48.23
5.00
7.58
17.93
SCE
54.88
56.18
54,93
33.72
46.87
50.54
12.59
19.96
36.70
6.26
8.72
12.16
Co-Teaching
55.85
58.66
59.65
37.79
41.83
45.29
21.11
24.43
28.00
6.72
9.28
11.57
Feature noise
Baseline
53.80
54.13
54.64
37.17
38.73
39.34
20.38
21.00
22.71
7.94
8.38
8.72
ClcanLab
51.74
52.75
53.53
33,42
36,36
40.58
11.91
14.64
22.56
6,56
6.86
8.04
MixUp
63.10
62.67
63.42
47.73
50.34
51.87
27.06
29.86
33.76
9.16
10.55
SCE
53.43
54,02
55.51
32.43
36.66
42.39
9.42
11.70
17.61
7.29
7.41
7.76
Co-Teaching
58.40
58.16
59.28
35.71
38.93
40.80
14.12
14.40
17.05
6.17
6.28
6.08
5 Image Benchmark Experiments
We compare methods for learning with noisy labels, including CleanLab with the confident joint [3]. MixUp 28), symmetric cross entropy (SCE) [3] and CoTeaching [3]: using the public-license open-source code provided by the authors. For all methods the base architecture is ResNet-32 [6] with more details including computational costs, and extended empirical results, in the Supplement. We also compare the baseline performance which is the ResNet-32 architecture without any label noise mitigation strategy.
We use the classification benchmarks CIFAR-10 and CIFAR- 100 of 32x32-pixel color images in 10 100 classes, with 60,000 images per dataset 2 according to Definition 3.4, assuming that the labels given in the dataset are the true labels Y*.
Class-dependent noisy labels Y|Y* generated
Generating feature-dependent label noise To generate label noise Y|X that is dependent features but independent from the learned classification function itself, we use preserrin image hashes [14] (7). For each image in the dataset, compute the similarity -rrearrvyi- hash, h()); which puts visually-similar (rather than semantically-similar images near each other. Then for each class, calculate the average hash, h4, which represents the "center" of the class. For class-conditional noise, we generate label flips between classes that are s-ncarest neighbors based on the hash centers and spread s. For feature-dependent noise, we generate label flips using the GapMax function of Table based on the distance from particular sample's ' hash to the s-nearest neighbor hash centers, i.e. Ply+= k|ar] x (/5)(zz) where (x) = [[((z) h& ll. We investigate two different similarity- simillrity-preserving hashes: 1) VisHash [4] which was designed to detect near-copy images ignoring changes in color and shading, so it will put images with similar shapes near each other; and 2) ((x)) is ResNet-50 [6] pre-trained on ImageNet- 1000 [I8] using the activations of the layer before the fully connected layers as the hash vector. The results for the VisHash-derived label flips are provided here with the ResNet-50 driven label flips provided in the Supplement, noting that the general trends are similar for these two types of feature-driven label flips.
Results The results for class-dependent label flips on CIFAR-10 in Table show general patterns of what our theory predicts: accuracy drops severely between c 0.4 and 0.6 when s For 2, the drop is less severe until = 0.8. Also supporting our theory, the results for feature- dependent label flips show more gradual decline in accuracy so that on average the accuracy lower for feature-dependent label flips than for class-dependent label flips when (0.2, 0.4). ). well as for higher values of when spread, s E {2, 5). Table 3 shows that similar trends hold for a dataset with much high number of classes. It is interesting to note that when mitigation strategy performing poorly (e.g. SCE on CIFARIO at = 0.2 or CleanLab on CIFARIOR at e = 0.2) compared with the other methods; then it does not seem to matter whether the noise is feature- dependent or class dess-deeendent. Therefore, we see that in general the robustness classifiers with successful label noise mitigation strategies behave differently whether that noise is feature-dependent. Feature-dependent noise reduces classification accuracy at lower levels of noise.
CleanLab and MixUp show the strongest results, but there is no clear winner among mitigation strategies for label noise; as all methods display weaknesses under various noise levels or noise types. One promising result is that the mitigation strategies tend to narrow the gap in performance between

---

handling class noise and feature noise; which is consistent with our findings on the synthetic data in Figure The strong performance of MixUp on CIFAR-
100 is probably due to it being particularly Whereas, Cleanl Lab struggles with CIFAR- 100 probably because the low baseline accuracy even low levels of noise makes it difficult to confidently predict clean versus noisy samples.
well-suited to the hierarchical nature of the classes 23 28
Conclusions
Limitations Our theoretical results are limited to the Bayes optimal classifier. As with most theory, the degree to which these results apply in practice must be explored empirically.
Future Directions The theory could be extended to explain why learning from massive, noisy datasets can be so successful, especially when the noisy dataset is used as a pre-training task: major patterns in data can be learned despite label noise long as there is some signal within the noise. Our theory could also be used to guide the curation of datasets as they are being collected. Not all labels need be clean, but enough labels in every class across the relevant feature space do need to be clean. Dpta-specific approaches may look for regions of feature space where labels tend to be noisy and focus more effort cleaning labels for those regions.
Conclusion In both the uniform and class- dependent label flip scenarios, classification is robust to label noise up to tipping point; and beyond that tipping point, classification fails catastrophically. These theoretical findings are helpful in designing evaluation approaches for label noise detection and mitigation. Considering that label noise mitigation strategies can require training 2 models (such as for CoTeaching) even 6 models (such as for CleanLab); we can see why empirical studies are computationally limited to investigating just a few variations on noise level and shape. We now know that levels of noise near where the tipping-point occurs will be most informative; that there is little reason to evaluate various levels of spread of class deuss-depnndett noise, and that incorporating feature-dependent noise is most informative for practical applications.
Classification accuracy is significantly lower at small levels of noise when the noise distribution depends features and is targeted at samples with the highest gap between the likelihood of the true label and the next-most-likely label. While various label noise mitigation strategies provide guarantees about conditions under which they work; see that the mitigation strategies on real data generally fail for similar scale and shape of label noise distributions. Realistically, we expect that label noise does depend on the features; and this paper demonstrates theoretically and empirically that the old assumption of label noise noise-being independent of features given the class leads to an overly optimistic expectation of classifier robustness in the face of label noise. While it is challenging to model reature-dependent label noise; it is clearly necessary as we see significantly lower classification accuracy when label noise is feature-dependent.
Acknowledgments and Disclosure of Funding
Research presented in this paper was supported by the Laboratory Directed Research and Development program Los Alamos National Laboratory under project number 20210043DR.
References
[1] Gilles Blanchard and Clayton Scott. Decontamination of Mutually Contaminated Models. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, volume 33, Reykjavik, Iceland, 2014.
[2] Pengfei Chen, Ben Ben Liao, Guangyong Chen, and Shengyu Zhang. Understanding and utilizing deep neural networks trained with noisy labels. In International Conference on Machine Learning, pages 1062-1070, PMLR, 2019.
[3] Aritra Ghosh, Himanshu Kumar, and PS Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
10

---

[4] Jacob Goldberger and Ehud Ben-Reuven. Training deep tion layer. In International Conference on Learning Representations (ICLR), 2017.
using noise adapta-
[5] 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 Neural Information Processing Systems, 2018.
[6] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[7] Bai Jiang, Tung-yu Wu, Charles Zheng, and Wing H Wong. Learning summary statistic for approximate bayesian computation via deep neural network. Statistica Sinica, pages 1595-1618, 2017.
[8] Heinrich Jiang and Ofir Nachum. Identifying and correcting label bias in machine learning. In International Conference on Artificial Intelligence and Statistics, pages 702-712. PMLR, 2020.
[9] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[10] Yuncheng Li, Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from noisy labels with distillation. In IEEE International Conference on Computer Vision, 2017.
[11] Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(3):447-40 2015.
[12] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances Neural Information Processing Systems, 26, 2013.
[13] Curtis Northcutt, Lu Jiang, and Isaac Chuang. Confident learning: Estimating uncertainty in dataset labels. Journal of Artificial Intelligence Research, 70:1373-141,, 2021.
[14] Diane Oyen, Michal Kucer, and Brendt Wohlberg. VisHash: Visual similarity preserving image hashing for diagram retrieval. In Applications of Machine Learning. International Society for Optics and Photonics, 2021.
[15] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: loss correction approach. In IEEE Conference on Computer Vision and Pattern Recognition, 2017.
[16] Scott Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neural networks on noisy labels with bootstrapping. In Workshops of International Conference Learning Representations (ICLR), 2015.
[17] David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning is robust to massive label noise. arXiv preprint 1rXiv:1705.1061 2017.
[18] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211-255 2015.
[19) Clayton Scott. A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In International Conference on Artificial Intelligence and Statistics, volume 38, 2015.
[20] Clayton Scott, Gilles Blanchard, and Gregory Handy. Classification with asymmetric label noise: Consistency and maximal denoising. In Conference on Learning Theory, pages 489-511, 2013.
[21] Yanyao Shen and Sujay Sanghavi. Learning with bad training data via iterative trimmed loss minimization. In International Conference on Machine Learning, volume 97, 2019.
11

---

[22] Sainbayar Sukhbaatar, Joan Bruna, Manohar Paluri, Lubomir Bourdev, and Rob Fergus. Training convolutional networks with noisy labels. In Workshops of International Conference Learning Representations (ICI.R), 2015.
[23] Sunil Thulasidasan, Gopinath Chennupati, Jeff A Bilmes, Tanmoy Bhattacharya, and Sarah Michalak. On mixup training: Improved calibration and predictive uncertainty for deep neural networks. In Advances in Neural Information Processing Systems, pages 13888- 18888-1389,, 2019.
[24] Nidhi Vyas, Shreyas Saxena, and Thomas Voice. Learning soft labels via meta learning. arXiv preprint arXiv:2009.09996 2020.
[25] Yisen Wang, Xingjun Ma, Zaiyi Chen, Yuan Luo, Jinfeng Yi, and James Bailey, Symmetric cross entropy for robust learning with noisy labels. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 322-330, 2019.
[26] Yilun Xu, Peng Cao, Yuqing Kong, and Yizhou Wang. LDMI: A novel information-theoretic loss function for training deep nets robust to label noise. Advances in Neural Information Processing Systems, 32, 2019.
[27] Christoph Zauner, Martin Steinebach, and Eckehard Hermann. Rihamark: perceptual image hash benchmarking. In Media Watermarking, Security, and Forensics III, volume 7880, pages 343 357. SPIE, 2011.
[28] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. International Conference on Learning Representations, 2018.
12


Reviews:
[{"review_id": "jDVe5tcxfa", "reviewer": "Reviewer_xHwG", "summary": "The authors analyze the problem of the robustness of the machine learning classifiers to the label noise under different noise types: 1) uniform (independent of features and classes), 2) class-dependent, and 3) feature-dependent. In their analysis, the authors focus on analyzing the \"typing point\" - the noise ratio value below which classifiers suffer a significant reduction in predictive performance. The authors show that typing point can be much lower when noise is feature dependent than in two other cases, suggesting that one needs to be careful when assuming that the noise is independent of features. The theoretical results are later confirmed by empirical evaluation on both synthetic and real datasets with introduced noise. ", "questions": "I don't have questions right now.", "limitations": "Since this isn't a methodology paper, there are not many limitations to discuss. Also, there are no potential negative social impacts of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Although this isn't a methodology paper, and while the main claim is not surprising, the paper helps to understand and provide a sound analysis of the problem. This is the type of paper that is interesting to read as opposed to many papers that demonstrate yet another epsilon improvement in an experimental evaluation.\n- The theoretical results are confirmed by empirical experiments, on different datasets and with different types of introduced noise.\n- The experiment with methods for learning with noise labels is a nice addition.\n\nWeaknesses:\n- Most of the presented results come from previous works.\n- The main conclusions are not surprising and, as the authors acknowledge, observed in previous empirical studies.\n\nNITs:\n- In eq 14. I think double equal signs are not needed.\n- In line 180, P Y|X are missing brackets.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P9ZNzPPmIy", "reviewer": "Reviewer_7YEL", "summary": "This manuscript studies the robustness of instance-dependent label noise. The authors provide a theoretical framework that generalizes beyond a typical assumption that label noise is independent of the features by modeling label noise as a distribution over feature space. They also show that the shape of noise distribution has a strong impact on classification performance if the noise is concentrated in feature space. \n ", "questions": "In Lemma 3.2, what is the definition of a Bayes optimal classifier, or what is the property of a Bayes optimal classifier? Please formulate it since it is important to understand the following Eq.(6).\n\nCorollary 3.2.1 \"The minimum noisy accuracy of $\\frac{1}{c}$ occurs at $\\epsilon=\\frac{c-1}{c}$\". This claim is not exactly correct since it misses the condition of uniform assumption. Besides, this claim does no significance since it is common sense that the training labels are useless if $\\epsilon=\\frac{c-1}{c}$.\n\nCorollary 3.3.1 \"Clean accuracy drops by half at $\\epsilon=\\frac{c-1}{c}$\". This claim is not exactly correct. what is the meaning of \"Clean accuracy drops by half\", is $\\epsilon<\\frac{c-1}{c}$, and the clean accuracy does not drop by half?\n\nIn Fig.3(a), why the greater the $\\epsilon$ (noise rate) the better the noisy accuracy? \n\nEq.(8) is problematic. Since $\\sum_{i\\neq k}|t_{ki}|^0=s$ and  $\\sum_{i\\neq k}t_{ki}=1$, $\\sum_{i=1}^{k} \\eta_{ki} \\neq 1$ if $s\\geq 2$.\n\nFrom the process of generating feature-dependent noise (line186-188), it seems a class-dependent label noise rather than feature-dependent noise.\n", "limitations": "Please see the comment above.", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The theories (Lemma3.2 and Lemma3.5) presented in this paper simply derived the results from [2] under both uniform label noise and class-dependent label noise, while theoretical analysis on instance-dependent label noise is not provided, the novelty is limited.\n\nThis paper focus on the instance-dependent label noise studied, but two-thirds of the paragraph are describing instance-independent label noise.\n\n[2] Understanding and Utilizing Deep Neural Networks Trained with Noisy Labels.\n\n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "FbeZRHtyhY", "reviewer": "Reviewer_sFMH", "summary": "The paper suggest difference of generalization ability of Machine Learning considering the scale and shape of the noise distribution. Theoretically and empirically, Machine learning is known to be robust to uniform label noise. However, no study has been researched for the case of class-dependent or instance-dependent label noise setting, and this paper supports theoretical background for those cases. The paper also shows the degradation of noisy label managing algorithms after tipping point empirically, supporting the theoretical result they show.", "questions": "1) How did you generate featrure-dependent label noise for CIFAR10 and CIFAR100 for experiments?\n2) What will happen if two or more types of noisy label generation algorithm are simultaneously applied? e.g. a noisy labeled dataset with symmetric noise 20% and asymmetric noise 20%.\n3) Not to face sudden model performance degradation, is it the only way to get dataset clean enough (not having noisy label as many as the tipping point)?\n", "limitations": "The authors have not addressed ther limitations. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "<<Strengths>>\n- Originality : The paper theoretically proves the robustness and fragility of ML under trained with noisy labeled dataset setting with different noisy label condition. It is quite interesting. Not only showing the robustness of uniform label noise, the paper also shows the weakness of class- and instance- dependent label noise, which is novel.\n\n- Quality  : The submission is technically sound and the claims are well supported both by theoretical analysis and the expermental results.\n\n- Clarity : Sentences are easy to read. Mathematical expressions are understandable. Well organized.\n\n- Significance : The results are important suggesting two points.\n1) The existence of tipping point \n2) The model performance degrades suddenly after the tipping point, not gradually.\n\n======================================================================================================\n\n<<Weaknesses>>\n- Quality :  Maybe want to see more experimental results?(e.g. Clothing 1M, a well-known benchmark real dataset for noisy label problem, would it also have tipping point?)\n\n- Clarity : (typo) Py|x for section 4.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8jzn7S5KtWS", "reviewer": "Reviewer_sTc1", "summary": "This paper studies how different forms of label noise affect the performance of ML classifiers. It is argued that the most benign form of label noise is uniform noise independent of features and labels, and the most harmful is feature dependent label noise. For feature independent label noise, classifiers retain good accuracy until some level of noise, after which there is a sharp drop-off. On the other hand, for feature dependent label noise, what matters is whether the flips occur close to or far away fromt he decision boundary. This is illustrated through theory and experiments. ", "questions": "I have asked a few questions in the strengths and weaknesses section, as well as the limitations section. \n\nThe \\eta_{ki} values in eq. 8 do not seem to add up to 1? Could you please clarify. \n\nI like the paper and would be happy to increase my score from 6 to 7 if the response is strong. \n", "limitations": "I feel that this paper does not address the 'so-what' question: how do I use this theory in a practical setting where I don't know the extent of label noise, or the type of label noise? I encourage the authors to think and elaborate on this. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "For the theory, the authors study how the Bayes optimal classifiers with and without label noise compare for simple label flipping attacks. While studying the Bayes optimal classifiers is quite limiting, it is nonetheless a useful starting point that seems to not have been considered before in the literature. The theory is simple, but leads to the following insights:\n- Feature-independent label flipping is benign until a large value of epsilon, after which there is a sudden drop in performance. In particular, for class-dependent label flipping, the point of drop in performance depends on the 'spread' of the flip (the support size of the flip targets).\n- Feature dependent label flipping can hurt even at a small value of epsilon, especially if the flipped labels are closed to the optimal decision boundary. On the other hand, flips away from the decision boundary have a smaller effect. \n\nDespite the simplicity of the theoretical analysis, it matches very well with synthetic experiments. \n\nThe results on CIFAR-10 and CIFAR-100 (Tables 2 and 3) seemed more of a mixed bag. Shouldn't the drop in performance from class noise to feature noise be more based on the theory? Why is this not the case? \n\nThe paper was easy to read and follow, although I felt that the authors could have been more transparent about the limited scope of the theoretical study (only Bayes optimal classifiers). \n\nOverall, I found the paper informative, but lacking in a final punchline message. The existing findings are concrete and well-supported, but not too surprising (at least to me): I would have expected that feature based label noise is a more powerful attack than class based or uniform noise. The work makes no methodological contribution, which for me slightly increases the bar of acceptance. (Perhaps this research could help engineers seeking annotations to take appropriate steps if label noise seems higher than a threshold? Not sure.)", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept