Marginalized Multi-Instance Kernels

1 Introduction

In supervised learning, each training pattern has a known class label. However, many applications only have weak label information and thus cannot be formulated as supervised learning problems. A classic example as discussed by [Dietterich et al., 1997] is drug activity prediction, where the task is to predict whether a drug molecule can bind to the targets (enzymes or cell-surface receptors). A molecule is considered useful as a drug if one of its conformations can bind to the targets. However, biochemical data can only tell the binding capability of a molecule, but not a particular conformation. In other words, we only have class labels associated with sets of patterns (bags), instead of the individual patterns (instances). Dietterich et al. called this multi-instance (MI) learning. Another well-known MI application is content-based image retrieval [Chen and Wang, 2004], where each image is a bag and each local image patch an instance.

Following Dietterich et al. 's seminal work, a number of new MI learning methods, such as the Diverse Density (DD) algorithm [Maron and Lozano-Perez, 1998], have emerged. Here, we will focus on methods based on the support vector machines (SVM), which have been highly successful in many machine learning problems. There are two main approaches to extend the standard SVM for MI data. One is to modify the SVM formulation, as in [Andrews et al., 2003; Cheung and Kwok, 2006]. However, unlike the standard SVM, they lead to non-convex optimization problems which suffer from local minima. Another approach is to design kernels directly on the bags [G¨artner et al., 2002]. These socalled MI kernels can then be used in a standard SVM. As the instance labels are unavailable, the MI kernel implicitly assumes all instances in the bag to be equally important. However, a central assumption in MI learning is that not all the instances in a positive bag are necessarily positive. Thus, many of these instances should have small contributions and the assumption made by the MI kernel is very crude.

Recall that the major difference between MI learning and traditional single-instance learning lies in the ambiguity of the instances labels. If the instance labels were available, then the MI problem could be solved much more easily. A related idea is explored in the EM-DD algorithm [Zhang and Goldman, 2002]. In each bag, the instance that is most consistent with the current hypothesis is selected as the representative of the whole bag. This converts the multiple-instance data to single-instance data and leads to improved speed and accuracy over the DD algorithm. However, it implicitly assumes that there is only one positive instance in each positive bag. In practice, both DD and EM-DD are often inferior to kernel-based MI algorithms [Andrews et al., 2003; Cheung and Kwok, 2006].

In this paper, we address the ambiguity of instance labels in the design of MI kernels by using the method of marginalized kernels [Tsuda et al., 2002]. Similar to the ExpectationMaximization (EM) algorithm, it transforms an incomplete data problem (with only the observed data) to a complete data problem (with both the observed and hidden data), which is then often easier to solve. This method has been successfully used to define marginalized kernels for strings, [Tsuda et al., 2002], trees and graphs [Mah´e et al., 2004].

The rest of this paper is organized as follows. Section 2 first gives a brief introduction to the marginalized kernel. Section 3 then describes the proposed marginalized kernel for MI classification, which is followed by an extension to MI regression in Section 4. Experimental results on a number of classification and regression data sets are presented in Section 5, and the last section gives some concluding remarks.

2 Marginalized Kernels

Like the EM algorithm, the data are assumed to be generated by a latent variable model, with observed variable x and hidden variable θ. The task is to define a (marginalized) kernel between two observed variables x1 and x2. With the help of the hidden variables, one can first define a joint kernel kz(z1, z2) over the pairs z1 = (x1, θ1) and z2 = (x2, θ2). As the hidden information is indeed unobserved, the posterior distribution of θ1 ad θ2 are obtained by some probabilistic model p(θ|x), which in turn is estimated from the data. The marginalized kernel is then obtained by taking expectation of the joint kernel w.r.t. the hidden variables, as:

where Θ is the domain of the hidden variables. When the hidden variable is continuous, the summation is replaced by an integration. Note that computing (1) may be intractable when Θ is large, and so this is an important issue in designing marginalized kernels.

3 Marginalized Kernels for MI Classification

In MI classification, we are given a set of training bags {(B1, y1), . . . , (Bm, ym)}, where Bi = {xi1, . . . , xini } is the ith bag containing instances xij's, and yi ∈ {0, 1}. For each bag Bi, the observed information is then the associated xij's while the hidden information is the unknown instance labels ci = [ci1, . . . , cini ]′ , where cij ∈ {0, 1}.

3.1 The Joint Kernel

The joint kernel is defined on two combined variables z1 = (B1, c1) and z2 = (B2, c2). It can thus utilize information on both the input (xij's) and instance labels (ci). Note that while traditional kernels (such as the polynomial and Gaussian kernels) are defined on the input part only, recent results show that the use of label information can lead to better kernels (e.g, [Cristianini et al., 2002]).

In this paper, we define the joint kernel as:

where kx(·, ·) and kc(·, ·) are kernels defined on the input and label parts of the instances, respectively. A simple and reasonable definition of kc is 1

where I(·) returns 1 when the predicate is true, and 0 otherwise. In this case, (2) is also equal to the alignment between kernel kx and the instance labels [Cristianini et al., 2002]. A high alignment thus implies a high kernel value (or similarity) between B1 and B2.

1 Other definitions are also possible, e.g., one can have kc(c1i, c2j) = 1 if c1i = c2j = 1; and 0 otherwise.

3.2 Marginalizing the Joint Kernel

To obtain the marginalized kernel, we take expectation of the joint kernel in (2) w.r.t. the hidden variables c1 and c2, as:

Computation of the conditional probability P(ci|Bi) will be postponed to Section 3.3. Note that even when P(ci|Bi) is known, a direct computation of (4) is still computationally infeasible (and takes Ω(2n1+n2 ) time) as ci ∈ {0, 1}ni .

With the joint kernel defined in (2), k(B1,B2) in (4) can be simplified as:

where ci \ cij = [ci1, . . . , ci,j-1, ci,j+1, . . . , cini ]′ . Using ∑ci\cij P(cij , ci \ cij |Bi) = P(cij |Bi) and the conditional independence assumption that P(cij|Bi) = P(cij|xij), k(B1, B2) can be reduced to

As will be shown in Section 3.4, this can now be computed in polynomial time. In particular, on using (3) as the instance label kernel, k(B1,B2) is simply

which is very intuitive. Finally, to avoid undesirable scaling problems, we normalize the kernel as in [G¨artner et al., 2002]:

Note that (5) reduces to the MI kernel k(Bi,Bj) = ∑n1 i=1 ∑n2 j=1 kx(x1i, x2j) in [G¨artner et al., 2002] if kc(·, ·) is constant. Thus, while [G¨artner et al., 2002] assumes that all the instance pairs between Bi and Bj are equally important, kc in (5) weights them differently according to the consistency of their probabilistic labels. Moreover, compared to EM-DD which chooses only one representative instance from each bag during inference, here we perform marginalization over all possible instance labels and is thus more consistent with the Bayesian framework.

3.3 Defining the Conditional Probabilities

In this section, we consider how to obtain the conditional probability P(ci|Bi). As mentioned in [Tsuda et al., 2002], an advantage of the marginalized kernel approach is that the definitions of the joint kernel and probabilistic model are completely separated. Thus, one has a lot of freedom in picking a good probabilistic model.

Using the Probabilistic Model for Diverse Density

Motivated by the success of the DD algorithm in MI learning [Maron and Lozano-Perez, 1998], we first consider using its probabilistic model for estimating P (cij |xij ). The DD algorithm finds a hypothesis h over the whole instance space 2 X by maximizing the following DD function:

Here, B+ i and Bi index all the positive and negative bags in the training set, respectively. Intuitively, h has a high DD value if all positive bags have instances close to h, while negative instances from all the negative bags are far away from h. Under this model, we can then define

where Z is a normalizing factor such that ∑h P (h|D) = 1,

and P (cij = 0|xij ) = 1 - P (cij = 1|xij ).

However, the DD function is highly nonlinear with many local minima. Hence, instead of using only one h obtained from the optimization process, it is often advantageous to use multiple hypotheses [Chen and Wang, 2004]. We then have 3

where the summation is over the set of hypotheses obtained. Note that (8) automatically weights each hypothesis by its likelihood. On the contrary, the DD-SVM in [Chen and Wang, 2004] has no such weighting and has to rely on additional heuristics to filter away the less important hypotheses. Substituting all these equations into (5), we finally have

The complete algorithm is shown in Algorithm 1.

Very recently, [Rahmani and Goldman, 2006] proposed a graph-based MI semi-supervised learning method, where the edge weight between bags B1 and B2 is roughly equal to 4

This is quite similar to (9). However, in general, (10) is not positive semi-definite and so not a valid kernel function.

2 Searching over a large X can be prohibitive. To be computationally efficient, one often performs a gradient-based optimization of the DD function by initializing from every instance in every positive bag [Chen and Wang, 2004; Maron and Lozano-Perez, 1998].

3 Note that all the probabilities here are implicitly conditioned on the training data D. For clarity, in (8) we write P(h|D) (the posterior probability of h given the data), instead of P(h).

4 In [Rahmani and Goldman, 2006], the DD values in (10) are first normalized, nonlinearly transformed and then filtered. Moreover, this weight is defined on positive bags only.

Algorithm 1 Marginalized MI kernel for classification.

Input: Training set D; A pair of bags B1 and B2 Output: k(B1,B2)

• 1: Run the DD algorithm with different initializations and store the hypotheses obtained in the array H.
• 2: for all h ∈ H do
• 3: Compute P(h|D) using (6) or (11) and store the value in array Q.
• 4: end for
• 5: for all xij ∈ B1 ∪B2 do
• 6: Compute P(cij|xij) using (7) and (8).
• 7: end for
• 8: Compute kx(x1i, x2j) for all instance pairs in B1 ×B2.
• 9: Compute k(B1,B2) as in (9), using the pre-computed values in the array Q, kx and P (cij |xij ).

Using the Training Accuracy to Improve P (h|D)

As mentioned earlier, the DD algorithm has been very successful. Note that one only has to use the hypotheses, but not their DD values, on classification. Recall that the obtained hypotheses are local minima of the DD function. While many of them may have comparable classification accuracies, as will be demonstrated in Section 5, a few hypotheses can have DD values that are much higher than the others. This is not surprising as DD value may drop significantly even if the hypothesis is close to only one negative instance. Consequently, the summation in (8) is often dominated by a few hypotheses.

To alleviate this problem while still retaining the merits of DD, we will instead define P(h|D) of each DD hypothesis to be proportional to its training accuracy. Let predh (Bi) be the label predicted by h on Bi, which is equal to 1 if maxxij∈Bi e-‖xij-h‖2 ≥ 0.5, and 0 otherwise. Then,

where m is the number of training bags and Z is again for normalization. Its superiority over the definition in (6) will be experimentally verified in Section 5.

Because of the modular design of the marginalized kernel, we can easily plug in other good estimators of P(cij|xij). For example, an EM-based approach may also be used.

3.4 Time Complexity

Let Nh be the number of DD hypotheses. In Algorithm 1, computing all the P(cij|xij)'s at Step 6 takes O((n1 + n2)Nhd) time (assuming that P(h|D)'s can be obtained in constant time or have been pre-computed), where d is the data dimensionality. Assuming that each evaluation of the kernel kx takes O(d) time, then computing all the kx(·, ·)'s in Step 8 takes O(n1n2d) time. The summation involved in k(B1, B2) of Step 9 takes O(N 2 h n1n2) time (as cij only takes 0 or 1). Thus, the total time complexity for computing k(B1,B2) is O((N 2 h + d)n1n2 + (n1 + n2)Nhd), which is polynomial.

