LIFT: Multi-Label Learning with Label-Specific Features

1 Introduction

Multi-label learning deals with objects having multiple labels simultaneously, which widely exist in real-world applications [Boutell et al., 2004; Elisseeff and Weston, 2002; Schapire and Singer, 2000]. Formally, let X = Rd be the d-dimensional input space and Y = {l1, l2, · · · , lq} be the finite set of q possible labels. Then, the task of multi-label learning (or multi-label classification) is to learn a function h : X → 2Y which maps each instance x ∈ X into a set of proper labels h(x) ⊆ Y.

During the past decade, considerable number of approaches have been proposed to learn from multi-label data

∗This work was supported by the National Science Foundation of China (60805022), Ph.D. Programs Foundation of Ministry of Education of China for Young Faculties (200802941009), and the Startup Foundation of Southeast University.

[Tsoumakas et al., 2009]. The common strategy adopted by existing approaches is that identical feature representation of the instance, i.e. x, is utilized to discriminate all the class labels in Y. This amounts to induce a family of q functions {f1, f2, · · · , fq}, where fk : X → R determines the membership of lk to each instance such that h(x) = {lk | fk(x) > 0, 1 ≤ k ≤ q}. Here all functions in the family operate on the same feature set x. Although this strategy has gained much success in algorithm design, it might be too straightforward and away from being optimal for multi-label learning.

For example, in automatic image annotation, suppose sky and desert are two possible labels in the label space. Intuitively, color-based features would be preferred in discriminating sky and non-sky images, texture-based features would be preferred in discriminating desert and non-desert images, while both color- and texture-based features might be useful in discriminating other labels in the label space. For another example, in text categorization, features related to terms such as government, reform and president might be important in discriminating political and non-political documents, while features related to terms such as stadium, matches and champions might be important in discriminating sport and nonsport documents.

The above observations reflect the fact that, in multi-label learning different class labels in the label space may carry specific characteristics of their own. Therefore, we hypothesize that if label-specific features, i.e. the most pertinent and discriminative features for each class label, could be used in the learning process, a more effective solution to the problem of multi-label learning can be expected.

To justify this hypothesis, a new algorithm named LIFT, i.e. multi-label learning with Label specIfic FeaTures , is proposed in this paper. LIFT tackles multi-label learning problem with two simple steps. Firstly, for each class label lk ∈ Y, clustering analysis is conducted on its positive instances as well as negative instances in the training set, and then features specific to lk are constructed by querying the clustering results. Secondly, a family of q classifiers are induced where each of them is trained with the generated labelspecific features other than the original features under X. To thoroughly evaluate the effectiveness of LIFT, extensive experiments over sixteen regular-scale and large-scale data sets clearly verify that our approach compares favorably against other state-of-the-art multi-label learning algorithms.

The rest of this paper is organized as follows. Section 2 briefly discusses existing approaches to multi-label learning. Section 3 presents the details of the proposed approach. Section 4 reports the results of comparative studies. Finally, Section 5 concludes and indicates several issues for future work.

2 RelatedWork

Generally, the task of multi-label learning is rather challenging due to the exponential number of possible label sets (i.e. 2q ) to be predicted for an unseen example. To cope with this issue, existing approaches focus on exploiting the correlations between labels to facilitate the learning process, which can be roughly grouped into three categories based on the order of label correlations [Zhang and Zhang, 2010], namely first-order approaches, second-order approaches and highorder approaches.

First-order approaches tackle multi-label learning problem by decomposing it into a number of independent binary classification problems. Specifically, a family of q functions {f1, f2, · · · , fq} are learned in a label-by-label style, one for each possible class label [Boutell et al., 2004; Zhang and Zhou, 2007]. First-order approaches are conceptually simple, efficient and easy to implement, while may be less effective due to their ignorance of label correlations.

Second-order approaches tackle multi-label learning problem by considering pairwise relations between labels. Specifically, a family of q functions {f1, f2, · · · , fq} are learned by exploring the interactions between a pair of functions fk and fk′ such as their co-occurrence patterns [Ghamrawi and McCallum, 2005; Zhu et al., 2005] or their ranking constraints [Elisseeff and Weston, 2002; Zhang and Zhou, 2006; F¨urnkranz et al., 2008]. Second-order approaches address label correlations to some extent and are relatively effective, while may suffer from the fact that label correlations could go beyond second-order under real-world scenarios.

