PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiple Instance Learning with Bag Dissimilarities

Veronika Cheplygina, David M. J. Tax, Marco Loog

arXiv:1309.5643v3stat.MLcs.LG

TL;DR

Because instance labels in MIL are ambiguous, methods that rely on assumptions about their relationship to bag labels may not generalize across problems. The paper represents bags by dissimilarities to training bags, and reports competitive performance with low computational effort across a range of MIL datasets.

  • Problem

    Instance labels in MIL are ambiguous, and assumptions about their relationship to bag labels may fit particular datasets without generalizing across MIL problems.

    Source: §1 · p. 2

  • Method

    MInD represents each bag by its dissimilarities to training bags and uses that vector as a feature representation for supervised classification.

    Source: §1 · p. 3, §7 · p. 30

  • Results

    The approach was very competitive with other MIL algorithms at low computational effort, and minimum-instance-distance averaging performed well on all discussed real-life datasets.

    Source: §7 · p. 30

  • Takeaways & Limitations

    The dissimilarity approach permits expert-defined dissimilarities without metricity or positive-definiteness restrictions and allows flexibility in classifier choice.

    Source: §1 · p. 3, §7 · p. 31

    The choice between point-set and instance-distribution approaches may depend on bag size and computational issues, and their trade-off remains to be investigated.

    Source: §7 · p. 31

Abstract

from arXiv · show

Multiple instance learning (MIL) is concerned with learning from sets (bags) of objects (instances), where the individual instance labels are ambiguous. In this setting, supervised learning cannot be applied directly. Often, specialized MIL methods learn by making additional assumptions about the relationship of the bag labels and instance labels. Such assumptions may fit a particular dataset, but do not generalize to the whole range of MIL problems. Other MIL methods shift the focus of assumptions from the labels to the overall (dis)similarity of bags, and therefore learn from bags directly. We propose to represent each bag by a vector of its dissimilarities to other bags in the training set, and treat these dissimilarities as a feature representation. We show several alternatives to define a dissimilarity between bags and discuss which definitions are more suitable for particular MIL problems. The experimental results show that the proposed approach is computationally inexpensive, yet very competitive with state-of-the-art algorithms on a wide range of MIL datasets.

1. Introduction

Multiple instance learning represents complex objects as bags of instances when reducing them to a single vector may lose important differences. Because label-based assumptions may not fit many applications, the paper introduces MInD, a flexible bag-dissimilarity approach, and examines how to choose dissimilarities for different MIL problems.

1. Introduction

  • Representing complex objects as bags of feature vectors can preserve information that a single feature vector may lose.Examples include images represented as bags of segments.Source: §1 · p. 2
  • Standard MIL assumptions may not fit some applications, such as treating sand as the defining concept for desert images when beach images are also present.Relaxed approaches allow varying fractions or numbers of concept instances and multiple concepts.Source: §1 · p. 2
  • Bag-level methods avoid explicit assumptions about instance labels, but converting bags to a single dissimilarity vector can lose representational power and the preferred dissimilarity is not always clear.The definition can affect how well the representation captures class differences.Source: §1 · pp. 2–3
  • MInD represents each bag through dissimilarities to other bags and discusses the assumptions and suitability of alternative definitions for different MIL problems.The paper also presents a repository of MIL problem examples.Source: §1 · p. 3

2. Review of MIL Approaches

MIL approaches differ in how they relate bag labels to instance labels and in the representation used for learning. This review covers concept-based methods, relaxed assumptions, bag-level methods, and supervised learning on propagated instance labels.

2. Review of MIL Approaches

  • Under the standard assumption, a bag is positive if and only if it contains at least one positive or concept instance.Concept-based methods model a feature-space region containing an instance from every positive bag and none from negative bags.Source: §2 · p. 4
  • Diverse Density searches for a concept point using positive-bag proximity and negative-instance distance, while EM-DD iteratively refines instance selections and the concept.Diverse Density optimization may reach a local optimum, so several restarts are needed.Source: §2 · p. 4
  • mi-SVM infers hidden instance labels under bag-label constraints, whereas MILBoost reweights instances during boosting and combines their labels using noisy OR.Source: §2 · pp. 4–5
  • Relaxed MIL assumptions allow fractions or specified numbers of positive instances and multiple concepts; MILES represents bags by similarities to candidate instances and selects discriminative ones with a sparse 1-norm SVM.MILES also permits negative concepts that occur only in negative bags.Source: §2 · p. 5
  • Bag-based methods assume same-class bags are similar and learn from bag distances, kernels, or dissimilarities; SimpleMIL instead propagates bag labels to instances for supervised learning.The review distinguishes instance-vector, bag-dissimilarity, and bag-instance representations; the latter two allow regular supervised classifiers with fewer label-relationship assumptions, while their similarity definitions still imply assumptions about important instances.Source: §2 · pp. 5–6

3. Bag Dissimilarity Representation

MInD represents each bag by its dissimilarities to training-set prototypes, turning MIL into a feature-based supervised learning problem. The framework allows different bag representations and dissimilarity definitions, with choices suited to different MIL settings.

3. Bag Dissimilarity Representation

  • Each bag becomes a vector of dissimilarities to a subset of training bags, so regular supervised learning can be applied to the resulting feature representation.The framework separates how a bag is represented from how the dissimilarity between two bags is defined.Source: §3 · pp. 6–7

3.1. Bags as Point Sets

  • Point-set dissimilarities aggregate instance distances; unlike strict Hausdorff metrics, general dissimilarity features may be asymmetric and need not satisfy metric properties.The framework can retain both directions of an asymmetric dissimilarity rather than forcing symmetry.Source: §3.1 · pp. 7, 9

3.2. Bags as Instance Distributions

  • Bags can be approximated as distributions, from a normal model to Parzen densities or instance-level Dirac deltas, with distance measures chosen to suit the approximation.For the Dirac-delta representation, earth mover's distance minimizes transport cost between bags, with each instance assigned an equal share of its bag's probability mass.Source: §3.2 · pp. 9–11

3.3. Contrast with related approaches

  • Compared with Citation-kNN's nearest-neighbor voting, the dissimilarity-space approach uses the dissimilarity matrix as features; unlike kernel methods, it does not require a positive semi-definite matrix.It can use dissimilarities to a subset of training bags rather than requiring all pairwise values.Source: §3.3.1 · p. 11, §3.3.2 · pp. 12–13

3.3.1. Distances

  • A dissimilarity need only distinguish positive from negative bags relative to a prototype; unlike a distance, it need not assign lower values to same-class bags.Thus, both distributions shown in Figure 4 can be informative for classification in dissimilarity space, though only one suits nearest-neighbor classification.Source: §3.3.1 · p. 12, Figure 4 · p. 12

3.3.2. Kernels

  • Dissimilarity-based methods allow any dissimilarity function and can use a subset of training bags as prototypes, reducing the computation needed for the matrix and classifier.The paper gives M = log(N) as an example of a prototype-set size that could reduce cost while still producing good performance.Source: §3.3.2 · pp. 12–13

3.3.3. Instance similarity

  • Using bags as prototypes can reduce dimensionality and capture instance interactions, while direct distances can remain informative when an RBF similarity would suppress large distances.In the Multi-concept example, a distance to an outlying concept instance encodes that positive bags contain an instance far from the other bags.Source: §3.3.3 · pp. 13–14

4. Multiple Instance Datasets

The datasets span image, text, and molecule tasks, with varied data-generation processes and MIL properties. The examples include both standard instance-label assumptions and settings with multiple concepts or correlated labels.

Multiple Instance Datasets

  • Musk bags are molecules whose instances are conformations, and the standard assumption holds: one musky-smelling conformer is sufficient for a positive label.The conformer features describe surface properties related to binding.Source: §4 · p. 15
  • Corel scene categories can require multiple concepts, as Beach images may need both water and sand; Historical buildings also spans visually diverse structures and interiors.For these examples, a single positive instance may not determine the bag label.Source: §4 · pp. 15–16
  • AjaxOrange bags are object images, but hard-to-segment objects can yield several visible part-concepts, with orientation and lighting affecting which parts appear.The source images show objects against varying backgrounds and under varying orientations and lighting conditions.Source: §4 · p. 16
  • Bird-song bags are positive when a species is heard, while label correlations up to 0.7 mean instances negative for one species may still help classify it.The passages suggest separate concepts for different species because their songs may be similar within species.Source: §4 · p. 16
  • Newsgroups positive bags may contain politics posts that differ widely in feature space, so several distinct concepts can each suffice for the category.The passage describes positive bags as containing 3% politics posts.Source: §4 · p. 16
  • Web Recommendation bags are webpages represented by linked pages; the task predicts user-specific recommendations, with cooking and sports content as possible interests.The datasets share websites but use labels from different users; the train and test sets were concatenated for cross-validation.Source: §4 · pp. 16–17

5. Experiments

Across varied MIL datasets, the experiments compare bag dissimilarities and other MIL methods, finding MInD competitive overall while showing that dissimilarity choice and bag structure matter. The results also indicate that dissimilarity matrices can be useful for classification without being metric or Euclidean.

