Dissimilarity-Based Multiple Instance Learning

Lauge Sørensen, Marco Loog, David M. J. Tax, Wan-Jui Lee, Marleen de Bruijne, Robert P. W. Duin

Abstract

Multiple Instance Learning (MIL) deals with data organized into "bags" of instances, where only bag-level labels are available. This paper proposes a novel framework that shifts the focus from instance-level feature spaces to bag-level dissimilarity spaces. By representing bags through their distances to other bags—utilizing both point-set metrics and Earth Mover’s Distance (EMD) on internal distance distributions—the authors transform complex MIL problems into standard supervised learning tasks. This approach enables the use of "off-the-shelf" classifiers and achieves competitive results on standard benchmarks.

Introduction

In traditional supervised learning, each object is represented by a single feature vector. However, in Multiple Instance Learning (MIL), objects are collections of points called "bags." A bag is labeled positive if at least one of its instances represents the target concept. For example, a medical image might be labeled "diseased" if any single patch contains a lesion.

The primary challenge in MIL is the ambiguity of instance labels. Previous approaches often relied on identifying specific "important" instances or using mathematically restrictive kernels. This paper addresses these limitations by proposing a flexible dissimilarity-based representation that captures the relationships between instances within and across bags.

Methodology

The proposed method involves a two-step transformation to map bags into a vector space suitable for standard classification.

Bag Dissimilarity Measures

The authors define the distance between two bags, $B_i$ and $B_j$, using two main categories of metrics:

  1. Point Set Distances: Simple metrics such as the minimum distance ($d_{min}$) or the Hausdorff distance ($d_H$).
  2. Distribution-Based (EMD): This more sophisticated approach examines the distribution of distances between instances within a bag and between bags. By using the Earth Mover’s Distance (EMD) to compare these histograms, the method can identify the "signature" of positive instances.
Distance distributions between bags used for EMD calculation.

Dissimilarity Space Construction

Instead of raw features, each bag is represented by a vector of its distances to all other bags in the training set, creating a "dissimilarity space" ($D$). To further improve linear separability, a second transductive step ($D2$) re-maps bags based on their Euclidean distances within the initial dissimilarity space. Standard classifiers like Support Vector Machines (SVM) and Fisher’s Linear Discriminant are then applied to this $D2$ space.

Experimental Setup

The framework was evaluated on five classic MIL benchmarks:

  • MUSK1 & MUSK2: Molecular activity prediction tasks where the goal is to determine if a molecule has a musky odor.
  • Image Retrieval (Elephant, Fox, Tiger): Identifying specific animals within images based on segmented patches.

Results and Discussion

The dissimilarity-based approach achieved results competitive with, and often exceeding, state-of-the-art specialized MIL algorithms.

Performance comparison on MUSK datasets.

On the MUSK2 dataset, Fisher’s Linear Discriminant in the $D2$ space achieved an accuracy of 93.5%, outperforming many complex kernel-based methods. Similarly, on image datasets like Tiger, the distribution-based measures ($d_{BWmean}$) reached 81.5% accuracy.

Key Insights

  • Flexibility: Unlike SVM kernels that must satisfy Mercer’s condition, the dissimilarity approach allows for any proximity measure, including non-metric ones.
  • Geometric Signatures: The authors demonstrate that positive instances change the internal geometry of a bag. The "bump" in distance histograms allows the model to detect concepts without explicitly identifying positive instances.
  • Transductive Refinement: The transition from space $D$ to $D2$ significantly boosted performance for linear classifiers, suggesting that the initial mapping effectively "unwraps" the data structure.

Conclusion

By shifting the focus to dissimilarity spaces, this paper provides a powerful and flexible framework for MIL. While calculating full dissimilarity matrices can be computationally intensive, the success of "off-the-shelf" classifiers on these representations highlights the importance of the data representation itself. Future work may explore prototype selection to reduce dimensionality and improve computational efficiency.

Summary updated

Abstract

In this paper, we propose to solve multiple instance learning problems using a dissimilarity representation of the objects. Once the dissimilarity space has been constructed, the problem is turned into a standard supervised learning problem that can be solved with a general purpose supervised classifier. This approach is less restrictive than kernel-based approaches and therefore allows for the usage of a wider range of proximity measures. Two conceptually different types of dissimilarity measures are considered: one based on point set distance measures and one based on the earth movers distance between distributions of within- and between set point distances, thereby taking relations within and between sets into account. Experiments on five publicly available data sets show competitive performance in terms of classification accuracy compared to previously published results.
BibTeX
@inproceedings{srensen2010dissimilarity,
  author = {Lauge Sørensen and Marco Loog and David M. J. Tax and Wan-Jui Lee and Marleen de Bruijne and Robert P. W. Duin},
  title = {{Dissimilarity-Based Multiple Instance Learning}},
  booktitle = {SSPR/SPR},
  year = {2010},
  doi = {10.1007/978-3-642-14980-1\_12},
}
Figure