Multi-Instance Multi-Label Learning with Application to Scene Classification

Zhi-Hua Zhou, Min-Ling ZhangNeurIPS 2006 · OpenReview

TL;DR

This paper formalizes Multi-Instance Multi-Label (MIML) learning, a framework where a single training example is described by multiple feature vectors (instances) and associated with multiple class labels simultaneously. By proposing two new algorithms—MIMLBOOST and MIMLSVM—the authors demonstrate that capturing ambiguity in both the input and output spaces leads to significantly better performance in complex tasks like scene classification compared to traditional methods.

What Problem Does This Paper Address?

In traditional supervised learning, we assume a one-to-one relationship: one object equals one feature vector and one label. However, the real world is messy. Consider an image of a landscape: it contains multiple patches (trees, water, sky), and it can belong to multiple categories (e.g., "mountains" and "forest").

Existing frameworks only solved half the puzzle:

  • Multi-Instance (MI) learning handles input ambiguity (one object = many instances) but assumes only one label.
  • Multi-Label (ML) learning handles output ambiguity (one object = many labels) but assumes only one instance.
Learning Paradigms

The authors argue that forcing complex data into these "degenerated" frameworks loses vital structural information. They introduce MIML to handle objects that are inherently "many-to-many."

Methods

The authors propose two distinct strategies to solve MIML problems by "bridging" them to better-understood frameworks:

  1. MIMLBOOST (The MI Bridge): This approach transforms the MIML task into a Multi-Instance learning task. It breaks down the multi-label requirement by treating each label as a separate MI problem. It uses an adaptation of boosting (specifically MIBOOSTING) to minimize a bag-level exponential loss function, ultimately building an instance-level predictor that aggregates up to the bag's labels.
  2. MIMLSVM (The ML Bridge): This approach transforms the MIML task into a Multi-Label learning task. Since SVMs usually require a single fixed-length vector, the authors use $k$-medoids clustering with Hausdorff distance (a metric for measuring how far two sets of points are from each other) to map a "bag" of instances into a single numerical vector. This vector represents the bag's distance to various cluster centers. Once "flattened" this way, a standard multi-label SVM (MLSVM) is applied.

Datasets

The primary evaluation was conducted on a Natural Scene Classification dataset:

  • Size: 2,000 images collected from the COREL collection and the Internet.
  • Classes: Desert, mountains, sea, sunset, and trees.
  • Complexity: Over 22% of the images are associated with more than one label.
  • Preprocessing: Each image was divided into 9 overlapping patches (instances) using the SBN (Single Blob with Neighbors) method.

Key Insights and Ideas

  • MIML as the General Case: The authors show that traditional supervised learning, MI learning, and ML learning are all special, simplified cases of MIML. By solving the most general version, we can capture more "original information."
  • The Power of Structural Representation: Even though MIMLSVM involves a transformation that "loses" some information (mapping bags to distance vectors), it still outperforms traditional ML methods. This suggests that treating the image as a collection of parts (instances) is fundamentally more powerful than concatenating those parts into one giant, flat vector.
  • Reducing Complexity: The paper proves that you don't necessarily need a brand-new mathematical paradigm to solve MIML; you can effectively "reduce" the problem to MI or ML tasks using clever mappings or transformations.

Key Results

The MIML algorithms were compared against state-of-the-art Multi-Label (ADABOOST.MH, MLSVM) and Multi-Instance (Diverse Density, EM-DD) algorithms.

  • Vs. Multi-Label: Both MIMLBOOST and MIMLSVM significantly outperformed ADABOOST.MH and MLSVM across all five evaluation metrics (Hamming loss, one-error, coverage, ranking loss, and average precision). For example, MIMLSVM achieved an average precision of 0.783, while the best traditional ML method (MLSVM on flat vectors) only reached 0.756.
MIMLSVM Performance
  • Vs. Multi-Instance: In terms of predictive accuracy, MIMLSVM achieved an overall accuracy of 82.0%, significantly higher than the 73.9% achieved by Diverse Density and 71.1% by EM-DD.
  • Algorithm Comparison: MIMLSVM generally performed slightly better and more consistently than MIMLBOOST in the scene classification task.

Limitations and Future Work

  • Computational Efficiency: MIMLBOOST is computationally more expensive than standard boosting because it performs more operations per round to handle the bag-to-instance relationship.
  • Direct Solutions: The current algorithms rely on "bridges" (converting MIML to MI or ML). The authors note it remains an open question whether MIML can be tackled directly by exploiting the explicit connections between specific instances and specific labels (e.g., which specific patch in an image triggered the "trees" label).
  • Algorithm Expansion: The authors suggest developing MIML versions of other popular machine learning algorithms beyond boosting and SVMs.

Summary updated

Abstract

In this paper, we formalize multi-instance multi-label learning, where each train- ing example is associated with not only multiple instances but also multiple class labels. Such a problem can occur in many real-world tasks, e.g. an image usually contains multiple patches each of which can be described by a feature vector, and the image can belong to multiple categories since its semantics can be recognized in different ways. We analyze the relationship between multi-instance multi-label learning and the learning frameworks of traditional supervised learning, multi- instance learning and multi-label learning. Then, we propose the MIMLBOOST and MIMLSVM algorithms which achieve good performance in an application to scene classification.
BibTeX
@inproceedings{zhou2006multi,
  author = {Zhi-Hua Zhou and Min-Ling Zhang},
  title = {{Multi-Instance Multi-Label Learning with Application to Scene Classification}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=rGVBwNOnnQz},
}
Figure