Multiple Instance Learning: A Survey of Problem Characteristics and Applications

1 Introduction

• MIL groups instances into bags and provides labels only for whole bags; weak supervision can reduce labeling effort compared with detailed local annotations.For example, object detectors can use web-image tags instead of locally annotated images.Source: §1 · p. 1
• Without formal definitions of key MIL characteristics, results are difficult to interpret, benchmark datasets may be inappropriate, and synthetic findings may not generalize to real data.Similar scenarios have also been described using different terms, such as “sparse bags” and “low witness rate.”Source: §1 · p. 2
• The paper organizes MIL problem characteristics into four categories: prediction level, bag composition, label ambiguity, and data distribution.These characteristics relate to instance-label ambiguity and the grouping of data into bags.Source: §1 · p. 2
• Experiments with 16 representative MIL algorithms found that instance classification, witness rate, and negative-class modeling considerably affect performance, with methods affected differently.The paper reports the first comparisons of algorithms on bag- and instance-classification tasks in light of these challenges.Source: §1 · p. 2
• The paper reviews methods addressing these challenges and examines MIL applications, identifying differences such as spatial relations among computer-vision instances that are absent in most bioinformatics applications.It aims to provide insights and directions for future research from the perspective of problem characteristics.Source: §1 · p. 2

2.1 Assumptions

• Standard MIL labels a bag positive if it contains at least one positive instance and negative if all instances are negative; collective assumptions use multiple instances to define bag labels.Under the standard assumption, a classifier need only find one witness in each positive bag; collective cases include beaches containing both sand and water segments and traffic jams requiring many cars.Source: §2.1 · p. 3

2.2 Tasks

• Bag and instance classification are distinct objectives, so bag-level performance does not indicate instance-level performance and some bag classifiers cannot classify instances.Their loss functions differ, and bag structure can affect loss.Source: §2.2 · p. 3
• MIL also supports assigning multiple labels to bags, which can contain instances representing different concepts.Multi-label classification is subject to the same problem characteristics as single-label classification.Source: §2.2 · p. 3
• MIL regression assigns real values to bags or instances, using a single instance, a combination of instances, or a bag-level regressor.Approaches include using the instance closest to a target concept, the best-fitting instance, or an average or weighted combination of instances [38–40].Source: §2.2 · p. 3
• MIL ranking compares bag or instance scores for sorting rather than predicting an exact real-valued label.Ranking can be performed at either the bag level or the instance level.Source: §2.2 · p. 4
• MIL clustering seeks structure among unlabeled bags, either in bag space with set-based distances or in instance space.Examples include k-Medoids with Hausdorff distance and clustering the most relevant instance from each bag; the paper focuses mainly on classification, while noting that its conclusions also apply to other tasks.Source: §2.2 · p. 4

3 Studies on MIL

• Existing surveys distinguish polymorphism from part-whole ambiguity and classify methods by instance- or bag-space representation; bag-space accuracy advantages remain data-, distance-, and embedding-dependent.The surveys also cover MIL algorithms, applications, learnability, and related tasks and methods.Source: §3 · p. 4
• Algorithm behavior also depends on assumptions and application: collective-assumption methods transfer to standard MIL data, dense image sampling and collective methods help image classification, and intra-bag similarity helps CAD bag classification [17] [3].Simple lazy-learning techniques also achieved results comparable to state-of-the-art techniques on some MIL problems.Source: §3 · pp. 4–5
• Datasets considered similar because of application or size can behave differently, suggesting that unobserved properties influence MIL algorithm performance.The study found dissimilarity between 2-D embeddings based on dataset meta-features and those based on MIL algorithm performance.Source: §3 · p. 4
• Bag- and instance-level performance correlate weakly: depending on the data, the best bag classifier can be average or worst at instance classification, and top bag performers need not yield stable instance labels.The relationship between bag- and instance-level performance was investigated analytically and experimentally; instance-label stability was studied separately.Source: §3 · pp. 4–5
• Few bags favor instance classifiers, whereas partial instance information about bag labels favors bag-level representations; supervised methods may also be competitive, and instance-count effects are mild.The preferred representation and method depend on the data and task; statistical performance is only mildly dependent on instances per bag.Source: §3 · pp. 4–5
• MIL performance depends on dataset properties; when instance combinations matter, bag-level or embedding methods perform better, while the best bag- and instance-level classifiers rarely coincide [15, 18, 20, 21, 23, 48].These differences motivate identifying MIL-specific characteristics and understanding their impact on algorithms.Source: §3 · p. 5

4 Characteristics of MIL Problems

