PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Noise Transition Matrix from Only Noisy Labels via Total Variation Regularization

Yivan Zhang, Gang Niu, Masashi Sugiyama

arXiv:2102.02414v2stat.MLcs.LG

TL;DR

Estimating transition matrices from noisy labels is difficult when noisy class-posterior estimates are unreliable and the transition matrix and clean posterior are not identifiable without additional assumptions. The paper uses total variation regularization to estimate the matrix while learning a classifier, assuming anchor points exist. It reports favorable benchmark and real-world results, with theoretical consistency under mild conditions.

  • Problem

    With both the transition matrix and clean class-posterior unknown, observationally equivalent models prevent their identification without an additional assumption, and noisy-posterior estimates may be inaccurate due to neural-network overconfidence.

    Source: §2.3 · p. 3, §2.4 · p. 4

  • Method

    The method regularizes predicted probabilities with total variation to find the “cleanest” posterior while estimating the noise transition matrix and learning a classifier simultaneously.

    Source: §1 · p. 2

  • Results

    On benchmark datasets, the proposed methods performed well in accuracy and usually had lower transition-matrix estimation error than baselines; on real-world data, the method outperformed baselines in accuracy.

    Source: §6.1 · p. 8, §6.2 · p. 9

  • Takeaways & Limitations

    Under mild conditions, total variation regularization is theoretically guaranteed to find the optimal transition matrix despite observationally equivalent models.

    Source: §7 · p. 9

    The method assumes anchor points exist to guarantee identifiability, although it does not explicitly model or detect them.

    Source: §1 · p. 2

Abstract

from arXiv · show

Many weakly supervised classification methods employ a noise transition matrix to capture the class-conditional label corruption. To estimate the transition matrix from noisy data, existing methods often need to estimate the noisy class-posterior, which could be unreliable due to the overconfidence of neural networks. In this work, we propose a theoretically grounded method that can estimate the noise transition matrix and learn a classifier simultaneously, without relying on the error-prone noisy class-posterior estimation. Concretely, inspired by the characteristics of the stochastic label corruption process, we propose total variation regularization, which encourages the predicted probabilities to be more distinguishable from each other. Under mild assumptions, the proposed method yields a consistent estimator of the transition matrix. We show the effectiveness of the proposed method through experiments on benchmark and real-world datasets.

1. Introduction

The paper studies class-conditional label noise, where an unknown transition matrix governs label corruption, and addresses the unreliability of estimating noisy class-posteriors with overconfident neural networks. It proposes total variation regularization to estimate the transition matrix and learn a classifier simultaneously, assuming anchor points exist for identifiability.

1. Introduction

  • In class-conditional noise, labels flip between classes according to an unknown transition matrix, while deep models can overfit noisy training labels.The paper frames this as a longstanding classification problem made more important by large-scale datasets with imperfect labels.Source: §1 · p. 1
  • Earlier transition-matrix methods use anchor points and noisy class-posterior estimates, which can be inaccurate because neural networks are overconfident.The paper notes that errors in this estimation stage threaten two-step methods.Source: §1 · p. 1
  • The proposed approach avoids estimating the noisy class-posterior and assumes anchor points exist for identifiability, without explicitly modeling or detecting them.The paper notes that decomposing the noisy posterior into the transition matrix and clean posterior is not always unique.Source: §1 · pp. 1–2
  • Because the transition mapping contracts total variation distance, the method regularizes predicted probabilities to find the “cleanest” posterior and consistently estimate the transition matrix.The method learns the classifier and transition matrix simultaneously under mild conditions.Source: §1 · p. 2
  • The paper constructs a partial order over equivalent transition matrices and proposes a Dirichlet-based estimator, with a neural classifier and transition-matrix posterior in its model.Its objective combines noisy-label cross-entropy with total variation regularization of predicted probabilities.Source: §1 · p. 2, Figure 1 · p. 2

2. Problem: Class-Conditional Noise

The section defines class-conditional label noise and explains why learning with an unknown transition matrix is difficult: noisy-posterior estimates can be overconfident, while the transition matrix and clean posterior are not jointly identifiable without added assumptions.

2.1. Noisy Labels

  • Noisy labels make the clean-label prediction task harder; the paper models corruption explicitly and aims to predict true labels from noisy-labeled examples.The observed label is denoted eY, and the true label is Y.Source: §2.1 · p. 2