4 Marginalized Kernels for MI Regression

In regression, we assume that each bag output yi is normalized to the range [0, 1]. Subsequently, each (hidden) instance label cij is also in [0, 1]. In this real-valued setting, we follow the extended DD model in [Amar et al., 2001], and have:

where Z(xij) ensures that ∫ 1 0 P(cij|xij)dcij = 1. It can be easily shown that Z(xij ) = 0.75 - (e-‖h-xij‖2 - 0.5)2 .

Proceeding as in Section 3, we employ the same joint kernel in (2) (but with summations of c1i and c2j replaced by integrations over [0, 1]) in the marginalized kernel k(B1, B2) of (5). Again, this can then avoid integrating over an (n1 +n2)- dimensional space.

The probability that two instances share the same realvalued label is zero, and so (3) is a poor measure of instance label similarity. Intuitively, the larger the difference between c1i and c2j, the smaller is kc(c1i, c2j). Noting that |c1i - c2j| ∈ [0, 1], we have two natural choices for kc (Figure 1) 5 :

Putting all these together, and after long but straightforward calculations, it can be shown that the marginalized MI kernel between bags B1 and B2 is given by:

where G(u, v) is equal to

when (13) is used; and is equal to

when (14) is used. Closed form expressions for these two integrals can be found in the Appendix. Moreover, as in classification, both definitions of k(B1,B2) can be computed in polynomial time.

