A Review of Multi-Instance Learning Assumptions <s> Nearest Neighbour 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> BIB001 </s> A Review of Multi-Instance Learning Assumptions <s> Nearest Neighbour Assumptions <s> In this paper we propose a quadratic programming approach to computing the edit distance of graphs. Whereas the standard edit distance is defined with respect to a minimum-cost edit path between graphs, we introduce the notion of fuzzy edit paths between graphs and provide a quadratic programming formulation for the minimization of fuzzy edit costs. Experiments on real-world graph data demonstrate that our proposed method is able to outperform the standard edit distance method in terms of recognition accuracy on two out of three data sets. <s> BIB002 </s> A Review of Multi-Instance Learning Assumptions <s> Nearest Neighbour Assumptions <s> Previous studies on multi-instance learning typically treated instances in the bags as independently and identically distributed. The instances in a bag, however, are rarely independent in real tasks, and a better performance can be expected if the instances are treated in an non-i.i.d. way that exploits relations among instances. In this paper, we propose two simple yet effective methods. In the first method, we explicitly map every bag to an undirected graph and design a graph kernel for distinguishing the positive and negative bags. In the second method, we implicitly construct graphs by deriving affinity matrices and propose an efficient graph kernel considering the clique information. The effectiveness of the proposed methods are validated by experiments. <s> BIB003
In traditional single-instance learning, the k-nearest neighbour algorithm is a simple classification method where examples are labeled according to the majority class of the k-closest training examples. Here, "closest" is easily defined using a distance metric such as the Euclidean distance. In multi-instance learning, it is not as immediately obvious how distances between bags should be computed. BIB001 used the maximal and minimal Hausdorff distance for this purpose (see Section 3.5 for more information on this distance). BIB003 note that the graph edit distance BIB002 , as computed on the -graphs of the bags, could be used as a metric for k-nearest neighbours. In nearest-neighbour approaches a specific kind of relationship between bags and class labels is not directly assumed. Instead, the implicit assumption is that bags that are "similar" according to the distance measure used are likely to have the same class label. This is closely related to the BARTMIP assumption (Section 3.5). Note that there is no clear relationship between the nearest neighbour assumption (at least when using variants of the Hausdorff distance) and the standard MI assumption.