Abstract: We consider a supervised learning setting in which the main cost of learning is the number of training labels and one can obtain a single label for a bag of examples, indicating only if a positive example is present in the bag. This setting, known as Multi-Instance Learning (MIL), is particularly effective when the positive class is rare. We provide a theoretical framework for choosing the optimal bag size and introduce PMIL, a simple algorithm that successfully learns individual classifiers from these aggregate labels.
Introduction
In many real-world machine learning applications—such as medical screening, chemical testing, or ad-click prediction—unlabeled data is plentiful, but obtaining ground truth labels is expensive. This paper, originally presented at AISTATS 2010, addresses this bottleneck by proposing a strategy where the learner chooses to group examples into "bags" and requests a single label for the entire group.
This approach leverages a specific opportunity: in many domains, it costs roughly the same amount of effort to label a group of items as it does to label one. For instance, a chemist might test a mixture of multiple molecules for a specific reaction, or a human annotator might quickly scan a grid of images to determine if any contain a target object. By optimizing how these bags are formed, we can significantly reduce the total number of labels required to train an accurate classifier.
Theoretical Framework and Label Complexity
The core of the paper is a theoretical analysis using VC-dimension theory to determine the number of labels needed to reach a target error rate. The authors demonstrate that when the positive class frequency ($\alpha$) is low, the number of required labels drops considerably when using bags instead of individual points.
Optimal Bag Size Selection
To maximize the information gained from each label, the learner should aim for a bag size $r^*$ that results in a roughly 50/50 split of positive and negative labels from the teacher. This maximizes the entropy of the labels. The derived rule of thumb is $r^* \approx 1/\alpha$.
As shown in the figure above, when the positive rate $\alpha$ is small (e.g., < 0.04), the reduction in the number of labels required is mathematically guaranteed. This "Information Paradox" suggests that by making the bag-level task harder (closer to a 50% positive rate), the model is forced to extract more nuanced information about the underlying distribution.
The PMIL Algorithm
Since a positive label for a bag does not specify which example triggered it, the authors propose PMIL (Perceptron-based Multi-Instance Learning). This iterative algorithm operates as follows:
- Initialize with a random separator.
- For each positive bag, identify the "representative" example currently most favored by the model.
- Perform a standard Perceptron update using these representatives.
- Repeat until convergence.
Experimental Validation
The approach was validated across synthetic data, the Statlog (Shuttle) dataset, and the Caltech101 computer vision benchmark. In the Caltech101 experiments, the authors simulated a task where a user identifies if a specific object (like a face or a seahorse) exists within an array of images.
On the Statlog dataset, using bags of size 14 allowed the model to reach target error rates much faster than training on individual labels. The empirical results showed that the benefits of bagging extended even to higher positive rates, up to $\alpha = 0.2$.
Key Insights and Conclusion
By allowing the learner to control bag formation, this method effectively bypasses class imbalance problems. In standard supervised learning with a 1% positive rate, a model can achieve 99% accuracy by always guessing "negative." Bagging "balances" the labels provided by the teacher, forcing the learner to find the true signal.
While the current theory assumes examples within a bag are independent and identically distributed (I.I.D.), future work could incorporate cost functions for human factors (as very large bags may be harder to scan) and explore the impact of correlated data within bags. Nonetheless, the paper provides a robust foundation for reducing label complexity in data-scarce environments.
Summary updated