A Unifying Framework for Learning Bag Labels from Generalized Multiple-Instance Data

1 Introduction

Many real-world problem domains require learning from structured data. For example, consider the content-based image retrieval (CBIR) domain, in which the goal is to retrieve images that contain some object or scene of interest [Maron and Ratan, 1998]. If the image is segmented, then the presence of an object within the image corresponds to the presence of certain classes of segments within the image. For such problems, the multiple-instance (MI) setting offers a richer representation for these structured objects as sets, or "bags," of feature vectors, each of which is called an "instance" [Dietterich et al., 1997]. In CBIR, an image is a bag of segments, each of which can be described with a feature vector. The MI setting can also be applied to other problems with structured objects, such as text categorization, audio classification, or drug discovery.

In the "standard" MI setting, it is assumed that a bag is positive if it contains at least one instance from the positive class of instances. This makes sense for many CBIR problems; for example, an image contains an apple if some segment corresponds to an apple. However, prior work has observed that a more complex relationship is required for many real-world problems. Consider a CBIR problem in which the task is to distinguish pictures of deserts, oceans, and beaches [Foulds and Frank, 2010]. Segments in these images are primarily either sand or water. However, in this case, the presence of both sand and water is required to distinguish beaches from deserts (only sand) or oceans (only water). Similarly, Wang et al. [2004] study the problem of identifying members of the Thioredoxin-fold "superfamily" of proteins. A sequence of amino acids corresponding to a protein (bag) is represented using properties of subsequences (instances) surrounding a central "motif" within the protein sequence. To be a member of this superfamily, the sequence must contain certain subsequences and exclude others. Such concepts can be learned under the generalized MI (GMI) framework [Weidmann et al., 2003; Scott et al., 2005]. Here, we assume that some types of instances are "attractive" and that others are "repulsive." For a bag to be positive, it must contain a certain number of attractive instance types and exclude some number of the repulsive instance types. The generalization allows for richer relationships between bag and instance labels than the standard MI setting, which is a special case of GMI as follows: there is one attractive type, no repulsive types, and a bag is labeled positive if it has at least one instance from the attractive type.

Many existing supervised learning approaches such as decision trees [Blockeel et al., 2005] and support vector machines (SVMs) [Andrews et al., 2003] have been extended to standard MI learning, but none of these approaches are directly applicable to the GMI setting. Furthermore, many of these approaches extend instance-based approaches, and therefore use instance-level hypothesis classes to label bags. An alternative, successfully employed by other prior work [G¨artner et al., 2002; Chen et al., 2006; Foulds, 2008; Zhou et al., 2009; Amores, 2013a], is to explicitly or implicitly construct a feature vector representation for bags and use a standard supervised classifier to solve the bag-labeling task. In fact, these bag-level classifiers often outperform their instance-level counterparts in practice in terms of both accuracy and efficiency on the bag-labeling task [Amores, 2013b; Doran and Ray, 2013; Cheplygina et al., 2015]. Given this observation, we are interested in the question: how can we appropriately represent bags so that standard supervised approaches can learn GMI concepts?

Kernel methods are a well-studied set of approaches for implicitly constructing feature vector representations of arbitrary objects. Given a set of objects X, a positive-definite function k : X ⇥ X ! R is a "kernel function" that is implicitly associated with a "feature map" φ : X ! H such that k(x↪ x0 ) = hφ(x)↪ φ(x0 )iH. Given the uncountably infinite family of potential kernel functions, how can we choose a class of kernel functions that are appropriate for the GMI setting? Some of the first work on MI kernels showed that a family of set kernels could be used to represent standard MI concepts [G¨artner et al., 2002]. However, the desirable properties of such kernels hold only under the standard MI assumption in which a bag's label is the logical disjunction of its instances' labels. Subsequent work devised a specialized kernel for the GMI setting [Tao et al., 2004; 2008]. In our work, we propose a new formal generative model that describes GMI concepts in a setting where bags are distributions over instances. We show that in this generative model, a family of distribution-distance kernels can be successfully applied to the GMI setting. In particular, we show that a universal kernel based on the maximum mean discrepancy (MMD) distance between distributions is sufficient for representing GMI concepts given some weak assumptions [Christmann and Steinwart, 2010].

