Recovering Accurate Labeling Information from Partially Valid Data for Effective Multi-Label Learning

1 Introduction

Partial Multi-label Learning (PML), a novel learning paradigm with noisy supervision, draws increasing attention from the machine learning community [Fang and Zhang, 2019; Sun et al., 2019]. It refers to induce the multi-label predictor from PML datasets, with each training instance associated with multiple candidate labels that are only partially valid. The PML datasets are available in many real-world applications, where collecting the accurate supervision is quite expensive for many scenarios, e.g., crowdsourcing annotations. To visualize this, we illustrate a PML image instance in Fig.1(a): an annotator may roughly select more candidate labels, so as to cover all ground-truth labels but ineluctably with several irrelevant ones, imposing big challenges for learning with such noisy PML training instances.

∗Yang Wang is the Corresponding Author, denoted by *

Formally speaking, given a PML dataset D = {(xi, yi)}i=n i=1 with n instances and l labels, where xi ∈ Rd denotes the feature vector and yi ∈ {0, 1}l the candidate label set of xi. For yi, the value of 0 or 1 represents the corresponding label to be a non-candidate or candidate label. Let y∗ ∈ {0, 1}l denote the (unknown) ground-truth label sets of instances. Specifically, for each instance xi, its corresponding y∗ i is covered by the candidate label set yi, i.e., y∗ i ⊆ yi. Accordingly, the task of PML aims to induce a multi-label predictor f(x) : Rd → {0, 1}l from D.

To solve the problem, several typical attempts have been made [Xie and Huang, 2018; Yu et al., 2018; Fang and Zhang, 2019; Sun et al., 2019], where the basic idea is to recover the ground-truth labels by leveraging the ground-truth confidence of the candidate label, i.e., the likelihood of a candidate label being a ground-truth one, and learning with it, instead of the candidate label. For example, an early framework of PML [Fang and Zhang, 2019] estimates the ground-truth confidences via label propagation over an instance neighbor graph, following the intuition that neighboring instances tend to share the same labels; another work [Sun et al., 2019] recovered the ground-truth confidences by decomposing the candidate labels under a low-rank scheme.

Revisiting the existing PML methods, we find that they basically estimate the ground-truth confidence around candidate label annotations, but neglect the information from noncandidate labels, which potentially contributes to the groundtruth label recovery. The irrelevance degree of the noncandidate label, i.e., the degree of a non-candidate label being irrelevant with the instance, is contributive to distinguish the irrelevant noisy labels within candidate label sets, since any candidate label tends to be an irrelevant noisy one if its highly correlated labels are given higher irrelevance degrees. For example, in Fig.1(b) and (c), the candidate label "airplane" is more likely to be an irrelevant noisy label, since its highly correlated labels, e.g., "airport" and "runway", are with higher irrelevance degrees for the example image instance.

Based on the above analysis, we propose to estimate the ground-truth confidences over both candidate and noncandidate labels. In particular, we develop a novel twostage PML method, namely Partial Multi-Label Learning with Label Enrichment-Recovery (PML3 ER). On the first stage, we estimate the label enrichment, composed of the relevance degrees of candidate labels (i.e., the complementary definition of irrelevance degree) and irrelevance degrees of non-candidate ones, using an unconstrained label propagation procedure. In the second stage, we jointly train the groundtruth confidence and multi-label predictor given the label enrichment learned from the first stage. We conduct extensive experiments to validate the effectiveness of PML3 ER.

The contributions of this paper are summarized below:

• We propose PML3 ER by leveraging both the information from candidate and non-candidate labels.
• The PML3 ER estimates the label enrichment using unconstrained label propagation, and then trains the multilabel predictor with label recovery simultaneously.
• We conduct extensive experiments to validate the effectiveness of PML3 ER.

2 RelatedWork

2.1 Partial Multi-label Learning

Abundant researches towards Partial Label Learning (PLL) have been made, where each training instance is annotated with a candidate label set but only one is valid [Cour et al., 2011; Liu and Dietterich, 2012; Chen et al., 2014; Zhang et al., 2017; Yu and Zhang, 2017; Wu and Zhang, 2018; Gong et al., 2018; Chen et al., 2018; Feng and An, 2018; Feng and An, 2019b; Feng and An, 2019a; Wang et al., 2019]. The core idea of PLL follows the spirit of disambiguation, i.e., identifying the ground-truth label from the candidate label set for each instance. In some cases, PLL can be deemed as a special case of PML, where the ground-truth label number is fixed to one. Naturally, PML is more challenging than PLL, even the number of ground-truth labels is unknown.

The existing PML methods mainly recover the groundtruth labels by estimating the ground-truth confidences [Xie and Huang, 2018; Yu et al., 2018; Fang and Zhang, 2019;

Sun et al., 2019]. Two PML methods are proposed [Xie and Huang, 2018], i.e., Partial Multi-label Learning with label correlation (PML-lc) and f eature prototype (PML-fp), which are upon the ranking loss objective weighted by ground-truth confidences. The other one [Sun et al., 2019], namely Partial Multi-label Learning by Low-Rank and Sparse decomposition (PML-LRS), trains the predictor with ground-truth confidences under the low-rank assumption. Besides them, the two-stage PML framework [Fang and Zhang, 2019], i.e., PARTIal multi-label learning via Credible Label Elicitation (PARTICLE), estimates the ground-truth confidences by label propagation, and then trains the predictor over candidate labels with high confidences only. Two traditional methods of victual Label Splitting (VLS) and Maximum A Posteriori (MAP) are used in its second stage, leading to two versions, i.e., PARTICLE-VLS and PARTICLE-MAP.

Orthogonal to those methods, our PML3 ER estimates the ground-truth confidence using the label enrichment involving both candidate and non-candidate labels to recover more accurate supervision.

2.2 Learning with Label Enrichment

Learning with label enrichment, also known as label enhancement, explores richer label information, e.g., the label membership degrees of instances, to enhance the performance [Gayar et al., 2006; Jiang et al., 2006; Li et al., 2015; Hou et al., 2016; Xu et al., 2018]. The existing methods achieve the label enrichment using the similarity knowledge of instances by various schemes, such as fuzzy clustering [Gayar et al., 2006], label propagation [Li et al., 2015], manifold learning [Hou et al., 2016] etc. They have been applied to the paradigms of multi-label learning and label distribution learning with accurate annotations.

Our PML3 ER also refers to the label enrichment, but it works on the scenario of PML under noisy supervision.

3 The PML3 ER Algorithm

Following the notations in Section 1, we denote X = [x1, · · · , xn]⊤ ∈ Rn×d andY = [y1, · · · , yn]⊤ ∈ {0, 1}n×l the instance matrix and candidate label matrix, respectively. For each instance xi, yij = 1 means that the j-th label is a candidate label, otherwise it is a non-candidate one.

Given a PML dataset D = {X,Y}, our PML3 ER first estimates the label enrichment, which describes the relevance degrees of candidate labels and irrelevance degrees of noncandidate ones. Specifically, for each instance xi, we denote the corresponding label enrichment ̂yi = [̂ yi1, · · · , ̂ yil]⊤ as follows:

referring to the example image instance in Fig.1(b). Further, we denote by ̂Y = [̂y1, · · · , ̂yn]⊤ the label enrichment matrix. Then, PML3 ER induces the multi-label predictor from the enrichment version of PML dataset ̂D = {X, ̂Y}.

We now describe the two stages of PML3 ER, i.e., label enrichment by unconstrained propagation and jointly learning the ground-truth confidence and multi-label predictor.

3.1 Label Enrichment by Unconstrained Propagation

In the first stage, PML3 ER estimates the label enrichment matrix ̂Y. Inspired by [Li et al., 2015; Fang and Zhang, 2019], we develop an unconstrained label propagation procedure, which estimates the labeling degrees by progressively propagating annotation information over a weighted k-Nearest Neighbor (kNN) graph over the instances. The intuition is that the candidate and non-candidate labels with more accumulations during the kNN propagation tend to be with higher relevance degrees and lower irrelevance degrees, respectively.

We describe the detailed steps of the unconstrained label propagation procedure below.

[Step 1]: After constructing the kNN graph Ω, for each instance xi, we compute its reconstruction weight vector of kNNs, i.e., vi = [vi1, · · · , vin]⊤ ∈ Rn , by minimizing the following objective:

