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, classificationcalibrated 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 SLN-robustness of the unhinged loss. Binary classification is the canonical supervised learning problem. Given an instance space X, and samples from some distribution D over X × {±1}, the goal is to learn a scorer s : X → R with low misclassification error on future samples drawn from D. Our interest is in the more realistic scenario where the learner observes samples from a distribution D, which is a corruption of D where labels have some constant probability of being flipped. The goal is still to perform well with respect to the unobserved distribution D. This is known as the problem of learning from symmetric label noise (SLN learning) [Angluin and Laird, 1988] . Long and Servedio [2010] proved the following negative result on what is possible in SLN learning: there exists a linearly separable D where, when the learner observes some corruption D with symmetric label noise of any nonzero rate, minimisation of any convex potential over a linear function class results in classification performance on D that is equivalent to random guessing. Ostensibly, this establishes that convex losses are not "SLN-robust" and motivates the use of non-convex losses [Stempfel and Ralaivola, 2009 , Masnadi-Shirazi et al., 2010 , Ding and Vishwanathan, 2010 , Denchev et al., 2012 , Manwani and Sastry, 2013 . In this paper, we propose a convex loss and prove that it is SLN-robust. The loss avoids the result of Long and Servedio [2010] by virtue of being negatively unbounded. The loss is a modification of the hinge loss where one does not clamp at zero; thus, we call it the unhinged loss. We show that this is the unique convex loss (up to scaling and translation) that satisfies a notion of "strong SLN-robustness " (Proposition 4). In addition to being SLN-robust, this loss has several attractive properties, such as being classification-calibrated (Proposition 5), consistent when minimised on the corrupted distribution (Proposition 6), and having an easily computable optimal solution that is the difference of two kernel means (Equation 9). Finally, we show that this optimal solution is equivalent to that of a strongly regularised SVM (Proposition 7), and such a result holds more generally for any twice-differentiable convex potential (Proposition 8), implying that strong 2 regularisation endows most standard learners with SLN-robustness.  Fix an instance space X. We denote by D some distribution over X × {±1}, with random variables (X, Y) ∼ D. Any D may be expressed via the class-conditional distributions (P, Q) = (P(X | Y = 1), P(X | Y = −1)) and base rate π = P(Y = 1), or equivalently via the marginal distribution M = P(X) and classprobability function η : A scorer is any function s : X → R. A loss is any function : {±1} × R → R. We use −1 , 1 to refer to (−1, ·) and is the set of -risks for all scorers in S. A function class is any F ⊆ R X . Given some F, the set of restricted Bayes-optimal scorers for a loss are those scorers in F that minimise the -risk: The set of (unrestricted) Bayes-optimal scorers is S D, * = S D,F, * for F = R X . The restricted -regret of a scorer is its excess risk over that of any restricted Bayes-optimal scorer: Binary classification is concerned with the risk corresponding to the zero-one loss, 01 : (y, v) → yv < 0 +  The problem of learning with symmetric label noise (SLN learning) is the following [Angluin and Laird, 1988 , Kearns, 1998 , Blum and Mitchell, 1998 , Natarajan et al., 2013 . For some notional "clean" distribution D, which we would like to observe, we instead observe samples from some corrupted distribution SLN(D, ρ), for some ρ ∈ [0, 1/2). The distribution SLN(D, ρ) is such that the marginal distribution of instances is unchanged, but each label is independently flipped with probability ρ. The goal is to learn a scorer from these corrupted samples such that L D 01 (s) is small. For any quantity in D, we denote its corrupted counterparts in SLN(D, ρ) with a bar, e.g. M for the corrupted marginal distribution, and η for the corrupted class-probability function; additionally, when ρ is clear from context, we will occasionally refer to SLN(D, ρ) by D. By definition of the corruption process, the corruption marginal distribution M = M , and [Natarajan et al., 2013, Lemma 7]  2 3 SLN-robustness: formalisation For our purposes, a learner ( , F) comprises a loss , and a function class F, with learning being the search for some s ∈ F that minimises the -risk. Informally, the learner ( , F) is "robust" to symmetric label noise (SLN-robust) if minimising over F gives the same classifier on both the clean distribution D, which the learner would like to observe, and SLN(D, ρ) for any ρ ∈ [0, 1/2), which the learner actually observes. We now formalise this notion, and review what is known about the existence of SLN-robust learners. For some fixed instance space X, let ∆ denote the set of distributions on X × {±1}. Given a notional "clean" distribution D, N sln : ∆ → 2 ∆ returns the set of possible corrupted versions of D the learner may observe, where labels are flipped with unknown probability ρ: Equipped with this, we define our notion of SLN-robustness. Definition 1 (SLN-robustness). We say that a learner That is, SLN-robustness requires that for any level of label noise in the observed distribution D, the classification performance (wrt D) of the learner is the same as if the learner directly observes D. Unfortunately, as we will now see, a widely adopted class of learners is not SLN-robust. Fix X = R d , and consider learners employing a convex potential , and a function class of linear scorers This captures e.g. the linear SVM and logistic regression, which are widely studied in theory and applied in practice. Unfortunately, these learners are not SLN-robust: Long and Servedio [2010, Theorem 2] give an example where, when learning under symmetric label noise, for any convex potential , the corrupted -risk minimiser over F lin has classification performance equivalent to random guessing on D. This implies that ( , F lin ) is not SLN-robust 1 as per Definition 1. (All Proofs may be found in Appendix A.) The widespread practical use of convex potential based learners makes Proposition 1 a disheartening result, and motivates the search for other learners that are SLN-robust. In light of Proposition 1, there are two ways to proceed in order to obtain SLN-robust learners: either we change the class of losses , or we change the function class F. The first approach has been pursued in a large body of work that embraces non-convex losses [Stempfel and Ralaivola, 2009 , Masnadi-Shirazi et al., 2010 , Ding and Vishwanathan, 2010 , Denchev et al., 2012 , Manwani and Sastry, 2013 . However, while such losses avoid the conditions of Proposition 1, this does not automatically imply that they are SLN-robust when used with F lin . In Appendix B, we present evidence that some of these losses are in fact not SLN-robust when used with F lin . The second approach is to instead consider suitably rich F that contains the Bayes-optimal scorer for D, e.g. by employing a universal kernel. With this choice, one can still use a convex potential loss; in fact, owing to Equation 2, using any classification-calibrated loss will result in an SLN-robust learner when F = R X . 1 Even if we weaken the notion of SLN-robustness to allow for a difference of ∈ [0, 1/2] between the clean and corrupted minimisers' performance, Long and Servedio [2010, Theorem 2] implies that in the worst case = 1/2. 3 Proposition 2. Pick any classification-calibrated . Then, ( , R X ) is SLN-robust. Both approaches have drawbacks. The first approach has a computational penalty, as it requires optimising a non-convex loss. The second approach has a statistical penalty, as estimation rates with a rich F will require a larger sample size. Thus, it appears that SLN-robustness involves a computational-statistical tradeoff. However, there is a variant of the first option: pick a loss that is convex, but not a convex potential. If an SLN-robust loss of this type exists, it affords the computational and statistical advantages of minimising convex risks with linear scorers. Manwani and Sastry [2013] demonstrated that square loss, (y, v) = (1 − yv) 2 , is one such loss. We will show that there is a simpler loss that is similarly convex, classification-calibrated, and SLN-robust, but is not in the class of convex potentials by virtue of being negatively unbounded. To derive this loss, it is helpful to interpret robustness in terms of a noise-correction procedure on loss functions. The definition of SLN-robustness (Equation 3) involves optimal scorers with the same loss over two different distributions. We now re-express this to reason about optimal scorers on the same distribution, but with two different losses. This will help characterise the set of losses that are SLN-robust. Given any ρ ∈ [0, 1/2), Natarajan et al. [2013, Lemma 1] showed how to associate with a loss a noise- The loss is defined as follows. Definition 2 (Noise-corrected loss). Given any loss and ρ ∈ [0, 1/2), the noise-corrected loss is Since depends on the unknown parameter ρ, it is not directly usable to design an SLN-robust learner. Nonetheless, it is a useful theoretical construct, since the risk equivalence between L D (s) and L D (s) means that for any F, minimisation of the -risk on D over F is equivalent to minimisation of the -risk on D over F, i.e. S D,F, * = S D,F, * . With this, we can re-express the SLN-robustness of a learner ( , F) as This reformulation is useful, because to characterise SLN-robustness of ( , F), we can now consider conditions on such that and its noise-corrected counterpart induce the same restricted Bayes-optimal scorers. Manwani and Sastry [2013, Theorem 1] proved a sufficient condition on such that Equation 5 holds, namely, For such a loss, is a scaled and translated version of , so that trivially S D,F, * = S D,F, * . Ideally, one would like to characterise when Equation 5 holds. While this is an open question, interestingly, we can show that under a stronger requirement on the losses and , the condition in Equation 6 is also necessary. The stronger requirement is that the corresponding risks order all stochastic scorers identically. A stochastic scorer is simply a mapping f : X → ∆ R , where ∆ R is the set of distributions over the reals. In a slight abuse of notation, we denote the -stochastic risk of f by Equipped with this, we define a notion of order equivalence of loss pairs. Definition 3 (Order equivalent loss pairs). We say that a pair of losses ( ,˜ ) are order equivalent if Clearly, if two losses are order equivalent, their corresponding risks have the same restricted minimisers. Consequently, if ( , ) are order equivalent for every ρ ∈ [0, 1/2), this implies that S D,F, * = S D,F, * for any F, which by Equation 5 means that for any F, the learner ( , F) is SLN-robust. We can thus think of order equivalence of ( , ) as signifying strong SLN-robustness of a loss . Definition 4 (Strong SLN-robustness). We say a loss is strongly SLN-robust if for every ρ ∈ [0, 1/2), ( , ) are order equivalent. We establish that the sufficient condition of Equation 6 is also necessary for strong SLN-robustness of . We now return to our original goal, which was to find a convex that is SLN-robust for F lin (and ideally more general function classes). The above suggests that to do so, it is reasonable to consider as admissible those losses that satisfy Equation 6. Unfortunately, it is evident that if is convex, non-constant, and bounded below by zero, then it cannot possibly be admissible in this sense. But we now show that removing the boundedness restriction allows for the existence of a convex admissible loss. 5 The unhinged loss: a convex, classification-calibrated, strongly SLNrobust loss Consider the following simple, but non-standard convex loss: A peculiar property of the loss is that it is negatively unbounded, an issue we discuss in §5.3. Compared to the hinge loss, the loss does not clamp at zero, i.e. it does not have a hinge. Thus, we call this the unhinged loss 2 . The loss has a number of attractive properties, the most immediate of which is its SLN-robustness. Since unh 1 (v) + unh −1 (v) = 0 we conclude from Proposition 3 that unh is strongly SLN-robust, and thus that ( unh , F) is SLN-robust for any choice of F. Further, the following uniqueness property is not hard to show. Proposition 4. Pick any convex loss . Then, That is, up to scaling and translation, unh is the only convex loss that is strongly SLN-robust. Returning to the case of linear scorers, the above implies that ( unh , F lin ) is SLN-robust. This does not contradict Proposition 1, since unh is not a convex potential as it is negatively unbounded. Intuitively, this property allows the loss to compensate for the high penalty incurred by instances that are misclassified with high margin by allowing for a high gain for instances that correctly classified with high margin. 2 This loss has been considered in Sriperumbudur et al. [2009], Reid and Williamson [2011] in the context of maximum mean discrepancy; see Appendix E.4. The analysis of its SLN-robustness is to our knowledge novel. 5 SLN-robustness is by itself insufficient for a learner to be useful. For example, a loss that is uniformly zero is strongly SLN-robust, but is useless as it is not classification-calibrated. Fortunately, the unhinged loss is classification-calibrated, as we now establish. For reasons that shall be discussed subsequently, we consider minimisation of the risk over F B = [−B, +B] X , the set of scorers with range bounded by B ∈ [0, ∞). Thus, for every B ∈ [0, ∞), the restricted Bayes-optimal scorer over F B has the same sign as the Bayesoptimal classifier for 0-1 loss. In the limiting case where F = R X , the optimal scorer is attainable if we operate over the extended reals R ∪ {±∞}, in which case we can conclude that unh is classification-calibrated. While the classification-calibration of unh is encouraging, Proposition 5 implies that its (unrestricted) Bayesrisk is −∞. Thus, the regret of every non-optimal scorer s is identically +∞, which hampers analysis of consistency. In orthodox decision theory, analogous theoretical issues arise when attempting to establish basic theorems with unbounded losses [Ferguson, 1967, pg. 78], [Schervish, 1995, pg. 172]. We can side-step this issue by restricting attention to bounded scorers, so that unh is effectively bounded. By Proposition 5, this does not affect the classification-calibration of the loss. In the context of linear scorers, boundedness of scorers can be achieved by regularisation: instead of working with F lin , one can instead use Observe that restricting to bounded scorers does not affect the SLN-robustness of unh , because ( unh , F) is SLN-robust for any F. Thus, for example, ( unh , F lin,λ ) is SLN-robust for any λ > 0. As we shall see in §6.3, working with F lin,λ also lets us establish SLN-robustness of the hinge loss when λ is large. Using bounded scorers makes it possible to establish a surrogate regret bound for the unhinged loss. This shows classification consistency of unhinged loss minimisation on the corrupted distribution.  Standard rates of convergence via generalisation bounds are also trivial to derive; see Appendix D. We now turn to the question of how to minimise the unhinged loss when using a kernelised scorer. We now show that the optimal solution for the unhinged loss when employing regularisation and kernelised scorers has a simple form. This sheds further light on SLN-robustness and regularisation. Consider minimising the unhinged risk over some ball in a reproducing kernel Hilbert space H with kernel k, i.e. consider the function class of kernelised scorers F H,λ = {s : x → w, Φ(x) H | ||w|| H ≤ 1/ √ λ} for some λ > 0, where Φ : X → H is some feature mapping. Equivalently, given a distribution 3 D, we want 3 Given a training sample S ∼ D n , we can use plugin estimates as appropriate. The first-order optimality condition implies that Thus, the optimal scorer for the unhinged loss is simply That is, we score an instance based on the difference of the aggregate similarity to the positive instances, and the aggregate similarity to the negative instances. This is equivalent to a nearest centroid classifier [Manning et al., 2008, pg. 181 gives a simple way to understand the SLN-robustness of ( unh , F H,λ ): it is easy to establish (see Appendix C) that the optimal scorers on the clean and corrupted distributions only differ by a scaling, i.e. We note several points relating to practical usage of the unhinged loss with kernelised scorers. First, crossvalidation is not required to select λ, since s * unh,λ depends trivially on the regularisation constant: changing λ only changes the magnitude of scores, not their sign. Thus, regularisation simply controls the scale of the predicted scores, and for the purposes of classification, one can simply use λ = 1. Second, we can easily extend the scorers to use a bias regularised with strength 0 < λ b = λ. Tuning λ b is equivalent to computing s * unh,λ as per Equation 9, and tuning a threshold on a holdout set. Third, when H = R d for d small, we can store w * unh,λ explicitly, and use this to make predictions. For high (or infinite) dimensional H, we can make predictions directly via Equation 9. However, when learning with a training sample S ∼ D n , this would require storing the entire sample for use at test time, which is undesirable. To alleviate this, for a translation-invariant kernel one can use random Fourier features [Rahimi and Recht, 2007] to find an approximate embedding of H into some low-dimensional R d , and then store w * unh,λ as usual. Alternately, one can post hoc search for a sparse approximation to w * unh,λ , for example using kernel herding [Chen et al., 2012] . We now show that under some assumptions, w * unh,λ coincides with the solution of two established methods; Appendix E discusses some further relationships, e.g. to the maximum mean discrepancy. There is an interesting equivalence between the unhinged solution and that of a highly regularised SVM. Proposition 7. Pick any D and Φ : X → H such that R = sup x∈X ||Φ(x)|| H < ∞. For any λ > 0, let Since we know that ( unh , F H,λ ) is SLN-robust, it follows immediately that for hinge : (y, v) → max(0, 1− yv), ( hinge , F H,λ ) is similarly SLN-robust provided λ is sufficiently large. That is, strong 2 regularisation (and a bounded feature map) endows the hinge loss with SLN-robustness 4 . Proposition 7 can be generalised to show that with sufficiently strong regularisation, the limiting solution of any twice differentiable convex potential will be the unhinged solution, i.e. , the centroid classifier. Intuitively, with strong regularisation, one only considers the behaviour of a loss near zero; but since a convex 4 By contrast, Long and Servedio [2010, Section 6] establish that 1 regularisation does not endow SLN-robustness. 7 potential φ has φ (0) < 0, it will be well-approximated by the unhinged loss near zero (which is simply the linear approximation to φ). This shows that strong 2 regularisation endows most learners with SLNrobustness. Proposition 8. Pick any D, bounded feature mapping Φ : X → H, and twice differentiable convex potential φ. Let w * φ,λ be the minimiser of the regularised φ risk. Then, Recall that for binary classification on D M,η , the Fisher Linear Discriminant (FLD) finds a weight vector proportional to the minimiser of square loss  We now illustrate that the SLN-robustness of the unhinged loss is empirically manifest. We reiterate that with high regularisation, the unhinged solution is equivalent to an SVM (and in the limit to any classificationcalibrated loss) solution. Thus, the experiments do not aim to assert that the unhinged loss is "better" than other losses, but rather, to demonstrate that its SLN-robustness is not purely theoretical. We first show that the unhinged risk minimiser performs well on the example of Long and Servedio [2010]. Figure 1 shows the distribution D, where X = {(1, 0), (γ, 5γ), (γ, −γ)} ⊂ R 2 , with marginal distribution M = { 1 4 , 1 4 , 1 2 } and all three instances are deterministically positive. We pick γ = 1/2. From Figure 1 , we see the unhinged minimiser perfectly classifies all three points, regardless of the level of label noise. The hinge risk minimiser is perfect when there is no label noise, but with even a small amount of label noise, achieves an error rate of 50%. Hinge t-logistic Unhinged ρ = 0 0.00 ± 0.00 0.00 ± 0.00 0.00 ± 0.00 ρ = 0.1 0.15 ± 0.27 0.00 ± 0.00 0.00 ± 0.00 ρ = 0.2 0.21 ± 0.30 0.00 ± 0.00 0.00 ± 0.00 ρ = 0.3 0.38 ± 0.37 0.22 ± 0.08 0.00 ± 0.00 ρ = 0.4 0.42 ± 0.36 0.22 ± 0.08 0.00 ± 0.00 ρ = 0.49 0.47 ± 0.38 0.39 ± 0.23 0.34 ± 0.48  We next consider minimisers of the empirical risk from a random training sample: we construct a training set of 800 instances, injected with varying levels of label noise, and evaluate classification performance on a test set of 1000 instances. We compare the hinge, t-logistic (for t = 2) [Ding and Vishwanathan, 2010] and unhinged minimisers. For each loss, we use a linear scorer without a bias term, and set the regularisation strength λ = 10 −16 . From Table 1 , it is apparent that even at 40% label noise, the unhinged classifier is able to find a perfect solution. By contrast, both other losses suffer at even moderate noise rates. We next report results on some UCI datasets, where we additionally tune a threshold so as to ensure the best training set 0-1 accuracy. Table 2 summarises results on a sample of four datasets. (Appendix H contains results with more datasets, performance metrics, and losses.) While the unhinged loss is sometimes outperformed at low noise, it tends to be much more robust at high levels of noise: even at noise close to 50%, it is often able to learn a classifier with some discriminative power.  We have proposed a convex, classification-calibrated loss, proved that is robust to symmetric label noise (SLN-robust), shown it is the unique loss that satisfies a notion of strong SLN-robustness, established that it is optimised by the nearest centroid classifier, and also shown how the nature of the optimal solution implies that most convex potentials, such as the SVM, are also SLN-robust when highly regularised. Future work includes studying losses robust to asymmetric noise, and outliers in instance space. 9 Acknowledgments
Unhinged loss, a convex loss (which is not convex potential), is robust to symmetric label noise REF .
Learning with Symmetric Label Noise: The Importance of Being Unhinged
ArXiv
ArXiv
Mathematics Computer Science