PaperlayerView exact revision on arXiv

Source-linked AI summary

Clusterability as an Alternative to Anchor Points When Learning with Noisy Labels

Zhaowei Zhu, Yiwen Song, Yang Liu

arXiv:2102.05291v2cs.LGcs.AIstat.ML

TL;DR

Learning with noisy labels depends on estimating the transition matrix, but anchor-point approaches face practical estimation constraints. This paper estimates the matrix from neighbor-label consensuses under clusterability, and reports unique identification under stated conditions and empirical advantages across synthetic and human-noise settings.

  • Problem

    Estimating the noise transition matrix without clean labels is challenging, and anchor-point methods depend on finding examples that almost surely belong to a class.

    Source: §1 · p. 1

  • Method

    Under clusterability, HOC estimates T using first-, second-, and third-order consensuses among an example's two nearest neighbors' noisy labels.

    Source: §1 · pp. 1–2, §3.2 · p. 5

  • Results

    HOC reports a 0.097 estimation error in the global T on self-collected human-level CIFAR-10, alongside estimator advantages across synthetic CIFAR-10/100 and human-noise Clothing1M/CIFAR-10 studies.

    Source: §1 · p. 2, §5.2 · p. 9

  • Takeaways & Limitations

    Compared with anchor-point methods, the estimator uses substantially more instances, has better sample complexity, and is presented as potentially applicable to instance-dependent noise.

    Source: §1 · p. 2

    Anchor-point methods can be constrained by noisy-distribution fitting at high class counts and by the number of available, identifiable anchors.

    Source: §1 · p. 1, §2.2 · p. 3

Abstract

from arXiv · show

The label noise transition matrix, characterizing the probabilities of a training instance being wrongly annotated, is crucial to designing popular solutions to learning with noisy labels. Existing works heavily rely on finding "anchor points" or their approximates, defined as instances belonging to a particular class almost surely. Nonetheless, finding anchor points remains a non-trivial task, and the estimation accuracy is also often throttled by the number of available anchor points. In this paper, we propose an alternative option to the above task. Our main contribution is the discovery of an efficient estimation procedure based on a clusterability condition. We prove that with clusterable representations of features, using up to third-order consensuses of noisy labels among neighbor representations is sufficient to estimate a unique transition matrix. Compared with methods using anchor points, our approach uses substantially more instances and benefits from a much better sample complexity. We demonstrate the estimation accuracy and advantages of our estimates using both synthetic noisy labels (on CIFAR-10/100) and real human-level noisy labels (on Clothing1M and our self-collected human-annotated CIFAR-10). Our code and human-level noisy CIFAR-10 labels are available at https://github.com/UCSC-REAL/HOC.

1. Introduction

The introduction presents transition-matrix estimation as important to noisy-label learning, but difficult when methods depend on identifying anchor points. It proposes clusterability-based estimation as an alternative and situates the need for transition matrices in risk-consistent and local-noise approaches.

1. Introduction

  • Wrong annotations in large labeled datasets can be memorized by over-parameterized DNNs and lead to unexpected, disparate impacts.The supplied introduction passage is split across p00 and p01.Source: §1 · p. 1
  • Accurate knowledge of the noise transition matrix T supports risk-consistent methods, while existing estimators often rely on examples that almost surely belong to a particular class.The paper describes T as characterizing the probability that a training example is wrongly annotated.Source: §1 · p. 1
  • Anchor-point estimation can be constrained by noisy-distribution fitting at high class counts, limited anchor availability, and inflexibility for more complicated noise settings.Confident-learning methods may avoid explicitly identifying anchors but still fit noisy distributions and seek confident points.Source: §1 · p. 1
  • The proposed estimator uses high-order noisy-label consensuses among neighboring representations, uses more training examples than anchor-based methods, and is reported to have better sample complexity.The paper also states that up to third-order consensuses suffice for unique identification and reports studies on synthetic and human-noise datasets.Source: §1 · p. 2

1.1. Related Works

  • Some risk-consistent approaches avoid estimating T, but local transition matrices remain useful for instance-dependent noise and related applications.The cited examples include data groups, confidence-based revisions, and second-order information about local transition matrices.Source: §1.1 · p. 2
  • Other noisy-label approaches design bounded losses or select reliable samples without estimating T.The paper says it compares some popular approaches experimentally.Source: §1.1 · p. 2

2. Preliminaries

The preliminaries define the noisy-label setting and explain why estimating the transition matrix matters for corrected learning. They contrast anchor-point estimation with a clusterability-based alternative that uses nearby representations without requiring their true class labels.

