Active Learning with Multi-Label SVM Classification

1 Introduction

Traditional multi-class classification problems assume that each instance is associated with a single label from a category set Y, where |Y| > 2. Multi-label classification generalizes multi-class classification by allowing each instance to be associated with multiple labels from Y. In many real world data analysis problems, data objects can be assigned into multiple categories and hence produce multi-label classification problems. For example, an image for object categorization can be labeled as "desk" and "chair" simultaneously if it contains both objects. A news article talking about the effect of Olympic games on tourism industry might belong to multiple categories such as "sports", "economy", and "travel", since it may cover multiple topics.

Many approaches have been developed in the literature to address multi-label classification problems. One standard and simple solution for multi-label classification nevertheless is to generalize the "one-vs-all" scheme of multi-class classification. That is, one decomposes the multi-label problem into a set of binary classification problems, one for each class, and solves the multi-label classification problem by conducting standard binary classifications [Boutell et al., 2004;

Joachims, 1998; Lewis et al., 2004a]. Regardless of the approach used, multi-label learning in general requires a sufficient amount of labeled data to recover high quality classification models. However, the labeling process of multi-label problems is much more expensive and time-consuming than single-label problems. In the single label case, a human annotator only needs to identify a single category to complete an instance label, whereas in the multi-label case, the annotator must consider every possible label for each instance, even if the positive labels are sparse. Active learning, which aims on conducting selective instance labeling and reducing the labeling effort of training good prediction models, is therefore particularly important for multi-label classification.

Despite the importance of the problem, current research on active learning for multi-label classification remains in a preliminary state. The majority of active learning study in the literature has centered on single-label classification problems, especially binary classification problems [Settles, 2012]. The active learning strategies developed for singlelabel classifications however mostly are not directly well applicable in multi-label cases, since instance selection decisions in multi-label cases should be based on all labels. The main challenge of multi-label active learning is to develop effective strategies to evaluate the unified informativeness of an unlabeled instance across all classes. Existing multi-label active learning works, such as [Brinker, 2006; Li et al., 2004; Esuli and Sebastiani, 2009; Singh et al., 2009; Yang et al., 2009], measure the informativeness of an unlabeled instance by treating all labels in an independent way without considering the potential implicit label structure information across all classes.

In this paper, we propose two novel multi-label active learning strategies, a max-margin prediction uncertainty strategy and a label cardinality inconsistency strategy, which exploit the relative multi-label classification margin structure on each unlabeled instance and the statistical label cardinality information, respectively, to measure the unified informativeness of unlabeled instances. Moreover, we further investigate an adaptive integration framework of these two strategies by applying a novel approximate generalization error measure. Our empirical study on multiple multi-label classification data sets demonstrates the efficacy of the proposed multi-label active learning strategies and the integrated adaptive active learning approach.

2 RelatedWork

The aim of active learning is to reduce labeling effort and cost required for training a high quality prediction model. Given a large pool of unlabeled instances, an active learner iteratively selects most informative instances from the pool to query an oracle (e.g., a human annotator) for labels. Most active learning studies in the literature have focused on single-label classification problems. One most commonly used active learning strategy is uncertainty sampling, where the active learner selects the instance that is most uncertain to label for the current trained classification model. Though uncertainty sampling methods remain myopic without measuring the future predictive informativeness of the candidate instance on the large amount of unlabeled data, they are computationally efficient and have demonstrated good empirical performance [Lewis and Gale, 1994; Luo et al., 2005; Culotta and McCallum, 2005; Settles and Craven, 2008]. Some more sophisticated non-myopic active learning methods exploit unlabeled data to minimize an approximation of the generalization error [Guo and Greiner, 2007; Guo and Schuurmans, 2007; Roy and McCallum, 2001; Yan et al., 2003; Zhu et al., 2003]. Such methods however are usually computationally expensive because they require a new prediction model to be retrained for each candidate query.