• MIL problems are characterized by task, bag composition, data distributions, and label ambiguity, each posing challenges that require specific consideration.The survey discusses representative specialized methods for addressing these characteristics.Source: §4 · p. 5

4.1 Prediction: Instance-level vs. Bag-level

• Bag and instance classification are distinct objectives, so bag-classification performance often does not represent instance-classification performance.The relationship between their accuracies depends on the number of instances per bag, class imbalance, and instance-classifier accuracy.Source: §4.1 · p. 6
• Under the standard MIL assumption, identifying one positive witness suffices to label a bag positive, while other instance labels can be ignored for bag classification.False positives and false negatives may still count as instance-level errors.Source: §4.1 · p. 6
• In a negative bag, one false-positive instance causes bag misclassification, so 1% misclassified instances can mean 0% negative-bag accuracy despite 99% negative-instance accuracy.This difference in misclassification costs is illustrated by two decision boundaries that both classify bags perfectly, although only one classifies all instances correctly.Source: §4.1 · p. 6, Figure 2 · p. 6
• Bag-accuracy optimization can yield suboptimal instance boundaries; examples include APR, MI-SVM, MIL-Boost, EMDD, and MILD.False positives and false negatives that do not affect bag labels can still be errors at the instance level.Source: §4.1 · p. 6
• One proposed loss uses bag-level accuracy for positive bags but treats negative-bag instances individually, adjusting bag classifiers’ decision thresholds to improve instance accuracy.Another approach assigns different weights to false positives and false negatives during SVM optimization.Source: §4.1 · p. 7
• Methods that label instances independently, including mi-SVM and MissSVM, yielded the best instance-level classification results in the paper’s experiments.Ground-truth instance labels are scarce in benchmark data sets, complicating development and evaluation of instance-level classifiers.Source: §4.1 · pp. 6–7

4.2 Bag Composition Witness Rate

• Low witness rates can undermine MIL by making instance labels unlike bag labels, weakening pooled representations, and worsening instance-class imbalance.At very high witness rates, positive bags contain few negatives, so learning can instead be treated as supervised learning with one-sided noise.Source: §4.2 · p. 7
• Low-witness-rate methods modify optimization constraints or estimate witness rate, but a constant-rate assumption can limit estimation-based approaches.stMIL requires only one witness in positive bags and performs well at low but less efficiently at higher witness rates; sbMIL, ALP-SVM, SVR-SVM, and the γ-rule use witness-rate estimates.Source: §4.2 · p. 7
• CR-MILBoost and RSIS weight likely witnesses, while miGraph adjusts instance importance by clique size and miDoc performs well at very low witness rates.miGraph assumes positive and negative instances belong to different cliques; miDoc represents the MIL problem as a graph and compares bags through connecting edges.Source: §4.2 · p. 7

Relations Between Instances

• Real-world MIL often violates independent sampling because instances or bags are related through intra-bag similarities, co-occurrences, or structure.Intra-bag similarities can reflect shared molecule identity or image capture conditions, and can prevent transductive methods such as mi-SVM from inferring instance labels when negative instances differ across bags.Source: Relations Between Instances · pp. 7–8
• miGraph groups similar instances to adjust their importance, while CCE uses cluster-assignment vectors that remain robust when many instances share a cluster.CCE encodes whether at least one instance is assigned to each cluster, so additional instances assigned to the same cluster do not change the binary representation.Source: Relations Between Instances · p. 8
• Co-occurrences can aid bag classification and are modeled by distribution-based collective methods and tensor or multi-label models, but can raise false positives in instance classification.Co-occurrence can be necessary to distinguish beach images from sea or desert images; a positive instance paired with a negative one can cause the learner to label the negative instance positive.Source: Relations Between Instances · p. 9
• MIL structure may be spatial, temporal, relational, or causal; graph models represent relations among bags or instances, while zones and sequence models capture spatial and temporal dependencies.Examples include ordered video frames needed to distinguish taking from leaving a package, linked websites, zone-based bag-of-words representations, and CRF or HMM models.Source: Relations Between Instances · p. 9

Data Distributions

• Methods may implicitly assume particular distribution shapes or adequate training-set representation of the negative distribution, motivating study of overall-distribution challenges.Source: §4.3 · p. 9

Multimodal Distributions of Positive Instances

