Binary Classification with Instance and Label Dependent Label Noise

Within the framework of the traditional classification problem, it is generally assumed that both the training data and the test data are drawn from identical distributions. Nevertheless, there are several factors, including covariate shift, disturbances to the data, and changes in the domain of the application that can cause the distribution of testing data to be very different from that of training data. A particularly important example is label noise, where the labels in a classification problem may be corrupted with some nonzero probability. Various factors can contribute to the emergence of label noise, including human error during the annotation process, instances of ambiguous classification boundaries, and inconsistencies in data collection and processing. Also, with the increasing scale of data in recent years, researchers and practitioners are increasingly turning to cost-effective data collection methods, such as data mining on social media (Injadat et al., 2016) or web scraping (Schroff et al., 2010), rather than relying on human experts. These cost-effective approaches are more susceptible to the presence of label noise, which has contributed to the increased prevalence of this issue in recent years. Consequently, a critical question within the machine learning community is to understand the effects of label noise and when one may or may not be able to develop algorithms that are robust to the noise.

In this paper, we consider a binary classification problem with a feature space $\mathcal{X}\subset\mathbb{R}^{d}$ and a label space $\mathcal{Y}=\{-1,+1\}$. We adopt the label noise model using the label noise function $\rho_{y}(\mathbf{x})$, which quantifies the probability of flipping the label $y$ to -$y$ given the sample $(\mathbf{x},y)$. The simplest possible label noise model is the random classification noise (RCN) model (Angluin and Laird, 1988), in which the label noise function remains constant $\rho_{y}(\mathbf{x})=\rho$ for all $x\in\mathcal{X}$ and $y\in\mathcal{Y}$. The RCN model has been extensively studied in theory, and it is well established that certain loss functions, such as the 0-1 loss or squared loss, can learn an optimal classifier solely using noisy samples even when the noise rate $\rho$ is unknown (Manwani and Sastry, 2013; Ghosh et al., 2015).

The class-conditional noise (CCN) model is more complex than the RCN model, wherein the label noise function is a constant $\rho_{y}$ depending on each label $y\in\mathcal{Y}$ (Natarajan et al., 2013). Similarly to the RCN model, numerous theoretical works and methods have demonstrated that learning with the CCN is possible (Menon et al., 2015; Natarajan et al., 2013; Scott, 2015; Van Rooyen and Williamson, 2017; Reeve et al., 2019; Zhang et al., 2021). A common approach to tackle CCN is the loss correction method, which adjusts the loss function according to the estimated noise rate, ensuring the consistency of the estimator for clean samples. Some loss correction methods necessitate knowing the noise rates (Menon et al., 2015; Van Rooyen and Williamson, 2017; Patrini et al., 2017), while others estimate these rates under the assumption that anchor points exist (Scott et al., 2013; Scott, 2015; Ramaswamy et al., 2016; Liu and Tao, 2015; Reeve et al., 2019). An instance $\mathbf{x}$ is an anchor point for the label $y\in\mathcal{Y}$ if $\mathbb{P}(Y=y|\mathbf{X}=\mathbf{x})=1$ and it is useful in the sense that it allows us to learn the noise rates accurately. Moreover, Xia et al. (2019) proposed a noise rate estimator that does not require the anchor points. Recently, Liu and Guo (2020) introduced a peer loss function that allows learning with noisy samples without the need to estimate noise rates. Other approaches to handle CCN include sample selection method and label correction method, in which they aim to identify noisy samples, filter them out, or correct them to the accurate label (Bootkrajang and Kabán, 2012; Goldberger and Ben-Reuven, 2017; Malach and Shalev-Shwartz, 2017; Han et al., 2018; Jiang et al., 2018; Huang et al., 2019; Nguyen et al., 2019; Yu et al., 2019; Wei et al., 2020; Yi and Wu, 2019; Han et al., 2020; Park and Kwon, 2021). However, it is intuitive that the label noise in real-world data should be dependent on both the instance and the label rather than solely on the label. For example, a blurred image is more likely to be mislabeled compared to a clear version of the same image. Additionally, Chen et al. (2021) provided theoretical evidence that the CCN assumption does not hold in real-world datasets by introducing a CCN hypothesis testing method. Thus, this motivates us to examine a more general label noise model, instance and label dependent noise (ILN) model, in which the noise rate depends on both the instance and the label.