5 In the experiments, we set β such that kc(c1i, c2j) = 0.0001 when |c1i - c2j | = 1.

When multiple hypotheses are used, k(B1, B2) can be similarly generalized to:

As for the probability P(h|D), again one can follow the extended DD model and obtain:

Alternatively, as in (11), we can also use the training accuracy of each hypothesis. Following [Dooly et al., 2002], we use maxxij∈Bi e-‖h-xij‖2 as h's predicted output of bag Bi. The error of h is then eh = ∑mi=1 (yi -maxxij∈Bi e-‖h-xij‖2 )2 , and we can define

5 Experiments

In this section, we compare the performance of the proposed marginalized kernels with the MI kernel in [G¨artner et al., 2002] on a number of MI data sets. As for the kernel defined on the input parts, we use the Gaussian kernel kx(x1i, x2j) = exp (-γ ‖x1i - x2j‖2 ), where γ is the width parameter.

5.1 MI Classification

For simplicity, the marginalized kernels defined in (6) and (11) are denoted by MG-DDV and MG-ACC, respectively.

Drug Activity Prediction

The first experiment is performed on the popular Musk1 and Musk2 data sets 6 . The task is to predict if a drug is musky. As mentioned in Section 1, each drug is considered a bag, and each of its low-energy conformations an instance. We use 10-fold cross-validation. In each fold, the DD algorithm is applied only on the training data and so the DD hypotheses cannot capture any information in the test set. For comparison, the DD-SVM [Chen and Wang, 2004] is also run.

As can be seen from Table 1, the MG-ACC kernel always performs better than the MI kernel. It also outperforms the DD-SVM, which is also using multiple DD hypotheses that are assumed to be equally important. This thus demonstrates the importance of weighting instance pairs based on the consistency of their underlying labels (Section 3.2).

Moreover, the MG-ACC kernel is better than the MG-DDV kernel. Figure 2(a) compares their corresponding P(h|D)

6 ftp://ftp.ics.uci.edu/pub/machine-learning-databases/musk/

values ((6) for MG-DDV and (11) for MG-ACC) for all the DD hypotheses obtained from a typical fold of the Musk1 data. As can be seen, for the MG-DDV kernel, a small subset of P(h|D) values are very high, and so the summation in (8) is dominated by these few hypotheses. On the other hand, for the MG-ACC kernel, the P (h|D) values vary much gradually (Figure 2(b)), and hence more hypotheses can be utilized in computing P(cij |xij). Moreover, recall that P(h|D) in (6) is proportional to h's DD value, while the one in (11) is proportional to h's training accuracy. Hence, the almost linear trend in Figure 2(b) shows that the higher the DD value, the higher is the training accuracy of the hypothesis. It thus provides another evidence for the success of the DD algorithm.

DD hypothesis (b) A closer look on the P(h|D) values for the MGACC kernel.

