{'fraction_non_alphanumeric': 0.04794104239477283, 'fraction_numerical': 0.011890290229448413, 'mean_word_length': 4.37354562155542, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
CCMN: A General Framework for Learning with Class-Conditional Multi-Label Noise

Class-conditional noise commonly exists in machine learning tasks, where the class label is corrupted with a probability depending on its ground-truth. Many research efforts have been made to improve the model robustness against the class-conditional noise. However, they typically focus on the single label case by assuming that only one label is corrupted. In real applications, an instance is usually associated with multiple labels, which could be corrupted simultaneously with their respective conditional probabilities. In this paper, we formalize this problem as a general framework of learning with Class-Conditional Multi-label Noise (CCMN for short). We establish two unbiased estimators with error bounds for solving the CCMN problems, and further prove that they are consistent with commonly used multi-label loss functions. Finally, a new method for partial multi-label learning is implemented with unbiased estimator under the CCMN framework. Empirical studies on multiple datasets and various evaluation metrics validate the effectiveness of the proposed method.


Introduction
In ordinary supervised classification problems, a common assumption is that the class labels of training data are always correct. However, in practice, the assumption hardly holds since the training examples are usually corrupted due to unavoidable reasons, such as measurement error, subjective labeling bias or human labeling error. Learning in presence of label noise has been a problem of theoretical as well as practical interest in machine learning communities [8]. In various applications, such as the image annotation [33] and text classification [15], many successful methods have been applied to learning with label noise.
In general, to deal with noise-corrupted data, it is crucial to discover the causes of label noise. A natural and simple formulation of label noise is that the labels are corrupted by a random noise process [3], which can be described by the random classification noise (RCN) framework [1]. RCN framework assumes that each label is flipped independently with a specific probability ρ ∈ [0, 1 2 ). Despite the great impact that RCN framework has made, it is too simple to deal with practical tasks, where the cause of label noise may not follow a random process. In order to deal with such problems, in [29,24], authors propose a class-conditional random label noise (CCN) framework, where the probability of a label flipped depends on its true label. Unfortunately, CCN framework only considers single label case and fail to deal with multiple noisy labels, where multiple labels assigned to one instance may be corrupted simultaneously.
In this paper, we extend CCN to a more general framework of Class Conditional Multi-label Noise (CCMN) to learn with multi-class and multi-label classification tasks. In CCMN framework, each instance is associated with multiple labels and each of class labels may be flipped with a probability ρ j +1 or ρ j −1 , which depends on its true label y j ∈ {+1, −1}. It is worth noting that a great deal of real-world applications in weak-supervised setting [44] can be included into the framework, such as learning from partial-labeled data [6,34] or learning with missing labels [30], which we will discuss detailedly in following content. To the best of our knowledge, general theoretical results in this setting have not been developed before.
To tackle corrupted data with class-conditional multiple noisy labels, we derive a modified loss function for learning a multi-label classifier with risk minimization. Theoretically, we show that the empirical risk minimization with modified loss functions can be in an unbiased fashion from independent and dependent perspectives. We then provide the estimation error bound for the two unbiased estimator and further show that learning with class-conditional multiple noisy labels can be multi-label consistent to two commonly used losses, i.e., hamming loss and ranking loss, respectively. Finally, CCMN can be regarded as a general framework of various weakly-supervised learning scenarios, such as partial label learning [6], partial multilabel learning [34] and weak label learning [30]. Among them, partial multi-label learning (PML) is a recently proposed weakly-supervised learning scenario. We further propose a new approach for partial multi-label learning with unbiased estimator. Comprehensive empirical studies demonstrate the effectiveness of the proposed methods.
Our main contributions are summarized as follows: • A general framework of learning from class-conditional multi-label noise is proposed. Varied weaklysupervised learning scenarios can be cast under CCMN framework.
• We propose two unbiased estimators for solving CCMN problems in independent and dependent fashion. These two estimators are proven to be multi-label consistent to hamming loss and ranking loss, respectively.
• A novel approach for Partial Multi-label Learning with unbiased estimator (uPML) is proposed under the CCMN framework.

Related Works
There are a great deal of previous works aiming to learn a robust classification model in presence of label noise. Most of these methods only consider single label case and cannot tackle class-conditional multi-label noise.
There has been a long line of studies in machine learning community on random label noise. The earliest work by Angluin and Laird [1] first propose the random classification noise (RCN) model. In [9], authors propose a boosting-based method and empirically show its robustness to random label noise. A theoretical analysis proposed in [21] proves that any method based on convex surrogate loss is inherently ill-suited to random label noise. In [3], authors consider random and adversarial label noise and try to utilize a robust SVM to deal with label noise.
The first attempt to tackle class-conditional label noise is in [29] where authors propose a variant of SVM to deal with noisy labels with theoretical guarantee. In [24], authors propose unbiased estimators to solve class-conditional label noise in binary classification setting. Based on the assumption that the classconditional distributions may overlap, a method called mixture proportion estimation is proposed in [28] to estimate the maximal proportion of one distribution that is present in another. Furthermore, authors extend the method into multi-class setting in [4].
In this paper, we also employ the CCMN framework to solve partial multi-label learning problems. In order to deal with partial-labeled data, the most commonly used strategy is disambiguation [6,12], which recovers ground-truth labeling information for candidate labels. Some methods perform disambiguation strategy by estimating a confidence for each candidate label [34,40]. Other methods utilize decomposition scheme [20] or adversarial training [37]. However, aforementioned methods never consider the generation process of noisy labels in candidate label set, which is a essential information for solving PML problems. In [35], authors first consider modeling the relationship between noisy labels and feature representation. Nevertheless, all of these methods failed to prove the consistency of the proposed method.

Formulation of CCMN
Let x ∈ X be a feature vector and y ∈ Y be its corresponding label vector, where X ⊂ R d is the feature space and Y ⊂ {−1, 1} q is the target space with q possible class labels. For notational convenience, the label y j can be denoted by its index j. In the setting, y j = 1 indicates the j-th label is a true label for instance x; y j = −1, otherwise. In this paper, we focus on the multi-label learning problem, where each instance may be assigned with more than one label, i.e., q j=1 I(y j = 1) ≥ 1 holds, where I is the indicator function. Let S = {(x 1 , y 1 ), ..., (x n , y n )} be the given training data set, drawn i.i.d. according to the true distribution D. We also use [q] to denote the integer set {1, ..., q}.
In this paper, for instance x, its corresponding label y can be corrupted and may be flipped intoỹ following a class-conditional multi-label noise model as follows: where ρ j +1 and ρ j −1 are noise rates for each class label and are assumed to be known to the learner. After injecting random noise into original samples S, the observed data set S ρ = {(x 1 ,ỹ 1 ), ..., (x n ,ỹ n )} are drawn i.i.d., according to distribution D ρ . Our goal is to learn a prediction function h : X → Y can accurately predict labels for any unseen instance. In general, it is not easy to learn h directly, and alternatively, one usually learns a real-valued decision function f : X → R K . Note that, for each instance x, even though its final prediction depends on h(x), we also call f itself the classifier. As mentioned before, CCMN can be used to solve multi-class and multi-label learning problems. In this paper, we focus on the multi-label classification task without loss of generality.
In general, CCMN framework has implications in varied real-world applications. In the following content, we discuss on two popular weakly-supervised learning scenarios, i.e., partial multi-label learning and weak label learning, which can be regarded as special cases of CCMN framework.
In PML problems, each instance is associated with a candidate label set Y c , which contains multiple relevant labels and some other noisy labels. One intuitive strategy to solve the task is that treat all labels in Y c as relevant labels and transform Y c intoỸ . Here, we useỸ , since there may exist irrelevant labels inỸ . Then, a new training set is obtained, where each instance is associated with the label setỸ . Besides relevant labels,Ỹ is also injected into some irrelevant labels, which can be regarded as class-conditional multi-label noise, i.e., irrelevant labels are flipped into relevant labels with ρ j −1 > 0 while ρ j +1 = 0.
In weak label learning, also known as learning with missing label, relevant labels of each instance are partially known. Specifically, each instance is associated with a label set Y +1 whileỸ −1 is the irrelevant label set. Here, we useỸ −1 since there may exist missing labels inỸ −1 , i.e., relevant labels are missed. Similarly, one can treat all labels inỸ −1 as irrelevant labels. Besides irrelevant labels,Ỹ −1 is also injected into some relevant labels which can be regarded as class-conditional multi-label noise with ρ j +1 > 0 while ρ j −1 = 0.

Learning with CCMN
In this section, we first provide some necessary preliminaries, and then derive two CCMN solvers in independent and dependent cases. In the independent case, we solve each binary classification task of the CCMN problem independently while in the dependent case, we solve the CCMN problem by considering label correlations.

Preliminaries
To derive our results for solving CCMN problems, we introduce some notations and the property of multilabel consistency.
There are many multi-label loss functions (also called evaluation metrics), such as hamming loss, ranking loss and average precision [41], etc. In this paper, we focus on two well known loss functions, i.e., hamming loss and ranking loss, and leave the discussion on other loss functions in the future work.
The hamming loss considers how many instance-label pairs are misclassified. Given the decision function f and prediction function F , the hamming loss can be defined by: whereŷ = F (f (x)) = (ŷ 1 , ...,ŷ q ). The ranking loss considers label pairs that are ordered reversely for an instance. Given a real-value decision function f = (f 1 , f 2 , ..., f q ), the ranking loss can be defined by: L r (f , y) = 1≤j<k≤q I(y j < y k )ℓ(j, k) + I(y j > y k )ℓ(k, j) where The risk of f with respective to loss L is given by R(f ) = E (x,y)∼D [L(f (x), y)] and the minimal risk (also called the Bayes risk) can be defined by R * = inf f R(f ). For an instance x, the conditional risk of f can be defined as where p y = (Pr(y|x)) y∈Y is a vector of conditional probability over y ∈ Y. Note that the above mentioned two loss functions are non-convex and computationally NP-hard, which makes the corresponding optimization problems hard to solve. In practice, a feasible solution is to consider alternatively a surrogate loss function L which can be optimized efficiently. The L-risk and minimal L-risk can be defined as Furthermore, we define the conditional L-risk of f and the conditional Bayes L-risk The definition of multi-label consistency can be formulated as follows. Definition 1.
[10] Given a below-bounded surrogate loss L, where L(·, y) is continuous for every y ∈ Y, L is said to be multi-label consistent w.r.t. the loss L if it holds, for every p, that Based on the definition, the following theorem can be further established.
The surrogate loss L is multi-label consistent w.r.t. the loss L if and only if it holds for The theorem tells us that the multi-label consistency is a necessary and sufficient condition for the convergence of L-risk to the Bayes L-risk, implying R(f ) → R * . Our goal is to learn a good classification model with the modified loss functionL(f (x),ỹ) from noise-corrupted data by minimizing empiricalL-risk: where F is a function class.

Independent Case
In order to solve multi-label learning problems, the most straightforward method is to decompose the task into q independent binary classification problems [41], where the goal is to learn q functions, f = (f 1 , f 2 , ..., f q ). However, as mentioned before, it is difficult to directly optimize the hamming loss due to its non-convexity. Alternatively, we consider the following surrogate loss where φ is a convex loss function. The common choices are least square loss φ(t) = (1 − t) 2 and hinge loss The modified loss function under class-conditional multi-label noise in independent case can be defined as follows:L Here, κ j = We extend the results in [24] to have the following lemma, which shows the unbiasedness of the estimator defined by Eq.(4).
Let σ = {σ 1 , ..., σ n } be n Rademacher variables with σ i independently uniform random variable taking value in {−1, +1}. Then, the Rademacher complexity with respective to function class F and unbiased estimatorL can be formulated as follows: Accordingly, the performance guarantee for the unbiased estimator in independent case can be derived as following theorems.
Then, for the loss function φ(·) bounded by Θ, with probability at least 1 − δ, we have wheref is trained by minimizing RL h (f ) and K ρ is the Lipschitz constant ofL h . Theorem 3. If φ is convex function with φ ′ (0) < 0, then the modified surrogate lossL h defined by Eq.(4) is consistent w.r.t hamming loss, i.e., there exists a non-negative concave function ξ with ξ(0) = 0, such that As shown in Theorem 2, the generalization error is dependent to the noise rates ρ −1 and ρ +1 . It is intuitive that smaller noise rates lead to a better generalization performance owing to a smaller µ. By combining Theorem 2 with Theorem 3, we obtain a performance guarantee for learning from class-conditional multiple noisy labels with respective to hamming loss, that is as n → ∞, we have

Dependent Case
In multi-label learning problems, a common assumption is that there exist label correlations among labels [26,39]. Therefore, it is fundamental to learning with class-conditional multi-label noise in a dependent fashion. The ranking loss considers the second-order label correlation and its surrogate loss is commonly defined as . Then, the modified loss function under class-conditional multi-label noise in the dependent case can be defined asL whereφ((f j , f k ), (y j , y k )) can be abbreviated byφ(j, k), is a constant. The unbiasedness of the estimator defined by Eq. (6) can be shown as following lemma.
Accordingly, the performance guarantee for the unbiased estimator in the dependent case can be derived as following theorems.
Then, for the loss function φ(·) bounded by Θ, with probability at least 1 − δ, we have wheref is trained by minimizing RL r (f ) and K ρ is the Lipschitz constant ofL r . Theorem 5. If φ is a differential and non-increasing function with φ ′ (0) < 0 and φ(t) + φ(−t) = 2φ(0), then the modified surrogate lossL r defined by Eq.(6) is consistent w.r.t ranking loss, i.e., there exists a non-negative concave function ξ with ξ(0) = 0, such that From Theorem 2, it can be observed that besides the noise rates ρ −1 and ρ +1 , the generalization error is also dependent to the difference between noise rates, i.e., |ρ −1 − ρ +1 |. Generally, a smaller difference also leads to a better generalization performance owing to a smaller µ. By combining Theorem 2 with Theorem 3, we obtain a performance guarantee for learning from class-conditional multiple noisy labels with respective to ranking loss, that is as n → ∞, we have R Lr (f n ) → R * Lr , then R Lr (f n ) → R * Lr . Testing Phase. Regarding the classifierf trained by minimizing the loss functionL h or L h , for each testing instance x t , we use the sgn(f j (x t )) to predict its labels, where sgn(a) is a function which outputs +1 if a >= 0; −1, otherwise.
However, regarding classifier f trained by minimizing the loss functionL r or L r , it is unreasonable to use 0 as a threshold directly. Instead, to perform predictions, in training phase, we introduce a dummy label y 0 = 0 for each instance, and then, in testing phase, the output of the classifier for label y 0 is used as the threshold to decide the label assignment for each instance.
Specifically, for instance x, suppose that its corresponding label vector can be represented by y = (y 0 , y 1 , ..., y q ), where y 0 is indexed by 0. In the training phase, the cumulative lossL 0 with respective to y 0 can be written as follows:L where f j0 (x) = f j (x) − f 0 (x) and y j0 = y j − y 0 . Note that y j0 = y j , since we have y 0 = 0. In the situation, the formulation of lossL 0 is the same as Eq.(4) and can be solved efficiently.

Partial Multi-Label Learning with CCMN
In the section, from perspective of CCMN framework, we propose a new approach for partial multi-label learning with unbiased estimator (uPML for short). In such case, ∀j ∈ [q], Pr(ỹ j = +1|y j = −1) = ρ j , Pr(ỹ j = −1|y j = +1) = 0 holds. Here, we omit the subscript of ρ j for notational simplicity. Based on the results in Section 4, for the independent case, the objective function of uPMLL PML h can be defined as follows: where,φ For the dependent case, the objective function of uPMLL PML r can be defined as follows: where,φ We derive the generalization error bound for the proposed uPML method, which is the special case of Theorem 2 and 4. Corollary 1. For the least square loss φ(t) = (1 − t) 2 , with probability at least 1 − δ, we have where ρ min = min j ρ j andf is trained by minimizing RLPML h (f ), and

Experiment
The experiments for CCMN data are firstly reported, followed by the experiments for PML data.

Study on CCMN Data
We perform experiments on 8 benchmark data sets 1 which spanned a broad of applications: scene and mirflickr for image annotation, music emotion and music style for music recognition, yeast for protein function prediction as well as slashdot, enron and tmc for text categorization. For each data set, we randomly sample 50% data for training and 30% data for testing while the rest 20% data is used for validation. To inject label noise into training examples, each class label is flipped according to noise rate ρ j −1 and ρ j +1 randomly sampled from {0.1, 0.2, 0.3, 0.4, 0.5}. We repeat experiments 5 times with different combinations of noise rates and report the averaging results.
We compare the performance of the proposed method with their baselines. Specifically, two variants of the proposed method, i.e.,L h (Eq.(4)) andL r (Eq. (6)) are compared with their baselines, i.e., L h (Eq.(3)) and L r (Eq. (5)). ForL h and L h , the surrogate loss function φ is defined as the least square loss and hinge loss; ForL r and L r , besides the least square loss and hinge loss, we also adopt Sigmoid loss, since it has been proved as a consistent surrogate loss with respective to ranking loss [10]. For all methods, we use a linear model and a three-layer MLP with 128 hidden neural units as the based model. We use Adam [16] as the optimizer for 200 epochs and learning rate is chosen from {5e-2,5e-3,5e-4}. The ℓ 2 -regularization term is added with the parameter of 1e-4. The testing performance of the model is reported with the best validation result out of all iterations. We conduct all experiments with Pytorch [25].
As mentioned before, there are different criteria for evaluating the performance of multi-label learning. In our experiments, we employ three commonly used criteria including hamming loss, ranking loss and average precision. More details can be found in [41]. Table 1 and Table 2 report comparison results of the proposed methods between baseline methods using linear and MLP models, respectively. For each data set, paired t-test based on 5 repeats (at 0.05 significance level) is conducted to show weather the proposed unbiased estimator is significantly different from the comparing methods. From the results, it is obvious that the proposed method outperforms their corresponding baselines with significant superiority in almost all cases, which validates the effectiveness of the proposed method. The performance ofL r is generally superior toL h , which validates the label correlation is beneficial for learning with class-conditional multi-label noise.

Study on PML Data
To validate the effectiveness of the proposed uPML method, we perform experiments on totally 8 data sets, including 3 real-world PML datasets, music style, music emotion and mirflickr as well as 5 multi-label dataets, yeast, enron, scene, slashdot and tmc. Regarding the multi-label datasets, for each instance, the negative label is flipped according to noise rate ρ randomly sampled from {0.1, 0.2, 0.3, 0.4, 0.5, 0.6}. We repeat experiments 5 times with different noise rate and report the averaging results. We compare with five state-of-art PML algorithms: PML-NI [35], PARTICLE (including two implementations: PAR-VLS and PAR-MAP) [40], PML-LRS [20] and fPML [38]. To make a fair comparison, we use a linear classifier as the base model for uPML. We use Adam [16] as the optimizer for 200 epochs and the learning rate is chosen from {0.05,0.005,0.0005}. The ℓ 2 -regularization term is added with the parameter of 1e-4. The testing performance of the model is reported with the best validation result out of all iterations. For the other comparing methods, parameters are determined by the performance on validation set if no default value given in their literature. Table 3 reports the comparison result of two variants of the proposed uPML method against comparing PML methods. For each data set, pair t-test based on five repeats (at 0.05 significance level) is conducted to show weather the proposed unbiased estimator is significantly different from the comparing methods. The proposed uPML method significantly outperforms the comparing PML methods in almost all cases except for the case on music style, where PMLNI is significantly better than uPML in terms of average precision.
In general, uPML withL r is better than uPML withL h due to the label correlation is considered for the former one. Theses results convincingly demonstrate the effectiveness of the proposed method.

Conclusion
In this paper, we study the problem of multi-label classification with class-conditional multiple noisy labels, where multiple class labels assigned to each instance may be corrupted simultaneously with class-conditional probabilities. From the perspective of the unbiased estimator, we derive efficient methods for solving CCMN problems with theoretical guarantee. Generally, we prove that learning from class-conditional multiple noisy labels with the proposed unbiased estimators is consistent with respective to hamming loss and ranking loss. Furthermore, we propose a novel method called uPML for solving PML problems, which can be regarded as a special case of CCMN framework. Empirical studies on multiple data sets validate the effectiveness of the proposed method. In the future, we will study CCMN with more loss functions.

B Proof for Theorem 2
Proof. The proof is mainly composed of the following two lemmas.
Lemma 3. Let Rn(L h • F) be the Rademacher complexity with respective to the unbiased estimatorL h and function class F over Sρ of n training points drawn from Dρ, which can be defined as Then, where Kρ is the Lipschitz constant ofL h .
Without loss of generality, assume that µ = maxj where p + j = y:y j =+1 py and p − j = y:y j =−1 py. This yields minimizing W (p, f ) is equivalent to minimizing W (p, f ). Accordingly, we have where Wj(p + j , fj) = p + j φ(fj) + p − j φ(−fj). Based on the consistency of binary classification setting proposed in [2,42], it is easy to prove thatL h is consistent to hamming loss. Therefore, based on Corollary 25 in [42], we have where ξ is a non-negative concave function with ξ(0) = 0.

E Proof for Theorem 4
Proof. The proof is mainly composed of the following two lemmas.
Sequentially, let (y, y ′ ) be the current label pair to be cumulated, then, according to Talagrand's contraction lemma [18], we have We omit the proof, since it can be proved similarly to Lemma 4. Finally, similar to theorem 2, based on lemma 5 and 6, it is easy to obtain theorem 4.

F Proof for Theorem 5
Proof. For notational simplicity, we introduce the following notation: ∆ j,k = y:y j =−1,y k =+1 py and we have ∆j,t ≤ ∆t,j if ∆ j,k ≤ ∆ k,j and ∆ k,t ≤ ∆ t,k which has been proved in [10]. Let us first define the set of Bayes predictors with respective to ranking loss Following Theorem 10 in [10], if φ is a differential and non-increasing function with φ ′ (0) < 0 and φ(t) + φ(−t) = 2φ(0), it suffices to prove that fj > f k if ∆ j,k < ∆ k,j for every f such that W * (p) = W (p, f ), where W * (p) = inf f W (p, f ).Therefore, by minimizing W (p, f ), we obtain the Bayes decision function f , which provesLr is consistent to ranking loss. Accordingly, based on Corollary 25 in [42], we have where ξ is a non-negative concave function with ξ(0) = 0.