Class2Simi: A New Perspective on Learning with Label Noise
Authors: Songhua Wu
Xiaobo Xia
Tongliang Liu
Bo Han
Mingming Gong
Nannan Wang
Haifeng Liu
Gang Niu
Venue:  (2021)

Abstract: Label noise is ubiquitous in the era of big data. Deep learning algorithms can easily fit the noise and thus cannot generalize well without properly modeling the noise. In this paper, we propose a new perspective on dealing with  label noise called ``\textit{Class2Simi}''. Specifically, we transform the training examples with noisy class labels into pairs of examples with noisy similarity labels, and propose a deep learning framework to learn robust classifiers with the noisy similarity labels. Note that a class label shows the class that an instance belongs to; while a similarity label indicates whether or not two instances belong to the same class. It is worthwhile to perform the transformation: We prove that the noise rate for the noisy similarity labels is lower than that of the noisy class labels, because similarity labels themselves are robust to noise. For example, given two instances, even if both of their class labels are incorrect, their similarity label could be correct. Due to the lower noise rate, Class2Simi achieves remarkably better classification accuracy than its baselines that directly deals with the noisy class labels.

Under review as a conference paper at ICLR 2021
CLASS2SIMI: A NEW PERSPECTIVE ON LEARNING WITH LABEL NOISE
Anonymous authors Paper under double-blind review
ABSTRACT
Label noise is ubiquitous in the era of big data. Deep learning algorithms can easily fit the noise and thus cannot generalize well without properly modeling the noise. In this paper, we propose new perspective on dealing with label noise called "Class2Simi". Specifically, we transform the training examples with noisy class labels into pairs of examples with noisy similarity labels, and propose a deep learning framework to learn robust classifiers with the noisy similarity labels. Note that class label shows the class that instance belongs to; while similarity label indicates whether or not two instances belong to the same class. It is worthwhile to perform the transformation: We prove that the noise rate for the noisy similarity labels is lower than that of the noisy class labels, because similarity labels themselves are robust to noise. For example, given two instances, even if both of their class labels are incorrect, their similarity label could be correct. Due to the lower noise rate, Class2Simi achieves remarkably better classification accuracy than its baselines that directly deals with the noisy class labels.
INTRODUCTION
It is expensive to label large-scale data accurately. Therefore, cheap datasets with label noise are ubiquitous in the era of big data. However, label noise will degenerate the performance of trained deep models, because deep networks will easily overfit label noise (Zhang et al., 2017: Zhong et al., 2019: Li al., 2019; Yi & Wu, 2019; Zhang et al., 2019; 2018; Xia al., 2019; 2020).
In this paper, we propose a new perspective on handling label noise called "Class2Simi", i.c., transforming training examples with noisy class labels into pairs of examples with noisy similarity labels. A class label shows the class that an instance belongs to, while similarity label indicates whether or not two instances belong to the same class. This transformation is motivated by the observation that the noise rate becomes lower, e.g., even if two instances have incorrect class labels, their similarity label could be correct. In the label-noise learning community, lower noise rate usually results in higher classification performance (Han et al., 2018b; Patrini et al., 2017).
Specifically, we illustrate the transformation and the robustness of similarity labels in Figure 1. Assume we have eight noisy examples {x11 B1),... (æs, f8)} } as shown in the upper part of the middle column. Their labels are of four classes, i.e., 21, 3, 3.4. The labels marked in red are incorrect labels. We transform the 8 examples into 8 x 8 example-pate shown in the bottom part of the middle column, where the similarity label 1 means the two instances have the same class label and 0 means the two instances have different class labels. We present the latent clean class labels and similarity labels in the left column. In the middle column, we can see that although the instances x2 and x, both have incorrect class labels, the similarity label of the example- Sammple-pair& (I2, z4) is correct. Similarity labels are robust because they further consider the information on the pairwise relationship. We prove that the noise rate in the noisy similarity labels is lower than that of the noisy class labels. For example, if we assume that the noisy class labels in Figure are generated according to the latent clean labels and the transition matrix shown in the upper part of the right column (the ij entry of the matrix denotes the probability that the clean class label i flips into the noisy class label j), the noise rate for the noisy class labels is 0.5 while the rate for the corresponding noisy similarity labels is 0.25. Note that the noise rate is the ratio of the number of incorrect labels to the number of total examples, which can be calculated from the noise transition matrix combined with the proportion of each class, i.e., 1/6 3/4 + 1/2 1/4 0.25.
with noisy similarity labels as

---

Under review as a conference paper at ICLR 2021
X:
X1
Xa
X6
X5
Kn.
35
X:
X1
Xx
Xx
Xa
Xn
Xy
Xn
y:
y:
Examples with clean class Inbels
Examples with noisy class labels
X2
X2
X3
X4
X5
2
2
3
3
2
2
3
3
0.5
X1
1
L
0
0
0
0
0
X1
0
0
0
0
0.5
0.5
X2
1
0
0
0
A2
2
0
Class noise transition matrix
2
0
0
X5
0
2
0
0
X4
0
0
X9
0
0
A5
0
0
X
0
0
X
1/2
1/2
Example pairs clean similarity labels
Example pairs with noisy similarity labels
Similarity noise transition matrix
Figure 1: Illustration of the transformation from class labels to similarity labels. Note that stands for the noisy class label and y for the latent clean class label. The labels marked in red are incorrect labels. If we assume the class label noise is generated according to the noise transition matrix presented in the upper part of the right column, it can be calculated that the noise rate for the noisy class labels is 0.5 while the rate for the noisy similarity labels is 0.25. Note that the noise transition matrix for similarity labels can calculated by exploiting the class noise transition matrix in Theorem 1.
It is obvious that Class2Simi suffers information loss because we can not recover the class labels from similarity labels. However, since the similarity labels are more robust noise than the class labels, the advantage of the reduction of noise rate overweighs the disadvantage of the loss of information. Intuitively, in the learning process, it the signal in the information that enhances the performance of the model, while the noise in the information is harmful to the model. Through Class2Simi, although the total amount of information reduced, the signal noise ratio increased, and so would be the total amount of signals. Thus, can benefit from the transformation and achieve better performances. Theorem and the experimental results will verify the effectiveness this transformation.
remains unsolved how to learn robust classifier from the data with transformed noisy similarity labels. To solve this problem, first estimate the similarity noise transition matrix, 2 matrix whose entries denote the flip rates of similarity labels. Note that the transition matrix bridges the noisy similarity posterior and the clean similarity posterior. The noisy similarity posterior can be learned from the data with noisy similarity labels. Then, given the similarity noise transition matrix, we can infer the clean similarity posterior from the noisy similarity posterior. Since the clean similarity posterior is approximated by the inner product of the clean class posterior (Hsu et al., 2019), the clean class posterior (and thus the robust classifier) can thereby be learned. We will empirically show that Class2Simi with the estimated similarity noise transition matrix will remarkably outperform the baselines even given with the ground- truth class noise transition matrix.
The contributions of this paper are summarized as follows:
We propose new perspective on learning with label noise, which transforms class labels into similarity labels. Such transformation reduces the noise level.
We provide a way to estimate the similarity noise transition matrix by theoretically establishing its relation to the class noise transition matrix. We show that even if the class noise transition matrix is inaccurately estimated, the induced similarity noise transition matrix still works well.
We design a deep learning method to learn robust classifiers from data with noisy similarity labels and theoretically analyze its generalization ability.
We empirically demonstrate that the proposed method remarkably surpasses the baselines on many datasets with both synthetic noise and real-world noise.
The rest of this paper is organized as follows. In Section 2, we formalize the noisy multi-class classi- fication problem, and Section 3, we propose the Class2Simi strategy and practical implementation. Experimental results discussed in Section 4. We conclude paper in Section 5.
2

---