Active learning for multi-label classification however is still in a preliminary state. Most multi-label active learning methods decompose multi-label classification into a set of binary classification problems and make instance selection decisions by exploiting the binary classifiers independently without considering the label structure information of an instance revealed across all classes. [Brinker, 2006] uses a simple extension of the uncertainty sampling strategy. It decomposes the multi-label classification problem into several binary ones using the one-vs-all scheme, and selects the instance that minimizes the smallest SVMmargin among all binary classifiers. [Singh et al., 2009] simply takes the average of the uncertainty scores from all SVM binary classifiers as the instance selection measure. In [Li et al., 2004], an SVM active learning method was proposed for multi-label image classification. It determines the predicted labels of an unlabeled instance using binary SVM classifiers and make instance selection decision by using Max Loss (ML) and Mean Max Loss (MML) strategies to count prediction losses of all binary classifiers. [Yang et al., 2009] presents a strategy called maximum loss reduction with maximal confidence (MMC). It uses a multi-class logistic regression to predict the number of labels for an unlabeled instance and then computes the MMC measure by summing up losses from SVM classifiers on all labels. Different from these methods above, [Esuli and Sebastiani, 2009] exploits a multi-label boosting classification method and tests a number of strategies that conduct instance selections by combining measures from each class in an unequally weighted way. In addition, some other multilabel active learners consider selecting both instance and labels for annotations. For example, [Qi et al., 2009] develops a two-dimensional active learning algorithm that selects sample-label pairs to minimize the Bayesian classification error bound. [Vijayanarasimhan and Grauman, 2009] develops a multi-label multiple-instance active learning approach that selects both an image example and a level of annotation to request. In this work, we nevertheless focus on the general problem of instance selection, and develop two novel multilabel uncertainty sampling strategies and an approximate generalization error measure to efficiently select the most informative instance.

3 Multi-label SVMClassification

Transforming a multi-label classification problem into a set of independent binary classification problems via the "onevs-all" scheme is a conceptually simple and computationally efficient solution for multi-label classification. In this work, we conduct multi-label learning under such a mechanism by using standard support vector machines (SVMs) for the binary classification problems associated with each class.

Given a labeled multi-label training set D = {(xi, yi)}Ni=1 , where xi is the input feature vector for the i-th instance, and its label vector yi is a {+1, -1}-valued vector with length K such as K = |Y|. If yik = 1, it indicates that the instance xi is assigned into the k-th class; otherwise, the instance does not belong to the k-th class. For the k-th class (k = 1, · · · ,K), the binary SVM training is a standard quadratic optimization problem:

where {ξik} are the slack variables and C is the trade-off parameter. It maximizes the soft class separation margin. The model parameters wk and bk returned by this binary learning problem define a binary classifier associated with the k-th class: fk(xi) = wT k xi + bk. The set of binary classifiers from all classes can be used independently to predict the label vector ˆy for an unlabeled instance ˆx. The k-th component of the label vector ˆyk has value 1 if fk(ˆx) > 0, and has value -1 otherwise. The absolute value |fk(ˆx)| can be viewed as a confidence value for its prediction ˆyk on instance ˆx.

4 Max-MarginMulti-label Active Learning

In this paper, we consider pool-based active learning which appears to be the most popular scenario for applied research in active learning. Assume we have a small set of labeled multi-label instances L = {(xi, yi)}Nℓ i=1 , but a large pool of unlabeled instances U = {(xi)}Nu i=1 . Same as above, the label vector yi is a {+1, -1}-valued vector with length K. An active learner will iteratively select the most informative instance from the unlabeled pool U to label, then move it to the labeled set L and retrain the classification model on the augmented L. We aim to design multi-label active learning strategies for learning a good multi-label SVM classification model with fewer labeled instances and hence lower labeling cost. Below we will first present two novel multi-label uncertainty sampling strategies from the perspectives of label prediction and label dimension statistics respectively, and then present an adaptive integration of these two strategies under a novel approximate generalization error measure.

4.1 Max-Margin Uncertainty Sampling

Uncertainty sampling is one of the simplest and most effective active learning strategies used for single-label classification. The central idea of this strategy is that the active learner should query the instance which the current classifier is most uncertain about. For binary SVM classifiers, the most uncertain instance can be interpreted as the one closest to the classification boundary [Campbell et al., 2000]. As we reviewed in previous section, many multi-label active learning methods simply extend this binary uncertainty concept into the multi-label learning scenarios by integrating the binary uncertainty measures associated with each individual class in independent manners, such as taking the minimum over all classes [Brinker, 2006], and taking the average over all classes [Singh et al., 2009; Yang et al., 2009].