High-order approaches tackle multi-label learning problem by considering high-order relations between labels. Specifically, a family of q functions {f1, f2, · · · , fq} are learned by exploring the influences among a subset of functions {fk1 , fk2 , · · · , fkq′ } (q′ ≤ q) [Tsoumakas and Vlahavas, 2007; Read et al., 2009; Zhang and Zhang, 2010] or among all the functions [Yan et al., 2007; Ji et al., 2008; Cheng and H¨ullermeier, 2009]. High-order approaches could address more realistic label correlations, while may exhibit high model complexities.

A commonness of these existing approaches is that they deal with multi-label learning problem mainly from the perspective of output space, i.e. manipulating correlations between labels, and identical features inherited from the original input space are directly used in discriminating all the labels. In the next section, we will present the LIFT approach which works mainly from the perspective of input space, i.e. manipulating label-specific features.

3 The LIFT Approach

Let D = {(xi, Yi) | 1 ≤ i ≤ m} be the training set with m multi-label training examples, where xi ∈ X is a d-dimensional feature vector and Yi ⊆ Y is the set of labels Y =LIFT(D, r, L, u)

Table 1: Pseudo-code of LIFT.

Inputs:

• D : the multi-label training set {(xi, Yi) | 1 ≤ i ≤m} (xi ∈ X, Yi ⊆ Y, X = Rd , Y = {l1, l2, · · · , lq})
• r : the ratio parameter as used in Eq.(2)
• L : the binary learner for classifier induction
• u : the unseen example (u ∈ X)

Outputs:

• Y : the predicted label set for u (Y ⊆ Y)

Process:

1. for k = 1 to q do
2. Form Pk and Nk based on D according to Eq.(1);
3. Perform k-means clustering on Pk and Nk, each with mk clusters as defined in Eq.(2);
4. Create the mapping φk for lk according to Eq.(3);
5. endfor
6. for k = 1 to q do
7. Form D∗ k accroding to Eq.(4);
8. Induce f ∗ k by invoking L on D∗ k, i.e. f ∗ k ← L(D∗ k);
9. endfor
10. Y = {lk | f ∗ k (φk(u)) > 0, 1 ≤ k ≤ q}.

associated with xi. Then, LIFT learns fromD following two elemental steps, i.e. label-specific features construction and classification models induction.

In the first step, LIFT aims to generate distinguishing features which capture the specific characteristics of each label to facilitate its discrimination process. To achieve this, LIFT employs clustering techniques which have been widely used as stand-alone tools to gain insights into the properties of data [Jain et al., 1999]. Specifically, with respect to each class label lk ∈ Y, the set of positive training instances Pk as well as the set of negative training instances Nk are denoted as:

In other words, Pk and Nk consist of the training instances in D with and without label lk respectively.

The popular k-means algorithm [Jain et al., 1999] is adopted to partition Pk into m+k disjoint clusters whose centers are denoted as {pk1, pk2, · · · , pkm+k }. Similarly, Nk is also partitioned into m-k disjoint clusters whose centers are denoted as {nk1 , nk2 , · · · , nkm-k }. Here, we choose to set equivalent number of clusters for Pk and Nk, i.e. m+k = m-k = mk. In this way, clustering information gained from positive instances as well as negative instances are treated with equal importance. Specifically, the number of clusters retained for both positive and negative instances is set to be:

Here, | · | represents the set cardinality and r ∈ [0, 1] is the ratio parameter controlling the number of clusters thus retained.

Intuitively, the retained cluster centers characterize the underlying structure of input space, and can be used as the bases for label-specific features construction with regard to lk. In detail, LIFT creates a mapping φk : X → Zk from the original d-dimensional space X to the 2mk-dimensional labelspecific feature space Zk as follows: 1

Here, d(·, ·) returns the distance between two instances and is set to the Euclidean metric in this paper.

Note that we do not claim that the above process is the best possible practice for label-specific features construction. Actually, the mapping φk can be implemented in alternative ways, such as setting different number of clusters for positive and negative instances (i.e. m+k ̸= m-k ), utilizing more sophisticated distance for d(·, ·) other than the Euclidean metric, or even employing kNN rule [Wang et al., 2010] to identify the bases for feature mapping other than invoking the kmeans procedure, etc. Nevertheless, LIFT's simple construction process of label-specific features suffices to yield competitive performance as shown in Section 4.