Under review as a conference paper at ICLR 2021
2 PROBLEM SETUP AND RELATED WORK
Let (X E X'x [I,...,C} C} be the random variables for instances and clean labels, where X' represents the instance space and C' is the number of classes. However, in many real-world applications (Zhang et al.. 2017; Zhong et al., 2019; Li et al., 2019; Yi & Wu, 2019; Zhang et al., 2019; Tanno et al., 2019; Zhang et al., 2018), the clean labels cannot be observed. The observed labels are noisy. Let Y be the random variable for the noisy labels. What we have is sample {<11, ,..,..., (Fn } drawn from the noisy distribution Do of the random variables (X, Y). Our aim is to learn robust classifier that could assign clean labels to test data by exploiting the sample with noisy labels.
Existing methods for learning with noisy labels can be divided into two categories: algorithms that result in statistically inconsistent or consistent classifiers. Methods in the first category usually employ heuristics to reduce the side-effect of noisy labels, e.g., selecting reliable examples (Yu et al., 2019; Han et al., 201 8b; Malach & Shalev-Shwartz 2017), reweighting examples (Ren et al., 2018; Jiang al., 2018; Ma et al., 2018; Kremer al., 2018; Tanaka al., 2018; Reed et al., 2015), employing side information (Vahdat, 2017: Li et al., 2017: Berthon et al.. 2020), and adding regularization (Han et al., 2018a; Guo al., 2018; Veit al., 2017: Vahdat, 2017: Li et al., 2017). Those methods empirically work well in many settings. Methods in the second category aim to learn robust classifiers that could converge to the optimal ones defined by using clean data. They utilize the noise transition matrix, which denotes the probabilities that the clean labels flip into noisy labels, to build consistent algorithms (Goldberger & Ren-Reuven, 2017: Patrini et al., 2017; Thekumparampil et al., 2018; Yu et al., 2018; Liu & Guo, 2020; Zhang & Sabuncu, 2018; Kremer et al., 2018; Liu & Tao, 2016; Northcutt et al., 2017: Scott, 2015; Natarajan et al., 2013; Yao et al., 2020b). The idea is that given the noisy class posterior probability and the noise transition matrix, the clean class posterior probability can be inferred.
Note that the noisy class posterior and the noise transition matrix can be estimated by exploiting the noisy data, where the noise transition matrix additionally needs anchor points (Liu & Tao, 2016; Patrini et al., 2017). Some methods assume anchor points have already been given (Yu et al., 201 8). There are also methods showing how to identify anchor points from the noisy training data (Liu & Tao, 2016; Patrini al., 2017).
3 CLASS2SIMI MEETS NOISY SUPERVISION
In this section, we propose a new strategy for learning from noisy data. Our core idea is to transform class labels to similarity labels first, and then handle the noise manifested on similarity labels.
3.1 TRANSFORMATION ON LABELS AND THE TRANSITION MATRIX
As in Figure 1, combine every 2 instances in pairs, and if the two instances have the same class label, we assign this pair a similarity label 1, otherwise O. the class labels are corrupted, the generated similarity labels also contain noise. We denote the clean and noisy similarity labels of the example-pair (I;, ,,) by Hij and H., respectively.
The definition of the similarity noise transition matrix is similar to the class one, denoting the probabilities that clean similarity labels flip into noisy similarity labels, i.e., Ts.ma P(H.j niHF, m). The dimension of the similarity noise transition matrix is always 2 x 2. Since the similarity labels are generated from class labels, the similarity noise is also determined and, thus can be calculated, by the class noise transition matrix.
Theorem 1. Assume that the dataset is balanced (each class has the same amount of samples, and classes in total), and the noise is class-dependent. Given a class noise transition matrix To, such that To P(Y = = i). The elements of the corresponding similarity noise transition matrix T, can be calculated as
c--c- (E, Te,s) [co1
ΣS(E, Toiy) ||T.1
Ta,00
T..01
C- ||To||2
||Te|B30o
Te.10
T T
c
3

---

Under review as a conference paper at ICLR 2021
Input ssampies noiay simillriity lahels
Neural Network
Clean Clasatier
Pairwise enumeration layer
Bl
Rly
Softmax
(00) = POY
T(xa" ((X)) Sy
Cross-entrogy
((Y1)))))))))
T 18 Sy]
An overview of the proposed method. We add pairwise enumeration layer and similarity transition matrix to calculate and correct the predicted similarity posterior. By minimizing the proposed loss L.2s. a classifier f can be learned for assigning clean labels. The detailed structures of the Neural Network are provided in Section 4. Note that for the noisy similarity labels, some of them are correct and some are not. The similarity label for dogs is correct and the similarity label for cats incorrect. In practice, the input data is original class-labeled data, and the transformation is conducted during the training procedure rather than before training.
Figure 2:
detailed proof is provided in Appendix A.
Remark 1. Theorem can easily extend to the setting where the dataset is unbalanced in classes by multiplying each To.aj by a coefficient n4. n, is the number of examples from the i-th class.
Note that the similarity labels are only dependent on class labels. If the class noise is class-dependent, the similarity noise is also "class-dependent" (class means similar and dissimilar). Under class- dependent label noise, binary classification is learnable as long as Too + Ti1 1 (Menon et al., 2015), where T' is the corresponding binary transition matrix; a multi-class classification is learnable if the corresponding transition matrix T. is invertible. For Class2Simi, in the most general sense, i... Te is invertible, Te,u0 + T2,11 > holds. Namely, the learnability of the pointwise classification implies the learnability of the reduced pairwise classification. However, the latter cannot imply the former. A proof and a counterexample are provided in Appendix
Theorem 2.
Assume that the dataset is balanced (each class has the same amount of samples), and the noise is plass-dependers When the number of classes 2 8', the noise rate for the noisy similarity labels is lower than that of the noisy class labels.
A detailed proof is provided in Appendix B.
When dealing with label noise, a low noise rate has many benefits. The most important one is that the noise-robust algorithms will consistently achieve higher performance when the noise rate is lower (Bao et al., 2018 8; Han et al., 2018b; Xia et al., 2019; Patrini et al., 2017). Another benefit is that, when the noise rate is low, the complex instance-dependent label noise can be well approximated by class dlas-deepnndent label noise (Cheng et al., 2020), which is easier to handle. After the Class2Simi transformation, the number of dissimilar pairs (c 1) times as much as that of similar pairs. Meanwhile, compared with the original noise rate of class labels, the noise rate of similar pairs (the ratio of the number of mislabeled similar pairs to the number of total real similar pairs) is higher and the noise rate of dissimilar pairs is lower, while the overall noise rate of pairwise examples is lower, which partially reflects that the impact of the label noise is less bad. Moreover, the flip from dissimilar to similar should be more adversarial and thus more important. In practice, it is common that one class has more than one clusters, while it is rare that two or more classes are in the same cluster. If there is flip from similar to dissimilar and based on it we split (latent) cluster into two (latent) clusters, we still have a high chance to label these two clusters correctly later. If there is a flip from dissimilar to similar and based on it we join two clusters belonging two classes into single cluster, we nearly have zero chance to label this cluster correctly later. As a consequence, the flip from dissimilar to similar is more adversarial, and thus more important. To sum up. considering the reduction of the overall noise rate is meaningful.
3.2 LEARNING WITH NOISY SIMILARITY LABELS
In order to learn a multi-class classifier from similarity labeled data, we should establish relation- ships between class posterior probability and similarity posterior probability. Here we employ the relationship established in (Hsu et al., 2019), which is derived from a likelihood model. As in Figure
In multi-class classification problems, the number of classes is usually bigger than 8, e.g., MNIST (LeCun, 1998), CIFAR-1O, and CIFAR-J00 (Krizhevsky al., 2009).
4

---

