Cost-Effective Active Learning for Hierarchical Multi-Label Classification

1 Introduction

Multi-label learning (MLL) is a practical and effective learning framework for objects with complex semantics, where each instance can be simultaneously associated with multiple class labels. While the output space is exponentially larger than that of single-label learning, it usually requires a large labeled dataset to train an effective MLL model. On the other hand, the annotation cost of an multi-label object could be very high when there is a large number of candidate labels. It is thus important to reduce the labeling cost for multi-label learning. Active learning is a primary approach to achieving this goal. It iteratively selects the most important instances to query their labels, and tires to improve the model with less queries.

Active learning for multi-label classification has attracted much research interest in recent years. Most of the previous methods try to extend some selection criteria from singlelabel to multi-label cases. There are a few other studies try to design novel query types to acquire other supervised information rather than class labels. These methods have achieved decent performances on some tasks, but pay less attention to the label correlations, which is crucial for multi-label learning. In this paper, we study the active learning for multi-label tasks with label correlations, especially in the form of label hierarchical tree.

∗This research was supported by JiangsuSF (BK20150754) and NSFC (61503182, 61732006).

In many multi-label learning tasks, the labels can be organized into a hierarchical tree structure from coarse to fine. For example, in document categorization, the candidate topics can be organized to a tree structure according to the Open Directory Project (ODP); and the topics of a specific document may cover one or multiple paths of the tree. In medical image analysis, each image is associated with a subset of the labels, which can be organized as part of IRMA hierarchical classification scheme.

The label hierarchies may contain important information, and should be exploited when perform active selection. Firstly, for a specific instance, its relevance to some labels can be directly decided from the others. An instance must have all the ancestor labels of a relevant label, and can never be assigned with any descendant labels of irrelevant labels. Secondly, the labels are typically organized from coarse to fine as the tree goes deeper. So the labels located at deeper layers are expected to contain more detailed information. Lastly, the annotation cost of labels at different levels can differ greatly. For example, it is easy for a labeler to identify whether there is a dog in an image, but rather difficult to identify whether the dog is a poodle.

In this paper, we propose a novel batch mode active learning approach to exploit the label hierarchies for cost-effective multi-label classification. Specifically, a new criterion is proposed to estimate the informativeness of an instance-label pair, which considers not only the usefulness of the current query, but also the potential contributions of ancestor and descendant labels after the query. Further, labels at different levels of the hierarchical tree are allowed to have different annotation costs. In each iteration, a batch of instance-label pairs is selected by automatically maximizing the informativeness while minimizing the overall annotation cost. The cost-effective selection is achieved with a bi-objective optimization problem. Our empirical study on multiple datasets and with different cost settings demonstrates the advantage of the proposed approach.

The rest of this paper is organized as follows. In Section 2, we introduce the related work. In Section 3, the propose approach is introduced. Section 4 presents the experiments, followed by the conclusion in Section 5.

2 RelatedWork

In many multi-label tasks, the labels are organized into a hierarchical tree structure from coarse to fine. The flat classification is the simplest method for hierarchical MLL [Burred and Lerch, 2003]. It ignores the label hierarchy, and makes predictions only for labels at leaf nodes. So traditional multilabel or multi-class approaches can be easily extended to this scenario. There are some other approaches try to exploit the hierarchies locally [Koller and Sahami, 1997] or globally [Blockeel et al., 2002]. Local methods train the model by utilizing the local information, such as the information per node [Eisner et al., 2005], per parent node [Secker et al., 2007] or per tree level [Freitas and de Carvalho, 2007]. Global methods consider the dependencies between different labels and learning a single global model.

Active learning has been successfully applied to many multi-label tasks [Hung and Lin, 2011; Huang et al., 2014a]. Most previous studies focus on designing the selection criterion such that the selected instances can improve the model maximumly. Uncertainty is one of the most effective criteria for active selection [Tong and Koller, 2001]. Some researches exploit the diversity [Brinker, 2003] or density [Nguyen and Smeulders, 2004] of data to estimate the representativeness of instances. Criteria combining different measurements are also studied, and have shown descent performances [Huang et al., 2014b]. Moreover, the query type has been validated to be important for multi-label active learning. Typical query types include querying all the labels of selected instances [Li et al., 2004], querying instance-label pairs [Huang and Zhou, 2013] and querying the relevance ordering of label pairs [Huang et al., 2015].

