Year: 2018

Abstract:
We propose an energy-based framework for correcting mislabelled training examples in the context of binary classification. While existing work addresses random and class-dependent label noise, we focus on feature dependent label noise, which is ubiquitous in real-world data and difficult to model. Two elements distinguish our approach from others: 1) instead of relying on the original feature space, we employ an autoencoder to learn a discriminative representation and 2) we introduce an energy-based formalism for the label correction problem. We prove that a discriminative representation can be learned by training a generative model using a loss function comprised of the difference of energies corresponding to each class. The learned energy value for each training instance is compared to the original training labels and contradictions between energy assignment and training label are used to correct labels. We validate our method across eight datasets, spanning synthetic and realistic settings, and demonstrate the technique’s state-of-the-art label correction performance. Furthermore, we derive analytical expressions to show the effect of label noise on the gradients of empirical risk.

heading: 1 INTRODUCTION
text: Machine learning algorithms depend on reliable training labels or, when applicable, sufficiently robust learning models in order to produce generalizable predictions (Zhu & Wu, 2004; Frénay & Verleysen, 2014). Many empirical datasets suffer from training label corruption, which can result from annotation error, human bias, or a noisy process for generating labels (Smyth, 1996; Brodley & Friedl, 1999). In practice, it can be costly to obtain noise-free labels; hence, research on reducing the effects of label noise on learning has received considerable attention.
Most work, however, focuses on label noise that is independent of the input features (e.g., random label noise or class conditional random noise). The introduction of feature dependency significantly complicates mathematical analysis (Natarajan et al., 2013; Liu & Tao, 2014; Northcutt et al., 2017). Although work in this domain has yielded impressive results and improved generalization (Rebbapragada & Brodley, 2007a; Natarajan et al., 2013; Patrini et al., 2017; Rolnick et al., 2017; Ren et al., 2018), the simplicity of these noise assumptions fails to capture crucial mislabelling processes that arise in practice. In this work, we propose a semi-supervised framework for correcting the effects of feature dependent label noise on supervised learning algorithms.
Label noise processes are categorized into three types, as illustrated in Figure 1. Type I refers to a noise model where any label in the training data is incorrect with probability γ. In the case of type II noise, the probability of label corruption is conditioned on the class, such that we have different noise rate γ0 and γ1 for each class. Finally, type III noise models describe how label noise depends explicitly on input features. Feature dependent label noise or equivalently type III noise is a more realistic type of label noise that is ubiquitous in empirical datasets (Lachenbruch, 1974; Schafer & Graham, 2002; Frénay & Verleysen, 2014). As an example of type III noise, consider the diagnostic labels of Alzheimer’s disease. In this setting, the probability of label noise depends on both age and sex (i.e., younger male patients are harder to diagnose) (Khachaturian, 1985; Murray et al., 2016). Type III noise also includes the prevalence of unreliable labels for training instances in low density regions of feature space (Denoeux, 1995; 1997; 2000) or near classification boundaries (Lachenbruch, 1966; 1974; Chhikara & McKeon, 1984; Cohen, 1997; Beigman & Klebanov, 2009; Beigman Klebanov & Beigman, 2009; Kolcz & Cormack, 2009).
In this paper, we present a practical framework for correcting label noise that extends beyond type I and type II noise. We train an energy-based generative model on a small subset of the training data with reliable labels, either manually annotated or automatically learned. This model is used to identify and correct mislabelled examples based on the whether the assigned energy of a given point is compatible with its original label. We empirically demonstrate our framework’s ability to handle input dependent label noise on both simulated and real datasets.

heading: 2 RELATED WORK
text: The full body of work on the problem of label noise is too extensive to review here; however, we direct interested readers to the detailed review by Frénay & Verleysen (2014). In this section, we highlight key contributions in the label noise literature. We then briefly discuss existing theoretical work.

