Convex Multiple-Instance Learning by Estimating Likelihood Ratio

Fuxin Li, Cristian SminchisescuNeurIPS 2010 · OpenReview

This paper presents a significant theoretical and practical shift in how we approach Multiple-Instance Learning (MIL). By moving away from binary labels and toward continuous likelihood ratios, the authors transform a notoriously difficult non-convex optimization problem into a manageable convex one.

TL;DR

The authors reformulate Multiple-Instance Learning (MIL) as a convex optimization problem by estimating the likelihood ratio of instances rather than their binary labels. This approach provides a theoretically grounded surrogate for classification loss and achieves state-of-the-art performance on complex datasets like text categorization, regardless of the "witness rate" (the proportion of positive instances in a bag).

What Problem Does This Paper Address?

In Multiple-Instance Learning (MIL), data is organized into "bags." A bag is labeled positive if it contains at least one positive instance, and negative if all its instances are negative. This is a "weakly supervised" problem because we don't know which specific instances in a positive bag are the "witnesses" that triggered the label.

Traditionally, this leads to a non-convex optimization problem. Most algorithms use alternating minimization: they guess which instances are positive, train a classifier, and then use that classifier to update their guesses. This process is prone to getting stuck in local optima. Furthermore, many existing MIL methods are sensitive to the "witness rate"—they fail if a positive bag contains only a tiny fraction of positive instances.

Methods

The core innovation is the Convex Reformulation of the MIL constraint. Instead of trying to find binary labels ($+1$ or $-1$), the authors estimate the likelihood ratio: the probability of an instance being positive divided by the probability of it being negative.

  1. Joint Estimation: The authors propose a joint optimization that simultaneously learns a likelihood ratio predictor (a function) and the target likelihood ratio values for the training instances.
  2. $f$-Divergence as a Surrogate: They prove that using $f$-divergences (like $L_1$ or KL-divergence) to estimate these ratios serves as a mathematically sound upper bound for the standard 0-1 classification loss.
  3. SVR-SVM Framework: The method is implemented using a Support Vector Regression (SVR) scheme to estimate the ratios.
  4. Bag Classification via Sorting: Because the joint estimation can introduce bias, the authors don't just threshold the ratios. Instead, they sort the estimated ratios of all instances in a bag into a vector and train a linear SVM on these sorted features to make the final bag-level prediction.
Comparison of surrogate loss functions and estimated likelihoods separating instances.

Datasets

The authors evaluated their approach on three types of data:

  • Synthetic Data: A 2D dataset used to test how the algorithm handles varying "witness rates" (from 10% to 100% positive instances in positive bags).
  • Classic MIL Benchmarks: The standard Musk-1, Musk-2, Elephant, Tiger, and Fox datasets.
  • Text Categorization: A derived version of the 20 Newsgroups corpus, which is particularly challenging because it has a very low witness rate (~3%).

Key Insights and Ideas

  • Convexity is Key: By switching to likelihood ratios, the "at least one" (OR) relationship in MIL can be expressed as a sum constraint, which is convex and thus avoids the local optima issues of previous methods.
  • Theoretical Consistency: The paper provides a formal proof showing that minimizing the proposed divergence loss actually helps minimize the classification error.
  • Witness Rate Independence: Unlike many MIL algorithms that assume a high percentage of positive instances, this method "self-adjusts" and remains stable even when positive instances are rare.
  • Sorting as a Feature: Sorting instance scores within a bag is a clever way to handle variable bag sizes and capture the "distribution" of evidence within a bag for the final classifier.

Key Results

  • 20 Newsgroups: The proposed method (SVR-SVM) significantly outperformed the previous state-of-the-art (miGraph). It achieved the best results in 14 out of 20 news categories.
  • Robustness: In synthetic tests, while competing methods like mi-SVM saw their error rates spike as the witness rate dropped, the SVR-SVM error rate remained nearly constant.
  • Benchmark Performance: On classic datasets, it was highly competitive, particularly excelling on the "Fox" and "Elephant" datasets where instance-level identification is difficult.

Limitations and Future Work

  • Estimation Bias: The authors acknowledge that the joint estimation of the function and the ratios introduces a bias. This makes it difficult to find a single, universal threshold to classify individual instances perfectly.
  • Suboptimal Post-processing: The current method of using a linear combination of sorted ratios for bag classification is described as a "partial solution." The authors suggest that a more integrated way to find the optimal classification threshold remains an open problem.
  • Transductive Learning: Incorporating transductive learning (using the distribution of unlabeled test data) could further improve the accuracy of the learned likelihood ratio function.

Summary updated

Abstract

Multiple-Instance learning has been long known as a hard non-convex problem. In this work, we propose an approach that recasts it as a convex likelihood ratio estimation problem. Firstly, the constraint in multiple-instance learning is reformulated into a convex constraint on the likelihood ratio. Then we show that a joint estimation of a likelihood ratio function and the likelihood on training instances can be learned convexly. Theoretically, we prove a quantitative relationship between the risk estimated under the 0-1 classification loss, and under a loss function for likelihood ratio estimation. It is shown that our likelihood ratio estimation is generally a good surrogate for the 0-1 loss, and separates positive and negative instances well. However with the joint estimation it tends to underestimate the likelihood of an example to be positive. We propose to use these likelihood ratio estimates as features, and learn a linear combination on them to classify the bags. Experiments on synthetic and real datasets show the superiority of the approach.
BibTeX
@inproceedings{li2010convex,
  author = {Fuxin Li and Cristian Sminchisescu},
  title = {{Convex Multiple-Instance Learning by Estimating Likelihood Ratio}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=BJ-SJ_-uZr},
}
Figure