Research map / Learning theory and algorithms / Combinatorial and search optimization
Are Multiple Instance Learning Algorithms Learnable for Instances?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a PAC-learning-based theoretical framework for deciding whether Deep MIL algorithms are learnable at the instance level, derives conditions per pooling type, and checks them on synthetic MNIST and WebTraffic experiments.
Problem
Existing MIL theory only addresses bag-level learnability, leaving unclear whether a given deep MIL algorithm can also learn to predict individual instance labels from bag labels.
Approach
Defines instance-level PAC learnability and a necessary and sufficient condition (risk of bag optimum equals sum, or weighted sum, of per-instance optima) under independent and general bag domains, then classifies deep MIL pooling types (instance, embedding, attention, additive, conjunctive) by whether they satisfy it.
Key results
- Attention-pooling and additive-pooling MIL show large instance-level drops versus bag-level (e.g., Attention MIL Macro-F1 bag 0.8434 vs instance 0.3215), while Conjunctive MIL has a much smaller gap (0.7916 vs 0.6430 Macro-F1; AUROC 0.9463 vs 0.9516).
- On WebTraffic, positional encoding or RNN added to features for prediction degrades instance-level NDCG (Default 0.676 vs PE (All) 0.665 and RNN (All) 0.642), whereas positional information used only in attention (PE (Att) 0.727) improves it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Conjunctive-Pooling instead of feature-level Attention-Pooling | Deep MIL · Synthetic instances | Macro-F1: 0.3215 -> 0.6430 | Helped |
| Use Conjunctive-Pooling instead of feature-level Attention-Pooling | Deep MIL · Synthetic instances | AUROC: 0.7317 -> 0.9516 | Helped |
| Apply positional encoding to features for attention and prediction (ablation) | Conjunctive MIL · WebTraffic test | AOPCR: 13.041 -> 12.372 | Hurt |
| Apply positional encoding to features for attention and prediction (ablation) | Conjunctive MIL · WebTraffic test | NDCG@n: 0.676 -> 0.665 | Hurt |
| Use positional information only for attention (ablation) | Conjunctive MIL · WebTraffic test | AOPCR: 13.041 -> 14.555 | Helped |
| Use positional information only for attention (ablation) | Conjunctive MIL · WebTraffic test | NDCG@n: 0.676 -> 0.727 | Helped |
| Use positional information only for prediction (ablation) | Conjunctive MIL · WebTraffic test | AOPCR: 13.041 -> 12.256 | Hurt |
| Use positional information only for prediction (ablation) | Conjunctive MIL · WebTraffic test | NDCG@n: 0.676 -> 0.642 | Hurt |
| Use GRU-extracted features for attention and prediction (ablation) | Conjunctive MIL · WebTraffic test | AOPCR: 13.041 -> 9.011 | Hurt |
| Use GRU-extracted features for attention and prediction (ablation) | Conjunctive MIL · WebTraffic test | NDCG@n: 0.676 -> 0.620 | Hurt |
| Use GRU positional information only for attention (ablation) | Conjunctive MIL · WebTraffic test | AOPCR: 13.041 -> 17.502 | Helped |
| Use GRU positional information only for attention (ablation) | Conjunctive MIL · WebTraffic test | NDCG@n: 0.676 -> 0.714 | Helped |
Surprising findings
- Javed et al.'s additive-pooling learnability result is argued to contain an error, and similar errors are claimed in conjunctive-pooling works (MILNET, MILLET).
- Positional encoding or RNN features improve bag prediction in prior work but harm instance-level prediction according to the experiments.
Limitations
- Theoretical results assume bag-level PAC learnability (Assumption 1) rather than proving it.
- Empirical validation is limited to synthetic MNIST-based bags and one synthetic time-series dataset.
Experimental setup
Datasets: MNIST WebTraffic
Benchmarks: MNIST-based synthetic bags WebTraffic
Metrics: Macro-F1 Micro-F1 Weighted-F1 AUROC AOPCR NDCG@n
Baselines: mi-Net Causal MIL MIREL Attention MIL Loss-Attention SA-AbMILP TransMIL Additive MIL Conjunctive MIL
Builds on: PAC learning Deep MIL Causal MIL MILLET
Closest papers by meaning
- Loss-Based Attention for Deep Multiple Instance Learning (AAAI 2020 · similarity 0.88)
- Attention-based Deep Multiple Instance Learning (ICML 2018 · similarity 0.87)
- Model Agnostic Interpretability for Multiple Instance Learning (ICLR 2022 · similarity 0.87)
- Multiple Instance Verification (NeurIPS 2026 · similarity 0.84)
- Sm: enhanced localization in Multiple Instance Learning for medical imaging classification (NeurIPS 2024 · similarity 0.83)
- Incorporating probabilistic domain knowledge into deep multiple instance learning (ICML 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.