heading: 2.1 LABEL NOISE CORRECTION
text: Existing work in label noise correction is designed for Type I and Type II noise and falls into three categories: relabeling, learning procedures and loss functions. We expand on each area below.
Relabeling: Earlier approaches to label noise focus on relabeling the noisy training set. Brodley & Friedl (1999) use the output of an ensemble of classifiers to identify mislabeled training examples. Sun et al. (2007) identify mislabeled instances based on the entropy of class probabilities outputted by a Bayesian classifier. These approaches, while robust to simpler label noise models, do not account for Type III noise.
Learning Procedures: Methods modifying the learning procedure include the perceptron algorithm with margin (PAM) Frénay & Verleysen (2014). Crammer & Lee (2010) use a velocity-based learning procedure to learn the weight vector distribution, termed gaussian herding (NHERD). Sukhbaatar et al. (2014) introduce a noise layer to a neural network architecture to learn the noise function, while Rebbapragada & Brodley (2007b) weight each example by class confidence in the training procedure. These methods commonly suffer from overfitting to the noise and again, primarily focus on Type I and Type II noise.
Loss Functions: Long & Servedio (2010) have shown classification algorithms that optimize a convex potential over a linear class are not robust to random label noise. This has led to work which aims to modify convex loss functions in order to make them noise-tolerant in the presence of type I and type II noise. Ghosh et al. (2015) derived sufficient conditions for classification losses that render them robust to random noise; namely, the components of a loss (where each component is defined over a given class) must sum to a constant value. Rooyen et al. (2015) proposed a convex loss that avoids the negative result of Long & Servedio (2010) for type I noise by virtue of being negatively unbounded. Natarajan et al. (2013) have shown that risk minimization over the corrupted data is consistent with risk minimization over clean data provided that the standard convex loss (e.g., binary cross entropy) is modified appropriately to produce an unbiased loss estimator (ULE). Each of these loss functions is presented for and validated on Type I and Type II noise.

heading: 2.2 EXISTING THEORETICAL GUARANTEES
text: (Bylander, 1994; Blum et al., 1998; Blum & Mitchell, 1998) offer guarantees for hypothesis generalization in the face of Type I and Type II noise. Angluin & Laird (1988); Bylander (1997; 1998); Servedio (1999) present guarantees for type III noise, where the probability of error depends on the distance to the margin. We introduce a gradient-based interpretation of label noise to these existing results.

heading: 3 BINARY CLASSIFICATION IN THE PRESENCE OF LABEL NOISE

heading: 3.1 PROBLEM SETUP AND NOTATION
text: Let P denote the true distribution from which n i.i.d. training examples (x1, y1), (x2, y2), . . . , (xn, yn) have been drawn, where (xi, yi) ∈ Rd × {0, 1}. The clean and corrupted training datasets are denoted as
T = { (xi, yi) for i = 1, 2, . . . , n } & T̃ = { (xi, ỹi) for i = 1, 2, . . . , n } , (1)
respectively, where due to some label noise process yi → ỹi. Hence, we have access to the noisy data T̃ during training instead of the clean data T . It can be assumed that the corrupted samples (xi, ỹi) are drawn from a noisy distribution P̃ .
In supervised binary classification, we aim to learn a discriminator f : Rd → R that minimizes the risk with respect to a given loss function1. Formally, we want to minimize the empirical risk is R̂ [`, f, T ] = 1m ∑m i=1 ` (f(xi,θ), yi), where the m, `, θ denote the size of the mini-batch size, loss function, and the learnable model parameters respectively. Gradient based learning algorithms compute ∇θ(R̂ [`, f, T ]) and update model parameters. For example, as in mini-batch gradient descent,
θt+1 = θt − η∇θ ( R̂ [`, f, T ] ) , (2)
where η is the learning rate. In practice, we may not have access to the clean data T . Instead we must learn the discriminator using the noisy data T̃ . Thus, the second term in Eq. 2 becomes ∇θ(R̂[`, f, T̃ ]), which denotes the risk with respect to the noisy training data.

