Year: 2018

Abstract:
Memorization in over-parameterized neural networks can severely hurt generalization in the presence of mislabeled examples. However, mislabeled examples are to hard avoid in extremely large datasets. We address this problem using the implicit regularization effect of stochastic gradient descent with large learning rates. By the loss statistics, we are able to identify mislabeled examples with remarkable success. Then, we discard the mislabeled examples on the fly and continue training with the rest of the examples. This leads to ON-THE-FLY DATA DENOISING (ODD), a simple yet effective algorithm that is robust to mislabeled examples, while introducing almost zero computational overhead. Empirical results demonstrate the effectiveness of ODD on several datasets containing artificial and real-world mislabeled examples.

heading: 1 INTRODUCTION
text: Over-parametrized deep neural networks have remarkable generalization properties while achieving near-zero training error (Zhang et al., 2016). However, the ability to fit the entire training set is highly undesirable, as a small portion of mislabeled examples in the dataset could severely hurt generalization (Zhang et al., 2016; Arpit et al., 2017). Meanwhile, an exponential growth in training data size is required to linearly improve generalization in vision tasks (Sun et al., 2017); this progress could be hindered if there are mislabeled examples within the dataset.
Mislabeled examples are to be expected in large datasets that contain millions of examples. Webbased supervision produces noisy labels (Li et al., 2017a; Mahajan et al., 2018); whereas human labeled datasets sacrifice accuracy for scalability (Krishna et al., 2016). Therefore, algorithms that are robust to various levels of mislabeled examples are warranted in order to further improve generalization for very large labeled datasets.
In this paper, we propose On-the-fly Data Denoising (ODD), a simple and robust method for training with noisy examples based on the implicit regularization effect of stochastic gradient descent. First, we train residual networks with large learning rate schedules and use the resulting losses to separate clean examples from mislabeled ones. This is done by identifying examples whose losses exceed a certain threshold. Reasonable thresholds can be derived from the loss distribution for uniform label noise which does not depend on the amount of mislabeled examples in the dataset. Finally, we remove these examples from the dataset and continue training until convergence.
Empirically, ODD performs significantly better than previous methods in datasets containing artificial noise (Sections 4.1 and 4.2) or real-world mislabeled examples (Section 4.3), while achieving equal or better accuracy than the state-of-the-art on clean datasets (Sections 4.1 and 4.2). We further conduct ablation studies to demonstrate that ODD is robust w.r.t hyperparameters and artificial
noise levels (Section 4.4). Our method is also able to detect mislabeled examples in the CIFAR-100 dataset without any additional supervision (Figure 1).

heading: 2 DENOISING DATASETS ON-THE-FLY
text: The goal of supervised learning is to find a function f ∈ F that describes the probability of a random label vector Y ∈ Y given a random input vector X ∈ X , which has underlying joint distribution P (X,Y ). Given a loss function `(y, ŷ), one could minimize the average of ` over P :
R(f) = ∫ `(y, f(x)) dP (x,y)
The joint distribution P (X,Y ) is usually unknown, but we could gain access to its samples via a potentially noisy labeling process, such as crowdsourcing (Krishna et al., 2016) or web queries (Li et al., 2017a). We denote the training dataset with N examples as D = (xi,yi)i∈[N ] = G ∪ B. G represents correctly labeled (clean) examples sampled from P (X,Y ). B represents mislabeled examples that are not sampled from P (X,Y ), but from another distribution Q(X,Y ); G ∩ B = ∅. We aim to learn the function f from D without knowledge about B, G or their statistics (e.g. |B|). A typical approach is to assume that B = ∅, i.e. all examples are i.i.d. from P (X,Y ), and minimizing the following objective:
R̂(f) = − 1 N N∑ i=1 `(y, f(x))
If B = ∅ is indeed true, then R̂(f) → R(f) as N → ∞. However, this is not true if B 6= ∅ since D is no longer an unbiased population of P (X,Y ). Moreover, when F is the space of large neural networks with parameters exceeding N , f could fit the entire training dataset (Zhang et al., 2016), including the mislabeled examples. This results in undesired behavior of f on inputs of the mislabeled set, let alone outside the training data.
To illustrate the harm of mislabeled examples to generalization, we consider training on CIFAR-10 where some examples are mislabeled uniformly at random. Compared with training on D, training only on G could decrease validation error from 11.53 to 4.25 if there are 20% mislabeled examples, and from 15.57 to 5.06 if there are 40% mislabeled examples1. Therefore, if we are able to identify examples that belong to G, we could vastly improve generalization on P (X,Y ).