Figure 2: P(h|D) values obtained from a typical fold of the Musk1 data. The x-axis shows the different hypotheses obtained by the DD algorithm, sorted in increasing P (h|D) values as obtained for the MG-ACC kernel.

Image Categorization

The second experiment is on an image categorization task using the data set 7 in [Chen and Wang, 2004]. There are 10 classes (beach, flowers, horses, etc.), with each class containing 100 images. Each image is regarded as a bag, and each segment an instance. We follow exactly the same setup as [Chen and Wang, 2004]. The data is randomly divided into a training and test set, each containing 50 images of each category. Since this is a multi-class classification problem, we employ the standard one-vs-rest approach to convert it to a number of binary classification problems. The experiment is repeated 5 times, and the average testing accuracy reported.

Table 2 shows the results, along with those of the DDSVM, Hist-SVM [Chapelle et al., 1999] and MI-SVM as reported in [Chen and Wang, 2004]. As can be seen, the MGACC kernel is again superior to the MI kernel and others. To ensure that the improvement over the MI kernel is statistically significant, we repeat the experiment 50 times (instead of only 5). The difference is confirmed to be significant at the 0.05 level of significance by using the paired t-test.

5.2 MI Regression: Synthetic MuskMolecules

We performMI regression on the data set used in [Dooly et al., 2002], where the goal is to predict the binding energies of the musk molecules. We use three data sets (LJ-16.30.2, LJ-80.166.1 and LJ-160.166.1) downloaded from the author's website 8 , and three more 9 (LJ-16.50.2, LJ-80.206.1 and LJ160.566.1) used in a recent study [Cheung and Kwok, 2006]. The latter were obtained by adding irrelevant features to the former data sets, while keeping its real-valued outputs intact.

7 http://www.cs.uno.edu/∼yixin/ddsvm.html

As demonstrated in Section 5.1, the MG-ACC kernel is superior than the MG-DDV kernel. Hence, we will only experiment with the MG-ACC kernel defined with (17) here. As in [Dooly et al., 2002], we report both the percentage error (%err) 10 and mean squared error (MSE).

Table 3 shows the results, along with those of DD, EMDD and citation-kNN [Wang and Zucker, 2000] as reported in [Cheung and Kwok, 2006]. As can be seen, the proposed MG-ACC kernel with the Gaussian instance label kernel kc in (14) consistently outperforms the others. Its superiority over the MG-ACC kernel (with a linearly decaying instance label kernel) indicates that a much smaller weight should be assigned to instance pairs whose labels are quite different (Figure 1). This also explains the relatively inferior performance of the MI kernel, which weights all instance pairs equally.

6 Conclusion

In this paper, we show how to design marginalized kernels in multiple-instance learning. First, we pretend that all the hidden instance labels are known, and define a joint kernel using both the instance inputs and labels. By integrating out the hidden data, the marginalized kernel is obtained. This kernel differs from the existing MI kernel in that different instance pairs are weighted by the consistency of their probabilistic labels. Experimentally, this marginalized MI kernel always performs better than the MI kernel and also often outperforms other traditional MI learningmethods.

Note that the proposed kernel can be straightforwardly used in the regularization framework recently proposed in [Cheung and Kwok, 2006]. Moreover, because of the modularity of the marginalized kernel, we will also explore even better definitions of the joint kernel and probabilistic model.

Acknowledgments

This research has been partially supported by the Research Grants Council of the Hong Kong Special Administrative Region.

8 http://www.cs.wustl.edu/∼sg/multi-inst-data. There are four more data sets available. However, they are easier variations of the three that we used, and so are dropped in this study.

9 http://www.cs.ust.hk/∼jamesk/papers/icml06 data.zip

10 %err is the classification error obtained by thresholding both the target output and the predicted output at 0.5.

A Appendix

Using Mathematica, it can be shown that (16),

where

and erf(u) = 2 √π ∫ u 0 exp (-t2 )dt is the so-called error function. Similarly, (15) can be shown to be