A Review of Multi-Instance Learning Assumptions <s> Motivations for Alternative MI Assumptions <s> The multiple instance problem arises in tasks where the training examples are ambiguous: a single example object may have many alternative feature vectors (instances) that describe it, and yet only one of those feature vectors may be responsible for the observed classification of the object. This paper describes and compares three kinds of algorithms that learn axis-parallel rectangles to solve the multiple instance problem. Algorithms that ignore the multiple instance problem perform very poorly. An algorithm that directly confronts the multiple instance problem (by attempting to identify which feature vectors are responsible for the observed classifications) performs best, giving 89% correct predictions on a musk odor prediction task. The paper also illustrates the use of artificial data to debug and compare these algorithms. <s> BIB001 </s> A Review of Multi-Instance Learning Assumptions <s> Motivations for Alternative MI Assumptions <s> Many object classes, including human faces, can be modeled as a set of characteristic parts arranged in a variable spatial configuration. We introduce a simplified model of a deformable object class and derive the optimal detector for this model. However, the optimal detector is not realizable except under special circumstances (independent part positions). A cousin of the optimal detector is developed which uses “soft” part detectors with a probabilistic description of the spatial arrangement of the parts. Spatial arrangements are modeled probabilistically using shape statistics to achieve invariance to translation, rotation, and scaling. Improved recognition performance over methods based on “hard” part detectors is demonstrated for the problem of face detection in cluttered scenes. <s> BIB002 </s> A Review of Multi-Instance Learning Assumptions <s> Motivations for Alternative MI Assumptions <s> As opposed to traditional supervised learning, multiple-instance learning concerns the problem of classifying a bag of instances, given bags that are labeled by a teacher as being overall positive or negative. Current research mainly concentrates on adapting traditional concept learning to solve this problem. In this paper we investigate the use of lazy learning and Hausdorff distance to approach the multiple-instance problem. We present two variants of the K-nearest neighbor algorithm, called Bayesian-KNN and Citation-KNN, solving the multiple-instance problem. Experiments on the Drug discovery benchmark data show that both algorithms are competitive with the best ones conceived in the concept learning framework. Further work includes exploring of a combination of lazy and eager multiple-instance problem classifiers. <s> BIB003 </s> A Review of Multi-Instance Learning Assumptions <s> Motivations for Alternative MI Assumptions <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> Motivations for Alternative MI Assumptions <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> Motivations for Alternative MI Assumptions <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> Motivations for Alternative MI Assumptions <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> BIB007 </s> A Review of Multi-Instance Learning Assumptions <s> Motivations for Alternative MI Assumptions <s> We empirically study the relationship between supervised and multiple instance (MI) learning. Algorithms to learn various concepts have been adapted to the MI representation. However, it is also known that concepts that are PAC-learnable with one-sided noise can be learned from MI data. A relevant question then is: how well do supervised learners do on MI data? We attempt to answer this question by looking at a cross section of MI data sets from various domains coupled with a number of learning algorithms including Diverse Density, Logistic Regression, nonlinear Support Vector Machines and FOIL. We consider a supervised and MI version of each learner. Several interesting conclusions emerge from our work: (1) no MI algorithm is superior across all tested domains, (2) some MI algorithms are consistently superior to their supervised counterparts, (3) using high false-positive costs can improve a supervised learner's performance in MI domains, and (4) in several domains, a supervised algorithm is superior to any MI algorithm we tested. <s> BIB008 </s> A Review of Multi-Instance Learning Assumptions <s> Motivations for Alternative MI Assumptions <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> BIB009 </s> A Review of Multi-Instance Learning Assumptions <s> Motivations for Alternative MI Assumptions <s> We propose a new multiple instance learning (MIL) algorithm to learn image categories. Unlike existing MIL algorithms, in which the individual instances in a bag are assumed to be independent with each other, we develop concurrent tensors to explicitly model the inter-dependency between the instances to better capture image's inherent semantics. Rank-1 tensor factorization is then applied to obtain the label of each instance. Furthermore, we formulate the classification problem in the reproducing kernel Hilbert space (RKHS) to extend instance label prediction to the whole feature space. Finally, a regularizer is introduced, which avoids overfitting and significantly improves learning machine's generalization capability, similar to that in SVMs. We report superior categorization performances compared with key existing approaches on both the COREL and the Caltech datasets. <s> BIB010
Although the standard MI assumption is widely believed to be appropriate for the musk drug activity prediction problem, the multi-instance representation can be applied to a number of other problem domains where the standard MI assumption may not be directly applicable. In these domains, algorithms that rely upon alternative MI assumptions may be more appropriate. A prominent example of this is the task of learning visual concepts from databases of labeled images. This learning problem arises in several computer vision tasks including object detection or recognition, image categorization and content-based image retrieval. Although standard supervised learning could be applied directly to learn from global features of images, the task of learning visual concepts lends itself well to an MI representation because the target concepts typically only occupy part of the space of an image. Therefore, it makes sense to split the image into smaller regions (segments) BIB002 . Based on this approach, an image can be represented as a bag of segments, which are represented by instances. Segments can simply be equal-sized blocks, or more sophisticated segmentation methods can be used. Each instance in a bag contains features extracted from the corresponding segment, such as colour, texture and shape information. Features describing relative relationships to adjacent segments can also be used  . Multiinstance learning has been frequently applied to visual concept learning tasks -see, for example,  ,  ,  , BIB007 , BIB009 and BIB010 . Methods using the standard MI assumption have been applied to visual concept learning tasks with some success. The standard assumption is a good heuristic for many such tasks, but not all visual concepts can be represented under that assumption. First, for the purposes of comparison let us briefly consider a task where the standard MI assumption may be applicable.  identified the task of identifying natural scenes of waterfalls as such a problem. Here, if image segments (instances) containing a waterfall can be identified, images containing that instance-level concept can be identified under the standard MI assumption: an image contains a waterfall if and only if it contains at least one waterfall segment. We will now describe a learning task where the standard MI assumption is not sufficient to represent the desired concept. Consider the task of categorizing images of natural scenes of beaches, oceans and deserts. Since the standard MI assumption requires a binary classification task, one would generally approach this by learning one-against-the-rest models for each class. However, there is no single item contained in a segment of a beach scene that defines it as belonging to the beach category, as opposed to the other two alternatives. Unlike the waterfall scenario, where the existence of at least one segment with a specific property is a necessary and sufficient condition for a positive class label, we cannot identify a part of a scene that directly corresponds to a beach or non-beach scenario. Thus the standard MI assumption cannot apply. We would still like to use the multi-instance representation in order to capture localized information from the image, but we need to assume a non-standard relationship between instances and baglevel class labels. Let us now consider a generalized MI model that would allow us to represent this type of concept. For the sake of simplicity, we can define ocean scenes as images with water instances (segments), and no sand instances, desert scenes as images with sand instances and no water instances, and beach scenes as images with both sand and water segments. Then the beach concept can be defined to be Such a concept can be represented under alternative MI assumptions such as presence-based MI and the GMIL assumption BIB005 (described in Sections 3.1.1 and 3.2, respectively). A similar scenario arises in text categorization, where the task is to assign semantic labels to text documents. A document can be represented as an MI bag: instances are obtained by splitting the document into smaller passages. Features such as word occurrence frequencies can be extracted from each passage to form instances. This MI approach to text categorization has been applied by  and BIB008 . Like visual concept learning, text categorization can potentially benefit from an MI representation because it allows localized information to be used. In both of these problem scenarios, the MI representation is used to describe an object by a set of parts, each of which is a feature vector (instance).  refer to this type of problem as a Multiple Part Problem (MPP). As they observe, although the multi-instance representation is useful for describing MPP learning examples, the standard MI assumption is not guaranteed to hold. Other problem domains where the relaxation of the standard MI assumption is appropriate include robot localization via landmark matching, activity prediction for drugs that bind at multiple sites simultaneously, and identifying thioredoxin-fold proteins. For a thorough account of these scenarios, the reader is referred to BIB005 . A further motivation for the investigation of MI approaches based on alternative assumptions is the empirical success that such methods have enjoyed on benchmark problems, including the musk datasets where the standard MI assumption was originally claimed to be necessary BIB001 . A number of authors have reported very competitive results on these datasets using methods that do not strictly respect the standard MI assumption (deliberately or otherwise), including BIB004 , BIB003 , BIB006 , BIB009 and  . As we have seen, different problem domains require different MI assumptions. Although the standard MI assumption is often an effective heuristic, the existence of a natural MI representation for learning examples in a given domain does not imply that this assumption will apply in that domain. Data mining practitioners need to take this into consideration, and select algorithms that are known to depend only on assumptions that are likely to be true for the problem at hand. We therefore consider the relaxed MI scenario to be worthy of continued research, with the caveat that authors make explicit their assumptions whenever the standard MI assumption is disregarded.