heading: 2.1 SEPARATING MISLABELED EXAMPLES VIA IMPLICIT REGULARIZATION
text: Fortunately, in the case of classification with deep residual networks (He et al., 2015a), the implicit generalization of stochastic gradient descent (SGD) with large learning rates (e.g. 0.1) can separate examples from G and examples from B via the loss statistics. We demonstrate this in Figure 2, where we train deep residual networks on CIFAR-100 and ImageNet with different percentages of uniform label noise. In early stages of training, the loss distributions of clean examples and mislabeled ones have notable statistical distance. The network starts to fit mislabeled examples when learning rate starts to decrease, which is also crucial for achieving better generalization on clean datasets.
The working of the implicit regularization of gradient descent is by and large an open question that attracts much recent attentions (Neyshabur, 2017; Li et al., 2017b; Du et al., 2018). Empirically, it has been observed that large learning rates are beneficial for generalization (Kleinberg et al., 2018). Recent work has shown that the stationary distribution of SGD iterates corresponds to an Ornstein-Uhlenbeck process (Uhlenbeck & Ornstein, 1930) with noise proportional to the learning rate (Mandt et al., 2017). Training with large learning rates would then encourage solutions that are more robust to large random perturbations in the parameter space and less likely to overfit to mislabeled examples. Therefore, given these empirical and theoretical evidence on large learning rate helps generalization, we propose to classify correct and mislabeled examples through the loss statistics, and achieve better generalization by removing the examples that are potentially mislabeled and training on clean examples only.
1Validation error is 3.73 for 0% mislabeled case. Additional details for CIFAR-100 in Table 1.

heading: 2.2 THRESHOLDS THAT CLASSIFY MISLABELED EXAMPLES
text: To improve generalization in practice, one critical problem is to select a reasonable threshold for classification. High thresholds could include too many examples from B, whereas low thresholds could prune too many examples from G; reasonable thresholds should also adapt to different unknown ratios of mislabeled examples. Let us first consider the case where Q(Y |X) has the highest entropy, which is the uniform distribution over labels. From Figure 2, the loss distribution for B is relatively stable with different ratios of |B|/|D|; examples in B are making little progress when learning rate is large. We propose to characterize the (negative log-likelihood) loss distribution of uniform label noise pn(l) via the following generative procedure:
l = −ỹk + log  ∑ i∈[N ] exp(ỹi)  ≡ − log softmax(ỹ)[k] (1) ỹ = fc(relu(x̃)), x̃ ∼ N (0, I), k ∼ Uniform{0, . . . ,K}
where fc(·) is the final (fully connected) layer of the network, relu(x̃) = max(x̃,0) is the Rectified Linear Unit, and k represents a random label from K classes. This represents the case where the model’s prediction is uncorrelated with the labels. The actual noise distribution could skew to the left if the model overfits to the noise, and skew to the right if the model predicts a label different from the noisy one. We find that an identity covariance matrix for x̃ is able to explain the noise distribution; this could result from well-conditioned objectives defined via deep residual networks (He et al., 2015a) and careful initialization (He et al., 2015b). We qualitatively demonstrate the validity of our characterization on CIFAR-100 and ImageNet datasets in Figure 2.
Therefore, we could define a threshold via the p-th percentile of pn(l); it relates to approximately how much examples in B we would retain if Q(Y |X) is uniform. In Section 4.4, we show that this method is able to identify different percentages of uniform label noise with high precision.

