Identifiability in Noisy Label Learning: A Multinomial Mixture Modelling Approach

## Abstract

Abstract Learning from noisy labels (LNL) is crucial in deep learning, in which one of the approaches is to identify clean-label samples from poorly-annotated datasets. Such an identification is challenging because the conventional LNL problem, which assumes only one noisy label per instance, is non-identifiable, i.e., clean labels cannot be estimated theoretically without additional heuristics. This paper presents a novel data-driven approach that addresses this issue without requiring any heuristics about clean samples. We discover that the LNL problem becomes identifiable if there are at least 2 ​ C − 1 2C-1 i.i.d. noisy labels per instance, where C C is the number of classes. Our finding relies on the assumption of i.i.d. noisy labels and multinomial mixture modelling, making it easier to interpret than previous studies that require full-rank noisy-label transition matrices. To fulfil this condition without additional manual annotations, we propose a method that automatically generates additional i.i.d. noisy labels through nearest neighbours. These noisy labels are then used in the Expectation-Maximisation algorithm to infer clean labels. Our method demonstrably estimates clean labels accurately across various label noise benchmarks, including synthetic, web-controlled, and real-world datasets. Furthermore, the model trained with our method performs competitively with many state-of-the-art methods.

## 1 Introduction

The significant advances in machine learning over the past decade have led to the development of numerous applications that tackle increasingly-complex problems in many areas, such as computer vision [29, 12], natural language processing (NLP) [2, 52] and reinforcement learning [46, 25]. These solutions often rely on high-capacity models trained on vast amounts of annotated data. The annotation of large datasets often relies on crowd-sourcing services, such as Amazon Mechanical Turk, or automated approaches based on NLP or search engines. This might, generally, produce poor-quality annotated labels, especially when data is ambiguous. Such a subpar annotation, coupled with the well-known issue of deep neural networks being susceptible to overfitting to randomly-labelled data [69], might lead to catastrophic failures, particularly in critical applications such as autonomous vehicles or medical diagnostics. These challenges have spurred research in the field of noisy label learning, aiming at addressing the problem of learning from datasets with noisy annotations.

More specifically, learning from noisy labels (LNL) aims to employ mis-labelled training data to train a classifier that can generalise well. One approach to accomplish this is to infer the clean label $Y$ of an instance $X$ from an observed noisy label $\hat{Y}$. If $C$ is the number of classes, then one can relate $Y$ and $\hat{Y}$ through the sum rule of probability as follows:

$$ $\textstyle{\Pr}(\hat{Y}|X)=\sum_{c=1}^{C}{\Pr}(\hat{Y}|X,Y=c)\,\Pr(Y=c|X).$ (1) $$

In the literature, the clean label probability $\Pr(Y|X)$, the transition probability ${\Pr}(\hat{Y}|X,Y)$ and the noisy label probability ${\Pr}(\hat{Y}|X)$ are modelled as categorical distributions. This, however, results in an ambiguous estimation because there are multiple combinations of hidden probability pair $({\Pr}(\hat{Y}|X,Y),\Pr(Y|X))$ leading to the same observed noisy label probability ${\Pr}(\hat{Y}|X)$.
For example, the following 3-class classification has at least two different solutions that result in the same observed noisy label distribution ${\Pr}(\hat{Y}|X)$:

$$ $\displaystyle\Pr(\hat{Y}|X)=\begin{bmatrix}0.25\\ 0.45\\ 0.3\end{bmatrix}$ $\displaystyle=\underbrace{\begin{bmatrix}0.8&0.1&0.2\\ 0.15&0.6&0.3\\ 0.05&0.3&0.5\end{bmatrix}}_{\Pr_{1}(\hat{Y}|X,Y)}\underbrace{\begin{bmatrix}\nicefrac{{2}}{{11}}\\ \nicefrac{{13}}{{22}}\\ \nicefrac{{5}}{{22}}\end{bmatrix}}_{\Pr_{1}(Y|X)}=\underbrace{\begin{bmatrix}0.7&0.2&0.1\\ 0.1&0.6&0.1\\ 0.2&0.2&0.8\end{bmatrix}}_{\Pr_{2}(\hat{Y}|X,Y)}\underbrace{\begin{bmatrix}\nicefrac{{2}}{{15}}\\ \nicefrac{{7}}{{10}}\\ \nicefrac{{1}}{{6}}\end{bmatrix}}_{\Pr_{2}(Y|X)}.$ $$

Failing to address the LNL identifiability issue might lead to estimating an undesirable model which may not be useful for making predictions or drawing conclusions. Existing LNL methods address the identifiability issue primarily through modelling-driven approaches, often by imposing ad-hoc priors in the form of heuristic assumptions and constraints, such as small-loss criterion [19], anchor points [37] or zero Bayes risk [71]), feature-based methods [28] or unique constraints on the modelling of transition matrix [34, 68]. Other methods follow a data-driven approach with multiple noisy labels per sample [38]. Although methods based on the modelling-driven approach have achieved successful results in several benchmarks, their heuristics are either *(i)* sub-optimal, e.g., small-loss criterion might under-select “hard examples” (i.e., samples that are near decision boundaries) that are informative for learning, or *(ii)* associated with assumptions that might not always hold in practice, e.g., anchor points in [37], zero-error data in [71], or “alignment clusterability” in [28]. In contrast, the data-driven approach tackles the problem more fundamentally without relying on heuristic assumptions; however, current results in methods based on the data-driven approach are difficult to interpret (e.g., full-rank transition matrices [38]), reducing their applicability in practice.

In this paper, we investigate the identifiability issue in LNL following the data-driven approach with multiple noisy labels per training sample. Specifically,

- •
we formulate clean labels in LNL through multinomial mixture models and theoretically derive the identifiability condition, showing that at least $2C-1$ i.i.d. noisy labels are required per training sample, and
- •
we propose a practical method based on nearest neighbours to generate additional i.i.d. noisy label to meet the identifiability condition.

The empirical evaluation of the proposed method evaluated on several LNL benchmarks (including synthetic, web-controlled and real-world label noise problems) demonstrates its capability to estimate clean labels without any heuristics. Furthermore, even though the main goal of this paper is the theoretical investigation of the identifiability condition, our practical method shows competitive results with several state-of-the-art techniques.

## 2 Background

Identifiability  studies whether the exact parameters of a model of interest can be uniquely recovered from observed data. Generally, a model is identifiable if and only if its parameters can be uniquely determined from available data. In contrast, a non-identifiable model implies that there exists multiple sets of parameters, where each set can explain the observed data equally well. Identifiability is particularly important in statistical modelling, where statistical methods are used to infer the true set of parameters from data. Formally, the identifiability of a distribution $\Pr(X;\theta)$ over a random variable $X$, parameterised by $\theta\in\Theta$ with $\Theta$ denoting a parametric space, can be defined as:

###### Definition 1 .

$\Pr(X;\theta)$ is identifiable if it satisfies: $\Pr(X;\theta)=\Pr(X;\theta^{\prime})\implies\theta=\theta^{\prime},\forall\theta,\theta^{\prime}\in\Theta$.

Mixture models  A mixture of $P$ distributions can be written as:
$q(X)=\sum_{c=1}^{P}\pi_{c}\Pr(X;\theta_{c})$,
where $X$ is a random variable in $\mathcal{X}$, $\pi$ is the mixture coefficient vector in the $(P-1)$-dimensional probability simplex $\Delta^{P-1}=\left\{\mathbf{y}:\mathbf{y}\in[0,1]^{P}\wedge\boldsymbol{1}^{\top}\mathbf{y}=1\right\}$, and $\{\Pr(X;\theta_{c})\}_{c=1}^{P}$ is a set of $P$ distributions. Compared to a single distribution, mixture models are more flexible with higher modelling capacity, and hence, widely used to provide computationally convenient representation of complex data distributions.
And since mixture models are an instance of latent variable models, the Expectation - Maximisation (EM) algorithm [11] can be used to infer their parameters.

