# Bootstrapping the Relationship Between Images and Their Clean and Noisy
Labels

Brandon Smart
Australian Institute for Machine Learning
University of Adelaide, Australia
<EMAIL_ADDRESS>Gustavo Carneiro
Centre for Vision, Speech and Signal Processing
University of Surrey, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

Many state-of-the-art noisy-label learning methods rely on learning mechanisms
that estimate the samples’ clean labels during training and discard their
original noisy labels. However, this approach prevents the learning of the
relationship between images, noisy labels and clean labels, which has been
shown to be useful when dealing with instance-dependent label noise problems.
Furthermore, methods that do aim to learn this relationship require cleanly
annotated subsets of data, as well as distillation or multi-faceted models for
training. In this paper, we propose a new training algorithm that relies on a
simple model to learn the relationship between clean and noisy labels without
the need for a cleanly labelled subset of data. Our algorithm follows a
3-stage process, namely: 1) self-supervised pre-training followed by an early-
stopping training of the classifier to confidently predict clean labels for a
subset of the training set; 2) use the clean set from stage (1) to bootstrap
the relationship between images, noisy labels and clean labels, which we
exploit for effective relabelling of the remaining training set using semi-
supervised learning; and 3) supervised training of the classifier with all
relabelled samples from stage (2). By learning this relationship, we achieve
state-of-the-art performance in asymmetric and instance-dependent label noise
problems111Supported by Australian Research Council through grants DP180103232
and FT190100525.. Code is available at
https://github.com/btsmart/bootstrapping-label-noise.

##  1 Introduction

Supervised deep learning has had great success generating effective
classification models from sets of labelled training data [24, 26]. Modern
deep learning models require large-scale datasets to achieve state-of-the-art
(SOTA) results [38, 39]. However, real-world large-scale datasets, such as
those collected from search engines or available from hospitals and clinics,
tend to have a non-negligible amount of instance-dependent label noise (IDN)
[32, 53]. Existing methods often attempt to address instance-independent label
noise (IIN), such as symmetric or asymmetric noise [65, 15, 58]. Handling the
IDN present in large-scale real-world datasets has become one of the main
research problems in the field.

When naively trained with noisy-labelled data, deep learning models generalise
poorly because they can easily overfit the incorrectly labelled samples [62].
Many methods have been developed for handling label noise, with SOTA
approaches relying on sample relabelling mechanisms. These strategies are
based on techniques to estimate the relationship between images and clean
labels, and after relabelling, the old noisy labels are discarded [29, 65,
47]. However, to model how different image features and noisy labels affect
the mislabelling process in IDN, we need to estimate the relationship between
images, clean labels and noisy labels [65, 17]. Some methods have attempted to
model this relationship with noise-transition matrices and corrective layers
for asymmetric noise [57, 15, 37] or part-dependant noise in place of
instance-dependant noise [56], but they failed to achieve SOTA results.

Figure 1: On the left, we show a ‘normal’ deep neural network model used for
noisy label learning tasks. On the right, we present a ‘modified’ model that
can learn the relationship between images $\mathbf{x}$, noisy labels
$\tilde{\mathbf{y}}$ and clean labels $\mathbf{y}$, similar to those used by
methods that have access to a clean set of data [21, 52, 17]. Figure 2: Our
proposed algorithm. The bootstrapping stage consists of self-supervised pre-
training, followed by early-stopping classification training to identify a
small set of confidently relabelled samples (i.e., clean labelled samples).
This set is then used to learn the relationship between images, noisy labels
and clean labels during semi-supervised learning, and at the end of this
stage, we relabel the samples classified as noisy during bootstrapping. The
last stage is the final training that trains the classifier using the clean
and noisy samples identified in the SSL stage.

Rather than the usual noisy-label learning setting, where a set of cleanly
annotated samples is not available, some methods assume the existence of a
subset of training data containing images, clean labels and noisy labels [21,
52, 17]. By training a model that predicts clean labels from both images and
noisy labels (see right of Figure 1), these methods are able to learn the
relationship between image features, noisy labels and clean labels, allowing
them to model IDN and more effectively relabel noisy samples. However, it can
be expensive, difficult and time-consuming to obtain a clean subset of data
with noisy labels and clean labels that is representative of the instance-
dependant noise in the dataset. Furthermore, these methods require
distillation to a more standard model (such as the one on the left of Figure
1) for evaluation on samples without labels.

In this paper, we introduce a new algorithm to learn the relationship between
images and their clean and noisy labels without using any clean-label set. Our
algorithm follows a 3-stage process (see Fig. 2): 1) Bootstrapping: self-
supervised pre-training followed by an early-stopping training [62] of the
classifier that receives images and ‘null’ labels as input and predicts the
noisy labels as output – this stage forms a subset of predicted clean labels
for the second stage of training; 2) Semi-supervised Learning: use this
predicted clean subset to learn the relationship between images, noisy labels
and clean labels, which we exploit for an effective, explicit relabelling of
the remaining training set; and 3) Final training: supervised training of the
classifier using the relabelled samples. The main contributions of this paper
are:

  * •

An effective three-stage training algorithm designed to address instance-
dependent label noise by learning the relationship between images and their
clean and noisy labels – using a noise-transition sample balancing scheme,
explicitly relabelling training samples and without requiring a cleanly
annotated training set;

  * •

A method that reaches SOTA asymmetric and instance dependent label noise
results using a simple single-model architecture, unlike DivideMix [29] (and
its derivatives such as [42, 68, 35, 11, 22]) that require a more complex
2-model architecture.

  * •

A ‘label dropping’ strategy that removes the need for distillation to a
standard model and allows predictions to be made on samples with and without
noisy labels;

##  2 Related Work

###  2.1 Noisy Label Learning Based on Semi-supervised Learning (SSL)

Many SOTA methods in noisy label learning use SSL techniques to perform label
correction and consistency regularization. DivideMix [29] and variants [42,
11, 68] perform sample re-labelling with co-teaching and MixMatch data
augmentation [6]. ELR+ [33] and PES [5] similarly use MixUp [63] based SSL on
top of a regularising loss functions. These techniques are effective for
symmetric and asymmetric noise, but are dependent on carefully tuned
hyperparameters and cautious integration of the sample re-labelling and SSL
techniques used.

To identify the incorrectly labelled samples for forming the unlabelled set,
many methods depend on loss-separation techniques, relying on the ability of
deep networks to learn clean samples faster than noisy samples [2], which
leads to lower loss values for clean samples after a few stages of training
[18, 7, 1, 29, 59]. FINE alternatively uses eigen-decomposition to separate
samples in feature space [22]. However, such automatic and dynamic
identification of noisy-label samples is a brittle process that tends to fail
in challenging noisy-label learning scenarios, such as instance-dependent
label noise, because the differences between hard clean-label and noisy-label
samples can be subtle during early training stages.

###  2.2 Label Transition Estimation Methods

Many methods attempt to model the class-dependent asymmetric noise, such as
with a label transition matrix [57], by learning noise-adaption layers and
performing loss-correction [15, 37], or by using reconstruction error as a
consistency objective [40]. However, these methods are not as competitive as
SSL approaches in Sec. 2.1 because they generally do not address instance-
dependent noise and have limited mechanisms to make use of mislabeled samples.
Methods that attempt to handle semantic noise by estimating instance-based
transition matrices can in principle deal with semantic noise [15] and can
provide guarantees on convergence and bounds on generalization error [65], but
they do not provide SOTA results in practice.

###  2.3 Methods Based on Clean Validation Sets

Alternatively, researchers have explored learning methods that require the
existence of a small, additional clean set of data to learn from. For
instance, many meta-learning strategies require clean validation samples to
adjust the weights of each training sample [41], to simulate regular training
with synthetic noise labels [30], to learn an explicit weighting function
[44], or to estimate the noise transition matrix [54]. Other noisy label
learning algorithms rely on clean sets of data for which noisy labels and
clean labels exist for samples, so that the relationship between image
features, noisy labels and clean labels can be learned [52, 21, 17], using
fully-connected neural networks to predict true labels from images and their
noisy labels. Together, these methods show the utility of representative clean
sets of data to the noisy label problem, but they rely on manual labelling,
which can be expensive and time-consuming to collect, particularly in domains
that require a high degree of expertise for labellers, such as medical imaging
[34, 67].

Other methods aim to dynamically construct a pseudo-clean set out of high-
confidence samples, such as by using K-Nearest Neighbours to identify related
samples in the feature space [4, 36], or by using meta-learning to identify a
dictionary of dynamically updating valuable training samples [66].

###  2.4 Background Material

Our method relies on many techniques previously developed in the field, such
as self-supervision, SSL and data augmentation. Recently, self-supervised
methods such as SimCLR [8, 9] and SCAN [50] have been used for pre-training,
or as auxilliary objectives in noisy-label learning tasks [68, 42], due to
their ability to learn high-level features from noisy data without the risk of
overfitting incorrect labels. In this paper, we utilize the SSL method
FixMatch [46], which uses pseudo-labelling thresholds and consistency between
strong and weak augmentations to regularize training through consistency
regularization [3, 49, 25] and entropy minimization [16, 27]. Strong data
augmentation strategies, such as RandAugment [13], AutoAugment [12] and MixUp
[63] have been shown to be effective for regularising training, preventing
overfitting and dramatically improving the tolerance of algorithms to higher
noise levels [35, 29, 1].

##  3 Methodology

Our algorithm (see Fig. 2) is motivated by the objective to train a model that
can accurately relabel samples by predicting true labels from images and noisy
labels without requiring clean-labelled data. The stages of the proposed
algorithm are: 1) Bootstrapping: perform self-supervised pre-training and
early-stopping training to identify a representative, clean subset of samples,
2) SSL: learn the instance-dependant noise relationship from the clean set
(from stage 1) and use it to relabel the remaining noisy samples, and 3) Final
Training: use the relabelled samples from stage 2 to train a final,
regularized classifier.

For the methods described below, assume the availability of a training set
$\mathcal{D}=\\{(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i})\\}_{i=1}^{|\mathcal{D}|}$,
where $\mathbf{x}\in\mathcal{X}\subset\mathbb{R}^{H\times W\times R}$ denotes
an image of size $H\times W$ with $R$ colour channels, and
$\tilde{\mathbf{y}}\in\mathcal{Y}\subset\\{0,1\\}^{|\mathcal{Y}|}$ represents
the one-hot noisy label. Our model, referred to as ’modified’, receives an
image and the noisy label at the input and outputs a clean label
classification distribution, with
$f_{\theta}:\mathcal{X}\times\mathcal{Y}\to\Delta_{|\mathcal{Y}|-1}$, where
$\Delta_{|\mathcal{Y}|-1}$ represents the $|\mathcal{Y}|-1$ probability
simplex, and $\theta\in\Theta$ denotes the model parameters. Note that we also
consider a ‘normal’ model, which is a model that takes an image input and
outputs a classification, with
$f_{\theta}:\mathcal{X}\to\Delta_{|\mathcal{Y}|-1}$.

