Abstract
Multiple instance learning (MIL) has attracted great attention recently in the machine learning community. However, most MIL algorithms are computationally intensive and struggle with large datasets. In this paper, we propose a greedy strategy to accelerate the MIL process. Our contribution is twofold: first, we propose a density ratio model and demonstrate that maximizing a density ratio function serves as a lower bound for the Diverse Density (DD) model under specific conditions. Second, we utilize a histogram ratio between positive and negative bags to represent the density ratio function, identifying codebooks for both bag types via a greedy strategy. For classification, a nearest neighbor strategy is employed. Experimental results on benchmark datasets and the large TRECVID MED11 dataset show that our method yields comparable accuracy to state-of-the-art models while being at least one order of magnitude faster.
Introduction
In traditional supervised learning, each data point is associated with a single label. Multiple Instance Learning (MIL) relaxes this requirement by organizing data into "bags." A bag is labeled positive if it contains at least one positive instance (the target concept) and negative only if all its instances are negative. This paradigm is particularly useful in fields like drug discovery or image classification where the exact location of a feature is unknown.
The primary challenge in MIL is identifying the true positive instances within positive bags, a task that is often computationally expensive or NP-complete. Existing algorithms like Diverse Density (DD) or MI-SVM rely on iterative optimizations that do not scale well. We introduce GMIL (Greedy Multiple Instance Learning) to address these efficiency bottlenecks.
The GMIL Framework
GMIL shifts the focus from complex optimization to an efficient "greedy" selection of representative points, known as codebooks. The process follows a streamlined pipeline:
- Density Ratio Model: Instead of maximizing the likelihood of a single concept, we maximize a density ratio, focusing on regions where positive instances are frequent and negative instances are rare.
- Clustering and Histograms: All instances across all bags are clustered into $K$ bins using K-means++. Histograms are then constructed for positive and negative bags based on these bins.
- Greedy Codebook Discovery: Bins are ranked by their positive-to-negative frequency ratio. The top $p$ bins are selected as positive codebooks and $q$ bins as negative codebooks.
- Nearest Neighbor Voting: Classification of a new bag is performed by measuring the distance from its instances to the learned codebooks using a minimum Hausdorff distance.
Experimental Results and Analysis
We evaluated GMIL against standard benchmarks (MUSK1, MUSK2, COREL) and the large-scale TRECVID MED11 video dataset.
Performance and Scalability
GMIL demonstrates significant speedups. On the MUSK1 dataset, the traditional DD algorithm required 1,725 seconds, whereas GMIL completed the task in just 1.7 seconds—a thousand-fold improvement. On the TRECVID dataset, GMIL finished training in 1–2 days, compared to over 7 days for MI-SVM. Despite this speed, accuracy remains competitive, with GMIL achieving the highest accuracy (70.0%) on the "Fox" dataset.
Parameter Sensitivity
A key insight of GMIL is the explicit learning of "negative candidate centers," which helps the model ignore common background instances. We analyzed the sensitivity of the model's accuracy to the number of clusters and the number of negative centers.
As shown in the figures, the model maintains stable performance across a range of hyperparameter values, confirming the robustness of the greedy selection strategy.
Conclusion
GMIL provides a highly efficient alternative to traditional MIL algorithms. By approximating the Diverse Density model through a density ratio and employing a greedy codebook discovery strategy, it achieves state-of-the-art performance with linear complexity. Future work may explore more sophisticated distance metrics or kernel-based clustering to further enhance accuracy in complex feature spaces.
Summary updated