A Review of Multi-Instance Learning Assumptions <s> The DD-SVM / MILES Assumption <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> BIB001 </s> A Review of Multi-Instance Learning Assumptions <s> The DD-SVM / MILES Assumption <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> BIB002 </s> A Review of Multi-Instance Learning Assumptions <s> The DD-SVM / MILES Assumption <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> BIB003
The DD-SVM BIB002 algorithm and its successor MILES BIB003 also use a generalized MI assumption where bag-level class labels are determined based on the distance from each of a set of target points. Although the authors of DD-SVM and MILES note that their algorithms do not follow the standard MI assumption, they do not explicitly describe their new assumptions independently from the descriptions of the algorithms. This section attempts to isolate the common assumptions between these algorithms and thus describe the types of MI concepts that the algorithms attempt to learn. The DD-SVM / MILES assumption is related to BIB001 GMIL assumption, in that distance from a set of target points is used to determine bag labels. However, "distance" is defined differently, and the r-of-k threshold is not used. As in the GMIL assumption, the target points can be related to either positive or negative concepts. The DD-SVM and MILES methods each include a distance-related measure of similarity between a target point and a bag, and it is assumed that bag-level class labels are in some way determined by these similarity values. In DD-SVM, the similarity function is where B ij are the instances in the bag B i , x is a target point and w is a weight vector determining the importance of each feature. In MILES, a Gaussian function is used instead: where σ is a scaling factor, which is a parameter to the algorithm. The relationship between the "similarities" to target points and bag-level class labels is dependent on the single-instance base learner that is applied to the data after transformation based on the similarity scores. In the original statement of DD-SVM and MILES, a support vector machine is used. If a linear kernel is used for the SVM, class labels are determined by a weighted linear threshold defined on the similarity values, i.e. DD-SVM / MILES concepts are of the form where T is the set of target points, w k is the weight associated with target point k and b is a bias parameter. If a target point has a positive weight, it can be viewed as being positive -bags with points close to that target point are more likely to be positive; and similarly for negative target points, i.e. points with negative weight. However, alternative single-instance base learners are possible for both DD-SVM and MILES. If we view the algorithms as "wrapper" methods where arbitrary base learners are possible, the assumption is merely that bag-level labels can be determined in some way from the similarities to the set of target points.