###  3.1 Bootstrapping

The goal of this first stage is to train a model that accepts images and noisy
labels and predicts clean labels, however at the beginning of training we only
have access to images and noisy labels from $\mathcal{D}$. Following [50, 68],
we start with SimCLR pre-training [8], which allows us to learn an initial
feature representation from $\mathcal{D}$ without the risk of overfitting.

Next, we take the pre-trained model above to learn a classifier with early-
stopping and small learning rate with

$\theta^{*}=\arg\min_{\theta}\frac{1}{|\mathcal{D}|}\sum_{(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i})\in\mathcal{D}}\mathbb{E}_{a(.)\sim\mathcal{A}_{S}}\left[\ell_{CE}(\tilde{\mathbf{y}}_{i},f_{\theta}(a(\mathbf{x}_{i}),\mathbf{0}_{|\mathcal{Y}|}))\right],$

(1)

where $a(.)$ is a strong data augmentation sampled from the set of strong data
augmentation functions $\mathcal{A}_{S}$, $\ell_{CE}(.)$ denotes the cross-
entropy loss function, and $\mathbf{0}_{|\mathcal{Y}|}$ is a ‘null’ label
vector with $|\mathcal{Y}|$ zeros.

Then, we use our trained model to generate a prediction distribution for all
training samples using test-time weak augmentation, as follows:

$\hat{\mathbf{y}}_{i}=\mathbb{E}_{a(.)\sim\mathcal{A}_{W}}\left[f_{\theta^{*}}(a(\mathbf{x}_{i}),\mathbf{0}_{|\mathcal{Y}|})\right],$
(2)

where $a(.)$ is a weak augmentation sampled from the set of weak data
augmentation functions $\mathcal{A}_{W}$. We also have dropout enabled during
this evaluation process. By using dropout and multiple weak augmentations to
evaluate samples, we penalise samples with highly confident but inconsistent
predictions [65]. The confidence prediction for $\mathbf{x}_{i}$ is given by
$\max_{c\in\mathcal{Y}}\hat{\mathbf{y}}_{i}(c)$.

We then split the dataset into a confident clean set and a noisy set. However,
if we naively select the most confident samples, we will disproportionally
select samples from easy classes, and samples whose original noisy labels were
correct. We want the clean set to contain representative samples from all
classes and noise transitions in the dataset, as the upcoming SSL process can
only learn noise transitions which are present in the clean set. To achieve
this, we propose noise-transition sample balancing that first estimates the
dataset’s noise transition matrix $\mathbf{T}$ by using the noisy labels and
predicted labels for the 90% of most confident predictions per class, where
$\mathbf{T}_{ij}$ represents the estimated proportion of samples in the
dataset with the noisy label $i$ and clean label $j$. We then select the
$K\times|\mathcal{Y}|\times\mathbf{T}_{ij}$ most confident samples from each
noise transition, as well as any other samples $\mathbf{x}_{i}$ where
$\max_{c\in\mathcal{Y}}\hat{\mathbf{y}}_{i}(c)>\tau$, where $K$ is a
hyperparameter controlling the minimum fraction of samples from each subset we
want to select, and $\tau$ is a hyperparameter controlling how confident a
prediction needs to be before it is guaranteed to be selected.

We note that this process does not guarantee that all instance-dependent
relationships between image features and noisy label transitions are captured,
but in practice this ensures a large coverage of the different noise
transitions present in the dataset. This ‘noise-based’ balancing approach can
be contrasted against the usual class-based balancing typically seen in noisy-
label learning methods, where samples are selected to balance the number of
samples per class. The initial clean set will contain the samples with both
the noisy and estimated clean labels with
$\mathcal{C}=\\{(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i},\hat{\mathbf{y}}_{i})|(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i})\in\mathcal{D}\\}$,
and the initial noisy set will contain the samples and noisy labels as
$\mathcal{U}=\\{(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i})|(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i},\hat{\mathbf{y}}_{i})\notin\mathcal{C}\text{,
and }(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i})\in\mathcal{D}\\}$.

###  3.2 Semi-Supervised Learning (SSL) for Noisy Label Correction

The next stage of our framework takes the initial clean set $\mathcal{C}$ and
the initial noisy set $\mathcal{U}$ to train the SSL model, where images and
noisy labels (the model inputs) are present for all samples, and the true
labels (the model output) are present for samples in $\mathcal{C}$. Our SSL
algorithm is based on FixMatch (see Fig. 3), which achieves competitive
performance by focusing on consistency regularization and entropy minimization
[46]. We do not reinitialize the network before semi-supervised learning,
instead using the bootstrapping process as a form of warmup.

Figure 3: The noisy-label FixMatch algorithm.

Because we are learning to predict the ‘true’ labels of samples from images
and noisy labels, our model is able to learn a joint distribution between the
three, similar to works that require a clean set [52, 21, 17]. However, if we
were to train our model to always make predictions from images and noisy
labels, our model would no longer be able to make meaningful predictions on
samples without associated noisy labels, such as those in a ‘test’ set. To
remedy this, we randomly ‘drop’ the one-hot noisy label from samples 50% of
the time, replacing it with a ‘null’ label. By doing this, our model also
learns a direct relationship between images and true labels without depending
on the noisy labels, allowing us to evaluate test samples by passing them into
the model alongside a ‘null’ label. In our implementation of FixMatch, we drop
the noisy label of supervised samples and strong augmentations of unsupervised
samples 50% of the time. However, we keep the noisy labels for the weakly
augmented unsupervised samples as we want to always use these noisy labels to
predict higher accuracy pseudo-labels, given that the loss is not
backpropagated along these samples (see Fig. 3). We experiment with this
decision in the Supplementary Material. The SSL training is based on the
following optimisation:

$\begin{aligned} \theta^{*}&=\arg\min_{\theta\in\Theta}\\\
&\frac{1}{|\mathcal{C}|}\sum_{(\mathbf{x}_{i},\tilde{\mathbf{x}}_{i},\hat{\mathbf{y}}_{i})\in\mathcal{C}}\mathbb{E}_{a(.)\in\mathcal{A}_{W}}[\ell_{CE}(\hat{\mathbf{y}}_{i},f_{\theta}(a(\mathbf{x}_{i}),\iota_{50\%}(\tilde{\mathbf{y}}_{i})))]+\\\
&\frac{1}{|\mathcal{U}|}\sum_{(\mathbf{x}_{i},\tilde{\mathbf{x}}_{i})\in\mathcal{U}}\mathbb{I}(\max\bar{\mathbf{y}}_{i}>\kappa)\mathbb{E}_{a(.)\in\mathcal{A}_{S}}[\ell_{CE}(\lceil\bar{\mathbf{y}}_{i}\rceil,f_{\theta}(a(\mathbf{x}_{i}),\iota_{50\%}(\tilde{\mathbf{y}}_{i})))],\end{aligned}$

(3)

where $\mathbb{I}(.)$ denotes an indicator function,
$\bar{\mathbf{y}}_{i}=\mathbb{E}_{a(.)\sim\mathcal{A}_{W}}[f(a(\mathbf{x}_{i}),\tilde{\mathbf{y}}_{i})]$,
$\iota_{50\%}(\tilde{\mathbf{y}}_{i})$ randomly returns
$\tilde{\mathbf{y}}_{i}$ or $\mathbf{0}_{|\mathcal{Y}|}$, each with $50\%$
chance, and $\lceil\bar{\mathbf{y}}_{i}\rceil$ is an operator to transform
$\bar{\mathbf{y}}_{i}$ into a binary vector, with $1$ for the class with
largest probability and $0$ otherwise. After this SSL stage, we re-label the
whole training set to form

$\bar{\mathcal{D}}=\\{(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i},\bar{\mathbf{y}}_{i})|(\mathbf{x}_{i},\tilde{\mathbf{y}}_{i})\in\mathcal{D}\\},$
(4)

with $\bar{\mathbf{y}}_{i}$ defined in (3). As in the bootstrapping phase of
training, we enable dropout when averaging over the predictions of multiple
weak augmentations to calculate $\bar{\mathbf{y}}_{i}$. Note in (4) that our
model uses the learned relationship between images, noisy labels and ‘true’
labels to relabel the remaining noisy samples.

###  3.3 Final Model Training

After forming $\bar{\mathcal{D}}$, we train a final model with strong
augmentations and MixUp, due to their robustness to any noise that may remain
in the re-labelled training set [1, 29]. MixUp is applied on both images and
their noisy labels together. After applying Mixup, we randomly replace the
noisy label with a ‘null’ label in 50% of samples.

##  4 Experiments

###  4.1 Data sets

To investigate our method, we perform experiments using the CIFAR-10,
CIFAR-100 [23], Animal10N [47], and Webvision [32] datasets. CIFAR-10 and
CIFAR-100 consist of 50,000 training and 10,000 testing images of size
$32\times 32$ pixels, with 10 and 100 classes respectively. As CIFAR-10 and
CIFAR-100 do not contain label noise, we follow the literature and perform
experiments with different types of controlled, synthetic label noise. The
first type of noise is the Polynomial Margin Diminishing (PMD) semantic noise
[64], where confusing samples near decision boundaries are mislabelled at
higher rates than samples far from decision boundaries. The second type is the
semantic noise introduced by Lee et al. [28], where incorrect predictions from
trained VGG [45], DenseNet [20], and ResNet [19] models are used to generate
mislabelled samples (which we refer to as ‘RoG’ noise). We also test our
system with symmetric noise rates of $\\{20\%,50\%,80\%,90\%\\}$ and
asymmetric noise using the mapping from [29, 37] with $40\%$ rate.

The Animal10N dataset [47] consists of 50,000 training images and 5,000
testing images of size $64\times 64$, consisting of five pairs of semantically
similar classes. Images are collected for each label using online search
engines, resulting in incorrect classifications for an estimated $6\%$ to
$10\%$ of samples. Finally, we test with Mini-Webvision, which consists of the
65,944 samples which make up the first 50 classes of the Webvision dataset
that contains images collected from the internet. Images are resized to
$256\times 256$, and the corresponding 50 classes in the ILSVRC12 dataset [14]
are also used for validation.

###  4.2 Implementation

Following contemporary work [29, 11, 33], we use a PreAct-ResNet-18 (PRN18)
network [19] as our backbone model for CIFAR10 and CIFAR100 experiments, use a
VGG19 model [45] as our backbone for Animal10N, and use a Inception-ResnetV2
model [48] as our backbone for Webvision. For weak augmentations, we use
horizontal flipping and random cropping, and for strong augmentations we used
AutoAugment [12], followed by horizontal flipping and random cropping. For all
experiments, we perform bootstrapping with strong augmentations and perform
pseudo-labelling with with 25 weak augmentations. Final model training is done
using Mixup [63] (with $\alpha=1$). For all stages of training, we use
stochastic gradient descent, with additional information about the optimizer
and training schedule hyperparameters provided in the supplementary material.
For Webvision, we additionally use label smoothing (with $\epsilon=0.1$).
Following existing implementations of FixMatch (such as by TorchSSL [61]), we
use Exponential Moving Average (EMA) models to perform temporal ensembling
[25]. For fair comparison with existing noisy-label learning methods, we
shorten the training schedules typically used by FixMatch implementations (we
use 100,000 training iterations with $\mu=4$ rather than 1,000,000 iterations
with $\mu=8$).