Under review as a conference paper at ICLR 2021
700
Sy 1000 (()) 930
5U 100' ((5) 00634
sep
100
0.00
055
666
(a) Similar example
(b) Dissimilar example
Figure 3: Examples of predicted noisy similarity. Assume class number is 10; f(X;) and f(X;) are categorical distribution of X; and X, respectively, which are shown above in the form of area charts. Sig is the predicted similarity posterior between two instances, calculated by the inner product between two categorical distributions.
2, they denote the predicted clean similarity posterior by the inner product between two categorical distributions: Š.j = f (X;) f (X2). Intuitively, f(X) outputs the predicted categorical distribution of input data and f(X.) f(X,) can measure how similar the two distributions are. For clarity, we visualize the predicted similarity posterior in Figure 3. If X, and X, predicted belonging to the same class, i.e., argmaxmec' fm (X;) = argmaxnec' fn (x,)), the predicted similarity posterior should be relatively high (S.g = 0.30 in Figure 3(a)). By contrast, if X; and Xj are predicted belong- ing different classes, the predicted similarity posterior should be relatively low ($;z = 0. 0.0654 in Figure 3(b)). Note that the noisy similarity posterior distribution P(H, [X, X,) and clean similarity posterior distribution P(Hij)Xo X;, Xj) satisfy
P( X, X,) = P(H:j
T X,,
Therefore, we can infer noisy similarity posterior Si from clean similarity posterior S.y with the similarity noise transition matrix. To measure the error between the predicted noisy similarity posterior Sy and noisy similarity label Hay. we employ binary cross-entropy loss function (Shannon, 1948). The final optimization function is
Le2s (1 (Hyy Sig)
Σ Hig log Siz + (1 Hig) log(1 $.y)
The pipeline of the proposed Class2Simi is summarized in Figure 2. The softmax function outputs an estimation for the clean class posterior, i.c., f(X) = P(Y) where P(Y|X) denotes the estimated class posterior. Then a pairwise enumeration layer (Hsu et al., 2018) is added to calculate the predicted clean similarity posterior Š., of every two instances. According to Equation 1, by mee-mulipplyin the transpose of the noise similarity transition matrix,
obtain the predicted noisy similarity posterior Š.y. Therefore, by minimizing Le2s, we can learn classifier for predicting noisy similarity labels. Meanwhile, before the transition matrix layer, the pairwise enumeration layer will output a prediction for the clean similarity posterior, which guides f(X) to predict clean class labels.
3.3 IMPLEMENTATION
The proposed algorithm is summarized in Algorithm 1. Since learning only from similarity labels will lose the mapping between the output nodes and the semantic classes, we load the model trained on the data with noisy class labels to learn the class information in Stage 2. It is worthwhile to mention that Class2Simi increases the computation cost slightly. Note that the transformation of labels is during the training phase rather than before training. Specifically as in Figure 2, first, batch n examples, and generate their corresponding n² similarity labels. Since n is the batch size, it is usually small. In addition, we only save the labels, not example-pairs, such that it introduces
read
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Class2Simi
Input: training data with noisy class labels; validation data with noisy class labels.
Stage 1: Learn T.
Learn (-X) (X) by training data with noisy class labels, and save the model for Stage 2:
2: Estimate T, following the optimization method in (Patrini al., 2017);
3: Transform T. to T..
Stage 2: Learn the classifier f(X) P(Y|X)
4: Load the model saved in Stage 1, and train the whole pipeline showed in Figure 2.
Output: classifier f.
negligible memory overhead. Then the neural network outputs the class posterior probabilities of single examples in the batch of data. After that pairwise enumeration layer calculates the inner products between every two instances, outputting n² predicted similarity posterior probabilities. Then the similarity transition matrix corrects the n² predicted similarity posterior probabilities. Finally, the loss is accumulated by n² items. Namely, Class2Simi only does the additional computation on generating similarity labels and calculating the inner products between every two instances in the pairwise enumeration layer, which is time-efficient.
3.4 GENERALIZATION ERROR
We formulate the above problem in the traditional risk minimization framework (Mohri et al., 2018).
The expected and empirical risks of employing estimator f can be defined as
R(J) = E(x,,X, P.,, (,,,,,,,,,)))),,,LL((((((((,1),, Hsy),,
(3)
and
ΣΣ (FXX)) - = TI ==1
(4)
where n is training sample size of the noisy data. Assume that the neural network has layers with parameter matrices W1, Wa. and the activation functions 01, .... Jd-1 are Lipschitz continuous, +
(W)) E R the standard form of the neural network. H = (e h4 Then the output of the softmax
satisfying (0) O. We denote by H
function is defined as f((X) exp (lx Σÿ exp (X)),)), i I,...,C.. C. We can obtain the following generalization error bound as follow.
Theorem 3. Assume the parameter matrices WI...., Wa have Frobenius norm most Mı..... Má. and the activation functions are I-Lipschitz, positive-homogenenn as the ReLU). Assume the transition matrix is given, and the instances X are upper bounded by B, iee, || S B for all X, and the loss function & is upper bounded by M Then, for any ó >> 0, with probability least 8,
and applied element wise (such
R(A- (n) < (Ta.11 - -T,,0 (2O0))20C(/222l 1)11 M,
log 1/6 2n
M
(5)
T
Notation and detailed proof are provided in Appendix C.
Theorem implies that the training error small and the training sample size is large, the expected risk R( of the representations for noisy similarity posterior will be small. If the transition matrix well estimated, the clean similarity posterior as well as the classifier for the clean class will also have a small risk according to Equation| and the Class2Simi relations. This theoretically justifies why the proposed method works well. In the experiment section, will show that the transition matrices well estimated and that the proposed method significantly outperforms the baselines.
In Class2Simi, multi-class classification is reduced pairwise binary classification. For pairwise examples, if a surrogate loss is waassifcation-calirattee minimizing leads to minimizing the zero- one loss the pointwise random variables in the limit case. Otherwise, cannot guarantee the
The assumption holds because deep neural networks will always regulate the objective to be finite value and thus the corresponding loss functions are of finite values.

---

Under review as a conference paper at ICLR 2021
Table 1: Means and Standard Deviations of Classification Accuracy over 5 trials on image datasets.
MNIST Sym-Noise
0.1
0.2
0.3
0.4
0.5
Co-teaching
98.40:1:.07
98.22:10.10
97.56.10.04
97.30-1:.115
0..5
APL
98.77:10.07
98.62:1.112
98.55:0.111
98.40=20.12
98.05=00.29
S2E
98.13:10.57
98.18:10221
97.7110.118
97.41=0.17
96.63:10.29
Forward
98.64.10.18
98.33310.23
98.20.10.11
97.99-1.200
97.35-10.46
Forward & Class2Simi
98.84-10.09
98.74:10.17
9..56
98.44
98.25 0.26
Reweight
98.23++0.27
98.01+0.117
97.72+0.30
97.66+00.4
96.81 +0.81+0.70
Reweight & Class2Simi
98.51-10.13
98.07.10.29
98.0810.18
97.82.10.29
97.11
Revision
98.59::0.12
98.48=0..0
98.15+0.17
97.94=0.16
97.53=0031
Revision & Class2Simi
98.62++0.17
98.57+0024
98.19+0.21
97.99-+019
97.73+0.27
CIFARIO Sym-Noise
0.1
0.2
0.3
0.4
0.5
Co-teaching
85.16+0.225
83.59+-0.17
80.47+0.39
78.42+0.22
74.35+00.84
APL
83.81+0.45
02.2+0.56
80.49+0.82
77.80=1.62
73.25+2245
S2E
60.01+0.89
58.53:1 1.49
55.07:4..35
52.07=3.33
50.10=33.61
Forward
87.01+00.41
85.75+-0.37
83.72+0..3
81.28:+0.34
78.10+0.72
Forward & Class2Simi
87.84-00.12
86.62.10.20
84.8911.119
83,32.10.72
81.15
Reweight
86.80.10.36
85.08
83.03.10.63
80.35.10.41
76.61
Reweight & Class2Simi
87.2
8..4
83.18:10557
80.67:0062
77.66
Revision
87.09-00.36
85.68+0022
83.88+00.49
81,41+00.47
77.96+0.44
Revision & Class2Simi
+7.4
83.87+0.588
83,92+0.37
81.87=00.4
78.70
CIFARI00 Sym-Noise
0.1
0.2
0.3
0.4
0.5
Co-teaching
52.39910.47
0..83
46.31
42.05:10.80
35.21:11001
APL
37.70=1.722
33.35+2.07
28.8012.58
24.82:22.79
21.27
S2E
49.30:11.3
46.20:1.110
43.241:2.48
39.6311.86
34.98
Forward
52.6311..48
45.67
42.25.11.83
37.42-11.45
30.66.11.1
Forward & Class2Simi
55.56-10.55
52.85
49.44.10.00
45.52.10.52
39.86-10.38
Reweight
51.43++0.22
+7.03
42.62+0.66
36.02-+2.40
26.34-+0.96
Reweight& & Class2Simi
51.74
1..57
46.5413.20
43.65.1..14
34.01:13.49
Revision
51.48::0.22
47.11
42.75
36.08+22.22
26.32=t0.94
Revision & Class2Simi
53.30-+1.81
50.88
47.51+1.71
44.20-11.70
2..86
worst-case learnability of learning pointwise labels from pairwise examples, but it cannot imply the average-case non-learnability either. Theoretically, Bao et al. (2020) proved that when the pairwise labels are all correct, for the special case = 2, a good model for predicting similar/dissimilat pairs must also be a good model for predicting the original classes, under mild assumptions. In practice, seems fine use multi-class margin loss (i.e., one-vs-rest loss) and the pairwise comparison loss (i.c., one-vs-one loss) proved to be non-calibrated, but they are still the main multi-class losses in Mohri et al. (2018); Shalev-Shware & Ben-David (2014).
caassificationccalirattee losses. According to Tewari & Bartlett (2007), the
EXPERIMENTS
Datasets. We employ three widely used image datasets, i.e., MNIST (LeCun, 1998). CIFAR- 10, and
CIFAR-100 (Krizhevsky al., 2009), text datuset News20, and one real-world noisy dataset Clothing IM (Xiao et al., 2015). MNIST has 28 x 28 grayscale images 10 classes including 60,000 training images and 10,000 test images. CIFAR-10 and CIFAR- 100 both have 32 32 x 3 color
7

---

Under review as a conference paper at ICLR 2021
images including 50,000 training images and 10,000 test images. CIFAR-10 has 10 classes while CIFAR-100 has 100 classes. News20 is a collection of approximately 20,000 newsgroup documents, partitioned nearly evenly across 20 different newsgroups. Ilothing has 1M images with noisy labels and additional 50k, 14k, 10k images with clean labels for training, validation and test, and we only use noisy training set in the training phase. Note that the similarity learning method of Class2Simi is based on Cluster because there is no class information. Intuitively, for noisy class, if most instances in it belong to another specific class, we can hardly identify it. For example, assume -ruut labels and n, instances with
that a class with noisy labels i contains n; instances with ground ttantd labels j. n is bigger than n,, the model will cluster class i into j. Unfortunately, in Clothing M, most instances with label '5' belong to class '3' actually. Therefore, we merge the two classes, and denote the fixed dataset by Clothing /M which contains 13 classes. For all the datasets, we leave out 10% of the training examples as a validation set, which is for model selection.
Noisy class labels generation. For the three clean datasets, we artificially corrupt the class labels of training and validation sets according to the class noise transition matrix. Specifically, for each instance with clean label i, we replace its label by j with a probability of Te,sj. In this paper, we consider both symmetric and asymmetric noise settings which are defined in Appendix D.
Baselines. As mentioned before, Class2Simi is a strategy rather than a specific algorithm. In this paper, we employ three T baade methods. i.c., Forward correction (Patrini et al., 2017). Reweight (Liu & Tao, 2016), and T-revision (Xia et al., 2019), which all utilize a class-dependent transition matrix to model the noise, to implement our approach show the effectiveness of Class2Simi. Besides, we externally conduct experiments on Co-teaching (Han et al., 2018b), which is a representative algorithm of selecting reliable examples for training; APL (Ma et al., 2020), which applies simple normalization on loss functions and makes them robust to noisy labels; S2E (Yao et al., 2020a), which properly controls the sample selection process so that deep networks can benefit from the memorization effect.
Network structure and Optimizer. For MNIST, we use LeNet (LeCun al., 1998). For CIFAR-1O. we use ResNet-32 with pre-activation (He et al., 201 For CIFAR-100 100, we use ResNet-56 with veeactivationn (He et al., 2016b). For News20, we use GloVe (Pennington et al., 2014) to obtain vector representations for text, and employ a 3-layer MLP with the Softsign active function. For Clothing/M' we use pre-trained ResNet-50 (He et al., 201 We use the same optimization method as Forward correction to learn the noise transition matrix Te. In Stage 2, we use the Adam optimizer with initial learning rate 0.001. On MNIST, the batch size is 128 and the learning rate decays every 20 epochs by a factor of 0.1 with 60 epochs in total. On CIFAR-JO. 10, the batch size is also 128 and the learning rate decays every 40 epochs by a factor of 0. with 120 epochs in total. On CIFAR- /00, the batch size is 1000 and the learning rate drops at epoch 80 and 160 by factor of 0.1 with 200 epochs in total. On News20, the batch size is 128 and the learning rate decays every 10 epochs by a factor of 0.1 with 30 epochs in total. On Clothing IMM, the batch size is 32 and the learning rate drops every 5 epochs by a factor of 0.1 with 10 epochs in total.
Results on noisy image datasets. The results in Table I and Figure 4 demonstrate that Class2Simi achieves distinguished classification accuracy and robust against the estimation errors on transition matrix.
From Table 1, overall, we can see that after the transformation, better performances are achieved due to lower noise rate and the similarity transition matrix being robust to noise. Specifically, On MNIST, as the noise rate increases from Sym-0.1 to Sym-O.5, Forward & Class2Simi maintains remarkable accuracy above 98.20% while the accuracy of Forward decreases steadily. On CIFARIO0, there are obvious decreases in the accuracy of all methods and our method achieves the best results across all noise rate, i.c., at Sym-0.5, Class2Simi gives accuracy uplifts of about 9.0% compared with those T based methods. Results under asymmetric noise are provided in Appendix E.3.
In Figure 4, we show that the similarity noise transition matrix is robust against estimation errors. To verify this, we add some random noise to the ground-truth T. through multiplying every element in class T. by a random variable aij. We control the noise rate on the T. by sampling on in different intervals, i.e., 0.1 noise means that oz is uniformly sampled from +[1.1, 1.2]. Then we normalize T. to make its row sums equal to 1. From Figure we can see that the accuracy of Forward drops dramatically with the increase of the noise on T. on three datasets. Meanwhile, there is only a slight fluctuation of Forward & Class2Simi on MNIST
8

---

Under review as a conference paper at ICLR 2021
Irwed
Freel
65
MOIST
CHARR0
CHEARNN
Figure 4: Means and Standard Deviations Classification Accuracy over 5 trials on MNIST, CIFARIO and CIFARIOO with perturbational ground-truth Te.
and CIFARIO. On CIFAR100, the accuracy of Forward & Class2Simi is affected by the noise on Te. but the decline is much lower than Forward. The reason is that Forward & Class2Simi needs to learn the class information from noisy data which is hard when the number of classes large.
Results noisy text dataset. Results in Table 2 show that the proposed strategy works well the text dataset under both symmetric and asymmetric noise settings.
Table 2: Classification Accuracy on News20.
News20
Sym-0.2
Sym-0.4
Asym-0.3
Forward
48.07-10.26
46.4910.54
47.30
F & C2S
48.52.10.47
47.04
4..70-0.45
Results on real-world noisy dataset. Re- sults in Table 3 show that the proposed strategy significantly improves the classi- fication accuracy of the T'based methods. T-based methods with Class2Simi also out- perform those classic methods.
Reweight
48.30:10.44
46.3410.31
47.25=0.91
Ri & C2s
48.55:10.46
47.71
48.43-10611
Revision
48.25:10.43
46.32.10.19
07.40.1..6
Rn C2S
48.63++0.48
47.84+-064
48.53 0.53
(CE uses class labels and the cross-entropy loss function.)
Ablation study. To investigate how the similarity loss function influences the clas- sification accuracy, we conduct experi- ments with the cross-entropy loss function and the similarity loss function respectively clean datasets over 3 trails where the Te is set to an identity matrix. All other settings are kept the same. As shown in Ta- ble 4, the similarity loss function does not improve the classification accuracy, which means the accuracy increase in our paper benefited from the lower noise rate and the more robust transition matrix.
Table 3: Classification Accuracy on Clothing IM*
CE
72.49
S2E
72.30
APL
58.93
Co-teaching
74.70
Forward
73.88
Forward & Class2Simi
75.41
Reweight
74.44
Reweight & Class2Simi
75.76
Revision
74.65
Revision & Class2Simi
75.79
Table 4: Classification Accuracy on clean datasets.
Dataset
MNIST
CIFARIO
CIFAR 100
News20
CE
99.19
89.09+0.119
56.12-+0.93
49.29+0.33
C2S
19.10+0.13
89.18 + 0.25
56.17+0.37
48.71+0.56
5 CONCLUSION
This paper proposes a new perspective on dealing with class label noise (called Class2Simi) by transforming the training sample with noisy class labels labels. We also propose deep learning framework to learn classifiers directly with the noisy similarity labels. The core idea is to transform class information into similarity information, which makes the noise rate lower. We also prove that not only the similarity labels but also the similarity noise transition matrix is robust to noise. Experiments are conducted on benchmark datasets, demonstrating the effectiveness of our method. In future work, investigating different types of noise for diverse real-life scenarios might prove important.
training sample with noisy similarity

---

Under review as a conference paper at ICLR 2021
REFERENCES
Han Bao, Gang Niu, and Masashi Sugiyama. Classification from pairwise similarity and unlabeled data. In ICML, pp. 461 461-470, 2018.
Han Bao, Takuya Shimada, Liyuan Xu, Issei Sato, and Masashi Sugiyama. Similarity- classifi-
cation: Connecting similarity learning to binary classification. arXiv preprint arXiv:2006.02200 2020.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482 2002.
Antonin Berthon, Bo Han, Gang Niu, Tongliang Liu, and Masashi Sugiyama. Confidence scores make instance-dependent label-noise learning possible. arXiv preprint vrXiv:2001.03772. 2020.
Pengfei Chen, Benben Liao, Guangyong Chen, and Shengyu Zhang. Understanding and utilizing deep neural networks trained with noisy labels. ICML, 2019.
Jiacheng Cheng, Tongliang Liu, Kotagiri Ramamohanarao, and Dacheng Tao. Learning with bounded instance-and and label-dependent label noise. In ICML, 2020.
Xavier Gastaldi. Shake-shake regularization. arXiv preprint arXiv: 1705.07705 2017.
Jacob Goldherger and Ehud Ben-Reuven. Training deep neural-networks using noise adaptation layer. In ICLR, 2017.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In COLT, 2018.
Sheng Guo, Weilin Huang, Haozhi Zhang, Chenfan Zhuang, Dengke Dong, Matthew R Scott, and Dinglong Huang. Curriculumnet: Weakly supervised learning from large-scale web images. In ECCV, pp. 135-150, 2018.
Bo Han, Jiangehao Yao, Gang Niu, Mingyuan Zhou, Ivor Tsang, Ya Zhang, and Masashi Sugiyama. Masking: A new perspective of noisy supervision. In NeurlPS, pp. 5836-5846, 2018a. 8a.
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 NeurlPS, 2018b.
Godfrey Harold Hardy, John Edensor Littlewood, George Pólya, György Pólya, DE Littlewood, et al. Inequalities. Cambridge university press, 1952.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In ECCV, pp. 630-645. Springer, 2016b.
Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira. Learning to cluster in order to transfer across domains and tasks. In ICLR, 2018. URL httpp:://///t settps:://peereevieee net www.://wwneetttueuee/ee forum? id=ByRMCqVT-
Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classification without multi-class labels. In ICLR, 2019.
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Fei-Fei. MentorNet: Learning data- driven curriculum for very deep neural networks corrupted labels. In ICML, pp. 2309-2318, 2018.
Jan Kremer. Fei Sha, and Christian Igel. Robust active label correction. In AISTATS, pp. 308-316. 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
10

---

Under review as a conference paper at ICLR 2021
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 36(11))2278-2324, 1998.
Michel Ledoux and Michel Talagrand. Probability Banach Spaces: isoperimetry and processes. Springer Science & Business Media, 2013.
Junnan Li, Yongkang Wong, Qi Zhao, and Mohan Kankanhalli. Learning to learn from noisy labeled data. In CVPR, pp. 5051-5059, 2019.
Yuncheng Li, Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from noisy labels with distillation. In ICCV, pp. 1918,1918, 2017.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions on pattern analysis and machine intelligence, 38(3)447-461, 2016.
Yang Liu and Hongyi Guo. Peer loss functions: rates, In ICML, 2020.
Learning from noisy labels without knowing noise
Xingjun Ma, Yisen Wang, Michael E Houle, Shuo Zhou, Sarah M Erfani, Shu-Tao Xia, Sudanthi Wijewickrema, and James Bailey. Dimensionallty-driven learning with noisy labels. In ICML, pp. 3361-3370, 2018
Xingjun Ma, Hanxun Huang, Yisen Wang. Simone Romano, Sarah Erfani, and James Bailey. Nor- malized loss functions for deep learning with noisy labels. In JCML, 2020.
Eran Malach and Shai Shalev-Shwartz. Decoupling" when to update" from" how to update". In NeurlPS, pp. 960-970, 2017.
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. Learning from corrupted binary labels via class-probability estimation. In ICML, pp. 125-134, 2015.
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2018.
Nagarajan Natarajan, Inderjit $ Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. In NeurIPS, pp. 1196-1204, 2013.
Curtis G Northeutt, Tailin Wu, and Isaac I. Chuang. Learning with confident examples: Rank pruning for robust classification with noisy labels. In UAI, 2017.
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu. Making deep neural networks robust to label noise: A loss correction approach. In CVPR, pp. 1944-1952, 2017.
Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In EMNLP, pp. 1532-1543, 2014.
Scott E Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neural networks on noisy labels with bootstrapping. In ICLR, 2015.
Mengye Ren, Wenyuan Zeng, Bin Yang. and Raquel Urtasun. Learning to reweight examples for robust deep learning. In ICML, pp. 4331-4340, 2018.
Clayton Scott. A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In AISTATS, pp. 838-846, 2015.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Claude Shannon. mathematical theory of communication. Bell system technical journal, 27(3): 379-423, 1948.
11

---

Under review as a conference paper at ICLR 2021
J Michael Steele. The Stuchy-Schward master class: an introduction to the art of mathematical inequalities. Cambridge University Press, 2004.
Yong Su and Bin Xiong. Methods and Techniques for Proving Inequalities: In Mathematical Olympiad and Competitions, volume 11. World Scientific Publishing Company, 2015.
Daiki Tanaka, Daiki Ikami, Toshihiko Yamasaki, and Kiyoharu Aizawa. Joint optimization framework for learning with noisy labels. In CVPR, pp. 5552-5560, 2018.
Ryutaro Tanno, Ardavan Saeedi, Swami Sankaranarayanan, Daniel C Alexander, and Nathan Silber- man. Learning from noisy labels by regularized estimation of annotator confusion. In CVPR, pp. 11236-11245, 2019.
Ambuj Tewari and Peter L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 100 2007.
Kiran K Thekumparampil, Ashish Khetan, Zinan Lin, and Sewoong Oh. Robustness of conditional gans to noisy labels. In NeurlPS, pp. 10271-10282 2018.
Arash Vahdat. Toward robustness against label noise in training deep discriminative neural networks. In NeurlPS, pp. 5596-5605, 2017.
Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, and Serge Belongie. Learning from noisy large-scale datasets with minimal supervision. In CVPR, pp. 839-847, 2017.
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 NeurlPS, pp. 6835-6846 2019.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang. Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Parts-dependent label noise: Towards instance-dependent label noise. In NeurlPS, 2020.
Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang. Learning from massive noisy labeled data for image classification. In CVPR, pp. 2691-2699, 2015.
Quanming Yao, Hansi Yang, Bo Han, Gang Niu, and J Kwok. Searching to exploit memorization effect in learning with noisy labels. In ICML, 2020a.
Yu Yao, Tongliang Liu, Bo Han, Mingming Gong, Jiankang Deng, Gang Niu, and Masashi Sugiyama. Dual t: Reducing estimation error for transition matrix in label-noise learning. In NeurIPS, 2020b.
Kun Yi and Jianxin Wu. Probabilistic end-to-end noise correction for learning with noisy labels. In CVPR, pp. 7017-7025, 2019.
Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor W Tsang, and Masashi Sugiyama. How does disagreement benefit co-teaching? In ICML, 2019,
Xiyu Yu, Tongliang Liu, Mingming Gong, and Dacheng Tao. Learning with biased complementary labels. In ECCV, pp. 68-83, 2018
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
Jing Zhang, Tong Zhang, Yuchao Dai, Mehrtash Harandi, and Richard Hartley Deep unsupervised saliency detection: A multiple noisy labeling perspective. In CVPR, pp. 9029-90323 2018.
Weihe Zhang, Yali Wang, and Yu Qiao. Metacleaner: Learning to hallucinate clean representations for nobse-labeled visual recognition. In CVPR, pp. 7373-7382, 2019.
Zhilu Zhang and Mert Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In NeurlPS, pp. 8778-8788. 2018
Jia- Xing Zhong, Nannan Li, Weijie Kong, Shan Liu, Thomas H Li, and Ge Li. Graph convolutional label noise cleaner: Train a plug-and plug-and-ples and-play action classifier for anomaly detection. In CVPR, pp. 1237-1246, 2019.
12

---

Under review as a conference paper at ICLR 2021
APPENDICES
A PROOF OF THEOREM
Theorem 1. Assume that the dataset is balanced (each class has the same amount of samples, and classes in total), and the noise is class-dependent. Given a class noise transition matrix To such that Te.15 P(Y j|Y Y i). The elements of the corresponding similarity noise transition matrix
can be calculated as
²² (E
Tews)
TTll
E,(, Tett) )2 1TTell
T2,00
Ta.01
c² cc
α² -
|Te Piro
|Tel
T2.10
T..11
Proof. Assume each class has n samples. PPTexTTerr. represents the number of sample-pair generated by (Y = = = i) and (Y = j ='). For the first element T,,00. n²² Eipe ToisTery is the number of sample-pairs with clean similarity labels H = 0, while n² Eiji jæj Te,sTe, is the number of example-pairs with clean similarity labels S and noisy similarity labels H O. Thus the ratio of these two terms is exact the Ts,00 = P(H = 0 H 0). The remaining three elements can be represented in the same way. The primal representations are follows,
Tx,00 Eipy sty TosTTery
Ts,01 Eiprs=y TeNTToy
Eiey TegsTep's'
Ener TeisTaR3
Eisl TodsTes Tess
TA,11 Eisi Teks ToNy
T T0
Eisy To,sfee9
Eier To.1I
Further, note that
EestTerr = TaisTeis = = Teni) Σ Tej.s') =c
iddd
3
TeisTooRs = Σ
TeisTeps
- Teis)) >
Tois') = (c - 1)c,
141
3'
Σ
Tej TeisTer Tepp
= ||Tol
(=/
TeiyTe Tep *Æ'
Σ
Tax)) ||To|
Substituting above four equations the primal representations, we have the Theorem proved. L
B PROOF OF THEOREM
Theorem 2. Assume that the dataset is balanced (each class has the same amount of samples), and the noise is class-depens class-dependent. When the number of classes e 2 8, the noise rate for the noisy similarity labels is lower than that of the noisy class labels.
Proof. Assume each class has samples. As state in the proof of Theorem 1, the num- ber of example-pairs with clean similarity labels = 0 and noisy similarity labels = 0 is n² Eipesty T. We denote it by Noo- Similarly, we have,
Noo = =
Σ
TaisTerr
No1 n²²
Σ
ToisTeR3
(#' J43
$4'
N10 = n²
Σ
ToiTToR'
Nu= = n
Σ
ToiSToN3
i=
13

---

Under review as a conference paper at ICLR 2021
The noise rate is the ratio of the number of noisy examples to the number of total examples. Assume that the number of classes is c. We have
No1 Ni0
No1 + N10
Smoise
Noo + No1 + N10 + N11
e2n²
ni n ig Te,
Cnoise
Let Snoise minus Cnoise, we have
2 Eijt.je TeiiTery + Disi Teay
EEizj Tei
Snoise
Cnoise
en?
en
Enprosy TeisTery + Ei Teis - c Eitg Tais
Let A Eifr TaisTary + Eisn TesTTary Eitj
Togjy we have
A =
Σ TaNTeNy + Σ
ToifTeNy - i=ljjij'
Σ
Toii
$73
TeayTesy sprg=
Σ
TesyTery c( imiitt
Σ
E Teiis
Te,ss)
Σ
TaxyTe
Σ
Teay
Tany 2 + Σ
Te,i
im i$j"
i=j
The second equation holds because the row sum of T is 1.
For the first term Σif Te,iyTa je notice that:
Σ
Toi = Σ> E Te Σ
Tows)
3
Σ ETa
Tegig
Tejyi + +Tesi -Tess)
Σ CETose
Σ
TTOys -Tais)
Σ E Te,s - Tois)
(S₂ is the column sum of the j - column)
Σ Σ So - -T2
J
Σ Sj Σ Tess - -EE T
Σ 5 ΣΣ
T Texj
(6)
Due to the symmetry of and j, for the second term Eier 543 To.ise. we have
Σ
TeiTTe.
Σ Σ (e, Te,ús)
(R, is the of the i th row, and R, 1)
(m 547
Σ Σ Ta..j -T2,5
$
ΣΣ
T2
(7)
Therefore, substituting Equation (6) and (7) into A, we have
A= 53
ΣΣ T2 cag + c ΣΣ T2 à + <
Tej
3 3
i=)
14

