Multi-Label Co-Training

1 Introduction

In multi-label learning, each sample is associated with several related class labels [Zhang and Zhou, 2014; Gibaja and Ventura, 2015]. Let X ∈ Rn×d be the data matrix including n d-dimensional samples, and Y ∈ Rn×q be the qdimensional label space for the samples. Given a training dataset D = {(xi, yi))|1 ≤ i ≤ n}, the task of multi-label learning is to learn a predictive function f(x) ∈ Rq that maps the input feature space of the samples onto the label space.

Most multi-label learning methods train the predictor using only labeled samples [Zhang and Zhou, 2007; Bucak et al.,

∗Guoxian Yu is the corresponding author.

2011; Huang and Zhou, 2012; Yu et al., 2014]. Given the exponential size of the power set of the labels, a very large number of labeled training samples is generally required. In practice, collecting sufficient labeled samples in this scenario is very expensive, and often impractical. On the other hand, with the rapid advancement of data collection and storage techniques, it has become feasible to collect a large number of unlabeled samples. Inspired by single-label semi-supervised learning [Zhu, 2008], efforts have been made to leverage both labeled and unlabeled samples for multi-label learning, giving promising results [Qian and Davidson, 2010; Yu et al., 2012; Kong et al., 2013; Wu et al., 2015; Zhang and Yeung, 2009; Zhang et al., 2015b]. The nature of this work, though, is typically transductive; that is, the canonical approach is to construct a graph that captures the connections between labeled and unlabeled instances, and then to predict the labels of the unlabeled instances embodied in the graph. As such, this approach cannot generalize to unseen samples. It is obviously desirable to empower the learner with an inductive ability that enables label prediction for new instances unseen during training.

Few attempts have been made to achieve inductive semisupervised multi-label learning [Guo and Schuurmans, 2012; Wu and Zhang, 2013; G¨onen, 2014; Tan et al., 2017; Zhan and Zhang, 2017]. In [Guo and Schuurmans, 2012], the authors utilized unlabeled and labeled instances to learn a subspace representation, while simultaneously training a supervised large-margin multi-label classifier on the labeled instances, which could be directly applied to unseen instances. In [Wu and Zhang, 2013], the authors took advantage of label correlations in labeled instances and of maximum-margin regularization over unlabeled instances to optimize a collection of linear predictors for inductive multi-label classification. In [G¨onen, 2014], the author proposed a Bayesian semi-supervised multilabel learning (BSSML) approach that combines linear dimensionality reduction with linear binary classification under a low-density assumption. In [Tan et al., 2017], the authors introduced SMILE, which first estimates the missing labels of labeled samples and uses a graph to embody both labeled and unlabeled samples; it then trains a graph-regularized semi-supervised linear classifier, to further recover the missing labels of labeled samples, and to directly predict labels of unseen new samples. In [Zhan and Zhang, 2017], the authors introduced an inductive semi-supervised multi-label learning using a co-training approach called COINs. Specifically, to enable single view co-training, COINs first optimizes two disjoint feature views from the whole feature space by maximizing the diversity between two classifiers independently trained on the two views [Chen et al., 2011], and then iteratively communicates the pairwise ranking predictions of either classifier on unlabeled instances for model refinement. COINs communicates only the single predicted most relevant label and the single predicted most irrelevant label between two classifiers. However, multi-label instances are often simultaneously associated with several relevant and irrelevant labels, and not just a single one. For this reason, only communicating the two most relevant and irrelevant labels may mislead the refinement process, and may not achieve pronounced performance improvement. Furthermore, COINs only focuses on two views.

To fully accomplish inductive multi-label classification and to leverage labeled and unlabeled instances of multiple feature views, we advocate the integration of multi-label learning with the well-established co-training paradigm [Blum and Mitchell, 1998; Zhou and Li, 2005]. Co-training has a natural inductive classification ability. It mutually communicates the labels predicted with most confidence among classifiers, which are independently trained on the respective views of data, thus augmenting the labeled training sets. The classifiers are then independently retrained on the respective augmented training sets; the communication and update iterate till convergence. Nevertheless, it is a difficult challenge to integrate multi-label learning with co-training. Two distinct issues should be addressed:

• (i) How to solve the widely-witnessed class-imbalance problem in multi-label learning. For multi-label datasets, the number of samples relevant to a label is generally much smaller than the number of samples irrelevant to that label. Furthermore, the number of relevant samples for different labels can vary significantly [Zhang et al., 2015a; Sun and Lee, 2017]. The class-imbalance problem can be exaggerated when communicating labels among learners during the iterative process of co-training.
• (ii) How to select the samples and communicate their predicted labels with confidence among multiple co-training classifiers. Unlike traditional co-training, the to-becommunicated samples can be associated with several labels, and not just one.

To address the above two issues in multi-label co-training, we propose a co-training based multi-label classification method called MLCT. MLCT first independently trains predictors on different views and makes prediction on unlabeled samples. Then, it uses the co-occurrence information of labels to adjust the predicted likelihoods and to deal with the class-imbalance problem. Next, it summarizes the adjusted likelihoods across views and measures the predictive confidence of samples based on the summarized likelihoods. After this, it selects samples with the highest confidence, applies label-wise filtering on the summarized likelihoods of the selected samples, and then communicates filtered labels among learners during the iterative co-training process. MLCT repeats the above iterative process till convergence and makes the final prediction on unseen samples by combining the predictions of the classifiers via a majority vote. An extensive comparative study shows that MLCT performs favorably against the recently proposed COINs [Zhan and Zhang, 2017] and other representative multi-label learning methods (including ML-KNN [Zhang and Zhou, 2007], MLRGL[Bucak et al., 2011], MLLOC[Huang and Zhou, 2012], BSSML[G¨onen, 2014] and SMILE[Tan et al., 2017]).

2 The MLCT Approach

The original co-training approach was applied to samples with multiple feature views [Blum and Mitchell, 1998], under the assumption that each feature view would provide sufficient and independent information to produce a classifier with a good generalization capability. In this paper, we mainly focus on mining multi-label samples naturally represented by multiple views. MLCT can also work on feature views generated by a particular view splitting technique [Chen et al., 2011; Du et al., 2011]. Let X = {Xv }mv=1 be m view representations of n samples, where each viewXv ∈ Rn×dv . xvj ∈ R1×dv is the dv-dimensional feature vector for the j-th sample in the v-th view, and yj ∈ {±1}q is the q-dimensional label vector for the j-th sample, where yj,c = +1(-1) indicates whether the c-th (1 ≤ c ≤ q) label is relevant (irrelevant) for the sample. Without loss of generality, we assume that the first l samples are labeled and the remaining u = n - l (l ≪ u) samples are unlabeled, L = {(xj , yj )}lj=1 , U = {xj}nj=l+1 .

The goal of MLCT is to perform multi-label co-training on X and {yj}nj=1 , and to make accurate predictions on unseen new samples. To accomplish this goal, MLCT first uses correlations of labels to address the widely witnessed classimbalance problem in multi-label learning, and to adjust the predicted label confidence values of samples. Next, it introduces a confidence measure to select samples, performs label-wise filtering on the predicted label confidence values of the selected samples, and communicates their labels among classifiers. The following subsections elaborate on the above two steps.

2.1 Addressing Class-imbalance via Label Correlation

In multi-label learning, labels have much fewer relevant samples than irrelevant ones, and the number of relevant samples varies significantly across labels [Zhang et al., 2015a]. This class-imbalance issue can become even more pronounced during the iterative process of label communication in co-training. Inspired by the class-imbalance solutions for multi-label learning proposed in [Zhang et al., 2015a; Sun and Lee, 2017], MLCT makes use of label correlation to address class-imbalance in multi-label co-training.

Two labels c1 and c2 are considered as positively correlated if they often co-occur as sample labels, and their correlation can be empirically estimated as follows:

where [·] is true if and only if the condition is met. C(c2, c1) represents the probability that a sample is labeled as c2, given that it's already labeled as c1. Although c1 and c2 might coexist for some samples, the number of relevant samples for c1 might be far less than that of c2, or vice versa. As such, we separately compute C(c2, c1) and C(c1, c2) (C(c2, c1) ̸= C(c1, c2)) to account for the imbalance phenomenon.

