Multi-Instance Learning with Key Instance Shift

1 Introduction

Multi-instance learning (MIL) [Herrera et al., 2016] deals with the tasks where each example is represented by a bag of instances. A bag is positive if it contains at least one positive instance, and negative otherwise. The instances that trigger the positive labels are also called key instances. Only bag labels are observed, whereas instance labels are unknown in MIL. MIL has been applied in many domains, including image classification [Zhang et al., 2002], text categorization [Andrews et al., 2002], and web mining [Zhou et al., 2005], etc.

Previous studies of MIL typically assume that the training and test data are drawn from the same distribution, which may be violated in many real-world tasks. The distribution discrepancy may arise when training and test data are collected in different time, location or with different labeling cost, etc.

∗This research was supported by the NSFC (61333014) and Huawei Fund (YBN2017030027).

Take text categorization for example, supposing that we want to judge whether a text is about 'sport' and the training/test data are collected in 2012/2016, respectively. Then compared with training data, test data may have less texts about 'Kobe Bryant', but more about 'Stephen Curry'. Here the paragraphs containing 'Kobe Bryant' or 'Stephen Curry' can be regarded as key instances. In this case, the distribution of key instances changes between training and test phase due to different collection time. Also, if the training/test data are collected in America/China respectively, then compared with training data, test data may have less texts about 'baseball', but more about 'table tennis'. Here the paragraphs with 'baseball' or 'table tennis' can be regarded as key instances. The distribution of key instances varies due to different collection locations. In this paper, we formalize this problem as MIL with key instance shift and propose the MIKI (Multi-Instance with Key Instance shift) method to solve it.

MIKI follows the embedding based manner [Chen et al., 2006], which transforms bags into single instance vectors via embedding. Instance prototypes are selected to encode both bag-level information and key instance shift information. First, a weighted multi-class model is trained to select the instances with high positiveness as instance prototypes, and the bags are transformed into informative vector representations with selected instance prototypes. Then, we learn the weights for the transformed bag vectors and incorporate the original instance weights into them to narrow the gap between training/test distributions. Finally, a model is learned by using the new representations and their weights. Experiments on different data sets demonstrate the effectiveness of our approach when key instance shift occurs. Even without key instance shift, MIKI still works comparable with the state-of-the-art methods.

The rest of this paper is organized as follows. Section 2 reviews related work. Section 3 presents the proposed method. Section 4 reports the experimental results. Section 5 applies the proposed method to moving object localization problem and Section 6 concludes.

2 RelatedWork

Multi-instance learning was first proposed in [Dietterich et al., 1997]. Since then, many approaches have been proposed, which mainly fall into two categories: some try to directly solve the MIL problem in either instance level [Maron and Lozano-P´erez, 1998; Li et al., 2009; Faria et al., 2017] or bag level [G¨artner et al., 2002; Zhou et al., 2009], while the others transformMIL into single instance learning via embedding, among which MILES [Chen et al., 2006] is a typical representative, and many methods [Amores, 2015; Yuan et al., 2016; Wei et al., 2017] have been proposed recently following this manner. It is noteworthy that previous MIL methods typically assume that the training and test data follow the same distribution. In contrast, we consider the key instance shift problem, which has not been thoroughly studied to our best knowledge.

In addition, due to the differences in gathering data, distribution change between training and test data may always arise, among which covariate shift [Shimodaira, 2000] has attracted much attention. In covariate shift, the input distribution P(x) is different between training and test phase but the conditional distribution of output P(y|x) remains unchanged. A common approach for covariate shift is importance reweighting, which assigns each training instance x with a weight w(x) = pte(x)/ptr(x) to diminish the discrepancy of training and test marginals by some criteria [Sugiyama et al., 2012]. Note that test data is needed to estimate the difference of distribution. Many methods have been proposed to estimate the weight, such as KMM [Huang et al., 2006], KLIEP [Sugiyama et al., 2008], LSIF and uLSIF [Kanamori et al., 2009], etc. However, all of these studies focus on single-instance learning.

The most related literature of our work is [Zhang and Zhou, 2014], which considers the setting when MIL encounters distribution change and proposes the MICS method. In contrast to considering situations where the bag label is decided by multiple instances and their relations [Zhang and Zhou, 2014], in this paper, we follow the standard MIL setting that bag labels are determined by the key instances, and consider the distribution change problem of key instances.