Next, we show that some existing bag-level representations of GMI data can be viewed as approximations of certain distribution-distance or distribution-embedding kernels. Prior work [Amores, 2013b] proposed a taxonomy of MI learning algorithms that included categories for "bag-space" approaches that implicitly map bags into a feature space via kernels or distance metrics, and "embedded-space" approaches that first construct feature vectors from bags before applying supervised learning techniques. By showing that some of these embedded-space approaches are actually approximations to bag-space approaches, our work implies that these two separate categories can be unified into a single framework for understanding bag-level representations.

Finally, we empirically evaluate the performance in terms of both accuracy and efficiency of distribution kernels as well as existing bag-level representations across 72 datasets from a variety of real-world domains. We show that distributionbased kernels yield the best performance in terms of these two metrics. Thus, in addition to the theoretical understanding provided by our results, we also provide practical recommendations regarding the use of distribution-based kernels for a wide variety of MI and GMI problems.

2 The GMI Generative Model

In this section, we describe the generative process for GMI data. Although the original work on standard MI learning leaves the precise generative process unspecified [Dietterich et al., 1997], subsequent theoretical analyses either assume the bags are independent and identically distributed (IID)

samples from a single distribution across bags [Blum and Kalai, 1998], or are drawn from an arbitrary distribution over tuples of instances [Sabato and Tishby, 2012]. Our approach builds on a more recently proposed generative model [Doran and Ray, 2014] that assumes that bags correspond to distinct distributions over instances. This model makes fewer assumptions about the generative process than prior work. It is motivated by domains such as 3-dimensional Quantitative Structure-Activity Relationship (3D-QSAR), where a molecule exists in a dynamic equilibrium whose distribution over shapes is governed by the energy associated with each shape, or text categorization, for which existing successful models such as topic models already treat documents as topic-specific distributions over words or passages [Blei et al., 2003]. We extend this distribution-based model of MI data to the GMI setting.