In the second step, LIFT aims to induce a family of q classification models {f ∗ 1 , f ∗ 2 , · · · , f ∗ q } with the generated labelspecific features. Specifically, for each class label lk ∈ Y, a binary training set D∗ k with m examples is created from D and φk as follows:

Based on D∗ k , any binary learner can be applied to induce a classification model f ∗ k : Zk → R for lk. Given an unseen example u ∈ X, its associated label set is predicted as Y = {lk | f ∗ k (φk(u)) > 0, 1 ≤ k ≤ q}. In principle, the classifiers induction process of LIFT is similar to those of the first-order approaches discussed in Section 2. The major difference lies that LIFT induces the classifier on each label with label-specific features instead of the original ones.

1 Note that in multi-label learning, the distribution of positive instances and negative instances for each label is usually imbalanced with |Pk| ≪ |Nk|. Thus, the dimensionality of Zk, i.e. 2·r ·min(|Pk|, |Nk|), would be of reasonable size in most cases. As an intance, for the ohsumed data set with 13929 examples and 1002 features (Table 2), the dimensionality of the label-specific feature space is only around 100 ± 93 across all labels with r = 0.1.

In summary, Table 1 presents the complete description of LIFT. Based on the multi-label training examples, LIFT firstly constructs label-specific features for each possible class label (steps 1 to 5); After that, a family of q binary classification models are induced based on the constructed features in a round-robin style (steps 6 to 9); Finally, the unseen example is fed to the learned system for prediction (step 10).

Note that the idea of exploiting label-specific features should be regarded a meta-strategy to multi-label learning, and LIFT serves as one possible instantiation of this strategy. There are learning algorithms such as decision trees which can implicitly do feature selection during their learning process. However, this is only a by-product of these algorithms and should not be regarded a stand-alone tool for feature construction. Employing algorithms such as decision trees in first-order approaches could yield similar methods to LIFT. However, the major difference lies in that the former one wraps around the construction of label-specific features and the induction of learning models, while LIFT constructs label-specific features independent of the model induction.

4 Experiments

4.1 Configuration

To thoroughly evaluate the performance of our approach, a total of sixteen real-world multi-label data sets are studied in this paper. For each data set S = {(xi, Yi) | 1 ≤ i ≤ p}, we use |S|, dim(S), L(S) and F(S) to denote the properties of number of examples, number of features, number of possible class labels, and feature type respectively. In addition, several other multi-label properties [Read et al., 2009; Tsoumakas et al., 2009] are denoted as:

• LCard(S) = 1p ∑pi=1 |Yi| : label cardinality which measures the average number of labels per example;
• LDen(S) = LCard(S) L(S) : label density which normalizes LCard(S) by the number of possible labels;
• DL(S) = |{Y |(x, Y ) ∈ S}| : distinct label sets which counts the number of distinct label combinations in S;
• PDL(S) = DL(S) |S| : proportion of distinct label sets which normalizes DL(S) by the number of examples.

Table 2 summarizes the detailed characteristics of those multi-label data sets used in our experiments. Roughly ordered by |S|, eight regular-scale data sets (first part, |S| < 5000) as well as eight large-scale data sets (second part, |S| ≥ 5000) are included. As shown in Table 2, the sixteen data sets cover a broad range of cases whose characteristics are diversified with respect to different multi-label properties.

In this paper, LIFT is compared with four well-established multi-label learning algorithms, including BSVM [Boutell et al., 2004], ML-KNN [Zhang and Zhou, 2007], BP-MLL [Zhang and Zhou, 2006] and ECC [Read et al., 2009]. As discussed in Section 2, BSVM and ML-KNN are first-order approaches which work in a similar way as LIFT by generating classifiers in a label-wise style, though under the original feature space X. In addition, BP-MLL is a second-order approach and ECC is a high-order approach both of which consider exploiting label correlations in their learning processes. For fair comparison, LIBSVM (with linear kernel) [Chang and Lin, 2001] is employed as the binary learner for classifier induction to instantiate LIFT, BSVM and ECC.