We report two sets of results for our experiments in order to understand how
the use of noisy labels during semi-supervised learning can improve results:
’Normal Model’ and ’Modified Model’. In both cases, we utilise the training
procedure outlined in Figure 2, however:

  1. 1)

In ‘Normal Model’, we use a standard model which only accepts image inputs.
Because this type of model does not aim to learn the relationship between
noisy labels and clean labels, we perform class-based balancing rather than
the proposed noise-based balancing.

  2. 2)

In ‘Modified Model’, we use noise-based balancing, as well as the model that
accepts images and noisy labels, as described in Sec. 3.

For all our experiments, we also report the accuracy obtained from test-time
augmentation, where 25 weakly augmented versions of each testing sample are
generated, and the model’s predictions (with dropout enabled) are averaged to
generate a final prediction. Because this extends the inference time for our
model, we report these results separately in italics.

###  4.3 Results

Method | Top-1
---|---
Cross Entropy | 79.4
SELFIE [47] | 81.8
PLC [64] | 83.4
NCT [43] | 84.1
Ours (Normal Model) | 85.84
\+ Test-Time Aug. | 86.98
Ours (Modified Model) | 88.48
\+ Test-Time Aug. | 89.38

Table 1: Test accuracy (%) for Animal10N. Top methods within $1\%$ in bold
(Results other than ours are from [43]).

Method | Webvision | ILSVRC2012
---|---|---
| Top-1 | Top-5 | Top-1 | Top-5
ELR [33] | 76.26 | 91.26 | 68.71 | 87.84
ELR+ [33] | 77.78 | 91.68 | 70.29 | 89.76
PropMix [11] | 78.84 | 90.56 | / | /
NGC [55] | 79.16 | 91.84 | 74.44 | 91.04
FaMuS [60] | 79.40 | 92.80 | 77.00 | 92.76
RRL [31] | 76.30 | 91.50 | 73.30 | 91.20
Ours (Normal Model) | 80.24 | 90.84 | 76.44 | 90.00
\+ Test-Time Aug. | 81.52 | 92.52 | 78.36 | 91.80
Ours (Modified Model) | 80.88 | 92.76 | 75.96 | 92.20
\+ Test-Time Aug. | 83.16 | 94.28 | 79.64 | 94.20

Table 2: Test accuracy (%) for Webvision. Top methods within 0.5% in bold

In Tables 1 and 2, we show the accuracy of our model on the Animal10N and
Webvision benchmarks, respectively. In both cases, it can be seen that the
modified model improves results, demonstrating that on these instance-
dependant noise datasets, learning the relationship between images, noisy
labels and ‘true’ labels has allowed more accurate relabelling, and an
improvement in final model accuracy. Animal10N, which consists of five pairs
of commonly confused image classes, sees a significant improvement of $2.64\%$
from using our modified training approach, due to the relationship between
commonly confused classes being easy to learn. Webvision sees a more modest
but still meaningful improvement of $0.64\%$ accuracy when using our modified
model. It can be seen that on both benchmarks, we report state-of-the-art
results, and that using dropout-based test-time augmentation further improves
our accuracy.

We next turn our attention to the synthetic ‘Polynomial Margin Diminishing
(PMD)’ [64] and ‘RoG’ [28] instance-dependent noisy label benchmarks based on
CIFAR10 and CIFAR100 in Tables 3 and 4. In all cases considered in these two
tables, our accuracy results are substantially higher than by other
approaches, even without our modified model. When we do use a modified model
for these synthetic instance-dependent noisy-label benchmarks, we find mixed
results, with performance often decreasing, potentially due to learned noise
transitions not generalizing as well as they do in real-world instance-
dependent noise datasets.

Dataset | CIFAR-10 | CIFAR-100
---|---|---
Noise Type | Type-I 35% | Type-II 35% | Type-III 35% | Type-I 35% | Type-II - 35% | Type-III - 35%
Cross-Entropy | 78.11 | 76.65 | 76.89 | 57.68 | 57.83 | 56.07
PLC [65] | 82.80 | 81.54 | 81.50 | 60.01 | 63.68 | 63.68
Ours (Normal Model) | 94.06 | 93.25 | 93.35 | 65.87 | 65.80 | 66.36
\+ Test-Time Aug. | 94.72 | 93.79 | 93.97 | 66.83 | 66.48 | 67.42
Ours (Modified Model) | 94.00 | 93.76 | 94.23 | 68.25 | 68.14 | 68.22
\+ Test-Time Aug. | 94.39 | 94.19 | 94.23 | 70.13 | 69.35 | 70.13

Table 3: Test accuracy (%) for Polynomial Margin Diminishing Noise [64]. Top
methods are in bold.

Data set | CIFAR-10 | CIFAR-100
---|---|---
Method/ Noise Ratio | DenseNet (32%) | ResNet (38%) | VGG (34%) | DenseNet (34%) | ResNet (37%) | VGG (37%)
D2L + RoG [28] | 68.57 | 60.25 | 59.94 | 31.67 | 39.92 | 45.42
CE + RoG [28] | 68.33 | 64.15 | 70.04 | 61.14 | 53.09 | 53.64
PropMix [11] | 84.25 | 82.51 | 85.74 | 60.98 | 58.44 | 60.01
Ours (Normal Model) | 93.26 | 92.05 | 93.29 | 62.47 | 64.91 | 64.98
\+ Test-Time Aug. | 93.87 | 92.66 | 93.86 | 63.40 | 65.74 | 66.10
Ours (Modified Model) | 89.46 | 90.97 | 89.77 | 63.68 | 63.09 | 63.89
\+ Test-Time Aug. | 90.25 | 91.85 | 90.42 | 65.15 | 64.70 | 65.30

Table 4: Test accuracy (%) for the RoG label noise benchmark [28], where
baseline results are from [28]. Top methods are in bold.

Finally, in Table 5 we show the results of our method on the synthetically
constructed symmetric and asymmetric noise for CIFAR10 and CIFAR100. These
noise types are rare in practice, but they are common noisy-label benchmarks
so we include them here for completeness. We see that our method is
competitive with the state-of-the-art on CIFAR10 symmetric and asymmetric
noise, despite featuring fewer mechanisms designed to address these types of
noise. We particularly note 40% asymmetric noise, which benefits from the
modified model due to noisy labels greatly limiting the set of feasible
samples for each image, allowing us to exceed the state-of-the-art. In
contrast to this, we report our results on symmetric label noise in CIFAR100,
where existing methods perform better than ours. In all cases, our modified
model is able to take advantage of the noise to provide more accurate
relabelling, but the regularisation strategies that other methods use work
well under the assumption of symmetric noise and provide stronger results.
Perfectly symmetric noise over 100 classes is rare in practice though, and our
results show universally strong performance on real-world instance-dependent
datasets.

Dataset | CIFAR-10 | CIFAR-100
---|---|---
Noise type | Sym. | Asym. | Sym.
Method / Noise Ratio |  20% |  50% |  80% |  90% |  40% |  20% |  50% |  80% |  90%
Cross-Entropy [29] | 82.7 | 57.9 | 26.1 | 16.8 | 72.3 | 61.8 | 37.3 | 8.8 | 3.5
ELR [33] | 95.8 | 94.8 | 93.3 | 78.7 | 93.0 | 77.6 | 73.6 | 60.8 | 33.4
DivideMix [29] | 95.7 | 94.4 | 92.9 | 75.4 | 92.1 | 76.9 | 74.2 | 59.6 | 31.0
AugDesc [35] | 96.3 | 95.4 | 93.8 | 91.9 | 94.6 | 79.5 | 77.2 | 66.4 | 41.2
ContrastToDivide [68] | 96.4 | 95.3 | 94.4 | 93.6 | 93.5 | 78.7 | 76.4 | 67.8 | 58.7
PropMix [11] | 96.09 | 95.53 | 93.77 | 93.20 | 94.64 | 76.99 | 73.71 | 66.75 | 58.32
Ours (Normal Model) | 95.04 | 95.13 | 94.51 | 91.72 | 94.91 | 69.02 | 68.87 | 64.09 | 55.91
\+ Test-Time Aug. | 95.47 | 95.39 | 94.90 | 92.32 | 95.14 | 70.17 | 69.57 | 65.10 | 56.81
Ours (Modified Model) | 95.99 | 95.59 | 94.48 | 93.52 | 95.85 | 75.09 | 70.86 | 57.03 | 39.95
\+ Test-Time Aug. | 96.75 | 96.16 | 94.98 | 93.93 | 96.42 | 76.65 | 72.95 | 57.83 | 40.31

Table 5: Test accuracy (%) for all competing methods on CIFAR-10 and CIFAR-100
under symmetric and asymmetric noises. Results from related approaches are as
presented in [29] and [55]. Top methods within $1\%$ are in bold.

###  4.4 Predictions with Noisy Labels

A unique feature of our method is that our final model can be used to predict
the labels of samples with and without noisy labels. In some applications,
e.g., tagged image classification, images at test-time may also have noisy
labels associated with them, which our model can use to improve classification
performance. To show this, we generate artificial noisy labels for all the
samples in the CIFAR10 test set using the same procedure as we used for 40%
Asymmetric noise, and in Table 6 we show the accuracy of our model on these
samples when these noisy labels are and are not used. We see that our model
performance increases when using the noisy labels, because our model has
learned to use noisy labels (when they are available) to improve prediction
accuracy.

Test Set |  | Accuracy
---|---|---
Without Noisy Labels |  | 95.85
With Noisy Labels |  | 97.59

Table 6: Accuracy of our model tested with and without noisy labels on CIFAR10
Asym. 40% noise. Noisy labels are generated for training and testing samples
using the same procedure.

We further demonstrate this learned relationship in Table 7, where we show how
the prediction of our model changes depending on what noisy label is provided
to the model. In this 40% Asymmetric noise dataset, the image of the dog shown
would only ever be labelled as a dog or a cat, and in both cases it can be
seen that our model makes the correct prediction. Our model also makes the
correct prediction when provided with no noisy label, although with lower
confidence because it does not have access to the noisy label. Because our
model has learned that none of the other classes are ever confused with dogs,
it makes other predictions when provided with these labels. These results show
that our model has learned the noise relationship, and that it can use both
the image features and the noisy label (when it is available) to generate
higher confidence predictions.