---

Under review as a conference paper at ICLR 2021
To prove Snoise Croise I 0 is equivalent to prove A - 0.
Let M = e² - c, N = E, $ - 2I, + Tiy (we drop the subscript c in Teay), and A N M. Now we utilize the Adjustment method (Su Xiong, 2015) to scale N. For every iteration, we denote the original N by No. and the adjusted N by Na.
Since e 2 8, there can not exist three columns with column sum bigger than c/2 1. Otherwise, the sum of the three columns will be bigger than c, which is impossible because the sum of the whole matrix is c.
Therefore, first, we assume that the j. k th columns have column sum bigger than c/2 - 1. Then, for the row i, we add the elements I, which are not in j. k - th columns, to the diagonal element. We have
Na- No (8, (5:+ + - 2(Th + +T))² - S - + + +
TT((TT + +25, - 25; +c-
Tu(2Th + 27.)
(: Tw)
T2((TT -c+2+ 2T.
(: < c/2 1)
20. (: T: 1)
We do such adjustment to every rows, then N₂ is getting bigger and the adjusted matrix will only have values on diagonal elements and the j, k - th columns. Since the diagonal elements are dominant in the row, S + S < 2c/3 + 2/3 (because for # j. T. + Tik- < 2/3).
Assume that the column sum of k th column is no bigger than that of the j th column, and thus Se <
+ e/3+1/3. Then, for a row i, we add the Tip to Tã. We have
Na No = (S; + T + (Sa + Txx)² + cTax- 2(Ts + Tax)² - S? -5t 2(T + T7,)
Ti (2TT + +2; - + c- 4T):)
2 Ta -25, c
(: 2 TT)) (: Sx < <c/3 1/3)
Tok (2 + -/3-2/3 -TT.)
2 0.
(: 8, and Ti S 1)
We do such adjustment to every rows, then N₂, is getting bigger and the adjusted matrix will only have values on diagonal elements and the j th column, which is called final matrix.
Note that if there is only one column with a column sum bigger than c/2 - 1, we can adjust the rest columns as above and then obtain the final matrix well. If there is column with column sum bigger than c/2 1. we can adjust all the elements as above and then obtain unit matrix. For the unit matrix,
N M N. M- 0, the Theorem 2 is proved.
Now we process the final matrix. For simplification, we assume j = 0 in the final matrix. We denote the Tiş by b, and Tú by az for i = c 1). We have
No Σ of (1+ b.)
0: 11) 2
2 Σ
a
63 +1)
(1 (1+] Σ b2)2 + Σ
0i +
Σng -2 2
82
1+
b 2 + +2 Σ
bi + Σ
4 +c Σ 0 -2-27 > -2 -2
Σ 6))² + 2 Σ b - 2 Σ
b + e Σ 4; Σ a +c-1
Σ b 2 3 14 2 Σ
1/ + e Σ (1 - b)) -
(1 - b,)² +c-1
E 6) + 2 b. - 2 2 2
Eb.
bi --- (1 2b, + b8) +c-1
cc
Σ 6.) 4 Σ
b -3 Σ
1 Σ +2 -c
15

