Greedy Multiple Instance Learning via Codebook Learning and Nearest Neighbor Voting

Gang Chen, Jason J. CorsoarXiv 2012 · DOI · arXiv

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
Overview of the GMIL pipeline, illustrating the transition from raw bags to target discovery through clustering and histogram analysis.

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.

Sensitivity analysis of GMIL accuracy based on the number of clusters (a) and the number of negative centers (b).

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

Abstract

Multiple instance learning (MIL) has attracted great attention recently in machine learning community. However, most MIL algorithms are very slow and cannot be applied to large datasets. In this paper, we propose a greedy strategy to speed up the multiple instance learning process. Our contribution is two fold. First, we propose a density ratio model, and show that maximizing a density ratio function is the low bound of the DD model under certain conditions. Secondly, we make use of a histogram ratio between positive bags and negative bags to represent the density ratio function and find codebooks separately for positive bags and negative bags by a greedy strategy. For testing, we make use of a nearest neighbor strategy to classify new bags. We test our method on both small benchmark datasets and the large TRECVID MED11 dataset. The experimental results show that our method yields comparable accuracy to the current state of the art, while being up to at least one order of magnitude faster.
BibTeX
@misc{chen2012greedy,
  author = {Gang Chen and Jason J. Corso},
  title = {{Greedy Multiple Instance Learning via Codebook Learning and Nearest Neighbor Voting}},
  year = {2012},
  eprint = {1205.0610},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1205.0610},
}
Figure