Noisy Label | Prediction (Confidence)
---|---
- | Dog (90.27%)
Airplane | Bird (65.39%)
Automobile | Automobile (62.75%)
Bird | Bird (98.30%)
Cat | Dog (94.51%)
Deer | Deer (96.06%)
Dog | Dog (96.29%)
Frog | Frog (96.49%)
Horse | Horse (75.84%)
Ship | Ship (95.46%)
Truck | Truck (96.88%)

Table 7: Predictions made by our model with different noisy labels for a
testing sample (showing a dog) in Asym 0.4 noise for CIFAR10. ‘-’ represents
using a null label in place of a noisy label.

###  4.5 Clean Set Selection

On the left of Figure 4, we show the distribution of confidences of our model
after bootstrapping, and see that the highest confidence predictions are
almost entirely for samples whose predicted ‘true’ label ($\hat{\mathbf{y}}$)
is correct, which allows us to select highly accurate clean sets for SSL. On
the right, we show the percentage of the selected samples for the clean set
that were originally clean (i.e. samples for which $\tilde{\mathbf{y}}$
matches the true label) if no form of noise balancing is performed. We see
that if we did not perform noise balancing, the selected clean set would
disproportionally consist of clean samples, which would cause a degenerate
relationship between noisy labels and clean labels to be learned during the
SSL stage of training, preventing accurate relabeling of samples from other
noise transitions.

Figure 4: Histograms showing the distribution of confidences after
bootstrapping for correct/incorrect classifications (left), and how the
highest confidence samples are disproportionally clean (right) for 50%
Symmetric Noise on CIFAR10.

###  4.6 Ablations and Training Time

In Tables 8, 9 and 10, we perform a number of ablation studies on the CIFAR10
40% Asymmetric noise. In Table 8, we show the accuracy of our trained model
after each stage of training. We see that the model accuracy improves after
each stage of training, with the final training’s use of MixUp and strong
augmentations providing an additional $0.87\%$ accuracy over the semi-
supervised learning stage.

In Table 9, we see the large impact that the choice of augmentations has on
the number of errors in the clean set after the bootstrapping phase. We see
that using strong augmentations for training greatly reduces the number of
errors, likely due to their regularising effect and its ability to prevent
overfitting to the noisy labels. During the evaluation stage however,
averaging the prediction of the model over multiple weak augmentations
performs best. We see that this matches the findings by Nishi et al. [35], who
find that using strong augmentations for training and weaker augmentations for
loss modelling works best.

In Table 10, we see the similarly large impact that using self-supervised
pretraining has on the number of errors in the clean set after bootstrapping.
In the supplementary material, we show additional experiments with ‘null
labels’ and different model architectures.

As for training time on CIFAR10 problems, our method takes on average 13.8h
for SimCLR pretraining, 0.5h for bootstrapping, 7.5h for SSL, and 2.5h for
final training (total of 24.3h) on an Nvidia RTX 2080. In comparison,
DivideMix [29] takes on average 5h, and the more recent method of PropMix [11]
can take up to 10h.

Training Stage |  | Accuracy
---|---|---
After Bootstrapping |  | 91.41
After Semi-Supervised Learning |  | 94.98
After Final Training |  | 95.85

Table 8: Model accuracy after each stage of training on CIFAR10 Asym. 40%
noise.

|  |  | Evaluation Aug.
---|---|---|---
|  |  |  None |  Weak |  Strong
Train | None |  | 579 | 361 | 456
Weak |  | 265 | 56 | 300
Strong |  | 28 | 21 | 31

Table 9: Effect of different training/testing augmentations on the number of
errors in a clean set of 10,000 samples selected after bootstrapping. Test
performed on CIFAR10 Asym. 40% noise.

Training Strategy |  |  No. of Errors
---|---|---
No Self-Supervision |  | 369
With Self-Supervision |  | 21

Table 10: Effect of self-supervision on the number of errors in a clean set of
10,000 samples selected after bootstrapping. Test performed on CIFAR10 Asym.
40% noise

##  5 Conclusions

In this paper, we proposed a new method that predicts labels from images and
their noisy labels. Unlike other methods, our training procedure does not
require access to a clean set of data, which we achieve by introducing
bootstrapping and a careful noise-based balancing procedure. By utilising the
relationship between images, noisy labels and ‘clean’ labels to accurately
relabel samples, we find that we can achieve SOTA results. By simply changing
the model used, we further unify the noisy label learning and semi-supervised
learning domains, resulting in a simplified architecture that can improve
performance for challenging instance-dependent noisy-label tasks.
Additionally, we find that by randomly replacing noisy labels with ‘null’
labels during training, we can remove the need for model distillation,
allowing practitioners of our method to perform predictions with and without
noisy labels.

