Discriminative and Correlative Partial Multi-Label Learning

1 Introduction

In multi-label learning (MLL) tasks, an object can be associated with multiple labels simultaneously. A lot of recent works have witnessed the rapid development of MLL in many research areas, e.g. text categorization [Lin et al., 2018], image/video annotation [Yang et al., 2018], music emotion recognition [Trohidis et al., 2008], and gene function prediction [Fodeh and Tiwari, 2018].

A common assumption in traditional MLL tasks is that the training instances are precisely annotated. Unfortunately, in many real-world applications, it is difficult to obtain noisy-free labels but alternatively, a set of candidate labels are accessible. This scenario is referred as to partial multilabel (PML) learning which is formalized by [Xie and Huang, 2018]. Formally, let X = Rp be the d-dimensional feature space and Y = {y1, y2, ...yq} be the q-dimensional label space. Given a PML training dataset D = {(xi, Yi)|1 ≤ i ≤

∗Corresponding Author.

n} where xi ∈ X is the instance vector and Yi ⊆ Y is the candidate label set, the goal of PML is to learn a multi-label predictor f : X ↦→ Y from D. PML makes a basic assumption that the ground-truth label set ˆ Yi of an instance xi is concealed in its candidate label set, i.e. ˆ Yi ⊆ Yi, and is invisible to the predictor.

The most intuitive way is to regard all the candidate labels as valid ones. Then the PML problem can be solved by any off-the-shelf multi-label learning algorithms, e.g. Binary Relevance (BR) [Zhang and Zhou, 2014], Classifier Chains [Liu et al., 2017], CPLST [Chen and Lin, 2012] and so on. However, such a strategy neglects the false positive labels in the candidate label set, which may lead to insufficient label correlation extraction and in turn the performance degenerates.

In order to tackle this problem, a few PML techniques are proposed. Some methods focus on disambiguation by assigning a confidence value for each candidate label to estimate how likely it is a correct label. For example, Xie and Huang [2018] propose two effective approaches PML-lc and PMLfp where the confidence scores are calculated by minimizing a confidence-weighted ranking loss. Nonetheless, when the proportion of false positive labels is high, the algorithms are error-prone due to the alternative optimization strategy. PARTICLE [Fang and Zhang, 2019] utilizes the nearest neighbors in the feature space to identify the credible labels with high labeling confidences through an iterative label propagation procedure. Then it applies the pair-wise label ranking technique to induce a multi-label predictor. However, it only extracts second-order label correlations and hence may achieve degenerated performance on complex datasets. fPML [Yu et al., 2018] is another popular PML approach that concentrates on exploring label correlations. It follows the classic label embedding paradigm and can only handle those datasets whose label spaces are highly sparse. We observe that existing PML methods pay attention to either candidate label set disambiguation or label correlation extraction. As a result, their predictive performance is limited.

To bridge this gap, we propose a novel two-stage PML approach named DiscRiminative and correlAtive partial Multilabel leArning (DRAMA). In the first stage, we generate a real-valued label confidence matrix under the guidance of feature manifold and the candidate label set. To achieve the goal of disambiguation, we make the smoothness assumption [Zhu et al., 2005] that the examples close to each other in the feature space are prone to share the same labels. Based on the our assumption, the feature and label spaces share a similar local topological structure which could be captured by the sparse reconstruction relationships among each instance and its nearest neighbors. In the second stage, based on the label confidences, we present a gradient boosting algorithm for our proposed multi-output regression problem. In each boosting round, the learned labels are used to augment the feature space, and thus the label correlations can be effectively extracted to improve the generalization performance. Extensive experimental results demonstrate that our proposed method outperforms other state-of-the-art partial multi-label learning algorithms.

The rest of the paper is organized as follows. The next section briefly discusses some related works on partial multilabel learning. The technical details of the proposed DRAMA are presented in the Section 3. Section 4 reports our experimental results on various real-world datasets. Finally, concluding remarks are provided in the last section.

2 RelatedWork

The goal of partial multi-label learning is to deal with the imprecise tagging problem in multi-label learning. Hence, PML integrates two popular learning framework: multi-label learning and partial label learning.