However, though multi-label classification can be conducted by training a set of independent binary classifiers, the prediction values produced by the multiple binary classifiers over the same instance are not irrelevant to each other. Note the training processes of multi-label classification and multiclass classification via the "one-vs-all" scheme are exactly the same. However, for a new instance x, multi-class classification determines its single positive label by comparing the prediction values of all binary classifiers, such as yk∗ = 1 for k∗ = argmaxk fk(x). [Rifkin and Klautau, 2004] shows such a simple "one-vs-all" multi-class classifier is as accurate as any other multi-class approach, assuming the underlying binary classifiers are well-tuned regularized classifiers such as SVMs. This suggests the prediction values of binary SVM classifiers trained using the "one-vs-all" scheme for multilabel classification are directly comparable as well.

Moreover, inspired by ranking-loss based multi-label classification methods [Crammer and Singer, 2003; Guo and Schuurmans, 2011], we observe that multi-label prediction is really about the overall separation of the group of positive labels from the group of negative labels. We thus propose to use a global separation margin between the group of positive label prediction values and the group of negative label prediction values to model the prediction uncertainty of an instance under the current multi-label SVM classifiers. Specifically, given the set of binary SVM classifiers f1, · · · , fk, the predicted label vector ˆyi of an unlabeled instance xi can be determined by the sign of the prediction values such as ˆyik = sign(fk(xi)). Let ˆy+ i denote the set of predicted positive labels and ˆyi denote the set of predicted negative labels, the separation margin over instance xi can then be defined as

Intuitively, a good multi-label classification model should maximize such separation margins over all instances to make sure the positive labels and the negative labels are well separated. The instance that has the smallest separation margin should be the most uncertain instance under the current classification model. Thus we define a novel global multi-label uncertainty measure as the inverse separation margin

We call this measure a max-margin prediction uncertainty measure since it aims to reduce the prediction uncertainty and increase the separation margins of all instances.

4.2 Label Cardinality Inconsistency

. The separationmargin we defined above is computed based on the predicted positive labels and negative labels. However, when there are mistakes in label prediction, the predicted separation margin of an instance may not correctly reveal its prediction uncertainty property. Figure 1 demonstrates such a toy example with five classes, where the predicted separation margin of the example instance is large, but the prediction mistakes show the instance is in fact very uncertain to predict. Though it is impossible to identify exact prediction mistakes on unlabeled instances, we observe that the number of predicted positive labels can shed some useful information over the possible prediction mistakes and overall prediction uncertainty of an unlabeled instance according to the statistical dimension of positive labels.

The labeled and unlabeled instances are all drawn from the same underlying distribution, thus not only their input features, but also their output labels share common statistical properties. One observation we have is that the multilabel instances usually have similar number of positive labels. The average number of positive labels assigned to each instance in a multi-label data set is called its label cardinality [Tsoumakas and Katakis, 2007]. Thus the number of predicted positive labels of an unlabeled instance is expected to be consistent with the label cardinality computed on the labeled data. Based on this observation, we introduce a novel active selection strategy called label cardinality inconsistency to measure the prediction uncertainty over an unlabeled instance from the label dimension perspective. For an unlabeled instance xi, this inconsistency measure is defined as the Euclidean distance between the number of predicted positive labels and the label cardinality of the current labeled data:

where I[·] is an indicator function and it has value 1 when the given condition is true, 0 otherwise. Though very simple, our

Algorithm 1 Adaptive Active Learning Procedure

Input: labeled set L, unlabeled set U, parameter set B.

repeat

Train multi-label SVM classifiers F 0 on L.

for each xi ∈ U do

Compute u(xi) and c(xi).

end for

for each β ∈ B do

Mark a candidate instance x = arg maxx∈U q(x, β).

end for

Copy all marked candidate instances into a set S.

for each x ∈ S do

Produce ˆy using classifiers F 0 .

Retrain a new classifiers F on (x, ˆy) ∪ L.

Compute ε(x) using classifier F and Eq. (6).

end for

Select instance x∗ from S using Eq. (7).