where Ω(xi) denotes the kNNs of xi. This objective can be efficiently solved by any off-the-shelf Quadratic Programming (QP) solver 1 . Repeat to solve the problem of Eq.(2) for each instance, we can achieve the reconstruction weight matrix V = [v1, · · · , vn]⊤ ∈ Rn×n . Then, we normalize V by row, i.e., V ← VD-1 , where D = diag[d1, · · · , dn], di = ∑nj=1 vij .

[Step 2]: Following the idea that the relationships of instances can be translated to their associated labels, we can enrich the labeling information by propagating over Ω with V. Formally, we denote by F = [f1, · · · , fn]⊤ ∈ Rn×l + the label propagation solution, which is initialized by the candidate label matrix Y, i.e., F(0) = Y. Then, F can be iteratively updated by propagating over Ω with V until convergence. At each iteration t, the update equation is given by:

1 We apply the public QP solver of mosek downloaded at https://www.mosek.com/

Algorithm 1 Unconstrained label propagation for ̂Y

Input: The PML dataset D = {X,Y}, nearest neighbor number k and propagation rate α;

Output: The label enrichment matrix ̂Y.

• 1: Construct the kNN graph of X, and initialize F(0) by Y
• 2: Compute V by solving Eq.(2) for each instance, and then normalize it by row
• 3: While not convergence Do
• 4: Update F using Eq.(3)
• 5: Normalize F using Eq.(4)
• 6: EndWhile
• 7: Compute ̂Y using Eq.(5)

Algorithm 2 Predictive model induction for PML3 ER

Input: The enriched PML dataset ̂D = {X, ̂Y}, regularization parameters {λ1, λ2};

Output: The predictive parameter matrixW.

• 1: Initialize {C,B,W, ̂B,Θ}
• 2: While not convergence Do
• 3: Update C using Eq.(10)
• 4: For t = 1 to Niter
• 5: Update ̂B,B,Θ using Eqs.(13), (14) and (15)
• 6: End For
• 7: UpdateWusing Eq.(17)
• 8: EndWhile

where α ∈ [0, 1] is the propagation rate. To avoid overestimate non-candidate labels, we normalize each row of F(t) :

where vmin(f (t) i ) denotes the minimum of f (t) i , and cvmax(f (t) i ) the maximum over candidate labels in f (t) i . [Step 3]: After obtaining the optimal F, denoted by F∗ = [f ∗ ij ]n×l, we compute the label enrichment matrix ̂Y as follows:

For clarity, we summarize the unconstrained label propagation for ̂Y in Algorithm 1.

3.2 Jointly Learning the Ground-truth Confidence and Multi-label Predictor

In the second stage, PML3 ER jointly trains the ground-truth confidence matrix C = [cij]n×l ∈ [0, 1]n×l and multi-label predictor given the enrichment version of PML dataset ̂D = {X, ̂Y}.

First, we aim to recover C from ̂Y by leveraging the following minimization:

where B = [bij]l×l denotes the label correlation matrix, and 0n×l the all zero matrix. Specifically for capturing local label correlations, we utilize the nuclear regularizer for B, i.e., ‖B‖∗, with the regularization parameter λ1.

Second, we aim to train a linear multi-label predictor with C by leveraging a least square minimization with a squared Frobenius norm regularization:

where W ∈ Rd×l is the predictive parameter matrix, and λ2 the regularization parameter.

By combining Eqs.(6) and (7), we achieve the overall objective as follows:

Discussion on RecoveringC from ̂Y. Referring to Eq.(6), we jointly learn the ground-truth confidence matrix C and label correlation matrix B by minimizing their reconstruction error of ̂Y. By omitting the regularizers, it can be roughly reexpressed below:

Obviously, for each component ̂ yij, it contributes that any cih tends to be larger or smaller given larger value of bhj (i.e., a higher correlation between label j and h), if ̂ yij corresponds to a candidate label (≥ 0) or a non-candidate one (≤ 0). That is, we actually recover C using the information from candidate and non-candidate labels simultaneously.

Optimization

As directly solving the objective of Eq.(8) is intractable, we optimize the variables of interest, i.e., {C,B,W}, via alternating fashion, by optimizing one variable with the other two fixed. Repeat this process until convergence or reaching the maximum number of iterations. We describe the update equations of {C, B,W} one by one.

[Update C] When {B,W} are fixed, the sub-objective with respect to C can be reformulated as follows:

This optimization refers to a convex optimization, so as to achieve the following truncated update equation:

where C′ = [c′ij ]n×l:

Algorithm 3 Full algorithm of PML3 ER

Input: The PML dataset D = {X, Y}, k = 10, α = 0.5 and {λ1, λ2};

Output: The predictive parameter matrixW.

• 1: Compute the label enrichment matrix ̂Y using Algorithm 1
• 2: OptimizeWusing Algorithm 2 given D = {X, ̂Y}

[Update B] When {C,W} are fixed, the sub-objective with respect to B can be reformulated as follows:

Following the spirit of Alternating Direction Method of Multipliers (ADMM) [Boyd et al., 2011], we convert Eq.(11) into an augmented Lagrange problem with an auxiliary matrix ̂B ∈ Rl×l and Lagrange parameter matrix Θ ∈ Rl×l :

where τ is the penalty parameter. We perform an inner iteration to alternatively optimizing each of {̂B,B,Θ} with the other two fixed. After some simple algebra, the update equations are formulated as follows:

For B, it can be directly solved by

where SVDλ1 τ (·) is the singular thresholding with λ1 τ [Cai et al., 2010]. Then, for Θ, it can be updated by:

[Update W] When {C, B} are fixed, the sub-objective with respect toWcan be reformulated as follows:

The problem has an analytic solution as follows:

For clarity, we summarize the procedure of this predictive model induction in Algorithm 2.

3.3 PML3 ER Summary

We describe some implementation details of PML3 ER. First, following [Fang and Zhang, 2019], we fix the parameters of the unconstrained label propagation as: k = 10 and α = 0.05. Second, we empirically fix the penalty parameter τ of ADMM as 1. Third, the maximum iteration number of both ADMM loops is set to 5, as to be widely known, ADMM basically converges fast. Overall, the PML3 ER algorithm is outlined in Algorithm 3.

Time Complexity. We also discuss the time complexity of PML3 ER. First, in the unconstrained label propagation procedure, we require O(n2d2 ) time to construct the weighted kNN graph, and O(T1n2 l) time to obtain the label enrichment matrix, referring to Eq.(3), where T1 denotes its iteration number. Second, in predictive model induction, the major computational costs include matrix inversion and SVD, requiring roughly O(T2(d3 +n2 l)) time, where T2 denotes the iteration number of the outer loop 2 . Therefore, the total time complexity of PML3 ER is O(n2d2 + T1n2 l + T2(d3 + n2 l)).

4 Experiment

4.1 Experimental Setup

Datasets

In the experiment, we downloaded five public multi-label datasets from the mulan website 3 , including Genbase, Medical, Arts, Corel5k and Bibtex. The statistics of those datasets are outlined in Table 1.

To conduct experiments under the scenario of noisy supervision, we generate synthetic PML datasets from each original dataset by randomly drawing irrelevant noisy labels. Specifically, for each instance, we create the candidate label set by adding several randomly drawn irrelevant labels with a% number of ground-truth labels, where we vary a over the range {50, 100, 150, 200}. Besides, to avoid useless PML instances annotated with all l labels, we fix each candidate label set at most l - 1 labels. Accordingly, a total of twenty synthetic PML datasets are generated.

Baseline Methods

We employed five baseline methods for comparison, including three PML methods and two traditional methods of Multilabel Learning (ML). For the ML ones, we directly train them over the synthetic PML datasets by considering all candidate labels as ground-truth ones. We outline the method-specific settings below.

• PML-fp [Xie and Huang, 2018]: A PML method with a ranking loss objective weighted by ground-truth confidences. We utilize the code provided by its authors, and tune the parameters following the original paper. Here, the other version of [Xie and Huang, 2018], i.e., PMLlc, was neglected, since it performed worse than PML-fp in our early experiments.

2 Here, we omit the iteration numbers of inner ADMM loop for

B, since it converges very fast.

3 http://mulan.sourceforge.net/datasets-mlc.html

