PaperlayerView exact revision on arXiv

Source-linked AI summary

Noise Tolerance under Risk Minimization

Naresh Manwani, P. S. Sastry

arXiv:1109.5231v4cs.LG

TL;DR

The paper asks whether classifiers learned by risk minimization remain accurate when training labels are corrupted with feature-dependent probabilities. It formalizes noise tolerance by comparing clean and noisy risk minimizers, then analyzes several losses. The main result is that 0-1 loss is tolerant under uniform noise and, under non-uniform noise, when clean risk is zero; squared error is tolerant only under uniform noise, while other examined losses are not.

  • Problem

    The paper addresses whether classifier learning remains noise-tolerant when observed labels are corrupted with probabilities that depend on feature vectors.

  • Method

    It analyzes risk minimization under multiple loss functions by comparing minimizers trained with ideal noise-free labels and corrupted labels.

  • Results

    0-1 loss is tolerant under uniform noise and under non-uniform noise when clean risk is zero; squared error is tolerant only to uniform noise, while other examined losses are not.

  • Takeaways & Limitations

    The analysis suggests that minimizing 0-1 loss may be promising for classifier design with noisy training data, despite its optimization difficulty.

  • Takeaways & Limitations

    Using 0-1 loss in practice is constrained by discontinuity and the difficulty of standard optimization, motivating more efficient gradient-free methods.

Abstract

from arXiv · show

In this paper we explore noise tolerant learning of classifiers. We formulate the problem as follows. We assume that there is an ${\bf unobservable}$ training set which is noise-free. The actual training set given to the learning algorithm is obtained from this ideal data set by corrupting the class label of each example. The probability that the class label of an example is corrupted is a function of the feature vector of the example. This would account for most kinds of noisy data one encounters in practice. We say that a learning method is noise tolerant if the classifiers learnt with the ideal noise-free data and with noisy data, both have the same classification accuracy on the noise-free data. In this paper we analyze the noise tolerance properties of risk minimization (under different loss functions), which is a generic method for learning classifiers. We show that risk minimization under 0-1 loss function has impressive noise tolerance properties and that under squared error loss is tolerant only to uniform noise; risk minimization under other loss functions is not noise tolerant. We conclude the paper with some discussion on implications of these theoretical results.

I. INTRODUCTION

The introduction frames label noise as a pervasive classification problem and studies whether risk minimization remains reliable when corruption depends on features. It compares loss functions through a formal noise-tolerance analysis, emphasizing the strong properties of 0-1 loss alongside its computational difficulty.

  • Noisy training examples can have incorrect class labels from overlapping class distributions, manual classification errors, and other sources.
  • Risk minimization chooses a loss function and seeks a classifier minimizing expected loss over the feature distribution, including noise when samples are corrupted.
  • The paper studies noise tolerance for 0-1, squared error, exponential, and hinge losses under feature-dependent label corruption.
  • Noise tolerance is defined by equal noise-free misclassification probability for minimizers learned from ideal versus noisy data.
  • Risk minimization with 0-1 loss has strong noise-tolerance properties, but its optimization problem is computationally hard compared with convex surrogate losses.

II. NOISE TOLERANT LEARNING

The paper formalizes noise-tolerant learning by comparing risk minimizers trained with unobservable clean labels and observed corrupted labels. Its model allows example-specific corruption probabilities, while the analysis focuses on binary classification and a unified classifier notation.

  • Standard noise-handling methods include outlier detection, label restoration, and limiting noisy-point effects, but they are largely heuristic and may assume uniform noise.
  • The paper instead studies inherently noise-tolerant risk minimization, whose output remains equivalent in the relevant sense for noisy and noise-free inputs.
  • Statistical-query approaches have noise-tolerance properties but are mostly limited to binary features, and their required statistics depend on noise and classifier type.
  • The framework restricts attention to two-class classification and represents classifiers as real-valued functions whose predicted labels are sign(f(x)).
  • The ideal noise-free sample is assumed to exist but remain unobservable, while observed training labels are independently flipped with example-specific probabilities η_x.
  • Noise is uniform when η_x is constant across examples and non-uniform otherwise, with the standing assumption η_x < 0.5 for every x.
  • Noise tolerance compares the noise-free and noisy risk minimizers by their probability of misclassification on the underlying noise-free distribution.
  • The noisy and clean minimizers need not be identical because equal noise-free misclassification probability is sufficient for tolerance.

III. NOISE TOLERANCE OF RISK MINIMIZATION

This section analyzes risk minimization under different losses, establishing when 0-1 loss preserves the clean minimizer and constructing a counterexample when its clean risk is nonzero. It also highlights the computational trade-off that motivates alternative losses.

  • Theorem 1 states that 0-1 risk minimization tolerates uniform noise and tolerates non-uniform noise when the clean risk minimizer has zero risk.
  • Under uniform noise, noisy risk is η + (1 − 2η)R(f), so the clean minimizer remains a noisy-risk minimizer when η < 0.5.
  • When the clean minimizer achieves zero risk, it also minimizes noisy risk under non-uniform corruption with η_x < 0.5 for all x.
  • If the clean minimum risk is nonzero, 0-1 risk minimization is generally not tolerant to non-uniform noise, as shown by a counterexample.
  • The counterexample restricts a quadratic-boundary problem to linear classifiers, producing nonzero clean risk and a different minimizer after non-uniform label corruption.
  • The analysis also applies to empirical risk minimization by treating the feature distribution as the empirical distribution.
  • Although 0-1 loss has strong tolerance properties, its discontinuity makes risk minimization a difficult non-convex optimization problem.