heading: 2.3 A PRACTICAL ALGORITHM FOR ROBUST TRAINING
text: We can utilize this implicit regularization effect to remove examples that might harm generalization, leading to On-the-fly Data Denoising (ODD), a simple algorithm robust to mislabeled examples:
1. Train all examples with large learning rates for E epochs.
2. Compute the p-th percentile of the distribution in Eq. (1), denoted as Tp.
3. Remove examples whose average loss of the past h epochs exceeds T from the dataset.
4. Continue training the remaining examples from epoch E + 1.
ODD introduces three hyperparameters: E determines the amount of training that separates clean examples from noisy ones; p determines Tp that specifies the trade-off between less noisy examples and more clean examples; h determines the window of averaged loss statistics to reduce variance from data augmentation. We do not explicitly estimate the portion of noise in the dataset, nor do we assume any specific noise model. In fact, the threshold Tp could be used to accurately predict the portion of uniform noise in the dataset, and works quite well even on other types of label noise; we will demonstrate this in Section 4. Moreover, ODD is compatible with existing practices for learning rate schedules, such as stepwise (He et al., 2015a) or cosine (Loshchilov & Hutter, 2016).

heading: 3 RELATED WORK
text: Implicit Regularization of SGD The generalization of neural networks trained with SGD depend heavily on learning rate schedules (Loshchilov & Hutter, 2016). It has been proposed that wide local minima2 could result in better generalization (Hochreiter & Schmidhuber, 1995; Chaudhari et al., 2016; Keskar et al., 2016). Several factors could contribute to wider local optima and better generalization, such as smaller minibatch sizes (Keskar et al., 2016), reasonable learning rates (Kleinberg et al., 2018), and longer training time (Hoffer et al., 2017). Moreover, solutions that are further away from the initialization may lead to wider local minima and better generalization (Hoffer et al., 2017). In the presence of mislabeled examples, changes in optimization landscape (Arpit et al., 2017) could result in bad local minima (Zhang et al., 2016), although it is argued that larger batch sizes could mitigate this effect (Rolnick et al., 2017).
Training with Mislabeled Examples One paradigm to robust training with noisy labels involves estimating the noise distribution (Liu & Tao, 2014) or confusion matrix (Sukhbaatar et al., 2014). Another line of methods propose to identify and clean the noisy examples through predictions of auxillary networks (Veit et al., 2017) or via binary predictions (Northcutt et al., 2017); the noisy labels are either pruned (Brodley et al., 1996) or replaced with model predictions (Reed et al., 2014). Our method is comparable to these approaches, but the key difference is that we leverage the implicit regularization effect of SGD to identify noisy examples. Other approaches propose to reweigh the examples via a pretrained network (Jiang et al., 2017), meta learning (Ren et al., 2018), or surrogate loss functions (Ghosh et al., 2017; Zhang & Sabuncu, 2018). Some methods require a set of trusted examples (Xiao et al., 2015; Hendrycks et al., 2018).
ODD has several appealing properties compared to existing methods. First, the thresholds for classifying mislabeled examples from ODD do not rely on estimations of the noise confusion matrix. Next, ODD does not require additional trusted examples. Finally, ODD removes potentially noisy examples on-the-fly; it has little computational overhead compared to standard SGD training.

heading: 4 EXPERIMENTS
text: We evaluate our method on clean and noisy versions of CIFAR-10, CIFAR-100, ImageNet (Russakovsky et al., 2015) and WebVision (Li et al., 2017a) datasets. We use stochastic gradient descent with momentum for training while following standard image preprocessing and data augmentation practices. We do not consider dropout (Srivastava et al., 2014) or model ensembles (Huang et al., 2017) in our experiments. We use h = 2 for all our ODD experiments; we observe that having h ∈ [2, 5] yields similar results.

heading: 4.1 CIFAR-10 AND CIFAR-100
text: We first evaluate our method on the CIFAR-10 and CIFAR-100 datasets, which contain 50,000 training images and 10,000 validation images of size 32×32 with 10 and 100 labels respectively. During training, we follow the data augmentations in (Zagoruyko & Komodakis, 2016), which performs horizontal flips, takes random crops from 40× 40 images padded by 4 pixels on each side, and fills missing pixels with reflections of the original images.
In our experiments, we train the wide residual network architecture (WRN-28-10) in (Zagoruyko & Komodakis, 2016) for 200 epochs with a minibatch size of 128, momentum 0.9 and weight decay
2Although the notion of wideness is controversial (Dinh et al., 2017).
5×10−4. We consider a cosine annealing schedule as described in (Loshchilov & Hutter, 2016) with T0 = 200, Tmult = 1, ηmax = 0.1, ηmin = 10
−5 (no warm restarts), as we observe this schedule outperforms the traditional stepwise schedules on the clean dataset. We include results for two types of stepwise schedules in Appendix A.1.