---

Under review as a conference paper at ICLR 2021
Now prove A= N - Na
M I 0. Note that
Na M Σ b Σ b 3
E b3 - Σ
Σ b 2 b, 3 Σ b (c 1) Σ b,
Σ 1.) + 3 Σ 4 3 3 6 Σ -b;)) + Σ b.)
Σ
b;
i
3 Σ b - Σ 6 Σ
(1-10) - b.) Σ bi
3 Σ 4(1 b.) Σ (1 - b:) Σ bi.
According to the rearrangement inequalityHHardy et al., 1952), we have
b, (c- 1) Σ be(1 b;))
S 0, and A S 0. Therefore Snoise Croise S O, and the equation holds if and only if the noise rate is 0 or every instances have the same noisy class label (i.e., there one column in the T. of which every elements are I, and the rest elements of the Te are 0). Above two extreme situations are not considered in this paper. Namely, the noise rate of noisy similarity labels lower than that of the noisy class labels. Theorem 2 is proved.
Note that 2 thus 3 Σ, -,
C PROOF OF THEOREM 3
Theorem 3. Assume the parameter matrices Wi...., Wa have Frobenius norm at most Mi..... Má and the activation functions are I-Lipschitz, positiv--honogeeouu, and applied element- wise (such as the ReLU). Assume the transition matrix given, and the instances X are upper bounded by B, i.e., ||X|| S B for all X, and the loss function 8 is upper bounded by M Then, for any ó >> 0, with probability least 8,
(Tu.11 - TT,01 (000)) + 1)II M,
log 1/6
R( (f) 5
+ M
(8)
Tau1v
2n
Proof. We have defined
R(f) =
(9)
and
Rn,(f) 1=1
(10)
where n is training sample size of the noisy data.
First, we bound the generalization error with Rademacher complexity (Bartlett & Mendelson, 2002).
Theorem (Bartlett Mendelson (2002)). Let the loss function be upper bounded by M. Then, for
any 8 0, with the probability 1 5, have
log 1/8
sup R(f) - (2) < fer
(11)
2n
Thh assumption holds because deep neural networks will always regulate the objective to be a finite value and thus the corresponding loss functions are of finite values.
16

---

Under review as a conference paper at ICLR 2021
where ( F) is the Rademacher complexity defined by
m
(e F)
sup [EF
T(x) Hig))
(12)
and (or,... Ja) are Rademacher variables uniformly distributed from (-1,1}.
Before further upper bound the Rademacher complexity R, (8 F), we díscuss the special loss function and its Lipschitz continuity w.r.t h2 (Xi), {l..... C}.
Lemma Given similarity transition matrix T, loss function f(X() H.y) p Lipschitz with respect hg (X+), {1,...,C)) and μ (Ts,11 //s.0)//ss.11
T. Hoy)) (X,)
T3,11 - TT.01
(13)
Ta.11
Detailed proof of Lemma I can be found in Section C.I.
Lemma shows that the loss function is p-LLisccitz with respect to (x,)),, (I...., C}. Based on Lemma 1, we can further upper bound the Rademacher complexity R., F) by the following lemma.
Lemma 2. Given similarity transition matrix Tg and assume that loss function (((()), Ts, H.z) is p- p-Lipschitz with respect to h2 (x)), k= (1....,C) we have
Rr
E
sup fer n
(((() ((X))) Tu, Fl.s)
S
4CE
sup helf TI
ash(())
(14)
where is the function class induced by the deep neural network.
Detailed proof of Lemma 2 can be found in Section C.2.
The right-hand side of the above inequality, indicating the hypothesis complexity of deep neural networks and bounding the Rademacher complexity, can be bounded by the following theorem.
Theorem 5. (Golowich et al., 2018) Assume the Frobenius norm of the weight matrices WI...., Wa at most MI,..., Ma. Let the activation functions be 1-Lipschitz, cositiv--homogenenss and applied element-wise (such as the ReLU). Let X is upper bounded by B, i.e., for any X, |X|| < B. Then,
B(V2dlog2 + I)III,
E sup he n
(15)
Combining Lemma 1,2, and Theorem 4, 5, Theorem is proved.
C.1 PROOF OF LEMMA
Recall that
(U(()), To, Hi = log($;;)
log(S x T2.11 (1 3y) Te.1))
- -log(f(XX,) f(Xx) Ta.1 + ((x, f(x))
f(X)))(((x)) x TT,01):
(16)
17

---

Under review as a conference paper at ICLR 2021
where
f(X;) =
..... (x(xx))....((xx...]]
= - exp(hx(X))
exp(Ii
exp(he(X)) Ek= exp(ha(X))
(17)
Take the derivative of ((f(()), f(X)), Te, Hig = 1) w.r.t he (Xx)), we have
(e(f(X)), F(X,),, H. = 1) 08 (e(f(X)). ((X,), H.g 1)
0f((x))
1T 0Sg
(18)
(X,)
05:g
@hr(X.)
0f(x,))
where
((X,,) Te, Hij =)
1 f(X.) f(X,) Te.11 + (1 f(X,) f(X,)) x T,,01
08:;
aš. ((x)) Ts,11 (x(1)) Ts,01,
0f(X.)
0x(X.) (X())) = LI( (((.)..
(X,)
Note that the derivative of the softmax function has some properties, i.e., if m # k, fz (X.)
and if m = k, (X;) = (1 - (X.))..)
We denote by Vectorm the (X,) < 1, Vm E (1,...,c), c). we have
th element in Vector for those complex vectors. Because 0
(x.)). S (X.)) (x,),, f(x.)) f(x,) < s(X,).
Vm (l.....cc
(19)
(20)
Therefore,
((X)( T,, H.g 1) 11)
((X() T., H.; = 0x,),))
as,;
(hx.
a5.g
Oh4
0f(X.)
('(X) f(X;) x Ts.11 ('(X,) x Ts.0
f(X.) f(X,) X To.11 + (1- f(x))(((Xxx)
f(X;)) x Ts,01
((X,) x xT,
f(X;) x T2.01
f(X.) f(X,) T&m (1 fXX, f(X,)) x Ts,01
T..11 T1.01
To.11
Ta. -T..01
(21)
Ta,11
The second inequality holds because of T..11 > To,01 (Detailed proof can be found in Section C.I.I) and Equation (20). The third inequality holds because of / f(X,) s(x,) <1. Similarly, prove
H.j =0] (X,,
Ts.11 Tx.01
(22)
T.111
Combining Equation (21) and Equation (22), we obtain
[e(](X)), Tu, Hig)
To Ts,11 - Ta.
(23)
(X,)
Tem
18

---

Under review as a conference paper at ICLR 2021
C.1.1 PROOF OF Ts,11 Ta,01
As we mentioned in Section B, we have,
Noo n² Σ
TowTTors
No1 n² i#'
Σ
TesiToNy
64'551
N10 = n²
N11 = n²
Σ
No1
No T=,1= Nio + N11
T,,01 = Noo + Noi
T,,11 T3,01 No1 + NI1 No1 Nio N11
(Noo + No1) + N11)
Let us review the definition of similarity labels: if two instances belong to the same class, they will have similarity label = 1. otherwise S = 0. That is to say, for k-class dataset. only & of similarity data has similarity labels S 1, and the rest
We denote the number of data with similarity labels S = 1 by N,. otherwise No- Therefore, for the balanced dataset with n samples of each class, N1 = en?, and No c(c 1)n?. Let A T. To, 00, we have
has similarity labels S
A = Nu Noo No1 Noo
Nu Noo (No No N11)
Nu Noo NoNi NoNNo + N No + No
No No
c(c 1)n²
Nn N1
on2 No1
> 0.
The last equation holds because of (c 1) No1 >> 0 according to the rearrangement inequality (Hardy et al., 1952).
C.2 PROOF OF LEMMA 2
n sup JEF 11
((X((( H.)
sup 71
Hey))
sup argmnax ke n
(x((((x),,(()).))..) H.))
=
sup
max hh) i=1
1
< E
sup
#= ty EH
1=1
Σ
E
sup
1
(((x)))) ((,,)))
hiEH ni
$ μCE
sup
(X,)
MiEH n
1 a ax,((x))
μCF
sup heH n
where the first three equations hold because given Ts, and max(h hc) give the same constraint on (X.). (1...., C}; the sixth inequality holds because of the Talagrand Contraction Lemma (Ledoux & Talagrand, 2013).
19