• APR, Diverse Density, CKMIL, and methods in and assume positive instances occupy a single cluster or region in feature space.APR searches for a hyper-rectangle separating positive- from negative-bag instances; Diverse Density finds a point close to positive-bag instances and far from negative-bag instances. CKMIL uses proximity to a single cluster center, while uses a sphere that includes at least one positive instance per positive bag and excludes negative-bag instances; uses a similar strategy.Source: Multimodal Distributions of Positive… · p. 9
• Image-classification concepts such as ants can span many feature-space clusters, so a compact single-cluster representation may fail to encompass their variation.Ant appearance varies with color, wings, body shape, species, caste, and viewpoint.Source: Multimodal Distributions of Positive… · p. 10, Figure 5 · p. 10
• The single-cluster assumption is reasonable for some applications, such as molecule classification, but problematic in contexts where positive concepts have multiple modes.Simple non-parametric methods can also produce competitive MIL results.Source: Multimodal Distributions of Positive… · p. 10
• Distance-based bag methods, prototype representations, kernel SVMs, vocabulary models, and mixture or cluster-composition models can represent disjoint or multiple positive clusters.Citation-kNN and MInD handle varied distribution shapes; DD-SVM and MILES represent clusters with prototypes; mi-SVM handles disjoint regions with a kernel. Vocabulary-based methods, the mixture model, and also model multiple modes or clusters.Source: Multimodal Distributions of Positive… · p. 10

Non-Representative Negative Distribution

• Training data may not represent the negative-instance distribution, which can vary widely across environments, unlike healthy tissue regions with a limited appearance range.The passage notes that learnability results require identical training and test distributions for instance concepts, a condition that may fail for negative instances.Source: Non-Representative Negative Distribution · p. 10
• Positive-concept methods classify by distance to a concept or region, treating sufficiently distant or outside instances as negative, so the negative distribution’s shape is unimportant.APR uses a hyper-rectangle; many other methods use one or more hyper-spheres or hyper-ellipses.Source: Non-Representative Negative Distribution · p. 10
• Citation-kNN uses distances to positive instances, while one-class SVM methods treat positive instances as the target class.Both approaches offer a way to handle differing negative distributions in test.Source: Non-Representative Negative Distribution · p. 11
• Experiments compare reference MIL algorithms when the negative distribution differs between training and test.Source: Non-Representative Negative Distribution · p. 11

4.4 Label Ambiguity

• Weak supervision inherently creates label ambiguity, with noise and mismatches between instance and bag labels adding further sources of ambiguity.Source: §4.4 · p. 11

Label Noise

• Under the standard MIL assumption, DD is vulnerable to a single negative instance near the positive concept, while a mislabeled positive bag can give APR a high FPR.Source: Label Noise · p. 11
• Positive instances can occur in negative bags through labeling errors or inherent data ambiguity, such as flowers in a house image or analogies in text.Source: Label Noise · p. 11
• Collective-assumption methods can tolerate noisy instances because a single positive instance does not determine a bag’s label.Distribution-based methods and NSK-kernel averaging reduce the effect of an isolated positive instance in a negative bag.Source: Label Noise · p. 11
• Threshold-based MI counts positive instances and classifies bags using a positive-instance threshold [17].Source: Label Noise · p. 11
• The method in combines thresholding with averaging the top- and bottom-ranked instances, mitigating the impact of positive instances in negative bags.Source: Label Noise · p. 11
• A MILES-like bag-embedding method gains noise robustness by clustering with dominant sets and selecting relevant instance prototypes.Source: Label Noise · p. 11

Different Label Spaces

• Negative images can contain patches inside the target zebra concept region, so those instances may lack clear semantic meaning despite falling within the positive concept.More broadly, bag and instance labels may differ in granularity, such as a car bag containing wheel, windshield, and headlight instances.Source: Different Label Spaces · p. 11, Figure 6 · p. 12
• When instances lack specific class labels, collective-assumption methods are necessary; vocabulary-based methods represent bags as distributions over words discovered from instance distributions.Words may be prototypes or clusters.Source: Different Label Spaces · p. 11
• Distance-based embeddings using selected prototype instances, including MILES and MILIS, can also handle instances with ambiguous labels.Source: Different Label Spaces · p. 12
• MIL problem characteristics require different approaches, and the paper next relates them to prominent application fields.Source: Different Label Spaces · p. 12

5.1 Biology and Chemistry

• Biology and chemistry use MIL because individual instance classes, such as binding strengths across a molecule’s conformations, may be unobservable while bag-level outcomes are available.Applications model compounds, molecules, or genes as bags to classify entities and sometimes identify witness instances; tasks include bioavailability, peptide binding, binding-site discovery, and gene-function prediction. DNA sequences can form structured bags, and some applications quantify outcomes rather than classify them.Source: §5.1 · pp. 12–13

Content Based Image Retrieval