2.1. Our Setup

  • Training examples pair features with clean labels in the unobserved dataset and noisy labels in the dataset available to the learner; T(X) gives the probability of each noisy label given a clean label and feature.When noise is feature-independent, T(X) is constant and denoted T.Source: §2.1 · p. 2

2.2. Loss Correction and Estimating T

  • The task is to learn a classifier minimizing cross-entropy risk, and knowing T enables corrected losses whose noisy-distribution minimizer matches the clean-risk minimizer.Transition-matrix knowledge may also help with instance-dependent noise, fairness guarantees, and hyperparameter choices in sample selection and label smoothing.Source: §2.1 · pp. 2–3, §2.2 · p. 3
  • An anchor point belongs almost surely to one class, allowing its noisy-label posterior to reveal a row of T, but estimation depends on fitting noisy-label posteriors and having enough identifiable anchors.The approach is also less flexible for estimating local transition matrices.Source: §2.2 · p. 3

2.3. Clusterability

  • k-NN label clusterability requires each example and its k nearest representations to share a clean class; larger k makes the condition harder to satisfy.Same-class clusters need not form one continuum, and the condition does not require specifying the true class.Source: §2.3 · p. 3
  • The paper focuses on 2-NN clusterability, motivated by settings where nearby representations share labels, and uses higher-order consensuses of neighbors’ noisy labels rather than simple neighbor votes.The authors state that this requires only 2-NN clusterability, a weaker condition than requiring more neighbors to share the clean class.Source: §2.3 · p. 4
  • Unlike anchor-point estimation, clusterability does not require identifying the true class; with good representations already available, the proposed approach is model-free.Anchor-point methods rely on a trained classifier to identify anchors and their classes.Source: §2.3 · p. 4

3. The Power of High-Order Consensuses

The section estimates the noise transition matrix T from high-order noisy-label consensuses among an instance and its two nearest neighbors, under a clusterability condition. It develops the consensus equations, an estimator, and a local extension for instance-dependent noise.

3.1. Warm-up: A Binary Example

  • First-, second-, and third-order consensus probabilities among an instance and its two nearest neighbors provide the statistics used to estimate T.The probability of each consensus pattern can be estimated from the noisy dataset.Source: §3.1 · p. 4

3. The Power of High-Order Consensuses

  • Under 2-NN label clusterability, up to third-order noisy-label consensus probabilities jointly identify a unique transition matrix T.The consensus patterns use labels from an instance and its two nearest neighbors.Source: §3.1 · p. 4

3.2. Estimating T : The General Form

  • For K classes, the method expresses first-, second-, and third-order consensus probabilities in vector form to construct equations for T and the clean-label prior p.The equations rely on 2-NN label clusterability and conditional independence of noisy labels given clean labels.Source: §3.2 · p. 5

3.3. The HOC Estimator

  • The HOC estimator finds each example’s two nearest neighbors, estimates consensus probabilities from their noisy labels, then jointly optimizes T and p.It samples center indices repeatedly because overlapping neighbor tuples may violate the i.i.d. condition needed for consistent estimates.Source: §3.3 · pp. 5–6

Challenges for solving the constrained optimization

  • Softmax reparameterization turns the constrained optimization over T and p into an unconstrained problem while preserving T’s uniqueness property.The reparameterization maps unconstrained variables to probability measures and retains the transition probabilities outside corner cases.Source: Challenges for solving the constrained… · p. 6

3.4. Flexible Extensions to Instance-Dependent Noise

  • Local estimates can address instance-dependent noise when neighboring representations share the same local transition matrix and the data satisfy (H, M)-coverage.The method applies the estimator separately to local subsets; without local noise clusterability, properly constructed subspaces may be needed.Source: §3.4 · pp. 6–7

4. Theoretical Guarantees

The theoretical results establish when the consensus equations uniquely recover the true transition matrix and compare their sample complexity with anchor-point estimation. The guarantees rely on clusterability and properties of the transition matrix, with sample-complexity results given under additional conditions.

4.1. Uniqueness of Solution

  • With 2-NN label clusterability and a nonsingular, informative T, exact first- through third-order consensus probabilities uniquely recover the true T.The diagonal entries of an informative T are dominant over its off-diagonal entries.Source: §4.1 · p. 7
  • For a locally clusterable dataset, exact local consensus probabilities uniquely recover the local transition matrix when it is nonsingular and informative.This extends the uniqueness result to local datasets where T can vary across instances.Source: §4.1 · p. 7