heading: 3.2 LABEL NOISE EFFECT ON RISK MINIMIZATION
text: We can describe the effect of label noise on learning by expressing the noisy gradient∇θ(R̂[`, f, T̃ ]) in terms of the true gradient ∇θ(R̂[`, f, T ]) and a noise term. In the case of type I noise where any label yi can be flipped to 1− yi with probability γ ∈ [0, 1/2], we have
E(x,ỹ)∼P̃ [ ∇θR̂[`, T̃ ] ] = (1− 2γ)Etrue + 2γ Erand, (3)
where Etrue ≡ E(x,ỹ)∼P̃ [∇θR̂[`, T ]] is the true (i.e. noise-free) gradient, and Erand is the completely noisy term obtained by replacing all targets yi with a random value of either 0 or 1. For type II noise, we have an equation analogous to Eq. 3, where γ is replaced by the average γ̄ = (γ0 + γ1)/2 noise rate and we have an additional term reflecting the noise imbalance between each class when γ0 6= γ1. For more information on this and derivations of these equations, see Appendix A. From Eq. 3 we deduce that for small γ the true gradients dominate the dynamics of searching θ space for optimal parameters. As γ grows, the true gradients are scaled down by the factor (1−2γ), which means that the contribution of Etrue diminishes and the random perturbation term Erand starts to dominate as γ grows. A similar conclusion can be reached for type II noise (replacing γ with γ̄) where we have an additional term modifying the true gradients based on the class imbalance (see A.2).
The effect of Erand can be negated by increasing the amount of training data proportionately with γ̄ as discussed by Rolnick et al. (2017): i.e. as the probability of a random error occurring increases,
1In practice the loss function ` is usually classification-calibrated to minimize the 0-1 loss given that the sample size is sufficiently large (Bartlett et al., 2006).
the model needs more data to make progress in the direction of the true gradient. We can neutralize the effects (i.e. suppress Erand) of random noise (type I) or class conditional random noise (type II) by increasing the number of training examples and by utilizing a robust loss function when possible (Natarajan et al., 2013).
In contrast, Type III noise is substantially more difficult to address because the available training data T̃ can have optimal discriminators that are significantly different from the true discriminator corresponding to the clean data T . Separating Type III noise into the true term and the perturbation term necessitates restrictive assumptions on the noise model (See Appendix A. In Figure 2, we show this by visualizing SGD over the true training set (gold lines) and the noise training set (blue lines). As shown in Figure 2, increasing the size of the training set is effective in address Type II noise. This strategy is not only ineffective for addressing type III noise, but they can also lead to our model learning the biased discriminator; thus, hindering any possibility of generalization.

heading: 4 AN ENERGY-BASED FRAMEWORK FOR BIAS CORRECTION
text: Type III noise is particularly challenging because noise can depend on the input features in an arbitrarily complex way. Modeling this requires significant information about the noise process, which can be difficult to obtain in practice. In order to deal with this challenge we will avoid training directly on the mislabelled instances. Instead, we start our training procedure by assuming there exists a small subset of T̃ that is noise-free (e.g. 1% of the data is sufficient the MNIST dataset). Such a set can be obtained via a manual labelling process or by using domain knowledge to identify the appropriate data points2.
Our objective is to correct mislabelled training instances such that the corrected data leads to the improved generalization of a trained model. We will demonstrate in Section 5 that our framework extends beyond Type I and Type II noise to Type III noise, in realistic settings. In particular, we demonstrate the method’s strength in correcting algorithmically assigned labels.
The proposed correction framework consists of three steps:
1. Obtain known labels: There are two ways of identifying instances that have correct labels. The first approach is to use domain knowledge – frequently, one has access to a subset of clean labels and their instances. We can use this subset as our clean data for step 2. If this set is unknown or too small, then we can inference which examples are likely to be correctly labeled, as is done in Ding et al. (2018). We report results on both approaches in Section 5.
2This assumption can be relaxed in situations where we can learn which labels are likely to be clean. E.g. see Ding et al. (2018)
2. Train semi-supervised model: The framework uses the filtered data from the previous step to train a semi-supervised algorithm that learns to classify instances based on similarity between features. In contrast with supervised learning, where the goal is to learn p(y|x), we want to learn which features are most compatible with a given label: i.e. p(x|y). Thus, we train a generative model (e.g. energy-based autoencoder) to use feature similarity (as quantified by an energy function) to identify which instances belong to the specific class.
3. Identify and correct mislabelled instances: The features of the full training data (with mislabeled targets) are injected into the previously trained semi-supervised model resulting in each instance being assigned an energy value based on the output of the model. The energy corresponding to each instance serves as a proxy for class assignment (i.e. low energy corresponds to y = 0 whereas high energy corresponds to y = 1). Contradictions between energy assignment and training labels are used to correct the training data such that all labels are compatible with their assigned energy.
We first motivate the design decisions involved in this framework. Namely, we explore our choice of contrastive divergence as a loss function and empirically justify our use of an autoencoder. In the subsequent section, we elaborate on our implementation of the framework.

heading: 4.1 FRAMEWORK MOTIVATION
text: Given a small, clean dataset T ⊂ T̃ , we aim to train a model which can be used to determine labels on the remaining, noisily labelled dataset. One obvious approach is to train a binary classifier directly and use it to correct labels. However, as discussed by Berthelot et al. (2017), binary classification provides a relatively weak training signal which largely ignores the intricacies of the input feature distribution. See Fig. 3 where we compare the class separation achieved by a few standard binary classifiers with our proposed approach. Alternatively, one could train class conditional models. However, such models are trained without knowledge of the primary task, differentiating classes. Further, traditional unsupervised training regimes typically use a maximum likelihood formulation (i.e. forward KL divergence) which is prone to distributing probability mass broadly (the so-called “mean-seeking behaviour” (Murphy, 2012)) and further limit the discriminative ability of the learned model.
Instead, we prioritize learning to discriminate the underlying classes based on aspects of the input feature distributions. To do this, we propose to use a contrastive divergence (Carreira-Perpinan & Hinton, 2005) training loss:
CD (θ) = KL [p0 (x) ‖q (x;θ)]− KL [p1 (x) ‖q (x;θ)] . (4) where p0(x) and p1(x) denote the target probability distributions conditioned on class 0 and 1 respectively and q(x; θ) denotes the learned model. Thus, training aims to produce a model q (x;θ) which assigns high probability to samples from class 0, while giving low probability to samples from class 1. In theorem 1, we show that a finite sample approximation of the optimization objective in Eq. 4 can be computed as
L (θ) = 1 |T0| ∑ x0∈T0 E (x0;θ)− 1 |T1| ∑ x1∈T1 E (x1;θ) , (5)
where Ty , for y ∈ {0, 1}, contains instances from class y and Ty ⊆ T , |Ty| denotes the number of elements in Ty and E(x;θ) is the energy of the model q (x;θ), i.e., q (x;θ) = exp (−E(x;θ)) /Z(θ) where Z(θ) is the normalizing partition function. Analogously, we can define Eq. 5 over each mini-batch. This contrastive loss have been applied successfully in adversarial training, resulting in faster and improved stability of training, enhanced generator quality, and improved generator diversity (Zhao et al., 2016; Berthelot et al., 2017). As described in section 2.2 of (LeCun et al., 2006), the negative log-likelihood function, E(x;θ) = − log q (x;θ), constitute a valid energy which has been used in numerous energy-based models [e.g. (Bengio et al., 2003; Zhao et al., 2016; Berthelot et al., 2017)].
Theorem 1. The contrastive divergence CD (θ) in Equation 4 has the finite approximation L (θ) up to some constant k which is independent of θ.
Proof. Using the definition of KL divergence, we expand Equation 4: CD (θ) = − ∫ x p0 (x) log q (x;θ)dx+ ∫ x′ p1 (x ′) log q (x′;θ)dx′ + k (6)
where the two entropy terms ∫ x p0 (x) log p0 (x)dx and ∫ x p1 (x) log p1 (x)dx have been grouped in the constant k as they do not depend on the optimization parameters θ. Assume the Gibbs form for the model distribution,
q (x;θ) = e−E(x;θ)
Z(θ) , (7)
where E(x;θ) is the energy and Z(θ) = ∫ x e−E(x;θ)dx is the partition function. Then, Equation 6 becomes
CD (θ) = ∫ x p0 (x)E(x;θ)dx− ∫ x′ p1 (x ′)E(x;θ)dx′ (8)
− (∫
x
p0 (x) dx
) Z(θ) + (∫ x p1 (x) dx ) Z(θ) + k, (9)
where the partition function terms conveniently cancel out due to the normalization of p0 and p1. Therefore,
CD (θ) = Ep0(x) [E (x)]− Ep1(x) [E (x)] + k (10)
and we conclude that CD (θ) has the finite approximation L (θ) as defined in Equation 5, up to a constant k.

heading: 4.2 FRAMEWORK IMPLEMENTATION: CONTRASTIVE AUTOENCODER
text: Using the clean subset T , we implement step 2 of our framework by using an energy-based autoencoder (analogous to Zhao et al. (2016)). In order to ensure stable training and to prevent the second term of Equation 5 from diverging, we balance our mini-batch to have an equal number of positive and negative class samples. After training is complete, we process the original training data T̃ using the trained autoencoder. Specifically, we compute the energy using the resulting outputs: E (x;θ) = − log q (x;θ), which reduces to the reconstruction loss corresponding to the autoencoder (Goodfellow et al., 2016). For example, if the underlying distribution is assumed to be Gaussian then, we have E (x;θ) = ‖x − x̂(θ)‖2, where x̂(θ) is the output of
the autoencoder3. Whereas, if the underlying distribution is assumed to be Bernoulli, we obtain E (x;θ) = − [x log x̂(θ) + (1− x) log(1− x̂(θ))]. To execute our label correction protocol, we impose the following two conditions. (i) if E(x;θ) > Ē1− a for x ∈ T̃0, then change label of x. Here we denote T̃0 as the originals negative samples, Ē1 as the mean energy over the set of clean positive samples T1, and a is a tuneable hyperparameter that determines how aggressively we want to change 0→ 1. Analogously, we impose condition (ii) if E(x;θ) < Ē0 − b for x ∈ T̃1, then change label of x. The rationale is to modify samples where the original label ỹ contradicts the energy assignment. When one is not able to tune the threshold hyperparameters a and b, an empirical heuristic is to set them equal to the standard deviation about the means Ē1 and Ē0 respectively. See Appendix B details and pseudo-code.

heading: 5 EXPERIMENTS
text: We conduct experiments with simulated data and real-world data where three different type III noise models are studied: (i) Linear noise (perror ∼ αxi): the probability of an error occurring depends linearly on a feature (Table 1). (ii) Quadratic noise (perror ∼ αx2i ): the probability of an error occurring depends on the square of a feature. We control the amount of noise added with α and we select xi if it has sufficient variance to make the noise model distinct from random noise, i.e. 0 variance implies random noise (Table 2). (iii) Boundary noise: the probability of label error depends on the distance from the class boundary, which is determined using the noise-free data. We report the average class-weighted F1-score along with the standard error over 10 runs with random train-test (80:20) splits (Table 3).
UCI benchmark datasets: We train logistic regression on the corrected dataset resulting from the proposed algorithm. If a small clean dataset is not initially provided, then our results are labelled as AE (learned), otherwise they are labelled at AE (known) – see step 1 in Sec. 4. We compare to noise robust algorithms: NHERD Crammer & Lee (2010), PAM Frénay & Verleysen (2014), and ULE Natarajan et al. (2013). Additionally, we report upper and lower bounds by training logistic regression on the noisy data (LR-N) and on the clean data (LR-C). All algorithms are tested on noisefree data. Even without access to any clean labels (i.e., we learn which labels are likely clean), our framework generally outperforms the other algorithms in the presence of linear noise and quadratic noise. In general, learning which labels are noisy following the method in Ding et al. (2018) is not possible for arbitrary label noise processes: e.g., when the optimal discriminators of T̃ are very different than the optimal discriminators of T . For boundary noise, we show that using a small clean dataset T enables our methods to learn in the presence of boundary noise, where the other methods generally breakdown (Table 3). For a fair evaluation, the benchmark algorithms (which don’t have access to clean data) should be compared to AE (learned).
MNIST: Next, we compare our method with another state-of-the-art noise robust algorithm that relies on clean data, i.e., the loss weighting scheme of Ren et al. (2018). Both methods are given the same percentage of clean data for each noise setting. The task is to classify the distinguish “3” (class 0) vs. other digits (class 1). The noise process is input dependent as it changes 4, 5, 6 to class 0 depending on a specified noise rate (α). We demonstrate (Table 4) that our method generalizes better in the presence of type III noise, even when starting with only 1% of the data that is clean.
Arrhythmia We use the MIT-BIH Arrhythmia dataset Goldberger et al. (2000) to evaluate the proposed method’s ability to correct algorithmically assigned labels. Algorithmically-assigned labels (AALs) are prevalent in domains with abundant unlabeled data and high labelling costs. Common applications include web page annotation, but the value of this approach extends to automatic annotation of images and natural language. We employ the data preprocessing procedure described by Mondéjar-Guerra et al. (2019), where each arrhythmia is described by 59 features.
We divide the dataset into three parts: T1, T2 and T3. T1 and T2 serve as training sets and T3 is the test set. We train a classifier on T1 and subsequently use that classifier to generate AALs for T2. Thus, the predictions of the trained classifier become ỹ and the original expert labels remain y. As demonstrated in Table 1, the proposed technique achieves a higher F1 score than competing
3More precisely, E (x;θ) = ‖x− x̂(θ)‖2 up to an irrelevant scaling factor that we can drop for simplicity.
methods. The success of the model in this setting suggests its unique robustness to feature-dependent noise.

heading: 6 CONCLUSION
text: We have proposed an energy-based framework to correct mislabelled training instances. By minimizing a contrastive loss, the proposed method learns a representation that is valuable in relabeling noisy training sets. We evaluate the proposed model across six datasets and three noise models to demonstrate the method’s empirical value in correcting feature-dependent label noise. Furthermore, we demonstrate our method’s improvement upon existing work in making machine learning more robust to label noise processes.

heading: A EFFECT OF LABEL NOISE ON EMPIRICAL RISK
text: Here we show how label noise affects optimization of empirical risk. Recall that our task is to improve the labels of a training set in order to enable effective learning. In the following sections, we explore the Type I, Type II, and Type III noise. We first introduce the key variables.
We focus on binary classification, where the probability of class 0 is p and consequently, the probability of class 1 is (1− p):
p(y = 0) = p
p(y = 1) = 1− p
T represents the training set with correct labels, while T̃ represents the training set with label noise. In our setting, we are given T̃ and propose a method to transform T̃ into T . We will call D the true label distribution and P̃ the noisy label distribution.
T = { (Xi, Yi) for i = 1, 2, . . . , n }
T̃ = { (Xi, Ỹi) for i = 1, 2, . . . , n }
In the following calculations, we describe the difference in empirical risks over each training set and the subsequent effect on stochastic gradient descent. We refer to the empirical risk over the clean training set as R̂ [`, T ]. Similarly, we refer to the empirical risk over the corrupted training set as R̂ [ `, T̃ ] .
R̂ [`, T ] = 1 n n∑ i=1 ` (Φ(Xi,θ), Yi) ,
In order to explain the effects of label noise on stochastic gradient descent (SGD), we are primarily interested in the gradient of the empirical risk with respect to θ. Below, we break the empirical risk term into two class-dependent terms and introduce short-hand to represent each of these terms.
E(X,Y )∼D [ ∇θR̂[`, T ] ] = E(X,Y )∼D [ ∇θ 1
n n∑ i=1 ` (Φ(Xi,θ), Yi)
] (11)
= ∇θ 1
n n∑ i=1 E(X,Y )∼D [` (Φ(Xi,θ), Yi)] (12)
= ∇θ
[ 1
n n∑ i=1 ∫ p(xi, yi)` (Φ(xi,θ), yi) dxi dyi ] (13)
= ∇θ
[ 1
n n∑ i=1 ∫ p(xi|yi)p(yi)` (Φ(xi,θ), yi) dxi dyi ] (14)
= p(yi = 0)∇θ
[ 1
n n∑ i=1 ∫ p(xi|0)`0 (Φ(xi,θ)) dxi ] (15)
+ p(yi = 1)∇θ
[ 1
n n∑ i=1 ∫ p(xi|1)`1 (Φ(xi,θ)) dxi ] ,
We define shorthand based on Equation (5):
β0 = ∇θ
[ 1
n n∑ i=1 ∫ p(xi|0)`0 (Φ(xi,θ)) dxi ] (16)
β1 = ∇θ
[ 1
n n∑ i=1 ∫ p(xi|1)`1 (Φ(xi,θ)) dxi ] . (17)
Rewriting the original equation in terms of the above, we arrive at the following form for empirical risk:
E(X,Y )∼D [ ∇θR̂[`, T ] ] = p(yi = 0)β0 + p(yi = 1)β0 (18)
We revisit Equation 8 in the follow sections to interpret empirical risk under varying noise models. Note that β0 and β1 are the same in both the expected empirical risk with respect to the true label distribution (D) and the corrupted label distribution (P̃ ) for Type I and Type II noise. Additionally, we introduce shorthand for the true expectation of empirical risk (Etrue) and the expectation of empirical risk when labels are assigned at random (Erand).
Etrue = pβ0 + (1− p)β1 (19) Erand = .5β0 + .5β1 (20)
A.1 TYPE I: RANDOM NOISE
In the random noise scenario, each label has an equal probability of being flipped. We parameterize this noise by γ, resulting in :
γ = p(ỹi 6= yi) (21)
We may define both p(ỹi = 0) in terms of γ and p:
p(ỹi = 0) = p(ỹi = 0|yi = 0) + p(ỹi = 0|yi = 1) (22) p(ỹi = 0) = (1− γ)p+ γ(1− p) (23)
(24)
Likewise, we define p(ỹi = 1) as:
p(ỹi = 1) = p(ỹi = 1|yi = 0) + p(ỹi = 1|yi = 1) (25) p(ỹi = 1) = γp+ (1− γ)(1− p) (26)
Below, we substitute these expressions into Equation 8:
E(X,Ỹ )∼P̃ [ ∇θR̂[`, T̃ ] ] = p(ỹi = 0)β0 + p(ỹi = 1)β0 (27)
= ((1− γ) p+ γ − γp)β0 + ((1− γ) (1− p) + γp)β1 (28) = pβ0 − 2γpβ0 + γβ0 + β1 − γβ1 − pβ1 + 2γpβ1 (29) = pβ0 + β1 − pβ1 − 2γpβ0 − γβ1 + 2γpβ1 + γβ0 (30) = Etrue − 2γpβ0 − γβ1 + 2γpβ1 + γβ0 (31) = Etrue − 2γpβ0 − γβ1 + 2γpβ1 + γβ0 − γβ1 + γβ1 (32) = Etrue − 2γpβ0 − 2γβ1 + 2γpβ1 + γβ0 + γβ1 (33) = Etrue − 2γ (pβ0 + β1 − pβ1) + γβ1 + γβ0 (34) = (1− 2γ)Etrue + 2γErand (35)
A.2 TYPE II NOISE
Type II noise implies class-dependent label noise. Thus, we define γ0 and γ1, the class-dependent noise rates. In addition, we define γ∗ as the average class-dependent noise rate and as the absolute distance of γ0 and γ1 from γ∗. Without loss of generality, we assume γ0 > γ1.
γ0 = p(ỹi = 1|yi = 0) γ1 = p(ỹu = 0|yi = 1)
γ∗ = γ0 + γ1
2
= γ0 − γ1
2
We may redefine p(ỹi = 0) and p(ỹi = 1) using these terms:
p(ỹi = 0) = ((1− γ0) p+ γ1 (1− p)) (36) = ((1− γ∗ − ) p+ (γ∗ − ) (1− p)) (37) = (p− γ∗p− p+ γ∗ − γ∗p− + p) (38)
p(ỹi = 1) = ((1− γ1) (1− p) + γ0p) (39) = ((1− γ∗ + ) (1− p) + (γ∗ + ) p) (40) = (1− γ∗ + − p+ γ∗p− p+ γ∗p+ p) (41)
Plugging this into Equation 8,
E(X,Ỹ )∼P̃ [ ∇θR̂[`, T̃ ] ] = (p− γ∗p− p+ γ∗ − γ∗p− + p)β0 (42)
+ (1− γ∗ + − p+ γ∗p− p+ γ∗p+ p)β1 = (p− 2γ∗p+ γ∗ − )β0 (43) + (1− 2γ∗ + − p+ 2γ∗p+ γ∗)β1
Similar to our approach with Type I noise, we aim to rephrase this equation in terms of Etrue and Erand.
= (1− 2γ∗) pβ0 + (γ∗ − )β0 + (1− 2γ∗) (1− p)β1 + ( + γ∗)β1 (44) = (1− 2γ∗)Etrue + (γ∗ − )β0 + ( + γ∗)β1 (45) = (1− 2γ∗)Etrue + 2γ∗Erand + (β1 − β0) (46)
A.3 TYPE III NOISE
In this section, we analyze a specific case of type III noise where label corruption is restricted to a given region of the feature space. As above, we want to study the effect on learning by determining how the true gradient is modified in the presence of noise. We assume a scalar input space and define the feature dependent noise as follows:
p(ỹi|x) = { γ x ∈ [a, b] 0 x /∈ [a, b] } The noise model above asserts that label noise depends only on the feature space and is labelagnostic - thus, examples from both class 1 and class 0 with x ∈ [a, b] are equally likely to suffer from a label flip.
Revisiting
E(X,Ỹ )∼P̃ [ ∇θR̂[`, T̃ ] ] = ∇θ
[ 1
n n∑ i=1 ∫ p(ỹi|xi)p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ] ,
= ∇θ
[ 1
n n∑ i=1 ∫ b a p(ỹi|xi)p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ]
+ ∇θ
[ 1
n n∑ i=1 ∫ x/∈[a,b] p(yi|xi)p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ] .
Now we add and subtract the following term:
∇θ
[ 1
n n∑ i=1 ∫ b a p(yi|xi)p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ] (47)
In order to obtain:
E(X,Ỹ )∼P̃ [ ∇θR̂[`, T̃ ] ] = Etrue +∇θ
[ 1
n n∑ i=1 ∫ b a p(ỹi|xi)p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ]
− ∇θ
[ 1
n n∑ i=1 ∫ b a p(yi|xi)p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ]
= Etrue +∇θ
[ 1
n n∑ i=1 ∫ b a (p(ỹi|xi)− p(yi|xi)) p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ]
Where we have used the fact that:
Etrue = ∇θ
[ 1
n n∑ i=1 ∫ b a p(yi|xi)p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ]
+ ∇θ
[ 1
n n∑ i=1 ∫ x/∈[a,b] p(yi|xi)p(xi)` (Φ(xi,θ), ỹi) dxi dỹi ]

heading: B ALGORITHM PSEUDO-CODE
text: In this section, we include a more detailed form of the algorithms proposed in the paper.
Algorithm 1 Train energy-based autoencoder
Require: T̃ . full training data Require: T . training data with known labels Require: η . learning rate Require: Forward (x,θ) . autoencoder transformation that maps ∀x→ x̂ Require: E (x̂) . energy function, i.e. reconstruction loss Require: L (B,O;θ) . objective function as defined in eq. 5 Require: GetBalancedBatch (T ) . get mini-batch with an equal number
of instances from each class
1: for i in {1,2,. . . ,m} do . where m is total number of batches 2: Bi = {xj , yj} ← GetBalancedBatch (T ) 3: Oi = {x̂j} ← Forward (Bi,θi) 4: `i ← L (Bi,Oi;θi) . L (Bi,Oi;θi) is defined in Eq. 5 5: ∇θ (`i)← Backward (`i;θi) 6: θi+1 ← Step (θi, η,∇θ (`i)) 7: end for
8: Initialize: E = {} . empty dictionary that will store energies 9: for {xi, ỹi} in T̃ do 10: x̂i ← Forward (xi;θ?) . where θ? is the output of previous loop 11: ei ← E (x̂i) 12: E [i]← ei . E [i] is the value of E at index i 13: end for
Algorithm 2 Correct training data
Require: T̃ . full training data Require: T . training data with known labels Require: E . energies from algorithm 1 Require: E (x̂) . energy function, i.e. reconstruction loss Require: GetNegativeSamples (T ) . get all samples from class 0 Require: GetPositiveSamples (T ) . get all samples from class 1
1: T0 ← GetNegativeSamples (T ) 2: T1 ← GetPositiveSamples (T ) 3: Ē0 ← 1|T0| ∑ x∈T0 E (x) . get mean w.r.t class 0
4: Ē1 ← 1|T1| ∑ x∈T1 E (x) . get mean w.r.t class 1
5: σ0 ← [∑ x∈T0 (E(x;θ)−Ē0) 2 |T0|−1 ] 1 2
. get standard deviation w.r.t class 0
6: σ1 ← [∑ x∈T1 (E(x;θ)−Ē1) 2 |T1|−1 ] 1 2
. get standard deviation w.r.t class 1 7: T c ← T̃ T . i.e. T c = { (xi, yi) ∈ T̃ ‖ (xi, yi) /∈ T } 8: for {xi, yi} in T c do 9: ei ← E [i] . get energy corresponding to xi
10: if yi = 1 and ei < Ē0 + σ0 then 11: yi ← 0 12: else if yi = 0 and ei > Ē1 − σ0 then 13: yi ← 1 14: end if 15: end for

Review summaries:
This submission proposes an energy-based method to correct mislabelled examples. Intuitively, the authors claim that contradictions between energy and noisy labels can be used to identify label noise. To make the idea reliable, the authors propose to compute the energy by using learned (commonly shared) features. Experiment results look good. The presentation is also clear. My concerns are as follows: