Towards Robust Multi-Label Learning against Dirty Label Noise

1 Introduction

Multi-label learning (MLL), which involves training on instances with multiple labels, is increasingly researched across various fields [Zhang et al., 2022; Xu et al., 2023; Lin, 2023]. Traditional MLL relies on accurately labeled data; however, real-world datasets often contain noisy labels that significantly impair learning. There are two main types of noise in these datasets. Category 1 is the partial random noise incurred by human experts or automated classification tools. For example, this type of noise may be generated by the annotators due to the ambiguous contents (missing label, e.g., turtle in Fig.1(i) is obscured by the lawn), complicated structure of objects (extra labels, e.g., ship in Fig.1(f) shouldn't exist) or a combination of the above two (missing and extra labels, e.g., bear in Fig.1(g) is mislabeled as dog, where bear label is missing and dog label is extra, also known as error labels). The missing label noise can be regarded as negative noise, and the extra label noise as positive noise. This kind of artificial noise may be sparse (e.g., only three out of ten pictures are mislabeled in Fig.1) or specific to some labels, named subjective (e.g., crab is easier to distinguish than bird in Fig.1). Category 2 refers to the completely random noise by encoding errors or communication problems introduced by sensors in fields such as electrical engineering, signal processing, or hardware sensor calibration [Brodley and Friedl, 1999; Zhu and Wu, 2004], which is often gaussian. The instance and the label matrices are located in the same data packet, it implies that the label may be affected by real-valued noise (e.g., gaussian) during propagation just like feature instance. Examples of these noises (gaussian, subjective and sparse) reflected in noise matrices for 8 labels and 4 instances are shown in Figs.2(a), (b) and (c), respectively.

∗Corresponding author.

Recent research has made effort in handling the data noise in the learning model. For example, multi-label learning with missing labels (MLML) [Wu et al., 2014] trains the model for the case of missing labels (negative noise). Partial multilabel learning (PML) [Xie and Huang, 2018] considers the training samples with several extra distractor labels (positive noise). [Sun et al., 2021] handles both missing and extra labels. These works assume that the true noise only obeys a gaussian or laplace distribution (sparse) and is recovered by the ℓ2- or ℓ1-norm (to denoise), respectively. However, the noise distributions are intricate in real applications. For example, the noise may depend on some specific classes or obey multiple distributions simultaneously, and we define this kind of noise as the dirty noise. As shown in Fig.1, it is very common that the real datasets contain a dirty label noise, satisfying two numerical conditions (i.e., negative and positive) and multiple structural requirements (i.e., sparse, subjective and gaussian), simultaneously. A representation of the dirty noise on the noise matrix is shown in Fig.2(d). Note that the dirty noise is a different type of noise from a simple summation of the previous noises. Thus, it cannot be solved by simply combining existing methods. This calls for new technologies to handle the dirty noise that exists in real-world datasets.

We formalize this problem as a new learning framework called Noisy Multi-label Learning (NML). NML is a novel learning framework with significant difference from existing settings. More specifically, NML tries to learn a multi-label model from the training datasets with dirty label noise, where each instance in the dataset is assigned with multiple labels and the labeled datasets contain the label noise obeyed 3 noise distributions (i.e. gaussian, sparsity and subjective), simultaneously. And the label noise can be a real number, not just positive or negative alone.

To tackle the NML problem, we propose a robust Noisy Multi-label Learning against Dirty label noise (NMLD) approach, which learns a multi-label model from the dataset with dirty label noise using the idea of "simple but contracted ": while any one structure penalty might not capture the noise, a superposition of structural classes might. Specifically, we decompose the corrupted label matrix as a noise matrix plus a true label matrix (maybe high-rank), and use a mixed norm penalty of noise matrix based on 3 noise distributions. We provide theoretical guarantee for exact noise recovery from such a structured corruption. To more accurately identify the true label matrix, we apply a nonlinear mapping to it to ensure that the mapped matrix is of low-rank such that the highorder label correlation can be utilized. A novel accelerated proximal alternating algorithm is developed, and the problem is jointly optimized for the noise and true label matrix. To summarize, our contributions are:

• A new framework NML is proposed to learn multi-label models from noisy labeled data where the noise is promoted by various different types of noise patterns.
• An algorithm NMLD is proposed for solving the NML problem. NMLD unifies a mixed penalty on noise matrix and true matrix exploration in a unified objective. Theoretical conditions for exact noise recovery are provided.
• Experiments demonstrate that NMLD is effective on noisy data and with missing or extra labels.

2 RelatedWork

To mitigate the label noise issues in MLL, weakly supervision learning have been proven to be practical [Natarajan et al., 2013; Wang et al., 2023; Van Rooyen and Williamson, 2017; Xie et al., 2022; Xie et al., 2023; Wang et al., 2024a; Wang et

(a) Gaussian (b) Subjective

al., 2024b]. Multi-label learning with missing labels (MLML) is a learning task that conducts the learning over the data with partial set of positive labels and missing labels. Most of the MLML methods attempt to complete the missing labels first, and then train the classifiers with the complete labels [Wu et al., 2014].

Partial multi-label learning deals with training instances annotated with a candidate label set that contains true labels and extra labels. To identify the extra labels, [Xie and Huang, 2018] first utilizes the label confidence to measure the probability of being the true labels for each candidate label, and obtains the true labels according to label ranking. CORALS [Sun et al., 2021] propose to deal with the missing and extra labels simultaneously, where a label confidence matrix is constructed and the ordering of labels are optimized.

However, these methods consider one specific label noise only, which lacks of the capability of handling common possible type of dirty label noise. Therefore, they can not solve the NML problem that widely exist in real-world datasets.

3 Methodology

3.1 NML Definition

Let X ∈ Rd×n be the feature matrix for n instances in the ddimensional feature space. The corresponding ground-truth label of X is denoted as matrix Y ∈ {1, -1}q×n , where each column corresponds to an instance and each row corresponds to a label. If xi is associated with the c-th label, [Y]ci = 1; otherwise, [Y]ci = -1. And let ˜Y ∈ Γq×n denote the corrupted label matrix with dirty label noise, which satisfy two numerical conditions (i.e. negative and positive) and multiple structural requirements (i.e. sparse, subjective and gaussian), simultaneously. Generally, Γ := R due to the existence of noise. The goal of NML is to identify noisy labels of corrupted label matrix ˜Y and train a multi-label classifier f : Rd×n → {1,-1}q×n fromX.

3.2 NMLD Algorithm

To deal with the NML problem, in this paper, we propose a robust noisy multi-label learning method for dirty noise NMLD. Specifically, we decompose the corrupted label matrix as a noise matrix plus a true label matrix (maybe high-rank), and use a mixed norm penalty of noise matrix for different noise distribution to fit different types of noise. To improve the generalization ability, we apply a non-linear mapping on true label matrix to ensure the low-rankness such that the high-order label correlation can be easily utilized. To solve the resulting objective, we develop an optimization method to minimize the loss by alternating restricted minimization over the subsets of variables.

Our goal is to use the instance matrix X and the corrupted label matrix ˜Y for training a new NML model and to predict the labels for unlabeled data. To solve this problem, we assume the linear regression prediction model. Therefore, we can optimize the matrix W ∈ Rq×d by minimizing the square loss with the ℓ1-norm regularization

where ∥ · ∥F and ∥ · ∥1 are Frobenius- and ℓ1-norm, respectively, and α is the trade-off parameter.

However, the corrupted label matrix ˜Y often includes label noise in noisy multi-label learning. Many weakly supervised MLL methods assume the label matrix ˜Y is low-rank and use nuclear norm regularization to recover the true label matrix. Unfortunately, the low-rank assumption does not necessarily hold. For example, if each sample has a distinct label, the rank of the label matrix is rank( ˜Y) = min{q, n}. Obviously, the low-rank assumption fails when both n and c are large. In addition, the presence of noise may increase the rank of ˜Y. To deal with this problem, we decompose the corrupted label matrix ˜Y into a true label matrix Y and a noise label matrix E, i.e. ˜Y = Y + E. Motivated by the kernel principal component analysis (KPCA) method, we use a smooth nonlinear function ϕ to map the the columns of label matrix Y into a high-dimensional (possibly infinite) space such that ϕ(Y) ∈ Rκ×n is exactly or approximately of low-rank [Sch¨olkopf et al., 1997; Fan and Chow, 2019; Ma et al., 2019]. Thus, a low-rank constraint on ϕ(Y) is utilized to further exploit high-order label correlations [Xu et al., 2014]

to mitigate the impact of noise and strengthen the generalization performance, where β and γ are balancing parameters, ∥ · ∥2 denotes the ℓ2-norm, Θ = ϕ(Q) ∈ Rκ×r , and Υ = ϕ(Y) = ϕ( ˜Y - E). We find that the RBF kernel mapping is more effective than polynomial kernel. Hence, we mainly focus on RBF mapping with parameter σ. To capture the rank property of the mapped label matrix, the trace norm ∥ · ∥∗ is employed to introduce the low-rank assumption.

In this work, we aims to handle the dirty label noise (Fig.2(d)), which is promoted by the different noise priors: Gaussian (Fig.2(a)), Sparsity (Fig.2(c)) and Subjective (Fig.2(b)), simultaneously. As shown in Fig.2, the distribution of the dirty noise is completely different from any of the individual noise patterns, rather than a simple combination of them. To identify the dirty label noise, we use a simple but interesting idea: while any one structure constraint might not capture the dirty noise, a superposition of structural constraint classes might

where η1, η2 and η3 are balancing parameters. 1) ∥E∥2 is to capture the gaussian noise which is incurred by data encoding or communication errors; 2) Both ∥E∥1 and ∥E∥2,1 are to capture the label noise incurred by annotators (e.g., missing labels, extra labels etc.), where ∥E∥1 is for the case when ˜Y is partially and randomly corrupted (i.e., E is a sparse matrix) and ∥E∥2,1 is for the case when a few columns of ˜Y are corrupted by noise. We will prove later that this superposition of norms can identify with dirty label noise.

