PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiple Instance Learning: A Survey of Problem Characteristics and Applications

Marc-André Carbonneau, Veronika Cheplygina, Eric Granger, Ghyslain Gagnon

arXiv:1612.03365v1cs.CVcs.AIcs.IR

TL;DR

MIL uses bag-level supervision while leaving instance labels ambiguous, creating distinctive problem characteristics that affect algorithm behavior. This paper surveys those characteristics and shows that they inform experiment interpretation and method selection, including robustness differences and evaluation trade-offs.

  • Problem

    MIL provides supervision for bags without labels for their individual instances, making its characteristic challenges important to understand.

  • Method

    The paper surveys MIL problem characteristics, organizes them into four categories, and reviews their effects on algorithms across applications.

  • Results

    The survey identifies four characteristic types that dictate MIL algorithm behavior, including greater robustness of bag-space methods when negative distributions are incompletely represented.

  • Takeaways & Limitations

    Understanding MIL characteristics can help interpret experimental results and guide improved methods, while evaluation should not rely on AUC alone.

  • Takeaways & Limitations

    Public real-world MIL datasets are scarce, with few providing instance labels and no publicly available benchmark dataset for MIL regression.

Abstract

from arXiv · show

Multiple instance learning (MIL) is a form of weakly supervised learning where training instances are arranged in sets, called bags, and a label is provided for the entire bag. This formulation is gaining interest because it naturally fits various problems and allows to leverage weakly labeled data. Consequently, it has been used in diverse application fields such as computer vision and document classification. However, learning from bags raises important challenges that are unique to MIL. This paper provides a comprehensive survey of the characteristics which define and differentiate the types of MIL problems. Until now, these problem characteristics have not been formally identified and described. As a result, the variations in performance of MIL algorithms from one data set to another are difficult to explain. In this paper, MIL problem characteristics are grouped into four broad categories: the composition of the bags, the types of data distribution, the ambiguity of instance labels, and the task to be performed. Methods specialized to address each category are reviewed. Then, the extent to which these characteristics manifest themselves in key MIL application areas are described. Finally, experiments are conducted to compare the performance of 16 state-of-the-art MIL methods on selected problem characteristics. This paper provides insight on how the problem characteristics affect MIL algorithms, recommendations for future benchmarking and promising avenues for research.

1 Introduction

MIL organizes training instances into bags with labels only for entire bags, reducing annotation demands while introducing distinctive challenges. This paper formalizes those challenges into four categories and reviews methods, applications, and experimental effects.

  • Motivation: MIL provides labels for entire bags rather than individual instances, making it suitable for weakly labeled data and reducing labeling effort.Weak supervision can support applications such as object detection and computer-aided diagnosis without costly local annotations.
  • Research gap: The literature had not formally defined key MIL problem characteristics, making algorithm performance across data sets difficult to explain.This limited understanding also complicates benchmark selection and interpretation of synthetic-data results.
  • Problem characteristics: MIL performance depends on bag composition, data distribution, label ambiguity, and the prediction task.These characteristics arise from grouping data into bags and from ambiguity in instance labels.
  • Contributions: The paper reviews specialized methods, analyzes applications, and compares 16 representative MIL algorithms under selected problem characteristics.The experiments examine instance classification, witness rate, and negative-class modeling.

2 Multiple Instance Learning

MIL assigns supervision to bags while supporting classification, regression, ranking, and clustering at bag or instance level. Its assumptions determine how instance evidence combines into bag labels.

  • Assumptions: Under the standard MIL assumption, negative bags contain only negative instances, while each positive bag contains at least one positive witness.Bag labels are positive when at least one instance is positive and negative when all instances are negative.
  • Assumptions: The collective assumption allows bag labels to depend on interactions or accumulations of multiple positive instances.Examples include beach images requiring sand and water segments and traffic jams requiring many cars.
  • Tasks: Classification can target bags or individual instances, and performance at one level is not representative of performance at the other.Bag-level loss may ignore instance errors that still matter for instance classification.
  • Tasks: MIL also includes multi-label classification, regression, ranking, and clustering tasks.These tasks assign multiple labels, real values, orderings, or structures to bags or instances.
  • Scope: Classification receives most of the paper’s discussion, although its problem-characteristic conclusions also apply to other tasks.The survey treats classification as the most studied MIL task.