5. Experiments

  • The experiments use cross-validation and AUC, with all datasets in the final comparison; bags in each fold serve as prototypes, without prototype selection.The dCS parameter uses a default value, and the comparisons use logistic and SVM classifiers, with SVM results generally superior on average.Source: §5 · p. 17

5.1. Point Set Dissimilarities

  • Dminmin, Dmeanmin, and Dmaxmin best match the artificial Concept, Distribution, and Multi-concept settings, respectively; Dmeanmean also performs well on the latter two.Dminmin emphasizes minimum instance distances, Dmeanmin reflects contributions from most or all instances, and Dmaxmin selects remote informative instances.Source: §5.1 · p. 18
  • On real datasets, minimum-distance dissimilarities perform comparably, but Dminmin performs very poorly on AjaxOrange and alt.atheism; overall, Dmeanmin gives the best results.For alt.atheism, dense clusters make Dminmin produce many zero dissimilarities and class overlap, while informative outliers help Dmeanmin, Dmaxmin, and Dmeanmean.Source: §5.1 · pp. 18–20

5.2. Distribution Dissimilarities

  • DMaha performs poorly except on Musk2, EMD is good without clear advantages over point-set dissimilarities, and dCS is reasonable despite sensitivity to σ.DCS emphasizes smaller distances, unlike Dmeanmean, which gives large distances more influence; this helps explain their contrasting results on alt.atheism and Brown Creeper.Source: §5.2 · p. 21

5.3. Properties of dissimilarity matrices

  • Dissimilarity matrices need not be Euclidean or metric to remain useful for classification, but their properties alone cannot predict classifier performance.DCS shows highly non-Euclidean and non-metric behavior on Musk2 and Web; its sum of similarities can reflect varying bag sizes, which may be informative when bag size tracks labels.Source: §5.3 · pp. 22–24

5.4.1. Learning curves

  • Across six datasets, MInD and MILES are usually among the best performers, with MInD stronger on alt.atheism and MILES stronger on AjaxOrange.MInD's advantage is more apparent with fewer training bags except on AjaxOrange; Minimax and SimpleMIL are consistent but typically trail, while EM-DD needs larger training sets.Source: §5.4.1 · p. 25
  • Minimax, MInD, and MILES offer the best performance-time balance, although MInD and MILES are slower; their representation costs can be shared.MInD and MILES representation construction is quadratic in training instances, while SimpleMIL and Minimax are fastest with linear representation costs.Source: §5.4.1 · p. 26

5.4.2. Comparison

  • MInD ranked best in the Friedman test and significantly outperformed four classifiers; MILES and Minimax were not significantly different from MInD.Overall, MILES and MInD gave the best results; the authors recommend trying Minimax and MInD, and MILES when dimensionality allows.Source: §5.4.2 · pp. 26–27

6. Recommendations

Recommendations center on choosing dissimilarities for dataset properties and classifiers suited to the available bags and learning setting.

6.1. Dissimilarity measure

  • dmeanmin is reasonable for many datasets, but inspect instance projections and weigh bag size, instance dimensionality, and computational cost when choosing a measure.Experts can also supply application-specific instance measures; these may be non-metric, which the dissimilarity approach can handle.Source: §6.1 · pp. 28–29

6.2. Classifier

  • Dissimilarity features accept many supervised classifiers; with few bags, avoid overly complex classifiers, and multi-class tasks can use inherently multi-class options such as nearest neighbor.Sparse classifiers such as the 1-norm SVM can help explain predictions through their selected prototypes.Source: §6.2 · p. 30

7. Discussion and Conclusions

The paper represents each MIL bag by dissimilarities to training bags and compares ways to define them. Across the discussed problems, definitions encode different assumptions; averaging minimum instance distances performed well across the real-life datasets discussed, with low computational effort.

7. Discussion and Conclusions

  • Each bag is represented by its dissimilarities to training bags, converting MIL into supervised learning where any classifier can be used.Bag dissimilarities can treat bags as point sets, instance distributions, or attributed graphs.Source: §7 · p. 30
  • Averaging minimum instance distances showed good performance in all discussed real-life datasets; the approach was highly competitive while keeping computational effort low.Different dissimilarity definitions make different implicit assumptions about which instances are informative.Source: §7 · p. 30
  • The approach permits expert-defined and non-metric dissimilarities, accommodates flexible classifiers, and can extend to other learning settings.Non-metric dissimilarities may be more informative than metric counterparts.Source: §7 · p. 31
  • The paper leaves open when to choose point-set versus instance-distribution approaches, since accuracy and computational issues may favor different choices.The authors describe the approach as attractive for domains where data are naturally grouped in bags but MIL is not yet used.Source: §7 · p. 31
Loading 1309.5643v3…