The unified objective function for NMLD is defined as

where α, β, γ are parameters to keep the balance of the model. We introduce the specific noise matrix E to the first term which helps our method better identify the true labels and eliminate the impact of noisy labels.

Theoretically, we are also interested in providing sufficient condition on the recovering of the true noise label matrix. The following result provides sufficient condition for exactly reconstructing true noise E† using Eq.(4).

Theorem 1. If the true noise matrix E† (>0 for PML, <0 for MLML, both for NML) obeys 3 distribution as described in Figs.2(a), (b) and (c), simultaneously (i.e. Fig.2(d)). In Eq.(4), ˜Y -WX in the first term is an observation of the real noise E† , assume that the observation error ∆= ˜Y-WX-E† obeys the gaussian distribution. Let η1 = ν1√3nq/2, η2 = ν2√2 log(q/s1) and η3 = ν3(√2 log(m/s2) + √k), where νi ∈ [0, 1] and ∑i νi = 1, s◦ controls the sparsity proportion of ℓ1 and ℓ2,1, respectively. m denotes the number of groups for ℓ2,1. t denotes arbitrary constant. Then, whenever the number of observations

E† can be recovered exactly with probability 1 - 2e-t2 /2 .

This result shows how the noise recovery is governed by the number of observations for the real noise matrices.