As shown in Table 1, in addition to set L as linear kernel LIBSVM, the other factor needed to be specified for LIFT is r, i.e. the ratio parameter as used in Eq.(2). In this paper, r is set to be 0.1 for all data sets. 2 Furthermore, parameter configurations suggested in respective literatures are used for the other comparing algorithms. For BSVM, models are learned via the cross-training strategy [Boutell et al., 2004]; For ML-KNN, the number of nearest neighbors considered is set to be 10 [Zhang and Zhou, 2007]; For BP-MLL, the number of hidden neurons is set to be 20% of the input dimensionality and the maximum number of training epochs is set to be 100 [Zhang and Zhou, 2006]; For ECC, the ensemble size is set to be 10 and the sampling ratio is set to be 67% [Read et al., 2009].

4.2 Results

Performance evaluation in multi-label learning is more complicated than traditional single-label learning, as each example could be associated with multiple labels simultaneously. Firstly, five evaluation criteria popularly used in multi-label learning are employed, i.e. hamming loss, one-error, coverage, ranking loss and average precision [Schapire and Singer, 2000; Tsoumakas et al., 2009]. 3 Briefly, these criteria evaluate the quality of the predicted label set for each test example and then return the averaged value across all the test examples. In addition, we also employ the AUC criterion (area under the ROC curve) to evaluate the quality of the predictions for each class label and then return the averaged value across all the class labels.

2 In preliminary experiments, a number of values have been tested for r by increasing it from 0.02 to 0.2 (stepsize 0.02). Results show that the performance of LIFT becomes stable as r approaches 0.1.

3 Due to page limit, formal definitions on these criteria can be found in the references therein. In this paper, the coverage criterion is further normalized by |Y| so that all reported performance measures vary between [0,1].

On each data set, ten-fold cross validation is conducted and the mean value and standard deviation of each evaluation criterion is recorded. For AUC and average precision, the larger the values the better the performance; While for the other four criteria, the smaller the values the better the performance. All the above criteria serve as good indicators for comprehensive comparative studies as they evaluate the performance of an algorithm from various aspects.

Tables 3 and 4 report the detailed experimental results on the regular-scale and large-scale data sets respectively. For each evaluation criterion, "↓" indicates "the smaller the better" while "↑" indicates "the larger the better". Furthermore, the best performance among the five comparing algorithms is highlighted in boldface.

Across all the 96 configurations (i.e. 16 data sets × 6 criteria as shown in the two tables), LIFT ranks in 1st place among the five comparing algorithms at 47.9% cases, in 2nd place at 45.8% cases, in 3rd place at only 6.3% cases, and never ranks in 4th and 5th places. To perform comparative analysis in more well-founded ways, Friedman test is further examined which is a favorable statistical test for comparisons of more than two algorithms over multiple data sets [Demˇsar, 2006].

For each evaluation criterion, Friedman test at 0.05 significance level (five algorithms, sixteen data sets) rejects the null hypothesis of "equal" performance, which leads to the use of post-hoc tests to find out which algorithms actually differ. Specifically, Nemenyi test is utilized where the performance of two algorithms is significantly different if their average ranks over all data sets differ by at least one critical difference (CD). Figure 1 gives the CD diagrams [Demˇsar, 2006] for each evaluation criterion, where the average rank of each comparing algorithm is marked along the axis (lower ranks to the right). Groups of algorithms that are not significantly different according to Nemenyi test are connected with a thick line. The critical difference (CD=1.525 at 0.05 significance level) is also shown above the axis in each subfigure.

To summarize, out of all the 24 comparisons (4 algorithms to compare × 6 criteria), LIFT achieves statistically comparable performance in only 33% cases, i.e. the 8 comparisons against ML-KNN on hamming loss (Fig.1 a), against ECC on one-error (Fig.1 b), against BSVM and BP-MLL on coverage (Fig.1 c), on ranking loss (Fig.1 d), and on AUC (Fig.1 f). Rather impressively, LIFT achieves statistically superior performance in all the other 67% cases and no algorithms have once outperformed LIFT. These results clearly validate the superior effectiveness of our approach to the other wellestablished multi-label learning algorithms.

5 Conclusion

The major contributions of our work are two-fold: 1) A new strategy to multi-label learning via label-specific features is proposed, which suggests a new direction for learning from multi-label data; 2) A simple algorithm named LIFT is designed to justify the proposed strategy, whose effectiveness is thoroughly validated based on extensive comparative studies.

In the future, it is interesting to see whether LIFT can be further improved by incorporating label correlations into its label-specific features construction step as well as classification models induction step. Furthermore, designing other ways to fulfill the strategy of label-specific features is a direction very worth studying.

Acknowledgments

The author wishes to thank the anonymous reviewers for their helpful comments and suggestions.