4.2. Sample Complexity

  • Theorem 2’s estimate has the same order in N as standard empirical-mean estimation, while the anchor-point comparison uses fewer than N points and has worse sample complexity.The stated analysis assumes a dataset and feature extractor with |E*3| = Θ(N) and a uniform diagonal T.Source: §4.2 · p. 7

5. Experiments

The experiments evaluate HOC on synthetic and human label noise, comparing transition-matrix estimation, classification accuracy, and 2-NN clusterability. HOC has lower estimation error than T-Revision across the tested loss settings, while local estimates improve CIFAR-10 performance and feasibility ratios remain high in most cases.

5. Experiments

  • HOC is evaluated on CIFAR-10, CIFAR-100, and Clothing1M using synthetic symmetric and instance-dependent noise, plus human annotations.For CIFAR-10, the authors recollected human annotations for 50,000 training images; Clothing1M uses one million noisy training instances.Source: §5 · pp. 7–8

5.1. Performance of Estimating T

  • HOC achieves lower transition-matrix estimation error than T-Revision with both forward-corrected and reweighted losses under symmetric noise.The comparison uses the normalized matrix L1,1 error; HOC does not require epoch-by-epoch adaptation.Source: Figure 3 · p. 8, §5.1 · p. 8

5.2. Performance of Classification Accuracy

  • On synthetic instance-dependent and real human-label noise, global and local HOC estimates achieve satisfying classification performance, with local estimates improving CIFAR-10 results.For CIFAR-100, local estimation has a slight performance drop because estimating 10k transition-matrix variables from 10k instances may be inaccurate, but it still outperforms other methods.Source: Table 1 · p. 8, §5.2 · p. 9, Table 2 · p. 9

5.3. Feasibility of 2-NN label clusterability

  • More than two-thirds of 2-NN tuples are feasible in most tested cases, and sampling 5k rather than 50k examples does not substantially reduce the feasible-tuple ratio.A tuple is feasible when the example and its two nearest neighbors belong to the same true class.Source: §5.3 · p. 9, Table 3 · p. 9

6. Conclusions

The paper concludes that HOC estimates the noise transition matrix using first-, second-, and third-order noisy-label consensuses among an example and its two nearest neighbors.

6. Conclusions

  • HOC estimates the noise transition matrix by checking first-, second-, and third-order consensuses among an example and its 2-NN noisy labels.The authors identify more efficient local estimation and collaboration with other noisy-label techniques as future directions.Source: §6 · p. 9

Proof Sketch for Theorem 1

The proof transforms second- and third-order consensus equations into matrix and vector constraints, then establishes that only K distinct feasible rows determine T uniquely. The appendix also outlines related proofs, assumption discussions, and additional experimental material.

Proof Sketch for Theorem 1

  • Second- and third-order consensus equations are transformed into matrix relations, then into quadratic constraints on rows of T.The proof seeks to show that any additional feasible row duplicates one of the existing K rows.Source: Proof Sketch for Theorem 1 · p. 9
  • When T is nonsingular, the constructed (K + 1)-th feasible vector must duplicate an existing row, leaving only K distinct feasible rows.The informativeness of T fixes the ordering of those rows, establishing uniqueness.Source: Proof Sketch for Theorem 1 · p. 9

Appendix

  • The appendix covers consensus-equation derivations, proofs of uniqueness and other theoretical results, assumption feasibility, and further experiments.It also discusses soft 2-NN label clusterability and local transition matrices.Source: Appendix · p. 13

A. Derivation of Consensus Equations

The appendix derives first-, second-, and third-order consensus equations using clusterability and conditional independence. It then uses these constraints to establish uniqueness under stated assumptions and discusses when the feasible-triple count can grow linearly with dataset size.

A. Derivation of Consensus Equations

  • First-, second-, and third-order consensus equations factor noisy-label probabilities across neighbors using clusterability and conditional independence given clean labels.The derivation presents two first-order, four second-order, and eight third-order combinations in the binary example.Source: A. Derivation of Consensus Equations · pp. 13–14

B.1. Uniqueness of T

  • Second- and third-order consensus constraints are transformed into matrix equations and then a quadratic system over candidate rows of T.The first-order consensus is not needed for uniqueness, but helps stabilize numerical solutions for T and p.Source: §B.1 · pp. 15–16, uniqueness of · p. 16

uniqueness of

  • Under nonsingular and informative T, any additional feasible row must duplicate an existing row, so perfect first-, second-, and third-order consensus information identifies the true T uniquely.The proof uses the one-hot conclusion for the coefficients of an extra row, then establishes that only K distinct rows remain.Source: uniqueness of · p. 17