3.3 Optimization

To solve the problem in Eq.(4), we iteratively update Q, P, E and W. We summarize the key steps in Algorithm 1. Update Q. When W, P and E are fixed, the problem in Eq.(4) w.r.t Q ismin

We have ∥Θ∥2 = tr(ϕ(Q)⊤ϕ(Q)) = r, which means the norm has no effect on the problem and can be discarded, where tr(·) denotes the trace operator. The minimization of Eq.(5) has no closed-form solution, we optimize Q via the gradient descent algorithm. The gradient of Eq.(5) is

Algorithm 1 NMLD

Input: train data X, label matrix ˜Y

Output: W

1: ˙ω ← 1 and initialize ˙W, ˙Q, ˙P, ˙E;

• 2: while not converged

• 4: Q← ˙Q- δ∇Q( ˙Q);

• 6: ˙P ← P;
• 7: Update E using Eq.(19); % update E

8:

˙E ← E;

• 11: ¨W← ˙W, ˙W←Wand ˙ω ←ω;
• 12: returnW

where R1 = -P⊤ ⊙Υ ⊤Θ, R2 = (1/2PP⊤)⊙Θ⊤Θ, ˇRi = diag(1⊤Ri) and ⊙ denotes the Hadamard product. Then we update Q := ˙Q- δ∇Q( ˙Q), where δ is the step size and ˙Q denotes the solution of previous iteration.

