Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: 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.

Strengths:
- I believe the idea to use pairwise similarity as supervision is novel and interesting, and it is easy to implement.

Weaknesses & Questions:
- 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.
- 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.

[1] Chen, Pengfei, et al. "Understanding and Utilizing Deep Neural Networks Trained with Noisy Labels." International Conference on Machine Learning. 2019.

-----------------------------
Post Rebuttal Modification

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

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

I adjusted my rating from 5 to 1.

-----------------------------
Regarding the authors' 2rd and 3rd responses

First, 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.

Second, 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”.

What’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.

Finally, 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.

Best


review_title: Interesting idea but the analysis is problematic

final_score: rating: 3: Clear rejection
review_content: **Summary**
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. 
In 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. 
The 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.

**Quality**
The 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.

**Clarity**
The 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. 

**Originality**
The 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.

**Significance**
The 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.

**Major technical comments**

*Theory*

1. 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.
2. 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?
3. 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.

*Experiments*

1. 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).
2. 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.
3. the improvements for asymmetric noise, and on MNIST and CIFAR seem marginal. A statistical paired significance test could be useful.

**Minor technical comments**

- 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?
- the similarity label is denoted as $H_{ij}$ in section 3.1but as $S_{i,j}$ in figure 2 and section 3.2.
- what is the difference between samples denoted by $X_i$ in section 3.2 and $x_i$ in section 3.1?
- 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?
- the algorithm defines a function $g(.)$ which is not referred to in the methods section
- where are parameter matrices $W_1,...,W_d$ defined? What is d?
- how is the expected risk $R$ defined? 
- what is $\hat{f}$ 
- what is $R_n$?

**Overall**
While 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.  

**Post Rebuttal**
I 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:

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

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

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

On top of these, the final version of the pdf is still lacking on clarity several instances of which were listed in the original review. 

Thus, considering all the points above leads me to confidently keep the original rating as "clear reject".
review_title: Original and interesting idea but several major concerns regarding clarity, theory, and experiments. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

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

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

-------------------
After rebuttal:
I thank the authors for clarification. I would like to keep with my score.


review_title: The idea is novel. Deeper analysis is needed for experiment.

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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). 

It also provides the generalization bound for the proposed techniques. 
The paper has a strong experimental evaluation of the proposed method against recent models on robust learning with noisy labels. 

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


It 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? 

In 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?

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

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


---------------------
I thank the author for clarification. I would like to be with my score.
review_title: A novel model with good experimental support but marginal technical novelty

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Pros:

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

The authors provide a theoretical analysis of the proposed method to estimate similarity noise transition matrix which makes it more grounded.

The authors have provided sufficient experimental results on multiple datasets to demonstrate effectiveness of the proposed learning technique.

Cons:

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

The 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?

-- post rebuttal --

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


review_title: This work presents a new technique to address noise in labels by converting class labels to similary labels which has been shown to be very effective in noisy environment.

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