Learning with Symmetric Label Noise: The Importance of Being Unhinged
Convex potential minimisation is the de facto approach to binary classification. However, Long and Servedio [2010]  proved that under symmetric label noise (SLN), minimisation of any convex potential over a linear function class can result in classification performance equivalent to random guessing. This ostensibly shows that convex losses are not SLN-robust. In this paper, we propose a convex, classification-calibrated loss and prove that it is SLN-robust. The loss avoids the Long and Servedio [2010]  result by virtue of being negatively unbounded. The loss is a modification of the hinge loss, where one does not clamp at zero; hence, we call it the unhinged loss. We show that the optimal unhinged solution is equivalent to that of a strongly regularised SVM, and is the limiting solution for any convex potential; this implies that strong 2 regularisation makes most standard learners SLN-robust. Experiments confirm the unhinged loss' SLN-robustness is borne out in practice. So, with apologies to Wilde [1895], while the truth is rarely pure, it can be simple.
SUMMARYThe paper presents a solution to binary classification with symmetric label noise (SLN). They show that, in order to obtain consistency (w.r.t. to the 0-1 loss in the "noiseless" case) while using a convex surrogate, one must use the loss $\ell(v,y) = 1 - vy$ -- the "unhinged loss" -- , which is shown to enjoy some useful properties, including robustness to SLN. In a more restricted sense of robustness, it is the only such loss, but in any case it overcomes the limitations of other convex losses for the same problem.Different implications of using the unhinged loss are discussed; the problem of classification with SLN with the unhinged loss and "linear" classifiers is investigated and solved analytically. The authors also present an empirical evaluation to motivate that their theoretical considerations have practical impact. CONTRIBUTIONSThe main contribution is an SLN-robust loss (consistent in spite of label noise), and a demonstration that this function enjoys certain properties that make it suitable for classification with SLN, including with linear classifiers.The contributions are relevant for the problem of classification with SLN; they have limited scope outside the problem, which in this reviewer's opinion somewhat specific, but at the same time they address the it effectively and describe a clear-cut solution for the problem. SUPPORTThe support for the contributions is adequate. The results are clearly stated and the proofs are correct easy to follow. The illustrative empirical support of the theoretical results is also suitable, and may shed light on the finite-sample behavior of minimizers of SLN robust losses. TECHNICAL QUALITYThe paper is technically sound and well-executed.A discussion of the limitations of strong SLN robustness (as opposed to SLN robustness) would be informative, as would a discussion about the limitations of the SLN problem as a model for other problems would (though somewhat non-central).More considerations about the finite-sample behavior of minimizers of the unhinged loss would strengthen the discussion of the empirical results. ORIGINALITYThe work is well-placed in the literature, the results well-connected to existing ones, and contributions, novel. CLARITYThe paper is well written and easy to read. The different facts about the unhinged loss are brought together cohesively.Considering binary classification problems in general, the problem of classification with SLN is presented as more realistic than the general case, but this reviewer would appreciate some more motivation as to why one believes so (see detailed comments). (Appendix B.1 seems to briefly touch on this matter.) Perhaps SLN robustness is a step towards robustness to some types of outliers? FOR THE REBUTTALI would appreciate if the authors could give a brief motivation on SLN problems, and their importance in a more general binary classification context. DETAILED COMMENTSI am a bit confused as to the motivation behind SLN. On the one hand, in two dimensions it would be odd to just flip classes uniformly over the space. On the other hand, maybe this behavior in higher dimensions is not too strange and makes sense to be considered. Are there any practical issues motivating the interest in SLN (applications, robustness, etc.), or if the interest is of theoretical nature?Although the loss is unhinged, unboundedness is dealt with by bounding the scores. This essentially turns the unhinged loss into a hinge loss again. I would suggest looking into [1,2], from which we can infer that with $\mathcal{F} = \mathbb{R}^{[-1,1]}$ the hinge and unhinged losses are equivalent and, by a scaling argument, that so are the unhinged and the "scaled" hinge $f(v) = (1 + v/B)_+$ with $\mathcal{F} = \mathbb{R}^{[-B,B]}$. In terms of regret/excess risk (i.e., ignoring constants added to the losses) one can also obtain equivalence with $f(v) = \frac{1}{B}(1 + v)_+$. These results can be used to even obtain tight risk bounds with calibration functions [3].Regarding Conjecture 1 in Appendix B.2, I would point out that linear scorers and (some) proper losses do not go very well together: even in the absence of noise, minimizers of these losses fail to be consistent w.r.t. the best linear classifier in the class [4]. Perhaps the proof techniques used in [4] can provide some directions to develop proofs for Conjecture 1. I would also imagine that Conjecture 1 with linear scorers with $\|w\| \leq C$ for constants $C$ would be quite interesting to investigate.Based on your experimental results, and considering that the theoretical results are asymptotic in nature, can you make any statements about SLN robustness in the finite-sample setting based on your data? REFERENCES[1] Zou, Zhu & Hastie, 2006: "The margin vector, admissible loss and multi-class margin based classifiers" [2] Avila Pires, Szepesvari & Ghavamzadeh, 2013: "Cost-sensitive multiclass classification risk bounds" [3] Steinwart, 2007: "How to compare different loss functions and their risks" [4] Long & Servedio, 2013: "Consistency versus Realizable $H$-Consistency for Multiclass Classification" SUGGESTED FIXES[l:75] "argmin" [l:120-121] "w.r.t." [l:144-145] Your appendix references seem to be broken. [l:234-237]This intuition is compatible with a "graphical" view of the SLN setup, where we would lay out points in space and uniformly flip their labels with a given probability. This also begs the question as to whether this setup is realistic at all, of course, but it makes sense that a classifier should be able to "ignore" large errors introduced by the noise in order to succeed. [l:245] Interestingly, Proposition 5 is also the case for the hinge loss with scaled scores, which is equivalent to the unhinged loss with bounded scores. Note that you instantly get even risk bounds in that case. [l:270] In Proposition 6, you can have R_{01}(s) = B \cdot R_{\ell}(s) (by looking at the minimizers directly). [l:308-311] Because you already have the expectations, you do not need to regularize in the Ridge sense -- I was going to suggest that you can regularize by biasing the centroid estimates, but you already allude to that in the next paragraph. [l:341-347] The statement here seems like a natural consequence of over-regularization. The conclusions you use for SLN robustness are interesting, nonetheless. [l:344-345] $\limsup_{\lambda \rightarrow \infty}$? [l:362] The appendix references are broken here too. [l:445] "$\ell$-risk w.r.t. some convex" [l:480] "any $\rho < \frac{1}{2}$" [l:494] This notation where one integrates out the subscript can be confusing... I would suggest using conditional expectation. [l:514] I believe you need $\alpha \geq 0$. [l:535] $(1 - 2\eta)v + 1$POST-REBUTTAL REMARKSThis paper has the potential to reach a larger audience on account of its proposed algorithm, which the authors should tap. Although SLN has attracted interest from the theoretical and practical points of view, I have the impression that it is too harsh a noise model. Nevertheless, this work is a step in the direction of understanding how to have robustness to noise in classification.The lack of comparison between SLN robustness and its strong counterpart seems to have been a concern in other reviews. While strong SLN robustness ensures that a loss is suitable for classification with SLN, it also restricts the number of such suitable losses. It would be interesting to understand whether how limiting this restriction is.The Appendix carries a relatively large portion of work that may not have been peer-reviwed, but this reviewer verified the proofs (Appendix A).