Recently, a few works applies active learning methods to hierarchical classification. However, these methods focus on the multi-class case, and regard only leaf nodes as labels in the hierarchal tree. Cheng et al. [2012] embed the label hierarchy and training data into a latent semantic space, and propose a uncertainty strategy based on the semantic space to query the informative instances. They improve this approach by joining a diversity measure in selection criterion and select a batch size of unlabeled data to query in [Cheng et al., 2014]. Chakraborty et al. [2015] propose a batch mode active learning method based on informativeness and diversity, and reduce the batch selection task to a score ranking problem. These methods assume that each instance has only one relevant label, and cannot handle multi-label learning problems. Li et al. [2012; 2013] use the uncertainty strategy to query the most informative instance. They pay more attention on minimizing the out-of-domain queries, and propose two strategies to subdivide the unlabeled data based on a top-down active learning framework. This method only explores the information of data while ignoring the different annotation cost of labels.

3 The Proposed Approach

Let X = Rd be the input space and Y = {y1, y2, · · · yL} be the label space with L possible labels. We denote by {(x1, Y1), (x2, Y2), ..., (xn, Yn)} the training data that consists of n instances, where each instance xi is a d-dimensional feature vector, and Yi ⊆ Y is the set of labels relevant to xi.

We focus on the batch mode active learning setting, where a small batch of queries are performed at each iteration, and each query is for checking the relevance of an instance-label pair. We propose a new criterion for estimating the informativeness of an instance-label pair with hierarchies in the first subsection, and then present the algorithm for selecting costeffective queries in the second subsection.

3.1 Informativeness for Hierarchical Labels

It has been well accepted that if the current model is less certain about the prediction on an instance, then the instance is likely to be more informative, and can contribute more for improving the model. Uncertainty is one of the most commonly used criterion to measure the informativeness. Specifically, we estimate the uncertainty of an instance xi on a label yj by the reciprocal of the closeness to the decision boundary:

where fj is the classification model for label yj.

Then we extend this definition to incorporate the information embedded in the hierarchical structure. When querying the relevance of an instance-label pair (xi, yj), we may get extra supervised information of ancestor or descendant labels. Moreover, the extra information is dependent to the groundtruth relevance of (xi, yj). For example, if label yj is relevant to instance xi, the ancestor nodes of yj are also relevant to instance xi. On the contrary, if label yj is irrelevant to instance xi, the descendant nodes of yj are also irrelevant to instance xi. This characteristic indicates that the informativeness defined in Eq. (1) can not be fully utilized. Thus the information of ancestor and descendant nodes should be considered to contribute the current label nodes, which are denoted by U ij anc and U ij des , respectively. So the enhanced informativeness of each instance-label pair (xi, yj) can be discussed for two cases:

Unfortunately, before the querying, it is unknown whether xi is relevant to yj or not. Instead, we try to evaluate the relevance by exploiting the information from similar examples. Specifically, majority voting on k nearest neighbors is employed to decide the relevance hij of (xi, yj):

where nei(xi, yj, k) consists of k nearest neighbors of xi with regard to label yj . If x is an labeled instance, then gj(x)

is the ground-truth relevance on yj , otherwise gj (x) = fj (x). To avoid negative affection from unreliable instances, we filter out half of the unlabeled instances with low confidence when searching for the k nearest neighbors. Note that the predictions of the same instance on different labels may have different confidences, so nei(xi, yj, k) varies with different yj .

With the estimated relevance hij, the two cases in Eq. (2) can be integrated into an unified formulation:

where I[·] is the indicator function which returns 1 if the argument is true and 0 otherwise. From Eq. (4) we can observe that if hij == 1, labels in deeper level are preferred because it brings more label information of its ancestor; otherwise, labels in upper level are preferred because they have more descendant labels to be additionally identified as irrelevant.

We now discuss the implementation of U ij anc and U ij des for estimating the contribution of ancestor and descendant labels. A straightforward method is to simply summarize the uncertainty of all ancestor or descendant labels, leading to the following definitions:

where anc(j) and des(j) denote the set of ancestor and descendant labels of yj, respectively. Note that if a label yk has been previously annotated for xi, it will not bring any extra information, and thus Uik will be set to 0. Obviously if the ancestor(or descendant) set is empty, the U ij anc (or U ij des ) is 0.

The above definition takes all ancestor or descendant labels into consideration, but neglects the risk of information redundancy. As mentioned before, labels at deeper level usually have more detailed information, which may cover most of those embedded in labels at upper level. Considering this, we redefine U ij anc and U ij des as:

where leaf(j) is the set of leaf labels of the subtree rooted at yj. In other words, the redundant information contained in the internal nodes is filtered out.

3.2 Cost-effective Selection

As discussed before, the annotation cost of labels at different levels can differ greatly. Thus in addition to exploiting the informativeness embedded in label hierarchies, it is also important to consider the annotation cost to achieve cost-effective querying. In this subsection, we introduce a subset selection method, which balances the conflict of informativeness and cost, and selects a batch of instance-label pairs with most information and least cost.

A general subset selection problem aims to select a subset S from a total set V of n elements so that the objective J can be optimized with the constraint |S| ≤ b, where | · | denotes the size of a set. b is the maximum number of selected elements. This problem can be formalized as

For convenience of presentation, a binary vector s ∈ {0, 1}n is introduced to indicate the subsets membership, where si = 1 if the i-th element in V is selected, and si = 0 otherwise. Follow the method in [Qian et al., 2015], the subset selection problem in Eq. (9) can be reformulated as a bi-objective minimization problem:

The original target of the method in [Qian et al., 2015] is to achieve sparse selection while minimizing the objective function J. Here, we extend it to perform active selection, which maximizes the informativeness of selected instancelabel pairs, and at the same time minimizes the annotation cost. Then the two objectives can be defined as the negative informativeness and annotation cost of the selected instancelabel pairs, respectively. We denote by Cij the cost of annotating the relevance of yj on instance xi, and have the following bi-objective optimization problem.

Here s is a n-dimensional binary vector, n is the number of unlabeled instance-label pairs, and s(i, j) returns the element of s corresponding to the instance-label pair (xi, yj). b is the cost budget of the batch.

We then employ the bi-objective optimization method POSS in [Qian et al., 2015] to solve Eq. (11). The POSS method maintains a set of candidate solutions for s. In each iteration, it generates a new solution s′ from the candidate solution set by random flipping, then compares it with all the other candidate solutions. s′ is then added into the candidate solution set if it is both better in two objectives. This process repeats until the maximum number of iterations is reached. Then the optimal solution in the remaining solution set is selected. By solving Eq. (11), a cost-effective batch of instance-label pairs are expected to be selected.

Finally, we summarize pseudo code of the proposed algorithm HALC (Hierarchical Active Learning with Cost) in Algorithm 1. In each iteration, we first compute the informativeness for each instance-label pair, the POSS method then balances the computed informativeness and pre-defined cost. After that, a batch of instance-label pairs is selected to query the oracle, and we can further obtain the annotation of the ancestor or descendant simultaneously without any cost. The complexity of active selection is O(n), where n is the size of unlabeled set.

4 Experiments

4.1 Settings

To examine the effectiveness of the proposed approach, we perform the experiments on four datasets. The statistical information of these datasets are summarized in Table 1, including number of instances, number of labels, feature space dimensionality and depth of the label hierarchy. It is worth notice that we convert the DAG structure of Yeastgo[Barutcuoglu et al., 2006] and Scop-go[Clare, 2003] to hierarchical tree structure by removing subtrees with multiple parents. We also remove labels associated with too few instances. After removing the labels, the size of label set is large enough for experiments. Meanwhile, the class-imbalance problem still exists and imbalance rate is larger than 100:1.

On each data set, we randomly divide it into two parts with 70% as training set and 30% as test set. In the training set, we randomly sample 5% as initial labeled data and the rest as unlabeled pool for active learning. We randomly partition the data for 10 times and report the average results over the 10 repetitions. At each iteration of active learning, a small batch of instance-label pairs is selected by the active learning approaches from unlabeled pool, and then added into the labeled data.

