A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> There are many learning problems for which the examples given by the teacher are ambiguously labeled. In this thesis, we will examine one framework of learning from ambiguous examples known as Multiple-Instance learning. Each example is a bag, consisting of any number of instances. A bag is labeled negative if all instances in it are negative. A bag is labeled positive if at least one instance in it is positive. Because the instances themselves are not labeled, each positive bag is an ambiguous example. We would like to learn a concept which will correctly classify unseen bags. ::: We have developed a measure called Diverse Density and algorithms for learning from multiple-instance examples. We have applied these techniques to problems in drug design, stock prediction, and image database retrieval. These serve as examples of how to translate the ambiguity in the application domain into bags, as well as successful examples of applying Diverse Density techniques. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) <s> BIB001 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> The multiple-instance learning model has received much attention recently with a primary application area being that of drug activity prediction. Most prior work on multiple-instance learning has been for concept learning, yet for drug activity prediction, the label is a real-valued affinity measurement giving the binding strength. We present extensions of k-nearest neighbors (k-NN), Citation-kNN, and the diverse density algorithm for the real-valued setting and study their performance on Boolean and real-valued data. We also provide a method for generating chemically realistic artificial data. <s> BIB002 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Following the success of inductive logic programming on structurally complex but small problems, recently there has been strong interest in relational methods that scale to real-world databases. Propositionalization has already been shown to be a particularly promising approach for robustly and effectively handling larger relational data sets. However, the number of propositional features generated here tends to quickly increase, e.g. with the number of relations, with negative effects especially for the efficiency of learning. In this paper, we show that feature selection techniques can significantly increase the efficiency of transformation-based learning without sacrificing accuracy. <s> BIB003 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Learning from structured data is becoming increasingly important. However, most prior work on kernel methods has focused on learning from attribute-value data. Only recently, research started investigating kernels for structured data. This paper considers kernels for multi-instance problems a class of concepts on individuals represented by sets. The main result of this paper is a kernel on multi-instance data that can be shown to separate positive and negative sets under natural assumptions. This kernel compares favorably with state of the art multi-instance learning algorithms in an empirical study. Finally, we give some concluding remarks and propose future work that might further improve the results. <s> BIB004 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> We describe a generalisation of the multiple-instance learning model in which a bag's label is not based on a single instance's proximity to a single target point. Rather, a bag is positive if and only if it contains a collection of instances, each near one of a set of target points. We then adapt a learning-theoretic algorithm for learning in this model and present empirical results on data from robot vision, content-based image retrieval, and protein sequence identification. <s> BIB005 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Multi-instance learning is commonly tackled using special-purpose algorithms. Development of these algorithms has started because early experiments with standard propositional learners have failed to produce satisfactory results on multi-instance data—more specifically, the Musk data. In this paper we present evidence that this is not necessarily the case. We introduce a simple wrapper for applying standard propositional learners to multi-instance problems and present empirical results for the Musk data that are competitive with genuine multi-instance algorithms. The key features of our new wrapper technique are: (1) it discards the standard multi-instance assumption that there is some inherent difference between positive and negative bags, and (2) it introduces weights to treat instances from different bags differently. We show that these two modifications are essential for producing good results on the Musk benchmark <s> BIB006 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Multiple instance (MI) learning is a relatively new topic in machine learning. It is concerned with supervised learning but differs from normal supervised learning in two points: (1) it has multiple instances in an example (and there is only one instance in an example in standard supervised learning), and (2) only one class label is observable for all the instances in an example (whereas each instance has its own class label in normal supervised learning). In MI learning there is a common assumption regarding the relationship between the class label of an example and the “unobservable” class labels of the instances inside it. This assumption, which is called the “MI assumption” in this thesis, states that “An example is positive if at least one of its instances is positive and negative otherwise”. In this thesis, we first categorize current MI methods into a new framework. According to our analysis, there are two main categories of MI methods, instancebased and metadata-based approaches. Then we propose a new assumption for MI learning, called the “collective assumption”. Although this assumption has been used in some previous MI methods, it has never been explicitly stated,1 and this is the first time that it is formally specified. Using this new assumption we develop new algorithms — more specifically two instance-based and one metadata-based methods. All of these methods build probabilistic models and thus implement statistical learning algorithms. The exact generative models underlying these methods are explicitly stated and illustrated so that one may clearly understand the situations 1As a matter of fact, for some of these methods, it is actually claimed that they use the standard MI assumption stated above. <s> BIB007 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> In our prior work, we introduced a generalization of the multiple-instance learning (MIL) model in which a bag’s label is not based on a single instance’s proximity to a single target point. Rather, a bag is positive if and only if it contains a collection of instances, each near one of a set of target points. This generalized model is much more expressive than the conventional multipleinstance model, and our first algorithm in this model had significantly lower generalization error on several applications when compared to algorithms in the conventional MIL model. However, our learning algorithm for this model required significant time and memory to run. Here we present and empirically evaluate a new algorithm, testing it on data from drug discovery and content-based image retrieval. Our experimental results show that it has the same generalization ability as our previous algorithm, but requires much less computation time and memory. <s> BIB008 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> The multiple-instance learning (MIL) model has been very successful in application areas such as drug discovery and content-based image-retrieval. Recently, a generalization of this model and an algorithm for this generalization were introduced, showing significant advantages over the conventional MIL model in certain application areas. Unfortunately, this algorithm is inherently inefficient, preventing scaling to high dimensions. We reformulate this algorithm using a kernel for a support vector machine, reducing its time complexity from exponential to polynomial. Computing the kernel is equivalent to counting the number of axis-parallel boxes in a discrete, bounded space that contain at least one point from each of two multisets P and Q. We show that this problem is #P-complete, but then give a fully polynomial randomized approximation scheme (FPRAS) for it. Finally, we empirically evaluate our kernel. <s> BIB009 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Designing computer programs to automatically categorize images using low-level features is a challenging research topic in computer vision. In this paper, we present a new learning technique, which extends Multiple-Instance Learning (MIL), and its application to the problem of region-based image categorization. Images are viewed as bags, each of which contains a number of instances corresponding to regions obtained from image segmentation. The standard MIL problem assumes that a bag is labeled positive if at least one of its instances is positive; otherwise, the bag is negative. In the proposed MIL framework, DD-SVM, a bag label is determined by some number of instances satisfying various properties. DD-SVM first learns a collection of instance prototypes according to a Diverse Density (DD) function. Each instance prototype represents a class of instances that is more likely to appear in bags with the specific label than in the other bags. A nonlinear mapping is then defined using the instance prototypes and maps every bag to a point in a new feature space, named the bag feature space. Finally, standard support vector machines are trained in the bag feature space. We provide experimental results on an image categorization problem and a drug activity prediction problem. <s> BIB010 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> In this paper we upgrade linear logistic regression and boosting to multi-instance data, where each example consists of a labeled bag of instances. This is done by connecting predictions for individual instances to a bag-level probability estimate by simple averaging and maximizing the likelihood at the bag level—in other words, by assuming that all instances contribute equally and independently to a bag’s label. We present empirical results for artificial data generated according to the underlying generative model that we assume, and also show that the two algorithms produce competitive results on the Musk benchmark datasets. <s> BIB011 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> In multi-instance learning, the training set is composed of labeled bags each consists of many unlabeled instances, that is, an object is represented by a set of feature vectors instead of only one feature vector. Most current multi-instance learning algorithms work through adapting single-instance learning algorithms to the multi-instance representation, while this paper proposes a new solution which goes at an opposite way, that is, adapting the multi-instance representation to single-instance learning algorithms. In detail, the instances of all the bags are collected together and clustered into d groups first. Each bag is then re-represented by d binary features, where the value of the ith feature is set to one if the concerned bag has instances falling into the ith group and zero otherwise. Thus, each bag is represented by one feature vector so that single-instance classifiers can be used to distinguish different classes of bags. Through repeating the above process with different values of d, many classifiers can be generated and then they can be combined into an ensemble for prediction. Experiments show that the proposed method works well on standard as well as generalized multi-instance problems. <s> BIB012 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Multiple-instance problems arise from the situations where training class labels are attached to sets of samples (named bags), instead of individual samples within each bag (called instances). Most previous multiple-instance learning (MIL) algorithms are developed based on the assumption that a bag is positive if and only if at least one of its instances is positive. Although the assumption works well in a drug activity prediction problem, it is rather restrictive for other applications, especially those in the computer vision area. We propose a learning method, MILES (multiple-instance learning via embedded instance selection), which converts the multiple-instance learning problem to a standard supervised learning problem that does not impose the assumption relating instance labels to bag labels. MILES maps each bag into a feature space defined by the instances in the training bags via an instance similarity measure. This feature mapping often provides a large number of redundant or irrelevant features. Hence, 1-norm SVM is applied to select important features as well as construct classifiers simultaneously. We have performed extensive experiments. In comparison with other methods, MILES demonstrates competitive classification accuracy, high computation efficiency, and robustness to labeling uncertainty <s> BIB013 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> This paper focuses on kernel methods for multi-instance learning. Existing methods require the prediction of the bag to be identical to the maximum of those of its individual instances. However, this is too restrictive as only the sign is important in classification. In this paper, we provide a more complete regularization framework for MI learning by allowing the use of different loss functions between the outputs of a bag and its associated instances. This is especially important as we generalize this for multi-instance regression. Moreover, both bag and instance information can now be directly used in the optimization. Instead of using heuristics to solve the resultant non-linear optimization problem, we use the constrained concave-convex procedure which has well-studied convergence properties. Experiments on both classification and regression data sets show that the proposed method leads to improved performance. <s> BIB014 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Multi-instance (MI) learning is a variant of supervised machine learning, where each learning example contains a bag of instances instead of just a single feature vector. MI learning has applications in areas such as drug activity prediction, fruit disease management and image classification. This thesis investigates the case where each instance has a weight value determining the level of influence that it has on its bag’s class label. This is a more general assumption than most existing approaches use, and thus is more widely applicable. The challenge is to accurately estimate these weights in order to make predictions at the bag level. An existing approach known as MILES is retroactively identified as an algorithm that uses instance weights for MI learning, and is evaluated using a variety of base learners on benchmark problems. New algorithms for learning instance weights for MI learning are also proposed and rigorously evaluated on both artificial and realworld datasets. The new algorithms are shown to achieve better root mean squared error rates than existing approaches on artificial data generated according to the algorithms’ underlying assumptions. Experimental results also demonstrate that the new algorithms are competitive with existing approaches on real-world problems. <s> BIB015 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> We propose a new generalized multiple-instance learning (MIL) algorithm, MICCLLR (multiple-instance class conditional likelihood ratio), that converts the MI data into a single meta-instance data allowing any propositional classifier to be applied. Experimental results on a wide range of MI data sets show that MICCLLR is competitive with some of the best performing MIL algorithms reported in literature. <s> BIB016 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Refining agents comprising intimate mixtures of finely-divided sulfates and reducing agents are added to vitrifiable charges of glassmaking raw materials prior to melting the raw materials so that, when the charge is melted, the refining agent will evolve bubbles of sulfur dioxide gas which will remove smaller bubbles of other gases from the molten glass as these bubbles rise to the surface of the molten glass. The metal sulfates and reducing agents (preferably carbon) employed in the refining agent have a particle size of less than about 0.1 mm and are formed into homogeneous agglomerates having a size of about 1 to 5 mm. The glassmaking raw materials are also finely-divided and may be used in this form or may be formed into agglomerates of about the same size as, or containing the agglomerated refining agent. The relative amounts of reducing agent to sulfur in the refining agent is such that at least one-fourth of the sulfate present will be reduced to the sulfide form, and the amount of refining agent employed is such that the amount of added sulfur expressed as SO3 is at least 0.05% by weight of the glass to be obtained. <s> BIB017 </s> A Review of Multi-Instance Learning Assumptions <s> Algorithms and Models <s> Previous studies on multi-instance learning typically treated instances in the bags as independently and identically distributed. The instances in a bag, however, are rarely independent in real tasks, and a better performance can be expected if the instances are treated in an non-i.i.d. way that exploits relations among instances. In this paper, we propose two simple yet effective methods. In the first method, we explicitly map every bag to an undirected graph and design a graph kernel for distinguishing the positive and negative bags. In the second method, we implicitly construct graphs by deriving affinity matrices and propose an efficient graph kernel considering the clique information. The effectiveness of the proposed methods are validated by experiments. <s> BIB018
The Two-Level Classification (TLC) algorithm is designed to learn the type of MI concepts that are described in Weidmann's concept hierarchy, where it is assumed that bag-level class labels are determined by the counts of each instance-level concept in a bag. TLC learns in a two-step process. The first step learns instance-level concepts using a decision tree. The tree is built on all of the instances in all of the bags in the training data, with class labels of the instances set to the labels of the parent bags. Each node in the tree is considered to represent a candidate concept. Then each bag is converted into a single-instance representation, with an attribute for every node in the tree (i.e. each candidate concept), the value of which is set to the number of instances that reach that node in the decision tree. The second step learns bag-level concepts, based on the candidate instance-level concepts discovered in the first step. A single-instance learning algorithm is applied to the transformed data. The same mapping is performed at classification time, and the bag-level predictions are made by the single-instance learner. A further (optional) refinement to the algorithm is to use attribute selection to try to eliminate the attributes that do not contribute to the instance-level classification problem learned by the decision tree. The Constructive Clustering Ensemble (CCE) method BIB012 also uses a propositionalization method that may be appropriate for some Weidmann type concepts. The algorithm uses a clustering method to cluster the instances in the training bags into d clusters. Bags are mapped into a boolean feature space where each attribute corresponds to a cluster, and the value of an attribute is set to 1 if and only if that bag has an instance in that cluster. A single-instance model is built on the resulting dataset. The algorithm is repeated for multiple values of d, and classification predictions are made via a majority vote of the resulting ensemble of single-instance classifiers. Given that the feature space constructed by CCE represents the presence or absence of instances with certain properties, it appears that this algorithm may be best suited for learning presence-based MI concepts. However, the algorithm could be easily extended to learn count-based concepts if the transformed feature space was modified to include the number of occurrences of the instance-level concepts, as in the earlier TLC algorithm. It should also be noted that BIB012 results indicate that the algorithm is less accurate when learning on presencebased MI data than TLC (with attribute selection enabled). BIB005 3 introduced a new MI assumption based on theoretical results from geometric pattern recognition. We will refer to this assumption as the GMIL assumption. In this model, there is a set of target points C = {c 1 , c 2 , . . . , c k }. A bag is positive if and only if it contains instances sufficiently close to at least r points, out of the k target points. The task of enumerating all axis-parallel boxes is exponential in the number of dimensions, which makes GMIL-1 very inefficient. GMIL-2 BIB008 ) is an attempt to improve the computational and memory efficiency of the algorithm. The algorithm is roughly the same as GMIL-1, but it selects groups of boxes in a different way. First, GMIL-2 reduces the number of instances to consider by selecting a subset of representative instances, Ψ. Then it constructs groups by considering the boxes represented by the bounding box of each possible subset of Ψ. A breadth-first search approach is used to attempt to efficiently find the sets of groups that are geometrically valid, i.e. all instances within the bounding box of the group are contained within the group. Although GMIL-2 is far more efficient than GMIL-1, it still suffers from limited scalability BIB009 . In a further attempt to improve the algorithm's computational complexity, BIB009 presented a kernel-based reformulation of the GMIL learning problem. The kernel, k ∧ , allows a support vector machine to be applied directly to the problem. As the computation of k ∧ belongs to the complexity class #P-complete and thus suffers from severe scalability issues that quickly make the problem intractable as the problem size increases, the authors presented a fully-polynomial randomized approximation scheme (FRAPS) for it. Tao et al. proposed an extended version of the k ∧ kernel, called k min , which allows a support vector machine to solve the MI learning problem under the Count-Based GMIL Assumption. Unlike the k ∧ kernel, the feature space associated with the k min kernel includes information related to the number of instances within the box that describes the concept concerned. Multiple-Instance Learning via Embedded Instance Selection (MILES) BIB013 embeds bags into a single-instance feature space based on similarity scores obtained from Equation 2, and applies the 1-norm support vector machine algorithm to the transformed dataset. MILES uses the instances in the training bags as candidates for target points. A feature-space mapping is defined, where each attribute represents the closeness of an instance to a candidate target point (i.e. training instance). Each training bag is mapped into this space (with class labels appended), and a single-instance base learner is built on the transformed dataset. At testing time, bags are similarly mapped into the instance-based feature space, and classification predictions are made by the single-instance base learner. The diverse density support vector machine (DD-SVM) algorithm BIB010 ) is a predecessor to MILES that is conceptually very similar to the later method. Chen et al.'s (2006) experimental results show that MILES is much more efficient than DD-SVM in terms of computational complexity, while maintaining similar or better classification accuracy and increased robustness to label noise, hence we do not discuss DD-SVM in detail here. The BARTMIP algorithm performs an initial bag-level clustering step on the training bags using the k-medoids algorithm adapted to MI learning by using a Hausdorff distance variant for its distance function. As well as grouping the bags into k clusters, the clustering algorithm also outputs the medoid 4 of each cluster. The training bags are then mapped to a k-dimensional single-instance feature space, where the ith attribute corresponds to the distance of the bag to the ith medoid, under the same baglevel distance measure that was used in the clustering step. The class labels of the original bags are appended to the transformed instances, and a single-instance base learner is applied to the resulting feature space. At classification time, the mapping is performed to the test bags and predictions are made by the single-instance base learner. Note that this method is identical to MILES, except for the different feature-space transformation used. Xu (2003) developed statistical algorithms for learning this kind of probabilistic concept, the most notable of which are versions of logistic regression and boosting, upgraded to solve MI learning problems under the collective MI assumption (see also BIB011 ). BIB006 also investigated a simple heuristic algorithm called MIWrapper for applying single-instance learners under the collective assumption. The first step of the MIWrapper algorithm is to collect all of the instances from all of the bags, and label each of them with the label of the bag that they came from. This effectively creates a propositional (i.e. single-instance) dataset. The algorithm then weights all of the instances so that each bag has equal total weight. A single-instance learner is applied to this propositional dataset. At classification time, the singleinstance learner predicts class probabilities for all of the instances in the bag for which the classification is to be predicted. The output is merely the average (arithmetic or geometric) of the predicted instance-level class probabilities. Using the arithmetic mean at prediction time, the method applies the "sample" version of the collective assumption formula when making predictions. Implementing the weighted collective assumption requires a method for learning instance weights. BIB015 investigated an Iterative Framework for Learning Instance Weights (IFLIW), a heuristic algorithm for learning weighted collective assumption concepts. The algorithm is an extension of the MIWrapper approach from Section 3.7.1. IFLIW uses MIWrapper to learn the class probability function pr(c|x) via the simple propositionalization method described in Section 3.7.1 and a single-instance base learner. The challenge, however, is to estimate the weight function. An iterative method is applied, where instance weights of the training data are updated according to an update function, and the MIWrapper model is rebuilt using the new weights. The update function that is used is: x.weight = x.weight × exp(inf ogain(pr(c|x), pr(c))) , where x.weight is the weight of instance x, inf ogain is the information gain of pr(c|x), the class probability distribution for the instance x predicted by the single-instance base classifier, relative to pr(c), the prior class probabilities computed from the class frequencies in the training data. The iteration continues until a stopping criterion is met. The weight function is then estimated using a regression model built on the training instance weights. It is also possible to learn a model based on the weighted linear threshold assumption. The MILES method from Section 3.4 can be modified so that it learns weighted linear threshold concepts when a linear classifier is used as the base learner BIB015 . This is achieved by using an alternative similarity measure between a bag and a target point. Recall that the similarity measure s(x, B) used in MILES (Equation 2) includes a max operator, which effectively selects only the closest instance in the bag B when determining the similarity value. This is based on Maron's (1998) most likely cause estimator from the diverse density framework. The models learnt by MILES (with a linear classifier as the base learner) can be understood as being similar to weighted linear threshold concepts, except that the use of the max operator in the similarity measure means that instance weights are bag-dependent, as only the closest instance in the bag to each target point contributes to the bag-level classification. By simply replacing the max operator with a sum operator, the bag-dependence is removed, resulting in a true weight function over instance space. The resulting similarity measure, called Yet Another Radial Distance-based Similarity measure (YARDS) BIB015 , is defined as follows: 18 j. foulds and e. frank Hence, by replacing the similarity measure s(x, B) in the MILES algorithm with the YARDS similarity measure s y (x, B), MILES can be adapted to learn weighted linear threshold concepts. The YARDS method can represent weighted linear threshold concepts where the weight function is the sum of a set of Gaussian-like influence functions, and makes the further assumption that the peak (or trough) of each of the Gaussian-like functions is at the location of an instance from one of the training bags. The MILES, YARDS, BARTMIP, TLC and CCE algorithms discussed above all use featurespace transformations, where bags are mapped to single-instance feature vectors, and singleinstance algorithms are applied to the resulting datasets. These methods can therefore be viewed as metadata approaches. However, the feature spaces used by these methods are intended to represent more sophisticated MI concepts, and are perhaps better understood with respect to the underlying MI assumptions that the feature-space transformations are designed to encode. In contrast, we will now describe a method that uses simple summary statistics as metadata. Using this approach, multi-instance learning problems are converted into single-instance problems by replacing each bag with a feature vector consisting of summary statistics derived from the instances in that bag. This method originates from a similar approach to propositionalization for relational data known as RELAGGS BIB003 ). We will follow  , and refer to the approach based on summary statistics as Simple MI. Dong described three versions of Simple MI, each of which differs only in the type of summary statistics used for the single-instance feature space. The first two methods merely average the values of the instances in a bag for each dimension, using either the arithmetic or the geometric mean. Formally, the two methods can be defined as follows: if b is a bag with instances from feature space χ = (x 1 , x 2 , . . . , x n ), then b is mapped to (x 1 ,x 2 , . . . ,x n ), wherex is the arithmetic (or geometric) mean of the instances in the bag. The third option is called the "minimax" method. Here, the minimum and maximum values of each variable are recorded for each bag. This method is equivalent to Gärtner et al.'s (2002) minimax kernel, used as a kernel in a standard support vector machine algorithm. Using the same notation as before, each bag b is mapped to (min x 1 , min x 2 , . . . , min x n , max x 1 , max x 2 , . . . , max x n ). The new feature space contains 2n dimensions. The main advantage of Simple MI is that it is extremely fast. The computation of the featurespace transformation is trivial, and the single-instance base learner only has to learn from as many instances as there are bags in the training set, regardless of how many instances are contained inside the bags. Of course, this simple model is not able to represent some types of problems. However, Dong found that Simple MI (with appropriate base learners) performs surprisingly well on many datasets, even outperforming all of the special-purpose MI algorithms that were investigated in some cases. A more sophisticated metadata approach is used by the MICCLLR algorithm BIB016 , which performs propositionalization by replacing each bag by a feature vector containing statistics computed based on the class conditional log-likelihood ratios of the attribute values of the instances in the bags. These statistics are computed using the relative frequencies of attribute values and class labels in a flattened version of the MI dataset (using the same method as in the MIWrapper algorithm from Section 3.7), under the assumption that attribute values are conditionally independent given the class value. As the authors note, Gärtner et al.'s kernel (or equivalently, the minimax Simple MI method) may not be able to represent binary data well, unlike MICCLLR; however the former method does not rely upon the conditional independence assumptions used by the latter. MI learning algorithms can also be said to rely on a metadata assumption if they are equivalent to a metadata approach for some feature space transformation, even when the algorithm does not explicitly perform the transformation. Learning algorithms of this type include the Relic multi-instance decision tree learner  and Gärtner et al.'s (2002) K M I multi-instance kernel method. Relic is an information gain-based decision tree learner that has been upgraded to handle MI data by defining a test-selection criterion for MI bags. Although Relic does actually not perform propositionalization, BIB007 showed how, in the case of data with numeric attributes, Relic is equivalent to the minimax version of Simple MI with a decision tree base learner, and hence effectively relies upon the same MI assumption. BIB004 presented multi-instance kernels that can be used to apply a standard SVM algorithm directly to multi-instance data. As well as the aforementioned minimax kernel, they also proposed the MI kernel K M I , a variant of the set kernel  . The kernel is defined as where k p I is an arbitrary instance-level SVM kernel k I , raised to the pth power. As products of kernels are kernels, k p I is also a kernel. Gärtner et al. showed that for a sufficiently large p, any standard MI concept is separable (and thus representable by an SVM using that kernel) assuming that the underlying instance-level concept is separable. It follows from this result that MI concepts that respect the standard MI assumption (with separable instance-level concepts) can be learnt by this method. However, this method does not actually make any use of the standard MI assumption, and can in fact be shown to use a metadata assumption. Using the fact that the dot product is distributive over scalar multiplication, it is not hard to show that K M I can be rewritten as where φ I (x) is the feature space transformation implicit in the kernel k p I . Thus, an SVM using the K M I kernel is equivalent to propositionalizing via mapping each bag X to x∈X φ I (X), and applying a standard SVM using a linear kernel to the resulting dataset. Later, BIB014 proposed a regularization framework for MI learning via SVMs using a loss function that encodes a trade-off between Gärtner et al.'s K M I model and an SVM algorithm based on the standard MI assumption that is due to  . The tradeoff is accomplished via a weight parameter λ in the loss function. The implicit assumption of this method is that bag-level class labels are determined by some combination of the K M I metadata assumption and the standard MI assumption. 3.10 The MIGraph Assumption BIB018 proposed algorithms that depend upon the assumption that the spatial relationships between instances in bags are important contributors to bag labels. Consider the 20 j. foulds and e. frank -graph of a bag, which has nodes for each instance, and edges exist between nodes if and only if the distance between their associated instances (under some metric) is less than a fixed threshold . The edges are weighted according to the affinity of the two nodes -Zhou et al. set the weights to be the normalized reciprocal of the (non-zero) distance between them. The assumption, which we will call the M Igraph assumption, is that bag labels are in some way determined by the properties of the -graph. The MIGraph and miGraph algorithms BIB018 apply support vector machines to multi-instance data by using graph kernels on the -graphs of the bags. Although any graph kernel could be used, Zhou et al. define two new kernels based on Gärtner et al.'s MI kernel. The MIGraph and miGraph methods differ only in the kernels used. MIGraph uses the kernel k G , defined as where E(I) is the edge set of bag I, and k node and k edge are positive semidefinite kernels defined on nodes and edges, respectively. Zhou et al. use the Gaussian RBF kernel for k node . For the k edge kernel, they define a kernel with the property that edges are similar if their ending nodes have similar degree, taking the edge weights into account. Note that the node portion of the kernel k G is the same as Gärtner et al.'s MI kernel. As the computational complexity of k G is dominated by the number of edges in X and Y if the graphs are not sparse, it can be computationally expensive to compute the kernel function. To counter this, Zhou et al. introduce the miGraph algorithm, where the k g kernel is used: where W Ii is the reciprocal of the number of instances from bag I in an -ball around instance i (including itself). In BIB018 , the W Ii s are computed using the Gaussian distance, consistently with the Gaussian RBF kernel used for k node . The authors describe k g as a soft version of a clique-based graph kernel; it behaves identically to a clique-based kernel when all instances are clustered into cliques. Wang and Zucker proposed two variants of the standard k-nearest neighbour algorithm. In these methods, neighbours are computed in the normal way via the (maximal or minimal) Hausdorff distance; the difference is in the method for selecting the label of an example given a set of neighbours. These methods were motivated by the authors' observation that predicting the majority class of the neighbours does not always give the optimal classification result. Their Bayesian-KNN algorithm uses a Bayesian method for predicting the most likely class given a set of neighbours, while the Citation-KNN algorithm is based on the notions of references and citers from the field of library and information science -when making a classification decision, not only are nearest neighbours (references) of an example considered, but also bags that consider the example to be a nearest neighbour (citers). The experimental results presented by Wang and Zucker indicate that these methods are very competitive with other algorithms on the musk benchmark datasets. However, a comparison with the standard k-NN majority voting method is not provided. It should also be noted that the Bayesian and Citation alternatives to majority voting are not at all dependent on the multiinstance nature of the data, and are hence equally applicable in a single-instance scenario. Finally, Wang and Zucker used parameter values selected on the test data when comparing their methods to other algorithms, so their comparative results may be optimistic.  Under Ray and Page's assumptions, an ideal MI regression model is a hyperplane Y = Xb such that where n is the number of bags, y i is the real-valued label of bag i, X ip is the primary instance of the ith bag, and L is a loss function. Ray and Page use L(y i , X ij , b) = (y i − X ij b) 2 , similarly to traditional multiple regression. However, the primary instances X ip are not known at training time, so Ray and Page propose that the "best fit" hyperplane be used instead: j. foulds and e. frank They state that the decision problem for the existence of such a hyperplane can be shown to be N P -complete via a reduction from the 3SAT problem. They therefore instead present an approximation algorithm. Their algorithm is an Expectation Maximization (EM) approach, which iteratively improves an initial guess at a hypothesis. In the expectation step, an instance is selected from each bag, namely the one that has the least L-error with respect to the current guess at the hypothesis hyperplane. In the maximization step, ordinary multiple regression is performed to find a hyperplane that best fits the selected instances. These steps are repeated until convergence. As Ray and Page observe, this algorithm can easily be modified to incorporate alternative L-error functions and alternative (possibly non-linear) hypotheses. The algorithm is however dependent upon the standard MI regression assumption. BIB014 presented a support vector regression approach for MI regression under the standard MI regression assumption. To make computation feasible, their method relies on the simplifying assumption that the primary instance is the one with the highest output value according to the SVM. BIB002 adapted the diverse density algorithm (see Section 2.4) to MI regression data by using a real-valued version of BIB001 most likely cause model, and used a similar method to apply EM-DD (see also Section 2.4) to real-valued data. Here, the assumption is that the closest instance to a certain "target point" is responsible for a bag's label, which is compatible with the standard MI regression assumption. Bag labels are determined from the distance between the target point and the closest point in the bag by a Gaussian function with a peak at the target point. BIB017 proposed MI regression algorithms that are similar to the Simple MI and MIWrapper algorithms described in Sections 3.9 and 3.7, respectively. The GlobalPruning-MIR and BalancedPruning-MIR algorithms are expectation-maximization versions of an MIWrapperlike approach that discards those instances that are most likely to be noisy in each iteration. It should be noted that these methods are very similar to the IFLIW algorithm from Section 3.8.3, except that sampling is used instead of weighting in the former methods, in order to remove the effects of noisy or unimportant instances.