Remove x∗ from U, query its label vector y∗ .

Add (x∗ , y∗ ) into L.

until enough instances are queried

empirical work presented later shows this instance selection measure works reasonably well, even better than a few other multi-label instance selection strategies.

To our knowledge, exploiting information from label dimension perspective for active instance selection has also been exploited in the MMC method but in an indirect way [Yang et al., 2009]. It uses a multi-class logistic regression classifier to predict the number of positive labels, m, for an unlabeled instance and then compute the loss reduction measure based on this prediction.

4.3 An Adaptive Integration Approach

The two active learning strategies we proposed above can be complementary to each other in many cases. For the toy example given in Figure 1, if the label cardinality computed from the labeled data is 2, then the uncertainty of the example instance x can be captured by the label cardinality inconsistency measure thought it has a low uncertainty value under the max-margin prediction uncertainty measure. We thus propose to combine the strengths of the two measures by integrating them in a weighted form

where β ∈ [0, 1] is a trade-off parameter that balances the relative importance degrees of the two measures.

However, it is difficult to pick a fixed weight parameter β that works well in different phases of active learning process and different active learning scenarios, since the strength of each component measure may vary in different learning scenarios. It is important to conduct flexible selections over the β parameter to fit into different learning scenarios. A previous work [Donmez et al., 2007] tackled dynamic active learning by making strategy switch across stages of active learning process, which nevertheless lacks a consistent selection criterion across iterations. To achieve a consistent but flexible application of the integration criterion (5), we propose to adaptively select the best integration parameter β∗

in each iteration of the active learning. Though it is hard to make continuous β value selection, we propose to select β value from a prefixed set of discretely sampled values, e.g., B = [0, 0.1, · · · , 0.9, 1]. For each β value in the given set B, we can select one instance from the unlabeled pool U using the integrated selection measure in (5). After collecting all selected instances (no more than |B| instances) together into a set S, we then select the best β value from B by selecting the most informative instance from the set S.

To make β selection, we propose an approximate generalization error for refined instance selection from the preselected set S, which measures the future prediction error if the candidate instance and its predicted labels were added to the labeled training set. Specifically, for each instance x ∈ S, we use the multi-label SVM classifier F 0 = [f 0 1 , · · · , f 0K ] trained on the current labeled set L to predict its label vector ˆy. Then we train a new multi-label SVM classifier F = [f1, · · · , fK] on the augmented labeled set L ∪ (x, ˆy). The approximate generalization error of this new classifier F induced by the candidate instance x is defined as

where [a]+ = max(0, a), ˆy+ i denotes the predicted positive labels of the unlabeled instance xi by the classifier F , and ˆyi denotes the predicted negative labels correspondingly. This error is simply the sum of the two hinge losses around the predicted separation margin on each unlabeled instance. Finally the instance selection on S can be conducted by

It is natural to choose the unlabeled instance that would lead to the greatest reduction in future prediction error. However, it is computationally expensive to employ such a strategy directly because it requires retraining the multi-label classification model for each candidate instance in the unlabeled pool U. Nevertheless, it is a suitable strategy to make refined instance selection from a pre-selected small set in our algorithm. The overall adaptive active learning procedure is described in Algorithm 1.

5 Experimental Results

We evaluate our proposed multi-label active learning approach by conducting experiments on three image data sets, Corel5K [Duygulu et al., 2002], MSRC 23-class [Shotton et al., 2006], MIR Flickr [Huiskes and Lew, 2008], and a text data set, RCV1-S2 [Lewis et al., 2004b]. We compared the following approaches in our experiments:

• Random- the baseline using random instance selection.
• SVM- the baseline method that selects the most uncertain instance from all the uncertainty instances selected by the individual binary SVM classifiers, following the principle of the work [Brinker, 2006].
• MML- the method proposed in [Li et al., 2004].
• MMC- the method proposed in [Yang et al., 2009].

• MMU- the active learning method based on the maxmargin prediction uncertainty sampling strategy we proposed in Section 4.1.
• LCI- the active learning method based on the label cardinality inconsistency strategy in Section 4.2.
• Adaptive- the adaptive active learning approach we developed in this paper.