• PARTICLE-MAP [Fang and Zhang, 2019]: A two-stage PML method with label propagation. We employ the public code 4 , and tune the parameters following the original paper. Here, the other version of [Fang and Zhang, 2019], i.e., PARTICLE-VLS, was neglected, since it performed worse than PARTICLE-MAP in our early experiments.
• PML-LRS [Sun et al., 2019]: A PML method with candidate label decomposition. We utilize the code provided by its authors, and tune the regularization parameters over {10i |i = -3, · · · , 1} using cross-validations.
• Multi-Label k Nearest Neighbor (ML-kNN) [Zhang and Zhou, 2007]: A kNN ML method. We employ the public code 5 implemented by its authors, and tune its parameters following the original paper.
• Multi-label learning with Label specIfic FeaTures (LIFT) [Zhang and Wu, 2015]: A binary relevance ML method. We employ the public code 6 implemented by its authors, and tune its parameters following the original paper.

For our PML3 ER, the regularization parameter λ1 is fixed to 1, and λ2 is tuned over {10i |i = 1, 2} using 5-fold cross validation results.

Evaluation Metrics

We employed seven evaluation metrics [Zhang and Zhou, 2014], including Subset Accuracy (SAccuracy), Hamming Loss (HLoss), One Error (OError), Ranking Loss (RLoss), Average Precision (AP), Macro Averaging F1 (Macro-F1), Micro Averaging F1 (Micro-F1), where both instance-based and label-based metrics are covered. For SAccuracy, AP, Macro-F1 and Micro-F1, the higher value is better, while for HLoss, OError and RLoss, a smaller value is better.

4.2 Experimental Results

For each PML dataset, we randomly generate five 50%/50% training/test splits, and evaluate the average scores (±standard deviation) of comparing algorithms. Due to the space limitation, we only present detailed results of RLoss, AP and Macro-F1 in Table 2, while the observations of other metrics tend to be similar. First, we can observe that PML3 ER outperforms other three PML methods in most cases, where PML3 ER dominates the scenarios of AP and Macro-F1 on different noise levels. Especially, the performance gain over PARTICLE-MAP indicates that using the information from non-candidate labels is beneficial for PML. Besides, we can see that PML3 ER significantly performs better than the two traditional ML methods in most cases, since they directly use noisy candidate labels for training.

Additionally, for each PML dataset and evaluation metric, we conduct a pairwise t-test (at 0.05 significance level) to examine whether PML3 ER is statistically different to baselines. The win/tie/loss counts over 20 PML datasets and 7 evaluation metrics are presented in Table 3. We can observe that PML3 ER significantly outperforms the PML baseline methods PARTICLE-MAP, PML-LRS and PML-fp in 91.4%, 86.4% and 91.4% cases, and also outperforms the two traditional MLL methods ML-kNN and LIFT in 95.7% and 85% cases. Besides, on the results of evaluation metrics, PML3 ER achieves significantly better scores. For example, the SAccuracy, OError, AP, Macro-F1 and Micro-F1 of PML3 ER are better than all comparing algorithms in 95% cases.

4 http://palm.seu.edu.cn/zhangml/files/PARTICLE.rar

5 http://palm.seu.edu.cn/zhangml/files/ML-kNN.rar

6 http://palm.seu.edu.cn/zhangml/files/LIFT.rar

4.3 Parameter Sensitivity

We empirically analyze the sensitivities of the regularization parameters {λ1, λ2} of PML3 ER. For each one, we examine the AP scores by varying its value from {10i |i = -3, · · · , 3} across PML datasets with a = 100 by holding the other two fixed. The experimental results are presented in Fig.2. First, we can observe that the AP scores of λ1 seem quite stable over different types of PML datasets. That is, we empirically conclude that PML3 ER is insensitive to λ1, making PML3 ER more practical. Second, for λ2, it performs better with the values of {10i |i = 1, 2} across all PML datasets, which are the settings used in our experiment.

5 Conclusion

We concentrate on the task of PML, and propose a novel twostage PML3 ER algorithm. In the first stage, PML3 ER performs an unconstrained label propagation procedure to estimate the label enrichment, which simultaneously involves the relevance degrees of candidate labels and irrelevance degrees of non-candidate labels. In the second stage, PML3 ER jointly learns the ground-truth confidence and multi-label predictor given the label enrichment. Extensive experiments on PML datasets indicate the superior performance of PML3 ER.

Acknowledgments

We would like to acknowledge support for this project from the National Natural Science Foundation of China (NSFC) (No.61602204, No.61876071, No.61806035, No.U1936217)