3 MIL with Key Instance Shift

3.1 Problem Statement and Notations

Let X = Rd denote the instance space and Y = {-1,+1} denote label space. The learner is given a data set with m training bags Btr = {(Xtr 1 , y1), . . . , (Xtr i , yi), . . . , (Xtr m , ym)}, where Xi = {xi1, . . . , xij , . . . , xini } is a bag with xij ∈ X representing an instance. If there exists any positive instance in Xi, then Xi is a positive bag with yi = +1; otherwise Xi is negative with yi = -1. Those positive instances are also called key instances, which trigger the positive labels. Note that only bag labels are available, yet specific instance labels are unknown. The learner is also given a set of n unlabeled test bags Bte = {Xte 1 , . . . ,X te n }. In MIL with key instance shift problem, the distributions of key instances in training and test phase are different. Let P(·) denote the distribution, x∗ refer to the key instances, then we have P(xtr ∗ ) ̸= P(xte ∗ ) in this setting. In this work, we focus on transductive setting: given Btr and Bte, where P(xtr ∗ ) ̸= P(xte ∗ ), our goal is to learn a mapping f : 2X → Y that works fine for test data.

3.2 ProposedMethod

MIKI follows the embedding based manner [Chen et al., 2006], which transforms bags into single instance vectors via embedding. To handle the key instance shift problem, we try to select key instance candidates from both training and test sets as instance prototypes so that both bag-level information and key instance shift information can be encoded. Specifically, assuming that the positive instances belong to different subconcepts, then key instance shift may fall into any of these sub-concepts. Supposing that there are K sub-concepts, together with the negative concept, we build a (K + 1)-class model to distinguish different sub-concepts and the negative concept. If an instance belongs to any sub-concept with a high score, it would be regarded as a key instance candidate with high probability. In this way, different shift information can be captured. Moreover, in order to alleviate the influence of key instance shift, we introduce the instance weights to balance different distributions (i.e., higher/lower weights for underrepresented/overrepresented instances), so that the selected instance prototypes may include more key instances and encode more key instance shift information. Similarly, after getting the transformed bag vectors, we learn the weights for them to narrow the gap of training/test distributions. Note that if an instance is important, the bag containing it should also be valued, so we further incorporate weights of the original instances into the weights of the transformed bag vectors. The final model is learned with the transformed bag vectors and their weights. Figure 1 summarizes our MIKI approach.

Instance Prototype Learning

In instance prototype learning phase, a weighted multi-class model is trained to select key instance candidates as instance prototypes. We use an iterative framework to alternately build the multi-class model and optimize the selected key instance candidates, and then update the instance weights 1 . Algorithm 1 summarizes the instance prototype learning framework.

Specifically, in each iteration, a weighted (K + 1)-class model MD is trained for the K sub-concepts of positive instances and the negative concept. If an instance belongs to any sub-concept with a high score, it would be regarded with high positiveness. To represent the positiveness, we denote the probability of instance xij belonging to class k as Prk ij , and calculate the positiveness score Sij for each instance xij:

1 The importance weighting technique is same to the one introduced in the next section.

Algorithm 1 Instance Prototype Learning for MIKI

Input: Training bags Btr = {(Xtr i , yi)}mi=1, Testing bags Bte = {Xte j }nj=1, Instance selection parameters ntr θ and nte θ .

Output: Instance Prototype Set D.

• 1: Initialize all training instance weights w.
• 2: repeat
• 3: Train multi-class modelMD by Algorithm 2;
• 4: Calculate positiveness score for all instances by Eq. 1;
• 5: Separate instances into Ctr p , Ctr n , Cte p and Cte n by Eq. 4;
• 6: Reestimate the weights wp (wn ) for instances in Ctr p (Ctr n ) to approximate instances in Cte p (Cte n );
• 7: until max iteration is reached.
• 8: Output D = Cp tr ∪ Cp te .

Algorithm 2 shows the details of learning MD. We first run k-means on all instances from positive bags and initialize their labels as the associated cluster numbers, and assign all instances from negative bags with label 0. A multi-class SVM model M is trained with the weighted instances and their assigned labels. Given an instance xij, the model Mwill output the probability Prk ij of xij belonging to class k. Then for each instance xij from positive bags, its label is updated to be