Suppose f v j = [f v j,1 , · · · , f v j,q ] ∈ Rq is the likelihood of xvj with respect to q labels in the v-th view, initially predicted by a specific multi-label classifier (i.e., ML-KNN [Zhang and Zhou, 2007]) and trained on the l labeled samples. To address the class-imbalance problem, MLCT makes use of label correlation to adjust the predictive confidence values of labels as follows:

pvj,c is the updated likelihood of the c-th label for xvj . It follows the form of a logistic regression function to enforce that the adjusted value is within the range (0, 1). wj,c and w+ j,c are computed as follows:

where w+ j,c (wj,c ) reflects the confidence that c is a relevant (irrelevant) label for xvj . △ (a) is an indicator function; it's equal to 1 when a > 0, and to 0 otherwise. ∑qc2=1 △ (C(c, c2))-1 counts the number of labels positively correlated with the c-th label (c excluded). ∑qc2=1,c2̸=c f v j,c2C(c, c2) indicates how much information the other labels, which are correlated with the c-th label, contributes to the relevance between c and xvj . It is evident that the larger the margin w+ j,c - wj,c is, the more confident the prediction is. The margin indirectly reflects the relevance of the c-th label to xvj .

Eq. (2) is used to solve the class-imbalance problem via co-occurrence between labels, which not only considers the condition where xvj contains the c-th label, but also takes the reverse case into account (i.e., the c-th label does not belong to the label set of xvj ). With the correlations between labels as extra information, the impact of the class-imbalance issue can be effectively reduced.

2.2 Communicating Label Information

It's crucial to be able to communicate with confidence samples and labels among classifiers during the iterative process of co-training. A good communication strategy helps obtaining a pronounced and stable performance [Du et al., 2011]. Traditional co-training methods directly select samples with the most confident predictions for communication and model refinement [Blum and Mitchell, 1998; Zhou and Li, 2005; Levati et al., 2017]. However, for co-training with multi-label samples, since a sample may be annotated with several correlated labels, how to communicate labels with confidence is more challenging. As an inductive multi-label co-training algorithm, COINs [Zhan and Zhang, 2017] deals with this challenge by communicating the single positive and single negative labels of an unlabeled example predicted with the largest confidence. As such, the refined model may be misled by the two communicated labels, and may result in performance degeneration.

A sample in different views should share the same relevant labels. To select samples and labels to be propagated with confidence, MLCT first summarizes the prediction reliability based on m-1 views (the v-th view is excluded), and measures the overall prediction reliability of the j-th sample with respect to the c-th label as follows:

where |pv′ j,c - (1 -pv′ j,c )| is the prediction reliability of the c-th label of xv′ j . It's straightforward to see that a larger ˜hvj,c value indicates that the m- 1 classifiers are more in agreement on whether c should, or should not, be a relevant label for the j-th sample.

By extending the estimation in Eq. (5) to q labels, MLCT measures the overall prediction reliability of the j-th sample as follows:

where larger ˜rvj values imply more consistent predictions across the classifiers, and this makes the j-th sample a good candidate for communication. As such, MLCT selects ub (ub ≪ u) samples corresponding to the largest ˜rvj values as the candidate sample set Bv to be communicated for classifier refinement.

Next, to identify confident labels of the selected samples during co-training, MLCT defines two threshold values for each label on each view as follows:

θv+(c) is the average predicted likelihood of the c-th label on the v-th view, estimated using plausible relevant samples; similarly, θv-(c) is the average predicted likelihood of the c-th label on the v-th view, estimated using plausible irrelevant samples. Since the sample distribution of each label is different, the above two threshold values are computed separately for each label. MLCT then uses the above threshold values to convert f v j,c into a binary label as follows:

