PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning with Confident Examples: Rank Pruning for Robust Classification with Noisy Labels

Curtis G. Northcutt, Tailin Wu, Isaac L. Chuang

arXiv:1705.01936v3stat.MLcs.LG

TL;DR

Noisy PN learning must recover true binary classifications and label-noise rates from corrupted examples. The paper proposes Rank Pruning, which estimates asymmetric noise and prunes by confidence-ranked examples; it reports broad robustness and state-of-the-art performance across noisy-label settings.

  • Problem

    Noisy PN learning seeks true classifications and asymmetric noise rates when only corrupted labels are observed.

  • Method

    Rank Pruning estimates ρ1 and ρ0, then removes mislabeled examples using confident examples and rank-based pruning before training.

  • Results

    Rank Pruning achieves state-of-the-art noise estimation and F1, Error, and AUC-PR across varied datasets, classifiers, and noise conditions.

  • Takeaways & Limitations

    The method provides a time-efficient, general approach that can recover clean-label-equivalent expected risk under ideal conditions and remain robust under weaker assumptions.

  • Takeaways & Limitations

    Rank Pruning may remove correctly labeled examples that confuse the classifier, and its behavior can depend on classifier fit and classification threshold.

Abstract

from arXiv · show

Noisy PN learning is the problem of binary classification when training examples may be mislabeled (flipped) uniformly with noise rate rho1 for positive examples and rho0 for negative examples. We propose Rank Pruning (RP) to solve noisy PN learning and the open problem of estimating the noise rates, i.e. the fraction of wrong positive and negative labels. Unlike prior solutions, RP is time-efficient and general, requiring O(T) for any unrestricted choice of probabilistic classifier with T fitting time. We prove RP has consistent noise estimation and equivalent expected risk as learning with uncorrupted labels in ideal conditions, and derive closed-form solutions when conditions are non-ideal. RP achieves state-of-the-art noise estimation and F1, error, and AUC-PR for both MNIST and CIFAR datasets, regardless of the amount of noise and performs similarly impressively when a large portion of training examples are noise drawn from a third distribution. To highlight, RP with a CNN classifier can predict if an MNIST digit is a "one"or "not" with only 0.25% error, and 0.46 error across all digits, even when 50% of positive examples are mislabeled and 50% of observed positive labels are mislabeled negative examples.

1 Introduction

The paper introduces Rank Pruning for binary classification with asymmetrically noisy labels, combining noise-rate estimation with removal of likely mislabeled examples. It targets robust, time-efficient learning across classifiers, datasets, and noise conditions.

  • Core approach: Rank Pruning estimates asymmetric noise rates and removes mislabeled examples before training.Its two sequential stages address both noise estimation and classification under noisy labels.
  • Core approach: Confident examples are those predicted near 1 for positive labels or near 0 for negative labels.Removing non-confident examples is intended to reveal a subset of uncorrupted training data.
  • Efficiency: Rank-based pruning uses BFPRT to remove kth-ranked examples in O(n) time without sorting.This reduces sensitivity to probability calibration and exploits the simpler ranking problem.
  • Noise estimation: Noise rates are estimated from the fraction of confident examples in each observed class rather than averaged predicted probabilities.The approach is designed to be more robust to variation in probability estimation.
  • Theory: Rank Pruning provides perfect noise estimation and label-equivalent expected risk under stated assumptions, with closed-form solutions when assumptions are relaxed.These theoretical guarantees complement its general noisy-label classification objective.
  • Empirical results: Rank Pruning improves state-of-the-art F1, AUC-PR, and Error across varied noisy-label scenarios and can approach clean-label F1 under severe mislabeling.The reported generalization spans training size, feature dimension, mislabeling, and added third-distribution noise.

2 Framing the ˜P ˜N Learning Problem

The noisy PN problem seeks a classifier for hidden true labels when only corrupted labels are observed. Rank Pruning estimates the hidden noise rates and uses them to recover the true classification relationship under progressively weaker assumptions.

  • Problem formulation: A classifier fit directly to observed pairs estimates x → s rather than the desired mapping x → y.Its output is g(x) = P(ŝ = 1|x), based on corrupted labels.
  • Problem formulation: Observed labels s may differ from hidden true labels y through independent class-conditional flips with rates ρ1 and ρ0.The classification-noise process assumes label corruption is conditionally independent of x given y.
  • Problem formulation: The observed positive and negative sets are ˜P and ˜N, whereas P and N denote the unobserved true positive and negative sets.The learner receives only observed (x, s) pairs while y remains hidden.
  • Noise rates: ρ1 is the fraction of true positives mislabeled negative, and ρ0 is the fraction of true negatives mislabeled positive.The necessary condition ρ1 + ρ0 < 1 ensures correctly labeled examples remain more frequent overall.
  • Assumptions: The framework distinguishes perfect, non-overlapping, range-separable, and unassuming conditions for the data distributions and classifier.Range separability requires every true positive to receive a higher g value than every true negative.
  • Goals: Rank Pruning seeks perfect noise-rate estimation when g is ideal and exact expressions otherwise, then uses the estimates to uncover f from g.Both goals must be achieved using only observed pairs because the true labels and noise parameters are hidden.

