Multi-Instance Multi-Label Learning with Weak Label

1 Introduction

Conventional supervised learning often assumes that an object is represented by a single-instance and associated with one class label. In a recent learning framework, MultiInstance Multi-Label learning (MIML) [Zhou and Zhang, 2006; Zhou et al., 2012], an object is allowed to be represented by a bag of instances and associated with multiple class labels simultaneously. This framework has been found useful in diverse tasks especially those involving complicated data objects, such as image annotation [Zha et al., 2008], text categorization [Zhou et al., 2012], video annotation [Xu et al., 2012], acoustic classification [Briggs et al., 2012], bioinformatics [Li et al., 2009c], etc.

Many MIML algorithms have been developed during the past few years. To name a few, Zhou and Zhang [2006] proposed the MIMLSVM and the MIMLBoost by degenerating MIML to multi-label learning and multi-instance learning, respectively; Zha et al. [2008] addressed MIML problem with hidden conditional random field; Yang et al. [2009] tackled MIML with probabilistic generative models; Nguyen [2010] solved MIML problem through estimating instance labels;

∗This research was supported by NSFC (61273301, 61073097), 973 Program (2010CB327903) and Baidu Fund (181315P00441).

Briggs et al. [2012] optimized rankloss for each bag. MIML metric learning has also been studied in [Jin et al., 2009]. All these studies assumed that the labels for training examples, both positive and negative, are all given explicitly in advance; in other words, the complete label assignments for each training example are available.

In many real applications, however, the label assignments are generally given by users, and it is often difficult to expect the users to specify all labels for every example. It is very likely that, for example, in image annotation, users only tag a subset of positive labels for an image, and therefore, the untagged labels are not necessarily negative. This setting is called weak label, which has only been studied in two pieces of work on multi-label learning: Sun et al. [2010] proposed the WELL approach by assuming that the similarities between instances are derived from a group of low-rank base similarities; Bucak et al. [2011] proposed the MLR-GL approach by exploiting group lasso to combine ranking errors. Note that these two studies focused on single-instance data, whereas to the best of our knowledge, the MIML weak label setting has never been touched.

MIML transductive learning and semi-supervised learning have been studied before [Feng and Xu, 2010; Xu et al., 2012]. Both assumed that the labeled MIML examples are with complete label assignments, whereas unlabeled data are without any label information; this is related but different from the weak label setting because in these settings, once we get tagged labels for an example, we can conclude that all the untagged labels are negative.

In this paper, we propose the MIMLwel (MIML with WEak Label) approach for the weak label setting. Our basic assumption is that highly relevant labels generally share common instances, and the underlying class means of bags for each label are with a large margin. Specifically, we first explore a mapping from a bag of instances to a feature vector where each element measures the degree of the bag being associated with a group of similar instances. Then, we employ sparse predictors to learn the labels of bags such that the class means of bags for each label is maximized. We formulate the problem in a general framework and provide an efficient block coordinate descent solution. The effectiveness of the MIMLwel approach on handling the weak label problem is validated in experiments.

In the following we will present the MIMLwel approach in Section 2, and then report our experiments in Section 3. Finally, we conclude the paper in Section 4.

2 The MIMLwel Approach

In the original MIML setting [Zhou and Zhang, 2006; Zhou et al., 2012], we are given a training data set {(X1, Y1), (X2, Y2), . . . , (Xm, Ym)}, where Xi is a bag containing ni instances {xi,1, xi,2, . . . , xi,ni }, Yi = [yi,1, . . . , yi,L] ∈ {0, 1}L is a label vector containing L labels, where yi,l = +1 if the lth label is positive for Xi, and 0 otherwise. Note that the labels of instances xi,j's (i = 1, . . . ,m; j = 1, . . . , ni) are unknown.

In MIML weak label setting, however, only a subset of labels are tagged. Specifically, for Xi, we are given a label vector ˆ Yi = [ˆ yi,1, . . . , ˆ yi,L], where ˆ yi,l = 1 if the lth label is tagged for Xi, and 0 otherwise. The goal is to predict all the positive labels for unseen bags.

We first consider a mapping from a bag of instances to a feature vector, and then represent each bag Xi by φC(Xi), where C are prototypes. With such a mapping, each bag is re-represented by a single feature vector, and thus classical single-instance learning algorithms can be applied. The prototypes C can be generated by a clustering process, e.g., kmeans; however, such a process may result in a suboptimal performance. To address this problem, our proposed approach explicitly takes into account the learning of C .

