Year: 2020

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 “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.

heading: 1 INTRODUCTION
text: 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 et al., 2019; Yi & Wu, 2019; Zhang et al., 2019; 2018; Xia et al., 2019; 2020).
In this paper, we propose a new perspective on handling label noise called “Class2Simi”, i.e., 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 a 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, a 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 {(x1, ȳ1), . . . , (x8, ȳ8)} as shown in the upper part of the middle column. Their labels are of four classes, i.e., {1, 2, 3, 4}. The labels marked in red are incorrect labels. We transform the 8 examples into 8× 8 example-pairs with noisy similarity labels as 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 x4 both have incorrect class labels, the similarity label of the example-pair (x2, x4) 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 1 are generated according to the latent clean labels and the transition matrix shown in the upper part of the right column (the ij-th 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.
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 to 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 is 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 is reduced, the signal to noise ratio is increased, and so would be the total amount of signals. Thus, we can benefit from the transformation and achieve better performances. Theorem 2 and the experimental results will verify the effectiveness of this transformation.
It remains unsolved how to learn a robust classifier from the data with transformed noisy similarity labels. To solve this problem, we first estimate the similarity noise transition matrix, a 2 × 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 a new perspective on learning with label noise, which transforms class labels into similarity labels. Such a 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 classification problem, and in Section 3, we propose the Class2Simi strategy and practical implementation. Experimental results are discussed in Section 4. We conclude our paper in Section 5.

heading: 2 PROBLEM SETUP AND RELATED WORK
text: Let (X,Y ) ∈ X × {1, . . . , 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 a sample {(x1, ȳ1), . . . , (xn, ȳn)} drawn from the noisy distribution Dρ of the random variables (X, Ȳ ). Our aim is to learn a 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., 2018b; Malach & Shalev-Shwartz, 2017), reweighting examples (Ren et al., 2018; Jiang et al., 2018; Ma et al., 2018; Kremer et al., 2018; Tanaka et 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 et al., 2018; Veit et 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 & Ben-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., 2018). There are also methods showing how to identify anchor points from the noisy training data (Liu & Tao, 2016; Patrini et al., 2017).

heading: 3 CLASS2SIMI MEETS NOISY SUPERVISION
text: 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.

heading: 3.1 TRANSFORMATION ON LABELS AND THE TRANSITION MATRIX
text: As in Figure 1, we 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 0. If the class labels are corrupted, the generated similarity labels also contain noise. We denote the clean and noisy similarity labels of the example-pair (xi, xj) by Hij and H̄ij 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,mn = P (H̄ij = n|Hij = m). The dimension of the similarity noise transition matrix is always 2× 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 c classes in total), and the noise is class-dependent. Given a class noise transition matrix Tc, such that Tc,ij = P (Ȳ = j|Y = i). The elements of the corresponding similarity noise transition matrix Ts can be calculated as
Ts,00 = c2 − c−
(∑ j( ∑ i Tc,ij) 2 − ||Tc||2Fro )
c2 − c , Ts,01 =
∑ j( ∑ i Tc,ij)
2 − ||Tc||2Fro c2 − c ,
Ts,10 = c− ||Tc||2Fro
c , Ts,11 = ||Tc||2Fro c .
A detailed proof is provided in Appendix A.
Remark 1. Theorem 1 can easily extend to the setting where the dataset is unbalanced in classes by multiplying each Tc,ij by a coefficient ni. ni 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 classdependent label noise, a binary classification is learnable as long as T00 + T11 > 1 (Menon et al., 2015), where T is the corresponding binary transition matrix; a multi-class classification is learnable if the corresponding transition matrix Tc is invertible. For Class2Simi, in the most general sense, i.e., Tc is invertible, Ts,00 + Ts,11 > 1 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 F.
Theorem 2. Assume that the dataset is balanced (each class has the same amount of samples), and the noise is class-dependent. When the number of classes c ≥ 81, 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; 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-dependent label noise (Cheng et al., 2020), which is easier to handle. After the Class2Simi transformation, the number of dissimilar pairs is (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 a flip from similar to dissimilar and based on it we split a (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 to two classes into a 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.

heading: 3.2 LEARNING WITH NOISY SIMILARITY LABELS
text: In order to learn a multi-class classifier from similarity labeled data, we should establish relationships 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
1In multi-class classification problems, the number of classes is usually bigger than 8 , e.g., MNIST (LeCun, 1998), CIFAR-10, and CIFAR-100 (Krizhevsky et al., 2009).
2, they denote the predicted clean similarity posterior by the inner product between two categorical distributions: Ŝij = f (Xi) > f (Xj). Intuitively, f(X) outputs the predicted categorical distribution of input data X and f(Xi)>f(Xj) can measure how similar the two distributions are. For clarity, we visualize the predicted similarity posterior in Figure 3. If Xi and Xj are predicted belonging to the same class, i.e., argmaxm∈C fm(Xi) = argmaxn∈C fn(Xj), the predicted similarity posterior should be relatively high (Ŝij = 0.30 in Figure 3(a)). By contrast, if Xi and Xj are predicted belonging to different classes, the predicted similarity posterior should be relatively low (Ŝij = 0.0654 in Figure 3(b)). Note that the noisy similarity posterior distribution P (H̄ij |Xi, Xj) and clean similarity posterior distribution P (Hij |Xi, Xj) satisfy
P (H̄ij |Xi, Xj) = T>s P (Hij |Xi, Xj). (1)
Therefore, we can infer noisy similarity posterior ˆ̄Sij from clean similarity posterior Ŝij with the similarity noise transition matrix. To measure the error between the predicted noisy similarity posterior ˆ̄Sij and noisy similarity label H̄ij , we employ a binary cross-entropy loss function (Shannon, 1948). The final optimization function is
Lc2s(H̄ij , ˆ̄Sij) = − ∑ i,j H̄ij log ˆ̄Sij + (1− H̄ij) log(1− ˆ̄Sij). (2)
The pipeline of the proposed Class2Simi is summarized in Figure 2. The softmax function outputs an estimation for the clean class posterior, i.e., f(X) = P̂ (Y |X), 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 Ŝij of every two instances. According to Equation 1, by pre-multiplying the transpose of the noise similarity transition matrix, we can obtain the predicted noisy similarity posterior ˆ̄Sij . Therefore, by minimizing Lc2s, we can learn a 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.

heading: 3.3 IMPLEMENTATION
text: 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, we read a batch of n examples, and generate their corresponding n2 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 a
Algorithm 1 Class2Simi Input: training data with noisy class labels; validation data with noisy class labels. Stage 1: Learn T̂s 1: Learn g(X) = P̂ (Ȳ |X) by training data with noisy class labels, and save the model for Stage 2; 2: Estimate T̂c following the optimization method in (Patrini et al., 2017); 3: Transform T̂c to T̂s. 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 n single examples in the batch of data. After that pairwise enumeration layer calculates the inner products between every two instances, outputting n2 predicted similarity posterior probabilities. Then the similarity transition matrix corrects the n2 predicted similarity posterior probabilities. Finally, the loss is accumulated by n2 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.

heading: 3.4 GENERALIZATION ERROR
text: 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(f) = E(Xi,Xj ,Ȳi,Ȳj ,H̄ij ,Ts)∼Dρ [`(f(Xi), f(Xj), Ts, H̄ij)], (3)
and
Rn(f) = 1
n2 n∑ i=1 n∑ j=1 `(f(Xi), f(Xj), Ts, H̄ij), (4)
where n is training sample size of the noisy data. Assume that the neural network has d layers with parameter matrices W1, . . . ,Wd, and the activation functions σ1, . . . , σd−1 are Lipschitz continuous, satisfying σj(0) = 0. We denote by H : X 7→ Wdσd−1(Wd−1σd−2(. . . σ1(W1X))) ∈ R the standard form of the neural network. H = argmaxi∈{1,...,C} hi. Then the output of the softmax function is defined as fi(X) = exp (hi(X))/ ∑C j=1 exp (hj(X)), i = 1, . . . , C. We can obtain the following generalization error bound as follow. Theorem 3. Assume the parameter matricesW1, . . . ,Wd have Frobenius norm at mostM1, . . . ,Md, and the activation functions are 1-Lipschitz, positive-homogeneous, and applied element-wise (such as the ReLU). Assume the transition matrix is given, and the instances X are upper bounded by B, i.e., ‖X‖ ≤ B for all X , and the loss function ` is upper bounded by M 2. Then, for any δ > 0, with probability at least 1− δ,
R(f̂)−Rn(f̂) ≤ (Ts,11 − Ts,01)2BC(
√ 2d log 2 + 1)Πdi=1Mi
Ts,11 √ n
+M
√ log 1/δ
2n . (5)
Notation and a detailed proof are provided in Appendix C.
Theorem 3 implies that if the training error is small and the training sample size is large, the expected risk R(f̂) of the representations for noisy similarity posterior will be small. If the transition matrix is well estimated, the clean similarity posterior as well as the classifier for the clean class will also have a small risk according to Equation 1 and the Class2Simi relations. This theoretically justifies why the proposed method works well. In the experiment section, we will show that the transition matrices are well estimated and that the proposed method significantly outperforms the baselines.
In Class2Simi, a multi-class classification is reduced to a pairwise binary classification. For pairwise examples, if a surrogate loss is classification-calibrated, minimizing it leads to minimizing the zeroone loss on the pointwise random variables in the limit case. Otherwise, we cannot guarantee the
2The 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.
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 c = 2, a good model for predicting similar/dissimilar pairs must also be a good model for predicting the original classes, under mild assumptions. In practice, it seems fine to use non-classification-calibrated losses. According to Tewari & Bartlett (2007), the multi-class margin loss (i.e., one-vs-rest loss) and the pairwise comparison loss (i.e., one-vs-one loss) are proved to be non-calibrated, but they are still the main multi-class losses in Mohri et al. (2018); Shalev-Shwartz & Ben-David (2014).

heading: 4 EXPERIMENTS
text: Datasets. We employ three widely used image datasets, i.e., MNIST (LeCun, 1998), CIFAR-10, and CIFAR-100 (Krizhevsky et al., 2009), one text dataset News20, and one real-world noisy dataset Clothing1M (Xiao et al., 2015). MNIST has 28× 28 grayscale images of 10 classes including 60,000 training images and 10,000 test images. CIFAR-10 and CIFAR-100 both have 32 × 32 × 3 color
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. Clothing1M has 1M images with real-world 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 a noisy class, if most instances in it belong to another specific class, we can hardly identify it. For example, assume that a class with noisy labels ī contains ni instances with ground-truth labels i and nj instances with ground-truth labels j. If nj is bigger than ni, the model will cluster class i into j. Unfortunately, in Clothing1M, most instances with label ‘5’ belong to class ‘3’ actually. Therefore, we merge the two classes, and denote the fixed dataset by Clothing1M* 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 Tc,ij . 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 -based methods, i.e., 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 to 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 et al., 1998). For CIFAR-10, we use ResNet-32 with pre-activation (He et al., 2016b). For CIFAR-100, we use ResNet-56 with pre-activation (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 Clothing1M*, we use pre-trained ResNet-50 (He et al., 2016a). We use the same optimization method as Forward correction to learn the noise transition matrix T̂c. 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-10, the batch size is also 128 and the learning rate decays every 40 epochs by a factor of 0.1 with 120 epochs in total. On CIFAR-100, the batch size is 1000 and the learning rate drops at epoch 80 and 160 by a 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 Clothing1M*, 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 1 and Figure 4 demonstrate that Class2Simi achieves distinguished classification accuracy and is 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 a 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-0.5, Forward & Class2Simi maintains remarkable accuracy above 98.20% while the accuracy of Forward decreases steadily. On CIFAR100, there are obvious decreases in the accuracy of all methods and our method achieves the best results across all noise rate, i.e., 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 Tc through multiplying every element in class Tc by a random variable αij . We control the noise rate on the Tc by sampling αij in different intervals, i.e., 0.1 noise means that αij is uniformly sampled from ±[1.1, 1.2]. Then we normalize Tc to make its row sums equal to 1. From Figure 4, we can see that the accuracy of Forward drops dramatically with the increase of the noise on Tc on three datasets. Meanwhile, there is only a slight fluctuation of Forward & Class2Simi on MNIST
and CIFAR10. On CIFAR100, the accuracy of Forward & Class2Simi is affected by the noise on Tc, 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 is large.
Results on noisy text dataset. Results in Table 2 show that the proposed strategy works well on the text dataset under both symmetric and asymmetric noise settings.
Results on real-world noisy dataset. Results in Table 3 show that the proposed strategy significantly improves the classification accuracy of the T -based methods. T -based methods with Class2Simi also outperform those classic methods.
Ablation study. To investigate how the similarity loss function influences the classification accuracy, we conduct experiments with the cross-entropy loss function and the similarity loss function respectively on clean datasets over 3 trails where the Tc is set to an identity matrix. All other settings are kept the same. As shown in Table 4, the similarity loss function does not improve the classification accuracy, which means the accuracy increase in our paper is benefited from the lower noise rate and the more robust transition matrix.

heading: 5 CONCLUSION
text: This paper proposes a new perspective on dealing with class label noise (called Class2Simi) by transforming the training sample with noisy class labels into a training sample with noisy similarity labels. We also propose a 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.

heading: A PROOF OF THEOREM 1
text: Theorem 1. Assume that the dataset is balanced (each class has the same amount of samples, and c classes in total), and the noise is class-dependent. Given a class noise transition matrix Tc, such that Tc,ij = P (Ȳ = j|Y = i). The elements of the corresponding similarity noise transition matrix Ts can be calculated as
Ts,00 = c2 − c−
(∑ j( ∑ i Tc,ij) 2 − ||Tc||2Fro )
c2 − c , Ts,01 =
∑ j( ∑ i Tc,ij)
2 − ||Tc||2Fro c2 − c ,
Ts,10 = c− ||Tc||2Fro
c , Ts,11 = ||Tc||2Fro c .
Proof. Assume each class has n samples. n2Tc,ijTc,i′j′ represents the number of sample-pairs generated by (Ȳ = j|Y = i) and (Ȳ = j′|Y = i′). For the first element Ts,00, n2 ∑ i 6=i′ Tc,ijTc,i′j′
is the number of sample-pairs with clean similarity labels H = 0, while n2 ∑ i6=i′,j 6=j′ Tc,ijTc,i′j′ is the number of example-pairs with clean similarity labels S = 0 and noisy similarity labels H̄ = 0. 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 as follows,
Ts,00 = ∑ i6=i′,j 6=j′ Tc,ijTc,i′j′∑ i 6=i′ Tc,ijTc,i′j′ , Ts,01 = ∑ i 6=i′,j=j′ Tc,ijTc,i′j′∑ i 6=i′ Tc,ijTc,i′j′ ,
Ts,10 = ∑ i=i′,j 6=j′ Tc,ijTc,i′j′∑ i=i′ Tc,ijTc,i′j′ , Ts,11 = ∑ i=i′,j=j′ Tc,ijTc,i′j′∑ i=i′ Tc,ijTc,i′j′ .
Further, note that∑ i=i′ Tc,i,jTc,i′,j′ = ∑ i,j,j′ Tc,i,jTc,i,j′ = ∑ i ( ∑ j Tc,i,j)( ∑ j′
Tc,i,j′) = c,∑ i 6=i′ Tc,i,jTc,i′,j′ = ∑ i 6=i′,j,j′ Tc,i,jTc,i′,j′ = ∑ i 6=i′ ( ∑ j Tc,i,j)( ∑ j′
Tc,i,j′) = (c− 1)c,∑ i=i′,j=j′
Tc,ijTc,i′j′ = ||Tc||2Fro,∑ i 6=i′,j=j′ Tc,ijTc,i′j′ = ∑ j ( ∑ i Tc,ij) 2 − ||Tc||2Fro.
Substituting above four equations to the primal representations, we have the Theorem 1 proved.

heading: B PROOF OF THEOREM 2
text: Theorem 2. Assume that the dataset is balanced (each class has the same amount of samples), and the noise is class-dependent. When the number of classes c ≥ 8, the noise rate for the noisy similarity labels is lower than that of the noisy class labels.
Proof. Assume each class has n samples. As we state in the proof of Theorem 1, the number of example-pairs with clean similarity labels H = 0 and noisy similarity labels H̄ = 0 is n2 ∑ i 6=i′,j 6=j′ Tc,ijTc,i′j′ . We denote it by N00. Similarly, we have,
N00 = n 2 ∑
i6=i′,j 6=j′ Tc,ijTc,i′j′ , N01 = n
2 ∑
i 6=i′,j=j′ Tc,ijTc,i′j′ ,
N10 = n 2 ∑
i=i′,j 6=j′ Tc,ijTc,i′j′ , N11 = n
2 ∑
i=i′,j=j′
Tc,ijTc,i′j′ .
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
Snoise = N01 +N10 N00 +N01 +N10 +N11 = N01 +N10 c2n2 ,
Cnoise = n ∑ i6=j Tc,ij
cn .
Let Snoise minus Cnoise, we have Snoise − Cnoise = n2 ∑ i 6=i′,j=j′ Tc,ijTc,i′j′ + n 2 ∑ i=i′,j 6=j′ Tc,ijTc,i′j′ c2n2 − n ∑ i6=j Tc,ij cn
=
∑ i6=i′,j=j′ Tc,ijTc,i′j′ + ∑ i=i′,j 6=j′ Tc,ijTc,i′j′ − c ∑ i 6=j Tc,ij
c2 .
Let A = ∑ i 6=i′,j=j′ Tc,ijTc,i′j′ + ∑ i=i′,j 6=j′ Tc,ijTc,i′j′ − c ∑ i 6=j Tc,ij , we have
A = ∑
i6=i′,j=j′ Tc,ijTc,i′j′ + ∑ i=i′,j 6=j′ Tc,ijTc,i′j′ − c ∑ i 6=j Tc,ij
= ∑
i6=i′,j=j′ Tc,ijTc,i′j′ + ∑ i=i′,j 6=j′ Tc,ijTc,i′j′ − c( ∑ i,j Tc,ij − ∑ i=j Tc,ij)
= ∑
i6=i′,j=j′ Tc,ijTc,i′j′ + ∑ i=i′,j 6=j′ Tc,ijTc,i′j′ − c2 + c ∑ i=j Tc,ij .
The second equation holds because the row sum of Tc is 1. For the first term ∑ i 6=i′,j=j′ Tc,ijTc,i′j′ , notice that:∑ i6=i′,j=j′ Tc,ijTc,i′j′ = ∑ j ∑ i Tc,ij( ∑ i′ 6=i Tc,i′j)
= ∑ j ∑ i Tc,ij( ∑ i′ 6=i Tc,i′j + Tc,ij − Tc,ij)
= ∑ j ∑ i Tc,ij( ∑ i′ Tc,i′j − Tc,ij)
= ∑ j ∑ i Tc,ij(Sj − Tc,ij) (Sj is the column sum of the j − th column)
= ∑ j ∑ i Tc,ijSj − T 2c,ij
= ∑ j Sj ∑ i Tc,ij − ∑ j ∑ i T 2c,ij
= ∑ j S2j − ∑ j ∑ i T 2c,ij . (6)
Due to the symmetry of i and j, for the second term ∑ i=i′,j 6=j′ Tc,ijTc,i′j′ , we have∑ i=i′,j 6=j′ Tc,ijTc,i′j′ = ∑ j ∑ i Tc,ij(Ri − Tc,ij) (Ri is the row sum of the i− th row, and Ri = 1)
= ∑ j ∑ i Tc,ij − T 2c,ij
= c− ∑ j ∑ i T 2c,ij . (7)
Therefore, substituting Equation (6) and (7) into A, we have A = ∑ j S2j − ∑ j ∑ i T 2c,ij + c− ∑ j ∑ i T 2c,ij − c2 + c ∑ i=j Tc,ij .
To prove Snoise − Cnoise ≤ 0 is equivalent to prove A ≤ 0. Let M = c2 − c, N = ∑ j S 2 j − 2 ∑ j ∑ i T 2 ij + c ∑ i=j Tij (we drop the subscript c in Tc,ij), 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 c ≥ 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 l, which are not in j, k − th columns, to the diagonal element. We have
Na −No = (Si + Til)2 + (Sl + Til)2 + cTil − 2(Tii + Til)2 − S2i − S2l + 2(T 2ii + T 2il) = Til(2Til + 2Si − 2Sl + c− 4Tii) ≥ Til(2Til − 2Sl + c− 2Tii) (∵ Si ≥ Tii) > Til(2Til − c+ 2 + c− 2Tii) (∵ Sl < c/2− 1) ≥ 0. (∵ Tii ≤ 1)
We do such adjustment to every rows, thenNa 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, Sj + Sk < 2c/3 + 2/3 (because for i 6= j, k, Tij + Tik < 2/3). Assume that the column sum of k − th column is no bigger than that of the j − th column, and thus Sk < c/3 + 1/3. Then, for a row i, we add the Tik to Tii. We have
Na −No = (Si + Tik)2 + (Sk + Tik)2 + cTik − 2(Tii + Tik)2 − S2i − S2k + 2(T 2ii + T 2ik) = Tik(2Tik + 2Si − 2Sk + c− 4Tii) ≥ Tik(2Tik − 2Sk + c− 2Tii) (∵ Si ≥ Tii) > Tik(2Tik + c/3− 2/3− 2Tii) (∵ Sk < c/3 + 1/3) ≥ 0. (∵ c ≥ 8, and Tii ≤ 1)
We do such adjustment to every rows, then Na 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 c− 1 columns as above and then obtain the final matrix as well. If there is no column with a column sum bigger than c/2− 1, we can adjust all the elements as above and then obtain a unit matrix. For the unit matrix, A = N −M < Na −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 Tij by bi and Tii by ai, for i = {1, . . . , c− 1}. We have
Na = ∑ i a2i + (1 + ∑ i bi) 2 + c( ∑ i ai + 1)− 2( ∑ i a2i + ∑ i b2i + 1)
= (1 + ∑ i bi) 2 + c ∑ i ai + c− ∑ i a2i − 2 ∑ i b2i − 2
= 1 + ( ∑ i bi) 2 + 2 ∑ i bi + c ∑ i ai + c− ∑ i a2i − 2 ∑ i b2i − 2
= ( ∑ i bi) 2 + 2 ∑ i bi − 2 ∑ i b2i + c ∑ i ai − ∑ i a2i + c− 1
= ( ∑ i bi) 2 + 2 ∑ i bi − 2 ∑ i b2i + c ∑ i (1− bi)− ∑ i (1− bi)2 + c− 1
= ( ∑ i bi) 2 + 2 ∑ i bi − 2 ∑ i b2i + c 2 − c− c ∑ i bi − ∑ i (1− 2bi + b2i ) + c− 1
= ( ∑ i bi) 2 + 4 ∑ i bi − 3 ∑ i b2i − c ∑ i bi + c 2 − c.
Now we prove A = N −M ≤ Na −M ≤ 0. Note that
Na −M = ( ∑ i bi) 2 + 4 ∑ i bi − 3 ∑ i b2i − c ∑ i bi
= ( ∑ i bi) 2 + 3 ∑ i bi − 3 ∑ i b2i − (c− 1) ∑ i bi
= ( ∑ i bi) 2 + 3 ∑ i bi − 3 ∑ i b2i − ( ∑ i (1− bi) + ∑ i bi) ∑ i bi
= 3 ∑ i bi − 3 ∑ i b2i − ∑ i (1− bi) ∑ i bi
= 3 ∑ i bi(1− bi)− ∑ i (1− bi) ∑ i bi.
According to the rearrangement inequality(Hardy et al., 1952), we have∑ i (1− bi) ∑ i bi ≥ (c− 1) ∑ i bi(1− bi).
Note that c ≥ 8, thus 3 ∑ i bi(1−bi)− ∑ i(1−bi) ∑ i bi ≤ 0, andA ≤ 0. Therefore Snoise−Cnoise ≤ 0, 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 is one column in the Tc, of which every elements are 1, and the rest elements of the Tc are 0). Above two extreme situations are not considered in this paper. Namely, the noise rate of the noisy similarity labels is lower than that of the noisy class labels. Theorem 2 is proved.

heading: C PROOF OF THEOREM 3
text: Theorem 3. Assume the parameter matricesW1, . . . ,Wd have Frobenius norm at mostM1, . . . ,Md, and the activation functions are 1-Lipschitz, positive-homogeneous, and applied element-wise (such as the ReLU). Assume the transition matrix is given, and the instances X are upper bounded by B, i.e., ‖X‖ ≤ B for all X , and the loss function ` is upper bounded by M 3. Then, for any δ > 0, with probability at least 1− δ,
R(f̂)−Rn(f̂) ≤ (Ts,11 − Ts,01)2BC(
√ 2d log 2 + 1)Πdi=1Mi
Ts,11 √ n
+M
√ log 1/δ
2n . (8)
Proof. We have defined
R(f) = E(Xi,Xj ,Ȳi,Ȳj ,H̄ij ,Ts)∼Dρ [`(f(Xi), f(Xj), Ts, H̄ij)], (9)
and
Rn(f) = 1
n2 n∑ i=1 n∑ j=1 `(f(Xi), f(Xj), Ts, H̄ij), (10)
where n is training sample size of the noisy data.
First, we bound the generalization error with Rademacher complexity (Bartlett & Mendelson, 2002).
Theorem 4 (Bartlett & Mendelson (2002)). Let the loss function be upper bounded by M . Then, for any δ > 0, with the probability 1− δ, we have
sup f∈F |R(f)−Rn(f)| ≤ 2Rn(` ◦ F) +M
√ log 1/δ
2n , (11)
3The 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.
where Rn(` ◦ F) is the Rademacher complexity defined by
Rn(` ◦ F) = E [ sup f∈F 1 n n∑ i=1 σi`(f(Xi), f(Xj), Ts, H̄ij) ] , (12)
and {σ1, · · · , σn} are Rademacher variables uniformly distributed from {−1, 1}.
Before further upper bound the Rademacher complexity Rn(` ◦ F), we discuss the special loss function and its Lipschitz continuity w.r.t hk(Xi), k = {1, . . . , C}.
Lemma 1. Given similarity transition matrix Ts, loss function `(f(Xi), f(Xj), Ts, H̄ij) is µLipschitz with respect to hk(Xi), k = {1, . . . , C}, and µ = (Ts,11 − Ts,01)/Ts,11∣∣∣∣∂`(f(Xi), f(Xj), Ts, H̄ij)∂hk(Xi)
∣∣∣∣ < Ts,11 − Ts,01Ts,11 . (13) Detailed proof of Lemma 1 can be found in Section C.1.
Lemma 1 shows that the loss function is µ-Lipschitz with respect to hk(Xi), k = {1, . . . , C}. Based on Lemma 1, we can further upper bound the Rademacher complexity Rn(` ◦ F) by the following lemma.
Lemma 2. Given similarity transition matrix Ts and assume that loss function `(f(Xi), f(Xj), Ts, H̄ij) is µ-Lipschitz with respect to hk(Xi), k = {1, . . . , C}, we have
Rn(` ◦ F) = E [ sup f∈F 1 n n∑ i=1 σi`(f(Xi), f(Xj), Ts, H̄ij) ]
≤ µCE [ sup h∈H 1 n n∑ i=1 σih(Xi) ] , (14)
where H 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 W1, . . . ,Wd are at most M1, . . . ,Md. Let the activation functions be 1-Lipschitz, positive-homogeneous, and applied element-wise (such as the ReLU). Let X is upper bounded by B, i.e., for any X , ‖X‖ ≤ B. Then,
E [ sup h∈H 1 n n∑ i=1 σih(Xi) ] ≤ B( √ 2d log 2 + 1)Πdi=1Mi√ n . (15)
Combining Lemma 1,2, and Theorem 4, 5, Theorem 3 is proved.
C.1 PROOF OF LEMMA 1
Recall that
`(f(Xi), f(Xj), Ts, H̄ij = 1) = − log( ˆ̄Sij) = − log(Ŝij × Ts,11 + (1− Ŝij)× Ts,01) = − log(f(Xi)>f(Xj)× Ts,11 + (1− f(Xi)>f(Xj))× Ts,01),
(16)
where
f(Xi) = [f1(Xi), . . . , fc(Xi)] >
= [( exp(h1(X))∑c k=1 exp(hk(X)) ) , . . . , ( exp(hc(X))∑c k=1 exp(hk(X)) )]> . (17)
Take the derivative of `(f(Xi), f(Xj), Ts, H̄ij = 1) w.r.t. hk(Xi), we have
∂`(f(Xi), f(Xj), Ts, H̄ij = 1) ∂hk(Xi) = ∂`(f(Xi), f(Xj), Ts, H̄ij = 1)
∂ ˆ̄Sij
[ ∂f(Xi) ∂hk(Xi) ]> ∂ ˆ̄Sij ∂f(Xi) , (18)
where
∂`(f(Xi), f(Xj), Ts, H̄ij = 1) ∂ ˆ̄Sij = − 1 f(Xi)>f(Xj)× Ts,11 + (1− f(Xi)>f(Xj))× Ts,01 ,
∂ ˆ̄Sij ∂f(Xi) = f(Xj)× Ts,11 − f(Xj)× Ts,01,
∂f(Xi)
∂hk(Xi) = f ′(Xi) = [f ′ 1(Xi), . . . , f ′ c(Xi)] >.
Note that the derivative of the softmax function has some properties, i.e., if m 6= k, f ′m(Xi) = −fm(Xi)fk(Xi) and if m = k, f ′k(Xi) = (1− fk(Xi))fk(Xi). We denote by V ectorm the m − th element in V ector for those complex vectors. Because 0 < fm(Xi) < 1,∀m ∈ {1, . . . , c}, we have
f ′m(Xi) ≤ |f ′m(Xi)| < fm(Xi), ∀m ∈ {1, . . . , c}; (19) f ′(Xi) >f(Xj) < f(Xi) >f(Xj). (20)
Therefore,∣∣∣∣∂`(f(Xi), f(Xj), Ts, H̄ij = 1)∂hk(Xi) ∣∣∣∣ = ∣∣∣∣∣∂`(f(Xi), f(Xj), Ts, H̄ij = 1)∂ ˆ̄Sij [ ∂f(Xi) ∂hk(Xi) ]> ∂ ˆ̄Sij ∂f(Xi) ∣∣∣∣∣ =
∣∣∣∣ f ′(Xi)>f(Xj)× Ts,11 − f ′(Xi)>f(Xj)× Ts,01f(Xi)>f(Xj)× Ts,11 + (1− f(Xi)>f(Xj))× Ts,01 ∣∣∣∣
< ∣∣∣∣ f(Xi)>f(Xj)× Ts,11 − f(Xi)>f(Xj)× Ts,01f(Xi)>f(Xj)× Ts,11 + (1− f(Xi)>f(Xj))× Ts,01 ∣∣∣∣
< ∣∣∣∣Ts,11 − Ts,01Ts,11 ∣∣∣∣ = Ts,11 − Ts,01
Ts,11 . (21)
The second inequality holds because of Ts,11 > Ts,01 (Detailed proof can be found in Section C.1.1) and Equation (20). The third inequality holds because of f(Xi)>f(Xj) < 1.
Similarly, we can prove ∣∣∣∣∂`(f(Xi), f(Xj), Ts, H̄ij = 0)∂hk(Xi) ∣∣∣∣ < Ts,11 − Ts,01Ts,11 . (22)
Combining Equation (21) and Equation (22), we obtain∣∣∣∣∂`(f(Xi), f(Xj), Ts, H̄ij)∂hk(Xi) ∣∣∣∣ < Ts,11 − Ts,01Ts,11 . (23)
C.1.1 PROOF OF Ts,11 > Ts,01
As we mentioned in Section B, we have, N00 = n 2 ∑
i 6=i′,j 6=j′ Tc,ijTc,i′j′ , N01 = n
2 ∑
i 6=i′,j=j′ Tc,ijTc,i′j′ ,
N10 = n 2 ∑
i=i′,j 6=j′ Tc,ijTc,i′j′ , N11 = n
2 ∑
i=i′,j=j′
Tc,ijTc,i′j′ ,
Ts,01 = N01
N00 +N01 , Ts,11 = N11 N10 +N11 ,
Ts,11 − Ts,01 = N11N00 +N11N01 −N01N10 −N01N11
(N00 +N01)(N10 +N11) .
Let us review the definition of similarity labels: if two instances belong to the same class, they will have similarity label S = 1, otherwise S = 0. That is to say, for a k-class dataset, only 1k of similarity data has similarity labels S = 1, and the rest 1 − 1k has similarity labels S = 0. We denote the number of data with similarity labels S = 1 by N1, otherwise N0. Therefore, for the balanced dataset with n samples of each class, N1 = cn2, and N0 = c(c− 1)n2. Let A = Ts,11 − Ts,01, we have
A = N11N00 −N01N10 = N11N00 − (N0 −N00)(N1 −N11) = N11N00 −N0N1 −N11N00 +N11N0 +N1N00 = N11N0 −N01N1 = c(c− 1)n2N11 − cn2N01 > 0.
The last equation holds because of (c− 1)N11 −N01 > 0 according to the rearrangement inequality (Hardy et al., 1952).
C.2 PROOF OF LEMMA 2
E [ sup f∈F 1 n n∑ i=1 σi`(f(Xi), f(Xj), Ts, H̄ij) ]
= E [ sup g 1 n n∑ i=1 σi`(f(Xi), f(Xj), Ts, H̄ij) ]
= E [ sup
argmax{h1,...,hC}
1
n n∑ i=1 σi`(f(Xi), f(Xj), Ts, H̄ij)
]
= E [ sup
max{h1,...,hC}
1
n n∑ i=1 σi`(f(Xi), f(Xj), Ts, H̄ij)
]
≤ E [ C∑ k=1 sup hk∈H 1 n n∑ i=1 σi`(f(Xi), f(Xj), Ts, H̄ij) ]
= C∑ k=1 E [ sup hk∈H 1 n n∑ i=1 σi`(f(Xi), f(Xj), Ts, H̄ij) ]
≤ µCE [ sup hk∈H 1 n n∑ i=1 σihk(Xi) ]
= µCE [ sup h∈H 1 n n∑ i=1 σih(Xi) ] ,
where the first three equations hold because given Ts, f and max{h1, . . . , hC} give the same constraint on hj(Xi), j = {1, . . . , C}; the sixth inequality holds because of the Talagrand Contraction Lemma (Ledoux & Talagrand, 2013).

heading: D DEFINITION OF NOISE SETTINGS
text: Symmetric noise setting is defined as follows, where C is the number of classes.
Sym-ρ: T =  1− ρ ρC−1 . . .
ρ C−1
ρ C−1
ρ C−1 1− ρ ρ C−1 . . .
ρ C−1
... . . . ... ρ
C−1 . . . ρ C−1 1− ρ ρ
C−1 ρ
C−1 ρ C−1 . . . ρ C−1 1− ρ
 . (24)
The 0.3 asymmetric noise setting is set as follow,
1 def asym_transition_matrix_generate(noise_rate=0.3, num_classes=10, seed=1): 2 np.random.seed(seed) 3 t = np.random.rand(num_classes, num_classes) 4 i = np.eye(num_classes) 5 t = t + 1.2 * num_classes * i 6 for a in range(num_classes): 7 t[a] = t[a] / t[a].sum() 8
9 return t 10
Listing 1: Asymmetric noise (transition matrix) generation.

heading: E EXPERIMENTS
text: E.1 GIVEN GROUND-TRUTH CLASS Tc
From Figure 5, overall, we can see that Class2Simi (Class2Simi TrueT) achieves the best performance whenever class Tc is given or estimated. In most cases, Class2Simi with estimated Tc 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 rate increases from Sym-0.1 to Sym-0.5, Class2Simi TrueT maintains remarkable accuracy above 99.20% while the accuracy of Class2Simi and Forward TrueT decrease steadily. However, there is a significant decrease in the accuracy of Forward. On CIFAR10, the patterns of varying tendencies of four curves are similar to that of MNIST except that the decreases are more dramatic and even Class2Simi TrueT drops slightly at Sym-0.5. On CIFAR100, there is an obvious decrease in the accuracy of all methods and our method achieves the best results across all noise rate, i.e., at Sym-0.5, Class2Simi gives an accuracy uplift of about 8.0% compared with Forward.
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 is set to 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, CIFAR10 and CIFAR100, our method can achieve the same accuracy as Forward.
E.3 RESULTS ON ASYMMETRIC NOISE SETTING
In Table 5, we demonstrate the effectiveness of our method under the asymmetric noise setting.

heading: F LEARNABILTY CONNECTION BETWEEN PAIRWISE CLASSIFICATION AND POINTWISE CLASSIFICATION
text: F.1 Pointwise IMPLIES pairwise
For an invertible Tc, denote by vj the j-th column of Tc and 1 the all-one vector. Then,∑ j ( ∑ i Tc,ij) 2 = ∑ j 〈vj ,1〉2 ≤ ∑ j ||vj ||2||1||2 = c||Tc||2Fro,
where we use the Cauchy–Schwarz inequality (Steele, 2004) in the second step. Further, we have
Ts,11 + Ts,00 = ||Tc||2Fro c + c2 − c−
(∑ j( ∑ i Tc,ij) 2 − ||Tc||2Fro )
c2 − c
= (c− 1)||Tc||2Fro + c2 − c−
(∑ j( ∑ i Tc,ij) 2 − ||Tc||2Fro )
c2 − c
= (c− 1)||Tc||2Fro + c2 − c−
(∑ j〈vj ,1〉2 − ||Tc||2Fro ) c2 − c
≥ (c− 1)||Tc||2Fro + c2 − c−
( c||Tc||2Fro − ||Tc||2Fro ) c2 − c
= 1.
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, a singular Tc of the pair noise pattern and the transformed Ts are shown as follows,
Tc =  0.5 0.5 . . . 0 0 0 0.5 0.5 . . . 0 ... . . . ...
0 . . . 0 0.5 0.5 0.5 0 . . . 0 0.5
 , Ts = [ 0.95 0.05 0.50 0.50 ] .
In this case, the reduced pairwise classification is learnable while the original pointwise classification is not learnable.
Thus the learnability of the reduced pairwise classification does not imply the learnability of the pointwise classification.

Review summaries:
The 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. 

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.

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).