Partial label learning (PLL) is a weak-supervised multiclass learning framework where each instance is tagged by a set of candidate labels. Note that the relevant label is guaranteed to be contained in the candidate label set and the remaining labels are termed as false positive labels or distractor labels. To learn from these ambiguous examples, one intuitive strategy is to aggregate the output to optimize the objective such as margin [Nguyen and Caruana, 2008] or likelihood [Jin and Ghahramani, 2002; Cour et al., 2011] over training examples. Problem transformation is another popular strategy and is adopted by many algorithms. For instance, [Zhang et al., 2017; Wu and Zhang, 2018] construct multiple binary label datasets from the original partial label dataset, and then the PLL task is decomposed to a set of binary learning tasks. Other data transformation methods learn label structure from feature space [Zhang and Yu, 2015] to obtain a new numerical dataset whose labels are confidence vectors.

In multi-label learning (MLL), an object can be associated with multiple labels. It has attracted huge attention of researchers from different domains [Yang et al., 2018; Fodeh and Tiwari, 2018]. Binary Relevance [Zhang and Zhou, 2014] is one of the most straightforward solutions for MLL, which aims to decompose the MLL task to a series of independent single label classification problems. Despite its computational efficiency, BR ignores the correlations between labels and thus generally underperforms. To tackle this problem, many MLL algorithms are proposed, such as tree-based [Liu and Tsang, 2017] methods, embeddingbased [Yeh et al., 2017; Chen and Lin, 2012] approaches, and augmentation-based [Liu et al., 2017] algorithms.

Obviously, the biggest challenging issue for partial multilabel learning is how to simultaneously disambiguate the correct labels and exploit the label correlations. To address this issue, we propose an effective PML algorithm DRAMA, which marries the concepts of problem transformation in PLL and feature augmentation in MLL.

3 The ProposedMethod

In this section, we present the details of DRAMA.

3.1 Candidate Label Set Disambiguation

To explore the underlying structure of feature space, we first build a weighted graph G = (V, E,W) from the given training dataset D. Here V = {xi|1 ≤ i ≤ n} denotes the vertex set and E = {(xi, xj)|i ̸= j, xj ∈ kNN(xi)} denotes the edge set where kNN(xi) is the set of xi's k-nearest neighbors. W = [wij ]n×n is a non-negative weight matrix where wij = 0 if (xi, xj) ̸= E. For each example xi, we assume that it can be linearly reconstructed from its nearest neighbors and the sparse reconstruction error can be expressed as follows,

It is noteworthy that the l1-regularization can actually be regarded as n constraints 1⊤wj = 1 (1 ≤ j ≤ n). Moreover, since columns in W are independent to one another, we can obtain a series of standard constrained least square programming problems to minimize E(W),

where wj is the j-th column vector of W. Here Gj is the local Gram matrix for xj with Gjab = (xj - xa)⊤(xj - xb). By solving Eq. (2), the local topological information is embodied in the graph, which can be utilized to disambiguate the partially labeled data. Note that W is usually asymmetric because the importance of xi in reconstructing xj is generally different from the inverse case.

According to the smoothness assumption, the feature and label spaces are prone to share the same topological structure. Hence, the feature manifold can be transferred to a numerical label space. Formally, we can reconstruct the labels through the following minimization problem,

where U = [u1,u2, ..., un] = [uij]n×n is the transformed label matrix, i.e. the confidence matrix. Here δ1 and δ2 are positive constants.

It is worth pointing out that Eq. (3) is meticulously designed. The first constraint comes from the multi-label setting, i.e. there might be multiple relevant labels. Then, the original label information is preserved through the subsequent constraints. The sign of each element in U indicates whether the corresponding label is relevant or irrelevant and the magnitude reflects the relative confidence of the relevance. The threshold parameters also play an important role in our algorithm. As illustrated in Figure 1, with a small δ1, the groundtruth labels can obtain relatively high positive confidences and the false positive labels generally get low or even negative confidences. Moreover, with a relative bigger δ2, the confidences of irrelevant labels are forced to be negative enough.