• Content-based image retrieval treats image segments as instances and images as bags, primarily classifying images by the objects or concepts they contain.Dense grid sampling can produce correlated, similar instances, while semantic segmentation can reduce ambiguity; concept co-occurrence and collective-bag methods can help, and large appearance and background variability challenges unimodal models.Source: Content Based Image Retrieval · pp. 13–14

Object Localization and Segmentation

• Object localization uses weakly labeled images to train instance classifiers, often treating candidate bounding boxes as bag instances, unlike bag-level image retrieval.Weak labels can come from descriptions, search results, or tags, avoiding costly manual bounding boxes or pixel labels. Localization shares vision challenges such as correlated, structured instances, deformable objects, multimodal appearances, and sensitivity to initialization; some MIL methods also address pixel segmentation.Source: Object Localization and Segmentation · p. 14

Computer Aided Diagnosis and Detection

• In medical imaging, weak diagnosis labels enable MIL when detailed abnormality outlines are costly; bag classifiers can benefit from instance co-occurrence and structure.For tuberculosis in X-rays, a MIL classifier trained on image-level labels outperformed its supervised counterpart trained on lesion outlines; instance-level evaluation remains important but is often limited by missing ground truth. Medical tasks also vary in sampling, disease subtypes, patient and acquisition variability, and whether disease stages are treated as binary or continuous.Source: Computer Aided Diagnosis and Detection · pp. 14–15

5.3 Document Classification and Web Mining

• Text and web classification model documents, pages, and reviews as bags with instances ranging from words and passages to sentences, paragraphs, or linked pages.Applications include topic and sentiment classification, relation extraction, spam detection, recommendations, and contextual advertising. Bag-of-Words representations are sparse and high-dimensional, while context, co-occurrence, structure, low witness rates, and multimodal distributions pose challenges.Source: §5.3 · pp. 15–16

5.4 Other Applications

• Other MIL applications include reinforcement learning, audio recognition, wearable-sensor activity recognition, and hard-drive failure prediction, where weak labels apply to collections of instances.In reinforcement learning, successful episodes can reveal sub-goals, but bag structure and label noise matter; time-series instances are sub-periods or measurements, so their sequential structure should not be ignored.Source: §5.4 · pp. 16–17

Instance Space Methods

• Instance-space methods include approaches that assign bag labels to instances, iteratively update instance labels, or optimize a bag-level loss.SI-SVM discards bag information after assigning each instance its bag label; MI-SVM uses the most positive instance per bag while mi-SVM uses all instances, and MIL-Boost bases its loss on bag-classification error.Source: Instance Space Methods · pp. 17–18

Bag Space Methods

• Bag-space methods represent bags through distances, instance similarities, or instance-frequency histograms, then apply supervised classifiers.C-kNN uses minimal Hausdorff distance with two-level voting; MILES uses maximal similarities to selected prototypes, while BoW-SVM classifies bag histograms with an SVM.Source: Bag Space Methods · p. 18

6.2 Data Sets

• The instance-classification benchmarks span image, bird-song, and text data, with different sources of challenge across the sets.SIVAL images contain object segments and vary widely in witness rate; Birds recordings have low, nonconstant witness rates and sometimes imbalanced bag classes; Newsgroups uses sparse TFIDF features and averages 3.7% positive instances in positive bags.Source: §6.2 · p. 19

6.3 Instance-Level Classification

• For instance classification, mi-SVM and SI-SVM perform best on both metrics, while bag-accuracy-optimized methods can miss ambiguous positive instances.SI-SVM assigns each instance its bag’s label, and mi-SVM iteratively updates instance labels; SI-SVM corresponds to mi-SVM’s first iteration. Comparisons use UAR and F1-score over 58 problems.Source: §6.3 · pp. 20–21, Figure 7 · p. 20, Figure 8 · p. 20

6.4 Bag Composition: Witness Rate

• Lower witness rates reduce accuracy across methods, and performance on bag classification does not necessarily predict performance on instance classification.On Letters, bag-optimized methods can correctly classify a bag after detecting one positive letter while ignoring other positive concepts, yielding lower instance-classification accuracy despite comparable bag-classification accuracy.Source: Figure 9 · p. 21, Figure 10 · p. 21, Figure 11 · p. 22
• At witness rates above 50%, supervised classifiers are as effective as the best MIL classifiers for instance classification; at the lowest rate, MI-SVM has higher AUC than the other methods.At the minimum witness rate, each positive bag contains one witness, matching MI-SVM’s use of the single most positive instance.Source: §6.4 · p. 23
• Bag-level methods generally outperform instance-based methods for bag classification at witness rates of at least 50%, but the low-rate leader varies by data set.At 5–10% witness rates, the gap between approaches is smaller; MI-SVM leads on Letters, while EMD-SVM and NSK-SVM perform better on HEPMASS.Source: Figure 10 · p. 21, Figure 12 · p. 22, §6.4 · p. 23