Formally, let X be the space of instances, and P(·) denote the space of Borel probability measures over its argument. Then P(X), the space of probability measures over instances, is the space of bags. Hence, each bag B corresponds to a specific distribution over instances, denoted Pr(x ♣ B). Bags themselves are drawn from some fixed distribution over bags, which is given by DB 2 P(P(X)). After being sampled, these bags are labeled by a function F : P(X) ! ¶-1↪+1♦. In GMI learning, it is assumed that some types of instances are "attractive" and that others are "repulsive." For a bag to be labeled positive by F, it must contain or "hit" a certain number of attractive instance types and exclude or "miss" some number of the repulsive instance types. Figure 1 shows a GMI concept "sunny beach," for which the attractive types are sand and water, and a repulsive type is cloud. Let A = ¶Ai♦ai=1 denote a set of attractive types, and R = ¶Ri♦ri=1 be a set of repulsive types, all disjoint closed subsets of X. The set of "other" instances in the support of the instance distribution DX is defined as O , suppDX - SCi2A[R Ci, assumed to be a closed set.

Note that this is equivalent to the assumption that there is a continuous function that defines the boundary with separation between each of the types of instances. Formally, we say that a bag B hits a type Ci 2 A [ R if RCi dP(x ♣ B) ≥ ⇡i for threshold ⇡i and misses Ci if RCi dP(x ♣ B) = 0. That is, there must be probability ⇡i of sampling an instance from type Ci within a bag to hit the type, or zero probability to miss the type. Given this notion, we can extend the distributionbased generative process to the GMI setting:

Definition 1 (GMI-GEN). Let ⇧A = ¶⇡i♦ai=1 and ⇧R = ¶⇡i♦ri=1 be sets of positive type-specific threshold parameters for the attractive and repulsive types. Then GMI-GEN(A↪ R↪ ⇧A↪ ⇧R↪ ↵↪ ⇢) is the set of (DB↪ F) s.t.:

1. For each bag B in the support of DB, and each type in A [ R, B either hits or misses the type.
2. The support of the instance distribution defined by DX , R B dPrDB (B) is a compact set.
3. A bag is positive if and only if it hits at least ↵ of the types in A and misses at least ⇢ of the types in R.

Condition 3 allows for flexibility in using the attractive and repulsive types to define classes. To illustrate, consider a variant of our "sunny beach" example called "nice beach" with an extra repulsive type trash. A beach is nice if it does not have both trash and cloud, so selecting ⇢ = 1 with these two types can be used to express this condition.

An assumption of the standard MI setting is that there also exists some instance-labeling function f : X ! ¶-1↪+1♦, which has the relationship with F that F should label a bag B 2 P(X) negative if the labels of the instances sampled from B are almost surely negative, and positive if there is some nonzero probability ⇡ of sampling a positive instance within the bag. Note that given an instance-labeling function f and X+ = ¶x 2 X : f(x) = +1♦, the (DB↪ F) in GMI-GEN(¶X+♦↪ ?↪ ¶⇡♦↪ ?↪ 1↪ 0) correspond to the standard MI concepts. Hence, GMI-GEN is indeed a generalization of the standard MI setting. Having described possible generative processes for GMI data, we can begin to discuss kernel methods for learning from data generated in the manner described in Definition 1.

3 Learning GMI-GENConcepts with Kernels

We first show that certain classes of distribution kernels are sufficient to represent concepts in GMI-GEN. Then, we show that existing bag kernels and feature space embeddings can be viewed under one unifying framework provided by our generative process.

3.1 Distribution Kernels for GMI Data

Given our generative model where bags are distributions, we are interested in the application of kernels constructed for learning from distributions, which have been explored by prior work [Muandet et al., 2012]. One particularly successful kernel-based representation for distributions is the "mean embedding." Given an instance space X and instance kernel k with feature map φ, the mean embedding of a distribution P 2 P(X) is given by θ(P) , Ex⇠P[φ(x)]. The associated

"mean embedding kernel" K defined on distributions is given by K(P↪ Q) , E(x↪x0 )⇠P⇥Q[k(x↪ x0 )] for P↪ Q 2 P(X).

The mean embedding has some desirable theoretical properties. First, given a sample X ⇠ P n , the empirical mean embedding b θ(X) , 1n Pxi2X φ(xi) converges quickly to the underlying embedding θ(P) as sample size n increases [Smola et al., 2007]. Furthermore, whenever the instance kernel k is characteristic, the mean embedding θ is an injective mapping of distributions into the kernel feature space, or reproducing kernel Hilbert space (RKHS), H [Sriperumbudur et al., 2010]. This means that distinct distributions will have unique feature representations. A kernel is characteristic if it is universal, meaning that its RKHS H, interpreted as a space of functions over X, is uniformly dense in C(X), the space of bounded, continuous functions over X [Micchelli et al., 2006]. The commonly used radial basis function (RBF) kernel, k(x↪ x0 ) = e-γkx-x0 k2 , is universal.

Prior work describes the class of functions over distributions that can be represented using the mean embedding kernel [Muandet et al., 2012]. In particular, the RKHS of the mean embedding kernel with some universal instance kernel is dense in the set:

These are the functions we get by taking the expected value of a fixed but arbitrary continuous function with respect to probability distributions. However, the function class F is a strict subset of C(P(X)), the set of all bounded, continuous functions over the set of probability distributions, with respect to the weak topology on P(X) [Muandet et al., 2012]. Thus, the mean embedding defined in terms of a universal kernel with respect to C(X) is not itself universal with respect to C(P(X)).

MMD. However, as shown by Christmann and Steinwart [2010], it is possible to construct a universal kernel with respect to C(P(X)) using an additional level of embedding. That is, using the RBF kernel defined with respect to the mean embeddings of two distributions P and Q, k(P↪Q) = e-γkθ(P)-θ(Q)k2H , is universal with respect to C(P(X)) when θ is injective and X is compact. Note that this kernel is equivalent in form to the RBF kernel but treats H rather than X as the input space. Since the quantity kθ(P) -θ(Q)kH is known as the MMD [Smola et al., 2007], we refer to this as the MMD kernel. This iterated embedding is also called the "level-2" embedding by prior work [Muandet et al., 2012].

Are MMD distribution kernels expressive enough to represent bag-level GMI concepts from Definition 1? Our first result answers this question affirmatively.

Proposition 1. Let (DB↪ F) be an element of GMI-GEN(A↪R↪⇧A↪⇧R↪ ↵↪ ⇢). Then the universal MMD kernel can arbitrarily approximate in the uniform norm a function that separates bags according to F .

Proof. Since a universal kernel can arbitrarily approximate continuous functions, it suffices to show that a GMI concept F is separable with a continuous function.

Taking for granted that X is a normal space, 1 by Urysohn's Lemma, there exists a continuous function hi : X ! [0↪ 1] for each type Ci such that x 2 Ci =) hi(x) = 1 and x 62 Ci ^ x 2 suppDX =) hi(x) = 0. This follows from the assumption that all sets of instance types and their complements within suppDX are disjoint closed sets.

Given the existence of the hi, the function Hi(B) = min n1↪ 1 ⇡i RX hi dP(x ♣ B)o is 1 if B hits type Ci and 0 if B misses Ci. Furthermore, each Hi is a continuous function over bags since it is a composition of continuous functions.

Then, for a GMI concept F as described in Definition 1, the following concept separates F: G(B) = 2 min nPai=1 Hi(B) - ↵↪ Pa+r i=a+1 (1 - Hi(B)) - ⇢o + 1. The minimum is at least 1 if the number of hits and misses are both above their respective thresholds ↵ and ⇢. Thus, G(B) ≥ 1 for positive bags according to F , and G(B)  -1 for negative bags.

Finally, note that G is a composition of the continuous min function with continuous functions over bags, so it is in fact continuous and can be approximated by an element of the RKHS of the MMD kernel.

A corollary of this result is that the mean embedding kernel suffices to represent standard MI concepts. Recall that standard MI concepts are of the form GMI-GEN(¶X+♦↪?↪ ¶⇡♦↪?↪ 1↪ 0) for some ⇡ > 0 and X+ = ¶x 2 X : f(x) = +1♦, where f is an instancelabeling function. Then we have:

Corollary 1. Let (DB↪ F) be a standard MI concept, an element of GMI-GEN(¶X+♦↪ ?↪ ¶⇡♦↪ ?↪ 1↪ 0). Then the mean embedding kernel with a universal instance kernel can separate bags with respect to F .

Proof. By Proposition 1, there is a single function H+ such that a bag separating function is given by:

Hence, it follows that the function G0 (B) = 2⇡ R h+ d P(B) - 1 also separates bags.

Now, given that G0 (B) is a linear rescaling of the function R h+ d P(B), where h+ is a continuous function, it can be approximated by an element of the RKHS of the mean embedding kernel. This fact follows from the results of [Muandet et al., 2012] as shown in Equation 1.

The results above show that the mean embedding and MMD kernels can learn MI and GMI concepts. Note that these results do not require prior knowledge of the ⇡ parameters, only that they exist. These results assume that the entire bag distribution Bi is known during training. In practice, only samples of instances are observed for each bag. However, since empirical estimates of mean embeddings converge quickly to the underlying embeddings as the sample size within each bag increases [Sriperumbudur et al., 2010], we argue (and empirically show) that these approaches will also work well in practice.

1 A topological space is normal if for any disjoint closed sets A and B in the space, there are disjoint open sets U and V containing A and B, respectively [Folland, 1999].

3.2 Relationship of PriorWork to the MMD

In prior work, some other bag-level kernels have been defined for solving GMI classification problems. In this section, we discuss these approaches and their relationship to the mean embedding and MMD kernels. In particular we show that these approaches are either special cases, or approximations of the MMD, or learn hypotheses that are a proper subset of those representable by the MMD. Thus, although these approaches were placed in two distinct categories by prior work [Amores, 2013b], we argue that they can be unified under our proposed generative model.

Box-Counting Kernel. The box-counting kernel is motivated by the assumption that "attractive" and "repulsive" types of points as described in Definition 1 are contained within axis-parallel boxes in the feature space [Tao et al., 2004; 2008]. This is a stronger assumption than is made in Proposition 1, which allows these sets of types to be arbitrary closed sets. Hence, the hypothesis space of the MMD kernel subsumes that of the box-counting kernel. The box-counting kernel constructs a Boolean feature corresponding to every axis-parallel box in a discretized version of the feature space. A feature has value 1 if the corresponding box contains a point in the bag and value 0 otherwise.

Because it is intractable to explicitly enumerate all such features, Tao et al. [2004] use a "box-counting" kernel by observing that the inner product between two Boolean feature vectors above will be equal to the number of boxes that contain points from both corresponding bags. However, the box-counting problem is #P-complete, so an approximation is used to make even the kernel computation tractable [Tao et al., 2004]. The approximation scheme finds a value within a factor of ✏ of the true count with probability 1 - δ, in poly(mu↪ k↪ 1✏ ↪ 1δ ) time, where m is the bag size and k is the dimensionality of the input feature space. In contrast to this, the MMD kernel can be efficiently computed exactly.

YARDS. Another set of approaches for both MI and GMI learning construct a feature vector representation for each bag. The "yet another radial distance-based similarity measure" (YARDS) approach constructs a representation for bags as follows: First, each instance in a dataset is represented using a feature vector of length ♣X♣, where X is the set of all instances in the dataset, with each feature an RBF kernel between that instance and one of the xi 2 X. This mapping, x 7! ⇥k(x↪ x1)↪ ▷ ▷ ▷ ↪ k(x↪ x♣X♣)⇤, where k is the RBF kernel, is called the empirical kernel map [Sch¨olkopf and Smola, 2002], which we denote b φ(x). YARDS then proceeds to represent each bag as the average of these empirical kernel mappings, as in bb θ(Bi) = 1 ♣Bi♣ Pxi2Bi b φ(xi). We call this the doubly empirical mean embedding, since it is empirical in terms of both the kernel feature map as well as the estimate of the underlying mean embedding. This embedding is equivalent to the implicit kernel feature map with the empirical mean embedding up to a linear rescaling of the features [Sch¨olkopf and Smola, 2002]. Finally, YARDS uses another RBF kernel to embed bb θ into a feature space, making it a doubly empirical version of the MMD kernel. Thus, when YARDS is used with a standard SVM and an RBF kernel, it can learn the same concepts as the MMD kernel. However, some practical differences between these approaches are observed in the experiments, likely due to feature rescaling.

NSK. The normalized set kernel (NSK) is an early kernel method proposed for the standard MI setting [G¨artner et al., 2002]. In its most basic form, the set kernel between two bags is formed by a sum of pairwise instance kernel values between all pairs of instances across the two bags. Early work showed empirically that the kernel performs better when it is normalized, for example, by dividing by the bag sizes. In fact, the NSK with "averaging normalization" is equivalent to the empirical mean embedding kernel [Smola et al., 2007]; that is, kNSK(X↪X0 ) = 1 ♣X♣♣X0 ♣ Px2X Px02X0 k(x↪ x0 ) = hb θ(X)↪ b θ(X0 )i. The NSK is complete for standard MI classification, meaning that when the RKHS of k contains a function that separates instances of different classes, the RKHS of a corresponding kNSK contains a function that separates bags of different classes [G¨artner et al., 2002; Doran and Ray, 2013]. Proposition 1 shows this also holds for the standard MI setting within GMI-GEN.

mi-Graph. The MI-Graph and mi-Graph [Zhou et al., 2009] approaches first construct graphs for each bag by connecting two instances in a bag with an edge if they are within a distance of ⌧ of each other. The parameter ⌧ is chosen heuristically as the average distance between instances in a bag. The corresponding edge is weighted with a normalized reciprocal of the distance between the instances.

Like the NSK, the MI-Graph kernel is a sum of pairwise kernel values between instances and edges across two bags and their corresponding graphs based on an instance kernel and a kernel defined on edges. However, since the number of edges in a bag graph grows roughly as the square of the bag size, computing all pairwise edge kernel values is quartic in terms of the bag size. The mi-Graph kernel is a computationally more efficient version of MI-Graph that is equivalent to a weighted version of the mean embedding kernel. Under the view of bags as distributions, mi-Graph can be viewed as performing the mean embedding on a biased sample, or a sample drawn from a modified version of the bag's distribution.

EMD. The earth-mover's distance (EMD), also known as the Wasserstein metric, is a popular distance metric commonly used within the CBIR domain [Rubner et al., 2000]. The EMD is a proper distance metric between distributions, and its name comes from an intuitive description of how it operates. If one views one distribution as a pile of dirt, and the other distribution as a hole in the ground, then the EMD is a measure of the minimum amount of work, in terms of mass of dirt times Euclidean distance across the ground traveled, that it takes to fill the hole with the pile. The EMD kernel is formally defined via kEMD(Bi↪Bj) = e-γ EMD(Bi↪Bj) , which is similar to that of the MMD kernel. We hypothesize that because the EMD produces a similar representation of bag distributions to that of the MMD kernel, it can achieve similar performance on MI and GMI tasks.

4 Empirical Evaluation

In this section, we evaluate our hypothesis that the universal MMD kernel can efficiently learn accurate GMI concepts. We evaluate this hypothesis by comparing the MMD kernel to several baselines, described below.

4.1 Methodology

To evaluate our hypothesis, we use 52 existing datasets from 3D-QSAR [Dietterich et al., 1997], CBIR [Andrews et al., 2003; Maron and Ratan, 1998; Rahmani et al., 2005], text categorization [Andrews et al., 2003; Settles et al., 2008], audio classification [Briggs et al., 2012], and TRX protein sequence classification [Wang et al., 2004]. Of these, only the TRX dataset is known to require a GMI concept; thus, we augment our results with 20 semi-synthetic GMI datasets derived from the multi-label natural scenes datasets [Zhou and Zhang, 2006]. For each of the 5 instance types the bags in these datasets can contain (desert, mountains, sea, sunset, or trees), we form 20 datasets in which one of these is the attractive class and another is the repulsive class (e.g., images of mountains with no trees). Some of these datasets should be more difficult for standard MI methods; however, we cannot verify that all of them are strictly GMI without instance labels. We use 10-fold stratified cross-validation to evaluate algorithm performance in terms of accuracy, with 5-fold inner cross-validation and random parameter search [Bergstra and Bengio, 2012] used to select parameters. Details of the parameter ranges used for each kernel, full numerical tables of results, and additional figures are available in supplementary material online 2 .

We use the method described by [Demˇsar, 2006] to statistically compare the kernel approaches. We use the Friedman test to reject the null hypothesis that the algorithms perform equally at an ↵ = 0▷001 significance level, and an ↵ = 0▷05 significance level for the Nemenyi test and resulting critical difference diagram shown in Figure 2.

4.2 Results: Accuracy

The results in Figure 2 are generally consistent with the theoretical discussion presented above. The NSK and mi-Graph approaches produce very similar representations of the data, and also perform very similarly with no significant difference across datasets. The MMD kernel outperforms YARDS, which offers only an approximation of the same representation. Although the MMD kernel offers greater representational power than the NSK, the performance of these approaches is statistically equivalent across the MI and GMI datasets. On the other hand, restricting the analysis to the semi-synthetic GMI datasets, using the Wilcoxon signed-rank test to perform a pairwise comparison, the MMD does significantly outperform the NSK as expected. Interestingly, the mi-Graph O (m2 )

2 http://engr.case.edu/ray soumya/

Table 1: Complexity of computing bag-level kernel entries, where m denotes bag size, ♣X♣ is the number of instances in the dataset, ✏ is an approximation factor for the box-counting kernel, and 1 - δ is the probability of ✏-approximation.

O (m2 )

box-counting kernel, designed for the GMI setting, is typically outperformed by other kernels, even on GMI problems.

One somewhat surprising result is that the EMD kernel is slightly better than the MMD kernel, though not significantly so. We conjecture that the explanation for this result is that both the MMD and EMD kernels are actually members of the same family of distribution-distance kernels. Given any distance metric d, a kernel can be constructed using the generalized RBF kernel kd(xi↪ xj) = e-γd(xi↪xj)p [Sch¨olkopf and Smola, 2002]. Both the MMD and EMD kernels are of this generalized form based on distance metrics defined on the space of distributions (or samples from distributions). In fact, both distance metrics induce the same weak topology on the space of distributions over instances, P(X), when the instance space is separable [Sriperumbudur et al., 2010]. As discussed above, the MMD kernel is universal in its ability to represent continuous functions over distributions. Although it intuitively seems that the EMD kernel should have similar representational abilities, it is still an open question whether the EMD kernel is similarly universal over the space of distributions. However, given the empirical performance of the EMD kernel, we conjecture that this kernel is at least proficient at representing GMI concepts.

4.3 Results: Efficiency

Within the set of bag kernel classifiers, each approach requires differing amounts of time to construct the kernel matrix and train a classifier. The trade-off between training time and accuracy can be informative for selecting a bag kernel to apply in practice. Table 1 shows the time complexity of each algorithm. While the EMD occasionally outperforms the MMD in terms of accuracy, it is computationally more intensive. In practice, the NSK is the fastest algorithm given our implementations. The NSK, MMD, and EMD kernels lie on the Pareto frontier of algorithms ranked by both accuracy and running time (see supplementary materials).

5 Conclusion

In this paper, we have analyzed the GMI and MI settings in a model where bags are distributions over instances. Our theoretical results show that a class of distribution-based kernels are sufficient to represent GMI concepts. Furthermore, we show that many other existing approaches can be viewed as approximations or special cases of this approach. Finally, our empirical results indicate that the most accurate and efficient approaches are either distribution-distance or distributionembedding kernels. Accordingly, we recommend the use of these distribution-based kernels for a wide variety of MI and GMI problem domains in practice.

Acknowledgements

G. Doran was supported by GAANN grant P200A090265 from the US Department of Education and NSF grant CNS1035602. S. Ray was partially supported by CWRU award OSA110264. This work made use of the High Performance Computing Resource in the Core Facility for Advanced Research Computing at Case Western Reserve University.