The purely instance-dependent noise (PIN) model, where the noise rate depends only on the instance and not the label, has been studied by Menon et al. (2018) as a special case of the ILN model. Menon et al. (2018) showed that the Bayes optimal classifiers for both the clean and noisy distributions are identical, indicating that learning with PIN is possible. However, in the ILN model, the problem becomes more challenging, as estimating the noise rate for each instance is generally difficult. There are some algorithms proposed to address learning under the ILN model (Cheng et al., 2020b; Xia et al., 2020; Cheng et al., 2020a; Zhu et al., 2021). Xia et al. (2020) attempted to address the ILN model by making a part dependence assumption, which assumes that instances are composed of parts and that these parts are subject to corruption. Cheng et al. (2020b) considered the bounded instance and label dependent (BILN) model, where the noise rate for each label is bounded above. They tried to learn an estimator using samples that are consistent with the Bayes optimal classifier and samples that have been cleaned by human experts. Berthon et al. (2021) considered the confidence-scored instance-dependent model, in which the confidence score information is provided along with the instance and the label. Although these methods provide us with heuristic ways to address the ILN, there has been limited theoretical work on the ILN model. For example, each of these methods requires access to clean samples or relies on specific strong assumptions. Nevertheless, the question of whether learning with ILN is possible without these conditions or access to clean samples has not been adequately addressed. Furthermore, while much work has been done to modify the loss function to enable empirical risk minimization (ERM) to learn from noisy samples, it is often overlooked how the label noise might degrade the performance of ERM. Perhaps the work closest to these lines of questions and to this paper is the work of Lee and Foygel Barber (2022). They studied the performance of ERM in the presence of RCN. However, their work is restricted to the RCN model with Lipschitz loss functions and linear hypothesis classes, whereas this study explores more comprehensive settings: instance and label dependent noise, as well as a broader range of hypothesis classes and loss functions.

In this paper, we provide a novel theoretical analysis of the instance and label dependent (ILN) model. We consider loss functions that satisfy a mild boundedness assumption and ensure that standard generalization guarantees hold. These conditions do not require the loss function to be Lipschitz or convex, and even 0-1 loss complies with these requirements. Moreover, other general loss functions such as logistic loss or hinge loss, meet these conditions under certain settings. We start by studying the performance difference between the clean estimator and the noisy estimator, both obtained through empirical risk minimization (ERM) using clean samples and noisy samples, respectively. (Herein, we refer to a clean sample as a sample from the underlying distribution, and a noisy sample as one that has passed through the ILN model). We evaluate the performance of each estimator with respect to the risk under the clean (true) distribution and provide an upper bound for the difference between those risks. We identify a new source of irreducible error, namely a constant term proportional to the amount of label noise present, in the upper bound. Next, we show that this irreducible error term cannot be fully removed in the ILN model by developing a minimax lower bound of the 0-1 risk. This suggests that to learn an effective predictor under the ILN model, we may need access to clean samples (Cheng et al., 2020b) or require some additional assumptions (Xia et al., 2020) beyond those made in the CCN model.

In this section, we present our formal problem setting and assumptions of the ILN model. Let $\mathcal{X}\subset\mathbb{R}^{d}$ be the feature space and $\mathcal{Y}=\{-1,+1\}$ be the label space. We assume that the random variables $(\mathbf{X},Y,\tilde{Y})\in\mathcal{X}\times\mathcal{Y}\times\mathcal{Y}$ are jointly distributed with unknown distribution $D$, where $\mathbf{X}$ denotes the feature vector, $Y$ is the true label, and $\tilde{Y}$ is the noisy label. We use $P_{\mathbf{X}}$ to denote the marginal distribution of $D$ for $\mathbf{X}$, while $P$ and $\tilde{P}$ are used to indicate the marginal distribution of $D$ for $(\mathbf{X},Y)$ and the marginal distribution of $D$ for $(\mathbf{X},\tilde{Y})$, respectively. We refer to $P$ as a clean distribution as it is related to the true label $Y$ and refer to $\tilde{P}$ as a noisy distribution. We use $S_{n}$ and $\tilde{S}_{n}$ to denote $n$ i.i.d. samples drawn from $P$ and $\tilde{P}$, respectively. Furthermore, we use $P_{n}$ and $\tilde{P}_{n}$ to represent the corresponding product distribution associated with the samples $S_{n}$ and $\tilde{S}_{n}$. Given the noise functions $\rho_{y}(\cdot):\mathcal{X}\rightarrow[0,1)$ for $y\in\{-1,+1\}$, a sample of $(\mathbf{X},Y,\tilde{Y})$ is generated by the following procedure:

Here $\eta(\mathbf{x}):=\mathbb{P}(Y=1|\mathbf{X}=\mathbf{x})$, denotes the conditional probability of $Y=1$ given $\mathbf{X}=\mathbf{x}$ (i.e., the regression function), while $\rho_{y}(\mathbf{x})$ indicates the probabilty of the true label $y$ being flipped for instance $(\mathbf{x},y).$ Both $\eta(\cdot)$ and $\rho_{y}(\cdot)$ for $y\in\{\-1,+1\}$ are unknown. For simplicity, we use $\rho_{+}(\mathbf{x})$ and $\rho_{-}(\mathbf{x})$ to denote $\rho_{+1}(\mathbf{x})$ and $\rho_{-1}(\mathbf{x})$, respectively. As discussed in Section 1, various noise models have been considered in the literature and each of these models can be formulated using the noise functions $\rho_{y}(\mathbf{x})$. Precisely, the RCN model is a special case where the noise function is given by $\rho_{+}(\mathbf{x})=\rho_{-}(\mathbf{x})=\rho\in[0,1)$ for all $\mathbf{x}\in\mathcal{X}$. The CCN model generalizes the RCN model, with constant noise levels $\rho_{+}\in[0,1)$ and $\rho_{-}\in[0,1)$ such that $\rho_{+}(\mathbf{x})=\rho_{+}$ and $\rho_{-}(\mathbf{x})=\rho_{-}$ for all $\mathbf{x}\in\mathcal{X}$. For the ILN model, there are no specific constraints on the noise functions, covering the more general scenarios. In this study, we make the following mild assumption for the ILN model.

In this case, the constant $\rho$ represents a uniform bound on the sum of the two noise functions for all $x\in\mathcal{X}$. The objective in a binary classification problem with label noise is to determine a function $f:\mathcal{X}\rightarrow\mathbb{R}$ such that $\text{sgn}(f(\mathbf{x}))$ best predicts the true label $y$, for a given input $(\mathbf{x},y)$, where $\text{sgn}(\cdot)$ represents the sign function. However, we only observe a sequence of noisy pairs $\tilde{S}_{n}=\{\mathbf{x}_{i},\tilde{y}_{i}\}_{i=1}^{n}$, and the values of the true labels $\{y_{i}\}_{i=1}^{n}$ are unknown. As is standard in binary classification, a fundamental performance metric of the function $f(\cdot)$ is the 0-1 risk

where $\mathds{1}\{\cdot\}$ denotes the standard 0-1 indicator function. The function $f^{*}(\mathbf{x}):=\eta(\mathbf{x})-\frac{1}{2}$ associated with the Bayes optimal classifier minimizes the 0-1 risk, and $\mathcal{R}^{0/1}(f^{*})$ indicates the minimum misclassification rate under distribution $P$. Since the regression function $\eta(\cdot)$ is unknown, the learner must identify a function $f:\mathcal{X}\rightarrow\mathbb{R}$ that approximates $\eta(\cdot)$ based on the observed samples. Additionally, the distribution $P$ remains unknown and therefore the 0-1 risk can not be evaluated. As an alternative, the learner generally seeks a decision rule that (approximately) minimizes the empirical 0-1 risk

In the context of the noisy label setting where the true labels $\{y_{i}\}_{i=1}^{n}$ are unobserved, the learner may in fact instead (approximately) minimize the empirical 0-1 risk with noisy labels

The non-convex and discontinuous nature of the 0-1 loss makes the above minimization challenging, and the classical way to circumvent this issue is to consider an alternative surrogate convex loss function $\ell(f(\mathbf{x}),y)$ (Bartlett et al., 2006). The risk associated with the surrogate loss function $\ell(f(\mathbf{x}),y)$ is referred as $\ell$-risk of function $f$, and is denoted by

where $\mathcal{R}(f)$ denotes the $\ell$-risk under the clean distribution and $\tilde{\mathcal{R}}(f)$ denotes the $\ell$-risk under the noisy distribution. According to the above notation, we define $\mathcal{R}_{n}(f)$ and $\tilde{\mathcal{R}}_{n}(f)$ as the empirical $\ell$-risk of a function $f$ with clean samples and noisy samples, respectively. Generally, we select the function $f$ from a predefined class of functions $\mathcal{F}$, which represents the hypothesis class in our modeling framework. We denote the empirical risk minimizer with clean samples as:

and for noisy samples, we have:

For clarity, we call $f_{n}$ a clean estimator and $\tilde{f}_{n}$ a noisy estimator. Note that the loss function remains unchanged when obtaining the noisy estimator $\tilde{f}_{n}$, which distinguishes it from the loss correction or the label correction methods discussed in Section 1. Although empirical risk minimization (ERM) is a fundamental technique in machine learning and many works focused on modifying the loss function to learn with ERM using noisy samples, the question of how ERM degrades in the presence of label noise has been previously overlooked. Therefore, one of our interests is to study the performance difference between the noisy estimator and the clean estimator.

