Making Risk Minimization Tolerant to Label Noise

Aritra Ghosh; Naresh Manwani; P. S. Sastry

Source-linked AI summary

Making Risk Minimization Tolerant to Label Noise

Aritra Ghosh, Naresh Manwani, P. S. Sastry

arXiv:1403.3610v2Mar 14, 2014cs.LG

TL;DR

Label noise can corrupt classifier-training data, while standard methods such as SVM may be vulnerable. The paper derives loss-function conditions for risk minimization to tolerate uniform and non-uniform noise, and finds robust behavior for several non-convex losses in theory and experiments.

Problem
The paper addresses how to learn classifiers robustly when training labels are corrupted by noise.
Method
The paper derives sufficient conditions on loss functions for risk minimization to tolerate uniform and non-uniform label noise, then evaluates sigmoid and ramp loss methods empirically.
Results
0-1, sigmoid, ramp, and probit losses satisfy the uniform-noise condition, while sigmoid, ramp, and probit losses can also tolerate non-uniform noise under additional assumptions; experiments show stronger robustness than SVM.
Takeaways & Limitations
Risk minimization with sigmoid or ramp loss offers a non-convex alternative to SVM for learning classifiers robust to label noise.
Takeaways & Limitations
The theory applies to true risk minimization, while empirical-risk robustness is supported only by a plausibility argument requiring enough data and limited function-class complexity.

Abstract

from arXiv · show

In many applications, the training data, from which one needs to learn a classifier, is corrupted with label noise. Many standard algorithms such as SVM perform poorly in presence of label noise. In this paper we investigate the robustness of risk minimization to label noise. We prove a sufficient condition on a loss function for the risk minimization under that loss to be tolerant to uniform label noise. We show that the $0-1$ loss, sigmoid loss, ramp loss and probit loss satisfy this condition though none of the standard convex loss functions satisfy it. We also prove that, by choosing a sufficiently large value of a parameter in the loss function, the sigmoid loss, ramp loss and probit loss can be made tolerant to non-uniform label noise also if we can assume the classes to be separable under noise-free data distribution. Through extensive empirical studies, we show that risk minimization under the $0-1$ loss, the sigmoid loss and the ramp loss has much better robustness to label noise when compared to the SVM algorithm.

1. Introduction

The paper studies how to make risk minimization robust to label noise, extending prior analysis with sufficient conditions on loss functions. It shows that several non-convex losses satisfy these conditions and perform robustly in experiments.

Motivation: Label noise arises when training examples have incorrect or noise-corrupted class labels, including from user labeling variability, human errors, overlapping class-conditional densities, and feature measurement errors.The paper frames label noise as a practical issue in web applications and traditional pattern recognition.
Problem: The paper focuses on making the generic risk-minimization strategy robust to label noise.Risk minimization encompasses standard classifier-learning approaches through suitable loss functions.
Problem: A classifier is noise-robust when training with noisy and noise-free data yields the same classification accuracy on noise-free test data.Prior work showed this property for 0-1 loss under uniform noise below 50%, while many standard convex losses are not noise-tolerant.
Contributions: The paper derives sufficient loss-function conditions for tolerance to uniform and non-uniform label noise.For non-uniform noise, the results require a zero Bayes risk under noise-free data and a suitably chosen loss parameter.
Contributions: The 0-1, sigmoid, ramp, and probit losses satisfy the uniform-noise condition, while sigmoid, ramp, and probit losses can also tolerate non-uniform noise under additional conditions.The paper reports extensive empirical studies showing good robustness to label noise.

2. Prior Work

Prior work includes data-cleaning heuristics, inherently noise-tolerant algorithms, PAC-learning methods, and risk-minimization analyses. The paper generalizes earlier risk-minimization results by identifying sufficient conditions covering several non-convex losses.

Approaches: Label-noise methods either preprocess data to identify and alter corrupted examples or design learning algorithms whose outputs are less affected by noisy labels.The paper calls the latter approaches inherently noise tolerant.
Data Cleaning Based Approaches: Data-cleaning heuristics depend on the noise structure, can misidentify clean and noisy points, increase noise, and remove information about classification boundaries.Nearest-neighbor mismatch can also fail near the classification boundary and depends on the neighborhood size.
Inherently Noise Tolerant Approaches: Inherently noise-tolerant approaches modify algorithms such as Perceptron, AdaBoost, and SVM using heuristic controls on updates, weights, or kernels.These approaches work well in some cases but are generally heuristic rather than universally applicable.
PAC Learnability: PAC-learning research has produced polynomial-time methods for some noisy linear-classification settings, with results depending on assumptions such as uniform noise or linear separability with a large margin.Other methods avoid the large-margin condition but may output decision lists of linear threshold functions.
Risk Minimization: Earlier risk-minimization analysis established noise tolerance for 0-1 loss under uniform noise and under non-uniform noise when the noise-free optimal risk is zero.The earlier analysis did not establish tolerance for most other losses, apart from square loss under uniform noise.
Risk Minimization: This paper generalizes those results with sufficient conditions covering 0-1, ramp, sigmoid, and probit losses, including non-uniform-noise results under zero Bayes risk and suitable parameter choices.It also provides a sufficient condition for robustness to class-conditional noise.
Method: The paper investigates differentiable sigmoid and ramp approximations to 0-1 loss, using descent methods and a difference-of-convex program for ramp-loss nonlinear classification.The ramp-loss classifier is compared with an SVM based on hinge loss for nonlinear problems.

