Abstract
In Multiple-Instance Learning (MIL), data is organized into "bags" where a positive label implies at least one positive instance exists within. This paper demonstrates that instance-level concepts can be accurately learned by treating bags as probability distributions. We show that a "naive" Single-Instance Learning (SIL) approach—labeling all instances with their bag's label—is theoretically and empirically effective for ranking instances by their likelihood of being positive, often matching the performance of specialized MIL algorithms.
Introduction
Traditionally, MIL focuses on predicting labels for entire bags. However, in domains like drug discovery (3D-QSAR) or image retrieval, identifying the specific "instance concepts" (e.g., the active molecule conformation or the target object in an image) is critical. Learning these unobserved instance labels is challenging; general cases are NP-hard, and simpler models often rely on unrealistic independence assumptions. This work proposes a generative model, MI-GEN, that balances realism with theoretical tractability.
The MI-GEN Framework and the $\gamma$ Assumption
The authors model bags as probability distributions over an instance space. A molecule, for instance, exists in a dynamic equilibrium of various shapes. To ensure learnability, they introduce the $\gamma$ assumption: every negative instance must have a non-zero probability ($\gamma > 0$) of appearing in at least one negative bag. This prevents "confounding" where a negative instance only ever appears alongside positive ones, making it impossible to distinguish.
Under this framework, the authors extend PAC-learning (Probably Approximately Correct) to instance concepts. They specifically analyze Single-Instance Learning (SIL), a baseline where a standard supervised classifier is trained on noisy data created by assigning bag labels to all constituent instances.
The Ranking Revelation
A key insight of this research is the distinction between classification accuracy and ranking performance. While SIL yields poor absolute accuracy—due to mislabeling negative instances in positive bags—it excels at ranking. Because positive instances are exclusive to positive bags, they provide a stronger probabilistic signal. Consequently, a standard classifier learns to rank true positives higher than negatives, leading to high Area Under the ROC Curve (AUC).
Empirical Results
The theory was validated using synthetic Gaussian mixtures and the SIVAL image dataset. On SIVAL, which provides ground-truth instance labels for objects in varied backgrounds, SIL's AUC was statistically indistinguishable from state-of-the-art MIL algorithms like mi-SVM, MICA, and KI-SVM.
Experimental results confirmed that the sample complexity required to achieve a target AUC scales predictably with the noise parameter $\gamma^{-1}$, as shown in the training set size analysis.
Conclusion and Future Work
The MI-GEN model provides a bridge between simplistic IID models and intractable general MIL. While SIL is highly effective for ranking, it remains unsuitable for tasks requiring high instance-labeling accuracy. Future research may explore how the "bags as distributions" framework applies to bag-level concepts and how inductive biases in specialized algorithms can improve performance when data is limited.
Summary updated