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:
- Point Set Distances: Simple metrics such as the minimum distance ($d_{min}$) or the Hausdorff distance ($d_H$).
- 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.
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.
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