MLCT then uses {bvj,c }mv=1 , and the feature information of the respective samples in the v-th view, to augment the labeled training set and to refine the classifier in the corresponding view. We do not apply sample-wise filtering here because different samples have a different number of relevant labels, and an appropriate filter threshold is difficult to pursue [Quevedo et al., 2012]. The pseudo-code of MLCT is summarized in Algorithm 1. MLCT first computes label correlations based on available labels (step 2). Then, it randomly selects ua unlabeled samples and puts them in the buffer pool B (step 3), and independently predicts label likelihoods of these samples in each view (step 4-7). Next, it summarizes adjusted likelihoods and the overall predictive reliability of these samples in each view, chooses ub samples with the largest reliability, applies label-wise filtering on the summarized predicted likelihoods, and forms the communication label sets (step 8-12). After this, it appends the communication label sets obtained from the respective views to the labeled sets, and removes it from the unlabeled set (step 13). After the maximum number of iterations is reached, MLCT finally returns the iteratively refined classifier of each view, and makes ensemble predictions for new samples via majority vote of the classifiers.

Algorithm 1 MLCT pseudo-code

Input:

• L: labeled samples set in m views;
• U: unlabeled samples set in m views;
• B: buffered unlabeled samples for co-training;
• t: maximum number of iterations for co-training;

ua, ub: buffer size and number of communication samples.

Output:

Hv : the prediction model on the v-th (1 ≤ v ≤ m) view.

• 1: For iter = 1 : t
• 2: Estimate label correlation C(c2, c1)(1 ⩽ c1, c2 ⩽ q) via Eq. (1);
• 3: Randomly pick ua samples from U and put them into B;
• 4: For v = 1 : m
• 5: Update classifier Hv based on L and make predictions on B;
• 6: Adjust the initially predicted likelihoods f v j,c (xvj ∈ B) via Eq. (2);
• 7: End For
• 8: For v = 1 : m
• 9: Calculate ˜rvj (1 ≤ j ≤ ua) via Eq. (6), then select ub samples from B with the largest ˜rvj and form the set Bv ;
• 10: Compute θv+(c), θv-(c)(1 ⩽ c ⩽ q) via Eq. (7);
• 11: Apply label-wise filtering on f v j,c (xvj ∈ Bv ) via Eq. (8), and form the communication label set ∆v = {bvj,c};
• 12: End For
• 13: Communicate∆= {∆v }mv=1 to {Hv }mv=1, augment the labeled training set L = L ⋃ ∆ and reduce the unlabeled training set U = U - ∆.
• 14: End For
• 15: Return {Hv }mv=1.

3 Experiments

3.1 Experimental Setup

We assess the effectiveness of MLCT on four publicly accessible multi-label datasets from different domains, with different numbers of views and of samples [Gibaja et al., 2016; Guillaumin et al., 2010]. These datasets are described in Table 1. We also have computed the average imbalanced ratio (ImR) for all labels of each dataset. ImR reflects the degree of class-imbalance, and it is defined as follows [Sun and Lee, 2017]:

Max(ImR) and Min(ImR) represent the largest and the smallest imbalanced ratios of q labels, respectively. The larger the difference between Max(ImR), Min(ImR), and ImR, the more imbalanced the dataset is. From the statistics in Table 1, we can see that the labels of the last three datasets are quite imbalanced.

We compare the performance of MLCT against six representative and related multi-label learning algorithms: MLKNN [Zhang and Zhou, 2007], MLRGL [Bucak et al., 2011], MLLOC [Huang and Zhou, 2012]), BSSML [G¨onen, 2014], SMILE [Tan et al., 2017] and COINs [Zhan and Zhang, 2017]. To enable experimental comparisons with multi-label learning methods on a single view, we concatenate the feature vectors of different views for each sample into a single vector, and use the latter as the input of the comparing methods. COINs performs the feature view splitting and classifier refinement during the iterative process, and optimizes two views using the concatenated feature vectors. MLCT directly refines m ML-KNN classifiers on the naturally split views during the iterative process.

We use five widely-used multi-label evaluation metrics: Hamming Loss (HammLoss), Average AUC (Area Under receiver operating Curve) (AvgAUC), Ranking Loss (RankLoss), One Error (OneError), and Average Precision (AvgPrec). Due to space limitation, we omit the formal definitions of these metrics; they can be found in [Zhang and Zhou, 2014; Gibaja and Ventura, 2015]. HammLoss requires transforming the predicted probabilistic label vector of a testing sample into a binary vector. Following the setting of ML-KNN, a label is considered relevant to the sample if its predicted probability is above 0.5, otherwise is considered irrelevant. The smaller the values of HammLoss, RankLoss, and OneError are, the better the performance is. As such, to be consistent with the other evaluation metrics, we report 1-HammLoss, 1-RankLoss, and 1-OneError instead. With the latter measures, larger values indicate a better performance.