2.1 The Formulation

A straightforward strategy to deal with the weak label setting is to decompose the problem into L independent binary classification problems, each corresponding to a label; for the ith label, training data with the ith label tagged are regarded as positive training examples, whereas the untagged data are regarded as unlabeled data. Then, each of these problems can be addressed by PU-learning (Positive and Unlabeled learning) [Liu et al., 2003]. Such a strategy, however, ignores useful information concealed in label relations and often leads to a suboptimal performance. It also requires a high computational workload, particularly when there are a large number of training bags. Furthermore, existing PU-learning algorithms were mostly designed for single-instance data, whereas the training data for each of these L binary classification problems are bags rather than single-instances; therefore, existing PU-learning algorithms could not be applied directly.

Considering that existing approaches could not be applied to MIML weak label setting directly, we propose the MIMLwel approach. In order to take label relations into account, we assume that the highly relevant labels often share common instances. Moreover, in order to improve efficiency, particularly when there are a large number of bags, we employ an efficient strategy by assuming that the underlying class means of bags for each label are separated with a large margin.

For simplicity, we employ L linear models one for each label, i.e.,fl(X) = wT l ΦC(X) where each wl is a d- dimensional linear predictor [wl,1, . . . ,wl,d]T and wT l denotes the transpose of wl. To exploit label relations, we consider a label relation matrix R ∈ [0, 1]L×L, where Rl,˜l = 1 if the labels l and ˜l are related, and 0 otherwise. Let Wl,˜l denote

[wl,w˜l ] for the pair of related labels (l, ˜l). Inspired by [Argyriou et al., 2008], we assume that highly related labels often share common instances, implying that many rows of Wl,˜l should equal to zero; this can be characterized by a convexly relaxed term ‖w(l, ˜l)‖(2,1), which is a convex relaxation of ‖w(l, ˜l)‖(2,0). Thus, our goal is to find W = [w1, . . . ,wL] and an output matrix ¯Y such that:

where V is a loss function for each label, |·|1 stands for the l1-norm, ϵ controls the sparsity of | ¯ Yl - ˆ Yl|1, and η trades off the empirical risk and model complexity. Typically, V can be defined as a sum of losses on each bag; this involves label estimation for each bag and may be computationally costly, especially when there are a large number of bags. Recently, Li et al. [2009b] indicated that the estimation of a simpler statistic, i.e., the underlying class means of bags for each label, can be used for an effective approximation. This motivates us to define V ({¯ yi,l, Xi}mi=1 , wl) as

which implies that the class means of bags for each label are separated with a large margin.

Here, inspired by [Zhou and Zhang, 2006; Zhou et al., 2012], we consider to use label specified prototypes to initialize C, and the definition of ΦC(X) can be:

where C = [c11 , c12 , . . . , cLrL ] are prototypes and s(X, c) is a similarity function. Specifically, [cl1 , . . . , clrl ] are prototypes for the lth label, and rl is set as 0.1|Yl| in our experiments. Here, we measure the similarity by Gaussian Hausdorff function as in [Zhang and Wang, 2009], i.e., s(X, c) = minx∈X exp(-‖x-c‖2/δ) where δ is set to the average distance between all pairs of instances. Notice that other alternative implementations are also feasible.

Learning the Prototypes C

So far we assume that the prototypes C are available; as aforementioned, this may lead to a suboptimal performance because it leaves the learning model out of account. One alternative way is to learn {W, ¯Y} and C simultaneously, which can be formulated as

Algorithm 1 MIMLwel

Input: {Xi, ˆ Yi}mi=1 , R, η, β, ϵ; Output:W, ¯Y and C

• 1: Perform clustering for the positive bags on each label to initialize prototypes C;
• 2: while not converged do
• 3: while not converged do
• 4: Fix C and ¯Y, updateW←Eq. 5;
• 5: Fix C andW, update ¯Y←Eq. 7;
• 6: end while
• 7: FixWand ¯Y, update C←Eq. 8;
• 8: end while

Here, β is a parameter and Θ({Xi}mi=1 , C) can be realized by any clustering objective. For simplicity, we employ k-means and consider the positive bags to construct the prototypes as [Zhang andWang, 2009], i.e.,