3 Rank Pruning

Rank Pruning estimates asymmetric noise rates from confident examples, removes likely mislabeled data by rank, and retrains with class-conditional weighting. Under ideal or separability conditions, its estimators are consistent and its pruned loss matches the expected risk of learning from uncorrupted labels.

  • Noise-rate estimation: Rank Pruning estimates ρ1 and ρ0 from counts of confident examples, with out-of-sample estimation requiring O(T) classifier-fitting time.The paper uses 3-fold cross-validation in experiments, requiring at most 2T = O(T).
  • Noise-rate estimation: When g is ideal, threshold-based partitions separate correctly labeled from mislabeled examples within the observed positive and negative sets.The confident-count estimators are then consistent for the two noise rates.
  • Non-ideal conditions: With imperfect g and overlapping support, the confident-count estimators include a non-negative error term and therefore upper-bound the true noise rates in the infinite-sample limit.Under non-overlapping support, the estimators remain robust when probability-estimation error stays below the threshold-to-ideal-score distance.
  • Pruning and retraining: Rank Pruning removes the lowest-scoring observed positives and highest-scoring observed negatives using BFPRT rank selection, producing an O(n) pruning filter.The retained sets are ˜Pconf := {x ∈˜P | g(x) ≥k1} and ˜Nconf := {x ∈˜N | g(x) ≤k0}.
  • Pruning and retraining: The classifier is refit on the retained examples with weights 1/(1−ˆρ1) for positives and 1/(1−ˆρ0) for negatives, while pruned examples receive zero weight.This class-conditional reweighting restores the estimated balance between positive and negative examples.
  • Expected-risk guarantee: If g separates the hidden positive and negative distributions and the noise rates are exact, Rank Pruning exactly removes mislabeled examples and achieves the same expected risk as clean-label learning.The guarantee applies to any classifier fθ and bounded loss function l(ˆyi, yi).

4 Experimental Results

Rank Pruning is evaluated across synthetic, MNIST, and CIFAR settings spanning noise, data complexity, classifier choice, and sample size. It generally remains robust under severe mislabeling and added random noise, while estimating noise rates consistently and sometimes outperforming ground-truth or competing models.

  • Experimental scope: The evaluation spans separability, dimension, training-set size, added random noise, noise rates, MNIST and CIFAR, and logistic-regression and CNN classifiers.These scenarios are designed to test whether Rank Pruning is a general, classifier-agnostic solution.
  • Synthetic dataset: Rank Pruning’s synthetic-data F1 score is fairly agnostic to the magnitude of mislabeling across tested settings.The synthetic experiments vary separability, dimension, sample count, and added uniform noise across five noise-rate pairs.
  • Synthetic dataset: For ρ1 = 0.5 and π1 = 0.5, Rank Pruning often outperforms other methods and approaches the ground-truth classifier’s F1 across separability settings.The comparison gives all methods the same substantial noise rates.
  • Synthetic dataset: With 50% added random noise, Rank Pruning achieves F1 > 0.85, whereas all other methods achieve F1 < 0.5.The method can remove third-distribution noise because such examples are unlikely to appear confidently positive or negative.
  • Noise estimation: On MNIST with logistic regression, empirical estimates differ from actual ρ1 and π1 by 0.105 and 0.062 mean absolute difference, while empirical and theoretical ρ1 estimates differ by 0.0058.The experiments average consistency across digits over π1 ∈ [0, 0.8] and ρ1 ∈ [0, 0.9].
  • MNIST and CIFAR datasets: RPρ often matches MNIST Rank Pruning or exceeds it on CIFAR, particularly at large noise rates, while pruning can remove correctly labeled but confusing examples.On harder problems, less confident predictions can lead to more pruning; lowering the classification threshold to 0.3 removes the reported performance difference in the described CIFAR case.

5 Discussion

Rank Pruning combines consistent noise-rate estimation with confident-example pruning and remains general across classifiers and implementations. The discussion emphasizes robustness under imperfect modeling and broad evaluation settings.

  • Rank Pruning achieves similar or better F1, error, and AUC-PR than state-of-the-art methods across synthetic, MNIST, and CIFAR scenarios.The evaluation spans logistic regression and CNN classifiers, varying noise rates, added noise, dimension, separability, and sample size.
  • Rank Pruning accurately uncovers classifications from hidden labels and is perfect when the classifier range separates P and N.
  • When g is unassuming, Rank Pruning remains robust to imperfect g(x) within a range-separable subset, even with inexact noise-rate estimates.
  • The presented basic model prioritizes generality despite variants achieving significantly higher F1 on MNIST and CIFAR.The experiments use logistic regression, a generic CNN, and 3-fold cross-validation, while reporting only the simplest non-parametric version.
  • Rank Pruning reframes noisy-data learning around confident examples, which can reveal the true relationship P(y = 1|x) even when many examples are mislabeled.

A Proofs