3.2 Experimental Results and Analysis

To compute the performance of MLCT, we randomly partition samples of each dataset into a training set (70%) and a testing set (30%). For the training set, we again randomly select 10% samples as the initial labeled data (L) and the remaining as unlabeled data (U) for co-training. We independently repeat the above partition 10 times, and report the average results and standard deviations. For co-training based methods, the maximum number of iterations (t) is fixed to 30, the number of samples (ua) in the buffer pool B is fixed to ⌊u/t⌋, and the number of samples (ub) to be shared during the co-training process is fixed to ⌊5%ua⌋. The input parameters of the competitive methods are specified (or optimized) as indicated by authors in the codes or papers. Table 2 shows the results.

From Table 2, we can see that MLCT generally outperforms comparing methods on different datasets and across the used metrics. We used the signed rank test [Demˇsar, 2006] to check for statistical significance between MLCT and the other methods (except SMILE and MLLOC). All the p-values are smaller than 0.05. Both MLCT and COINs are multi-label co-training methods, and MLCT frequently outperforms the latter. This is because COINs only communicates the single positive and negative labels predicted with highest confidence during cotraining. Given the multi-label characteristics of multi-label samples, the two shared positive and negative labels may mislead the classifier update and thus degenerate the performance. In practice, we also randomly divided the concatenated view of the Pascal dataset into two views, and then applied MLCT on each view. Again, MLCT shows a better performance than COINs. MLCT runs much faster than COINs: their average runtimes on the first two datasets are 155.180 and 708.225 seconds, respectively. MLCT also outperforms two supervised multi-label solutions (ML-KNN and MLRGL), which uses different techniques for multi-label data classification. The performance margin shows the advantage of using unlabeled data for training. MLLOC explores label correlations locally and it holds comparable performance to MLCT, which employs label correlation globally. BSSML, SMILE, and MLCT use unlabeled data for training; BSSML loses to MLCT, and SMILE obtains comparable performance to MLCT. This fact suggests that co-training is an alternative and effective paradigm for using unlabeled data for semi-supervised multi-label learning. SMILE has higher AvgAUC than MLCT because the predicted likelihood vectors of SMILE are less sparse than MLCT. SMILE uses label correlation to replenish missing labels of instances before training the linear classifier, whereas MLCT directly uses the available label information for prediction.

Component Analysis

To further analyze the effect of the individual components of MLCT, we introduce four variants of MLCT:

• (i) MLCT(nC): does not adjust the initially predicted likelihoods; in other words, it does not explicitly tackle the classimbalance problem, and directly uses the initially predicted likelihoods during the whole iterative process.

(ii) MLCT(nS): first adjusts the initially predicted likelihoods, but randomly selects ub samples; it then follows the same process as MLCT.

(iii) MLCT(nF): first adjusts the initially predicted likelihoods and selects samples based on the summarized likelihoods ˜rvj ; it then communicates labels whose f v j,c >= 0.5 (as done by ML-KNN), without applying label-wise filtering on the summarized likelihoods.

(iv) MLCT(nCSF): does not adjust the initially predicted likelihoods, randomly selects ub samples, and then communicates labels whose f v j,c >= 0.5.

Figure 1 gives the results obtained with MLCT and its variants. Overall MLCT outperforms its variants, and MLCT(nCSF) usually has the lowest performance. MLCT(nF), MLCT(nS), and MLCT(nC) outperform MLCT(nCSF). MLCT(nC) is always better than MLCT(nCSF), and is worse than MLCT on various datasets,

(a) 1-RankLoss