The labels of instances in negative bags stay unchanged. For each positive bag Xi, if all instances are labeled negative, the label of the instance (denote as xip) with the highest positiveness score is adjusted to be

so that each positive bag contains at least one positive instance and the initialized false positives are calibrated through iteration. The step sequence interleaves until no label changes or max iteration is reached, then the model MD is obtained.

With the obtained model MD, the positiveness score of each instance is estimated and key instance candidates are selected. Specifically, let Str θ (Ste θ ) denote the ntr θ -th (nte θ -th) highest score of all training (test) instances, we then separate the instances into key instance candidates and negative instance candidates according to their positiveness scores:

Here, C tr p and C te p are those instances with higher positiveness scores, so they are more likely to be potential key instances and carry the key instance shift information.

After the separation, we reestimate the weights for training instances in key (negative) instance candidates correspondingly, i.e., reestimate the weights for C tr p (C tr n ) by using C te p (C te n ). Thus, all training instance weights are updated. Then the model MD will be trained again with updated weights and the key instance candidates will be updated. This step sequence interleaves until the max iteration is reached, and the

Algorithm 2 Learning algorithm for multi-class model MD

Input: Training bags Btr = {(Xtr i , yi)}mi=1, Training instance weights w, Positive cluster number K.

Output: Multi-class modelMD

• 1: Initialize the labels for all training instances;
• 2: repeat
• 3: Train multi-class model with the weighted training instances;
• 4: Update the labels of all instances from positive bags by Eq. 2;
• 5: For each positive bag, if all instances are labeled negative, select the most positive one and adjust its label by Eq. 3;
• 6: until no label changes or max iteration is reached.
• 7: Output the final model asMD.

selected instance prototypes (i.e., C tr p ∪C te p ) are outputted as instance prototype set D.

With D, we map both training and test bags into new vector representations following the typical procedure [Chen et al., 2006]. Concretely, each bag Xi is mapped into a (ntr θ +nte θ )- dimensional vector vi, and the j-th attribute vij is

where Dj is the j-th term of D. The new representations keep both bag-level information and key instance shift information.

Weight Learning

In this section, we present the details of learning the weights for transformed training vectors. Given transformed training vectors {vtr i }mi=1 with density ptr(v) and transformed test vectors {vte i }ni=1 with density pte(v), we want to estimate the importance w(v) = pte(v)/ptr(v) for all transformed training vectors. Following [Kanamori et al., 2009], we model the weight w(v) by the following linear model:

where α = (α1, . . . , αb)T are parameters to be learned and {ϕl(v)}bl=1 are basis functions satisfying ϕl(v) ≥ 0 for all v and l. Here we choose a fixed number of Gaussian kernels centered at test points as the basis functions. We need to estimate the parameters {αl}bl=1 to make ˆw(v) approximate to w(v). To achieve this, we minimize the following squared error L0(v):

since the last term in Eq. 7 is a constant given the training set, it can be safely ignored. Using pte(v) = w(v)ptr(v), we denote the first two terms by L(v):

Approximating to the expectations in L(v) by empirical averages, we obtain ˆL(v):

where ˆH is the b×b matrix with the (l, l′ )-th element ˆHl,l′ = ∑mi=1 ϕl(vtr i )ϕl′(vtr i )/m and ˆh is the b-dimensional vector with the l-th element ˆhl = ∑nj=1 ϕl(vte j )/n. Based on Eq. 9, we get the following optimization problem:

Eq. 10 is an unconstrained convex quadratic program, so the solution can be analytically computed as α = ( ˆH + λIb)-1ˆh, where Ib is the b-dimensional identity matrix, thus the parameters can be efficiently estimated and the weight of each training sample can be obtained. This importance weighting technique is exactly the one used in Algorithm 1 with v replaced by x.

With the aforementioned method, we can get the weights for all transformed training vectors, and we denote the weights as W 0 . Moreover, we address that if a bag contains an instance that should be valued, the bag should be valued too, thus we further incorporate instance weights into the transformed bag weights. Note that when we learn the instance prototypes, the instances are separated into C tr p (C te p ) and C tr n (C te n ) according to their positiveness. We follow the same procedure to learn the weights for instances in C tr p (C tr n ) to approximate the instances in C te p (C te n ), separately. Thus, all training instance weights are estimated and they are further integrated into the transformed bag weights. Concretely, for training bag Xtr i and its transformed vector vtr i , denote the weight learned from the transformed bag vectors as W 0 i and the weights for instances in this bag as {wij}ni j=1 , the final weight of vtr i is set to be:

At the end of MIKI, we use the transformed training feature vectors and their corresponding weights to learn the classification model, which is employed it to classify the transformed test feature vectors.

Note that the number of selected instance prototypes in MIKI is much smaller than that used in MILES and many other embedding based methods, and thus, MIKI is more efficient in this aspect. The iterative instance prototype learning process of MIKI is similar to miSVM [Andrews et al., 2002], and thus, mechanisms for time cost control and acceleration for miSVM can be applied.

4 Experiments

The experiments are performed on both synthetic data and real world datasets. We compare the proposed method with many state-of-the-art algorithms, including instance-level methods miSVM and MISVM [Andrews et al., 2002], and bag-level methods miGraph [Zhou et al., 2009], MILES [Chen et al., 2006] and MILDE [Amores, 2015]. We also derive three variants for comparison. The first one miSVM+, works by estimating the weights for all instances, and incorporating them directly to miSVM. The second one MILES+, is a variant of MILES and the weights are obtained based on the transformed feature vectors. In addition, since we have used instances from test bags in MIKI, we derive the third variant MILES++, using all instances from both training and test bags for feature mapping with importance weighting technique incorporated. Furthermore, we also compare with MICS [Zhang and Zhou, 2014], which focuses on the setting of MIL with distribution change. RBF kernel is used for all SVM-based methods. For MIKI, we simply set K to 5 for synthetic dataset and 10 for the other datasets without any tuning, and set max iteration to 5 to accelerate the method. Other parameters are selected via 5-fold cross validation.

4.1 Experiments on Synthetic Data

We first perform experiments on synthetic dataset. We generate two sub-concepts of positive instances which are represented by Gaussian distribution P1 = N(µ1, σ2 ) and P2 = N(µ2, σ2 ), and one negative concept represented by P3 = N(µ3, σ2 ). Here we set µ1 = (1, 1), µ2 = (2, 2), µ3 = (3.5, 2.5), σ2 = (0.5, 0.5). Each bag contains 10 instances, and each positive bag contains 1 positive instance, which is from one of the sub-concepts (i.e., P1 or P2). We generate 200 negative and 200 positive bags. Half of the positive bags contain positive instances from one sub-concept, and the other half from another.

We follow the typically deliberately biased sampling procedure [Zadrozny, 2004] to separate the bags into disjoint training and test sets. Specifically, we define a random variable si for each bag, where si = 1 means that the i-th bag is selected into training set, and si = 0 otherwise. For positive bag Xi, denote the key instance as xi∗, then the positive bags are sampled following the rules below:

Here, SC1 and SC2 denote different sub-concepts (i.e.,P1 and P2) and a = 0.8, b = 0.2. In other words, compared with test data, there are more positive bags in training data containing positive instances from sub-concept P1, but less from P2.

We repeat experiments for 30 times by using the sampling procedure to generate training and test sets. As shown in Table 1, our method outperforms all other ones. Though distribution change is considered, miSVM+, MILES+ and MILES++ do not show significant improvement, verifying that simply applying single-instance distribution shift approaches to MIL does not work. MICS does not get favorable result too.

Furthermore, we examine the influence of parameter K. In MIKI, we simply set K to 5, but not the ground-truth number of sub-concepts. The results in Figure 2 show that the behavior tends to get better as the value of K getting closed to the ground-truth. However, our method is not that sensitive to K. Moreover, we observe that almost 88% of the selected instance prototypes of MIKI are positive, verifying the effectiveness of selecting 'positive' instances in MIKI.

4.2 Experiments on Text Categorization

We then perform experiments on text categorization tasks. We derive 25 data sets from the popularly used 20 Newsgroups corpora. The documents belong to 6 main classes and 20 subclasses. For each dataset, we set one main class (e.g., 'comp') as positive, and the others as negative. For positive class, two sub-classes (e.g., 'comp.sys.ibm.pc' and 'comp.windows.x') are used as different sub-concepts. 200 positive and 200 negative bags are generated. Each positive bag contains averagely 1.5 instances from positive class, and the negative instances are randomly and uniformly drawn from the negative classes. Half of the positive bags contain positive instances from one sub-concept, and the other half from another sub-concept. An instance is a post represented by 100-dimensional LDA feature [Blei et al., 2003].