The proofs analyze Rank Pruning under class-conditional label noise, with independent flips for positive and negative examples. They establish a fundamental ideal-condition equation while relying on infinite hidden class distributions for several results.

  • The proof framework assumes a class-conditional Classification Noise Process with independent flip rates ρ1 and ρ0.It also requires ρ1 + ρ0 < 1 as a necessary condition.
  • Several lemmas and theorems assume P and N contain infinitely many examples, treating them as the true hidden distributions.
  • Under an ideal classifier and non-overlapping P and N supports, g(x) equals (1 −ρ1) for true positives and ρ0 for true negatives.This is the fundamental equation used in the proofs.
  • The proof derives the ideal equation by expanding the observed-positive probability over the two true classes and applying class-conditional noise.

A.1 Proof of Lemma 1

The proof of Lemma 1 uses the ideal classifier and non-overlapping supports to partition observed noisy sets according to their hidden true classes. It then relates pruning thresholds to the asymmetric noise rates.

  • The proof computes thresholds LBy=1 and UBy=0 from the class-separated supports before applying the noisy-set partition.
  • The threshold derivation expands expected observed-positive probabilities using the class-conditional noise model.
  • The condition ρ1 + ρ0 < 1 excludes π1 = 1 and similarly establishes π0 ∈[0, 1).
  • The threshold bounds become exact at the corresponding endpoints when π1 = 0 or π0 = 0.
  • Under ideal g and non-overlapping supports, the observed noisy sets partition into four subsets defined by true class and observed label.These subsets distinguish correctly and incorrectly labeled positives and negatives.

A.2 Proof of Theorem 2

The proof of Theorem 2 reuses Lemma 1 under ideal classification and non-overlapping supports. It connects the resulting partition to the asymmetric flip probabilities.

  • Theorem 2 assumes an ideal g and non-overlapping supports for P and N.
  • The proof invokes Lemma 1 to obtain the partition of observed sets by hidden class and observed label.
  • Using ρ1 = P(s = 0|y = 1) and ρ0 = P(s = 1|y = 0), the proof identifies the corresponding mislabeled fractions.

A.3 Proof of Lemma 3

The proof establishes Lemma 3 by first deriving bounds under perfect probability estimation and then extending them to imperfect estimation with overlapping class supports.

  • Lemma 3 considers imperfect probability estimates and potentially overlapping positive and negative supports.The estimation error is represented by ∆g(x) := g(x) − g∗(x).
  • The proof first calculates LBy=1 and UBy=0 under unassuming conditions before deriving the confidence noise-rate estimates.
  • For a perfect classifier, P(ŷ = 1, y = 0) equals P(ŷ = 0, y = 1) under the stated noisy-label setting.

I. Calculating LBy=1 and UBy=0 when g(x) = g∗(x) and support may overlap

This section derives the bounds LBy=1 and UBy=0 when support overlaps, accounting for imperfect probability estimates and showing how the resulting bounds upper-bound the noise-rate estimates.

  • With overlapping support, P(y = 1|x) is not an indicator, so the bounds incorporate class-conditional uncertainty.
  • The ideal lower bound is reduced by a non-positive correction when positive and negative supports overlap.
  • Equations (A.8) and (A.9) provide LBy=1 and UBy=0 for imperfect g under overlapping support.
  • Under conditional independence of s and x given y, the mislabeled subsets preserve the corresponding noise-rate proportions.
  • The derived equations show that the confidence estimates ˆρconf_i are upper bounds on ρ_i for i = 0, 1.
  • When support does not overlap, deviations in the confidence estimates arise only from imperfect g(x), because overlap contributions vanish.

A.5 Proof of Theorem 5

Theorem 5 shows that when the classifier range separates the classes and the noise rates are correctly estimated, Rank Pruning has the same expected risk as learning from true labels.

  • Rank Pruning keeps examples above k1 from the observed positive set and below k0 from the observed negative set.The thresholds are selected by ranked classifier scores using estimated class proportions.
  • The supporting construction assumes class-conditional label noise and uses the partition of P and N by observed labels.
  • When g’s range separates P and N, the confidence sets are uniform downsamplings of P and N with ratios 1 − ρ1 and 1 − ρ0.
  • Reweighting the retained examples restores class balance after pruning.
  • The expected risk with corrupted labels equals the expected risk with true labels for any classifier and bounded loss under the theorem’s conditions.

C Additional Tables

The additional tables document experimental comparisons across MNIST and CIFAR-10, classifiers, metrics, and noise-handling methods, while also exposing sensitivity to classifier quality.

  • The experiments compare RP, Nat13, Elk08, Liu16, a true-label classifier, and RPρ using error, AUC-PR, and F1.
  • Noise rates are supplied to baseline methods, whereas RPρ uses noise rates estimated by Rank Pruning.
  • Figure B1 visualizes average MNIST digits and indicates that Rank Pruning makes few mistakes under substantial mislabeling.
  • Liu16 can collapse to predicting all labels identically, producing constant metric values across scenarios.For example, its all-positive and all-negative predictions yield different fixed F1 and error values, while AUC-PR remains 0.55.
  • The tables cover one-vs-rest MNIST and CIFAR-10 with logistic regression and CNN classifiers.
  • Logistic regression severely underfits CIFAR, causing RP and RPρ to prune some correctly labeled confusing examples.
Loading 1705.01936v3…