All these methods use the multi-label SVM classification model for multi-label classification. We used a fixed tradeoff parameter C = 10 in all the experiments.

Experimental Setting To conduct our active learning experiments, we sampled a 15-class subset of the Corel5K data with 2,160 images and a label cardinality value 2.4; a 15-class subset of the MIR Flickr data with 2,301 images and a label cardinality value 2.3. We used the entire MSRC 23-class data set, which has 591 images over 23 classes and a label cardinality value 2.5. For these image classification tasks, we used GIST features [Oliva and Torralba, 2001] and SIFT [Lowe, 2004] features for image representation. For the RCV1-S2 text data, we sampled a 15-class subset with 2,657 documents in total and a label cardinality value 2.4.

For each active learning experiment, we first randomly partitioned the data into three parts: labeled set, unlabeled pool and test set, under the condition that at least one positive label appears for each class in the labeled set, and then ran each comparison approach independently to conduct active learning based on the same initial setting. The partition settings we used for the four data sets are given as below: Corel5K (115 labeled images; 1,496 unlabeled images; 690 test images); MSRC (59 labeled images; 354 unlabeled images; 177 test images); MIR Flickr (70 labeled images; 1,582 unlabeled images; 708 test images); and RCV1-S2 (132 labeled images; 1,727 unlabeled images; 797 test images). For each active learning approach, we ran it for 100 iterations, and queried 100 instances in total. In each iteration, after querying the label of the selected instance, we retrained the multi-label SVM classifier on the increased labeled set, and evaluated its performance on the test set in terms of three performance measures: macro-F1, micro-F1 and accuracy. We repeated each experiment 10 times and reported the average results.

Results The experimental results on the four data sets are reported in Figure 2 - Figure 5. We can see that the naive random sampling baseline, Random, obviously demonstrates inferior performance on all data sets, comparing to most other methods. The SVM method, which selects the most uncertain instance based on independent selections made by individual binary classifiers, demonstrates poor performance as well. Especially, on the MIR Flickr data set, the classification performance produced by SVM even degrades with more instances (possibly outliers) being labeled. The two specialized multi-label active learning methods, MMC and MML, demonstrate superior performance over the two baselines in many cases. MMC, originally introduced for document classification, outperforms both Random and SVM on the multi-label text classification data, RCV1-S2, in terms of micro-F1 and accuracy, and on the image data MIR Flickr, in terms of all three evaluation measures. MML, originally developed for image classification, outperforms the previous three methods, Random, SVM and MMC on the image data sets, Corel5K and MSRC 23-class, but produces similar performance as MMC on MIR Flickr and RCV1-S2. Nevertheless, the performance gains achieved by MMC and MML are small and inconsistent across different data sets. The proposed two novel active learning methods, MMU and LCI, on the other hand, demonstrate clear and consistent advantages over the previous four methods, Random, SVM, MML and MMC. MMU outperforms the previous four baseline methods on all data sets, and outperforms LCI on two data sets, MSRC 23-class and MIR Flickr. The simple label cardinality inconsistency based method, LCI, outperforms all four baseline methods on three data sets, Corel5K, MIR Flickr, and RCV1-S2. On RCV1-S2, LCI produces similar performance as MMU, and on Corel5K, LCI even outperforms MMU. This suggests the uncertainty knowledge based on simple label dimension statistics is very useful. The proposed Adaptive active learning method effectively combines the strengths of MMU and LCI, and has demonstrated outstanding superior performance comparing to all the other six comparison methods on all four data sets across all three evaluation measures.

6 Conclusions

In this paper, we proposed two novel multi-label active learning strategies, a max-margin prediction uncertainty strategy that exploits the relative multi-label classification margin structure of each unlabeled instance, and a label cardinality inconsistency strategy that exploits the statistical label cardinality information of the labeled data, to measure the unified informativeness of an unlabeled instance across multiple labels. Moreover, we further proposed to integrate the strengths of these two strategies using an adaptive integration framework, which relies on a novel approximate generalization error for refined instance selection. Our empirical study on multiple multi-label classification data sets from different application areas shows that the proposed multi-label active learning strategies, especially the integrated active learning approach, greatly outperform a number of multi-label active learning methods developed in the literature.