RML++: Regroup Median Loss for Combating Label Noise

Abstract

Training deep neural networks (DNNs) typically necessitates large-scale, high-quality annotated datasets. However, due to the inherent challenges of precisely annotating vast numbers of training samples, label noise—characterized by potentially erroneous annotations—is common yet detrimental in practice. Currently, to combat the negative impacts of label noise, mainstream studies follow a pipeline that begins with data sampling and is followed by loss correction. Data sampling aims to partition the original training dataset into clean and noisy subsets, but it often suffers from biased sampling that can mislead models. Additionally, loss correction typically requires knowledge of the noise rate as a priori information, of which the precise estimation can be challenging. To this end, we propose a novel method, Regroup Median Loss Plus Plus (RML++), that addresses both of the previous drawbacks. Specifically, the training dataset is partitioned into clean and noisy subsets using a newly designed separation approach, which synergistically combines prediction consistency with an adaptive threshold to ensure a reliable sampling. Moreover, to ensure the noisy subsets can be robustly learned by models, we suggest to estimate the losses of noisy training samples by utilizing the same-class samples from the clean subset. Subsequently, the proposed method corrects the labels of noisy samples based on the model predictions with the regularization of RML++. Compared to state-of-the-art (SOTA) methods, RML++ achieves significant improvements on both synthetic and challenging real-world datasets. The source code is available at https://github.com/Feng-peng-Li/RML-Extension.

Proofs

1.1 Proof of Theorem 1

We first introduce necessary lemmas that will facilitate our proof.

Lemma 1

The classifier $\hat{f}_{\tau }$ with the threshold $\tau$ can be expressed as:

$$\begin{aligned} {f}_{\tau }(x) & = \textrm{sign}(\hat{\eta }(x) - \tau )\\ & = \textrm{sign} \left( \eta (x) - \frac{\frac{1}{2}+\frac{1}{\beta }(\tau -\frac{1}{2})-\rho _{-1}}{1-\rho _{+1}-\rho _{-1}} \right) . \end{aligned}$$

Proof

By definition, we have:

$$ \begin{aligned} \tilde{\eta }(X)&= P(\tilde{Y} = 1, Y = 1 | X) + P(\tilde{Y} = 1, Y = -1 | X) \\&= P(\tilde{Y} = 1 | Y = 1) P(Y = 1 | X)\\&\quad + P(\tilde{Y} = 1 | Y = -1) P(Y = -1 | X) \\&= (1 - \rho _{+1}) \eta (X) + \rho _{-1} (1 - \eta (X)) \\&= (1 - \rho _{+1} - \rho _{-1}) \eta (X) + \rho _{-1}. \end{aligned} $$

Therefore,

$$\begin{aligned} \hat{f}_{\tau }(x) & =\textrm{sign}(\hat{\eta }(x) - \tau )\\ & =\textrm{sign}\left( \frac{1}{2}+\beta (\tilde{\eta }(x)-\frac{1}{2})-\tau \right) \\ & =\textrm{sign}\left( \tilde{\eta }(x)-(\frac{1}{2}+\frac{1}{\beta }(\tau -\frac{1}{2}))\right) \\ & =\textrm{sign}\left( (1 - \rho _{+1} - \rho _{-1}) \eta (x) + \rho _{-1}-(\frac{1}{2}+\frac{\tau -\frac{1}{2}}{\beta })\right) \\ & =\textrm{sign} \left( \eta (x) - \frac{\frac{1}{2}+\frac{1}{\beta }(\tau -\frac{1}{2})-\rho _{-1}}{1-\rho _{+1}-\rho _{-1}} \right) . \end{aligned}$$

Lemma 2

($\alpha$-weighted Bayes Optimal (Scott, 2012)) Define $U_{\alpha }$-risk under distribution D as

$$ R_{\alpha ,D}(f)=\mathbb {E}_{(X,Y) \sim D}[U_{\alpha }(f(X),Y)]. $$

Then, $f^{*}_{\alpha }=\textrm{sign}(\eta (x)-\alpha )$ minimizes $U_{\alpha }$-risk.

Now we proceed to prove Theorem 1 and Corollary 1.

Proof

By Lemma 1, the optimal threshold $\tau ^*$ is expected to satisfy:

$$ \frac{\frac{1}{2}+\frac{1}{\beta }(\tau -\frac{1}{2})-\rho _{-1}}{1-\rho _{+1}-\rho _{-1}} = \frac{1}{2}. $$

Solving this equation yields $\tau ^*=\frac{1}{2}+\frac{\beta }{2}(\rho _{-1}-\rho _{+1})$.

Applying Lemma 2, it follows directly that the $\alpha$-weighted Bayes classifier under noisy distribution is:

$$ \tilde{f}_{\alpha }^*={{\,\mathrm{arg\,min}\,}}_f R_{\alpha ,D_{\rho }}(f)=\textrm{sign}(\tilde{\eta }(x)-\alpha ). $$

Combining this with the result from Lemma 1, we observe that when

$$ \alpha =\frac{1}{2}+\frac{1}{\beta }(\tau -\frac{1}{2}), $$

it holds that $\hat{f}_{\tau }=\tilde{f}_{\alpha }^*$. By selecting the optimal threshold $\tau ^*$, we obtain $\alpha ^*=\frac{1-\rho _{+1}+\rho _{-1}}{2}$, as required.

1.2 Proof of Theorem 2

Proof