where {Xl i+}ml i=1 are the positive bags for the lth label, and H(Xi, c) = ∑ni j=1 ‖xi,j - c‖2/ni is the average Euclidean distance.

2.2 Block Coordinate Descend Algorithm

The objective function in Eq. 3 involves W, ¯Y and C, and it is not easy to optimize with respect to all the variables simultaneously. Here we extend an efficient block coordinate descend [Tseng, 2001] algorithm. Specifically, we first optimize the objective function with respect to Wwhen ¯Y and C are fixed, then optimize it with respect to ¯Y whenW and C are fixed, and finally optimize it with respect to C when the first two are fixed. These three procedures are repeated until convergence. Algorithm 1 summarizes the pseudo-code of MIMLwel. In the following, we will present these three procedures.

Fix C and ¯Y, UpdateW

When C and ¯Y are fixed, note that the term Θ({Xi}mi=1 ,C) is not related toW and thus, we need to solve the following optimization problem:

which is convex for W. To deal with the non-smoothness of ‖Wl,˜l ‖22,1 , according to [Argyriou et al., 2008], we have,

where M = {λ|λi ≥ 0, ∑di=1 λi ≤ 1}, Dl,˜l = Diag(λ(l,˜l) ) is a diagonal matrix and D+ l,˜l denotes the pseudoinverse of Dl,˜l . Eq. 5 can be rewritten as,

Here, a small constant ς (e.g., 10-3 in our experiments) is introduced to ensure the convergence [Argyriou et al., 2008]. Eq. 6 is jointly-convex for W and {λ(l,˜l)}1≤l,˜l≤L, and thus, one can iteratively solve one of them by fixing the others as constants until convergence. Specifically, when {λ(l,˜l)}1≤l,˜l≤L is fixed and note that wl's are decoupled in Eq. 6, Eq. 6 can be addressed by L independent subproblems each corresponding to one wl via a simple quadratic programming (QP).

When W is fixed, according to [Argyriou et al., 2008], {λ(l,˜l)}Ll,˜l=1 can be solved via a close-form solution, i.e.,

where P = ‖w(l,˜l) ‖2,1 + dς. Above procedures are repeated iteratively until convergence.

Fix C andW, Update ¯Y

When C and W are fixed, note that the second and third terms in Eq. 3 are not related to ¯Y and the ¯ Yls are decoupled with respect to the objective and constraints in Eq. 3, Eq. 3 can be addressed by L independent subproblems each corresponding to one label:

Let pi denote wT l ΦC(Xi), al denote 1/ ∑mi=1 (1 - ¯ yi,l) and bl denote 1/ ∑mi=1 ¯ yi,l. Then, the objective function in Eq. 7 can be rewritten as: min¯ Yl ∑mi=1 pi{al - (al + bl)¯ yi,l}. We have the following proposition:

Proposition 1 At optimality, pi ≥ pj if ¯ yi,l ≥ ¯ yj,l .

Proof. Assume, to the contrary, that the optimal ¯ Yl does not have the same sorted order as p. Then, there are two label elements ¯ yi,l and ¯ yj,l, with pi ≥ pj but ¯ yi,l ≤ ¯ yj,l . Then pi{al - (al + bl)¯ yi,l} + pj{al - (al + bl)¯ yj,l} ≥ pi{al - (al + bl)¯ yj,l} + pj{al - (al + bl)¯ yi,l}, as (pi - pj)(¯ yi,l - ¯ yj,l) ≤ 0. Thus, ¯ Yl is not optimal, a contradiction. □

According to Proposition 1, Eq. 7 can be solved by sorting. Specifically, let B = {Xi|ˆ yi,l = 1} and ¯ B = {Xi|ˆ yi,l = 0}. We first sort the pi's with respect to the bags in ¯ B in a descending order, and then add top-valued bag of ¯ B into B iteratively, until the constraint | ¯ Yl - ˆ Yl|1 ≤ ϵ| ˆ Yl|1 is violated; all these results are candidate solutions, and we finally output the best solution among them according to the minimal objective value in Eq 7.

Fix ¯Y andW, Update C

When ¯Y andW are fixed, note that the second term in Eq. 3 is not related to C, we need to solve the following optimization problem:

Eq. 8, however, is non-convex and non-differentiable. Let g(C) denote the objective function of Eq. 8 and C(0) denote the current solution. Here, we employ the subgradient method [Shor et al., 1985] to find a refined solution ¯C, i.e., g( ¯C) ≤ g(C). Let ∇g(C) denote the subgradient of C,we update C(u) as, ∀u = 0, 1, . . . , v

where α is the step size and v is the number of iterations; they are set as 10-4/u and 10, respectively, in our experiment. Because the subgradient method is not a descent method, it is common to keep track of the best candidate found so far, i.e., the one with the smallest function value,

It is evident that we will have g( ¯C) ≤ g(C). When g( ¯C) = g(C), the algorithm stops and outputs ¯C as the final result.

3 Experiments

In this section, we first compare MIMLwel with several stateof-the-art MIML algorithms on benchmark data sets, and then evaluate MIMLwel on a real-world image annotation task.

MIMLwel is compared with four state-of-the-art MIML algorithms including MIMLSVM [Zhou and Zhang, 2006], MIMLBoost [Zhou and Zhang, 2006], RANKLOSS [Briggs et al., 2012] and KISAR [Li et al., 2012]. MIMLwel is also compared with the weak label method WELL [Sun et al., 2010]. Note that WELL works for multi-label learning, which could not be applied directly to MIML. For a fair comparison, we first employ the feature mapping learned by MIMLwel, and then apply the WELL approach. Furthermore, WELL works under transductive setting which requires to know the testing instances in advance. In our comparison, we feed the testing data without the labels as well as the training data to WELL , and evaluate the performance of WELL on the test data. Note that this setup is unfair to our proposal because our proposal does not see any test data in the training process. We call the extended version of WELL as WELL+. MIMLwel is further compared with MIMLwel-D, a degenerated version of MIMLwel that does not learn C.

In our experiments we consider four weak label ratios (W.L.R.), defined as | ˆY.,l|1/|Y.,l|1, from 10% to 40% with 10% as the interval.

The compared algorithms are all set to the best parameters recommended in their corresponding papers. For MIMLSVM, the number of clusters is set to 20% of the training bags and the Gaussian kernel width is set to 0.2. For MIMLBoost, the number of boosting rounds is set to 25. For RANKLOSS, the regularization parameter is set to the default value. For KISAR, the number of clusters is set to 50% of training bags the parameter γ is set to default value. For WELL, the parameters α and β are set to default values, and parameter γ is tuned from {100 , . . . , 104} based on the best performance on kernel alignment using five-fold crossvalidation on training data. For MIMLwel, the parameters η, β and ϵ are simply fixed to 50, 2 and 1, respectively.

We use three popular multi-label learning evaluation criteria, i.e., Hamming Loss (HL), Macro-F1 (maF1) and Micro-F1 (miF1). Given a testing data set Q = {(X1, Y1), (X2, Y2), . . . , (Xq, Yq)}, and let h(Xi) denote the binary label vector which is predicted by the classifier for Xi.

Hamming Loss(HL):

where ⊖ stands for the symmetric difference of two sets. Hamming Loss is one of the most important criteria for multilabel learning. It evaluates how many times on average a baglabel pair is incorrectly predicted. The smaller the value of hamming loss, the better the performance.

Macro-F1 (maF1):

where hl(·) and yi,l denotes the lth element of h(·) and Yi, respectively. It can be seen that Macro-F1 calculates F1 measure on individual class labels at first, and then averages over all class labels. Macro-F1 is more affected by the performance of the classes containing less examples . The larger the value of Macro-F1, the better the performance.

Micro-F1 (miF1):

where 〈·, ·〉 denotes the inner product. It can be seen that Micro-F1 globally calculates the F1 measure on the predictions over all bags and all class labels. Micro-F1 is more affected by the performance of the classes containing more examples. The larger the value of Micro-F1, the better the performance.

Text Categorization

The text categorization data 1 is collected from Reuters-21578 collection [Sebastiani, 2002]. The data set we used here contains 2,000 examples and 7 class labels, where the average number of labels for each instance is 1.15±0.37. The dimension of each instance is 243. For MIMLwel, when experts have domain knowledge about label relations, they can assign values to the elements of R. When lack of domain knowledge, the entries of the label relation matrix R can be set with alternative method, such as the estimation of the concurrence of positive bags, i.e., Rl,˜l = I(∑mi=1 I(ˆ Yi,l = 1 ∧ ˆ Yi,˜l = 1) > θ), where I is identity function and θ is set as the average concurrence between all label pairs. Ten times 10-fold cross-validation is conducted and the average performances are reported in Table 1.