---

Under review as a conference paper at ICLR 2021
D DEFINITION OF NOISE SETTINGS
Symmetric noise setting defined as follows, where is the number of classes.
1 P
Sym-p: T=
(24)
p
C-1
The 0.3 asymmetric noise setting is set as follow,
def asym
(nois 3, cun_classes=10,
seed=1):
np. rp.dannom..s (seed)
t np. random. rand (num_classees num_classes
i - np.eye (num_classen)
t = t + 1.2 num classes
for in range (num classes)
tla] = tal / t [aa sum..umff ()
return
Listing 1: Asymmetric noise (transition matrix) generation.
E EXPERIMENTS
E.1 GIVEN GROUND-TRUTH CLASS Tg
012
112
Centiinn
(a) AINIST
(6) CIFARIO
(e) CIFARI00
Figure 5: Means and Standard Deviations (Percentage) of Classification Accuracy 5 trials MNIST, CIFARIO and CIFAR/00 with symmetric noise. Forward and Class2Simi are trained with estimated T. Forward.Trrues is trained with ground-truth class T, and Class2Simi.Truee TrueT trained with similarity T' calculated from ground-truth class Te-
From Figure 5, overall, we can see that Class2Simi (Class2Simi.Truel) achieves the best perfor- mance whenever class T. given or estimated. most cases. Class2Simi with estimated T, even outperforms baselines with the ground-truth class noise transition matrix, due to lower noise rate and the similarity transition matrix being robust to noise. Specifically, On MNIST, as the noise maintains remarkable accuracy above
rate increases from Sym-0.1 1 to Sym-0.5, Class2Simi.Truus 99.20% while the accuracy of Class2Simi and Forward TrueT decrease steadily. However, there is significant decrease in the accuracy of Forward. On CIFARIO, the patterns of varying tendencies of four curves are similar to that of MNIST except that the decreases are more dramatic and even Class2Simi_1 TrueT drops slightly at Sym-0.5. On CIFAR100, there is obvious decrease in the accuracy of all methods and our method achieves the best results across all noise rate, i.c., at Sym-0.5, Class2Simi gives accuracy uplift of about 8.0% compared with Forward.
20

---

Under review as a conference paper at ICLR 2021
Quicc
sar gp00n
sempleing
(4) MINIST
(b) CIFARIO
CIFAR/90
Figure 6: Means and Standard Deviations (Percentage) of Classification Aceuracy over 5 trials on MNIST, CIFARIO and CIFARI00 trained with different sampling rate of training data. The noise rate on training data set to Sym-0.5.
E.2 TRAINING WITH DIFFERENT SAMPLING RATE ON TRAINING DATA
In Figure 6, we show that the Class2Simi performs well even with fewer data. The noise in training data Sym-0.5, We randomly sample from original training data with a sampling rate from 0.5 to 1.0 and train the model on the sampled data. Test datasets remain the same. At each sampling rate, Class2Simi performs better than the baseline. With only 50%, 80% and 80% data on MNIST; CIFARIO and CIFARIO0, our method can achieve the same accuracy as Forward.
E.3 RESULTS ON ASYMMETRIC NOISE SETTING
Table 5: Means and Standard Deviations (Percentage) of Classification Accuracy over 5 trials on MNIST, CIFARIO and CIFAR100 with asymmetric noise of which the noise rate is about 0.3.
0.3 Asymmetric Noise
MNIST
CIFARIO
CIFARIOO
Co-teaching
97.99-10.16
83.08
47.07-40.84
APL
98.6910.14
80.9910.79
28.28:11.69
S2E
97.98.10.06
57.02 1.66
43.67.11.48
Forward
98.30110.33
84.03-10.47
42.77-11.52
Forward & Class2Simi
0.14
85.05
49.96-+0.88
Reweight
97.70++0.12
43.07+1.01 04.10
Reweight & Class2Simi
97.76.10.38
84.69
48.47
Revision
98,21=0.111
84.85:10.35
43. 43.14110.98
Revision & Class2Simi
98.24+0015
85.11+0.27
48.69++0.83
In Table 5, we demonstrate the effectiveness of our method under the asymmetric noise setting.
F LEARNABILTY CONNECTION BETWEEN PAIRWISE CLASSIFICATION AND POINTWISE CLASSIFICATION
F.1 Pointwise IMPLIES pairwise
For an invertible To, denote by v, the j-th column of Tf and the all-one vector. Then,
Σ
To Tex) = E (v 1)²
Σ 1|v 111111 clT..ll..
1
21