Similarly, the biased sampling procedure is used to separate bags. Eq. 12 is used to sample the bags, with SC1 and SC2 being different sub-classes, and a = 0.8, b = 0.2. Thus, compared with test data, there are more positive instances in training bags from SC1, but less from SC2.

We repeat experiments for 30 times by using the sampling procedure to generate training and test sets. The results are reported in Table 2, with the win/tie/loss counts in the last row. As we can see, MIKI achieves 22 times the best performance, which is significantly better than other algorithms. MICS does not work well because as we have mentioned in the end of related work, it is designed to handle other types of distribution shift rather than key instance shift. It is interesting to see that miSVM+ and MILES+/MILES++ are not necessarily better than miSVM and MILES, respectively. This suggests that a simple extension by applying single-instance distribution shift approach does not work. One important reason is that in multi-instance learning there is no accurate information of instance label, and thus, instance weighting approach which is effective for single-instance setting may become misleading in multi-instance setting.

4.3 Experiments on non-Shift Data

We also run experiments on the popularly used benchmark datasets to validate the robustness of MIKI in no key instance shift setting. We conduct ten times 10-fold cross validations as previous studies done. As shown in Table 4, our method behaves comparable with state-of-the-art methods. The results indicate that although it is designed for key instance shift setting, our method still works fine in non-shift setting, demonstrating the robustness of MIKI. This is reasonable, since if there is no change of distribution, the estimated weights should be approximately equal to 1, thus the results of our method should be similar to other embedding based methods.

5 Application toMoving Object Localization

With the help of RFID or wireless LAN, moving object localization is widely applied in many areas such as locating cleaning robot, tracing livestock in the farm, tracking inmate in prison [Ferrer et al., 2010], and it has been studied by using machine learning techniques [Senta et al., 2007]. However, sometimes, we only care about if an entity has been to a target region, but not the exact location at each moment. Thus, investing too much efforts in gathering numerous sensing data and their exact location is not necessary. Instead, we only need to know whether the trajectory is intersected with the target region. However, even with the data collected in this way, there may still exist inconsistencies between training and test data, leading to key instance shift. For example, as shown in Figure 3, it's the top view of a room. Some RFID readers (the rectangles) are placed in the room to locate an moving entity with a RFID tag (the triangle) attached. A particular region (the circle) is marked as the target region. The entity is moving in the room and the sensing data of its location is collected by the readers. If it goes through the target region, then the trajectory is marked positive. However, if the environment changes between training and test phase, say, training data is collected from the entities with faster speed, whereas test data is collected from slower entities, then distribution discrepancy may arise between training and test phase, leading to the performance degradation of the obtained model.

In this section, we formalize the aforementioned setting as an MIL problem. It's natural to regard each trajectory as a bag and the data from different location as instances, and the data collected from the target region is regarded as key instance. In addition, the inconsistencies of data collection result in the problem of key instance shift, which may seriously debase the performance of traditional MIL algorithms and make it necessary to consider the distribution change between training and test phase. In this paper, we apply MIKI to this problem and run experiments to verify its effectiveness.

We sample 80 bags from training data and test data each time, and we collect 30 sets of data in this way. As the results in Table 3 show, MIKI outperforms all other algorithms. The performances of the variants are even worse than miSVM and MILES, verifying again that direct adaptation of importance weighting technique can not work. Moreover, MICS behaves unfavorable, which inspires us that the distribution change of key instances should be addressed.

6 Conclusion

Previous studies of multi-instance learning (MIL) typically assume I.I.D. distribution, which may be violated in many applications. In this paper, we address the problem of MIL with key instance shift and propose an embedding based method MIKI to solve it. Experiments demonstrate the effectiveness of MIKI when key instance shift happens.

We mainly address the key instance shift problem of MIL in this work. We can also consider the scenario that distribution of negative instances varies. More sophisticatedly, distribution of both positive and negative instances may change in some tasks. The success of our proposed methods suggest that it is helpful to make good use of the instances in test bags.