B.2. Feasibility of Assumption |E∗

  • A special representation arrangement yields an expected number of feasible 3-tuples proportional to N, although the example does not establish a general lower bound.The construction assumes the two nearest neighbors are independently and uniformly distributed in the unit square.Source: §B.2 · p. 17

B.3. Proof for Lemma 1

The proof of Lemma 1 uses concentration of sample-mean estimates for high-order consensus patterns. It applies Hoeffding’s inequality to obtain a probability bound.

B.3. Proof for Lemma 1

  • Each high-order consensus pattern is estimated by the sample mean of |E*3| independent, identically distributed random variables.The proof uses this setup for the consensus estimates.Source: §B.3 · p. 17
  • Hoeffding’s inequality is applied to the consensus-pattern sample means.This is the stated concentration argument.Source: §B.3 · p. 17
  • The resulting bound is stated to hold with probability 1 − δ.The supplied passage does not give the full bound expression.Source: §B.3 · p. 17

B.4. Proof for Theorem 2

This block covers the theorem proof and extensions on soft clusterability, local transition matrices, assumption feasibility, and instance-dependent noise generation. The proof relates estimation error to estimated consensus statistics, while the extensions describe robustness and practical scope.

B.4. Proof for Theorem 2

  • A union-bound argument relates the error in estimating Tii to errors in estimated consensus statistics and the clean class prior.The proof also considers a uniform off-diagonal transition matrix and uses constraints on first- and second-order statistics.Source: §B.4 · p. 18

C.1. Soft 2-NN Label Clusterability

  • Soft 2-NN clusterability allows a small probability of differing clean classes, with the stated perturbation yielding estimates at most a factor e from the true T.When e = 0, the original 2-NN clusterability condition is recovered.Source: §C.1 · p. 19

C.2. Local T (X)

  • For sparse local datasets, a logarithmic regularizer on p is proposed because the standard ℓ1 norm is constant when ∥p∥1 = 1.The passage says the regularizer can shrink the search space and support accurate estimates with small M.Source: §C.2 · p. 19
  • Estimating local T across the dataset may require about N/M executions of Algorithm 1; grouping regions with shared T is offered as an alternative, while efficient grouping remains future work.The paper frames its focus as a generic clusterability-based estimator rather than an efficient local-dataset splitting algorithm.Source: §C.2 · p. 19

C.3. Feasibility of Assumption 1 and Assumption 2

  • The feasibility discussion says Assumption 1 requires invertible T for recovering the clean confusion matrix, while Assumption 2 fixes row ordering by requiring Tii > Tij.Without the ordering condition, the passage notes K! possible row permutations.Source: §C.3 · p. 19

D.1. Generating the Instance-Dependent Label Noise

  • The instance-dependent noise procedure samples per-instance flip rates and feature projection weights, then uses them to assign noisy-label probabilities.The rate qn is sampled from a truncated normal distribution centered at η; the method excludes the true class when assigning a wrong label.Source: §D.1 · pp. 19–20

D.2. Basic Hyper-Parameters

The experiments use staged pre-training, global training, and local training, with HOC estimates applied at the start of each stage. On human-noisy CIFAR-10, the reported global and local estimation errors are 0.0970 and a local mean of 0.1103.

D.2. Basic Hyper-Parameters

  • HOC is applied once at the start of pre-training, global training, and local training, and each stage retrains the model.The experiments are repeated three times.Source: §D.2 · p. 20
  • For Clothing1M, the global T is averaged across five random epochs, and only T(X) = T is used in local training.The passage leaves combining T(X) with loss correction or other advanced techniques for future work.Source: §D.2 · p. 20
  • The global estimation error is 0.0970, while local estimation errors have mean 0.1103 and standard deviation 0.0278.Figure 5 illustrates global and local estimation errors; the caption reports the mean and the accompanying passage gives the standard deviation.Source: Figure 5 · p. 21, §D.2 · p. 21

D.3. Global and Local Estimation Errors on CIFAR-10 with Human Noise

The section describes how local transition-matrix rows are completed using global estimates when local class information is insufficient. Figure 5 illustrates the variation in local estimation errors for human-noisy CIFAR-10.

D.3. Global and Local Estimation Errors on CIFAR-10 with Human Noise

  • When a local class prior is zero, the corresponding local transition-matrix row is completed using a weighted average with the global estimate.The row-wise rule uses the estimated local clean-class prior and a dataset-specific ζ value.Source: §D.3 · p. 21
  • Figure 5 illustrates variation in local estimation errors for CIFAR-10 with human noise.The passage identifies HOC as the estimator used for these local estimates.Source: §D.3 · p. 21

Related papers

Loading 2102.05291v2…