1 http://lamda.nju.edu.cn/datacode/miml- text-data.htm

It can be seen that MIMLwel achieves highly competitive performance with compared methods. Specifically, pairwise t-tests at 95% significance level indicates that MIMLwel achieves significantly better performance than MIMLwel-D as well as other compared methods in most cases, as shown by the overwhelming ·'s in Table 1.

Scene Classification

The scene classification data set 2 contains 2,000 nature scene images and 5 class labels: desert, mountain, sea, sunset and tree. About 22% of images have multiple labels, and the average number of labels per image is 1.24±0.44. By using the SBN bag generator [Maron and Lozano-P´erez, 1998], each image is represented by a bag of nine 15-dimensional instances each corresponding to a patch in the image. The label relation matrix used in MIMLwel is set as the same as that in text categorization. Ten times 10-fold cross-validation is conducted on this data set and the average performances are reported in Table 2.

2 http://lamda.nju.edu.cn/datacode/miml- image-data.htm.

It can be seen that MIMLwel achieves highly competitive performance with compared methods. Specifically, pairwise t-tests at 95% significance level indicates that the performances of MIMLwel is significantly better than MIMLwelD and other compared methods in most cases.

Image Annotation

A subset of MSRA-MM database [Li et al., 2009a] is used in this experiment. In this data set, 38 class labels are considered, and there are 1,605 examples in total where around 92% of them are with more than one label, and the average number of labels per image is 3.85 ± 1.75. Each image is represented by a bag of 6-dimensional instances via image segmentation [Wang et al., 2001], where each instance corresponds to the cluster center of one segment. The label relation matrix used in MIMLwel is set as same as that in text categorization. For each trial, we randomly selected 1,400 images for training and used the remaining images for testing. Experiments are conducted for ten times and the average performances and standard deviations are reported in Table 3. MIMLBoost is not listed here because it did not return results within a reasonable time period (24 hours in our experiments) in a single trial.

It can be seen that MIMLwel obtains highly competitive performance with compared methods. Specifically, pairwise t-tests at 95% significance level confirms that MIMLwel achieves significantly better performance on this real data with a lot of labels.

Figure 1 presents two example results. The first image has seven ground-truth labels: {people, clothing, cloud, sky, water, sea, nature}. During the training process, only three labels {people, clothing, sky} are given. After training with different methods, the trained model is then used to annotate the image, and thus we get the labels predicted by each method. It can be seen that MIMLwel successfully predicts all the ground-truth labels; however, it predicts one more label, i.e., leaf, which is not in the ground-truth. Nevertheless, it is easy to see that the label leaf is consistent with the scene semantics and is not a real mistake. MIMLwel-D misses the ground-truth label nature. This might be caused by the fact that MIMLwel-D does not consider the learning of prototypes C, and thus, it may lead to a suboptimal performance. WELL+ was originally designed for single-instance learning with weak label, and it predicts some untagged ground-truth labels, but still misses a lot. The other methods KISAR, RANKLOSS and MIMLSVM almost predict as same as the tagged labels, because they were not designed to handle the weak label setting. Similar observations can be found for the second example in Figure 1.

4 Conclusion

Previous studies on multi-instance multi-label learning (MIML) typically assumed that the complete label assignment for all labels are known. In many real applications such as image annotation, however, the learning problem often suffers from weak label; that is, users usually tag only a subset of positive labels, and the untagged labels are not necessarily negative. In this paper, we propose the MIMLwel approach by assuming that highly relevant labels generally share common instances, and the class means of bags for each label are with a large margin. We formulate the problem in a general framework and provide an efficient block coordinate descent solution. Experiments show that MIMLwel is superior to state-of-the-art methods in handling the weak label setting.

There are many future works. For example, instead of using a label relation matrix R specified by domain knowledge or estimated by label co-occurrence, inspired by [Huang et al., 2012], it will be interesting to develop better approaches that incorporate a process of learning R.

Acknowledgments: We thank Yu-Feng Li for helpful discussions.