heading: 4.1.1 GENERALIZATION ON INPUT-AGNOSTIC LABEL NOISE
text: We first consider label noise that are agnostic to inputs. Following Zhang et al. (2016), We randomly replace a 0%/20%/40%) of the training labels to uniformly random ones, and evaluate generalization error on the clean validation set. We compare with the following baselines: ORACLE, where the model knows the true identity of clean examples and only trains on them; Empirical Risk Minimization (ERM, Goyal et al. (2017)) which assumes all examples are clean; MENTORNET (Jiang et al., 2017), which pretrains an auxiliary model that predicts weights for each example based on its input features; REN (Ren et al., 2018), which optimizes the weight of examples via meta-learning; mixup (Zhang et al., 2017), a data augmentation approach that trains neural networks on convex combinations of pairs of examples and their labels; and Generalized Cross Entropy (GCE, Zhang & Sabuncu (2018)) that includes cross-entropy loss and mean absolute error (Ghosh et al., 2017).
We report the top-1 validation error in Table 1, where ? denotes methods trained with knowledge of 1000 additional clean labels. Notably, ODD significantly outperforms all other algorithms (except for the oracle) when there is artificial noise, and is on-par with ERM even when there is no artificial noise. On the one hand, this suggests that ODD is able to distinguish the mislabeled examples and improve generalization; on the other hand, it would seem that removing certain examples even in the “clean” dataset does not seem to hinder generalization.
ODD prevents overfitting to noise We compare the learning curves of ERM and ODD in Figure 3 with a stepwise schedule under 40% label corruption. ERM easily overfits the random labels when learning rate decreases, whereas ODD manages to continue improving generalization.
Mislabeled examples in CIFAR-100 We run our methods on three random seeds, and find the examples that are considered mislabeled by all the three instances (598 in total); we demonstrate some examples3 in Figure 1, which contains ambiguous / wrong labels.
3We include more examples in Appendix A.4.

heading: 4.1.2 GENERALIZATION ON INPUT-DEPENDENT LABEL NOISE
text: Images from some classes could be harder to label correctly than that from other classes. To simulate this, we perform experiments on settings where the label noise only comes from certain types of input data. Specifically, we remove a portion of classes from the dataset (e.g. class 9 in CIFAR-10), and assign the labels of all its examples to the remaining classes randomly (e.g. a class 9 example has a class 0 – 8 random label). This reduces the total number of classes, so on the validation set we only consider the classes that are not removed (e.g. classes 0 – 8). We compare ERM and ODD on datasets with 10% or 20% of the examples mislabeled, and summarize the results in Table 2. ODD is still able to significantly outperform ERM under such input-dependent noise.

heading: 4.1.3 GENERALIZATION ON NON-HOMOGENEOUS LABELS
text: We evaluate ERM and ODD on a setting without mislabeled examples, but the ratio of classes could vary. To prevent the model from utilizing the number of examples in a class, we combine multiple classes of CIFAR-100 into a single class, creating the CIFAR-20 and CIFAR-50 tasks. In CIFAR-50, we combine an even class with an odd class while we remove c% of the examples in the odd class. In CIFAR-20, we combine 5 classes in CIFAR-100 that belong to the same super-class4 while we remove c% of the examples in 4 out of 5 classes. This is performed for both training and validation datasets. Results for ERM and ODD with p = 10 and E = 75 are shown in Table 3, where ODD is able to outperform ERM in these settings where the input examples are not uniformly distributed.

heading: 4.2 IMAGENET
text: We conduct additional experiments on the ImageNet-2012 classification dataset (Russakovsky et al., 2015). The dataset contains 1.28 million training images and 50,000 validation images from 1,000 classes. Input-agnostic random noise of 0%, 20%, 40% are considered. We follow standard data augmentation practices during training, including scale and aspect ratio distortions, random crops, and horizontal flips. We only use the center 224× 224 crop for validation. We train ResNet-50 and ResNet-152 models (He et al., 2015a) with the cosine schedule with initial learning rate 0.1, momentum 0.9, weight decay 10−4, 90 training epochs, and report top-1 and top-5 validation errors in Table 4. ODD significantly outperforms ERM in terms of both top-1 and top-5 errors on the 20% and 40% mislabeled examples, while being competitive with the clean dataset.
4Super-class information is available at https://www.cs.toronto.edu/˜kriz/cifar.html.

