A Review of Multi-Instance Learning Assumptions <s> The GMIL Assumption <s> * Bridges the gap between traditional books on topology/analysis and more specialized treatises on fractal geometry ::: * Contains plenty of examples, exercises, and illustrations ::: * Ideal for classroom use with a self-contained and careful presentation ::: ::: For the Second Edition of this highly regarded textbook, Gerald Edgar has made numerous additions and changes, in an attempt to provide a clearer and more focused exposition. The most important addition is an increased emphasis on the packing measure, so that now it is often treated on a par with the Hausdorff measure. The topological dimensions were rearranged for Chapter 3, so that the covering dimension is the major one, and the inductive dimensions are the variants. A "reduced cover class" notion was introduced to help in proofs for Method I or Method II measures. Research results since 1990 that affect these elementary topics have been taken into account. Some examples have been added, including Barnsley leaf and Julia set, and most of the figures have been re-drawn. ::: ::: ::: ::: From reviews of the First Edition: ::: ::: "...there has been a deluge of books, articles and television programmes about the beautiful mathematical objects, drawn by computers using recursive or iterative algorithms, which Mandelbrot christened fractals. Gerald Edgar's book is a significant addition to this deluge. Based on a course given to talented high-school students at Ohio University in 1988, it is, in fact, an advanced undergraduate textbook about the mathematics of fractal geometry, treating such topics as metric spaces, measure theory, dimension theory, and even some algebraic topology...the book also contains many good illustrations of fractals..." ::: ::: - Mathematics Teaching ::: ::: "The book can be recommended to students who seriously want to know about the mathematical foundation of fractals, and to lecturers who want to illustrate a standard course in metric topology by interesting examples." ::: ::: - Christoph Bandt, Mathematical Reviews ::: ::: "...not only intended to fit mathematics students who wish to learn fractal geometry from its beginning but also students in computer science who are interested in the subject. [For such students] the author gives the required topics from metric topology and measure theory on an elementary level. The book is written in a very clear style and contains a lot of exercises which should be worked out." ::: ::: - H.Haase, Zentralblatt <s> BIB001 </s> A Review of Multi-Instance Learning Assumptions <s> The GMIL Assumption <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> BIB002 </s> A Review of Multi-Instance Learning Assumptions <s> The GMIL Assumption <s> Valiant (1984) and others have studied the problem of learning various classes of Boolean functions from examples. Here we discuss incremental learning of these functions. We consider a setting in which the learner responds to each example according to a current hypothesis. Then the learner updates the hypothesis, if necessary, based on the correct classification of the example. One natural measure of the quality of learning in this setting is the number of mistakes the learner makes. For suitable classes of functions, learning algorithms are available that make a bounded number of mistakes, with the bound independent of the number of examples seen by the learner. We present one such algorithm that learns disjunctive Boolean functions, along with variants for learning other classes of Boolean functions. The basic method can be expressed as a linear-threshold algorithm. A primary advantage of this algorithm is that the number of mistakes grows only logarithmically with the number of irrelevant attributes in the examples. At the same time, the algorithm is computationally efficient in both time and space. <s> BIB003
Scott et al. extend this model to also include a set of repulsion pointsC = {c 1 ,c 2 , . . . ,c k }. In the extended model, a positive bag may only contain instances that are close to at most s of the repulsion points. The model can be understood with reference to the ranked half-Hausdorff metric using the weighted infinity norm. The Hausdorff metric (see, for example, BIB001 ) provides a measure of distance between two bags of points, and is commonly used in computer vision applications. The sets of target points and repulsion points can be viewed as "ideal bags", where positive bags are within a ranked half-Hausdorff distance of some threshold γ from the ideal positive bag, and at least a ranked half-Hausdorff distance of γ away from the ideal negative bag. The Hausdorff distance between bags P and Q is defined to be the largest distance from either a point in P to its closest point in Q, or from a point in Q to its closest point in P , whichever is larger, under some norm. However, this is not robust against noise, so the ranked Hausdorff metric is used: instead of using the largest distance, the sth largest distance is used. Scott et al. compute the distance from the bag to the model (i.e. the half -Hausdorff metric), but not vice-versa, as it is assumed that the model is accurate and does not contain extraneous points. Scott et al. used the weighted infinity norm as the instance-level distance measure required to compute the Hausdorff distance. The infinity norm defines the length of a vector as x ∞ = max(|x 1 |, |x 2 |, . . . , |x n |), the largest absolute value of its components. Thus the set of points with a distance of at most d from a point p under the infinity norm are the points within a hypercube of width 2d and centre at point p. The weighted infinity norm allows scaling of the vector components, such as for normalization. The hypercubes from the infinity norm are hyperrectangles or "boxes" when the weighted infinity norm is used. The ranked half-Hausdorff metric using the weighted infinity norm can be stated formally as where max s is the sth max, P is a bag, Q is the set of target points, and "−" denotes standard vector subtraction. Let a bag P be positive if and only if the above equation evaluates to at most γ. Then a target concept is a set of k = |Q| axis-parallel target boxes, and a bag is positive if and only if it contains points within at least r = k − s + 1 of the k target boxes. To also include a setQ of k axis-parallel repulsion boxes, we must also check that the following formula evaluates to at least γ , which is another constant: Under this extended model, for a bag to be positive, it must also contain points within at most s − 1 of the k repulsion boxes. In terms of Weidmann's hierarchy, Scott et al.'s MI formulation, without repulsion points, is the same as presence-based MI learning when boxes are viewed as instance-level concepts and the minimum threshold r is equal to the number of target points k. When r = k, Scott et al.'s model is more general than the presence-based MI model. Weidmann's threshold and count-based MI concepts generalize presence-based MI concepts in a different fashion to Scott et al.'s model, and neither is strictly more general than the other. Count-based MI concepts can model repulsion points by setting the maximum count for some instance-level concepts to zero. However, count-based and threshold-based concepts cannot model the case where only r out of k concepts must be present for a bag to be positive. The GMIL assumption cannot represent problems where the number of instances belonging to specific concepts must be within a given range (as in threshold and count-based MI), as only concept presence rather than concept counts are included in the model. BIB002 proposed the GMIL-1 algorithm to learn GMIL concepts. The algorithm explicitly enumerates all possible axis-parallel boxes. It creates a single-instance feature space with boolean attributes for each box, signifying whether a bag contains an instance within that box. To reduce the dimensionality of this space, boxes that cover the same instances are grouped together, and only one representative box for each group is used. The training bags are mapped into the feature space, and the single-instance algorithm Winnow BIB003 is trained on the transformed dataset.