6.5 Data Distribution: Non-Representative Negative Distribution

• Most algorithms lose performance as test negatives diverge from training negatives, but C-kNN improves; bag-level methods are generally better suited to new negative distributions.C-kNN’s minimal Hausdorff distance can make positive bags closer to one another when their positive instances share a distribution. For bag classification, stable AUC alongside falling accuracy suggests that adapting decision thresholds may help.Source: Figure 13 · p. 24, Figure 14 · p. 24, Figure 15 · p. 25

7.1 Benchmarks Data Sets

• When validating methods only on Musk and TEF, performance on different MIL problems is difficult to predict; estimated witness rates are 82–100% for Musk1, 23–90% for Musk2, and 38–100% for TEF.The authors recommend more diverse benchmarks and better understanding of MIL dataset characteristics.Source: §7.1 · pp. 26–27
• For computer vision, the authors recommend strongly annotated benchmarks with instance positions, enabling MIL comparisons with other techniques and evaluation of spatial structure.SIVAL supports co-occurrence evaluation and reduces background interference; Pascal VOC and ImageNet offer bounding-box or pixel-level annotations for creating instance labels.Source: §7.1 · pp. 26–27
• Beyond computer vision, real-world instance-labeled data and public MIL regression benchmarks are scarce, while semi-artificial benchmarks often fail to represent real data.The authors call for instance-labeling datasets, regression benchmarks, and clear justification of semi-artificial data assumptions; Table 3’s benchmark-characteristic estimates need rigorous investigation.Source: §7.1 · p. 27

7.2 Accuracy vs. AUC

• Because algorithms can rank well by AUC yet perform poorly by accuracy or UAR, the authors recommend reporting accuracy alongside AUC.When negative distributions change, AUC may remain stable while accuracy falls because the decision threshold becomes suboptimal; unknown instance labels and limited validation data can prevent threshold optimization.Source: §7.2 · pp. 27–28

7.3 Future Direction

• Future work should expand MIL regression and clustering and develop methods specifically for instance classification, supported by more instance-annotated datasets.Affective computing and pathology progression are suggested regression applications; approaches that discard or minimally use bag arrangement appear better suited to instance classification than methods designed for bag accuracy.Source: §7.3 · p. 28
• MIL research should address intra-bag similarity, exploit bag structure, and investigate class imbalance.Per-bag normalization may remove shared content; graph or subgraph representations could exploit ordered instance arrangements, while imbalance methods may require probabilistic labels or class-specific costs.Source: §7.3 · pp. 28–29
• Research should improve computational efficiency for instance-level methods and explore active learning and reliable external knowledge to handle MIL uncertainty.Active learning could query clinicians about critical instances; methods could estimate confidence or information gain, while giving strong labels more influence than weak labels.Source: §7.3 · p. 29
• The authors call for MIL representation learning and methods for bags containing instances from different feature spaces.Promising directions include supervised discriminative or mid-level feature learning and multiple instance clustering, as well as multimodal fusion through shared semantic spaces, graphs, or paired instances.Source: §7.3 · p. 29

• Experiments with 16 methods show that MIL problem characteristics substantially affect performance, with each method behaving differently across characteristics.The survey argues that careful problem characterization is essential when evaluating experiments and proposing new methods.Source: §8 · p. 30
• For instance classification, high WR permits ordinary supervised learning with one-sided noise, and the best approaches use little or no bag information.Methods optimized for bag classification accuracy have higher false negative rates as WR increases, limiting performance on instance classification.Source: §8 · p. 30
• Bag-level methods and methods assuming instances inherit their bag label yield better classification performance, especially at high WR.Source: §8 · p. 30
• Bag-space methods are more robust than instance-space methods when training data cannot fully represent the negative distribution, particularly with minimal Hausdorff distance.Source: §8 · p. 30
• AUC alone can mislead because algorithms may learn accurate score functions but fail to optimize the decision threshold, yielding low accuracy.Source: §8 · p. 30
• The paper recommends broader, problem-characteristic-matched benchmarks and further work on underexplored MIL tasks and data challenges.It calls for benchmarks beyond Musk and Tiger, Elephant and Fox; more MIL regression and clustering, including for affective computing; methods leveraging instance structure for IoT time series; and efficient methods for large, multimodal, imbalanced data.Source: §8 · p. 30