We use one-vs-all linear SVM as baseline classification model for each label. LibSVM is used to implement the classifier in our experiments [Chang and Lin, 2011]. We evaluate the performances of the compared approaches with Hamming Loss and Micro-F1, among which F1 measure is commonly used in hierarchical classification.

To examine the effectiveness of selection method, we compare the proposed approach with three methods. To the best of our knowledge, there is no existing study can be directly applied to our setting. The following methods are compared in our experiments:

• HALC: The cost-effective approach proposed in this paper.
• Top-down: The method proposed in [Li et al., 2013], which selects instance-label pairs from top to down level of hierarchy based on uncertainty sampling.
• Uncertainty: Selects the most uncertain instance-label pairs, we use Unc for short.
• Random: Randomly selects instance-label pairs, we use Ran for short.

Note that in the top-down method, all the groundtruth of descendant nodes are received simultaneously when querying the selected label. This obviously leads to extra cost. To be fair, the oracle returns only one label of each query in our experiments.

4.2 Performance Comparison

As mentioned before, labels at deeper level cost higher, we manually set the cost of labels at 1:5:10:15 for 4-level hierarchy, and 1:5:10 for 3-level hierarchy. Labels on the same level have the same cost. The performance curves with the cost increasing are plotted in Figure 1 and Figure 2, respectively. Note that the star point of Top-down method is quite different from other methods because of the varies baseline classifiers. The Top-down adopted the hierarchical SVMs as the base classifiers due to the special top-down framework. We can observe that our method achieves the best performance in most cases on all datasets with regard to both measures. The Uncertainty approach can outperform the Random approach, but is worse than our proposed method. Random approach has little improvement on most datasets. The performance of Top-down method is improved quickly at the beginning, but loses its edge as the querying goes on. This is probably because that it simply querys from top to deep labels along the tree path, ignoring the trade-off between informativeness and cost. Further, The improvement of models in deeper level would cost much higher than that in upper nodes, leading to the slowly growth. These results valid that the proposed approach is cost-effective for active selection in hierarchical multi-label learning.

4.3 Study on Relevance Rate

In this subsection, we further compare the relevance rate on different levels. The degenerated version of our algorithm without considering cost , denoted by HALC-i, is an additional comparison method. HALC-i focuses only on hierarchical informativeness. The comparison results are presented in Figure 3. We can observe that our approach, especially HALC-i, queries more relevance instances in deeper level, which illustrates that data with more supervised information has been queried with the same annotation cost, including not only the information itself but the ancestors or descendants.

The top-down method queries rarely relevance instances in deep levels in some cases, this may be because it subdivides the unlabeled pool from top to down, and it may mistakenly remove the relevance instances. The relevance rate of Uncertainty is similar in different levels.

4.4 Study with Different Cost Settings

To examine the robustness of the proposed method to different cost ratios, we further perform experiments in 3 different cost settings, i.e., 1:5:10:15, 1:3:6:9 and 1:2:3:4. Due to space limitation, we cannot plot all the performance curves for all datasets, instead, we only report the average value of the performance curve in Table 2 and Table 3, respectively. The best result is highlighted in boldface in both tables. It can be observed from the tables that the proposed approach consistently achieves the best performance with various cost settings. The Top-down approach and uncertainty method are comparable in most cases. These results validate that the costeffective approach can effectively save the annotation cost, and is robust to different cost settings.

5 Conclusion

In this paper, we propose a multi-label active learning approach to exploit the label hierarchies for cost-effective queries. To incorporate the potential contribution of ancestor and descendant labels in the label hierarchy, a novel criterion is proposed to estimate the informativeness of each instance-label pair. To balance the conflict of informativeness and annotation cost of the query, a bi-objective optimization method is used for subset selection. Experiments on multiple datasets and different performance measures validate the effectiveness of both the informativeness criterion and active selection method. Moreover, the proposed approach maintains the best performance in various annotation cost settings. In the future, we plan to design other criteria to exploit the label hierarchy. Also, other label correlations rather than tree structure will be considered.