A Unifying Framework for Learning Bag Labels from Generalized Multiple-Instance Data

Gary Doran, Andrew Latham, Soumya RayIJCAI 2016

Introduction: Beyond Simple Disjunctions

In standard Multiple-Instance (MI) learning, a "bag" (a collection of instances) is labeled positive if at least one of its instances belongs to a target class. While effective for simple "OR" logic (e.g., an image contains an apple if at least one segment is an apple), many real-world scenarios require more complex relationships. For instance, identifying a "beach" requires the presence of both sand and water (an AND relationship), while a "desert" might require sand but the absence of water (a NOT relationship). This is known as Generalized Multiple-Instance (GMI) learning.

Figure 1: Examples of natural scenes used to construct GMI datasets, where concepts are defined by combinations of instances like sand, water, and mountains.

Existing MI algorithms often struggle with GMI tasks because they are designed for simple disjunctions. This paper introduces a mathematically rigorous framework to represent bags such that standard classifiers can learn these sophisticated "attractive" and "repulsive" instance relationships.

Methodology: Bags as Distributions

The core innovation of this work is the GMI-GEN generative model, which shifts the perspective from viewing bags as static sets to viewing them as samples from underlying probability distributions.

Mean Embeddings and MMD Kernels

By treating bags as distributions, the authors can map them into a high-dimensional Reproducing Kernel Hilbert Space (RKHS) using mean embeddings. The distance between these distributions is then measured using the Maximum Mean Discrepancy (MMD).

The authors prove a critical theoretical result: a "universal" MMD kernel can approximate any GMI concept to arbitrary precision. This provides a solid foundation for using distribution-distance kernels in MI tasks. Furthermore, the paper demonstrates that several popular MI kernels—including the Normalized Set Kernel (NSK), mi-Graph, and YARDS—are actually specific approximations or special cases of this unifying distribution-based framework.

Experimental Evaluation

To validate the framework, the authors conducted an extensive empirical study across 72 datasets:

  • 52 Real-world Benchmarks: Covering drug discovery (3D-QSAR), image retrieval (CBIR), text categorization, and protein sequence classification.
  • 20 Semi-synthetic GMI Datasets: Specifically designed to test complex concepts (e.g., "mountains without trees") where standard MI methods typically fail.

Key Results and Performance

The experimental results confirm the theoretical advantages of the distribution-based approach. As shown in the Critical Difference diagram below, the MMD and Earth Mover’s Distance (EMD) kernels consistently outperformed traditional MI methods across the diverse dataset suite.

Figure 2: Critical Difference diagram showing the average rank of various kernels across 72 datasets. MMD and EMD are the top-performing methods.

While EMD showed slightly higher accuracy in some cases, it suffers from $O(m^3)$ computational complexity (where $m$ is the bag size). In contrast, MMD offers a superior balance of performance and efficiency with $O(m^2)$ complexity.

Conclusion

The MMD kernel emerges as a robust, "safe bet" for practitioners. It effectively handles both standard MI and complex GMI problems without requiring prior knowledge of the underlying data structure. By unifying various MI approaches under the umbrella of distribution-distance kernels, this work provides both a powerful tool for current applications and a clear theoretical path for future research in multiple-instance learning.

Summary updated

BibTeX
@inproceedings{doran2016unifying,
  author = {Gary Doran and Andrew Latham and Soumya Ray},
  title = {{A Unifying Framework for Learning Bag Labels from Generalized Multiple-Instance Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure