Gaussian Processes Multiple Instance Learning

Minyoung Kim, Fernando De la TorreICML 2010 · OpenReview

TL;DR

This paper introduces GPMIL, a framework that applies Gaussian Processes (GP) to Multiple Instance Learning (MIL). By modeling bag labels as a sigmoid function over the maximum of latent instance variables, the authors provide a principled way to learn kernel parameters and obtain probabilistic predictions. This approach consistently outperforms traditional SVM-based MIL methods on standard benchmarks.

What Problem Does This Paper Address?

In standard supervised learning, every data point has a distinct label. In Multiple Instance Learning (MIL), data is instead organized into "bags." The algorithm only knows the label of the bag as a whole: a bag is considered positive if at least one instance inside it is positive, and negative if all its instances are negative.

This paradigm is highly relevant for tasks like:

  • Image Retrieval: An image (bag) is "positive" for a "tiger" if at least one patch (instance) contains a tiger.
  • Drug Discovery: A molecule (bag) is active if at least one of its low-energy shapes (instances) binds to a target.

The primary challenge is that the "max" relationship (where one positive instance dictates a positive bag) is non-linear and non-differentiable. Most existing methods, such as mi-SVM, are non-probabilistic and rely on heuristic grid searches to find the right model parameters. This is computationally inefficient and fails to provide a measure of predictive uncertainty.

Methods

The authors propose Gaussian Processes Multiple Instance Learning (GPMIL). The core idea is to define a bag-level likelihood based on the latent scores ($f$) of the instances within that bag.

Graphical model representation of GPMIL.

The Model

The probability of a bag being positive is modeled as the sigmoid of the maximum latent score among its instances: $$P(Y_b | \mathbf{F}_b) = \frac{1}{1 + \exp(-Y_b \max_{i \in b} f_i)}$$

Overcoming Intractability

Because the max function is non-differentiable and makes exact inference impossible, the authors propose two approximation strategies to make the model tractable:

  1. Soft-max Approximation: They replace the max operator with a differentiable log-sum-exp function. To handle the resulting non-convex optimization, they use a Laplace approximation combined with a PSD (Positive Semi-Definite) projection of the Hessian matrix to ensure stability during gradient descent.
  2. Witness Deterministic Annealing (WDA): They introduce "witness" indicator variables that represent the probability of a specific instance being the one responsible for a positive bag label. They use Deterministic Annealing, starting with a "high temperature" (where all instances are equally likely to be the witness) and gradually cooling down to "lock in" on the most likely positive instance.

Key Insights and Ideas

  • Probabilistic MIL: Unlike SVM-based methods, GPMIL provides a full probability distribution. This allows researchers to understand the confidence of a bag's classification, which is vital in risk-sensitive fields like medical diagnosis.
  • Principled Parameter Learning: By leveraging the GP framework, the authors can use Empirical Bayes (maximizing marginal likelihood) to learn kernel hyperparameters. This is far more robust than the manual grid search used by most MIL algorithms.
  • The "Witness" Matters: The WDA approach highlights that identifying the specific instance (the "witness") that triggers a bag's label is often more effective than simply smoothing the labels across all instances.
  • Smoothness via GP Prior: The GP prior naturally enforces that similar instances in the feature space should have similar latent scores, providing a built-in regularization that helps the model generalize from limited bag-level labels.

Key Results

GPMIL, particularly the WDA version, consistently outperformed state-of-the-art methods across several classic MIL benchmarks.

Performance comparison of GPMIL against state-of-the-art methods on MUSK and image datasets.
  • MUSK1 & MUSK2 (Drug Discovery): On the "gold standard" MUSK1 dataset, GPMIL achieved a test error of 10.53%, significantly better than mi-SVM (12.6%) and EMDD (15.2%).
  • Image Annotation (COREL): On the "Tiger" dataset, GPMIL reached 12.63% error, compared to 16.0% for the nearest competitor (MI-SVM).
  • Text Classification (TREC9): In 7 out of 10 TREC9 sub-datasets, GPMIL provided the best results, often by a wide margin (e.g., TST1 error of 5.57% vs. 14.2% for EMDD).
  • Hyperparameter Recovery: On synthetic 1D data, the model accurately estimated the RBF kernel width ($\sigma \approx 3.05$ vs. true $\sigma = 3.0$), proving the effectiveness of the Empirical Bayes approach.

Limitations and Future Work

  • Scalability: Like most standard GP models, GPMIL suffers from $O(n^3)$ computational complexity relative to the number of instances. This makes it difficult to apply to massive datasets without incorporating sparse GP approximations.
  • Non-Convexity: While the approximations help, the underlying MIL problem is inherently non-convex. Different starting points for gradient descent can lead to different local minima.
  • Future Directions: The authors suggest exploring more advanced approximation algorithms (like Expectation Propagation) and looking into ways to improve computational efficiency for larger-scale MIL problems.

Summary updated

Abstract

This paper proposes a multiple instance learning (MIL) algorithm for Gaussian processes (GP). The GP-MIL model inherits two crucial benefits from GP: (i) a principle manner of learning kernel parameters, and (ii) a probabilistic interpretation (e.g., variance in prediction) that is informative for better understanding of the MIL prediction problem. The bag labeling protocol of the MIL problem, namely the existence of a positive instance in a bag, can be effectively represented by a sigmoid likelihood model through the max function over GP latent variables. To circumvent the intractability of exact GP inference and learning incurred by the non-continuous max function, we suggest two approximations: first, the soft-max approximation; second, the use of witness indicator variables optimized with a deterministic annealing schedule. The effectiveness of GP-MIL against other state-of-the-art MIL approaches is demonstrated on several benchmark MIL datasets.
BibTeX
@inproceedings{kim2010gaussian,
  author = {Minyoung Kim and Fernando De la Torre},
  title = {{Gaussian Processes Multiple Instance Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=Hy4yIhWu-B},
}
Figure