Update P. Fixing W, Q and E, we have

Eq.(7) has no closed-form solution, since the presence of kernel mapping. We use the proximal gradient method to update P [Bauschke and Combettes, 2017]. Let g(P) = γ∥P∥∗ and f(P) = 1 2 ∥Υ - ΘP∥2F . f(P) is approximated by its first order expansion at the solution ˙P of previous iteration

where LPf is the Lipschitz constant of ∇Pf=Θ⊤(ΘP-Υ). We therefore turn to optimize the following problem

This can be solved by singular value thresholding (SVT) [Cai et al., 2010], and the optimizing rules are

where Tτ (Z) = USτ (Σ)V⊤ is the SVT operator, which U, Σ and V are given by the singular value decomposition of Z=UΣV⊤. S denotes the elementwise soft-thresholding operator defined by Sτ (v) = (v-τ )+-(-v-τ )+, which (x)+ replaces x with zero if x < 0, otherwise unchanged.

Update E. Fixing W, Q and P, we have

There is no closed-form solution for Eq.(11). We update E of three norms uniformly by the proximal gradient method. Let g(E) = Ω(E), f (E) = ∥( ˜Y - E) - WX∥2F /2 + ∥Υ - ΘP∥2F /2, and LEf is the Lipschitz constant of the gradient ∇Ef = (WX- ˜Y+E)+σ-1 (Y ˇR3-QR3)/2, where R3 = -P⊙Θ⊤Υ and ˇR3 is defined as in Eq.(6). The inequality

holds, where ˙E is the solution of previous iteration. We solve

Next, we provide two useful lemmas related to proximity in the following, which are then used in Theorem 2.

Lemma 1. [Jenatton et al., 2011] Let groups g1 ≼ . . . ≼ gm such that G = {g1, . . . , gm}, where ≼ is a total order relation defined by g ⪯ h ⇒ {g ⊆ h or g ∩ h = ∅}. The proximal operator ProxλΩ associated with the norm Ω can be written as the composition of elementary operators (◦)

Lemma 2. [Yu, 2013] We denote ∂f(x) as the subdifferential of the group f at point x, a sufficient condition for Proxf+g = Proxf ◦Proxg is

Theorem2. Let g1 = ∥·∥2, g2 = ∥·∥1 and g3 = ∥·∥2,1, then Proxη1g1+η2g2+η3g3 = Proxη3g3 ◦ Proxη1g1 ◦ Proxη2g2 , where Proxg (J) = arg minE LEf ∥E - J∥2F /2 + g(E).

For η1g1, the solution of related proximal map is

for η2g2, the related proximal map are given

for η3g3, the solution is

where Bτ (v) = (1 - τ/∥v∥2)+v is a block soft-thresholding operator which process matrix by column [Jenatton et al., 2011]. Let J = ˙E -∇Ef( ˙E)/LEf , the solution of Eq.(13) follows directly from Theorem 2

E∗ = Proxη3∥·∥2,1 ◦Proxη1∥·∥2 ◦Proxη2∥·∥1 (J) (19) Update W. When Q, P and E are fixed, the optimization problem in Eq.(4) w.r.t W can be reformulated as follows

The minimization of Eq.(20) is convex, but non-smooth due to the ℓ1-norm terms. We use the accelerated proximal gradient (APG) method to solve it [Beck and Teboulle, 2009]. Let g(W) = α∥W∥1 and f(W) = 1 2 ∥( ˜Y - E) - WX∥2F . The derivation of f is denoted as ∇Wf = (WX- ˜Y+E)X⊤, and let LWf denotes the Lipschitz constant, we consider the following QP problem

The APG method includes an extrapolation step in the algorithm, the optimizing rules are given

and

where ¨Wdenotes the optimal solution at the iteration before last. ˙ω, ¨ω ∈ [0, 1) are extrapolation parameter at previous iteration and before last iteration, respectively. In practice, we update ω = 1/2 + √4 ˙ω2 + 1/2.

4 Experiments

4.1 Experimental Setting

Datasets. To evaluate NMLD's performance, we conducted experiments on ten multi-label datasets: slashdot, medical, enron, scene, yeast, 20ng, corel5k, mirflickr, eurlex dc, and m emotion [Pestian et al., 2007; Tidake and Sane, 2018]. Table 2 shows their characteristics, including number of instances, features, label classes, and maximum and average true labels per dataset. We also generated 3 synthetic datasets with different label noises for further testing. 1) For comparison on dirty noise, given a noise rate ρ, to make the noise matrix E with the dirty distribution, we first set E = 0 and randomly sample the row Ei: from E with probability (subjective). Then, we draw elements from each row Ei: randomly (sparsity) and assign a value to each element such that the value obeys the gaussian distribution. 2) For partial multi-label learning comparison purpose, we generate synthetic datasets by adding random redundant label noises. We use the same approach as the existing PML works [Xie and Huang, 2018]. 3) For multi-label learning with missing labels comparison, we randomly remove few classes or positive labels as MLML [Wu et al., 2014]. In our work, the dirty, excess and missing rate are set to 50%, 20% and 50%, respectively. Baselines. Existing approaches fall into two categories: partial multi-label learning (PML) and multi-label learning with missing labels (MLML). We evaluated our method in both contexts by comparing it with 7 state-of-the-art PML algorithms (i.e., fPML [Yu et al., 2018], PML-NI [Xie and Huang, 2021], PART-VLS, PART-MAP [Fang and Zhang, 2019], PML-LC, PML-FP [Xie and Huang, 2018] and MUSER [Li et al., 2020]) and 7 state-of-the-art MLML algorithms (D2MLL, D2ML-NL [Ma and Chen, 2021], LEML [Yu et al., 2014], MLMLFS [Zhu et al., 2018], GLOCAL [Zhu et al., 2017], MLMLV1 [Wu et al., 2014] and MAXIDE [Xu et al., 2013]). Consider there is no existing methods designed for the NML problem. We compare with the following methods CORALS [Sun et al., 2021], ECC [Ferng and Lin, 2011], CBMLC [Zhao and Gomes, 2021], where CORALS and CBMLC handle missing and noisy labels and ECC is full-supervised.

4.2 Comparison Results

We use 4 MLL evaluation metrics: Coverages, Average Precision, One Error and Ranking Loss. We compare the proposed NMLD with the 17 comparison methods on the 10 datasets.

Comparison on Redundant Multi-Label Data. We compared the performance of NMLD with baselines in PML settings for label prediction across 10 datasets, as shown in Table 1. NMLD consistently outperformed other PML methods. Notably, NMLD significantly surpassed PART-VLS, PML-NI, PML-LC, and PML-FP, and often exceeded PML, PART-MAP, and MUSER. These results highlight NMLD's capability in managing redundant noisy labels and validate its effectiveness in nonlinear mapping for partial multi-label matrices.

Comparison on Missing Mutli-Label Data. In the MLML setting, NMLD demonstrates competitive performance against established multi-label algorithms, as seen in Table 3. It notably surpasses LEML and MLML-the top-performing baselines-across most datasets for all evaluation metrics. LEML considers only a low-rank decomposition of the model coefficient, while the low-rank label matrix assumption is violated in many real-world application due to the presence of tail labels [Xu et al., 2016]. The super performance of NMLD against LEML and others indicates the effectiveness of NMLD on solving MLML problem.

Comparison on Dirty Multi-Label Data. After that, we study the prediction of the proposed algorithm on dirty noisy multi-label learning. Table 4 provides the experimental result of each compared method on 10 different datasets. As shown in Table 4, out of 40 statistical tests (10 data sets × 4 evaluation metrics), NMLD ranks in 1st place among the 4 comparing methods at 90% cases and ranks in 2st place at 7% cases. NMLD achieves the best performance in most cases. Regarding the CORALS and CBMLC, NMLD significantly outperforms them on most datasets. Regarding the multi-label learning approaches, the performance of NMLD is statistically superior to ECC. This indicates that label noisy significantly influences the performance of multi-label classifiers and NMLD can identify noisy labels effectively.

Ablation Analysis. We set the corresponding parameters ηi = 0 for the ablation experiments respectively. For example, set η1 = 0 to get ℓ1+ℓ2,1 or η2 = 0, η3 = 0 to get ℓ2. The evaluation result Average Precision (AP) is given in Table 5. As shown in Table 5, we found that the performance of combined norm is generally better than that of single norm, such as the model with ℓ1 + ℓ2,1 is better than ℓ1 and ℓ2,1. Moreover, the model with ℓ2 + ℓ1 + ℓ2,1 has the best performance, which is in accordance with the Theorem 1.

Time Comparison. In this section we perform time comparison on two datasets medical and 20ng. The running time of each method on data with above dirty noise are recorded in Table 6. As shown in Table 6, our approach is the most efficient one. For example, in the MLML setting, NMLD significantly outperforms all MLML methods on these two datasets. NMLD is more than 3 times faster than LEML, which is the most efficient existing MLML approach.

4.3 Experiments on Large Scale Datasets

To validate the performance of NMLD on large-scale data, we conduct experiments on the extreme multi-label benchmark data EURLex-4K, which contains 15,539 instances and Mediamill containing 43,970 instances [Bhatia et al., 2016]. We add PML and MLML noise as described previously. Table 7 reports the detailed experimental results of the proposed NMLD and comparing algorithms in term of Coverages. As show in Table 7, NMLD achieves the best performance against other SOTA contenders on large scale data.

5 Conclusion

In this paper, we proposed a novel noisy multi-label learning framework NML, which tackles a more practical learning problem over training data with dirty noise. We presented a robust approach NMLD, which unifies a mixed penalty on noise matrix and true label matrix exploration in a unified objective. A theoretical guarantee for exact noise recovery from dirty noise data has been provided. We formulated the method as a non-convex and non-smooth problem with accelerated proximal alternating techniques to jointly optimize the noise and true label matrix in a mutually beneficial manner. Empirical studies on 10 datasets against 17 baselines confirmed that our proposed approach outperform state-of-theart baseline algorithms significantly in the new NML problem as well as existing partial multi-label learning and multi-label learning with missing labels settings.

Acknowledgments

This research is supported in part by the National Natural Science Foundation of China under Grant No.92267206 and No.62032013, Singapore Institute of Technology Ignition Grant (R-IE2-A405-0001), AcRF Tier 1 Grant (R-R12A405-0009).