A Review of Multi-Instance Learning Assumptions <s> Introduction <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> Introduction <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> BIB002 </s> A Review of Multi-Instance Learning Assumptions <s> Introduction <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
Multi-instance (MI) learning BIB001 (also known as "multiple-instance learning") is a variant of inductive machine learning that has received a considerable amount of attention due to both its theoretical interest and its applicability to real-world problems such as drug activity prediction and image classification. MI learning, as it is commonly defined, belongs to the supervised learning paradigm, which aims to solve classification and regression problems by using algorithms to build models from data based on a set of labeled examples. The majority of the work in MI learning is concerned with binary classification problems, where each example has a classification label that assigns it into one of two categories -"positive" or "negative". The goal is to "learn" a model based on the training examples that is effective in predicting the classification labels of future examples. All training examples have been (often manually) assigned a class label, which is why the term supervised learning is used. Where MI learning differs from the traditional scenario is in the nature of the learning examples. In the traditional supervised learning scenario, each example is represented by a fixedlength vector of features. However, in MI learning each example is represented by a multiset (or bag, as computer scientists often call it) of feature vectors. In other words, each example contains one or more feature vectors. The feature vectors are referred to as instances. Classification labels 2 j. foulds and e. frank are only provided for entire bags, and the task is to learn a model that predicts the classification labels for unseen future bags 1 . In early MI research, a strong assumption was made regarding the relationship between instances inside the bags and the label of the bag. This assumption is generally referred to as the standard MI assumption. Under this assumption, each instance has a hidden class label which identifies it as either a positive or a negative instance, and a bag is considered to be positive if and only if it contains at least one positive instance. This is generally believed to be true for the musk drug activity prediction problem, where a molecule will have the desired drug effect if and only if one or more of its conformations binds to the target binding site BIB001 . However, in other problem domains this assumption may not apply, and different or more general assumptions may be needed. A significant amount of the more recent research in MI is concerned with cases where the standard view of MI learning is relaxed, and alternative assumptions are used instead. Unfortunately, it is often not clear what particular assumptions are used and how they relate to other assumptions from the literature. This is perhaps at least partially due to the fact that the use of the term "MI learning" has evolved from the original statement by BIB001 . Dietterich et al. included the standard MI assumption in their original definition of MI learning, but many authors now include alternative assumptions within the MI learning framework (see, for example, BIB002 , BIB003 and  ). To compound the issue, some authors use alternative MI assumptions without explicitly describing the assumptions used. In this paper we aim to shed some light on existing MI assumptions and relationships by reviewing the MI assumptions that can be found in the literature. This paper is not intended as a review of algorithms for MI learning that implement the standard MI assumption.