Remark that we do not aim to perform dimension reduction [Gao et al., 2018; 2019] in the feature space. The instance matrix and the confidence matrix have different semantic information and are in two independent spaces that merely share the same local topological structure. Furthermore, our disambiguation strategy has three main advantages: 1) all the optimization problems are standard quadratic programming (QP) problems and can be efficiently solved; 2) the logical labels are extended to numerical labels, which helps enrich the original label space; 3) the labels are treated in an unequal manner which prevents the ground-truth labels being overwhelmed by distractor labels.

3.2 Correlative Multi-Label Predictor Inducing

In the second stage, we begin with transforming the training dataset to its disambiguated counterpart ˜D0 = {(xi,ui)|1 ≤ i ≤ n}. Since our new labels are numerical, we have to treat the learning problem as a multi-output regression problem now. There are a number of effective algorithms proposed, such as multi-regression support vector machines [Chung et al., 2015], metric learning based regressor [Liu et al., 2019] and so on. Nevertheless, most of existing multi-output regressors ignore the correlations among the labels and hence achieve degenerated performance. Consequently, we introduce a novel gradient boosting based model that manipulates the feature space in each boosting round.

We first induce a simple BR regression model f0 : X ↦→ ˆ Y from ˜D0 where ˆ Y denotes the numerical label space. Any offthe-shelf base regressor can be utilized, such as classification and regression tree (CART) [Liaw et al., 2002], support vector regressor (SVR) [Chung et al., 2015] and many others. Then we can obtain a predicted label matrix ˆU 0 = f0(X) where X is the instance matrix. Note that such a simple BR model usually underperforms for two reasons: 1) the generalization performance of BR is restricted to the base classifiers; 2) the label correlations are neglected. Thus, we boost it by incorporating a set of correlation aware regressors.

Formally, our goal is to induce a regressor F that minimizes the following loss function,

where || · ||F is the Frobenius norm. In order to find the optimal solution, we adopt an ensemble model by adding weak learners to the BR model using a gradient descent like procedure. Specifically, in t-th boosting round, a weak regressor ft is trained to fit the negative gradient of L at Ft-1(X),

where Rt = [rt1 , rt2 , ..., rtn ]. To exploit the label correlations, we further augment the original feature space using previously learned labels ˆU t-1 = [ˆut-1 1 , ˆut-1 2 , ..., ˆut-1 n ] = Ft-1(X). In other words, each weak regressor ft(X, ˆU t-1 ) is induced from the following training dataset,

Finally, we can sum up all the weak learners to obtain a robust model,

where T is the number of iterations. Here λt is the learning rate and can be calculated by,

In this work, we choose CART as our boosting weak learners. Since CART is a non-linear model, even complex label correlations can be explored. When an unseen instance x∗ is given, we can feed it in to F and then take the sign of the real-valued outputs to get logical labels.

It is worth noting that our model has two main superiorities: 1) the learned weak regressors can help improve the generalization ability of our simple BR model; 2) the boosting procedure is in a coarse-to-fine prediction manner and thus the label correlations can be effectively exploited as the iterations proceed.

Figure 2: Performance of DARAMA changes as the number of nearest neighbors k changes from 5 to 10 on 4 datasets.

boosting) as the base learners. Specifically, Gaussian kernel is equipped by SVM and SVR to handle non-linear separable cases. The number of boosting rounds is fixed to 10. k is set as 10 for all the nearest neighbor based algorithms. For CPLST, we take the first 5 principal components. Following the experimental setting in [Fang and Zhang, 2019], we set thr = 0.9 and α = 0.95 for PARTICLE.

Evaluation Metrics

Inspired by [Trohidis et al., 2008; Lin et al., 2018], we consider three widely-used multi-label learning metrics to evaluate the predictive performance of all the comparing methods, i.e. Micro-F1, Macro-F1 and Example-F1.

4.2 Results

Table 3 lists the performance of each comparing algorithm in terms of Micro-F1, Macro-F1 and Example-F1. Figure 2 illustrates the parameter sensitivity of DRAMA w.r.t. the number of nearest neighbor k. From the results, we conclude that:

• The proposed DRAMA generally achieves the best performance. For instance, on Emotions with 2 average candidate labels, in terms of Micro-F1, Macro-F1, Example-F1, DRAMA improves the best results of the baselines (except N-DRAMA) by 5.52%, 3.45%, 9.83% respectively. The results listed above validate the superiority of the proposed method.
• BR and PML-kNN is inferior to other methods due to the ignorance of label correlations. CPLST addresses this issue by label embedding and obtains excellent results on Emotions and CAL500 datasets. However, it is prone to be misled by false positive labels and thus underperforms on other datasets.
• N-DRAMA works well on many datasets, which proves the effectiveness of our disambiguation strategy. Nev-

4 Experiments

4.1 Settings

Datasets

Since PML is a newly proposed framework and there are no public partial multi-label learning datasets available yet, we synthesized a number of PML datasets from 5 multi-label datasets. These datasets are collected from various real-world tasks: Image [Fang and Zhang, 2019] and Scene [Boutell et al., 2004] for image annotation, Slashdot [Read et al., 2011] for text categorization, Cal500 [Turnbull et al., 2008] and Emotions [Trohidis et al., 2008] for music classification. For each example, we randomly select some irrelevant labels and aggregate them with ground-truth labels to obtain a candidate label set. Finally, a total of 16 datasets are synthesized whose characteristics are reported in Table 1. All the datasets are randomly partitioned to 80% for training and the rest for testing. We conduct all the experiments for 5 times and the mean metric values with standard deviations are reported.

Comparison Approaches

We compare our proposed method with two well-established multi-label classifiers and three partial multi-label methods:

• Binary Relevance (BR) [Zhang and Zhou, 2014]: BR is a classical one-vs-all MLL approach that breaks the original problem into binary classification tasks.
• CPLST [Chen and Lin, 2012]: it is a typical label embedding approach in MLL, which integrates the concepts of principal component analysis and canonical correlation analysis.
• PARTICLE [Fang and Zhang, 2019]: it transforms the PML task to a multi-label problem through a label propagation procedure. Then a calibrated label ranking model is induced to instantiate two effective PML methods P-VLS and P-MAP.
• PML-kNN: we further induce a k-nearest neighbor model from the PML datasets and an averaging strategy is adopted to obtain the predictions.

To validate the superiority of our gradient boosting procedure, we further propose a Na¨ıve-DRAMA (N-DRAMA) method that uses only a simple BR model in the second stage.

In this paper, δ1, δ2 are empirically set as 0.01, 1 for Cal500 and 0.01, 0.5 for other datasets. The QP problems are solved by interior-point method. For BR and our models, we employ Scikit-learn's [Pedregosa et al., 2011] implementation of SVM (for BR), SVR (for f0), and CART (for gradient ertheless, DRAMA is better than N-DRAMA, because it further considers high-order label correlations.

• It is worth noting that P-VLS and P-MAP are competitive to other methods, but underperform our DRAMA. Since PARTICLE only models second-order label dependencies, its generalization ability is limited.
• Our method is relatively stable with varying values of k.

4.3 Further Analysis

In addition, we evaluate all the methods on six synthesized PML datasets in the transductive setting, i.e. there is no testing data. The transductive performance of a PML algorithm manifests its disambiguating ability to the candidate label sets. The experimental results are reported in Table 2. We can observe that our method is the most successful on all datasets. For example, on Image with 3 average candidate labels, in terms of Micro-F1, Macro-F1, Example-F1, DRAMA improves the best results of the baselines (except N-DRAMA) by 5.7%, 5.1%, 5.4% respectively.

5 Conclusion

This paper focuses on the challenging problem of disambiguation and label correlation extraction in partial multilabel learning. We propose a novel two-stage DiscRiminative and correlAtive partial Multi-label leArning (DRAMA) algorithm that marries the concepts of problem transformation in PLL and feature augmentation in MLL. The resultant algorithm firstly disambiguates the candidate label sets by exploring the feature and label manifolds. Then we induce a gradient boosting regressor to utilize the elicited label information. In each boosting round, the original feature space is augmented by the elicited labels such that the high-order label correlations are exploited. Our empirical studies on a range of real-world datasets demonstrate that DRAMA can effectively handle PML tasks.

Acknowledgments

This work is supported by National Key R&D Program of China (2017YFB1201001). It is completed when the authors Yang Zhao and Chen Zhang are in inAI Lab, ZJUINA.