WPML3CP: Wasserstein Partial Multi-Label Learning with Dual Label Correlation Perspectives

1 Introduction

Multi-label learning (MLL) [Zhang and Zhou, 2014a] refers to inducing multi-label predictors from the precisely labeled training dataset, where each instance is annotated with its ground-truth labels. However, in many real-world scenarios, e.g., annotations from crowdsourcing platforms, only partially valid training dataset is available due to various reasons [Li et al., 2021; Li et al., 2022; Feng et al., 2022; Li et al., 2023; Xie et al., 2023], such as the difficulty of accurate supervision collection and human effort cost reduction, etc. A common situation is that each instance is associated with a set of candidate labels, which cover the groundtruth labels but also with some irrelevant ones, e.g., the image instance illustrated in Fig.1. Learning with such a partially valid training dataset, formally referred to as partial multilabel learning (PMLL), is naturally much more challenging than the traditional MLL since even the number of groundtruth labels is unknown.

∗Corresponding author.

To handle the emerging task of PMLL, many methods have been recently developed, where the basic idea is to estimate the ground-truth confidences of candidate labels, i.e., the likelihood of a candidate label being a ground-truth one, and induce the multi-label predictor with them rather than candidate labels [Xie and Huang, 2018a; Sun et al., 2019; Li et al., 2020; Li and Wang, 2020; Xie et al., 2021; Sun et al., 2022]. Naturally, the primary philosophy of PMLL is how to estimate precise ground-truth confidences, and to our knowledge, the prevalent spirit is to promote it by exploiting the correlations among labels. For example, the GLC method formulates the ground-truth confidences by integrating a label correlation matrix [Sun et al., 2022]; the MUSER method decomposes ground-truth confidences into two parts, including a low-dimensional label matrix and a label correlation matrix [Li et al., 2020]. Although this spirit is empirically effective in prior literature, it raises a new problem that label correlations are also required to estimate, and imprecise estimations may result in imprecise ground-truth confidence.

Accordingly, in this paper, we concentrate on estimating precise label correlations to promote the precision of groundtruth confidence. To this end, we propose to capture label correlations from both measuring and modeling perspectives. Specifically, we measure the loss between groundtruth confidences and predictions by employing the Wasserstein distance involving label correlations; and form a label correlation-aware regularization to constrain predictive parameters. The two techniques are coupled to promote precise estimations of label correlations. Upon these ideas, we propose a novel PMLL method, namely Wasserstein Partial Multi-Label Learning with dual Label Correlation Perspectives (WPML3 CP), which is optimized within the framework of the augmented Lagrange multiplier method. To evaluate the performance of WPML3 CP, we conduct extensive experiments on both real-world and synthetic datasets. Experimental results demonstrate that WPML3 CP can outperform the existing PMLL baselines in most cases.

To sum up, the main contributions of this paper are presented as follows:

• We propose a novel PMLL method named WPML3 CP, which promotes precise ground-truth confidences by capturing label correlations from both measuring and modeling perspectives.
• We efficiently optimize the proposed WPML3 CP method with the framework of augmented Lagrange multiplier.
• We empirically validate the effectiveness of WPML3 CP by comparing with the existing PMLL baselines on both real-world and synthetic datasets.

2 RelatedWorks

2.1 Partial Multi-Label Learning

Recently, several PMLL methods have been proposed. Generally, they mainly focus on estimating the ground-truth confidences, so as to capture more accurate supervised signals. At present, the methods to solve PMLL are mainly divided into unified framework method and two-stage method. Specifically, the unified framework method aims to integrate label confidence learning and multi-classification model into a joint framework, then the unified framework is optimized by iterative strategy. The PMLL framework proposed by [Xie and Huang, 2018b] is built on a ranking loss objective weighted by the ground-truth confidence, which is regularized through either label correlation or feature prototype, and gives two versions, named PML-lc and PML-fp, respectively. Then both fPML [Yu et al., 2018] and PML-LRS [Sun et al., 2019] utilize the low-rank decomposition to capture the ground-truth label matrix from the observed candidate labels. MUSER [Li et al., 2020] combines label decomposition and feature mapping to enhance the robustness of the classifier against redundant labels and noisy features. Another recent PML-NI [Xie and Huang, 2021] method jointly learns the multi-label classifier and noise label identifier which combines the label correlation exploitation and feature-induced noise model. In order to make full use of label correlation information to deal with noise labels, GLC [Sun et al., 2022]