B. Squared Error Loss Function

Squared error risk minimization for linear classifiers is noise tolerant under uniform label noise, but a counterexample shows it can fail under non-uniform noise.

  • Theorem 2 establishes noise tolerance for squared error risk minimization when learning linear classifiers under uniform noise ηx = η < 0.5.
  • Under uniform noise, the noisy and noise-free minimizers induce identical classifications, so least squares remains noise tolerant.
  • Fisher Linear Discriminant is noise tolerant under uniform label noise.
  • The stated squared-error result is proved for linear classifiers, with possible extension to richer families through nonlinear feature mappings.
  • Under non-uniform noise, the feature-dependent corruption rate remains inside the expectation and can change the risk minimizer.
  • In Example 2, the noise-free linear classifier classifies all points correctly, whereas non-uniform noise makes the learned classifier misclassify four points.
  • Squared error loss is therefore not noise tolerant under non-uniform noise, even with zero noise-free minimum risk and a linear optimal classifier.

C. Exponential Loss Function

The paper examines exponential-loss risk minimization through a three-point linear-classifier example and finds that uniform label noise can change the learned classifier's accuracy.

  • Exponential loss is the effective loss function for AdaBoost.
  • In the three-point example, the noise-free exponential-loss minimizer correctly classifies every point.
  • With uniform label noise at rate η = 0.3, exponential-loss risk minimization is not noise tolerant.

D. Log Loss Function

The paper uses the same three-point linear-classifier example to analyze log loss and reports that uniform label noise changes the classifier's noise-free accuracy.

  • Log loss is the effective loss function for logistic regression, but its risk minimization is not noise tolerant.
  • For the noise-free three-point dataset, the log-loss minimizer correctly classifies all points.
  • The analysis introduces uniform label noise at rate η = 0.3 and solves for the noisy-risk minimizer using a polynomial in t = e^b.
  • The resulting noisy classifier has different noise-free accuracy from the noise-free classifier, establishing failure of noise tolerance.

E. Hinge Loss Function

The paper shows that hinge-loss risk minimization is not noise tolerant, including under uniform label noise, even when the optimal classifier is linear.

  • Hinge-loss risk minimization is not noise tolerant, as shown by a counterexample.
  • The counterexample considers linear classifiers of the form sign(wx + b) on a specified training dataset.
  • Without noise, the optimal linear classifier correctly classifies all points, achieving P[sign(w∗x + b∗) = yx] = 1.
  • Uniform label noise with rate η = 0.3 is then introduced into the training data.
  • The resulting hinge-loss classifier is not noise tolerant even under uniform noise, despite the optimal classifier being linear.

IV. SOME EMPIRICAL RESULTS

The empirical study uses noisy Iris training data and noise-free testing to compare risk minimization under 0-1, hinge, squared-error, and log losses. The results support the theoretical pattern: 0-1 loss tolerates both noise types, while least squares tolerates uniform noise.

  • The simulations restrict learning to linear classifiers on a two-class version of the Iris dataset.The two classes combine Iris-versicolor and Iris-virginica; Iris-setosa is excluded from the binary task.
  • Uniform noise rates vary from 10% to 30%, while non-uniform flipping probabilities depend on the example’s quadrant in the first two features.
  • Training uses noisy examples, testing uses the original noise-free examples, and test error rate measures noise tolerance.
  • The comparison includes CALA with 0-1 loss, SVM with hinge loss, linear least squares with squared error loss, and logistic regression with log loss.
  • Under 20% uniform noise, SVM accuracy drops from 98% without noise to 89%, while logistic regression drops from 98% to 91%.
  • Linear least squares decreases from 92% accuracy without noise to 91% under 20% uniform noise, indicating tolerance to uniform noise.

V. CONCLUSION

The conclusion identifies 0-1 loss as the most noise-tolerant option, while convex alternatives trade noise tolerance for easier optimization. It also highlights computational barriers to exploiting 0-1 loss, especially beyond linear classifiers.

  • 0-1 loss is noise tolerant under uniform noise and under non-uniform noise when the noise-free risk minimizer has zero risk.
  • If the classifier family contains the Bayes classifier, the noise-free minimum risk can be zero, satisfying the condition for non-uniform noise tolerance.
  • Minimizing 0-1 loss is difficult because its discontinuity prevents standard optimization techniques.The paper calls for more efficient gradient-free methods, including methods for nonlinear classifiers.
  • Convex losses make risk optimization easy, but the paper reports that these approaches over-fit in the presence of noise.
  • Hinge, exponential, and log losses are not noise tolerant even under uniform label noise.
  • Linear least squares and Fisher linear discriminant are tolerant under uniform noise but not under non-uniform noise.
  • The analysis suggests investigating 0-1-loss minimization as a promising classifier-design approach for noisy training data.
Loading 1109.5231v4…