---

Under review as a conference paper at ICLR 2021
where we use the Cauchy-Schwarz inequality (Steele, 2004) in the second step. Further, we have é c
T |ell
EE [[Tll
T3 + T,,00
②² -c
1) Pro - (Ej (Ei (r.1s) 1[Tal P.o.)
(c- T)
+ +
(E) (Vj, 1)2 11Ta11ro0
c²
(c Tell
+
(cl Tell lTTel
c²
Thus the learnability of the pointwise classification implies the learnability of the reduced pairwise classification.
F.2 Pairwise DOES NOT IMPLY pointwise
Assuming the number of classes is 10 and the dataset is balanced, singular Te of the pair noise pattern and the transformed T3 are shown as follows,
0.5
0.5
0
0.5
0.5
0.95
0.05
Tg
T,
0.50
0.50
0.5
0.5
00.5
0
0
0.5
In this case, the reduced pairwise classification learnable while the original pointwise classification not learnable.
Thus the learnability of the reduced pairwise classification does not imply the learnability of pointwise classification.
22


Reviews:
[{"review_id": "qnFWEqnwKF", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this work the authors propose a method to learn from noisy labels. The propose method converts the noisy labels to similarity labels which are more robust to noise and helps in reducing the noise ratio in the training data. The proposed method has been evaluated on multiple datasets with consistent improvement across all noise ratios.\n\nPros:\n\nThe proposed idea to convert the class labels to similarity labels is very interesting and intuitive. It has some good properties which leads to a better performance.\n\nThe authors provide a theoretical analysis of the proposed method to estimate similarity noise transition matrix which makes it more grounded.\n\nThe authors have provided sufficient experimental results on multiple datasets to demonstrate effectiveness of the proposed learning technique.\n\nCons:\n\nFor asymmetric noise, the results are shown only for a noise rate of 0.3. How will the method perform when the noise rate is lower or higher in case of asymmetric noise. Also, how does the proposed method compares with existing approaches for asymmetric noisy learning? The asymmetric noisy learning in Li et. al. 2019 (and many others) can achieve around 93% accuracy on CIFAR-10 which is 10% higher then the proposed method. \n\nThe presented ablation study is not very meaningful. The authors have shown that on a clean dataset, the proposed method does not have any effect, sometimes the score improves, sometimes it goes down. Ideally the performance should not have been gone down, how will the authors explain the results on news20?\n\n-- post rebuttal --\n\nAfter carefully reading the authors response and the discussions with other reviewers, I am updating my ratings. The authors acknowledged that it is not a theory paper and therefore, the biggest concern is empirical evaluation. The shown performance is not comparable with existing high performing methods and therefore it is hard to judge without any direct comparison. The authors stated that their method can be applied on top of any existing method, which was not shown in this submission and therefore it will not be meaningful to judge just based on this statement. I believe showing this empirically will definitely strengthen this submission.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "e84yZrkWRXU", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper proposes a new perspective on dealing with label noise, called Class2Simi, by transforming the training examples with noisy labels into pairs of examples with noisy similarity labels and then learning a deep model with the noisy similarity labels. Experimental results on real datasets show that Class2Simi achieves better classification accuracy than its baselines that directly deals with the noisy class labels. \n\nThe idea to deal with label noise by transforming noisy class labels into noisy similarity labels seems to be novel. The proposed Class2Simi provides a framework to improve different existing learning methods. Furthermore, the paper proves that the noise rate for the noisy similarity labels is lower than that of the noisy class labels. In addition, the paper is well written with good organization. \n\nAlthough in most cases the proposed Class2Simi can improve the accuracy compared with baselines, the improvement is not significant in many cases like those on MNIST and CIFAR10. It is better to provide deep analysis about the principle of the proposed method and the experimental results, and give insight for readers about when the proposed method will achieve significant improvement and what is the underlying reason.\n\n-------------------\nAfter rebuttal:\nI thank the authors for clarification. I would like to keep with my score.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Irq4_pA_LED", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "**Summary**\nThe paper addresses the problem of learning with noisy labels by transforming the original category classification task into a semantic-similarity prediction task. The new task takes pairs of samples as input and predicts if the two samples are coming from the same category or not. It is theoretically shown that the similarity pairs have lower noise rates compared to the original categorization. It is then argued that this lower noise rate makes the learning more robust in the presence of class label noise. \nIn practice, the idea is applied on top of a standard categorization network (equipped with other approaches to handle class label noise). Specifically, for each pair, a similarity score $\\in[0,1]$ is obtained from the category outputs of the two samples as the dot product of their softmax distributions. Then, a similarity transition matrix (that is pretrained) is applied to the prediction. Finally, a two-class cross-entropy loss is optimized. \nThe similarity transition matrix is obtained by using prior techniques for finding a $C\\times C$ class transition matrix (with $C$ being the number of classes) and then analytically turning it into a $2\\times2$ similarity transition matrix.\n\n**Quality**\nThe writing is of a noticeably-low quality and seems to have been overly-rushed. The experiments are done on several datasets of different modalities. The theories are partially informative but not entirely and/or directly relevant.\n\n**Clarity**\nThe method section is not clearly written. Section 3.1 and 3.2 were quite hard to follow due to some notational inconsistencies, lacking definitions, and not being self-contained (relies on the knowledge of Hsu et al. 2018). The relevance and implications of the theories are not properly discussed. \n\n**Originality**\nThe idea of turning category classification to similarity prediction in order to make the learning robust to class label noise seems quite original to the reviewer’s knowledge.\n\n**Significance**\nThe results show improvements on various benchmarks as well as various underlying category classification methods for learning under noisy labels. The improvements are not always substantial but they seem to be statistically significant and consistently present for large synthetic symmetric noise levels of CIFAR100. The idea being general and the results somewhat significant indicate a potential significance of the method.\n\n**Major technical comments**\n\n*Theory*\n\n1. when learning with similarity labels, is it important to consider the total noise levels among similar and dissimilar pairs or also the worst case of noise level in similar pairs and dissimilar pairs separately? To make this more clear, imagine the extreme case that all of the given labels are noisy. Even for this case, when constructing the similarity labels, while all similar labels can be wrong, still the majority of dissimilar labels (and vast majority if the number of classes are high) will be correct. This renders the similarity noise rate to be (arbitrarily) low (depending on the number of classes and samples per classes). Does this low noise rate mean the task is learnable although there is literally zero information on true class labels? I doubt it. That would essentially mean we can take any set of images and apply random similar/dissimilar pairs to them and consider it a low-noise-rate dataset. Thus, formal analysis and/or informal theoretical discussions are required in this regard.\n2. from algorithm 1 it seems the method requires two independent trainings, shouldn’t that at least double the computational complexity? Learning with pairs could potentially take longer to converge due to the quadratic increase in the number of input data. How is the claim in section 3.3 that “Class2Simi increases the computation cost *slightly*” supported?\n3. regarding theorem 3, based on the first point above, I have a concern that the relevant risk to be studied here should be the original category classification risk as opposed to the similarity risk. The latter could be dominated by the dissimilar pairs and unless formally analyzed or at least directly discussed it’s hard to draw any conclusion on how the bound on the similarity prediction empirical risk translates to a bound on the original classification risk which is the objective of interest.\n\n*Experiments*\n\n1. Regarding the experiments on Clothing1M, while I understand the raised points regarding the dominant class confusion, I believe the method should still be compared on the original dataset along with the proposed Clothing1M*. In fact, this can be a weakness of the proposed method that should be studied further and more thoroughly with designated experiments. Such a noise is possible in the real-world applications due to semantic ambiguity or human error (as demonstrated in Clothing1M).\n2. Is the same set of hyperparameters used for all the baselines as well as the variants of the proposed approach? How are the hyperparameters optimizations done? In particular, which variant of the method or baselines are the hyperparameters optimized on? In our experience, when it comes to noisy labels, it is quite common that different methods perform better with different sets of hyperparameters, so it’s important to optimize the parameters per method.\n3. the improvements for asymmetric noise, and on MNIST and CIFAR seem marginal. A statistical paired significance test could be useful.\n\n**Minor technical comments**\n\n- the notation of the summands’ subindices $i,j,i’,j’$, in theorem 1 is a bit confusing. For instance, when $i=i’$ should only $i$ be used?\n- the similarity label is denoted as $H_{ij}$ in section 3.1but as $S_{i,j}$ in figure 2 and section 3.2.\n- what is the difference between samples denoted by $X_i$ in section 3.2 and $x_i$ in section 3.1?\n- what does $\\theta$ parametrize? The network or the similarity transition matrix? What is the difference between $f(X_i)$ and $f(X_i;\\theta)$ in figure 2?\n- the algorithm defines a function $g(.)$ which is not referred to in the methods section\n- where are parameter matrices $W_1,...,W_d$ defined? What is d?\n- how is the expected risk $R$ defined? \n- what is $\\hat{f}$ \n- what is $R_n$?\n\n**Overall**\nWhile the reviewer can guess the meaning of some of the notations based on the literature it renders the paper hardly readable and at times the discrepancies were unresolvable to the reviewer. Furthermore, there are concerns regarding the motivation, relevance of the theories, and the significance of the results. So, overall, while I believe the paper has original contributions of potentially high impact I strongly believe it needs a major revision before it’s presentable at a conference.  \n\n**Post Rebuttal**\nI had concerns regarding the clarity, theory, and experiments. During the rebuttal phase, the authors actively discussed various points raised by the reviewers and the AC. Despite its length and breadth, I do not find them addressing the core of the raised concerns. That is except my 2nd point of the major theory concerns, regarding the time complexity and convergence time which is at least partially addressed.  The time complexity is addressed since the length of the first round of training for transition matrix is negligible compared to the main training. The convergence time would also be addressed if the number of epochs for the proposed method is the same as the baselines. The reviewer is not entirely sure that is the case though. Given the outstanding majority of the concerns my final feedback is as follows:\n\nThe paper provides an original idea for learning with label noise which is positive, to rate the demonstration of the relevance of the idea, I can either consider the paper from an empirical study lens or a theoretical one. \n\nFrom the latter perspective, the concerns above effectively affect the whole theoretical arguments of the paper. The main claim of the paper, even in the latest revision, is based on the noise rate of similarity labels being lower than the noise rate of the corresponding class labels and that this is what can bring improvement in the final performance. This reads absolutely unfounded to the reviewer. As discussed, the similarity rate is mostly influenced by dissimilar labels (in the balanced c>2-classification scenario) and can be made arbitrarily low. Furthermore, the discussion still does not make a clear formal connection between the error bound on the noisy similarity learning and the noisy classification for the general case. Nevertheless, such a connection would require a major revision/addition to the paper that would need a proper round of review.\n\nWhen it comes to the empirical view, the experiments are inconclusive and not thorough-enough for an empirical paper due to 1) the drastic change in the learning setup (which is implemented inhouse including the base transition-matrix methods) in tandem with the fact that hyperparameter optimization is not done per method (e.g., the hyperparameters are taken from the papers for baselines while they are optimized for the proposed method's training). This is especially important since when learning with noisy labels, the choice of hyperparameters are extremely influential in the final results. 2) the improvements are mostly marginal except for CIFAR100. 3) Results are not provided for the original Clothing1M dataset. The shortcoming that led to changing Clothing1M needs to be thoroughly studied for an empirical work since it directly affects the applicability of the paper.\n\nOn top of these, the final version of the pdf is still lacking on clarity several instances of which were listed in the original review. \n\nThus, considering all the points above leads me to confidently keep the original rating as \"clear reject\".", "extra_scores": {}, "extra_text": {}}, {"review_id": "IT2KJXizSUR", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper proposes a new algorithm on learning noisy datasets by transforming class labels into pairwise similarity labels. It also gives some theoretical analysis on the fact that the induced similarity noise transition matrix works better than the class noise transition matrix. The paper empirically demonstrates that the proposed method works well on several synthetic datasets and a large-scale real-world dataset.\n\nStrengths:\n- I believe the idea to use pairwise similarity as supervision is novel and interesting, and it is easy to implement.\n\nWeaknesses & Questions:\n- I think the analysis is a bit problematic. Th. 2 shows that when the number of classes is large (>8), the noise rate of similarity labels is less than class labels. And the authors use Th. 3 to prove that if the noise rate of transition matrix decreases the model will have a better generalization. However, as far as I understand, the supervision effect of the pairwise label differs a lot between positive and negative labels. In fact negative pairwise supervision is not very meaningful as there are a lot of gradient directions that can minimize the loss. Thus I think evaluate on the noise ratio of the whole pairwise similarity matrix is not very meaningful. And since the supervision effect of class-level and similarity-level labels is so different, it casts questions on the whole theoretical analysis in my understanding.\n- The baselines on CIFAR seem too low compared with the SOTAs, e.g. [1], and the improvement of the proposed method is limited. And the final result is not comparable as well. For example, under the setting of 0.5 sym noise of CIFAR-10, the best result of the proposed method is 81.15, while [1] has 84.78.\n\n[1] Chen, Pengfei, et al. \"Understanding and Utilizing Deep Neural Networks Trained with Noisy Labels.\" International Conference on Machine Learning. 2019.\n\n-----------------------------\nPost Rebuttal Modification\n\nRegarding A1: I agree with R2 that the theory has major concerns and the authors were not able to fix it during rebuttal. I think we need to be clear that whether the method can work empirically and whether the provided theory can explain it are two problems. Now it seems to me that it is clear that the theory is wrong, and the problem is that the authors did not take into account the difference of the class-wise labels and pairwise labels. I suggest the authors to change the theory completely or remove the theory before next submission.\n\nRegarding A2: I don't chase SOTAs and I could certainly appreciate works that give nice theoretical insight but limited improvement. Now that the theory is wrong I have to be critical about the experiments. Since the performance is much worse than STOA, it is no longer clear whether the proposed algorithm works or it's just because the baselines are too bad.\n\nI adjusted my rating from 5 to 1.\n\n-----------------------------\nRegarding the authors' 2rd and 3rd responses\n\nFirst, please allow me to clarify that my wording \"the theory is wrong\" means the theoretical justification on why the proposed algorithm can benefit from the transformation and achieve better performances is wrong, as the authors wrote “This theoretically justifies why the proposed method works well” in their submission. The major flaw/concern has been raised by R1(Q1) and myself(Q1), and the authors’ responses on these two questions are not convincing. This is the concern that I have been asking, so I assume it is not “vague”. I don’t see any potential way to fix this major concern in the current theoretical justification sketch, so I think this submission needs a major revision. I want to give my apology if my wording \"the theory is wrong\" leads to misunderstanding to the authors or other reviewers.\n\nSecond, I would like to see ACs or PCs to step in and let me know if I could rate the submission as 1 in this case. I have temporarily increased my rating from 1 to 3 as it has been questioned by the authors, especially the author who “have served as a reviewer 100+ times and as an area chair 10+ times for top conferences like NeurIPS/ICML/ICLR”.\n\nWhat’s more, I would also like to request apologies from the authors. The wording “angry” is unpleasant and misleading. As the author asked, “what are you angry for?”, I’m not angry at all. I simply adjusted my post-rebuttal rating with my expertise after reading the authors’ responses and other reviewers’ comments.\n\nFinally, I would like to remind the author who “have served as a reviewer 100+ times and as an area chair 10+ times for top conferences like NeurIPS/ICML/ICLR”, one of the main rules of academic writing is to avoid using second person. I hope this will be helpful.\n\nBest\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "61INYCxsKOa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper presented a working framework for learning a robust classifier with noisy labels. It proves that if the number of the classes is more than 8 then the noise rate in the similarity matrix is less than that in the noise rate in labels. Hence after learning classifiers from noisy labels, it updates the classifier using entropy loss between predicted similarity matrix and actual similarity matrix calculated from similarity matrix from data multiplied with noisy transition matrix derived using existing techniques(Xia et al., 2019; Patrini et al., 2017). \n\nIt also provides the generalization bound for the proposed techniques. \nThe paper has a strong experimental evaluation of the proposed method against recent models on robust learning with noisy labels. \n\nMy concern is the technical novelty of the proposed model, as learning from the noise transition matrix (Xia et al., 2019; Patrini et al., 2017) and learning from the similarity matrix (Hsu et al., 2019) both are well known. It will be better if the author discusses their contribution in detail. \n\n\nIt will be good if the authors also comment on the running time of the proposed method as it is learning the classifier first from the noisy labels. What happens if one learns ‘f’ in stage 2 with a random classifier? \n\nIn Tabel 1 for most of the cases, forward+C2S is outperforming others. Why? In Table 2, we have seen that model does not make a significant change in the news20 data set. Why so?\n\nWe have seen that difference in performance is higher with a higher noise rate in the labels. The authors have stated in Theorem 1 that the noise rate for the noisy similarity labels is lower than that of the noisy class labels. But they did not provide any quantitative analysis of that. It will be good to see what is the reduction in the rate with respect to the number of classes and also the noise rate in labels.\n\nI tend to accept this paper with clarification asked. Though the paper has combined existing ideas to learn a robust classifier, the proposed classifier is outperforming when the noise rate is higher. Hence it can be useful for the ML communities. Along with this, the paper has also given a generalization bound. \n\n\n---------------------\nI thank the author for clarification. I would like to be with my score.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper's stated contributions are:

(1) a new perspective on learning with label noise, which reduces the problem to a similarity learning (Ie, pairwise classification) task

(2) a technique leveraging the above to learn from noisy similarity labels, and a theoretical analysis of the same

(3) empirical demonstration that the proposed technique surpasses baselines on real-world benchmarks

Reviewers agreed that (1) is an interesting new perspective that is worthy of study. In the initial set of reviews, there were concerns about (2) and (3); for example, there were questions on whether the theoretical analysis studies the "right" quantity (pointwise vs pairwise loss), and a number of questions on the experimental setup and results (Eg, the computational complexity of the technique). Following a lengthy discussion, the authors clarified some of these points, and updated the paper accordingly.

At the conclusion of the discussion, three reviewers continued to express concerns on the following points:

- *Theoretical justification*. Following Theorem 3, the authors assert that their results "theoretically justifies why the proposed method works well". The analysis indeed provides some interesting properties of the reduction, such as the fact that it preserves learnability (Appendix F), and that the "total noise" is reduced (Theorem 2). However, a complete theoretical justification would involve guaranteeing that the quantity of interest (Ie, the clean pointwise classification risk) is guaranteed to be small under the proposed technique. Such a guarantee is lacking. 
  - This is not to suggest that such a guarantee is easy -- as the authors note, this might involve a bound that relates pointwise and pairwise classification in multi-class settings, and such bounds have only recently been shown for binary problems -- or necessary for their method being practical useful (per discussion following Theorem 3). Nonetheless, without such a bound, there are limits to what the current theory justifies about the technique's performance in terms of the final metric of interest.

- *Comparison to SOTA*. Reviewers noted that the gains of the proposed technique are often modest, with the exception of CIFAR-100 with high noise. Further, the best performing results are significantly worse than those reported in two recent works, namely, Iterative-CV and DivideMix. The authors responded to the former in the discussion, and suggested that they might be able to combine results with the latter. While plausible, given that the latter sees significant gains (Eg, >40% on CIFAR-100), concrete demonstration of this point is advisable: it is not immediately apparent to what extent the gains of the proposed technique seen on "simple" methods (Eg, Forward) would translate more "complex" ones (Eg, DivideMix).
  - In the response, the authors also mentioned that (at least the initial batch of) the experiments are intended to be a proof-of-concept. This would be perfectly acceptable for a work with a strong theoretical justification. However, per above, this point is not definitive.

- *Creation of Clothing1M*. The authors construct a variant of Clothing1M which merges the classes 3 and 5. Given that prior work compares methods on the original data, and that this potentially reflects noise one may encounter in some settings, it is advisable to at least report results on the original, unmodified version.

- *Issues with clarity*. There are some grammatical issues (Eg, "is exact the"), typos (Eg, "over 3 trails"), notational inconsistencies (Eg, use of C for # of classes in Sec 2, but then c in Sec 3.1), and imprecision in explanation (Eg, Sec 3.2 could be clearer what precise relationships are used from [Hsu et al. 2019]).
  - These are minor but ought to be fixed with a careful proof-read.

Cumulatively, these points suggest that the work would be served by further revision and review. The authors are encouraged to incorporate the reviewers' detailed comments.
Decision: Reject