For convenience, we denote $\ell _{\textrm{RML}}(f(\varvec{x}),\tilde{y})$ by $\ell _{\textrm{RML}}$. First of all, with the regroup number n for RML++, we observe that the event $\left\{ |\ell _{\textrm{RML}}-\hat{\mu }|>\epsilon \right\}$ implies that at least $\frac{n+1}{2}$ of mean loss $\ell ^s_i$ in $\mathcal {W}^{*}$ have to be outside $\epsilon$ distance to $\hat{\mu }$. Namely,

$$ \left\{ |\ell _{\textrm{RML}}-\hat{\mu }|>\epsilon \right\} \subset \left\{ \sum ^{n+1}_{i=1} \mathbb {1}(|\ell ^s_i-\hat{\mu }|>\epsilon )\geqslant \frac{n+1}{2}\right\} . $$

Define $Z_i=\mathbb {1}(|\ell ^s_i-\hat{\mu }|>\epsilon )$. Let $p_{\epsilon ,k}=\mathbb {E}[Z_i]=P\left( |\ell ^s_i-\hat{\mu }|>\epsilon \right)$, $i=1,\dots ,n$, and $p_{\epsilon }=\mathbb {E}[Z_{n+1}]=P\left( |\ell -\hat{\mu }|>\epsilon \right)$, then we can obtain

$$\begin{aligned} & P\left( |\ell _\textrm{RML}-\hat{\mu }|>\epsilon \right) \leqslant P\left( \sum ^{n+1}_{i=1} Z_i \geqslant \frac{n+1}{2}\right) \\ & = P\left( \sum ^{n+1}_{i=1} (Z_i-\mathbb {E}[Z_i]) \geqslant \frac{n+1}{2}-n p_{\epsilon ,k}-p_{\epsilon }\right) \\ & =P\left( \frac{1}{n+1}\sum ^{n+1}_{i=1} (Z_i-\mathbb {E}[Z_i]) \geqslant \frac{1}{2}-\frac{n}{n+1}p_{\epsilon ,k}-\frac{1}{n+1}p_{\epsilon }\right) . \end{aligned}$$

Because $Z_i$ are independent random variable bounded by 1, then by Hoeffding’s inequality (one-sided), with any $\tau >0$, we can obtain

$$\begin{aligned}P\left( \frac{1}{n+1}\sum ^{n+1}_{i=1} (Z_i-\mathbb {E}[Z_i]) \geqslant \tau \right) \leqslant \textrm{e}^{-2(n+1)\tau ^2}. \end{aligned}$$

As a result,

$$\begin{aligned} & P\left( |\ell _{\textrm{RML}}-\hat{\mu }|>\epsilon \right) \\ & \leqslant P\left( \frac{1}{n+1}\sum ^{n+1}_{i=1} (Z_i-\mathbb {E}[Z_i]) \geqslant \frac{1}{2}-\frac{n}{n+1}p_{\epsilon ,k}-\frac{1}{n+1}p_{\epsilon }\right) \\ & \leqslant \textrm{e}^{-2(n+1)(\frac{1}{2}-\frac{n}{n+1}p_{\epsilon ,k}-\frac{1}{n+1}p_{\epsilon })^2}. \end{aligned}$$

Due to $\textrm{Var}_{\varvec{X^*}|\tilde{Y}=\tilde{y}}[\ell (f(\varvec{X^{*}}),\tilde{y})]=\hat{\sigma }^2<\infty$ and Chebyshev’s inequality, we can obtain

$$\begin{aligned} p_{\epsilon ,k} & =P(|\ell ^s_i-\hat{\mu }|>\epsilon )\leqslant \frac{\hat{\sigma }^2}{k\epsilon ^2} \ \text {and} \\ p_{\epsilon } & =P(|\ell -\hat{\mu }|>\epsilon )\leqslant \frac{\hat{\sigma }^2}{\epsilon ^2}. \end{aligned}$$

Then the bound is

$$ \begin{aligned} P\left( |\ell _{\textrm{RML}}-\hat{\mu }|>\epsilon \right)&\leqslant \textrm{e}^{-2(n+1)(\frac{1}{2}-\frac{n}{n+1}p_{\epsilon ,k}-\frac{1}{n+1}p_{\epsilon })^2}\\&\leqslant \textrm{e}^{-2(n+1)(\frac{1}{2}-\frac{n}{n+1}\frac{\hat{\sigma }^2}{k\epsilon ^2}-\frac{1}{n+1}\frac{\hat{\sigma }^2}{\epsilon ^2})^2}\\&=\textrm{e}^{-2(n+1)(\frac{1}{2}-\frac{n+k}{n+1}\frac{\hat{\sigma }^2}{k\epsilon ^2})^2}\\&=\textrm{e}^{-\mathrm {C_1}(\frac{1}{2}-\mathrm {C_2}\frac{\hat{\sigma }^2}{\epsilon ^2})^2}, \end{aligned} $$

where $\mathrm {C_1}=2(n+1),\mathrm {C_2}=\frac{n+k}{k(n+1)}>0.$ $\square$

Remark 2

Note that after the operation in Eqs. (1) and  (5), intuitively, losses are closer to the true loss and so that number of $\ell _i^s$ outside $\epsilon$ distance to $\hat{\mu }$ decreases. Therefore, $\sum ^{n+1}_{i=1} \mathbb {1}\left( |\ell ^s_i-\hat{\mu }|>\epsilon \right)$ decreases and so does $P\left( \sum ^{n+1}_{i=1} Z_i \geqslant \frac{n+1}{2}\right)$, i.e., the upper bound in Theorem 2 is reduced.