heading: 4.3 WEBVISION – A REAL-WORLD NOISY DATASET
text: We further verify the effectiveness of our method on a real-world noisy dataset. The WebVision2017 dataset (Li et al., 2017a) contains 2.4 million of real-world noisy labels, that are crawled from Google and Flickr using the 1,000 labels from the ImageNet-2012 dataset. We train two architectures, ResNet-50 and Inception ResNet-v2 (Szegedy et al., 2016) with the same procedure in the ImageNet experiments, except for Inception ResNet-v2 we train for 50 epochs and use input images of size 299×299. We use both WebVision and ImageNet validation sets for 1-crop validation, following the settings in Jiang et al. (2017). We do not use a pretrained model or additional labeled data from ImageNet during training.
Our ODD method with p = 30 removes in the training set around 9.0% of the total examples with ResNet-50 and 9.3% of the total examples with Inception ResNet-v2 (Szegedy et al., 2016). Table 5 suggests that our method is able to outperform both ERM and MENTORNET when the training dataset is noisy, even as we remove a notable portion of examples. We include more results in Appendix A.3. In comparison, we removed around 1.1% of examples in ImageNet (Table 10, Appendix A.2); this may suggest that WebVision labels are indeed much noisier.

heading: 4.4 ABLATION STUDIES
text: Sensitivity to p We first evaluate noisy ImageNet classification with ResNet-50 where p ∈ {1, 10, 30, 50, 80} and E = 60 in Table 6. A higher p includes more clean examples at the cost of involving more noisy examples. In the 20% and 40% noisy cases, the optimal trade-off for generalization is at p = 10, yet even when p = 50, the validation errors are still significantly better than ERM. When there is no artificial noise, generalization of ODD starts to match that of ERM as p ≥ 10. Therefore, ODD is not very sensitive to p in these cases, and empirically p = 10 represents the best trade-off. We include results for ResNet-152 in Appendix A.2.
Sensitivity to E We evaluate the validation error of ODD on CIFAR with 20% and 40% inputagnoistic label noise where E ∈ {25, 50, 75, 100, 150, 200} (E = 200 is equivalent to ERM). The results in Figure 4 suggest that our method is able to separate noisy and clean examples if E is
relatively small where the learning rate is high, but is unable to perform well when the learning rate decreases at later stages of the training.
Sensitivity to the amount of noise Finally, we evaluate the training error of ODD on CIFAR under input-agnostic label noise of {1%, 5%, 10%, 20%, 30%, 40%} with p = 5, E = 50 or 75. This reflects how much examples exceed the threshold and are identified as noise at epoch E. From Figure 5, we observe that the training error is almost exactly the amount of noise in the dataset, which demonstrates that the loss distribution of noise can be characterized by our threshold regardless of the percentage of noise in the dataset.

heading: 5 DISCUSSION
text: We have proposed ODD, a straightforward method for robust training with mislabeled examples. ODD utilizes the implicit regularization effect of stochastic gradient descent to prune examples that potentially harm generalization. Empirical results demonstrate that ODD is able to significantly outperform related methods on a wide range of datasets with artificial and real-world mislabeled examples, maintain competitiveness with ERM on clean datasets, as well as detecting mislabeled examples automatically in CIFAR-100.
The implicit regularization of stochastic gradient descent opens up other research directions for implementing robust algorithms. For example, we could consider using a smaller network to remove examples, removing examples not only once but multiple times, retraining from scratch with the denoised dataset, or other data-augmentation approaches such as mixup (Zhang et al., 2017). Moreover, it would be interesting to understand the implicit regularization over mislabeled examples from a theoretical viewpoint.