3. Problem Statement

The paper formalizes binary risk minimization under noisy labels and defines noise tolerance by comparing noisy- and noise-free risk minimizers' classification accuracy. It distinguishes uniform, class-conditional, and general feature-dependent noise.

Setting: The formal analysis concerns binary classification with labels Y = {1, −1} and classifiers represented by sign(f(x)), where f is a real-valued discriminant function.The classifier is selected from a function family F, such as linear functions parameterized by W and w_0.
Risk Minimization: A loss function L assigns a nonnegative penalty to a classifier output and label, and risk minimization learns a classifier with minimum expected loss.Because the data distribution is usually unknown, empirical risk approximates the expectation using iid training samples.
Risk Minimization: Under 0-1 loss, risk equals the probability of misclassification, and the Bayes classifier minimizes this risk.The paper distinguishes this ordinary classification risk from general L-risk under other loss functions.
Scope: The theoretical results apply to true risk minimization, while empirical-risk robustness is presented only as a plausibility argument requiring enough examples and controlled function-class complexity.The paper notes that empirical minimizers can approximate true-risk minimizers under standard consistency conditions.
Noise Models: Noise-free labels are independently flipped with feature-dependent probability η_x, producing the noisy distribution D_η.Uniform noise has η_x = η for all x; class-conditional noise uses one rate per class; general feature-dependent rates are non-uniform.
Noise Tolerance: Noise tolerance means the noisy-data global risk minimizer has the same misclassification probability as the noise-free global minimizer.The two minimizers may differ as functions while retaining equal classification accuracy under the noise-free distribution.

4. Sufficient Conditions for Noise Tolerance

The paper gives a symmetry-based sufficient condition for risk minimization to tolerate uniform label noise, and extends tolerance to non-uniform settings under zero Bayes risk or suitable parameter choices. The condition is satisfied by 0-1, sigmoid, ramp, and probit losses, but not standard convex losses.

Uniform and non-uniform noise: A loss satisfying L(f(x), 1) + L(f(x), −1) = K for all x and f is sufficient for uniform-noise tolerance when ηx < 0.5.With zero noise-free Bayes risk, the same condition also gives tolerance to non-uniform noise.
Uniform and non-uniform noise: Under uniform noise, the noisy-risk difference is scaled by 1 − 2η, preserving the noise-free risk minimizer when η < 0.5.The proof uses the fact that the scaling factor is nonnegative and the noise-free minimizer has no larger risk than any alternative.
Uniform and non-uniform noise: For non-uniform noise, zero Bayes risk ensures the loss at the noise-free minimizer is zero everywhere, allowing the minimizer to remain optimal under ηx < 0.5.When the minimum noise-free risk is small but nonzero, the paper establishes approximate rather than exact tolerance, with a bound worsening as the maximum noise rate approaches 0.5.
Loss-function conditions: The 0-1 loss satisfies the symmetry condition with K = 1, whereas standard convex losses such as hinge and exponential loss do not.For 0-1 loss, non-uniform tolerance additionally requires zero noise-free Bayes risk, meaning the classes are separable by a classifier in the chosen family.
Scope and limitations: The theoretical results apply directly to true-risk minimization, while extending them formally to empirical risk minimization requires further work.The paper treats empirical evidence and standard consistency arguments as motivation, but does not provide the requested finite-sample bounds.
Specific losses: Sigmoid, ramp, and probit losses tolerate uniform noise; with zero Bayes risk, sufficiently large loss parameters also yield non-uniform-noise tolerance.The stated thresholds are β ≥ βM for sigmoid, ramp, and probit losses, with a finite βM under the theorem assumptions.
Class-conditional noise: The class-conditional-noise construction transforms a symmetric loss using the noise rates so noisy-risk minimization recovers the noise-free minimizer.This result assumes η1 + η2 < 1 and a constant-sum loss condition.

5. Experiments

The experiments compare risk minimization with noise-tolerant losses against SVM and square loss across synthetic and UCI datasets under multiple label-noise settings. Sigmoid, ramp, and 0-1 loss generally retain accuracy better than SVM, especially with asymmetric, imbalanced, or nonuniform class distributions.

Experimental design: The study evaluates risk minimization under 0-1, sigmoid, ramp, SVM hinge, and square losses on five synthetic and five UCI datasets.Synthetic problems include linear and nonlinear two-class tasks, with both two-dimensional and d = 50 data.
Experimental design: Synthetic datasets vary class geometry, balance, dimensionality, and noise type, including uniform, nonuniform, and class-conditional label noise.The synthetic problems include asymmetric and imbalanced distributions, a high-dimensional task, and a 2 × 2 checkerboard.
Synthetic results: Under class-conditional noise on Synthetic Dataset 3, SVM accuracy drops to 86%, while the noise-tolerant losses achieve approximately 95%.The comparison concerns asymmetric and imbalanced classes with uniform class-conditional densities.
Synthetic results: Under 10% uniform noise on Synthetic Dataset 2, SVM accuracy drops to 77.8%, while sigmoid and ramp losses retain at least 96% accuracy under 40% noise.Sigmoid and ramp losses also achieve around 98% under nonuniform and class-conditional noise, compared with 77% for SVM.
Synthetic results: Under 40% uniform noise on Synthetic Dataset 3, SVM accuracy decreases to 75.8%, whereas sigmoid and ramp losses remain above 99%.Both losses also outperform SVM under nonuniform and class-conditional noise.
Synthetic results: On high-dimensional Synthetic Dataset 4, noise-tolerant losses maintain good performance, while SVM accuracy keeps dropping as label noise increases.This dataset contains imbalanced, asymmetric classes in R50.
Overall findings: Across the reported synthetic and real-data results, sigmoid, ramp, and 0-1 risk minimization show stronger noise tolerance than SVM, particularly for asymmetric or imbalanced class regions.The paper reports that SVM performs moderately well for balanced symmetric classes but degrades severely with intra-class nonuniformity or imbalance.

6. Conclusions and Future Work

The paper establishes sufficient loss-function conditions for risk minimization to tolerate uniform and, under stronger conditions, non-uniform label noise. Empirical studies support the robustness of sigmoid, ramp, and 0-1 losses while highlighting computational challenges from non-convexity.

The paper derives sufficient conditions making risk minimization noise-tolerant under uniform and non-uniform label noise.
Sigmoid, ramp, and probit losses tolerate uniform noise, while non-uniform tolerance requires a sufficiently high loss parameter.For non-uniform noise, the noise-free Bayes risk must be zero.
Extensive empirical studies demonstrate noise tolerance for sigmoid, ramp, and 0-1 losses, unlike the popular SVM method.The studies also identify class geometries that make SVM sensitive to label noise.
All highlighted noise-tolerant losses are non-convex, making risk minimization harder than with standard convex losses.Sigmoid and ramp losses are smooth, but nonlinear learning is not generally efficient with simple gradient descent.
A DC-programming algorithm enables ramp-loss risk minimization with kernel functions for robust nonlinear classifiers.
The paper proposes degree of noise tolerance as the difference between misclassification probabilities under noisy and noise-free data.The 0-1, ramp, and sigmoid losses have highest degree when this difference is zero.

Appendix A. Regularized Empirical Risk Minimization

The appendix reformulates regularized empirical risk minimization under ramp loss as a difference of convex functions. This decomposition yields a DC-programming procedure for minimizing the objective.

Ramp loss can be represented as the difference of two convex functions.
For nonlinear classifiers f(x) = w^Tφ(x) + b, the appendix defines regularized empirical ramp-loss risk using parameters Θ = (w, b).C is the regularization parameter and φ is a nonlinear transformation.
The regularized ramp-loss objective is decomposed into two convex components, Q1(Θ) and Q2(Θ).
The decomposition leads to a DC-programming algorithm for efficiently minimizing regularized empirical ramp-loss risk.
The appendix presents a high-level DC program for minimizing the regularized empirical ramp-loss objective.
The procedure derives the next parameters Θ^(l+1) from the current iterate using the main DC-program step.

Appendix A.1. Finding Θ(l+1)

The DC iteration converts ramp-loss minimization into a constrained quadratic optimization problem. It derives the associated dual formulation and solves it using generalized sequential minimal optimization.

The DC iteration identifies training examples through indicator-based conditions involving current parameters and β^(l).
The next optimization imposes nonnegative slack variables and margin constraints for every training example.
The constrained primal problem is transformed into a dual optimization problem using Lagrange multipliers α and µ.
Stationarity conditions relate the regularization parameter C, multipliers µ_i, and α_i for each training example.
Complementary slackness links µ_i to ξ_i and α_i to the margin constraint for each example.
The resulting dual is used in the subsequent optimization step and solved with generalized sequential minimal optimization for fast convergence.
The complete DC algorithm for ramp-loss minimization is specified in Algorithm 2.

Algorithm 2: DC Algorithm for Minimizing Rreg

Algorithm 2 takes a positive regularization parameter and training dataset as input, and returns the learned classifier parameters.

The algorithm accepts C > 0 and training dataset S as inputs, returning optimal parameters w* and b*.
Its first step computes β_i^(l) for every training example.