uses low-rank representation and label manifold regularizer to capture the global and local label correlation, respectively. Recently, graph-based methods have been widely used to deal with PMLL problems. PARD [Hang and Zhang, 2023] first applies the probabilistic graphical model to disambiguate the candidate labels. PLAIN [Wang et al., 2023] constructs the instance graph and the label graph in a data-driven way, and calculates similarity to generate pseudo-labels through label propagation.

Different from the unified framework method, the twostage method restores the ground-truth label distribution or learns a label confidence matrix in the first stage, and then builds a multi-classification prediction model based on the recovered label distribution or label confidence matrix in the second stage. PARTICLE [Zhang and Fang, 2021] first estimates the ground-truth confidences by iterating label propagation to select credible labels. Then, it induces the prediction model with these credible labels using either VLS or MAP, respectively. In addition to PARTICLE's work, PMLLD [Xu et al., 2020] uses the topological information of feature space and the correlation between labels to recover the label distribution. PML-MD [Xie et al., 2021] uses confidenceweighted ranking loss to process the PMLL data in the first stage, where confidences are estimated adaptively using a meta-learning-based approach. Considering that estimating label confidences may introduce a lot of uncertainty, PAMB [Liu et al., 2023] uses error-correcting output code (ECOC) technique to transform PMLL problems into multiple binary learning problems.

2.2 Learning withWasserstein Distance

The Wasserstein distance [Villani, 2008] has drawn great attention in the machine learning community, and been widely applied to various learning tasks [Cuturi and Doucet, 2014; Rubner et al., 2000; Arjovsky et al., 2017; Frogner et al., 2015; Kusner et al., 2015; Huang et al., 2016; Zhao and Zhou, 2018]. Recently, the authors of [Frogner et al., 2015] propose a novel learning framework, which refers to the Wasserstein distance as the loss function. Orthogonal to WPML3 CP, this framework is also solved using entropic regularization approximation [Cuturi, 2013], however, it is only applicable to precisely annotated datasets. Another representative work proposed in [Zhao and Zhou, 2018] employs Wasserstein loss for the task of label distribution learning. It introduces a kernel biased regularization to simultaneously leverage the label distribution and induce label correlations. However, it is also assumed that the ground-truth supervision is known.

3 Preliminaries

In this section, we first briefly review the Wasserstein distance and then introduce its entropic regularization.

The Wasserstein distance [Bogachev and Kolesnikov, 2012] is a special case of optimal transport distance [Villani, 2008], also referred as earth mover's distance [Rubner et al., 2000]. Formally, given any two probability measures µ(u), ν(v) on a space K (i.e., u, v ∈ K) and a cost function c : K×K → R, the optimal transport distance measures the cheapest way to transport the mass in µ to match that in ν:

where Π(µ, ν) denotes the set of all joint probability measures on K × K with marginals µ(u) and ν(v). The Wasserstein distance is the case of Eq.(1), in which the cost function c is specified by drK, the r-th power of a metric dK on K with r ∈ [1,∞).

Discrete Wasserstein distance. When K is a finite set of size |K| = K, both µ(u) and ν(v) are discrete distributions (i.e., histograms) in the simplex ∆K , i.e., {µ, ν ∈ RK+ | µ⊤1 = 1, ν ⊤1 = 1}, where 1 denotes the all-one vector. Given a cost matrix MK computed by the r-th power of pairwise distances over K, i.e., MK = [drK(ui, vj)]ij ∈ RK×K , the discrete Wasserstein distance between µ(u) and ν(v) can be written as:

where ⟨·, ·⟩ denotes the Frobenius dot-product, and U(µ, ν) = {T ∈ RK×K + |T1 = µ,T⊤1 = ν} is the transportation polytope.

Regularized Wasserstein distance. The discrete Wasserstein distance of Eq.(2) is not smooth with respect to its arguments µ, ν [Cuturi and Doucet, 2014], and its computation requires costly O(K3 logK) time [Pele and Werman, 2009]. To handle those problems, the authors of [Cuturi, 2013] incorporate an entropic regularizer into Eq.(2), leading to the regularized Wasserstein distance:

where H(T) = -⟨T, logT⟩ is the (strictly concave) entropy function and λ > 0 is the regularization parameter. Accordingly, given models with parameters of interest, i.e., denoted by {µ, ν,MK}, we can optimize them by the Sinkhorn's algorithm with O(K2 ) complexity [Cuturi, 2013; Cuturi and Doucet, 2014]. The optimization details are introduced in the Appendix 1 .

4 ProposedWPML3 CP Method

In this section, we introduce the proposed PMLL method named WPML3 CP.

Problem formulation of PMLL. Formally, given a partially valid training dataset D = {(xi, yi)}i=n i=1 with n instances and l category labels, let xi ∈ Rd and yi ∈ {0, 1}l denote the d-dimensional feature vector and the candidate label set associated with the i-th instance, respectively. For yi, the candidate label is signed by 1, otherwise 0. For each instance xi, its ground-truth label set y∗ i ∈ {0, 1}l is unknown, but it is covered by yi, i.e., y∗ i ⪯ yi. The objective of PMLL is to induce a classifier over D, which can predict the labels for unseen instances.

1 https://github.com/daidai1118/WPML3CP/blob/main/ WPML3CP Appendix.pdf

4.1 Method Description

For each instance xi, its (normalized) ground-truth confidence is defined by pi ∈ Rl such that 0 ⪯ pi ⪯ yi, p⊤i 1 = 1, where 0 denotes the all-zero vector. And the label correlation matrix is denoted by C ∈ Rl×l + with each c:,j being the coefficient vector for label j with respect to labels l. The basic idea of WPML3 CP is to estimate precise p by capturing precise C from both measuring and modeling perspectives.

Specifically, from the measuring perspective, we specify each pi as a discrete distribution, and measure the loss between it and the prediction model by exploiting the regularized Wasserstein distance Wλ(·). Toward this goal, we employ a normalized linear model f(xi|W) = Wxi, W = [w1, · · · ,wl]⊤ ∈ Rl×d such that (Wxi)⊤1 = 1, ensuring the prediction also as a discrete distribution. From the modeling perspective, we form a label correlation-aware manifold regularization term to constrain the parameter W of the model. Upon the above ideas, we formulate the objective of WPML3 CP with a squared Frobenius norm of W as follows:

where m(·) = 1 - sigmoid(·) is utilized to transform the label correlation matrix C to the cost matrix of Wasserstein distances; and {β1, β2} are the regularization parameters.

Since the constraints of Eq.(4) tend to increase the optimization complexity, we leverage two surrogate heuristics to eliminate them. First, for the two equality constraints of pi and Wxi, we exploit the softmax function s(·) to directly satisfy them. Specifically, for each pi we introduce an auxiliary softmax parameter qi, i.e., pi = s(qi), and therefore learn Q = [q1, · · · , qn]⊤ ∈ Rn×l , instead of P. Second, for the inequality constraint of pi, we consider the irrelevant labels existed in the observed candidate label matrix Y = [y1, · · · , yn]⊤, and decompose it into the matrix Q and a noise matrix E. Considering that the ground-truth labels are correlated in the multi-label learning case and the noise is always sparse in many real-world scenarios, we introduce a nuclear norm regularization for Q and ℓ1-norm regularization for E. Accordingly, we achieve the final objective of WPML3 CP with respect to {W, Q, C, E} below:

Here, the equality constraint of Eq.(5) can be eliminated easily by employing the augmented Lagrange multiplier technique [Zhang et al., 2017].

4.2 Optimization

The objective of WPML3 CP in Eq.(5) refers to four parameters of interest, i.e., {W,Q,C,E}. We optimize them with the gradient decent approach under the augmented Lagrange multiplier framework. Specifically, the augmented Lagrangian of Eq.(5) is given with an auxiliary variable H:

where L = diag(C1) - C is the Laplacian matrix of C. According to the LADMAP method [Lin et al., 2011], it can be rewritten as:

Accordingly, we employ the gradient decent approach to optimize {W, C, H}, whose gradients can be easily calculated with some simple derivations and the Sinkhorn algorithm, and update {Q, E} as well as {Y1, Y2, µ1, µ2} with the linear ADM method following [Liu et al., 2010]. Due to the space limitation, the optimization details are presented in the Appendix 2 .

Initialization of label correlation matrix C: We initialize the label correlation matrix C with the cosine similarities among label prototypes, which are calculated by averaging the training features X = [x1, · · · , xn]⊤ weighted with Y. Specifically, given the label prototypes O = Y⊤X = [o1, · · · , ol]⊤, the initialization of the label correlation matrix C is given by:

5 Experiment

In this section, we empirically evaluate the proposed WPML3 CP method.

Datasets. To thoroughly evaluate WPML3 CP, we employ 5 real-world PMLL datasets, 3 including Music emotion, Mirflickr, YeastBP, YeastCC, and YeastMF, and generate synthetic PMLL datasets by using 4 MLL datasets, 4 including Birds, Medical, Genbase, and Entertainment. For clarity, we present the detailed characteristics of all datasets in Table 1.

2 https://github.com/daidai1118/WPML3CP/blob/main/

WPML3CP Appendix.pdf

3 http://palm.seu.edu.cn/zhangml/

4 http://mulan.sourceforge.net/datasets-mlc.html, https://github. com/fcharte/mldr.datasets

Besides, the synthetic versions are generated by the following policies. For each instance, we randomly choose some irrelevant labels, and then mix them with the ground-truth ones, leading to the set of candidate labels. The number of irrelevant noisy labels is denoted by m%∥y∗ i ∥0, where the value of m is varied over [50, 100, 150]. Accordingly, in our experiments, we generate 12 synthetic PMLL datasets in total.

Baseline methods. We employ 7 the state-of-the-art PMLL methods for comparison. They include PAMB [Liu et al., 2023], GLC [Sun et al., 2022], PMLNI [Xie and Huang, 2021], PML-MD [Xie et al., 2021], PML-LRS [Sun et al., 2019], PAR-MAP and PAR-VLS [Zhang and Fang, 2021]. We set the parameters as suggested in their original papers. For our WPML3 CP, across Mirflickr and Music emotion the parameters are set as: β1 = 1, β2 = 10-3 , β3 = 10-1 , and β4 = 1, and across YeastBP, YeastCC and YeastMF the parameters are set as: β1 = 10-3 , β2 = 10-1 , β3 = 102 , and β4 = 102 . Furthermore, about the parameter λ of the regularized Wasserstein distance, we set λ = 1 for Mirflickr and λ = 50 for others.

Evaluation metrics. We employ 5 widely-used MLL metrics to measure the performance, including Average Precision (AP), Coverage Error (CError), Ranking Loss (RLoss), Macro Averaging F1 (Macro F1) and Micro Averaging F1 (Micro F1). Those evaluation metrics cover both rankingand binary-based ones and their detailed definitions can refer to the descriptions in [Zhang and Zhou, 2014b]. For CError and RLoss, the smaller value implies better performance (denoted by ↓); and for AP, Macro F1, and Micro F1, the larger value is better (denoted by ↑).

5.1 Results on Real-world Datasets

For each dataset, we conduct five-fold cross-validation and report the average results in Tables 2 and 3. We can clearly observe that WPML3 CP can outperform the baseline methods in most cases. Across all datasets and evaluation criteria on real-world datasets, WPML3 CP ranks 1st in 80% and 2nd in 12% cases. More detailed observations are made below.

Comparisons via the perspective of evaluation criteria: We can observe that, on the ranking based metrics (i.e., AP, CError and RLoss), WPML3 CP ranks first in 73.3% cases. Specifically, WPML3 CP dominates all seven PML baselines on CError and performs similarly on AP and Rloss: It outperforms most baselines on these criteria but slightly worse than PAMB in music emotion and PML-MD in mirflickr. On binary prediction-based metrics (i.e., Macro F1 and Micro F1), WPML3 CP ranks first in 90% cases. Specifically, WPML3 CP dominates all seven PML baselines under these two criteria, except in music emotion where PML-MD outperforms WPML3 CP over Micro F1. This probably because that our method primarily guiding prediction model generation based on label correlation, resulting in many irrelevant labels sharing similar features being predicted as correlated. As a result, the binary prediction is perceived as more accurate but ranks slightly lower. In particular, PAMB performs very well in music emotion on three ranking based metrics, but poorly on two binary prediction based metrics, which indicates that the binary decomposition technique still has some limitations for PMLL problems.

Comparisons via the perspective of datasets: We can observe that, on the datasets with a large number of features (i.e. YeastBP, YeastCC and YeastMF), WPML3 CP shows the best under all evaluation metrics. On datasets with a small number of features (i.e. Mirflickr and Music emotion), the average rank of WPML3 CP ranks first, slightly better than that of PML-MD. This might be caused by the too large average number of labels per instance of Yeast compared with the number of category labels, leading to the very sparse label vector of each instance. Fortunately, our method fully considers the label correlation from both measuring and modeling.

5.2 Results on Synthetic Datasets

Across all datasets and evaluation criteria on synthetic datasets, WPML3 CP ranks 1st in 76.7% and 2nd in 20% cases. We can observe that WPML3 CP consistently outperforms all baselines for both medical and entertainment datasets in terms of all five evaluation metrics. For genbase, WPML3 CP only has a small performance gap compared with PAR-MAP on CError and RLoss metrics but still competitive. In addition, PAMB outperforms WPML3 CP over Macro F1 metric. One exception is in birds, where PML-NI outperforms our method over CError and RLoss evaluation metrics. This may be caused by the noise label identifier proposed in PML-NI, which leads to the improvement of performance. Besides, the performance gain of WPML3 CP tends to be more significant with the proportions of irrelevant labels increasing.

Additionally, we examine whether the performance gain of WPML3 CP is statistically significant. To answer this question, for each PMLL dataset and evaluation metric, we conduct a pairwise t-test over the results of the corresponding five train/test splits. The resulting win/tie/loss counts over 425 statistical tests (17 PMLL datasets × 5 evaluation metrics × 5-fold cross-validation) are reported in Table 4. In summary, out of all the tests, WPML3 CP significantly outperforms recent PMLL algorithms in 88.9% (PAMB), 96.5% (GLC), 77.4% (PML-NI), 88% (PML-MD), 91.8% (PMLLRS), 80.2% (PAR-MAP) and 96% (PAR-VLS) cases, respectively. This further indicates the effectiveness of WPML3 CP.

5.3 Parameter Evaluation

In this subsection, we evaluate the sensitivity of the regularization parameter {β1, β2, β3, β4} of WPML3 CP. To this end, we examine the impact of varying {β1, β2, β3} values across the range {10i |i = -3, · · · , 3} and varying β4 values across the range {10i |i = -1, · · · , 5} on two real PMLL datasets Mirflickr and YeastCC, measured by the ranking based metric (i.e., AP) and the binary prediction based metric (i.e., Macro F1). The results are presented in Figure 2. Roughly, we can observe that WPML3 CP tends to achieve higher scores with relatively smaller values of {β1, β2} and higher value of β4, and excepts a smaller (higher) value of β3 on the dataset with a large (small) number of features. We empirically recommend selecting the values of {β1, β2} from 10-3 to 101 , β3 inversely proportional to dim(S) and β4 from 10-1 to 103 .

5.4 Ablation Study

In this subsection, we conduct ablative studies of different strategies (terms in the loss) by setting the corresponding regularization parameters to zero (see Figure 2). Specifically, {β1 = 0, β3 = 0, β4 = 0} represents the versions without the manifold regularization, ∥Q∥∗, and ∥E∥1 terms, respectively. Furthermore, to validate the effectiveness of Wasserstein distance, we compare substituting it with Euclidean distance in Table 5, serving as an ablation experiment for the label correlation-aware Wasserstein distance. The results on all real datasets demonstrate the superiority of the Wasserstein distance over the Euclidean distance.

6 Conclusion

In this paper, we investigate the paradigm of PMLL with noise supervised signals. A novel PMLL method, namely WPML3 CP, is proposed. In WPML3 CP, we specify the ground-truth confidence as the normalized discrete distribution, i.e., latent label distribution, to describe the probability of a candidate label being a ground-truth one. Considering it as a latent distribution variable, we jointly learn it and a normalized linear prediction model by minimizing the robust regularized Wasserstein distance. To reduce the optimization complexity, we eliminate the normalized constraints by exploiting the softmax function, leading to a surrogate objective without any constraint. The gradient descent with Adam is used to solve it. Extensive experimental results demonstrate that WPML3 CP outperforms the state-of-the-art baseline algorithms, and specifically it works well with high proportions of irrelevant labels.

Acknowledgements

We would like to acknowledge support for this project from the National Science and Technology Major Project (No.2021ZD0112501), the National Natural Science Foundation of China (No.62276113), and China Postdoctoral Science Foundation (No.2022M721321).