3 Studies on MIL

Prior MIL studies consistently show that algorithm performance depends on data-set properties and differs across tasks and applications. This survey consolidates those findings around problem characteristics.

  • Prior surveys: Earlier surveys organized MIL methods by assumptions, ambiguity types, or representation space, with bag-level performance depending on data and distance functions.The literature includes technical surveys, taxonomies, and comparative experiments across application fields.
  • Task dependence: The best bag classifier is rarely the best instance classifier, and the preferred representation can change when the number of bags is low.Some studies report that instance-based methods are preferable with few bags.
  • General findings: Studies found that MIL algorithm performance depends on data-set properties and that some MIL problems can also be addressed with standard supervised methods.The best approach is application-dependent rather than universally fixed.
  • General findings: When bag labels depend on combinations of instances, bag-level and embedding methods perform better.This conclusion concerns problems where multiple instances jointly provide the relevant evidence.
  • Synthesis: The survey identifies understanding MIL-specific characteristics as an important step toward advancing MIL research.These characteristics organize the differing conclusions reported across earlier studies.

4 Characteristics of MIL Problems

MIL problems are defined by four characteristics that shape algorithm behavior: task, bag composition, data distributions, and label ambiguity. Prediction level illustrates why bag- and instance-level performance can diverge.

  • Four characteristics: The four MIL characteristic categories are task, bag composition, data distributions, and label ambiguity.Each category poses distinct challenges requiring targeted treatment.
  • Prediction level: Bag-level accuracy is often unrepresentative of instance-level accuracy, with the relationship depending on bag size, class imbalance, and instance-classifier accuracy.Algorithms optimized for bag classification are therefore not necessarily optimal for instance classification.
  • Prediction level: Bag classification can remain perfect despite instance errors because false positives and false negatives may not affect bag labels.Under standard MIL, finding one witness can suffice for a positive bag, while a single false positive can misclassify a negative bag.
  • Prediction level: Loss functions and decision thresholds may need to distinguish positive- and negative-bag treatment when optimizing instance classification.One proposed criterion evaluates positive bags at bag level but treats negative-bag instances individually.

4.2 Bag Composition

Bag composition encompasses witness rate and relationships among instances, including similarity, co-occurrence, and structure. These properties create distinct challenges for bag- and instance-level prediction.

  • Witness Rate: The witness rate is the proportion of positive instances in positive bags, and very low values can hinder many MIL algorithms.Low witness rates weaken methods that equate instance and bag labels or pool instance contributions equally.
  • Witness Rate: Sparse transductive MIL modifies SVM constraints to require at least one witness in positive bags, improving performance at low witness rates but reducing efficiency at higher rates.
  • Relations Between Instances: Intra-bag similarities arise when instances within a bag share properties that distinguish them from instances in other bags.Examples include molecular conformations and overlapping image patches.
  • Relations Between Instances: Instance co-occurrence can provide useful semantic context, but in instance classification it may confuse the learner and increase false positive rates.Distribution-based, tensor, and multi-label methods model co-occurrence directly or indirectly.
  • Relations Between Instances: Instance and bag structure may be spatial, temporal, relational, or causal, and modeling it can improve classification performance.Graphs and sequence models are among the approaches used to capture such relations.

4.3 Data Distributions

MIL algorithms make assumptions about distribution shapes and how well training data represent the negative distribution. This section studies challenges arising from the overall data distribution.

  • Data Distributions: MIL methods often assume particular distribution shapes or adequate representation of the negative distribution in training data.

Multimodal Distributions of Positive Instances

Some MIL methods assume that positive instances occupy one cluster or region in feature space. This assumption can fail when a concept has multiple modes, such as ants varying in appearance and pose.

  • Single-Cluster Assumption: Single-cluster methods locate a compact positive region using strategies such as hyper-rectangles, cluster centers, or enclosing spheres.APR, Diverse Density, CKMIL, and related methods follow this assumption.
  • Single-Cluster Assumption: A single compact region may be unsuitable for image concepts with variations in color, wings, body shape, species, caste, and viewpoint.
  • Multimodal Methods: Non-parametric bag-distance methods and prototype-based representations can model multimodal positive concepts.Examples include Citation-kNN, MInD, DD-SVM, and MILES.

Non-Representative Negative Distribution

In some applications, the negative instance distribution in test data is not fully represented by training data. Methods that model the positive class can address this setting by relying on positive concepts or instances.

  • Distribution Shift: Learning an instance concept requires identical training and test distributions, but training data may not fully represent the negative instance distribution.
  • Positive-Class Modeling: Positive-class methods model regions around positive concepts or instances, avoiding reliance on a fully represented negative distribution.Approaches include hyper-rectangles, hyper-spheres, hyper-ellipses, distance-based methods, and one-class SVMs.
  • Evaluation: Experiments compare reference MIL algorithms when the negative distribution differs between training and test data.

4.4 Label Ambiguity

Label ambiguity in MIL arises from weak supervision, noisy labels, and instances whose labels differ from their bags. These sources can make standard MIL methods sensitive to mislabeled instances or bags.

  • Label ambiguity is inherent to weak supervision and can also arise from label noise or instance labels differing from bag labels.
  • A single negative instance near the positive concept can hinder DD performance under noisy labels.
  • A positive-labeled bag containing mislabeled negatives can lead APR to a high false-positive rate.
  • Positive instances may occur in negative bags because labeling errors can be inherent, such as flowers appearing in images labeled as houses.
  • Collective methods can tolerate noisy instances better because individual positive instances have less influence on bag representations.

Different Label Spaces

MIL may use different label spaces for bags and instances, including different granularity levels or semantically unclear instance labels. These settings favor collective representations over methods that must identify positive instances.

  • Bag and instance labels may differ in granularity, such as a car bag containing wheels, windshields, and headlights.
  • Instance labels may lack clear semantic meanings, as illustrated by patches inside a zebra concept region.
  • When instances cannot be assigned to specific classes, standard MIL methods that identify positive instances are inadequate.
  • Vocabulary-based methods represent bags as distributions over words discovered from instance prototypes or clusters.
  • Prototype-distance embeddings, including MILES and MILIS, can also address instances without clear class labels.
  • MIL problem characteristics define varied problems that must be addressed differently.

5 Applications

MIL applications span biology, chemistry, computer vision, medical imaging, and document classification because entities naturally form bags or only weak annotations are available. Each field exhibits distinct task, distribution, composition, and label challenges.

  • MIL is used when instances naturally form sets or when weakly annotated data must be leveraged.
  • The survey examines application fields according to their MIL problem characteristics.
  • Biology and Chemistry: Biology and chemistry naturally fit MIL because individual instance classes, such as molecular conformation binding strengths, are unobservable.
  • Biology and Chemistry: Chemical and biological entities are modeled as bags whose parts may induce an effect, with goals including bag classification and witness identification.
  • Computer Vision: Computer vision uses MIL to characterize visual concepts from sub-concepts and to learn from weakly annotated images.
  • Computer Vision: CBIR primarily performs bag classification, while object localization classifies candidate image regions as instances.
  • Object Localization and Segmentation: Object localization faces correlated, spatially structured, multimodal instances and sensitivity to initialization, unlike CBIR's bag-level focus.
  • Computer Aided Diagnosis and Detection: In medical imaging, a MIL classifier trained only on healthy or tuberculosis-labeled X-rays outperformed a supervised version trained on lesion outlines.

6 Experiments

Experiments compare 16 MIL reference methods to examine how prediction level, witness rate, and negative-class distribution influence algorithm behavior. Results show that the preferable strategy depends strongly on the task and data characteristics.

  • Experimental design: The experiments compare 16 reference methods across selected characteristics to assess how MIL problem properties influence algorithm behavior.The selected characteristics represent different categories discussed in the survey.
  • Instance-level classification: For instance classification, mi-SVM and SI-SVM perform best on both UAR and F1-score by assigning each instance its bag label and treating instances as atomic elements.SI-kNN is also competitive, while methods optimized for bag accuracy perform worse on this task.
  • Witness rate: Lower witness rates reduce accuracy for all methods, but higher witness rates do not necessarily improve instance-classification accuracy when positive instances are multimodal.Bag-optimized methods can ignore some positive modes while retaining strong bag-classification performance, producing lower instance accuracy.
  • Witness rate: For bag classification, bag-level methods generally outperform instance-based methods at witness rates of at least 50%, whereas differences narrow around 5–10%.At low witness rates, method choice also depends on positive and negative distribution shapes and witness-rate consistency across positive bags.
  • Negative distribution shift: When test negative-instance distributions differ from training, most algorithms lose performance, whereas C-kNN improves because minimal Hausdorff distance favors similarity among positive bags.Bag-level methods are suggested to be better suited to new negative distributions, and stable AUC with declining accuracy suggests threshold adaptation may help.