especially on Core15k, which is the most imbalanced dataset. This observation indirectly reflects the effectiveness of addressing class-imbalance during the co-training process. Moreover, we can see that MLCT(nS), which randomly selects the same number of samples for communication, is always outperformed by MLCT. This fact shows the effectiveness of MLCT in selecting samples with high confidence. We used a signed rank test to verify the statistical significance of the results of MLCT and its variants, and all p-values are smaller than 0.02. These results support the fact that MLCT is effective in addressing class-imbalance, and is capable of communicating labels with confidence for multi-label co-training.

Parameter Sensitivity Analysis

As with other co-training methods [Blum and Mitchell, 1998; Zhou and Li, 2005; Zhan and Zhang, 2017], two input parameters (t and ub) may affect the performance of MLCT. We conduct additional experiments to study the sensitivity of MLCT with respect to these parameters. Due to space limitation, we report only the average results with respect to 1-HammLoss. In fact, results with respect to other metrics provide similar patterns and conclusions.

Figure 2(a) shows the results for MLCT under different values of t; ua and ub were set to ⌊u/t⌋ and ⌊5%ua⌋, respectively. MLCT has an increasing 1-HammLoss as t increases, and it reaches a plateau after 15 iterations. Initially, MLCT has a lower performance than ML-KNN; that is because ML-KNN is trained on the integrated view, whereas MLCT works on separate views. To further study the generalization ability of MLCT, we also investigate the performance of MLCT with MLRGL [Bucak et al., 2011] and BPMLL [Zhang and Zhou, 2006] as base classifiers (instead of ML-KNN), and report these results in Figure 2(a). Again, MLCT has a performance that is superior to that of the adopted base classifiers.

Figure 2(b) exhibits the 1-HammLoss of MLCT for different number of selected samples (ub) for communication, with ua fixed to 50, 100, 300, and 500, respectively. The results are average on three datasets. Emotions is excluded from this experiment, since its small number of samples prevents the same setting of ua as for the other datasets. MLCT holds a stable performance when the ratio ub/ua increases from 1% to 10%, and then shows a decreasing trend as ub/ua > 10%. This indicates that a reasonable number of samples can be easily selected to achieve an effective co-training for MLCT.

MLCT also applies label-wise thresholds (θv+(c) and θv-(c)) to filter positive and negative labels. Figure 2(c) shows the 1-HammLoss of MLCT under different offsets of these two thresholds. Particularly, +0.2 (-0.2) means increasing (decreasing) the respective threshold by 0.2. From the Figure, we can observe that directly using θv+(c) and θv-(c) (both with offset as 0) gives a better performance than other values. In practice, we also tested a threshold fixed to 0.5, and the obtained performance is lower than that of MLCT. These results demonstrate the importance of label-wise filtering. Irrespective of the offset for θv+(c), either decreasing or increasing θv-(c) downgrades the performance. This is because decreasing θv-(c) results in a more stringent rule for negative samples, whereas increasing θv-(c) causes the detection of positive samples as negative ones. On the other hand, when the offset for θv-(c) is 0, MLCT shows a stable performance for different offsets of θv+(c). This is because the number of relevant samples for label c is generally smaller than the number of irrelevant samples for this label; as such, MLCT can identify the relevant samples of the c-th label even with a moderately decreased or increased θv+(c). In practice, we investigated the margin (θv+(c)-θv-(c)) and found it is generally larger than 0.5 across all labels. This investigation shows that label-wise filtering is important for multi-label co-training and the adaptive threshold values are effective. In summary, from these results, we can conclude that MLCT is robust to key input parameters.

4 Conclusions

In this paper, we study the multi-label co-training problem, an interesting but seldom studied learning paradigm. We introduce a solution to address the issue of class-imbalance, and to communicate confident labels of multi-label samples during the co-training process. Experimental results show that the proposed solution works better than other related methods. Several avenues remain to be explored, including how to accurately estimate label correlation from limited labeled data, and how to filter relevant labels more reliably during multi-label co-training. The code of MLCT is available at: http://mlda.swu.edu.cn/codes.php?name=MLCT.

Acknowledgments

This work is supported by NSFC (61741217, 61402378 and 61732019), Open Research Project of Hubei Key Laboratory of Intelligent Geo-Information Processing (KLIGIP2017A05).