## References

  * [1] Eric Arazo, Diego Ortego, Paul Albert, Noel O’Connor, and Kevin Mcguinness.  Unsupervised label noise modeling and loss correction.  In International Conference on Machine Learning, pages 312–321, 2019.
  * [2] Devansh Arpit, Stanisław Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al.  A closer look at memorization in deep networks.  In International conference on machine learning, pages 233–242. PMLR, 2017.
  * [3] Philip Bachman, Ouais Alsharif, and Doina Precup.  Learning with pseudo-ensembles.  Advances in neural information processing systems, 27, 2014.
  * [4] Dara Bahri, Heinrich Jiang, and Maya Gupta.  Deep k-nn for noisy labels.  In International Conference on Machine Learning, pages 540–550. PMLR, 2020.
  * [5] Yingbin Bai, Erkun Yang, Bo Han, Yanhua Yang, Jiatong Li, Yinian Mao, Gang Niu, and Tongliang Liu.  Understanding and improving early stopping for learning with noisy labels.  Advances in Neural Information Processing Systems, 34:24392–24403, 2021.
  * [6] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel.  Mixmatch: A holistic approach to semi-supervised learning.  Advances in Neural Information Processing Systems, 32, 2019.
  * [7] Pengfei Chen, Ben Ben Liao, Guangyong Chen, and Shengyu Zhang.  Understanding and utilizing deep neural networks trained with noisy labels.  In International Conference on Machine Learning, pages 1062–1070. PMLR, 2019.
  * [8] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [9] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton.  Big self-supervised models are strong semi-supervised learners.  Advances in neural information processing systems, 33:22243–22255, 2020.
  * [10] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  arXiv preprint arXiv:2003.04297, 2020.
  * [11] F. R. Cordeiro, Vasileios Belagiannis, Ian Reid, and Gustavo Carneiro.  Propmix: Hard sample filtering and proportional mixup for learning with noisy labels.  The 32nd British Machine Vision Conference, 2021.
  * [12] Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le.  Autoaugment: Learning augmentation strategies from data.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 113–123, 2019.
  * [13] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le.  Randaugment: Practical automated data augmentation with a reduced search space.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 702–703, 2020.
  * [14] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [15] Jacob Goldberger and Ehud Ben-Reuven.  Training deep neural-networks using a noise adaptation layer.  In ICLR, 2017.
  * [16] Yves Grandvalet and Yoshua Bengio.  Semi-supervised learning by entropy minimization.  Advances in neural information processing systems, 17, 2004.
  * [17] Keren Gu, Xander Masotto, Vandana Bachani, Balaji Lakshminarayanan, Jack Nikodem, and Dong Yin.  An instance-dependent simulation framework for learning with label noise, 2021.
  * [18] 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.  Advances in neural information processing systems, 31, 2018.
  * [19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In European conference on computer vision, pages 630–645. Springer, 2016.
  * [20] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017.
  * [21] Naoto Inoue, Edgar Simo-Serra, Toshihiko Yamasaki, and Hiroshi Ishikawa.  Multi-label fashion image classification with minimal human supervision.  In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 2261–2267, 2017.
  * [22] Taehyeon Kim, Jongwoo Ko, JinHwan Choi, Se-Young Yun, et al.  Fine samples for learning with noisy labels.  Advances in Neural Information Processing Systems, 34:24137–24149, 2021.
  * [23] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, Canadian Institute for Advanced Research, 2009.
  * [24] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [25] Samuli Laine and Timo Aila.  Temporal ensembling for semi-supervised learning.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
  * [26] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436–444, 2015.
  * [27] Dong-Hyun Lee.  Pseudo-label : The simple and efficient semi-supervised learning method for deep neural networks.  ICML 2013 Workshop : Challenges in Representation Learning (WREPL), 07 2013.
  * [28] Kimin Lee, Sukmin Yun, Kibok Lee, Honglak Lee, Bo Li, and Jinwoo Shin.  Robust inference via generative classifiers for handling noisy labels.  In International Conference on Machine Learning, pages 3763–3772. PMLR, 2019.
  * [29] Junnan Li, Richard Socher, and Steven CH Hoi.  Dividemix: Learning with noisy labels as semi-supervised learning.  arXiv preprint arXiv:2002.07394, 2020.
  * [30] Junnan Li, Yongkang Wong, Qi Zhao, and Mohan S Kankanhalli.  Learning to learn from noisy labeled data.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5051–5059, 2019.
  * [31] Junnan Li, Caiming Xiong, and Steven CH Hoi.  Learning from noisy data with robust representation learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9485–9494, 2021.
  * [32] Wen Li, Limin Wang, Wei Li, Eirikur Agustsson, and Luc Van Gool.  Webvision database: Visual learning and understanding from web data.  arXiv preprint arXiv:1708.02862, 2017.
  * [33] Sheng Liu, Jonathan Niles-Weed, Narges Razavian, and Carlos Fernandez-Granda.  Early-learning regularization prevents memorization of noisy labels.  Advances in neural information processing systems, 33:20331–20342, 2020.
  * [34] Ricardo V Lloyd, Lori A Erickson, Mary B Casey, King Y Lam, Christine M Lohse, Sylvia L Asa, John KC Chan, Ronald A DeLellis, H Ruben Harach, Kennichi Kakudo, et al.  Observer variation in the diagnosis of follicular variant of papillary thyroid carcinoma.  The American journal of surgical pathology, 28(10):1336–1340, 2004\.
  * [35] Kento Nishi, Yi Ding, Alex Rich, and Tobias Hollerer.  Augmentation strategies for learning with noisy labels.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8022–8031, June 2021.
  * [36] Diego Ortego, Eric Arazo, Paul Albert, Noel E O’Connor, and Kevin McGuinness.  Multi-objective interpolation training for robustness to label noise.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6606–6615, 2021.
  * [37] 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 Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1944–1952, 2017.
  * [38] Hieu Pham, Zihang Dai, Qizhe Xie, and Quoc V Le.  Meta pseudo labels.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11557–11568, 2021.
  * [39] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In International Conference on Machine Learning, pages 8748–8763. PMLR, 2021.
  * [40] Scott E. Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich.  Training deep neural networks on noisy labels with bootstrapping.  In ICLR 2015, 2015.
  * [41] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun.  Learning to reweight examples for robust deep learning.  In International Conference on Machine Learning, pages 4334–4343. PMLR, 2018.
  * [42] Ragav Sachdeva, Filipe R Cordeiro, Vasileios Belagiannis, Ian Reid, and Gustavo Carneiro.  Scanmix: Learning from severe label noise via semantic clustering and semi-supervised learning.  arXiv preprint arXiv:2103.11395, 2021.
  * [43] Fahad Sarfraz, Elahe Arani, and Bahram Zonooz.  Noisy concurrent training for efficient learning under label noise.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 3159–3168, 2021.
  * [44] Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng.  Meta-weight-net: Learning an explicit mapping for sample weighting.  Advances in neural information processing systems, 32, 2019.
  * [45] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [46] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li.  Fixmatch: Simplifying semi-supervised learning with consistency and confidence.  Advances in Neural Information Processing Systems, 33:596–608, 2020\.
  * [47] Hwanjun Song, Minseok Kim, and Jae-Gil Lee.  SELFIE: Refurbishing unclean samples for robust deep learning.  In ICML, 2019.
  * [48] Christian Szegedy, Sergey Ioffe, Vincent Vanhoucke, and Alexander A Alemi.  Inception-v4, inception-resnet and the impact of residual connections on learning.  In Thirty-first AAAI conference on artificial intelligence, 2017\.
  * [49] Antti Tarvainen and Harri Valpola.  Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results.  Advances in neural information processing systems, 30, 2017.
  * [50] Wouter Van Gansbeke, Simon Vandenhende, Stamatios Georgoulis, Marc Proesmans, and Luc Van Gool.  Scan: Learning to classify images without labels.  In European Conference on Computer Vision, pages 268–285. Springer, 2020.
  * [51] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [52] Andreas Veit, Neil Alldrin, Gal Chechik, Ivan Krasin, Abhinav Gupta, and Serge Belongie.  Learning from noisy large-scale datasets with minimal supervision.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 839–847, 2017.
  * [53] Xiaosong Wang, Yifan Peng, Le Lu, Zhiyong Lu, Mohammadhadi Bagheri, and Ronald M Summers.  Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2097–2106, 2017.
  * [54] Zhen Wang, Guosheng Hu, and Qinghua Hu.  Training noise-robust deep neural networks via meta-learning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4524–4533, 2020.
  * [55] Zhi-Fan Wu, Tong Wei, Jianwen Jiang, Chaojie Mao, Mingqian Tang, and Yu-Feng Li.  Ngc: A unified framework for learning with open-world noisy data.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 62–71, 2021.
  * [56] 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.  Advances in Neural Information Processing Systems, 33, 2020.
  * [57] Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama.  Are anchor points really indispensable in label-noise learning?  Advances in Neural Information Processing Systems, 32, 2019.
  * [58] Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang.  Learning from massive noisy labeled data for image classification.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2691–2699, 2015.
  * [59] Youjiang Xu, Linchao Zhu, Lu Jiang, and Yi Yang.  Faster meta update strategy for noise-robust deep learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 144–153, 2021.
  * [60] Youjiang Xu, Linchao Zhu, Lu Jiang, and Yi Yang.  Faster meta update strategy for noise-robust deep learning.  In CVPR, 2021.
  * [61] Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki.  Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling.  Advances in Neural Information Processing Systems, 34, 2021.
  * [62] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  arXiv preprint arXiv:1611.03530, 2016.
  * [63] Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In International Conference on Learning Representations, 2018.
  * [64] Le Zhang, Ryutaro Tanno, Kevin Bronik, Chen Jin, Parashkev Nachev, Frederik Barkhof, Olga Ciccarelli, and Daniel C Alexander.  Learning to segment when experts disagree.  In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 179–190. Springer, 2020.
  * [65] 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.
  * [66] Zizhao Zhang and Tomas Pfister.  Learning fast sample re-weighting without reward data.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 725–734, 2021.
  * [67] Zizhao Zhang, Han Zhang, Sercan O Arik, Honglak Lee, and Tomas Pfister.  Distilling effective supervision from severe label noise.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9294–9303, 2020.
  * [68] Evgenii Zheltonozhskii, Chaim Baskin, Avi Mendelson, Alex M Bronstein, and Or Litany.  Contrast to divide: Self-supervised pre-training for learning with noisy labels.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 1657–1667, 2022.

##  Appendix A Additional Training Information

###  A.1 Self-Supervised Pretraining

For CIFAR-10, CIFAR100 and Animal10N we use SimCLR [8] for self-supervised
pre-training. Pretraining is done for 1000 epochs, with the learning rate
starting at 0.5, and decaying by a factor of 0.1 after 700, 800 and 900
epochs. We use stochastic gradient descent as our optimizer, with Nesterov
momentum of 0.9 and weight decay of $1\times 10^{-4}$. We use a temperature of
0.5 for SimCLR and a batch size of 512.

For Webvision, we adopt MoCo-v2 [10], trained for 100 epochs (with 1 epoch of
warmup) and with a batch size of 128. We use stochastic gradient descent as
our optimizer, with momentum of 0.9 and weight decay of $1\times 10^{-4}$. The
learning rate starts at 0.015, decaying by a factor of 0.1 at epoch 50.

The feature embeddings generated by our models have 512 dimensions.

###  A.2 Bootstrapping Training

For CIFAR10, CIFAR100 and Animal10N, we do 60 epochs of bootstrapping training
with MixUp. We use a learning rate of 0.02, which decays to 0.002 after 5
epochs and to 0.0002 after 50 epochs. Stochastic gradient descent is used as
the optimizer, with Nesterov momentum of 0.9 and weight decay of $5\times
10^{-4}$.

For Webvision, we do 300 epochs of bootstrapping training with MixUp. We use a
starting learning rate of 0.005, which increases linearly for the first 30
epochs until it reaches 0.1, and then follows a cosine learning rate decay
(capped at a minimum of $1\times 10^{-5}$). Stochastic gradient descent is
used as the optimizer, with Nesterov momentum of 0.9 and weight decay of
$1\times 10^{-5}$.

In all cases, we use a batch size of 64 and a MixUp alpha of 0.2.

###  A.3 Semi-Supervised Learning

For semi-supervised learning, we use FixMatch for all our experiments, with
the temperature set at 0.5, the confidence threshold for pseudo-label
generation set at 0.95, and the unlabelled loss ratio set at 1.0. We train for
100,000 iterations in all cases, and use an exponential moving average
momentum of 0.999.

We use a cosine learning rate, starting at 0.02 (capped at a minimum of
$1\times 10^{-5}$ for Webvision, and at $1\times 10^{-4}$ for all other
experiments). We use stochastic gradient descent with nesterov momentum of
0.9, and weight decay of $1\times 10^{-5}$ for Webvision and $5\times 10^{-4}$
for all other experiments.

For CIFAR10, CIFAR100 and Animal10N, we use a batch size of $64$ clean
samples, and $3\times 64$ noisy samples per batch. For Webvision, we use a
batch size of $32$ clean samples, and $3\times 32$ noisy samples per batch.

###  A.4 Final Model Training

For final model training, we do 300 epochs of training for all experiments.

We use a cosine learning rate, starting at 0.02 (capped at a minimum of
$1\times 10^{-5}$ for Webvision, and at $1\times 10^{-4}$ for all other
experiments). We use stochastic gradient descent with nesterov momentum of
0.9, and weight decay of $1\times 10^{-5}$ for Webvision and $5\times 10^{-4}$
for all other experiments.

We use a batch size of 64 for Webvision and 128 for all other experiments,

###  A.5 Creating the Clean, Noisy and Final Datasets

For all of our experiments, we generate predictions for samples by averaging
over 25 weak augmentations of each sample, and use the 90% most confident
predictions to estimate the noise transition matrix for the dataset.

For CIFAR10 and Animal10N, we set $K=0.1$ and $\tau=0.99$. For CIFAR100 and
Webvision, we set $K=0.25$ and $\tau=0.99$.

###  A.6 Model Architecture

In the modified networks that we used to learn the relationship between
images, noisy labels and true labels, we project both the images and noisy
labels to have an encoding size of 128 before concatenating them together,
with our hidden layer also having a size of 128. We use a dropout layer with
$p=0.2$ after each of these linear projections (except the final classifier
head), and we use batch normalization before the final classifier head.

##  Appendix B Effect of Null Label Type

In our method, we describe the use of a ‘null’ label to represent the case
where no noisy label is present. For all of our experiments, if there are $k$
classes in the training set, we use a $k$-wide zero vector as our ‘null’
label. Here, we experiment with two alternative choices:

  * •

One Vectors: Using a $k$-wide vector filled with ones;

  * •

$\frac{1}{k}$ Vectors: Using a $k$-wide vector where every value equals
$\frac{1}{k}$ (so that the sum of all values is 1).

We show the results of using these alternative ‘null’ label representations in
Table 11.

Null Label Type | Accuracy
---|---
Zero Vectors | 95.70
One Vectors | 95.82
$\frac{1}{k}$ Vectors | 95.50

Table 11: Accuracy using different null label methods for Asym. 40% noise on
CIFAR10

In our experiments, we find that the choice of null label representation has
little impact on the final performance of the model. In all cases, the model
is able to learn to make predictions when a noisy label is and is not present.

##  Appendix C Ablation of Model Construction

For all of our results, we use a ‘concatenation’ based model architecture,
where image features and noisy labels are combined by projecting them to the
same dimensionality, and then concatenating them together before passing them
through the remaining linear, ReLU and batch normalisation layers of the
network. This form of combining noisy labels and image features together with
concatenation is the standard method used by contemporary works [17, 21, 52].

Here, we briefly explore two other potential architectures for combining image
features and noisy label information together.

  * •

Mixture of Experts: A separate classification head is created for every noisy
label class, with the noisy label controlling which noisy label head is used
for the prediction. In the case of mixed noisy labels (such as when performing
MixUp between two noisy labels of different classes), the model output is the
linear combination of each of the classification heads, weighted by their
corresponding value in the noisy label;

  * •

Attention: Scaled dot-product attention, as described by Vaswani et al. [51],
is used to allow different noisy labels to attend to different image features.
For our experiments on CIFAR10, we generate a query by projecting the noisy
label to a $1\times 16$ tensor, generate keys by projecting image features to
a $128\times 16$ tensor (representing a set of 128 keys), and generate values
by projecting image features to a $128\times 16$ tensor (representing a set of
128 values). Scaled dot-product attention is then used to compute a $1\times
16$ feature tensor, with a final linear layer acting as a classification head.

In Table 12, we show the results obtained by our training method using all
three of these model architectures on 40% Asymmetric noise on CIFAR10. We see
that the concatenation and mixture of experts models perform similarly well,
with the attention based model performing $\sim 1.5\%$ worse.

Model Type | Accuracy
---|---
Concatenation | 95.65
Mixture of Experts | 95.53
Attention | 94.02

Table 12: Accuracy using different model constructions for Asym. 40% noise on
CIFAR10

We note however that our exploration into using these model types is limited,
and there may be opportunities to further optimise for these architectures.

##  Appendix D Effect of Dropping Labels for Pseudo-Label Generation

In Section 3.2, we discuss how label-dropping is used during semi-supervised
learning to allow our model to make predictions with and without noisy labels
present. However, we do not use label dropping for the weakly augmented
samples used for pseudo-label generation, with the justification that the
model loss is not backpropagated through the weakly augmented samples in the
FixMatch algorithm, and that always using noisy labels improves pseudo-label
accuracy. Here, we experimentally justify this decision by comparing the final
model accuracy when label dropping is and is not used for weakly augmented
samples during semi-supervised learning.

- | Accuracy
---|---
With Label Dropping | 95.33
Without Label Dropping | 95.74

Table 13: Effect of Label Dropping on Final Accuracy for Asym. 40% noise on
CIFAR10

Here, we see that using label dropping for weakly augmented samples decreases
the accuracy of the model. Thus, we always use noisy labels for pseudo-label
generation.

##  Appendix E Generating Plausible Noisy Labels for Testing Samples

In our experiments, we explore using ‘null’ labels in place of a noisy label
for samples at testing time. However, rather than passing a null label into
the model alongside the testing sample, we could attempt to generate plausible
‘noisy’ labels from testing samples.

In this experiment, we attempt to generate plausible noisy labels from samples
using the model as it was at the end of the bootstrapping phase. For a given
testing sample, we use the bootstrapping model to generate the ‘noisy’ label,
then we pass the testing sample and the ‘noisy’ label into the final trained
model to generate the final prediction.

- | Accuracy
---|---
With Null Labels | 95.74
With Label Generation | 95.09

Table 14: Comparison of Null Labels and Label Generation on Final Accuracy for
Asym. 40% noise on CIFAR10

Here, we see that attempting to generate plausible noisy labels is a less
effective strategy that using null labels to represent samples without
associated noisy labels.

##  Appendix F 70% PMD Noise on CIFAR10 and CIFAR100

In this section, we investigate the results of our method on 70% PMD noise for
CIFAR10 and CIFAR100. In Table 15, we show the accuracy of our method on these
datasets. We see that on CIFAR100 we get SOTA results, greatly surpassing the
existing PLC method. However, on CIFAR10, we perform poorly.

To understand this, in Figures 5 and 6 we show the noise transition matrix and
the final confusion matrix of our model for 35% and 70% PMD-1 noise for
CIFAR10 and CIFAR100.

(a) PMD-1-0.35
Noise Transition Matrix

(b) PMD-1-0.35
Final Confusion Matrix

(c) PMD-1-0.70
Noise Transition Matrix

(d) PMD-1-0.70
Final Confusion Matrix

Figure 5: Noise Transition and Confusion Matrices for PMD-1 Noise on CIFAR10

(a) PMD-1-0.35
Noise Transition Matrix

(b) PMD-1-0.35
Final Confusion Matrix

(c) PMD-1-0.70
Noise Transition Matrix

(d) PMD-1-0.70
Final Confusion Matrix

Figure 6: Noise Transition and Confusion Matrices for PMD-1 Noise on CIFAR100

In Figure 5(c), we see the noise transition matrix for PMD-1-0.70 Noise on
CIFAR10, and we note that by introducing 70% noise in a non-symmetric way,
several of the classes have ‘flipped’. For example, more cats have become
labelled as dogs than are labelled as cats, and vice versa (classes 3 and 5).
Trucks and airplanes have similarly become flipped. Because of this, our
method attempts to ‘correct’ samples to the wrong class, which we show in
Figure 5(d).

If we measure the performance of our model with respect to the flipped classes
(by associating each label with the modal class it represents in the noise
transition matrix), we find that our model has an accuracy of 45.7%, slightly
surpassing the accuracy of PLC.

On CIFAR100, this form of class flipping happens much more rarely due to the
70% of mislabelled samples being ‘spread out’ among over more classes. Because
of this, our method is able to achieve much higher accuracy on CIFAR100 than
it does in CIFAR10. In Figure 6(d), we show that the final confusion matrix
for our trained model on CIFAR100 PMD-1-0.70 noise is much cleaner than it is
for CIFAR10 PMD-1-0.70 noise (shown in Figure 5(d)).

Dataset | CIFAR-10 | CIFAR-100
---|---|---
Noise Type | Type-I 70% | Type-II 70% | Type-III 70% | Type-I 70% | Type-II - 70% | Type-III - 70%
Cross-Entropy | 41.98 | 45.57 | 43.42 | 39.32 | 39.30 | 40.01
PLC [65] | 42.74 | 46.04 | 45.05 | 45.92 | 45.03 | 44.52
Ours (Regular Model) | 21.02 | 27.55 | 21.27 | 58.15 | 53.77 | 57.81
\+ Test-Time Aug. | 21.17 | 27.38 | 20.99 | 59.27 | 54.44 | 58.77
Ours (Modified Model) | 19.18 | 27.28 | 19.94 | 58.69 | 58.03 | 57.90
\+ Test-Time Aug. | 19.71 | 27.17 | 20.21 | 59.39 | 58.95 | 58.95

Table 15: Test accuracy (%) for Polynomial Margin Diminishing Noise [64]. Top
methods are in bold.


#  A product integration rule on equispaced nodes for highly oscillating
integrals ††thanks: The authors are member of the INdAM Research group GNCS
and the TAA-UMI Research Group. This research has been accomplished within
“Research ITalian network on Approximation” (RITA).

Luisa Fermo Department of Mathematics and Computer Science, University of
Cagliari, Via Ospedale 72, 09124, Italy<EMAIL_ADDRESS>Domenico Mezzanotte
Department of Mathematics and Computer Science, University of Basilicata,
Viale dell’Ateneo Lucano 10, 85100 Potenza, Italy
<EMAIL_ADDRESS> Donatella Occorsio Department of Mathematics
and Computer Science, University of Basilicata, Viale dell’Ateneo Lucano 10,
85100 Potenza, Italy and Istituto per le Applicazioni del Calcolo “Mauro
Picone”, Naples branch, C.N.R. National Research Council of Italy, Via P.
Castellino, 111, 80131 Napoli, Italy<EMAIL_ADDRESS>
###### Abstract

This paper provides a product integration rule for highly oscillating
integrands, based on equally spaced nodes. The stability and the error
estimate are proven in the space of continuous functions, and some numerical
tests which confirm such estimates are provided.

Keywords: Approximation by polynomials, Boolean iterated sums of Bernstein
operators, quadrature rules

Mathematics Subject Classification: 41A10, 65D32

##  1 Introduction

From a numerical point of view, the main difficulty to treat integrals of the
type

$\int_{-a}^{a}e^{-{\mathrm{i}}\omega(x-y)}f(x)dx,\quad
a>0,\quad{\mathrm{i}}=\sqrt{-1},\quad y\in[-a,a]$ (1.1)

depends on the presence of the kernel $e^{-{\mathrm{i}}\omega(x-y)}$, which
highly oscillates for frequencies $|\omega|>>1$. For the evaluation of such
integrals, many accurate formulas exist in the literature, mainly based on the
zeros of orthogonal polynomials; see e.g. [1, 2, 6, 7, 9, 15]. On the other
hand, in many practical applications, the function $f$ is known only at
equispaced nodes.

In order to adopt the values of $f$ at equidistant nodes, a widely used
technique is based on composite quadrature rules of “lower" degree, such as
Filón type rules, whose degree of approximation cannot be improved over the
saturation class of the approximation process. Recently, in [3] starting from
the knowledge of $f$ at a finite set of equally spaced nodes, an approach has
been introduced to efficiently compute weighted integrals, but not advisable
in the case of oscillating integrands. For a short review on the main
techniques the interested reader can consult [1].

Finding accurate quadrature rules based on equidistant points is still an open
problems. Here, we introduce a product integration rule based on the
approximation of the function $f$ through the generalized Bernstein (shortly
GB) polynomials $\bar{B}_{m,\ell}(f)$ of degree $m$ and parameter $\ell$
defined in the interval $[-a,a]$. Such polynomials represent an adequate tool
for our aims, since they make use of the samples of $f$ at $m+1$ equally
spaced nodes; see e.g. [4, 11, 12]. Moreover, unlike the classical Bernstein
polynomials $\bar{B}_{m}(f)$, the speed of the uniform convergence to $f$
accelerates as the smoothness of $f$ increases [8].

The outline of the paper is as follows. In Section 2 we provide definition and
main properties of GB polynomials. Section 3 contains the main results
regarding the product integration rules and its error estimates. In Section 4
two numerical examples are given to corroborate the theoretical estimate. The
proofs are given in the last Section 5.

##  2 Notation and Preliminary Results

In the sequel $\mathcal{C}$ denotes any positive constant having different
meanings at different occurrences and the writing
$\mathcal{C}\neq\mathcal{C}(a,b,..)$ has to be understood as $\mathcal{C}$ not
depending on $a,b,..$.

As usual, $\mathbb{P}_{m}$ denotes the space of the algebraic polynomials of
degree less than or equal to $m$, and $C^{0}:=C^{0}([-a,a])$ is the space of
the continuous functions on $[-a,a]$ equipped with the uniform norm
$\displaystyle\|f\|:=\max_{x\in[-a,a]}|f(x)|$. Morerover, for any bivariate
function $g(x,y)$, by $g_{x}(y)$ we refer to $g$ as function of the only
variable $y$. Finally, for a given integer $m$, we set
$N_{0}^{m}:=\\{0,1,2,\dots,m\\}.$

###  2.1 Iterated Boolean sums of Bernstein Operators in $[-a,a]$

For a fixed positive $a\in\vbox{\hbox{I\hskip-2.1ptR\hfil}}$, consider the
$m$-th Bernstein polynomial $\bar{B}_{m}f$ of a given $f\in C^{0},$

$\bar{B}_{m}(f,x):=\sum_{k=0}^{m}f(t_{k})\bar{p}_{m,k}(x),\qquad
t_{k}:=-a+k\frac{2a}{m},\qquad x\in[-a,a]$ (2.1)

where

$\bar{p}_{m,k}(x):=\binom{m}{k}\left(\frac{a+x}{2a}\right)^{k}\left(\frac{a-x}{2a}\right)^{m-k}.$
(2.2)

Based on $\bar{B}_{m}(f)$, the $\ell$-iterated boolean sum
$\bar{B}_{m,\ell}(f)\in\vbox{\hbox{I\hskip-2.1ptP\hfil}}_{m}$,
$\ell\in\vbox{\hbox{I\hskip-2.1ptN\hfil}}$, is defined for any $f\in C^{0}$ as

$\bar{B}_{m,\ell}(f)=f-(f-\bar{B}_{m}(f))^{\ell},\quad\bar{B}_{m,1}f=\bar{B}_{m}f.$

The polynomial $\bar{B}_{m,\ell}(f)$ can be expressed $\forall x\in[-a,a]$, as

$\bar{B}_{m,\ell}(f,x)=\sum_{j=0}^{m}\bar{p}_{m,j}^{(\ell)}(x)f(t_{j}),\quad\textrm{with}\quad\bar{p}_{m,j}^{(\ell)}(x)=\sum_{i=0}^{m}\bar{p}_{m,i}(x)c_{i,j}^{(m,\ell)},$
(2.3)

where $c_{i,j}^{(m,\ell)}$ are the entries of the matrix
$C_{m,\ell}\in\vbox{\hbox{I\hskip-2.1ptR\hfil}}^{(m+1)\times(m+1)}$,

$\displaystyle
C_{m,\ell}=\mathbf{I}+(\mathbf{I}-\mathbf{A})+\ldots+(\mathbf{I}-\mathbf{A})^{\ell-1},\quad
C_{m,1}=\mathbf{I},$

being $\mathbf{I}$ the identity matrix of order $m+1$ and
$\mathbf{A}\in\mathbb{R}^{(m+1)\times(m+1)}$ the matrix

$(\mathbf{A})_{i,j}=p_{m,j}(t_{i}),\quad i,j\in N_{0}^{m}.$

By induction on $\ell=2^{p},\ p\in\vbox{\hbox{I\hskip-2.1ptN\hfil}}$, the
following recurrence relation holds

$C_{m,2^{p}}=C_{m,2^{p-1}}+(\mathbf{I}-\mathbf{A})^{2^{p-1}}C_{m,2^{p-1}},$
(2.4)

which allows to a fast construction of the subsequence
$\\{B_{m,2^{p}}\\}_{p=1,2,\ldots}$, since

$B_{m,2^{p}}(f,x)=2B_{m,2^{p-1}}(f,x)-B_{m,2^{p-1}}^{2}(f,x).$ (2.5)

A survey containing properties and applications of Generalized Bernstein
polynomials is given in [14]. Moreover, specific employments of such
polynomials to Fredholm and Volterra integral equations can be found in [5,
13].

As we can note by (2.1), the polynomials $\bar{B}_{m,\ell}f$ require the same
samples of $f$ at $m+1$ equally spaced points of $[-a,a]$. Moreover, they
detain the special property that the speed of convergence to $f$ accelerates
as the smoothness of $f$ increases, unlike the “originating” polynomial
$\bar{B}_{m}(f)$.

To be more precise, if we consider the $r$th Sobolev type space $1\leq
r\in\vbox{\hbox{I\hskip-2.1ptN\hfil}}$, defined as

$W_{r}=\left\\{f\in
C^{0}:f^{(r-1)}\in\mathcal{AC}:\|f^{(r)}\phi^{r}\|<\infty\right\\},\quad\
\|f\|_{W_{r}}=\|f\|+\|f^{(r)}\phi^{r}\|,$

where $\phi(x)=\sqrt{a^{2}-x^{2}},$ and $\mathcal{AC}$ denotes the space of
all locally absolutely continuous functions on $[-a,a]$, then for each $f\in
W_{r}$ with $0<r\leq 2\ell$, we have [8]

$\|f-\bar{B}_{m,\ell}(f)\|=\mathcal{O}(\sqrt{m^{-r}}).$

In other words, the rate of convergence behaves like the square root of the
best approximation error for this space of functions.

##  3 A product integration rule

By separating the kernel $e^{-{\mathrm{i}}\omega(x-y)}$ into the real and
imaginary parts, we are dealing with integrals of the type

$\mathcal{I}^{\omega}(f,y):=\int_{-a}^{a}\kappa(\omega(y-x))\
f(x)\,dx,\qquad\textrm{where}\qquad\kappa(\omega(y-x))=\begin{cases}\sin(\omega(y-x)),\\\
\cos(\omega(y-x)).\end{cases}$ (3.1)

In order to evaluate numerically the above integral, we propose to approximate
$f$ by $\bar{B}_{m,\ell}(f)$, getting

$\mathcal{I}^{\omega}(f,y)=\int_{-a}^{a}k(\omega(y-x))\,\bar{B}_{m,\ell}(f,x)\,dx+\mathcal{R}_{m,\ell}^{\omega}(f,y):=\mathcal{I}_{m,\ell}^{\omega}(f,y)+\mathcal{R}_{m,\ell}^{\omega}(f,y).$
(3.2)

Then, taking (2.3) into account, we get

$\mathcal{I}_{m,\ell}^{\omega}(f,y)=\sum_{j=0}^{m}f(t_{j})\sum_{i=0}^{m}c_{i,j}^{(m,\ell)}\int_{-a}^{a}\kappa(\omega(y-x))\bar{p}_{m,i}(x)dx=:\sum_{j=0}^{m}f(t_{j})\sum_{i=0}^{m}c_{i,j}^{(m,\ell)}q_{i}(y).$
(3.3)

Let us note that, in the above formula, the patology of the integrand, that is
the presence of the oscillating kernel, has been isolated in the coefficients
$q_{i}$ that we approximate by using a suitable tecnique explained in the next
subsection.

Next theorem establishes conditions assuring that the rule (3.3) is stable and
convergent for any $f\in C^{0}$. Moreover, it also provides an error estimate
in suitable subspaces of $C^{0}$.

######  Theorem 3.1.

For any $f\in C^{0}$, and for any $k$ defined as in (3.1), and for each fixed
$\ell$, the rule (3.3) is stable, that is

$\sup_{m}\|\mathcal{I}_{m,\ell}^{\omega}(f)\|\leq\mathcal{C}\|f\|,\quad\mathcal{C}\neq\mathcal{C}(m,f).$
(3.4)

Moreover, for any $f\in W_{r}$, $0<r\leq 2\ell$, we have

$\|\mathcal{R}_{m,\ell}^{\omega}(f)\|\leq\mathcal{C}\left(\frac{a^{r+1}\|f\|_{W_{r}}}{(\sqrt{m})^{r}}\right),\quad\mathcal{C}\neq\mathcal{C}(m,f).$
(3.5)

###  3.1 The approximation of the coefficients

Now we approach to the computation of the coefficients $q_{i}(y)$, by
proposing a suitable technique that treats the pathology of the kernel.

Let $N=\left\lfloor\omega\frac{a}{\pi}\right\rfloor+1$, introduce the
partition

$[-a,\,a]=\bigcup_{h=1}^{N}[x_{h-1},x_{h}],\quad x_{0}=-a,\quad
x_{h}=-a+h\eta,\quad\eta=\frac{2a}{N},\quad h=1,2,\dots,N,$

and consider the following decomposition in sum

$q_{i}(y)=\sum_{h=1}^{N}\int_{x_{h-1}}^{x_{h}}\kappa(\omega(y-x))\,\bar{p}_{m,i}(x)dx,\quad
i=1,...,m.$

Let us now map each interval $[x_{h-1},\,x_{h}]$ into $[-1,\,1]$ through the
linear transformations $z=\gamma_{h}(x):=2\frac{x-x_{h-1}}{\eta}-1.$ In this
way we get

$q_{i}(y)=\frac{\eta}{2}\sum_{h=1}^{N}\int_{-1}^{1}\bar{p}_{m,i}\left(\gamma_{h}^{-1}(z)\right)\kappa\left(\omega\left(y-\gamma_{h}^{-1}(z)\right)\right)dz.$

Now, by approximating each integral by a $m$-point Gauss-Legendre, we have

$q_{m,i}(y)=\frac{a}{N}\sum_{h=1}^{N}\left(\sum_{k=1}^{m}\lambda_{k}\,\bar{p}_{m,i}\left(\gamma_{h}^{-1}(z_{k})\right)\kappa\left(\omega\left(y-\gamma_{h}^{-1}(z_{k})\right)\right)+\varepsilon_{m}^{i,h}(y)\right).$
(3.6)

where $\\{z_{k}\\}_{k=1}^{m}$ are the zeros of the $m$th Legendre polynomial
and $\\{\lambda_{k}\\}_{k=1}^{m}$ are the Christoffel numbers.

######  Theorem 3.2.

Fixed $y\in[-a,a]$, for any $1\leq h\leq N$ and $0\leq i\leq m$, we get

$|\varepsilon_{m}^{i,h}(y)|\leq\frac{\mathcal{C}}{\sqrt{2\pi
i}}\left(\frac{a}{N}\right)^{m}\left(m^{\frac{1}{2m}}\cdot\frac{m+\omega}{2m-1}\right)^{m},$

$\mathcal{C}\neq\mathcal{C}(m,f)$.

Hence, by replacing the approximation (3.6) into (3.3), we have the following
product integration rule

$\widetilde{\mathcal{I}}^{\omega}_{m,\ell}(f,y)=\frac{a}{N}\sum_{j=0}^{m}f(t_{j})\sum_{i=0}^{m}c_{i,j}^{(m,\ell)}\left(\sum_{h=1}^{N}\sum_{k=1}^{m}\lambda_{k}\bar{p}_{m,i}\left(\gamma_{h}^{-1}(z_{k})\right)\kappa\left(\omega\left(\gamma_{h}^{-1}(y-z_{k})\right)\right)\right).$
(3.7)

Combining estimates by Ths. 3.1 \- 3.2, assuming $f\in W_{r}$, with $1\leq
r\leq 2\ell$ , for any $y\in[-a,a]$ and for $m$ sufficiently large (say
$m>m_{0}$, $m_{0}$ fixed), the following error estimate holds:

$|\mathcal{I}^{\omega}(f,y)-\widetilde{\mathcal{I}}^{\omega}_{m,\ell}(f,y)|\leq\mathcal{C}\|f\|_{W_{r}}\left[\frac{a^{r+1}}{(\sqrt{m})^{r}}+m^{\frac{3}{2}}\|C_{m,\ell}\|_{\infty}\left(\frac{a}{N}\cdot\frac{m+\omega}{2m-1}\right)^{m}\,\right],$

where $\mathcal{C}\neq\mathcal{C}(m,f).$

##  4 Numerical tests

In this section, we show the accuracy of our product rule as well as the
reliability of our theoretical estimates, to the following two integrals

$\mathcal{I}^{\omega}(f_{1},y)=\int_{-1}^{1}\sin{\omega(y-x)}\,f_{1}(x)\,dx,\qquad\mathcal{I}^{\omega}(f_{2},y)=\int_{-2}^{2}\cos{\omega(y-x)}\,f_{2}(x)dx,$

with $f_{1}(x)=\tanh{(x+1)}$, and $f_{2}(x)=|x+1|^{9/2}.$ In both cases, the
exact value of the integrals is not known and then we consider as exact the
value provided by our quadrature rule with $m=512$. Table 1 contains, for
increasing values of $m$, the absolute errors

$e^{\omega}_{m,\ell}(f_{j},y)=|\widetilde{\mathcal{I}}_{512,\ell}^{\omega}(f_{j},y)-\widetilde{\mathcal{I}}^{\omega}_{m,\ell}(f_{j},y)|,\qquad
j=1,2$

for the first and second integral, respectively. In both text, we fix
$\ell=2^{8}$ and we show the results in two different points and for several
values of $\omega$.

Table 1: Numerical results for integral $\mathcal{I}^{\omega}(f_{1},y)$ to the
left and for integral $\mathcal{I}^{\omega}(f_{2},y)$ to the right

$m$ | $\omega$ | $e^{\omega}_{m,2^{8}}(f_{1},-0.7)$ | $e^{\omega}_{m,2^{8}}(f_{1},0.5)$
---|---|---|---
4 | 10 | 7.20e-04 | 1.30e-04
8 |  | 1.63e-05 | 2.25e-05
16 |  | 5.91e-09 | 4.15e-09
32 |  | 2.82e-12 | 8.81e-12
64 |  | 1.32e-15 | 7.42e-15
128 |  | 8.26e-15 | 3.23e-16
256 |  | 3.27e-15 | 7.28e-15
4 | $10^{2}$ | 8.71e-04 | 1.17e-04
8 |  | 2.38e-07 | 1.06e-07
16 |  | 1.37e-10 | 1.17e-10
32 |  | 2.47e-12 | 4.09e-14
64 |  | 2.99e-15 | 7.88e-16
128 |  | 3.07e-15 | 8.41e-16
256 |  | 1.99e-15 | 1.90e-15
4 | $10^{3}$ | 6.93e-04 | 6.64e-04
8 |  | 1.53e-09 | 1.44e-09
16 |  | 3.97e-12 | 4.25e-12
32 |  | 4.63e-14 | 5.18e-14
64 |  | 2.45e-15 | 1.53e-16
128 |  | 1.15e-15 | 1.07e-15
256 |  | 7.71e-16 | 9.89e-16

$m$ | $\omega$ | $e^{\omega}_{m,2^{8}}(f_{2},-1.5)$ | $e^{\omega}_{m,2^{8}}(f_{2},1)$
---|---|---|---
4 | 10 | 1.98e-02 | 6.34e-03
8 |  | 3.78e-03 | 3.47e-03
16 |  | 1.88e-04 | 1.79e-04
32 |  | 2.41e-05 | 2.75e-05
64 |  | 3.64e-08 | 1.30e-07
128 |  | 7.76e-10 | 3.92e-10
256 |  | 1.01e-11 | 4.75e-12
4 | $10^{2}$ | 1.36e-02 | 7.04e-02
8 |  | 4.20e-05 | 2.82e-06
16 |  | 7.27e-06 | 1.52e-06
32 |  | 1.08e-07 | 1.60e-07
64 |  | 2.05e-07 | 1.66e-07
128 |  | 4.32e-09 | 4.58e-09
256 |  | 1.36e-10 | 1.07e-10
4 | $10^{3}$ | 6.91e-02 | 2.67e-02
8 |  | 3.79e-07 | 4.19e-07
16 |  | 6.53e-08 | 7.24e-08
32 |  | 1.77e-09 | 1.90e-09
64 |  | 2.08e-09 | 2.44e-09
128 |  | 2.63e-11 | 2.94e-11
256 |  | 2.06e-12 | 2.67e-12

As we can observe, in the first integral the convergence is very fast due to
the analycity of the function $f_{1}$. On the contrary, in the second integral
the convergence is slower since $f_{2}\in W_{9/2}$.

##  5 The proofs

###### Proof of Theorem 3.1.

First, let us prove the stability, i.e. (3.4). By the first identity of (3.3),
for any $y\in[-a,a]$ we have

$\displaystyle|\mathcal{I}_{m,\ell}^{\omega}(f,y)|$
$\displaystyle\leq\|f\|\int_{-a}^{a}\sum_{j=0}^{m}\left|\sum_{i=0}^{m}c_{i,j}^{(m,\ell)}\bar{p}_{m,i}(x)\right|dx\leq\|f\|\int_{-a}^{a}\sum_{i=0}^{m}\bar{p}_{m,i}(x)\sum_{j=0}^{m}\left|c_{i,j}^{(m,\ell)}\right|dx$
$\displaystyle\leq 2a\,\|f\|\
\,\|C_{m,\ell}\|_{\infty}\leq\mathcal{C}\,\|f\|,$

since $\|C_{m,\ell}\|_{\infty}\leq 2^{\ell}-1.$

Let us now estimate the error. We have

$|\mathcal{R}_{m,\ell}^{\omega}(f,y)|\leq\int_{-a}^{a}|f(x)-\bar{B}_{m,\ell}(f,x)|\,k(\omega(y-x))dx\leq\mathcal{C}\,\|f-\bar{B}_{m,\ell}(f)\|.$

The thesis follows taking into account [8, Th. 2.1] . ∎

###### Proof of Theorem 3.2.

First, let us recall that that for any $g\in W_{m}([-1,1])$ the error of the
Gauss-Legendre rule is given by

$\left|\int_{-1}^{1}g(x)dx-\sum_{k=1}^{m}\lambda_{k}g(y_{k})\right|\leq\mathcal{C}E_{2m-1}(f)\leq\frac{\mathcal{C}}{(2m-1)^{m}}(\|g\|+\|g^{(m)}\varphi^{m}\|),\quad\varphi(x)=\sqrt{1-x^{2}}$

where here and in the next $\|g\|=\displaystyle\sup_{z\in[-1,1]}|g(z)|$.
Hence, we can write

$|\varepsilon_{m}^{i,h}(y)|\leq\frac{\mathcal{C}}{(2m-1)^{m}}\left\\{\left\|\bar{p}_{m,i}\left(\gamma_{h}^{-1}\right)\kappa_{y}\left(\omega\left(\gamma_{h}^{-1}\right)\right)\right\|+\left\|\left[\bar{p}_{m,i}(\gamma_{h}^{-1})\kappa_{y}(\omega(\gamma_{h}^{-1}))\right]^{(m)}\varphi^{m}\right\|\right\\}.$

Now, taking into account that for $1\leq i\leq m-1$

$\|\bar{p}_{m,i}\|=\binom{m}{i}\left(\frac{i}{m}\right)^{i}\left(\frac{m-i}{m}\right)^{m-i}$

by Stirling’s formula we have

$\|\bar{p}_{m,i}\|\sim\frac{\sqrt{m}}{\sqrt{2\pi i}}\quad\textrm{as}\quad
m\to\infty,$

and by Bernstein inequality for polynomials (see e.g.[10]) we deduce for
$0\leq r\leq m,\ r\in\vbox{\hbox{I\hskip-2.1ptN\hfil}}$

$\left\|\bar{p}_{m,i}^{(m-r)}(\gamma_{h}^{-1})\varphi^{m-r}\right\|\leq\mathcal{C}\left(\frac{a}{N}\right)^{m-r}m^{m-r}\|\bar{p}_{m,i}\|\leq\frac{\mathcal{C}}{\sqrt{2\pi
i}}{\sqrt{m}}\left(\frac{a}{N}\right)^{m-r}m^{m-r}.$

Moreover, by the definition of the kernel $k_{y}$ in (3.1) we have

$\left\|\kappa_{y}^{(r)}\left(\omega\left(\gamma_{h}^{-1}\right)\right)\right\|\leq\left(\omega\frac{a}{N}\right)^{r}.$

Consequently, by applying Leibniz formula, we get

$\displaystyle\left\|\left(\bar{p}_{m,i}\left(\gamma_{h}^{-1}\right)\kappa_{y}\left(\omega\left(\gamma_{h}^{-1}\right)\right)\right)^{(m)}\right\|$
$\displaystyle\leq\mathcal{C}\frac{\sqrt{m}}{\sqrt{2\pi
i}}\left(\frac{a}{N}\right)^{m}\sum_{r=0}^{m}\binom{m}{r}m^{m-r}\ \omega^{r}$
$\displaystyle=\mathcal{C}\frac{\sqrt{m}}{\sqrt{2\pi
i}}\left(\frac{a}{N}\right)^{m}(m+\omega)^{m},$

and then

$\displaystyle|\varepsilon_{m}^{i,h}(y)|$
$\displaystyle\leq\mathcal{C}\frac{\sqrt{m}}{\sqrt{2\pi
i}}\left(\frac{a}{N}\right)^{m}\left(\frac{m+\omega}{2m-1}\right)^{m}.$

∎

## References

  * [1] A. Asheim, A. Dea$\tilde{n}$o, D. Huybrechs, and H. Wang.  A gaussian quadrature rule for oscillatory integrals on a bounded interval.  Discrete and Continuous Dynamical Systems- Series A, 34(3):883–901, 2014.
  * [2] M. C. De Bonis and P. Pastore.  A quadrature formula for integrals of highly oscillatory functions.  Rend. Circ. Mat. Palermo (2), Suppl. No. 82:279–303, 2010.
  * [3] F. Dell’Accio, F. Di Tommaso, and F. Nudo.  Constrained mock-chebyshev least-squares quadrature.  Applied Mathematical Letters, 2022.
  * [4] G. Felbecker.  Linearkombinationen von iterierten bernsteinoperatoren.  Manuscripta Mathematica, 29(2-4):229 – 248, 1979.
  * [5] L. Fermo, D. Mezzanotte, and D. Occorsio.  On the numerical solution of Volterra integral equations on equispaced nodes.  submitted https://arxiv.org/abs/2207.06736, 2022.
  * [6] L. Fermo and C. van der Mee.  Volterra integral equations with highly oscillatory kernels: a new numerical method with applications.  Electronic Transactions on Numerical Analysis (ETNA), 54:333–354, 2021.
  * [7] W. Gautschi.  On the construction of Gaussian quadrature rules from modified moments.  Math. Comp., 24:245–260, 1970.
  * [8] H.H. Gonska and X.-l. Zhou.  Approximation theorems for the iterated boolean sums of bernstein operators.  Journal of Computational and Applied Mathematics, 53(1):21–31, 1994\.
  * [9] D. Huybrechs and S. Vandewalle.  The construction of cubature rules for multivariate highly oscillatory integrals.  Math. Comp., 76(260):1955–1980, 2007.
  * [10] G. Mastroianni and G. V. Milovanovic.  Interpolation Processes Basic Theory and Applications.  Springer Monographs in Mathematics. Springer Verlag, Berlin, 2009.
  * [11] G. Mastroianni and M.R. Occorsio.  Una generalizzazione dell’operatore di Bernstein.  Rend. dell’Accad. di Scienze Fis. e Mat. Napoli (Serie IV), 44:151–169, 1977.
  * [12] C. Micchelli.  The saturation class and iterates of the Bernstein polynomials.  Journal of Approximation Theory, 8(1):1 – 18, 1973.
  * [13] D. Occorsio and M.G. Russo.  Nyström methods for Fredholm integral equations using equispaced points.  Filomat, 28(1):49 – 63, 2014.
  * [14] D. Occorsio, M.G. Russo, and W. Themistoclakis.  Some numerical applications of generalized Bernstein operators.  Constructive Mathematical Analysis, 4(2):186–214, 2021.
  * [15] D. Occorsio and G. Serafini.  Cubature formulae for nearly singular and highly oscillating integrals.  Calcolo, 55(1), 2018.