2.2. Class-Conditional Noise (CCN)

  • Under class-conditional noise, the noisy label depends on the true label but not on X, and T maps the clean class-posterior to the noisy class-posterior.The transition matrix is row-stochastic, with entries Tij = p(eY = j|Y = i).Source: §2.2 · p. 2
  • The transition matrix maps the probability simplex into Conv(T); symmetric noise leaves the decision boundary unchanged, while different matrices can affect it differently.The section assumes diagonal dominance for noisy-label learning, though the formulation can also apply to complementary labels.Source: §2.2 · p. 2, Figure 2 · p. 3

2.3. Learning with Known Noise Transition Matrix

  • When T is known, the clean class-posterior is identifiable from the noisy class-posterior; when both are unknown, multiple pairs can yield the same noisy posterior.Without an additional assumption, T and the clean class-posterior cannot both be estimated from the noisy class-posterior.Source: §2.3 · p. 3

2.4. Learning with Unknown Noise Transition Matrix

  • Two-step methods estimate T using anchor points, but their noisy-posterior estimates can be overconfident and lead to transition-matrix errors.Anchor points are instances whose clean posterior assigns probability 1 to a class; the paper's method instead uses the product of estimated T and clean posterior without directly estimating the noisy posterior.Source: §2.4 · pp. 3–4

3. Motivation

The section studies ambiguity among transition-matrix solutions and uses contraction under total variation to order equivalent matrices. This order identifies (I, T) as the unique greatest element, motivating simultaneous estimation of the clean posterior and T.

3. Motivation

  • The contraction property of stochastic matrices induces a partial order within an equivalence class, which can be used to find the “cleanest” clean class-posterior.The section uses this structure to motivate the proposed method.Source: §3 · p. 4

3.1. Transition Matrix Equivalence

  • Equivalent transition-matrix pairs can produce the same product, so optimal fits may include (T, I), which predicts the noisy class-posterior instead of recovering the clean one.For a non-identity product, the equivalence class contains at least (W, I) and (I, W).Source: §3.1 · p. 4

3.2. Transition Matrix Decomposition

  • With anchor points for each class, an optimal estimated posterior can be expressed as U^T p(Y|X), so it may still contain class-conditional noise.Anchor points are sufficient but not necessary for this decomposition, and the method does not explicitly estimate U.Source: §3.2 · pp. 4–5

3.3. Transition Matrix as a Contraction Mapping

  • Stochastic-matrix multiplication contracts total variation distance on the probability simplex, providing the basis for comparing candidate transition matrices.The section introduces the contraction property as a way to distinguish the “cleanest” posterior.Source: §3.3 · p. 5

3.4. Transition Matrix Partial Order

  • The pair (I, T) is the unique greatest element under the transition-matrix partial order, and gradually increasing total variation can find it.The order supports simultaneous estimation of p(Y|X) and T.Source: §3.4 · p. 5

4. Proposed Method

The method uses total variation regularization to favor more distinguishable predictions, and trains the classifier and transition matrix together. A Dirichlet posterior update offers an alternative to gradient-based transition-matrix estimation.

4.1. Total Variation Regularization

  • Total variation regularization combines the KL-divergence learning objective with expected pairwise total variation to favor more distinguishable predictions.The regularization weight γ controls its importance, and sampling a fixed number of pairs can reduce its additional computational cost.Source: §4 · p. 5, §4.1 · pp. 5–6
  • Under anchor-point and compactness assumptions, the constrained objective yields a consistent estimator of the transition matrix.The regularizer favors the clean class-posterior with the highest pairwise total variation.Source: §4.1 · p. 5

4.2. Transition Matrix Estimation

  • The method estimates the classifier and transition matrix in a one-step training procedure.Gradient-based optimization is one option; the proposed alternative models transition-matrix uncertainty with Dirichlet distributions and updates their concentration parameters using the confusion matrix.Source: §4.2 · p. 6
  • The Dirichlet posterior update samples transition matrices during training, while its variance changes to reflect estimation uncertainty.The posterior has higher variance early in training and concentrates as the model converges.Source: §4.2 · p. 6

5. Related Work

Related work addresses noisy-label classification through robust losses, data-selection and other classifier-training strategies, and transition-matrix estimation. The paper contrasts its approach with methods that avoid estimating the transition matrix and a concurrent one-step method.