Identifiability issue in mixture models  is one of the most common problems in statistical inference. For example, if all of the $P$ component distributions in a mixture model $q(X)$ belong to the same parametric family, then $q(X)$ is invariant under $P!$ permutations by simply swapping the indices of the component distributions, a phenomenon known as *label-switching*. In practice, the identifiability issue due to *label-switching* (we will refer to this identifiability issue as label-switching from now on) is of no concern since one can impose an appropriate constraint on its parameters to obtain a unique solution. Nevertheless, parameter identifiability up to the permutation of class labels (we will refer this as identifiability in the remaining of this paper) is still a practical problem, at least in maximum likelihood for mixture models where the distribution components of such mixtures belong to certain distribution families. According to [50, Section 3.1], most mixture models supported on continuous space, e.g., Gaussian mixture models (excluding the mixture of uniform distributions), are identifiable. However, when the support space is discrete, the identifiability of such mixtures might not always hold. For example, a mixture of Poisson distribution [49] or a mixture of negative binomial distribution [61] is identifiable, while a mixture of binomial distributions is only identifiable under certain conditions [49, Proposition 4]. Another example is multinomial mixture models which is, according to the [Theorem 1](https://arxiv.org/html/2301.01405v3#Thmtheorem1) defined below, identifiable if and only if the number of samples is at least almost twice the number of mixture components.

###### Theorem 1 ( [ 26 , Lemma 2.2] , [ 14 , Theorem 4.2] ) .

The class of $N$-trial $C$-category multinomial mixture models:
$\left\{M(\mathbf{x}):M(\mathbf{x})=\sum_{c=1}^{C}\pi_{c}\,\mathrm{Mult}(\mathbf{x};N,\rho_{c})\right\}$
is identifiable (up to label permutation) *if and only if* $N\geq 2C-1$.

###### Definition 1 .

###### Theorem 1 ( [ 26 , Lemma 2.2] , [ 14 , Theorem 4.2] ) .

## 3 Methodology

The first part of this section establishes the data-driven identifiability condition for the LNL problem in the setting where each training sample has multiple i.i.d.​ noisy labels.
The second part introduces a practical method that satisfies the identifiability condition, enabling inference of the clean label distribution when only a single noisy label is available per training sample.

### 3.1 Identifiable condition for noisy label learning

In LNL, the clean label $Y$ is often considered as a latent variable, and hence, the noisy label distribution ${\Pr}(\hat{Y}|X=\mathbf{x}_{i})$ can be modelled as a mixture of $C$ distributions ${\Pr}(\hat{Y}|Y=c,X=\mathbf{x}_{i}),\forall c\in\{1,\dots,C\}$ as in [Eq. 1](https://arxiv.org/html/2301.01405v3#S1.E1). Conventionally, each of the $C$ distributions ${\Pr}(\hat{Y}|Y=c,X=\mathbf{x}_{i})$ is assumed to be a categorical distribution. Here, we expand the capability of such a modelling to the setting of multiple noisy labels by considering each ${\Pr}(\hat{Y}|Y=c,X=\mathbf{x}_{i})$ as a multinomial distributions. Specifically, we model
${\Pr}(\hat{Y}|Y=c,X=\mathbf{x}_{i})=\mathrm{Mult}(\hat{Y};N,\rho_{ic})$ as an $N$-trial multinomial component, and $\Pr(Y=c|X=\mathbf{x}_{i})=\pi_{ic}$ as the corresponding mixture coefficient,
where $N\in\mathbb{Z}_{+}$ is the number of trials in the multinomial components (or number of noisy labels per training sample), $\rho_{ic}\in\Delta^{C-1}$ is the probability parameter of the multinomial component, $\pi_{i}\in\Delta^{C-1}$ is the clean label probability and $c\in\{1,\ldots,C\}$ is the class index. [Eq. 1](https://arxiv.org/html/2301.01405v3#S1.E1) can, therefore, be written in the form of a multinomial mixture model as:

$$ $\textstyle{\Pr}(\left.\hat{Y}\right|X=\mathbf{x}_{i})=\sum_{c=1}^{C}\pi_{ic}\,\mathrm{Mult}(\hat{Y};N,\rho_{ic}).$ (2) $$

The modelling assumption in [Eq. 2](https://arxiv.org/html/2301.01405v3#S3.E2) allows to determine the identifiable condition in LNL by leveraging the result in [Theorem 1](https://arxiv.org/html/2301.01405v3#Thmtheorem1) as follows:

###### Identifiability Condition (Corollary of Theorem 1 ) .

Any noisy label learning problem where the noisy label distribution is modelled as a multinomial mixture model shown in [Eq. 2](https://arxiv.org/html/2301.01405v3#S3.E2) is identifiable *if and only if* there are at least $2C-1$ i.i.d. noisy labels $\hat{Y}$ of an instance $X$ (i.e., $N\geq 2C-1$).

For example, the conventional LNL setting has only one noisy label per sample: ${N=1}$, and hence, is non-identifiable for $C\geq 2$ unless additional assumptions or constraints are introduced. Another example is that binary classification on noisy labels, corresponding to $C=2$, is identifiable if $N\geq 3$, or in other words, there must be at least 3 noisy labels per sample. This agrees with previous studies identifiability for the LNL problem [73, 38].

###### Remark 1 .

Previous work by [38] establishes an identifiability condition that requires at least three noisy labels per instance, each provided by a highly skilled annotator whose associated transition matrix is full rank. This assumption, while theoretically appealing, imposes a significant practical burden: recruiting such highly competent experts is costly and becomes increasingly infeasible as the number of classes $C$ grows. In contrast, our result “transposes” the previous condition, in which at least $2C-1$ i.i.d. noisy labels from the same noisy label distribution ${\Pr}(\hat{Y}|X)$ are required per instance, without any requirement on annotator expertise beyond independence. Although our condition is less optimistic in terms of the number of labels needed, it eliminates the stringent high-skill (i.e., full rank) assumption. Intuitively, [38] relies on a small set of expert annotators, whereas our result trades annotator quality for quantity, enabling the use of large-scale crowdsourcing. The differences between these two studies are summarised in [Table 1](https://arxiv.org/html/2301.01405v3#S3.T1).

**Table 1: Comparison of identifiability conditions: [38] vs. our approach.**
| Aspect | [38] | Ours |
| --- | --- | --- |
| *Assumption* | Full-rank transition matrix annotators | i.i.d. noisy labels from $\Pr(\hat{Y}|X)$ |
|  | $\Leftrightarrow$ experts whose annotations have high probability of matching ground truths |  |
| *Min. № of labels per instance* | 3 expert annotations | $2C-1$ i.i.d. annotations |
| *Pros & cons* | ✓ Few annotations per instance | ✗ Higher number of annotations |
| ✗ Expert recruitment is costly and hard to meet for large number of classes $C$ | ✓ Easy to achieve (e.g., crowdsourcing) |  |
| $\to$ prioritise annotator quality to minimise annotation quantity | $\to$ trade annotator quality for annotation quantity |  |

According to the identifiability condition, at least additional $2C-2$ i.i.d. noisy labels per training sample must be
available to solve the LNL in its standard setting.
One can naively request more noisy labels per training sample, e.g., via crowd-sourcing, that satisfies the identifiability condition. Such an approach is, however, costly, time-consuming and poorly scalable, especially when the number of classes $C$ is large. For example, WebVision dataset [33] with $C=1,000$ classes will require at least an addition of 1,998 noisy labels per sample, resulting in an impractical solution.
To address this issue, we propose a practical method in [Section 3.2](https://arxiv.org/html/2301.01405v3#S3.SS2) to generate additional noisy labels to address the identifiability issue in LNL.

###### Identifiability Condition (Corollary of Theorem 1 ) .

###### Remark 1 .

### 3.2 Practical method to fulfil the identifiability condition

To obtain additional noisy labels per sample without additional labelling resources, we propose to approximate the noisy label distribution ${\Pr}(\hat{Y}|X)$ by taking the similarity between the features of training samples into account. Our assumption is that training samples with similar features tend to be annotated similarly. In other words, similar instances have similar noisy labels ([Table 5](https://arxiv.org/html/2301.01405v3#S5.T5) empirically verifies this claim on Cifar-10N). Thus, we can leverage
the single noisy label per training sample available in the training dataset to approximate the noisy label distribution ${\Pr}(\hat{Y}|X)$. The approximated distribution is then used to generate many i.i.d. noisy labels that meet the identifiability condition specified in [Identifiability Condition Identifiability Condition](https://arxiv.org/html/2301.01405v3#Thmconditionx1). Subsequently, the EM algorithm is employed to infer the parameters of the multinomial mixture model in [Eq. 2](https://arxiv.org/html/2301.01405v3#S3.E2), including the clean label distribution $\Pr(Y|X)$. [Appendix B](https://arxiv.org/html/2301.01405v3#A2) presents a discussion on alternative ways to approximate ${\Pr}(\hat{Y}|X)$.

#### 3.2.1 Approximating the multi-modal noisy label distribution Pr ⁡ ( Y ^ | X ) {\Pr}(\hat{Y}|X)

To generate additional i.i.d. noisy labels, we approximate the noisy label distribution of each training sample by exploiting the information of its nearest neighbours. The approximated noisy label distribution of an instance, denoted as $\widetilde{\Pr}(\hat{Y}|X=\mathbf{x}_{i})$, is derived not only from its own noisy label but also from the noisy labels of other instances whose features are similar to the instance:

$$ $\displaystyle\widetilde{\Pr}(\hat{Y}|X=\mathbf{x}_{i})$ $\displaystyle\leftarrow\mu\,\widetilde{\Pr}(\hat{Y}|X=\mathbf{x}_{i})+(1-\mu)\textstyle\sum_{j\neq i,j=1}^{K}\mathbf{A}_{ij}\,\widetilde{\Pr}(\hat{Y}|X=\mathbf{x}_{j}),$ (3) $$

where $\mu$ is a hyper-parameter in $[0,1]$ reflecting the trade-off between the noisy labels of the instance and its neighbours, $K$ is the number of nearest neighbours, and $\mathbf{A}_{ij}\in[0,1]$ is a coefficient representing the similarity between $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$. Note that $\sum_{j\neq i,j=1}^{K}\mathbf{A}_{ij}=1$.

There are several ways to find the similarity matrix $[\mathbf{A}_{ij}],\mathbf{A}_{ii}=0,i\in\{1,\ldots,M\},j\in\{1,\ldots,K\}$. For example, the study in [20] employs sparse subspace clustering method [13] to approximate the label distribution when learning human age from images. In this paper, we use a slightly similar but more efficient method that utilises the nearest neighbour information: locality-constrained linear coding (LLC) [53]. In particular, the coefficient $\mathbf{A}_{ij}$ can be determined via the following optimisation:

$$ $\displaystyle\textstyle\min_{\mathbf{A}_{i}}\norm{\mathbf{x}_{i}-\mathbf{B}_{i}\mathbf{A}_{i}}_{2}^{2}+\lambda\norm{\mathbf{d}_{i}\odot\mathbf{A}_{i}}_{2}^{2}\quad\text{s.t.: }\boldsymbol{1}^{\top}\mathbf{A}_{i}=1,\mathbf{A}_{ij}\geq 0,\forall j\in\{1,\ldots,K\},$ (4) $$

where $\mathbf{B}_{i}$ is a matrix containing the $K$ nearest neighbours of instance $\mathbf{x}_{i}$ (each column is a nearest-neighbour instance), $\mathbf{A}_{i}=\begin{bmatrix}\mathbf{A}_{i1}&\mathbf{A}_{i2}&\ldots&\mathbf{A}_{iK}\end{bmatrix}^{\top}$ is the $K$-dimensional vector representing the coding coefficients, $\odot$ is the element-wise multiplication (a.k.a. Hadamard product),
$\mathbf{d}_{i}=\exp(\nicefrac{{\mathrm{dist}(\mathbf{x}_{i},\mathbf{B}_{i})}}{{\sigma}})$ is the locality adaptor
with $\mathrm{dist}(\mathbf{x}_{i},\mathbf{B}_{i})$ being a vector of Euclidean distances from $\mathbf{x}_{i}$ to each of its nearest neighbours, and $\sigma$ being used for adjusting the weight decay speed for the locality adaptor. Nevertheless, since our interest is locality, not sparsity, in our implementation, we ignore the second term in [Eq. 4](https://arxiv.org/html/2301.01405v3#S3.E4) by setting $\lambda=0$.

Note that the optimisation in ([4](https://arxiv.org/html/2301.01405v3#S3.E4)) is slightly different from the original LLC due to the additional constraint of non-negativity of $\mathbf{A}_{ij}$. Nevertheless, the optimisation resembles a quadratic program, and therefore, can be efficiently solved by off-the-shelf solvers, such as OSQP [48].

To efficiently find nearest neighbours, we utilise TPU-KNN [10] – an efficient approximation to search for nearest neighbours with GPU acceleration capabilities. To optimise computational efficiency and memory usage, we employ the features extracted from training samples in the nearest neighbour search. Furthermore, to enhance the scalability of our method when dealing with large datasets containing millions of training samples, we perform the nearest neighbour search in a subset (about 15,000 training samples) that is randomly sampled from the training set.

##### Validity of i.i.d. assumption in generated noisy labels

The i.i.d. assumption in the identifiability condition means that noisy labels should be independently and identically distributed (i.e., knowing one noisy label gives no information about others).
This requirement is satisfied because the additional noisy labels are sampled independently from the approximated noisy label distribution $\widetilde{\Pr}(\hat{Y}|X)$.
This i.i.d. property of the generated noisy labels should not be confused with the inherent dependency of
$\widetilde{\Pr}(\hat{Y}|X)$ on neighbouring samples in [Eq. 3](https://arxiv.org/html/2301.01405v3#S3.E3).

#### 3.2.2 Infer clean label posterior with EM

Once the noisy label distribution $\widetilde{\Pr}(\hat{Y}|X)$ is approximated as a $(K+1)C$-multinomial mixture, we can generate $L$ sets, each consisting of $N$ noisy labels, with $N\geq 2C-1$, for each instance. The EM algorithm is then used to infer the parameter of the multinomial mixture model in [Eq. 2](https://arxiv.org/html/2301.01405v3#S3.E2). In particular, the objective function for the $i$-th sample can be written as:

$$ $\displaystyle\textstyle\max_{\pi_{i},\rho_{i}}\nicefrac{{1}}{{L}}$ $\displaystyle\textstyle\sum_{l=1}^{L}\ln{\Pr}(\hat{Y}=\hat{\mathbf{y}}_{l}|X=\mathbf{x}_{i};\pi_{i},\rho_{i})+\ln\Pr(\pi_{i};\alpha)+\ln\Pr(\rho_{i};\beta),$ (5) $$

where: $\hat{\mathbf{y}}_{l}\sim\widetilde{\Pr}(\hat{Y}|X=\mathbf{x}_{i})$ is an $N$-trial multinomial vector (e.g., sum of $N$ one-hot noisy labels of an instance), and $\alpha$ and $\beta$ are the parameters of the priors of $\pi_{i}$ and $\rho_{i}$, respectively.
The parameters $\pi_{i}$ and $\rho_{i}$ in ([5](https://arxiv.org/html/2301.01405v3#S3.E5)) can be optimised via the EM algorithm.

According to [Eq. 3](https://arxiv.org/html/2301.01405v3#S3.E3), additional multinomial noisy labels are sampled from a $(K+1)C$-multinomial mixture, $\widetilde{\Pr}(\hat{Y}|X=\mathbf{x}_{i})$.
Such a sampling process, however, has a complexity of $\mathcal{O}((K+1)C^{2})$, which is expensive when $C$ – the number of classes – is large. That is because the mixture coefficient (or pseudo-clean label probability), $\pi_{i}=\Pr(Y|X=\mathbf{x}_{i})$, is assumed to be dense with $C$ components, while in practice, $\Pr(Y|X=\mathbf{x}_{i})$ is often sparse with only $C_{0}$ components where $C_{0}\ll C$ [18]. We therefore exploit this observation to mitigate the issue of high complexity due to sampling. [Appendix E](https://arxiv.org/html/2301.01405v3#A5) provides further details on the reduction of number of noisy labels needed in our practical implementation.

The proposed method (see [Algorithm 1](https://arxiv.org/html/2301.01405v3#alg1) in [Appendix C](https://arxiv.org/html/2301.01405v3#A3)) relies on the extracted features to perform nearest neighbour search. Thus, if the features extracted are biased, it will worsen the quality of the nearest neighbours, reducing the effectiveness of the proposed method. To avoid such confirmation bias, we follow the *co-teaching* approach [19] that trains two models simultaneously where the noisy labels being cleaned by one model are used to train the other model and vice versa. We also analyse the complexity (only the “data pre-processing step” and excludes the loss calculation and model training because they are almost identical) of the proposed algorithm (see [Algorithm 1](https://arxiv.org/html/2301.01405v3#alg1)) and present the result in [Table 2](https://arxiv.org/html/2301.01405v3#S3.T2) (see [Appendix D](https://arxiv.org/html/2301.01405v3#A4) for the detailed analysis). In general, the bottleneck of our method is at the sampling of i.i.d. noisy labels and the EM algorithm due to its quadratic complexity with respect to the number of classes $C$. Readers are referred to [Table 9](https://arxiv.org/html/2301.01405v3#A4.T9) in [Appendix D](https://arxiv.org/html/2301.01405v3#A4) for the details of actual running time.

**Table 2: The running time complexity per epoch of the data pre-processing step of the proposed algorithm and existing methods, where: $\absolutevalue{\theta}$ is the number of model’s parameters, $M$ is the total number of training samples, $B$ is the mini-batch size, $C$ is the number of classes, $K$ is the number of nearest neighbours, L is the set of multiple noisy labels (e.g., $2C-1$ per training samples), $d$ is the dimension of input samples, $n_{\text{augment}}$ is the number of data augmentations, $n_{\text{iter}},n_{\text{osqp}},n_{\text{em}}$ are the number of optimisation iterations used within each method.**
| Method | Complexity |
| --- | --- |
| DivideMix [32] | $\order{6\absolutevalue{\theta}+\left[4+\nicefrac{{2}}{{B}}\left(n_{\text{augment}}d+2C\right)\right]M}$ |
| HOC [73] | $\order{\absolutevalue{\theta}+3M+2\ln M+n_{\text{iter}}C^{2}}$ |
| Ours | $\order{2\absolutevalue{\theta}+2\ln M+2n_{\mathrm{osqp}}Kd+2(L+n_{\mathrm{em}})C^{2}}$ |

## 4 Related work

LNL has been studied since the 1980s with some early works focusing on the statistical point of view [1, 5], such as determining the number of samples to achieve certain prediction accuracy under certain types of label noise. The field has then attracted more research interest, especially in the era of deep learning where an increasing number of annotated data is required to train large deep learning models. Learning from noisy labels is inherently challenging due to the issue of identifiability. Despite its importance, the identifiability issue in LNL remains a partially-addressed problem that requires the introduction of model-driven ad-hoc constraints or exploration through the use of data-driven multiple noisy labels.

Ad-hoc constraints  Many studies have implicitly or partially discussed the identifiability issue in the LNL problem and proposed practical methods designed with different heuristic criteria [42] to make the problem identifiable. The most widely-used constraint is the *small loss criterion* where the labels of samples with small loss values are assumed to be clean [19]. Training is then carried out either on only those low-risk samples [19] or cast as a semi-supervised learning approach with those clean samples representing labelled data while the others denoting un-labelled data [32]. Although this line of research achieves remarkable results in several benchmarks, they still lack theoretical foundations that explain why the *small loss criterion* is effective. There is one recent attempt that theoretically investigates the *small loss hypothesis* [17], but the study is applicable only to the class-dependent (a.k.a. instance-independent) label noise setting that assumes the presence of “anchor points”, i.e., samples that are guaranteed to have clean labels. Other methods propose different ad-hoc constraints based on observations in matrix decomposition and geometry. For instance, [35, 34] suggest the minimal volume of the simplex formed from the columns of transition matrices. [68] present a matrix decomposition approach and employ total variation regularisation to ensure the uniqueness of the solution. [9] impose similarity of transition matrices between samples that are close to each other.

Multiple noisy labels per instance  Learning from multiple noisy labels per instance has recently emerged as one approach to theoretically address the identifiability issue. The most relevant study in this area is the investigation of identifiability of transition matrices in noisy label learning [38]. In that paper, the authors implicitly extend the conventional 2-D transition matrix to a 3-D tensor with the third dimension representing annotators and exploit the results in 3-D arrays [30, 31] to find the condition of identifiability. Similar to a study in crowd-sourcing literature [51, Lemma 1], the authors in [38] conclude that at least 3 “informative” noisy labels per instance are needed. Although the finding is more optimistic than ours, it relies on the assumption of “informative” noisy labels, which requires a full-rank transition matrix for each annotator on each instance. The assumption of full-rank transition matrices implicitly depends on the number of classes as a larger number of classes increases the difficulty to make each $C$-by-$C$ transition matrix full-rank. Moreover, that assumption lacks clarity since it is unclear how to translate the full-rankness required for a transition matrix to a property an annotator must have. In contrast, our result does not rely on those assumptions, such as the “informativeness” of noisy labels nor full-ranked transition matrices, except that the multiple noisy labels should be i.i.d., and that we rely on a multinomial mixture modelling.
Another related study is the Higher-Order-Consensus (HOC) [73], which is a practical method present in [38]. To address the identifiability issue in LNL, HOC also relies on the full-rank transition matrices [73, Assumption 1] and the *2-NN label clusterability* [73, Definition 1] where the sample of interest and its two nearest neighbours belong to the same true class. HOC, however, mainly relies on instance-independent label noise, which may limit its applicability. Furthermore, the assumptions of clusterability in HOC does not always hold in practice [73, Table 3], especially at larger noise rates. Compared to HOC, our method presented in [Section 3.2](https://arxiv.org/html/2301.01405v3#S3.SS2) requires a less restricted assumption where similar samples are annotated similarly (see [Table 5](https://arxiv.org/html/2301.01405v3#S5.T5) for our empirical verification). We also provide an empirical comparison between HOC and our practical method in [Section 5.1](https://arxiv.org/html/2301.01405v3#S5.SS1) to understand further the differences.

## 5 Experiments

We employ several LNL benchmarks to evaluate the robustness of the proposed learning method when dealing with the most realistic type of label noise, namely: the instance-dependent noise. In particular, the experiments are performed on both synthetic and real-world instance-dependent label noise benchmarks. In addition, because our focus is on the theory of the identifiability in the LNL problem, we show that the proposed method is effective and competitive to other state-of-the-art (SOTA) methods without resorting to fine-tuning or employing highly-complex neural network architectures. The details of datasets, hyper-parameters and models used are shown in [Appendix F](https://arxiv.org/html/2301.01405v3#A6).

### 5.1 Comparison with identifiability-based methods

Since both [38] and our study tackle the same identifiability issue in LNL, but follow different approaches, it is important to evaluate the performance of practical methods derived from the two approaches.
More specifically, we compare HOC [73], representing [38], with our method presented in [Section 3.2](https://arxiv.org/html/2301.01405v3#S3.SS2). The comparison is conducted on multiple noisy-label datasets, namely: three human-annotated noisy labels in CIFAR-10N [56]. The results of HOC are obtained through its official implementation, which is publicly available.

For the real-world dataset CIFAR-10N, we evaluate on all of the available settings, including a single label for each of the three annotation cases, the *aggregate* which randomly selects one label from the three noisy labels, and the *worst* which selects the noisy label among the three labels annotated. We also consider the case of combining three noisy labels together by aggregating them into a soft label in the case of the cross-entropy baseline and our method, or passing all three into the model of interest to learn higher-order statistics in the case of HOC.

As shown in [Table 3](https://arxiv.org/html/2301.01405v3#S5.T3), our method outperforms the cross-entropy baseline and HOC in all CIFAR-10N settings. The performance gap between HOC and our method may be attributed to HOC’s dependence on *k-NN label clusterability* [73, Definition 1], which requires that the k-nearest neighbours of an instance must belong to the same true class. This is evident from the improvement of HOC’s performance when using three noisy labels per training sample, as shown in the last column of [Table 3](https://arxiv.org/html/2301.01405v3#S5.T3). In contrast, our method does not rely on the strong assumption of k-NN label clusterability and can consistently perform well with either single or multiple noisy labels per training sample. Note that when using all three available noisy labels, the performance gap between the baseline (training model directly on noisy label data), HOC and our method vanishes. This might be because the assumption of three noisy labels in HOC becomes valid. In addition, the label noise rate in this case is too small (approximately 0.02), and hence, makes the comparison less distinguishable. Note that in this experiment, our method relies on a PreAct Resnet-18 pre-trained on the training set of CNWL using SimCLR [7] for 500 epochs with a similar data augmentation policy (random crop and resize, colour jittering, grey or colourise and Gaussian blur), while the nearest neighbours in HOC rely on a Resnet-34 pre-trained on ImageNet.

**Table 3: Prediction accuracy on human-annotation CIFAR-10N.**
|  | CIFAR-10N |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Setting | Aggregate | Random 1 | Random 2 | Random 3 | Worst | 3 noisy labels |
| Noise rate | 0.09 | 0.17 | 0.18 | 0.18 | 0.40 | 0.02 |
| Cross-entropy [56] | 87.77 $\pm$ 0.38 | 85.02 $\pm$ 0.65 | 86.46 $\pm$ 1.79 | 85.16 $\pm$ 0.61 | 77.69 $\pm$ 1.55 | 92.24 $\pm$ 0.66 |
| HOC [73] | 83.34 $\pm$ 0.09 | 81.92 $\pm$ 0.18 | 81.76 $\pm$ 0.12 | 81.31 $\pm$ 0.17 | 62.31 $\pm$ 0.14 | 91.94 $\pm$ 0.73 |
| Ours | 89.69 $\pm$ 1.15 | 90.00 $\pm$ 0.23 | 89.79 $\pm$ 0.18 | 88.69 $\pm$ 0.23 | 89.89 $\pm$ 0.45 | 92.41 $\pm$ 0.79 |

**Table 4: Prediction accuracy (%) on real-world noisy label datasets: *(left)* Red CNWL, *(middle)* mini-WebVision and ImageNet and *(right)* Animal-10N. Best result in bold, $2^{nd}$ best in italics.**
| Method | Noise rate of CNWL |  |  |
| --- | --- | --- | --- |
| (no pre-trained) | 0.2 | 0.4 | 0.6 |
| Cross-entropy | 47.36 | 42.70 | 37.30 |
| mixup | 49.10 | 46.40 | 40.58 |
| DivideMix | 50.96 | 46.72 | 43.14 |
| MentorMix | 51.02 | 47.14 | 43.80 |
| FaMUS | 51.42 | 48.06 | 45.10 |
| SSR* | 52.18 | 48.96 | 42.42 |
| LSL | 54.68 | 49.80 | 45.46 |
| Ours | 52.78 | 49.18 | 46.00 |

### 5.2 Results on LNL common benchmarks

For Red CNWL, we follow the experimental setup from [60] and present results in [Table 4](https://arxiv.org/html/2301.01405v3#S5.T4) (left). This benchmark includes widely used SOTA methods evaluated on low-resolution (32-by-32 pixel^2) images to ensure a fair comparison. While our goal is not to outperform existing methods, these results illustrate that generating multiple noisy labels per sample shows competitive performance, supporting our theoretical claims.
We further evaluate the method on real-world noisy label datasets, mini-WebVision and Animal-10N, with results shown in [Table 4](https://arxiv.org/html/2301.01405v3#S5.T4) (middle) and (right). For mini-WebVision, we initialise the model with a ResNet-50 pre-trained for 100 epochs using DINO [6]. For Animal-10N, we use a VGG-19 pre-trained with DINO for 800 epochs. Again, the results are not intended to be SOTA but to show that the proposed approach is robust and performs comparably under realistic noisy conditions.
Additional results on CIFAR-10 and CIFAR-100 are provided in [Appendix G](https://arxiv.org/html/2301.01405v3#A7) (see [Table 10](https://arxiv.org/html/2301.01405v3#A7.T10)). [Table 10](https://arxiv.org/html/2301.01405v3#A7.T10) *(top)* compares our method to other approaches on synthetic noise settings. On CIFAR-10, our method performs on par with SOTA methods, and on CIFAR-100, it slightly outperforms them. These results further support the core claim: that leveraging a sufficient number of noisy labels per sample can effectively address the noisy-label problem.

### 5.3 Ablation studies

We further study the effect of the number of noisy labels per sample, the number of nearest neighbours and the effectiveness of our relabelling. Note that no self-supervised learning is used for pre-training the model in the ablation studies to avoid potential confounding factors.

Number of noisy labels per sample  We run experiments on the 100-class LNL problem of the Red CNWL dataset at 0.6 noise rate with various number of noisy labels per sample $N\in\{3,20,100,199,400\}$. We plot the results in [Fig. 1](https://arxiv.org/html/2301.01405v3#S5.F1) (left), where $L$ is the number of $N$ multinomial noisy labels defined in [Algorithm 1](https://arxiv.org/html/2301.01405v3#alg1). When $L$ is small, the more noisy labels per sample or larger $N$, the more effective, and the effectiveness diminishes after the threshold of $2C-1$, which in this case is 199. This empirically confirms the validity of [Identifiability Condition Identifiability Condition](https://arxiv.org/html/2301.01405v3#Thmconditionx1) about the identifiability in noisy label learning. However, when $L$ is large, the performance difference when varying $N$ is not as noticeable. In this regime (of large $L$), [Identifiability Condition Identifiability Condition](https://arxiv.org/html/2301.01405v3#Thmconditionx1) might result in a conservative requirement in terms of number of noisy labels per sample. The current LNL setting might contain some common latent structure between samples (e.g., limited number of candidate labels per instance), which we have not exploited yet to bring down the number of required noisy labels per sample. Future work will need to address such issue to make the problem more practical.

Effectiveness of label cleaning  is investigated by measuring the accuracy on the training set between the pseudo labels “cleaned” by EM and the ground truth labels on CIFAR-100 at a noise rate of 0.5. We also include the percentage of clean samples before training to compare more easily. Note that despite the nominal noise rate of 0.5, the “empirical” noise rate measured on the generated noisy labels following [57] before training is 0.44 (corresponding to 56 percent clean samples). The results in [Fig. 1](https://arxiv.org/html/2301.01405v3#S5.F1) (middle) show that the proposed method can improve from the initial dataset with 56 percent of clean samples to 68 percent. This 12 percent improvement is equivalent to cleaning 27 percent of noisy labels that are initially present in the training set.

Number of nearest neighbours  We also investigate the effect of the number of nearest neighbours $K$ to our proposed method by evaluating on CIFAR-100 at a noise rate of 0.5. The results in [Fig. 1](https://arxiv.org/html/2301.01405v3#S5.F1) (right) show that the larger $K$, the more accurate the testing accuracy. However, the trade-off is the running time shown in the right axis of [Fig. 1](https://arxiv.org/html/2301.01405v3#S5.F1) (right). Since $K=100$ gives a good balance between the performance and running time, this value is used in all of our experiments.

Figure: Figure 1: Ablation studies on: (left) the effect of number of noisy labels per sample on Red CNWL at a noise rate of 0.6, (middle) and (right) the accuracy of the relabelling and the influence of nearest neighbours on CIFAR-100.
Refer to caption: x1.png

**Table 5: Averaged label agreement of $K=10$ nearest neighbours (in percentage) on Cifar-10N to verify the assumption of label consistency.**
| Setting | Train directly | Warm-up |
| --- | --- | --- |
| Random 1 | 89.04 | 60.95 |
| Random 2 | 88.68 | 59.70 |
| Random 3 | 88.79 | 59.73 |
| 3 labels | 97.96 | 65.49 |

Label consistency of KNN  We verify the label consistency of nearest neighbours with features extracted from our models. It is measured as the average label agreement between the sample of interest and its nearest neighbours. [Table 5](https://arxiv.org/html/2301.01405v3#S5.T5) shows the label agreement evaluated at two checkpoints:
(i) training the model directly on noisy labels until convergence (*train directly*), and (ii) training the model for only 10 epochs (*warm-up*)
In general, approximately more than two thirds of the nearest neighbours of each sample share the same class label at the beginning of the training. This means that the assumption of label consistency, in which similar instances have similar noisy labels, made in [Section 3.2.1](https://arxiv.org/html/2301.01405v3#S3.SS2.SSS1) holds with adequate probability.

## 6 Conclusion

This study has conducted a formal investigation into the identifiability of noisy label learning using multinomial mixture models. Specifically, the LNL problem has been formulated as a multinomial mixture model, where the clean label probability is represented as the mixture coefficient and each column in the transition matrix is represented as each multinomial component. Such modelling reveals that LNL is identifiable when there are at least $2C-1$ i.i.d. noisy labels per sample provided; otherwise, the problem becomes non-identifiable unless additional assumptions or constraints are employed. This result agrees with previous studies on the identifiability of label noise learning, where the conventional setting of a single noisy label per training sample is non-identifiable. To practically address the LNL problem, we propose to leverage nearest neighbours to generate additional noisy labels to fulfill the identifiability requirement. The clean label distribution is then inferred through the EM algorithm for multinomial mixture models.
Even though our goal was not to outperform SOTA methods, the experimental results show that generating multiple noisy labels per sample yields competitive performance on various challenging benchmarks, particularly in scenarios involving instance-dependent and real-world label noises, supporting our theoretical claims. The proposed method also out-performs HOC – a practical method that deals with the identifiability in noisy label learning – in several settings, including the one with multiple noisy labels per training sample. Despite the promising finding, the number of noisy labels required to make the LNL identifiable in [Identifiability Condition Identifiability Condition](https://arxiv.org/html/2301.01405v3#Thmconditionx1) is still impractical in several applications where the number of classes is large, if we require additional manual labels. Future work will focus on the relation between class labels to further reduce this number, making it more practical.

## References

- [1]
Dana Angluin and Philip Laird
“Learning from noisy examples”
In *Machine Learning* 2.4
Springer, 1988, pp. 343–370
- [2]
Dzmitry Bahdanau, Kyunghyun Cho and Yoshua Bengio
“Neural Machine Translation by Jointly Learning to Align and Translate”
In *International Conference on Learning Representations*, 2015
- [3]
Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares-Lopez, Fabian Pedregosa and Jean-Philippe Vert
“Efficient and Modular Implicit Differentiation”
In *Advances in Neural Information Processing Systems* 35
Curran Associates, Inc., 2022, pp. 5230–5242
- [4]
James Bradbury et al.
“JAX: composable transformations of Python + NumPy programs”, software, 2018
URL: [http://github.com/google/jax](http://github.com/google/jax)
- [5]
Nader H Bshouty, Nadav Eiron and Eyal Kushilevitz
“PAC learning with nasty noise”
In *Theoretical Computer Science* 288.2
Elsevier, 2002, pp. 255–275
- [6]
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski and Armand Joulin
“Emerging Properties in Self-Supervised Vision Transformers”
In *International Conference on Computer Vision*, 2021
- [7]
Ting Chen, Simon Kornblith, Mohammad Norouzi and Geoffrey Hinton
“A simple framework for contrastive learning of visual representations”
In *International Conference on Machine Learning*, 2020, pp. 1597–1607
PMLR
- [8]
Yingyi Chen, Xi Shen, Shell Xu Hu and Johan AK Suykens
“Boosting co-teaching with compression regularization for label noise”
In *Conference on Computer Vision and Pattern Recognition*, 2021, pp. 2688–2692
- [9]
De Cheng, Tongliang Liu, Yixiong Ning, Nannan Wang, Bo Han, Gang Niu, Xinbo Gao and Masashi Sugiyama
“Instance-Dependent Label-Noise Learning with Manifold-Regularized Transition Matrix Estimation”
In *Conference on Computer Vision and Pattern Recognition*, 2022, pp. 16630–16639
- [10]
Felix Chern, Blake Hechtman, Andy Davis, Ruiqi Guo, David Majnemer and Sanjiv Kumar
“Tpu-knn: K nearest neighbor search at peak flop/s”
In *Advances in Neural Information Processing Systems* 35, 2022, pp. 15489–15501
- [11]
Arthur P Dempster, Nan M Laird and Donald B Rubin
“Maximum likelihood from incomplete data via the EM algorithm”
In *Journal of the Royal Statistical Society: Series B (Methodological)* 39.1
Wiley Online Library, 1977, pp. 1–22
- [12]
Alexey Dosovitskiy et al.
“An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale”
In *International Conference on Learning Representations*, 2021
- [13]
Ehsan Elhamifar and René Vidal
“Sparse Subspace Clustering: Algorithm, Theory, and Applications”
In *IEEE Transactions on Pattern Analysis and Machine Intelligence* 35.11, 2013, pp. 2765–2781
DOI: [10.1109/TPAMI.2013.57](https://dx.doi.org/10.1109/TPAMI.2013.57)
- [14]
Ryan T Elmore and Shaoli Wang
“Identifiability and estimation in finite mixture models with multinomial components”, 2003
- [15]
Chen Feng, Georgios Tzimiropoulos and Ioannis Patras
“SSR: An efficient and robust framework for learning with unknown label noise”
In *British Machine Vision Conference*, 2022
- [16]
Jacob Goldberger and Ehud Ben-Reuven
“Training deep neural-networks using a noise adaptation layer”
In *International Conference on Learning Representations*, 2017
- [17]
Xian-Jin Gui, Wei Wang and Zhang-Hao Tian
“Towards Understanding Deep Learning from Noisy Labels with Small-Loss Criterion”
In *International Joint Conference on Artificial Intelligence*, 2021
- [18]
Bo Han, Jiangchao Yao, Gang Niu, Mingyuan Zhou, Ivor Tsang, Ya Zhang and Masashi Sugiyama
“Masking: A new perspective of noisy supervision”
In *Advances in Neural Information Processing Systems* 31, 2018
- [19]
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor Tsang and Masashi Sugiyama
“Co-teaching: Robust training of deep neural networks with extremely noisy labels”
In *Advances in Neural Information Processing Systems* 31, 2018
- [20]
Zhouzhou He, Xi Li, Zhongfei Zhang, Fei Wu, Xin Geng, Yaqing Zhang, Ming-Hsuan Yang and Yueting Zhuang
“Data-dependent label distribution learning for age estimation”
In *IEEE Transactions on Image Processing* 26.8
IEEE, 2017, pp. 3846–3858
- [21]
Ahmet Iscen, Jack Valmadre, Anurag Arnab and Cordelia Schmid
“Learning with Neighbor Consistency for Noisy Labels”
In *Conference on Computer Vision and Pattern Recognition*, 2022, pp. 4672–4681
- [22]
Lu Jiang, Di Huang, Mason Liu and Weilong Yang
“Beyond synthetic noise: Deep learning on controlled noisy labels”
In *International Conference on Machine Learning*, 2020, pp. 4804–4815
PMLR
- [23]
Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li and Li Fei-Fei
“MentorNet: Learning data-driven curriculum for very deep neural networks on corrupted labels”
In *International Conference on Machine Learning*, 2018, pp. 2304–2313
PMLR
- [24]
Jeff Johnson, Matthijs Douze and Hervé Jégou
“Billion-scale similarity search with GPUs”
In *IEEE Transactions on Big Data* 7.3
IEEE, 2019, pp. 535–547
- [25]
John Jumper et al.
“Highly accurate protein structure prediction with AlphaFold”
In *Nature* 596.7873
Nature Publishing Group, 2021, pp. 583–589
- [26]
Byung Soo Kim
“Studies of multinomial mixture models”, 1984
- [27]
Noo-ri Kim, Jin-Seop Lee and Jee-Hyong Lee
“Learning with structural labels for learning with noisy labels”
In *IEEE/CVF Conference on Computer Vision and Pattern Recognition*, 2024, pp. 27610–27620
- [28]
Taehyeon Kim, Jongwoo Ko, JinHwan Choi and Se-Young Yun
“FINE samples for learning with noisy labels”
In *Advances in Neural Information Processing Systems* 34, 2021, pp. 24137–24149
- [29]
Alex Krizhevsky, Ilya Sutskever and Geoffrey E Hinton
“ImageNet Classification with Deep Convolutional Neural Networks”
In *Advances in Neural Information Processing Systems* 25, 2012
- [30]
Joseph B Kruskal
“More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling”
In *Psychometrika* 41.3
Springer, 1976, pp. 281–293
- [31]
Joseph B Kruskal
“Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics”
In *Linear algebra and its applications* 18.2
Elsevier, 1977, pp. 95–138
- [32]
Junnan Li, Richard Socher and Steven CH Hoi
“DivideMix: Learning with noisy labels as semi-supervised learning”
In *International Conference on Learning Representations*, 2020
- [33]
Wen Li, Limin Wang, Wei Li, Eirikur Agustsson and Luc Van Gool
“WebVision database: Visual learning and understanding from web data”
In *arXiv preprint arXiv:1708.02862*, 2017
- [34]
Xuefeng Li, Tongliang Liu, Bo Han, Gang Niu and Masashi Sugiyama
“Provably end-to-end label-noise learning without anchor points”
In *International Conference on Machine Learning*, 2021, pp. 6403–6413
PMLR
- [35]
Chia-Hsiang Lin, Wing-Kin Ma, Wei-Chiang Li, Chong-Yung Chi and ArulMurugan Ambikapathi
“Identifiability of the simplex volume minimization criterion for blind hyperspectral unmixing: The no-pure-pixel case”
In *IEEE Transactions on Geoscience and Remote Sensing* 53.10
IEEE, 2015, pp. 5530–5546
- [36]
Sheng Liu, Jonathan Niles-Weed, Narges Razavian and Carlos Fernandez-Granda
“Early-learning regularization prevents memorization of noisy labels”
In *Advances in Neural Information Processing Systems* 33, 2020, pp. 20331–20342
- [37]
Tongliang Liu and Dacheng Tao
“Classification with noisy labels by importance reweighting”
In *IEEE Transactions on Pattern Analysis and Machine Intelligence* 38.3
IEEE, 2015, pp. 447–461
- [38]
Yang Liu, Hao Cheng and Kun Zhang
“Identifiability of Label Noise Transition Matrix”
In *International Conference on Machine Learning*, 2023
- [39]
Yang Liu and Hongyi Guo
“Peer loss functions: Learning from noisy labels without knowing noise rates”
In *International Conference on Machine Learning*, 2020, pp. 6226–6236
PMLR
- [40]
Wenshui Luo, Shuo Chen, Tongliang Liu, Bo Han, Gang Niu, Masashi Sugiyama, Dacheng Tao and Chen Gong
“Estimating per-class statistics for label noise learning”
In *IEEE Transactions on Pattern Analysis and Machine Intelligence*
IEEE, 2024
- [41]
Eran Malach and Shai Shalev-Shwartz
“Decoupling “when to update“ from “how to update“”
In *Advances in Neural Information Processing Systems* 30, 2017
- [42]
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong and Bob Williamson
“Learning from corrupted binary labels via class-probability estimation”
In *International Conference on Machine Learning*, 2015, pp. 125–134
PMLR
- [43]
Diego Ortego, Eric Arazo, Paul Albert, Noel E O’Connor and Kevin McGuinness
“Multi-objective interpolation training for robustness to label noise”
In *Conference on Computer Vision and Pattern Recognition*, 2021, pp. 6606–6615
- [44]
Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock and Lizhen Qu
“Making deep neural networks robust to label noise: A loss correction approach”
In *Conference on Computer Vision and Pattern Recognition*, 2017, pp. 1944–1952
- [45]
Olga Russakovsky et al.
“ImageNet large scale visual recognition challenge”
In *International Journal of Computer Vision* 115.3
Springer, 2015, pp. 211–252
- [46]
David Silver et al.
“Mastering the game of Go with deep neural networks and tree search”
In *Nature* 529.7587
Nature Publishing Group, 2016, pp. 484–489
- [47]
Hwanjun Song, Minseok Kim and Jae-Gil Lee
“SELFIE: Refurbishing Unclean Samples for Robust Deep Learning”
In *International Conference on Machine Learning*, 2019
- [48]
Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad and Stephen Boyd
“OSQP: An operator splitting solver for quadratic programs”
In *Mathematical Programming Computation* 12.4
Springer, 2020, pp. 637–672
- [49]
Henry Teicher
“Identifiability of mixtures”
In *The Annals of Mathematical Statistics* 32.1
Institute of Mathematical Statistics, 1961, pp. 244–248
- [50]
DM Titterington, A Smith and U Makov
“Statistical Analysis of Finite Mixture Distributions”
New York: Wiley, 1985
- [51]
Panagiotis A. Traganitis, Alba Pagès-Zamora and Georgios B. Giannakis
“Blind Multiclass Ensemble Classification”
In *IEEE Transactions on Signal Processing* 66.18, 2018, pp. 4737–4752
DOI: [10.1109/TSP.2018.2860562](https://dx.doi.org/10.1109/TSP.2018.2860562)
- [52]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser and Illia Polosukhin
“Attention is all you need”
In *Advances in Neural Information Processing Systems* 30, 2017
- [53]
Jinjun Wang, Jianchao Yang, Kai Yu, Fengjun Lv, Thomas Huang and Yihong Gong
“Locality-constrained linear coding for image classification”
In *Conference on Computer Vision and Pattern Recognition*, 2010, pp. 3360–3367
IEEE
- [54]
Yuan Wang, Huaxin Pang, Ying Qin, Shikui Wei and Yao Zhao
“Adaptive estimation of instance-dependent noise transition matrix for learning with instance-dependent label noise”
In *Neural Networks*
Elsevier, 2025, pp. 107464
- [55]
Hongxin Wei, Lei Feng, Xiangyu Chen and Bo An
“Combating noisy labels by agreement: A joint training method with co-regularization”
In *Conference on Computer Vision and Pattern Recognition*, 2020, pp. 13726–13735
- [56]
Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu and Yang Liu
“Learning with Noisy Labels Revisited: A Study Using Real-World Human Annotations”
In *International Conference on Learning Representations*, 2022
- [57]
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang, Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao and Masashi Sugiyama
“Part-dependent label noise: Towards instance-dependent label noise”
In *Advances in Neural Information Processing Systems* 33, 2020, pp. 7597–7610
- [58]
Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu and Masashi Sugiyama
“Are anchor points really indispensable in label-noise learning?”
In *Advances in Neural Information Processing Systems* 32, 2019
- [59]
Yilun Xu, Peng Cao, Yuqing Kong and Yizhou Wang
“$\mathcal{L}_{\mathrm{DMI}}$: A novel information-theoretic loss function for training deep nets robust to label noise”
In *Advances in Neural Information Processing Systems* 32, 2019
- [60]
Youjiang Xu, Linchao Zhu, Lu Jiang and Yi Yang
“Faster meta update strategy for noise-robust deep learning”
In *Conference on Computer Vision and Pattern Recognition*, 2021, pp. 144–153
- [61]
Sidney J Yakowitz and John D Spragins
“On the identifiability of finite mixtures”
In *The Annals of Mathematical Statistics* 39.1
Institute of Mathematical Statistics, 1968, pp. 209–214
- [62]
Yu Yao, Tongliang Liu, Mingming Gong, Bo Han, Gang Niu and Kun Zhang
“Instance-dependent Label-noise Learning under a Structural Causal Model”
In *Advances in Neural Information Processing Systems* 34, 2021
- [63]
LIN Yong, Renjie Pi, Weizhong Zhang, Xiaobo Xia, Jiahui Gao, Xiao Zhou, Tongliang Liu and Bo Han
“A holistic view of label noise transition matrix in deep learning and beyond”
In *The Eleventh International Conference on Learning Representations*, 2022
- [64]
Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor Tsang and Masashi Sugiyama
“How does disagreement help generalization against label corruption?”
In *International Conference on Machine Learning*, 2019, pp. 7164–7173
PMLR
- [65]
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin and David Lopez-Paz
“mixup: Beyond Empirical Risk Minimization”
In *International Conference on Learning Representations*, 2018
- [66]
Ruiheng Zhang, Zhe Cao, Shuo Yang, Lingyu Si, Haoyang Sun, Lixin Xu and Fuchun Sun
“Cognition-driven structural prior for instance-dependent label transition matrix estimation”
In *IEEE Transactions on Neural Networks and Learning Systems*
IEEE, 2024
- [67]
Yikai Zhang, Songzhu Zheng, Pengxiang Wu, Mayank Goswami and Chao Chen
“Learning with feature-dependent label noise: A progressive approach”
In *International Conference on Learning Representations*, 2021
- [68]
Yivan Zhang, Gang Niu and Masashi Sugiyama
“Learning noise transition matrix from only noisy labels via total variation regularization”
In *International Conference on Machine Learning*, 2021, pp. 12501–12512
PMLR
- [69]
Zhilu Zhang and Mert Sabuncu
“Generalized cross entropy loss for training deep neural networks with noisy labels”
In *Advances in Neural Information Processing Systems* 31, 2018
- [70]
Xiong Zhou, Xianming Liu, Deming Zhai, Junjun Jiang and Xiangyang Ji
“Asymmetric loss functions for noise-tolerant learning: Theory and applications”
In *IEEE Transactions on Pattern Analysis and Machine Intelligence* 45.7
IEEE, 2023, pp. 8094–8109
- [71]
Yilun Zhu, Jianxin Zhang, Aditya Gangrade and Clay Scott
“Label noise: Ignorance is bliss”
In *Advances in Neural Information Processing Systems* 37, 2024, pp. 116575–116616
- [72]
Zhaowei Zhu, Tongliang Liu and Yang Liu
“A Second-Order Approach to Learning With Instance-Dependent Label Noise”
In *Conference on Computer Vision and Pattern Recognition*, 2021, pp. 10113–10123
- [73]
Zhaowei Zhu, Yiwen Song and Yang Liu
“Clusterability as an alternative to anchor points when learning with noisy labels”
In *International Conference on Machine Learning*, 2021, pp. 12912–12923
PMLR

## Appendix A EM for multinomial mixture models

This appendix presents the EM algorithm for multinomial mixture models mentioned in [Section 3.2.2](https://arxiv.org/html/2301.01405v3#S3.SS2.SSS2).

Recall that a mixture of multinomial distributions in the LNL problem can be written as:

$$ $p(\hat{Y}|X=\mathbf{x}_{i})=\sum_{c=1}^{C}p(Y=c|X=\mathbf{x}_{i})\,p(\hat{Y}|X=\mathbf{x}_{i},Y=c)=\sum_{c=1}^{C}\pi_{ic}\mathrm{Mult}(\hat{Y};N,\rho_{ic}).$ ( 2 ) $$

The aim here is to infer the parameters of the multinomial mixture model. In particular, we want to exploit the given $L$ noisy labels $\{\hat{y}_{l}\}_{l=1}^{L}$ of an instance $X=\mathbf{x}_{i}$ to infer $p(Y|X=\mathbf{x}_{i})$ and $p(\hat{Y}|X=\mathbf{x}_{i},Y)$.

We note that despite the identifiable condition in [Identifiability Condition Identifiability Condition](https://arxiv.org/html/2301.01405v3#Thmconditionx1) requiring $N\geq 2C-1$, we still need multiple sets of such $N$-trial noisy labels for inference. If only a single set of $N$ noisy labels is given, the inference will have a very large uncertainty although the problem is identifiable.

### A.1 Maximum likelihood

Given $L$ noisy labels $\{\hat{y}_{l}\}_{l=1}^{L}$ of an instance $X=\mathbf{x}_{i}$, the objective in terms of maximum likelihood estimation can be written as:

$$ $\max_{\pi_{i},\rho_{i}}\sum_{l=1}^{L}\ln p(\hat{Y}=\mathbf{y}_{l}|X=\mathbf{x}_{i})=\max_{\pi_{i},\rho_{i}}\sum_{l=1}^{L}\sum_{c=1}^{C}\pi_{ic}\mathrm{Mult}(\hat{Y}=\mathbf{y}_{l};N,\rho_{ic}).$ (6) $$

#### A.1.1 E-step

This step is to calculate the posterior of the latent variable $\mathbf{z}_{n}$ given the data $\mathbf{x}_{n}$:

$$ $\begin{split}\gamma_{lc}&=p(Y=c|\hat{Y}=\hat{\mathbf{y}}_{l},X=\mathbf{x}_{i};\pi_{i}^{(t)},\rho_{i}^{(t)})\\ &=\frac{p(\hat{Y}=\hat{\mathbf{y}}_{l}|Y=c,X=\mathbf{x}_{i};\rho_{i}^{(t)})\,p(Y=c|X=\mathbf{x}_{i};\pi_{i}^{(t)})}{\sum_{c=1}^{C}p(\hat{Y}=\hat{\mathbf{y}}_{l}|Y=c,X=\mathbf{x}_{i};\rho_{i}^{(t)})\,p(Y=c|X=\mathbf{x}_{i};\pi_{i}^{(t)})}\\ &=\frac{\pi_{c}^{(t)}\,\mathrm{Mult}(\hat{Y}=\hat{\mathbf{y}}_{l};N,\rho_{ic}^{(t)})}{\sum_{c=1}^{C}\pi_{ic}^{(t)}\,\mathrm{Mult}(\hat{Y}=\hat{\mathbf{y}}_{l};N,\rho_{ic}^{(t)})}.\end{split}$ (7) $$

#### A.1.2 M-step

In the M-step, we maximise the following expected completed log-likelihood w.r.t. $\pi_{i}$ and $\rho_{i}$:

$$ $\begin{split}Q&=\sum_{l=1}^{L}\mathbb{E}_{p(Y|\hat{Y}=\hat{\mathbf{y}}_{l},X=\mathbf{x}_{i};\pi_{i}^{(t)},\rho_{i}^{(t)})}\left[\ln p(\hat{Y},Y|X=\mathbf{x}_{i};\pi_{i},\rho_{i})\right]\\ &=\sum_{l=1}^{L}\mathbb{E}_{p(Y|\hat{Y}=\hat{\mathbf{y}}_{l},X=\mathbf{x}_{i};\pi_{i}^{(t)},\rho_{i}^{(t)})}\left[\ln p(Y|X=\mathbf{x}_{i};\pi_{i})+\ln p(\hat{Y}=\hat{\mathbf{y}}_{l}|Y,X=\mathbf{x}_{i};\rho_{i})\right]\\ &=\sum_{l=1}^{L}\sum_{c=1}^{C}\mathbb{E}_{p(Y=c|\hat{Y}=\hat{\mathbf{y}}_{l},X=\mathbf{x}_{i};\pi_{i}^{(t)},\rho_{i}^{(t)})}\left[\ln\pi_{ic}+\ln\mathrm{Mult}(\hat{Y}=\hat{\mathbf{y}}_{l};N,\rho_{ic})\right]\\ &=\sum_{l=1}^{L}\sum_{c=1}^{C}\gamma_{nk}\left[\ln\pi_{ic}+\sum_{c^{\prime}=1}^{C}\hat{\mathbf{y}}_{l}\ln\rho_{icc^{\prime}}+\mathrm{const.}\right].\end{split}$ (8) $$

The Lagrangian for $\pi$ can be written as:

$$ $Q_{\pi_{i}}=Q-\lambda\left(\sum_{c=1}^{C}\pi_{ic}-1\right),$ (9) $$

where $\lambda$ is the Lagrange multiplier. Taking derivative of the Lagrangian w.r.t. $\pi_{ic}$ gives:

$$ $\partialderivative{Q_{\pi_{i}}}{\pi_{ic}}=\frac{1}{\pi_{ic}}\sum_{l=1}^{L}\gamma_{lc}-\lambda.$ (10) $$

Setting the derivative to zero and solving for $\pi_{ic}$ gives:

$$ $\pi_{ic}=\frac{1}{\lambda}\sum_{l=1}^{L}\gamma_{lc}.$ (11) $$

And since $\sum_{c=1}^{C}\pi_{ic}=1$, one can substitute and find that $\lambda=L$. Thus:

$$ $\boxed{\pi_{ic}^{(t+1)}=\frac{1}{L}\sum_{l=1}^{L}\gamma_{lc}.}$ (12) $$

Similarly, the Lagrangian of $\rho_{icc^{\prime}}$ can be expressed as:

$$ $Q_{\rho_{icc^{\prime}}}=Q-\sum_{c=1}^{C}\eta_{c}\left(\sum_{c^{\prime}=1}^{C}\rho_{icc^{\prime}}-1\right),$ (13) $$

where $\eta_{c}$ is the Lagrange multiplier. Taking derivative w.r.t. $\rho_{icc^{\prime}}$ gives:

$$ $\partialderivative{Q_{\rho_{icc^{\prime}}}}{\rho_{icc^{\prime}}}=\frac{1}{\rho_{icc^{\prime}}}\sum_{l=1}^{L}\gamma_{lc}\hat{\mathbf{y}}_{lc^{\prime}}-\eta_{c}.$ (14) $$

Setting the derivative to zero and solving for $\rho_{icc^{\prime}}$ gives:

$$ $\rho_{icc^{\prime}}=\frac{1}{\eta_{c}}\sum_{l=1}^{L}\gamma_{lc}\hat{\mathbf{y}}_{lc^{\prime}}.$ (15) $$

The constraint on $\rho_{ic}$ as a probability vector leads to $\eta_{c}=N\sum_{l=1}^{L}\gamma_{lc}$. Thus:

$$ $\boxed{\rho_{icc^{\prime}}^{(t+1)}=\frac{\sum_{l=1}^{L}\gamma_{lc}\hat{\mathbf{y}}_{lc^{\prime}}}{N\sum_{l=1}^{L}\gamma_{lc}}.}$ (16) $$

### A.2 Maximum a posterior (MAP)

The objective function is similar to the one in [Section A.1](https://arxiv.org/html/2301.01405v3#A1.SS1), except including the prior on $\pi_{i}$ and $\rho_{i}$ as follows:

$$ $\max_{\pi_{i},\rho_{i}}Q:=\sum_{l=1}^{L}\sum_{c=1}^{C}\pi_{ic}\mathrm{Mult}(\hat{Y}=\mathbf{y}_{l};N,\rho_{ic})+\ln p(\pi_{i};\alpha)+\sum_{c=1}^{C}\ln p(\rho_{ic};\beta),$ (17) $$

where the two priors are:

$$ $\displaystyle p(\pi_{i};\alpha)$ $\displaystyle=\mathrm{Dir}(\pi_{i};\alpha)$ (18) $\displaystyle p(\rho_{ic};\beta)$ $\displaystyle=\mathrm{Dir}(\rho_{ic};\beta).$ (19) $$

The E-step in this case remains unchanged from ([7](https://arxiv.org/html/2301.01405v3#A1.E7)).

The derivative of the Lagrangian for $\pi$ can be written as:

$$ $\partialderivative{Q_{\pi_{i}}^{\mathrm{MAP}}}{\pi_{ic}}=\frac{1}{\pi_{ic}}\left(\sum_{l=1}^{L}\gamma_{lc}+\alpha_{c}-1\right)-\lambda.$ (20) $$

Thus:

$$ $\boxed{\pi_{ic}^{(t+1)}=\frac{\sum_{l=1}^{L}\gamma_{lc}+\alpha_{c}-1}{L+\sum_{c=1}^{C}\alpha_{c}-C}.}$ (21) $$

Similarly for $\rho_{icc^{\prime}}$:

$$ $\partialderivative{Q_{\rho}^{\mathrm{MAP}}}{\rho_{icc^{\prime}}}=\frac{1}{\rho_{icc^{\prime}}}\left(\sum_{l=1}^{L}\gamma_{lc}\hat{\mathbf{y}}_{lc^{\prime}}+\beta_{c^{\prime}}-1\right)-\eta_{c}.$ (22) $$

Thus:

$$ $\boxed{\rho_{icc^{\prime}}^{(t+1)}=\frac{\sum_{l=1}^{L}\gamma_{lc}\hat{\mathbf{y}}_{lc^{\prime}}+\beta_{c^{\prime}}-1}{N\sum_{l=1}^{L}\gamma_{lc}+\sum_{c^{\prime}=1}^{C}\beta_{c^{\prime}}-C}.}$ (23) $$

## Appendix B Alternative ways to approximate the noisy label distribution

There might be different ways to approximate $p(\hat{Y}|X)$, e.g., simply using a neural network trained directly on noisy-label data $\{(\mathbf{x}_{i},\hat{y}_{i})\}_{i=1}^{M}$. This approach is, however, sub-optimal since the noisy label distribution $p(\hat{Y}|X)$ is modelled as a simple categorical distribution (represented by the softmax output of the neural network). Inferring a mixture of multinomial distributions from samples generated from such a less expressive distribution may potentially result in a single-component mixture (i.e., component collapse), making the estimation inaccurate. Another way is to train a neural network to explicitly output $p(Y|X)$ and $p(\hat{Y}|X,Y)$ [16], which is equivalent to learn a mixture of categorical distributions. This would, however, be subjected to the identifiability issue in LNL. In contrast, our approach exploits the noisy labels of nearest neighbours to approximate the noisy label distribution. In particular, we model the distribution of noisy label of each instance as a mixture of $C$ multinomial components, and hence, the approximated noisy label distribution obtained through $K$ nearest neighbours would be a mixture of $(K+1)C$ multinomial distributions (please refer to [Eq. 3](https://arxiv.org/html/2301.01405v3#S3.E3)). In addition, exploiting nearest neighbours in the feature space results in more consistent label distributions across samples [21]. Furthermore, the nearest-neighbour based approach has been demonstrated to be effective and widely-used in label distribution learning [20].

## Appendix C Proposed learning algorithm to overcome the identifiability in label noise

The proposed learning algorithm to augment the noisy labels is shown in [Algorithm 1](https://arxiv.org/html/2301.01405v3#alg1).

Figure: Algorithm 1 Progressively clean noisy labels

## Appendix D Running time complexity analysis

We analyse the complexity of our proposed method, in which the pseudo-clean labels are inferred from the noisy label distributions. Our analysis focuses on the “pre-processing” step right before calculating loss and back-propagation because this is the main difference between these methods (the loss calculation and gradient update for the model’s parameters are similar). Hence, in the following analysis, we omit the complexity of relating to the loss calculation and parameter update.

Another note is that the complexity is analysed for one epoch. For the convenience, the notations used are explicitly defined in [Table 6](https://arxiv.org/html/2301.01405v3#A4.T6).

**Table 6: The notations used in the complexity analysis.**
| Notations | Description |
| --- | --- |
| $\absolutevalue{\theta}$ | the number of model’s parameters |
| $M$ | the total number of training samples |
| $C$ | the number of classes |
| $K$ | the number of nearest neighbours |
| $N$ | number of noisy labels per training samples (e.g., $N=2C-1$) |
| $L$ | the set of $N$ noisy labels per sample (applicable to ours only) |
| $n_{\text{osqp}},n_{\text{em}},n_{\text{em}}$ | the number of iterations used in optimisation |

### D.1 Complexity of our proposed method

The complexity of each step in [Algorithm 1](https://arxiv.org/html/2301.01405v3#alg1) for each model can be written as:

- •
Extract features: $\order{\absolutevalue{\theta}}$
- •
Fast nearest neighbour search $\approx\order{K\ln M}$ [24] or just $\order{\ln M}$ with GPU
- •
Finding similarity matrix $\mathbf{A}$ in ([4](https://arxiv.org/html/2301.01405v3#S3.E4)) with OSQP [3]: $\approx\order{n_{\mathrm{osqp}}Kd}$, where: $n_{\mathrm{osqp}}$ is the number of iterations and $d$ is the dimension of $X$
- •
Sampling $L$ sets of $N$-categorical samples where $N\geq 2C-1$ (in parallel for $N$): $\order{LC^{2}}$
- •
Running EM: $\order{n_{\mathrm{em}}NC}\approx\order{n_{\mathrm{em}}C^{2}}$.

Thus, the complexity of [Algorithm 1](https://arxiv.org/html/2301.01405v3#alg1) per iteration is: $\order{2\absolutevalue{\theta}+2\ln M+2n_{\mathrm{osqp}}Kd+2(L+n_{\mathrm{em}})C^{2}}$ since $C\ll M,d$. Nevertheless, the most expensive operation is the sampling that generates additional noisy labels to perform EM with a quadratic complexity in terms of the number of classes $C$.
To facilitate the comparison with existing works, we provide a summary of their complexity in [Table 2](https://arxiv.org/html/2301.01405v3#S3.T2). In general, our method has a higher complexity compared to DivideMix and HOC due to its nature of re-labelling data. The bottle-neck of our proposed method lies at the sampling where $L$ sets of $N$-trial multinomial noisy labels are generated.

### D.2 Complexity of DivideMix

The complexity of DivideMix for each model can be presented in

**Table 7: Running time complexity of data processing in DivideMix**
| Step | Complexity | Comment |
| --- | --- | --- |
| Cluster with Gaussian mixture model | $\order{M}$ |  |
| Augment data | $\order{n_{\text{augment}}\frac{M}{B}d}$ | vectorise over each mini-batch |
| Average prediction loss | $\order{\absolutevalue{\theta}+C+M}$ | parallel forward pass |
| Refine ground truth | $\order{\frac{M}{B}C}$ | vectorise over each mini-batch |
| Co-guessing | $\order{2\absolutevalue{\theta}+2M}$ |  |
| Sharpen guessed labels | $\order{\frac{M}{B}C}$ | vectorise over each mini-batch |
| Total per model | $\order{3\absolutevalue{\theta}+(2+\frac{1}{B}(n_{\text{augment}}d+2C))M+C}$ |  |

Because the number of class $C$ is small compared to the number of samples $M$ or the sample dimension $d$, one can simplify the complexity of the pre-processing step in dual-model DivideMix as follows:

$$ $\order{6\absolutevalue{\theta}+\left[4+\frac{2}{B}\left(n_{\text{augment}}d+2C\right)\right]M}.$ (24) $$

### D.3 Complexity of HOC

The running time complexity of HOC [73] is presented in [Table 8](https://arxiv.org/html/2301.01405v3#A4.T8).

**Table 8: Running time complexity of HOC**
| Step | Complexity | Comment |
| --- | --- | --- |
| Extract representation | $\order{\absolutevalue{\theta}}$ | assume $d,M\ll\absolutevalue{\theta}$ |
| Get 2-NN | $\order{2\ln M}$ |  |
| Count frequency | $\order{3M}$ |  |
| Solve for transition matrix | $\order{n_{\text{iter}}C^{2}}$ |  |
| Total | $\order{\absolutevalue{\theta}+3M+2\ln M+n_{\text{iter}}C^{2}}$ |  |

### D.4 Actual running time

We also provide the running time in practice for these methods in [Table 9](https://arxiv.org/html/2301.01405v3#A4.T9). Our proposed method takes longer time to run than DivideMix or HOC. For DivideMix, it relies on the small-loss hypothesis to separate which samples are clean or noisy. The bottle-neck in DivideMix properly lies at the dual models used to avoid confirmation bias. For HOC, it relies on nearest-neighbours to obtain higher-order statistics to determine the transition matrix of interest. That explains why it is the most efficient method. However, the trade-off is that it relies on the class-dependent instant-independent assumption to determine a single transition matrix. That might deteriorate the performance when such an assumption does not hold. For our method, it has the two bottle-necks of DivideMix (2 models) and HOC (nearest-neighbour search). In addition, it also requires to sample a large number of categorical samples. That explains why the method has a longer running time compared to DivideMix and HOC. In practice, we use 2 GPUs and hence, reduce the running time to 50 percent. The reported results in [Table 9](https://arxiv.org/html/2301.01405v3#A4.T9) are multiplied by 2 (i.e., GPU-h) to be fair when comparing with DivideMix and HOC.

**Table 9: Running time of some LNL methods.**
| Method | Time (GPU-h) |
| --- | --- |
| DivideMix - CIFAR-10 | 6.45 |
| HOC - CIFAR-10 | 2.65 |
| Ours - CIFAR-10 | 6.14 |
| Ours - CIFAR-100 | 19.17 |

## Appendix E Reducing number of noisy labels

As mentioned in [Section 3.2.2](https://arxiv.org/html/2301.01405v3#S3.SS2.SSS2), the space of a noisy label $\hat{Y}$ of an instance $X$ in practice is not often arbitrary (e.g., does not necessary in $\{1,\dots,C\}$), but may be in a much small set with $C_{0}$ classes, where $C_{0}\ll C$. In that case, the noisy label distribution is no longer a dense mixture of $C$ multinomial distributions, but it is sparse with only $C_{0}$ components. By exploiting this observation, we can reduce the complexity of the proposed method.
In particular, the $C$-component multinomial noisy label distribution, $p(\hat{Y}|X,Y)$, obtained through the EM algorithm is truncated to a $C_{0}$-component mixture where $C_{0}\ll C$. The approximation can be summarised as:

- •
At the initialisation stage (steps [9](https://arxiv.org/html/2301.01405v3#algx1.l9) and [10](https://arxiv.org/html/2301.01405v3#algx1.l10) in [Algorithm 1](https://arxiv.org/html/2301.01405v3#alg1) in [Appendix C](https://arxiv.org/html/2301.01405v3#A3)), the noisy label distribution of each sample is instantiated as a multinomial mixture model of $C_{0}$ components ($\pi_{i}$ is $C$-dimensional vector with only $C_{0}$ non-zero components), where each component still has $C$ categories ($\rho_{ic}\in\Delta_{C-1}$).
- •
Because the noisy label distribution of each sample is a multinomial mixture model of $C_{0}$ components, the approximation of noisy label distribution obtained in [Eq. 3](https://arxiv.org/html/2301.01405v3#S3.E3) results in a multinomial mixture model of $(K+1)C_{0}$ components. Such a mixture model can efficiently generate noisy labels with a complexity of $\order{(K+1)C_{0}C}$ given the reasonable size $C_{0}$.
- •
The generated noisy labels are passed to the EM algorithm to infer $\pi_{i}$ and $\rho_{i}$, which represent the multinomial mixture model $p(\hat{Y}|X=\mathbf{x}_{i})$ as shown in [Eq. 2](https://arxiv.org/html/2301.01405v3#S3.E2). The mixture coefficient $\pi_{i}$ (also known as the clean label probability) is a $C$-dimensional vector, which may or may not be sparse. We then enforce its sparsity by picking the top $C_{0}$ components, normalising them to 1, while setting the remaining components to zero. As a result, $\pi_{i}$ is a $C$-dimensional probability vector with $C_{0}$ non-negative components. In other words, $p(\hat{Y}|X=\mathbf{x}_{i})$ is a multinomial mixture model of $C_{0}$ components.

## Appendix F Datasets and experiment settings

##### Datasets

For the synthetic instance-dependent label noise setting, we use CIFAR-10 and CIFAR-100 datasets and follow [57] to generate synthetic instance-dependent noisy labels. For the real-world label noise setting, we use three common benchmarks, namely: Controlled Noisy Web Labels (CNWL) [22], mini-WebVision [33] with additional evaluation on the validation of ImageNet ILSVRC 2012 [45], and Animal-10N [47]. For CNWL, we use the web label noise (or red noise) setting where the labels of internet-queried images are annotated manually. For mini-WebVision, we follow previous works that take a subset containing the first 50 classes in the WebVision 1.0 dataset for training and evaluate on the clean validation set. The model trained on mini-WebVision is also evaluated on the clean validation set of ImageNet ILSVRC 2012. Finally, we evaluate the proposed method on Animal-10N dataset that contains 5 pairs of similar-looking animals.

##### Models

We follow the same setting in previous studies [32, 60] that use PreAct Resnet-18 as the backbone to evaluate the proposed method on CIFAR-10, CIFAR-100 and Red CNWL datasets. For CNWL, input images are resized from 84-by-84 pixel^2 to 32-by-32 pixel^2 to be consistent with previous evaluations [60]. For mini-WebVision, we follow the setting in DivideMix [32] by resizing images to 224-by-224 pixel^2 before passing the images into a Resnet-50. For Animal-10N, we follow experiment setting specified in [47] by training a VGG-19 backbone on 64-by-64 images to obtain a fair comparison with existing baselines.

##### Hyper-parameters

The model of interest is warmed-up for 10 epochs with a mini-batch size of 128 training samples and trained for 150 epochs in total. The optimiser used is the stochastic gradient descent (SGD) with a momentum of 0.9 and an initial learning rate of 0.02. The learning rate is decayed following a cosine annealing with a cycle of $10^{6}$ iterations (gradient update steps). For the priors defined in ([5](https://arxiv.org/html/2301.01405v3#S3.E5)), we assume both priors on the mixture coefficient (or clean label posterior) $\pi_{i}$ and the probability vector $\rho_{ic}$ of the multinomial components as symmetric Dirichlet distributions with $\alpha=1.1$ and $\beta=1.1$. For the nearest neighbours, we first randomly sample a subset of 15,000 samples then perform nearest neighbour search and select the 10 nearest samples for LLC. The parameters $\mu=0.5$ and $\gamma=0.95$ are used across all of the experiments.

Our implementation is in JAX [4] and can be accessed at
[https://anonymous.4open.science/r/identifiable_label_noise/](https://anonymous.4open.science/r/identifiable_label_noise/). All experiments are performed on a computer with a Intel 10th-gen i7 CPU, 32 GB RAM and NVIDIA A6000 GPU.

## Appendix G Additional results on common LNL benchmarks

We provide additional results on the common LNL benchmarks with synthetic instant-dependent label noise on the two datasets CIFAR-10 and CIFAR-100 in [Table 10](https://arxiv.org/html/2301.01405v3#A7.T10).

Table: Table 10: Comparison of prediction accuracy (%) on various instance-dependent label noise rates for CIFAR-10 and CIFAR-100 with different network architectures including self-supervised on the corresponding un-labelled datasets. The majority of results are adopted from [62] with † denoting results from their respective papers and ^* denoting results reported in [73]; the bold numbers denote the maximum mean values across all methods considered. Best result in bold, 2nd best in italics.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: N/A
soundness: 3
strengths: - This paper provides a clear identifiability condition for LNL: at least 2C−1 i.i.d. noisy labels needed.
- This paper offers a clean alternative to full-rank transition matrix assumptions used in prior work.
- Nearest-neighbor-based generation of pseudo noisy labels is elegant and interpretable.
-This paper includes complexity analysis and ablation experiments clarifying where the cost arises (sampling and EM).
summary: This paper studies the foundational identifiability problem in learning from noisy labels (LNL). It establishes that the standard single-label LNL setting is non-identifiable in theory, meaning the clean label distribution cannot be recovered without additional assumptions. The key contribution is proving that if each instance has at least 2C−1 i.i.d. noisy labels (where C is the number of classes), then clean labels are identifiable when modeling noisy labels as a multinomial mixture. Extensive experiments on synthetic and real-world noisy-label benchmarks support the theoretical claims, showing competitive or improved performance relative to state-of-the-art baselines such as DivideMix, HOC, and others.
weaknesses: - This paper relies on good features for nearest-neighbor graph; co-teaching partially mitigates but tight coupling remains.
- This paper argues generated labels are i.i.d. when sampled from estimated distributions, but correlation in neighbor graph may violate strict independence.
- Behavior in class-dependent noise not explicitly reported.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. In extremely noisy scenarios, generating high-quality pseudo i.i.d. labels via KNN may be difficult.
Did the authors analyze the effect of noise level on KNN reliability?
For example, is there an empirical study (similar to Table 5) showing how varying noise levels impact the accuracy or consistency of KNN-based pseudo-label construction (I mean various noise levels and various ks)?

2. Have the authors considered using feature denoising or representation refinement (e.g., pre-trained or self-supervised embeddings) to mitigate the dependence on feature quality during pseudo-label generation?
soundness: 3
strengths: 1. Novel and intuitive idea.

The identifiability-based perspective is conceptually novel in the LNL literature. The proposed KNN-based generation of “pseudo i.i.d. noisy labels” is both intuitive and innovative, providing a clear interpretation and offering potential for many future extensions.

2. Solid empirical results.

The method achieves competitive and stable performance across real-world noisy datasets. Despite its theoretical nature, the approach remains practical and delivers comparable results to state-of-the-art robust learning methods.
summary: The paper tackles the fundamental issue of identifiability in learning with noisy labels (LNL).
The authors demonstrate that when each sample is annotated with at least 2C−1 i.i.d. noisy labels (where C is the number of classes), the true clean-label distribution becomes identifiable under a multinomial mixture model.
Since collecting that many labels per sample is infeasible in practice, the authors propose a practical algorithm that approximates i.i.d. noisy labels using KNN and LLC, followed by an EM procedure to recover clean posterior estimates.
Extensive experiments on multiple benchmarks show that this surrogate approach is both theoretically justified and empirically effective.
weaknesses: 1. Practical labeling feasibility.

In practice, collecting 2C−1 i.i.d. labels per instance is unrealistic, so the framework relies entirely on pseudo-label generation. My main concern is the algorithm’s dependency on the quality of synthetic labels: when the neighborhood structure is unreliable or features are biased, the identifiability assumption may not hold.

(Optional, minor) The approach might also be computationally demanding for large C, as both the KNN and EM steps scale quadratically with the number of classes.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 3
questions: 1. **On i.i.d. Label Assumption:** Can the authors provide more rigorous empirical or theoretical support for the i.i.d. nature of generated noisy labels via nearest neighbours—especially in high-dimensional, structured data? Specifically, have they measured mutual information or entropy between neighbour-based samples, and how does this affect identifiability guarantees?
2. **Scalability:** How does the proposed method scale as $C$ increases? Could the authors provide more benchmarks (or at least detailed running time/memory analysis) for substantially larger $C$ (e.g., full ImageNet), and is the C0-sparsification sufficient for realistic streaming or web-scale settings?
3. **Non-Uniformity/Imbalance:** How does the method handle class imbalance or structured non-uniformity in annotator error rates? Is the mixture modeling robust under such misspecification? Are there modifications/extensions that could strengthen performance in such cases?
4. **Sensitivity to Hyperparameters:** Could the authors detail or provide ablations on the influence of $K$ (number of neighbours) and $L$ (number of pseudo-label samples) in more challenging benchmarks? Are there principled ways to set or automatically tune these hyperparameters (see Section 4.3 and Algorithm 1)?
5. **Algorithmic Reproducibility:** Is there publicly available implementation for the entire EM and sampling routine (including feature extraction and pre-processing), and are there resources to support scaling to multi-GPU/distributed environments?
6. **Extensions to Partial Labeling and Non-i.i.d. Annotators:** The Missing Related Works section includes several approaches to partial/noisy labelers. Could the proposed approach adapt to scenarios with partial, subjective, or correlated annotators?
soundness: 2
strengths: - **Theoretical Contribution:** The paper provides a precise, transparent identifiability condition for the LNL problem via multinomial mixture models, generalizing and clarifying prior results by relating the required number of noisy labels per sample to the number of classes in the task (Section 3.1, Table 1).
- **Methodological Novelty:** This paper proposes a practical, systematic way to generate the required number of noisy label replicates using feature-space nearest neighbours—trading off annotation quality for quantity, which is substantiated both theoretically and empirically .
- **Empirical Validation:** The paper shows strong results on several datasets, including CIFAR-10N, CNWL, mini-WebVision, and Animal-10N. It also tests the method under different kinds of label noise. These experiments prove the approach is reliable. Even when compared to current top methods, it holds up well.
- **Clarity and Reproducibility:** The paper gives full math details, especially in Appendix B. It clearly explains why each modeling choice was made. It also talks openly about the tradeoffs in the design. All the practical details are included.
- **Figure Engagement:** The ablations in **Figure 1** sharply illustrate the phase transition as the number of noisy labels or neighbours increases, validating both theoretical claims (left subfigure: test accuracy saturates at $N = 2C-1$) and practical effect of relabeling (middle: % clean after EM).
summary: This paper addresses the long-standing issue of identifiability in learning from noisy labels (LNL). The authors show that, under a multinomial mixture modeling approach, the LNL problem becomes identifiable if at least $2C-1$ independent and identically distributed (i.i.d.) noisy labels are available per instance (where $C$ is the number of classes). As manually acquiring such redundancy is impractical, the paper proposes estimating additional noisy labels via nearest-neighbour augmentation in feature space. Then the paper use an Expectation-Maximisation (EM) algorithm to estimate the clean label distributions. This algorithm works on the mixture model. The experiments show strong results on both synthetic and real-world datasets. This paper also ran many ablation studies. These studies back up our theoretical ideas and design decisions.
weaknesses: 1. **i.i.d. Sampling Validity and Empirical Support:** Although the paper claims that additional noisy labels from the approximation $\tilde{P}(\hat{Y}|X)$ are i.i.d. by construction (Section 3.2.1), this rests on the functional form of the mixture, and the empirical validation is limited. While Table 5 indicates a high degree of label consistency among neighbours on CIFAR-10N, it does not quantify the residual dependencies or their downstream effect on identifiability for more structured or heavily corrupted labels.
2. **Computational Complexity for Large C:** The method’s sampling and EM steps incur $\mathcal{O}(C^2(K+1))$ complexity per sample (Table 2, Appx E), which becomes prohibitive as $C$ grows (e.g., ImageNet-scale tasks). The practical efficacy of the C0-sparsification trick (Appendix F) is not deeply analyzed or benchmarked. The bottlenecks, highlighted in the right subfigure of **Figure 1**, may limit scalability and have not been fully benchmarked against distributed or alternative data-driven LNL schemes.
4. **Potential Overfitting to Benchmark Settings:** The method depends heavily on pretrained feature extractors and heavy preprocessing—such as SimCLR or DINO—in many experiments. This might unintentionally leak information or lead to biased results. The paper tries to reduce this risk by using co-teaching (Section 3.2.2). However, it’s not clear how much the good performance comes from strong self-supervised features. It’s also uncertain whether the approach would work as well in areas where those kinds of features aren’t as helpful.
5. **Algorithmic Details and Practical Usability:** The nearest-neighbour scheme, use of LLC, and the stochasticity of the sampling routine, while justified, would benefit from more explicit sensitivity analyses and implementation guidance. Algorithm 1, as presented, leaves choices of $K$, $L$, and ensemble size to heuristics; there is limited discussion on tuning strategies for practitioners.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: Please refer to weaknesses.
soundness: 2
strengths: 1. The proposed theorem on the identifiability condition is interesting and theoretically sound.
2. The experimental results demonstrate the effectiveness of the proposed approach in improving model robustness under noisy settings.
summary: This paper introduces a multinomial mixture modelling approach to address the identifiability problem in learning from noisy labels (LNL). The authors theoretically prove that LNL becomes identifiable when each sample has at least 2C−1 independent noisy labels, enabling the unique recovery of clean label distributions without relying on heuristic assumptions. To make this feasible in practice, they propose generating additional pseudo noisy labels from nearest neighbours and applying an Expectation–Maximization algorithm to infer clean labels. Extensive experiments on synthetic, web-controlled, and real-world noisy datasets demonstrate that the proposed method accurately estimates clean labels and achieves performance competitive with state-of-the-art LNL techniques.
weaknesses: 1. To be honest, I do not catch up the meaning of the task setting. The paper assumes that each sample is associated with multiple noisy labels, but in practical training datasets, it is rare for a single sample to have multiple annotations. This seems inconsistent with the practicality the authors aim to address.
2. Requiring 2C−1 additional noisy labels per sample would result in a prohibitively large workload.
3. It is not clear whether there are additional constraints for the identifiability condition—such as the i.i.d. assumption for the noisy samples. For instance, what happens if the 2C−1 noisy labels all belong to the same category?
4. The experimental setup lacks sufficient detail. I am a bit confused about what the accuracy in Tables 3 and 4 represents—does it refer to the accuracy of clean label identification, or to the image classification accuracy of the model trained on the selected clean samples? If it is the former, what about the recall metric? If it is the latter, what is the clean identification accuracy?
5. In Figure 1, only classification accuracy is reported. Since classification accuracy can be influenced by various factors (e.g., data scaling effects), directly showing the curve of clean-label identification accuracy would more clearly demonstrate the proposed identifiability condition.