heading: A ADDITIONAL EXPERIMENTAL RESULTS
text: A.1 CIFAR INPUT-AGNOSTIC NOISE
In addition to the existing experiments, we include results for ORACLE, ERM, ODD with two stepwise annealing schedules. In the stepwise schedules, the learning rate starts from 0.1 and is then divided by 5 after 60, 120, 160 epochs (stepwise-i, which is used in Zagoruyko & Komodakis (2016)) or after 100, 150, 175 epochs (stepwise-ii). We consider cosine schedule in Section 4 because it achieves better generalization performance on the clean dataset.
For the stepwise schedules, we set E to be the epoch at which learning rate begins to decay. For the cosine schedule, we set E = 100 for CIFAR-10 and E = 50 for CIFAR-100. We set p = 20 and p = 10 for CIFAR-10 and CIFAR-100 respectively for the clean datasets; p = 10 and p = 5 for noisy datasets. This is motivated by the fact that CIFAR-10 has less labels, so the threshold has to take into account random labels that happens to be correct.
Tables 7 and 8 contain summary of the results. The cosine learning rate schedule generally outperforms the stepwise schedules. We note that for the stepwise schedules in ERM, the optimal validation error is achieved when the learning rate just starts to decay to 0.2, after that the model starts to overfit to noise, as demonstrated in Figure 3.
We evaluate precision and recall for examples classified as noise on CIFAR10 and CIFAR100 for different noise levels (1, 5, 10, 20, 30, 40) in Figure 6. The recall values are around 0.84 to 0.88 where as the precision values range from 0.88 to 0.92. This demonstrates that ODD is able to achieve good precision/recall with default hyperparameters even at different noise levels.
A.2 IMAGENET ABLATION RESULTS ON RESNET-152
We include the ImageNet ablation experiments on the hyperparameter p on the ResNet-152 architecture in Table 9. Compared to the ResNet-50 experiments, we can draw similar conclusions here: p = 10 generally represents the best trade-off. We show the percentage of examples discarded by NOISE CLASSIFIER in Table 10; the percentage of discarded examples by p = 10 is very close to the actual noise level. Moreover, the percentage of discarded examples does not vary significantly when we change our architecture from ResNet-50 to ResNet-152.
A.3 WEBVISION ABLATION RESULTS
We include the WebVision ablation experiments on the hyperparameter p on the ResNet-50 and Inception ResNet-v2 architecture with E = 60 in Tables 11 and 12, where we report top-1 and top-5 validation errors on WebVision and ImageNet validation sets respectively, as well as how many examples are discarded by our method at epoch 60. Similar to the results in ImageNet, generalization performance is generally insensitive to the hyperparameter p, except for p = 1, which discarded 25.3% of the examples. We use 2 seeds for each experiment setting. Notice that at each p, WebVision has more examples discarded compared to ImageNet (with 0% artificial noise), which further suggests that it has more mislabeled examples than ImageNet. Again, the percentage of discarded examples does not vary significantly across different architectures.
A.4 IMAGES IN CIFAR-100 CLASSIFIED AS NOISE
We display the examples in CIFAR-100 training set for which our ODD methods identify as noise across 3 random seeds. One of the most common label such examples have is “leopard”; in fact, 21 of 50 “leopard” examples in the training set are perceived as hard, and we show some of them in Figure 7. It turns out that a lot of the “leopard” examples contains images that clearly contains tigers and black panthers (CIFAR-100 has a label corresponding to “tiger”).
We also demonstrate random examples from the CIFAR-100 that are identified as noise in Figure 8 and those that are not identified as noise in Figure 9. The examples identified as noise often contains multiple objects, and those not identified as noise often contains only one object that is less ambiguous in terms of identity.

Review summaries:
The paper aims to remove potential examples with label noise by discarding the ones with large losses in the training procedure. The idea also applies to the setting where instances may contain large noise. The proposed method may have an implicit trade-off between the robust to label noise and feature noise, which explains why the proposed method also has good performances on instance-dependent label noise. The paper is well-written and has sufficient experiments. 

This paper presents ODD, a method that rejects incorrectly labeled / noisy examples from training on the fly. The motivation is sound, that with the capacity of modern neural networks, it's easy to memorize the mislabeled data and thus hurt generalization. If we could reject such mislabeled data, we may be able to get a more generalizable model. The authors made an observation that when training with large learning rate, examples with correct labeling and incorrect labeling exhibits different loss distributions. The authors further noticed that the loss distribution of incorrectly labeled examples can be simulated using eq.(1). Therefore, by setting a threshold that corresponds to a percentile of the incorrectly labeled loss distribution, the authors are able to reject incorrect examples.