5. Related Work

  • The paper situates transition-matrix estimation among methods that explicitly use the matrix and two-step methods that detect anchor points from noisy data.It also reviews broader approaches to learning from noisy labels.Source: §5 · p. 6
  • Robust losses can alleviate label noise without estimating the noise rate under conditions such as symmetric noise, but may perform poorly when noise is heavy and complex.Other classifier-robustness approaches include sample selection, rejection, meta-learning, and semi-supervised learning; they may have limited consistency guarantees and higher computational cost or model complexity.Source: §5 · pp. 6–7
  • Li et al. (2021) concurrently used one-step training for class-conditional noise, with an assumption weaker than this paper’s but an additional transition-matrix term that may be incompatible with derivative-free optimization.Their approach uses transition-matrix characteristics rather than properties of the clean class-posterior.Source: §5 · p. 7

6. Experiments

Experiments evaluate the method on benchmark datasets with several noise types and on Clothing1M using noisy training data. The authors report lower transition-matrix estimation error in most benchmark settings and better accuracy than baselines on Clothing1M.

6.1. Benchmark Datasets

  • Benchmark evaluation covers MNIST, CIFAR-10, and CIFAR-100 under symmetric, pair-flipping, tridiagonal, and random noise, among other settings.Pair2 noise is formed by multiplying two pair-flipping matrices, allowing multiple decompositions of the transition matrix.Source: §6.1 · pp. 7–8
  • In most benchmark settings, the proposed methods have lower transition-matrix estimation error than baselines, sometimes by a large margin.Accuracy is also reported as strong; Dual-T is superior in some settings but has at least twice the computational cost of the proposed methods.Source: Table 2 · p. 8, §6.1 · p. 8
  • The benchmark study reports test accuracy and average total variation across 10 trials, with outperforming methods marked using one-tailed t-tests at significance level 0.05.The average total variation evaluates transition-matrix estimation.Source: §6.1 · p. 8

6.2. Real-World Dataset

  • On Clothing1M, the proposed method outperformed baselines in accuracy, while its estimated transition matrix has no ground-truth matrix available for evaluation.The study used only the 1M noisy training examples; the matrix may nevertheless reveal category relationships of interest.Source: Table 3 · p. 9, §6.2 · p. 9

7. Conclusion

The paper addresses observationally equivalent models by regularizing with a partial order derived from characteristics of the true model under realistic assumptions. It reports that total variation regularization is theoretically guaranteed to find the optimal transition matrix under mild conditions, consistent with benchmark experiments.

7. Conclusion

  • Total variation regularization is theoretically guaranteed to find the optimal transition matrix under mild conditions.The paper says this guarantee is reflected in experiments on benchmark datasets.Source: §7 · p. 9
  • The method estimates the noise transition matrix and learns a classifier simultaneously from only noisy data.Source: §7 · p. 9
  • A partial order regularizes the search for characteristics of the true model among observationally equivalent models.Source: §7 · p. 9

A. Beyond Class-Conditional Noise

This section situates the work's focus on multiclass class-conditional noise among other noise models. It notes that the method may be less suitable for mutual contamination and may approximate instance-dependent noise without theoretical guarantees.

A. Beyond Class-Conditional Noise

  • The paper focuses on multiclass class-conditional noise, while other noise models, including approaches that do not explicitly model label corruption, are outside its discussion.Random classification noise and binary class-conditional noise are presented as special cases in the background.Source: A. Beyond Class-Conditional Noise · p. 13
  • The method may not work well under mutual contamination because it explicitly relies on the i.i.d. assumption.Mutual contamination corrupts p(X|Y) rather than p(Y|X), and class-conditional noise is a special case of it.Source: A. Beyond Class-Conditional Noise · p. 13
  • Instance-dependent noise removes the class-conditional assumption, making the transition matrix a matrix-valued function of the instance.The section describes this setting as harder to estimate.Source: A. Beyond Class-Conditional Noise · p. 13
  • For instance-dependent noise, the transition matrix varies with the instance, and the method may serve as a practical approximation without theoretical guarantees.The section also notes that regularization techniques may inspire practical algorithm design for this setting.Source: A. Beyond Class-Conditional Noise · p. 13

B. Overconfidence in Neural Networks

Neural-network overconfidence makes noisy class-posterior estimation unreliable for transition-matrix estimation. The section explains that noisy-label training can produce probabilities outside the transition matrix's convex hull, while the proposed approach avoids estimating that posterior directly.

