A Review of Multi-Instance Learning Assumptions <s> The Standard MI Assumption <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> The Standard MI Assumption <s> Multiple-instance learning is a variation on supervised learning, where the task is to learn a concept given positive and negative bags of instances. Each bag may contain many instances, but a bag is labeled positive even if only one of the instances in it falls within the concept. A bag is labeled negative only if all the instances in it are negative. We describe a new general framework, called Diverse Density, for solving multiple-instance learning problems. We apply this framework to learn a simple description of a person from a series of images (bags) containing that person, to a stock selection problem, and to the drug activity prediction problem. <s> BIB002 </s> A Review of Multi-Instance Learning Assumptions <s> The Standard MI Assumption <s> In this paper we present a boosting approach to multiple instance learning. As weak hypotheses we use balls (with respect to various metrics) centered at instances of positive bags. For the oo-norm these hypotheses can be modified into hyper-rectangles by a greedy algorithm. Our approach includes a stopping criterion for the algorithm based on estimates for the generalization error. These estimates can also be used to choose a preferable metric and data normalization. Compared to other approaches our algorithm delivers improved or at least competitive results on several multiple instance benchmark data sets. <s> BIB003 </s> A Review of Multi-Instance Learning Assumptions <s> The Standard MI Assumption <s> We introduce a novel algorithm for decision tree learning in the multi-instance setting as originally defined by Dietterich et al. It differs from existing multi-instance tree learners in a few crucial, well-motivated details. Experiments on synthetic and real-life datasets confirm the beneficial effect of these differences and show that the resulting system outperforms the existing multi-instance decision tree learners. <s> BIB004 </s> A Review of Multi-Instance Learning Assumptions <s> The Standard MI Assumption <s> Multi-instance learning and semi-supervised learning are different branches of machine learning. The former attempts to learn from a training set consists of labeled bags each containing many unlabeled instances; the latter tries to exploit abundant unlabeled instances when learning with a small number of labeled examples. In this paper, we establish a bridge between these two branches by showing that multi-instance learning can be viewed as a special case of semi-supervised learning. Based on this recognition, we propose the MissSVM algorithm which addresses multi-instance learning using a special semi-supervised support vector machine. Experiments show that solving multi-instance problems from the view of semi-supervised learning is feasible, and the MissSVM algorithm is competitive with state-of-the-art multi-instance learning algorithms. <s> BIB005
A large percentage of the work on MI learning, including all early work and notably including BIB001 and BIB002 , makes a particular assumption regarding the relationship between the instances within a bag and the class label of the bag. Dietterich et al. considered this assumption to be so fundamentally important that they included it as part of their definition of multiple-instance learning. We will follow  , and refer to this assumption as the standard MI assumption. The standard MI assumption states that each instance has a hidden class label c ∈ Ω = {+, −}. Under this assumption, an example is positive if and only if one or more of its instances are positive. Thus, the bag-level class label is determined by the disjunction of the instance-level class labels. Formally, let X = {X 1 , X 2 , . . . , X n } ∈ N χ be a bag containing n instances from feature space χ. Each instance has a class label determined by some process g : χ → Ω. Let ν S : N χ → Ω be a standard MI concept, and equate "+" with the logical constant ''True", and "−" with the logical constant ''False". Then: It should be noted that the standard MI assumption is asymmetric: if the positive and negative labels are reversed, the assumption has a different meaning. Therefore, when we apply this assumption, we need to be clear which label should be the positive one. The standard MI assumption was adopted because it is believed to be appropriate for the musk problem domain. In the musk problem, it is assumed that a molecule (represented by a bag of instances) will emit a musky smell if and only if one of its conformations (represented by an individual instance) binds to a certain target site, hence the standard MI assumption applies BIB001 . A number of learning algorithms for MI classification under the standard MI assumption have been proposed in the literature. BIB001 presented several algorithms for learning axis-parallel rectangles to identify the positive region of instance space. A bag is classified as positive if it has at least one instance in this region. BIB002 defined diverse density, a measure of the likelihood that a point in instance space is a positive target concept, and used a gradient search to find the point that is most likely to define the target concept. A refinement of this algorithm, EM-DD, was proposed by . Several single-instance learning methods have been "upgraded" to the multi-instance scenario under the standard MI assumption, including support vector machines  , neural networks  decision trees BIB004 ,  , decision rules  , and weak learners for boosting BIB003 . BIB005 showed that multi-instance learning under the standard MI assumption can be viewed as a semi-supervised learning problem with the additional constraint that positive bags must contain at least one positive instance. They adapted semi-supervised support vector machines to the standard MI scenario by encoding this "positive constraint" in the objective function of the SVM.