In this section, we study the performance difference between the clean estimator $f_{n}$ and the noisy estimator $\tilde{f}_{n}$, each of which are obtained through empirical risk minimization (ERM) using clean samples and noisy samples, respectively. In particular, the performance difference can be expressed as:

It is important to emphasize that we do not apply any modification to the loss function $\ell(\cdot)$ to address the issue of noisy samples. We consider loss functions that adhere to the following mild assumption.

Assumption 3.1 states that the difference between the loss of input $(\mathbf{x},1)$ and input $(\mathbf{x},-1)$ is uniformly bounded over $\mathcal{X}$ and $\mathcal{F}$. This assumption is typical in the problem of binary classification. For example, the 0-1 loss satisfies (4) with $C=1$ for any $\mathcal{F}$ and $\mathcal{X}$. In addition, other loss functions, such as squared loss and logistic loss, satisfy (4) for specific $\mathcal{X}$ and $\mathcal{F}$. We introduce some relevant examples in section 3.2. Furthermore, we make a natural assumption about the generalization bound of the empirical risk minimization (ERM) procedure.

Note that the function $G_{\delta}$ in Assumption 3.2 may depend on $\mathcal{F}$, $\mathcal{X}$, and the loss function $\ell$, but not the distribution $P$. In particular, Assumption 3.2 also implies

for the noisy distribution $\tilde{P}$ as well. Assumption 3.2 is valid in various settings, such as a linear hypothesis class or a Reproducing Kernel Hilbert Space (RKHS) with a bounded kernel. Also, the function $G_{\delta}$ is closely connected to the complexity of the hypothesis class $\mathcal{F}$, which can be quantified through measures such as the VC dimension, Rademacher complexity, and $\epsilon$-covering number (Wainwright, 2019). The details are discussed in Section 3.2.

In this section, we study the minimax lower bound for 0-1 loss for binary classification within the ILN model, to see whether the irreducible error in Equation (8) can be removed. We would like to show that learning with ILN is not possible under assumptions typically made in the CCN model. These assumptions strengthen our lower bound results, as they make the clean distribution $P$ more favorable for learning. We start by introducing two widely adopted assumptions in the context of binary classification with CCN. These two assumptions only apply to the clean distribution $P$.

The margin assumption is widely used in the problem of binary classification (Audibert and Tsybakov, 2007; Mammen and Tsybakov, 1999; Pillaud-Vivien et al., 2018; Reeve et al., 2019). In binary classification, the easiest instance $\mathbf{x}$ is where the label is deterministic $(\eta(\mathbf{x})=0\text{ or }1)$, while the hardest instance $\mathbf{x}$ is where the conditional probability is on the decision boundary ($\eta(\mathbf{x})=\frac{1}{2}$). Thus, the difficulty of the problem is determined by the quantity of $\mathbf{x}\in\mathcal{X}$ where $\eta(\mathbf{x})$ is close to $\frac{1}{2}$. The margin assumption implies that we can control this quantity with the parameter $(\alpha,C_{\alpha})$ and also indicates that not all of the mass of $\mathbf{x}\in\mathcal{X}$ is concentrated around $\eta(\mathbf{x})=\frac{1}{2}$.

The anchor point assumption implies that for each label there exists at least one instance where the label is deterministic. The anchor point allows us to estimate the unknown noise rate in the classification problem with CCN (Scott, 2015; Reeve et al., 2019). With two assumptions together, many theoretical works showed that they were able to learn the optimal classifier only with noisy samples when the noise is instance-independent but label-dependent. However, the following theorem implies that this is not possible with instance- and label-dependent label noise.

Theorem 2 suggests that even when provided with a sufficiently large number of noisy samples, there is no estimator capable of learning the optimal function $f^{*}$. This occurs because the noise rate varies for each instance, making the presence of anchor points insufficient to accurately estimate these noise rates. Interestingly, when combined with Theorem 1, Theorem 2 suggests that empirical risk minimization achieves the optimal rate of excess risk, which is proportional to the noise level $\rho$. Also, this implies that no other sophisticated methods such as loss correction or label correction are necessary without any additional assumptions.

This paper provides a theoretical analysis of instance and label dependent noise model. We derived an upper bound for the excess risk of the empirical risk minimizer when using noisy samples. Furthermore, we showed that the minimax risk of the 0-1 loss is lower bounded by a constant that is proportional to the noise level. These results imply that the empirical risk minimizer achieves the optimal excess risk bound in terms of the noise level, despite its simplicity compared with other noise-tolerant methods. Furthermore, the lower bound result prompts us to consider what additional assumptions are required to make learning with ILN possible and some justification for using clean samples, as learning solely with noisy samples is not possible. These theoretical findings validate numerous works on the ILN model, which assumed stronger assumptions and used human experts to clean noisy samples.