B. Overconfidence in Neural Networks

  • Accuracy-calibrated losses can yield asymptotically optimal accuracy without recovering the class-posterior.Source: B. Overconfidence in Neural Networks · p. 14
  • Anchor-point transition-matrix methods rely on confidence-calibrated noisy class-posterior estimates from neural networks.The section notes that recalibration methods have been developed to alleviate overconfidence.Source: B. Overconfidence in Neural Networks · p. 14
  • Noisy class-posterior estimation has a significantly worse overconfidence issue than clean class-posterior estimation.The comparison uses a Gaussian-mixture dataset and a three-layer MLP.Source: B. Overconfidence in Neural Networks · p. 14
  • Without the convex-hull constraint, noisy-label training can produce overconfident probabilities outside Conv(T), which may degrade two-step transition-matrix estimation.The constraint also affects how difficult confidence recalibration may be.Source: B. Overconfidence in Neural Networks · p. 14
  • The method estimates the noisy class-posterior with the product of the transition matrix and clean class-posterior, avoiding direct neural-network estimation of the noisy posterior.The clean class-posterior may still be overconfident; post-hoc recalibration can be used when its confidence is needed.Source: B. Overconfidence in Neural Networks · p. 14

C. Proof

The proof establishes consistency of the transition-matrix estimator under stated assumptions and uses a decomposition result to characterize equivalent models. The intuition section links identifiability to selecting the “cleannest” posterior, with anchor points providing uniqueness.

C. Proof

  • Under the theorem's assumptions, the optimized transition matrix is a consistent estimator of the true transition matrix.The setup assumes a finite i.i.d. sample, anchor points for every class in the sample, and a compact parameter space.Source: C. Proof · p. 15
  • The decomposition theorem states that if two row-stochastic matrices generate the same outputs for every simplex input, one factors through the other via a row-stochastic matrix.Source: C. Proof · p. 15
  • Among zero-loss solutions, the proof uses total-variation contraction to show that the regularizer is no greater than its value at the ground-truth posterior.The argument compares transformed posteriors with the clean posterior and then with the ground-truth model.Source: C. Proof · p. 15

D. Intuition

  • Matching the noisy posterior alone permits multiple feasible transition-matrix and clean-posterior pairs when the function class is sufficiently large.The intuition section therefore seeks the “cleannest” feasible posterior rather than intermediate possibilities.Source: D. Intuition · p. 16
  • Anchor points for every class guarantee uniqueness of the “cleannest” clean posterior and transition matrix in the paper's argument.Source: D. Intuition · p. 16
  • Without anchor points for all classes, the algorithm may still work in practice, but the paper provides no theoretical guarantee.Source: D. Intuition · p. 16

E.1. Benchmark Datasets

Across MNIST, CIFAR-10, and CIFAR-100 experiments, the Dirichlet posterior update method usually estimates transition matrices better across noise types. The experiments use several synthetic noise settings and dataset-specific models and optimization schedules.

E.1. Benchmark Datasets

  • Experiments used MNIST, CIFAR-10, and CIFAR-100 with a clean baseline, symmetric noise (50%), pair-flipping noise (40%), and composed pair-flipping noise (30% and 20%; overall 44%).Source: §E.1 · p. 17
  • MNIST uses a sequential convolutional network, while CIFAR-10 and CIFAR-100 use ResNet-18; optimization schedules differ by dataset.MNIST uses Adam; the CIFAR datasets use SGD with momentum and weight decay.Source: §E.1 · p. 18
  • Hyperparameters were grid-searched on a small experiment and then fixed across settings, without tuning for each noise type.The authors note that noise-specific prior knowledge could support a better initialization.Source: §E.1 · p. 18
  • The proposed method, especially the Dirichlet posterior update method, usually estimates transition matrices better across noise types; Dual-T performs well in some settings.The results include transition-matrix heat maps in addition to accuracy and average total variation in Tables 1 and 2.Source: §E.1 · p. 18

E.2. Clothing1M

The Clothing1M experiment uses noisy training data and clean test data from a 14-class real-world dataset. It follows prior work's model and optimization setup.

E.2. Clothing1M

  • The Clothing1M experiment uses 1 million noisy training images and 10,526 clean test images from 14 classes.The dataset also has 47,570 clean training images and 14,313 clean validation images, but the experiment uses only noisy training data and clean test data.Source: §E.2 · p. 18
  • The experiment follows prior work with an ImageNet-pretrained ResNet-50, trained using SGD on 64 GPUs for 5,000 iterations.The learning rate is 1 × 10^-3 for the first half of training and 1 × 10^-4 for the second half.Source: §E.2 · p. 18
  • The concentration matrix is initialized with diagonal elements of 1 and off-diagonal elements of 0; β = (0.999, 0.01) and γ = 0.1.Average runtime is about 15 minutes without SyncBatchNorm and 25 minutes with it.Source: §E.2 · p. 18

Related papers

Loading 2102.02414v2…