7 Discussion

The discussion argues that MIL progress depends on matching benchmarks and evaluation practices to problem characteristics, while highlighting underexplored tasks and modeling opportunities.

  • Benchmarks: Computer-vision benchmarks should provide stronger annotations and instance positions to evaluate instance labeling and methods that exploit spatial structure.SIVAL enables co-occurrence analysis, while datasets such as Pascal VOC and ImageNet offer bounding-box or pixel-level annotations.
  • Benchmarks: Real-world MIL datasets with instance labels are scarce outside computer vision, and publicly available benchmarks for MIL regression are absent.The paper links this scarcity to MIL’s usual goal of avoiding labor-intensive instance annotation.
  • Benchmarks: Semi-artificial datasets help isolate individual parameters but are generally unrepresentative because their instances are usually i.i.d.Authors should state their assumptions and explain how these datasets differ from real data.
  • Benchmarks: Using only Musk and TEF benchmarks makes it difficult to predict performance across different MIL problems and may prematurely dismiss promising models.These datasets cover only some MIL challenges and can favor methods optimized for their specific characteristics.
  • Evaluation: AUC should be reported alongside accuracy because some algorithms achieve high AUC without accurately setting the threshold needed for hard labels.The paper attributes contrasting metrics partly to differences between optimizing bag accuracy and inferring instance labels, which create asymmetric false-positive and false-negative tendencies.
  • Research avenues: Future work should expand MIL regression and clustering, develop methods for instance classification, and address intra-bag similarity, structure, imbalance, and uncertainty.Suggested directions include bag normalization, graph representations, probabilistic labels for imbalance methods, and active learning queries.
  • Research avenues: Representation learning is an emerging direction because existing MIL methods usually treat features as immutable problem parameters and focus on classification or regression.The discussion notes supervised feature learning and deep-learning fine-tuning as recent approaches.

8 Conclusion

The conclusion finds that MIL problem characteristics materially affect algorithm performance and should guide experimentation, benchmark selection, and future research. Experiments with 16 methods support task- and characteristic-specific recommendations, including broader evaluation than traditional benchmarks.

  • Conclusion: Four types of characteristics define MIL problems and influence algorithm behavior: prediction level, bag composition, label ambiguity, and data distribution.The survey connects these characteristics to MIL’s grouped data and ambiguous instance labels.
  • Conclusion: Experiments with 16 methods showed that problem characteristics have an important impact on performance and that methods behave differently across problems.The authors therefore recommend careful characterization when evaluating or proposing MIL methods.
  • Experimental conclusions: When witness rate is relatively high in instance classification, the task can be formulated as supervised learning with one-sided noise.The conclusion states that MIL algorithms are unnecessary in this setting.
  • Experimental conclusions: For instance classification, the best approaches use little or no bag information, while bag-accuracy objectives produce higher false-negative rates as witness rate increases.The latter effect limits performance on the instance-classification task.
  • Experimental conclusions: Bag-level methods and methods assuming instances inherit their bag label perform better, especially when witness rate is high.
  • Experimental conclusions: Bag-space methods are more robust than instance-space methods when training data cannot completely represent the negative distribution.This was particularly true with the minimal Hausdorff distance.
  • Experimental conclusions: Measuring performance only with AUC is misleading because accurate score functions can still yield low accuracy when decision thresholds are poorly optimized.
  • Future research: MIL evaluation should use more benchmark datasets selected according to the characteristics of the target problem, while regression and clustering remain underexplored.
Loading 1612.03365v1…