A Review of Multi-Instance Learning Assumptions <s> Multi-Instance Multi-Label Learning <s> This work focuses on algorithms which learn from examples to perform multiclass text and speech categorization tasks. Our approach is based on a new and improved family of boosting algorithms. We describe in detail an implementation, called BoosTexter, of the new boosting algorithms for text categorization tasks. We present results comparing the performance of BoosTexter and a number of other text-categorization algorithms on a variety of tasks. We conclude by describing the application of our system to automatic call-type identification from unconstrained spoken customer responses. <s> BIB001 </s> A Review of Multi-Instance Learning Assumptions <s> Multi-Instance Multi-Label Learning <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> BIB002 </s> A Review of Multi-Instance Learning Assumptions <s> Multi-Instance Multi-Label Learning <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> BIB003 </s> A Review of Multi-Instance Learning Assumptions <s> Multi-Instance Multi-Label Learning <s> Multi-label classification methods are increasingly required by modern applications, such as protein function classification, music categorization, and semantic scene classification. This article introduces the task of multi-label classification, organizes the sparse related literature into a structured presentation and performs comparative experimental results of certain multilabel classification methods. It also contributes the definition of concepts for the quantification of the multi-label nature of a data set. <s> BIB004
In traditional supervised learning, multi-class learning problems contain more than two classification categories, but each learning example belongs to exactly one of these categories. An extension to this is multi-label learning, where the categories are not mutually exclusive, so that each example may belong to several class categories BIB001 .  formalized multi-instance multi-label learning (MIML), where each multi-instance bag may be associated with multiple class labels. In their formulation, the task in MIML is to learn a function of the form f M IM L : 2 χ → 2 Y , where χ is the instance space, and Y is the set of class categories. Given that multi-instance examples are really bags (multisets) rather than sets, we modify this definition to be f M IM L : N χ → 2 Y (see Section 2.3.1 for more information on this notation). As Zhou and Zhang observe, multi-instance learning and multi-label learning are both natural generalizations of traditional single-instance learning, and MIML is a generalization of both of these. In MIML, it is clear that the standard MI assumption is not directly applicable, as that assumption is dependent on the learning task being a binary classification problem. Other assumptions regarding the relationships between the instances and the bag-level labels are required for MIML. 22 j. foulds and e. frank Zhou and Zhang proposed two solution frameworks for applying single-instance learners to solve MIML problems. Although they did not discuss the types of concepts that these frameworks are appropriate for, we will attempt to unify them under a more general algorithm template, and thus expose the MIML assumptions used by both methods. Before discussing these solution frameworks, it is instructive to first consider a method for converting multi-label problems to single-label problems, used by both of Zhou and Zhang's MIML approaches. The method is referred to by BIB004 as Problem Transformation method PT4. In this method, the multi-label problem is converted into a set of binary classification problems -one for each of the labels. For each label, a dataset is created where the multi-label training examples that are associated with that label are tagged as positive in the new dataset, and are otherwise tagged as negative. Multi-label predictions are made by building a single-label classifier on each of the new datasets, and outputting the union of the positive predictions made by these classifiers. The first solution framework proposed by Zhou and Zhang (Solution 1 ) is to use multi-instance learning as a bridge between MIML and single-instance learning. The MIML problem is converted to a set of MI problems using PT4. Zhou and Zhang were interested specifically in methods that use traditional single-instance algorithms to solve MIML problems, and hence their formulation of Solution 1 insists on the use of an MI method that can be solved using a single-instance algorithm. Thus an MI method that applies a single-instance algorithm, such as MI Boosting BIB002 , is then applied to the resulting MI problems. However, it is clear that any arbitrary MI learning algorithm could in fact be applied. We will refer to this relaxed version of the Solution 1 framework as MIML PT4. Here, the assumption is that the MI concept corresponding to each label can be learned under the assumption used by the MI base learner. For example, when the MI base learner is BIB002 MI boosting algorithm, the implicit assumption is that the concept associated with each of the labels is a collective assumption MI concept. We shall call this general MIML assumption the MIML PT4 Assumption. Zhou and Zhang's other solution framework (Solution 2 ) uses multi-label learning as the bridge between MIML and traditional single-instance learning. First, a propositionalization method is used to map the MI bags into a single-instance feature space, retaining the multiple labels, resulting in a single-instance multi-label dataset. This new learning problem is transformed into a set of traditional single-instance single-label datasets by applying PT4, and hence is solved by building single-instance models on the resulting datasets. However, if we view the propositionalization step in Solution 2 as the application of a "wrapper"-type MI algorithm, Solution 2 can in fact also considered to be within the MIML PT4 framework. This is because the order of the transformations is not important -the result is the same whether we apply PT4 and then use the wrapper method to propositionalize the data (MIML PT4), or propositionalize first and then apply PT4 (Solution 2). Hence, the MIML PT4 assumption applies to Solution 2 algorithms -it is assumed that the MI assumption used by the propositionalization algorithm applies to each of the MI concepts associated with the MIML labels.  MimlBoost algorithm uses MI Boosting BIB002 as the multi-instance base learner for Solution 1, while their MimlSvm algorithm uses the constructive clustering propositionalization method BIB003 and an SVM base learner to implement Solution 2.