Research map / Label-efficient and robust learning / Recognition and long-tail
Learning from Label Proportions: Bootstrapping Supervised Learners via Belief Propagation
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 an iterative LLP framework that uses sum-product belief propagation on a Gibbs distribution (bag-count and kNN label-similarity constraints) for pseudo labels, then trains an MLP with an aggregate embedding loss, and repeats with learned embeddings.
Problem
Learning from label proportions (LLP) for binary instance-level classification, where only bag-level label counts are available during training and the goal is accurate instance-level prediction on test data.
Approach
Casts LLP pseudo-labeling as a parity-recovery problem: a Gibbs distribution (Ising model) over instance labels enforces bag-count constraints and kNN label-smoothness, marginalized with sum-product belief propagation; an aggregate embedding loss (instance CE on thresholded pseudo labels plus bag-proportion head with average pooling) then refines embeddings, iterated over rounds.
Key results
- On Adult, Ours-Itr-2 reaches 84.95 AUROC at bag size 2048 vs 62.58 for DLLP, and 86.26 vs 84.49 for DLLP on Marketing at bag size 8.
- On Criteo (1M samples) at bag size 8, Ours-Itr-2 achieves 74.97 AUROC vs 74.11 for the best baseline DLLP.
- On CIFAR-S at bag size 512-1024, Ours-Itr-1 reaches 83.49 and 74.45 AUROC, outperforming DLLP by up to about 20 points at large bags.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Run a second BP and embedding-refinement iteration instead of stopping after one | Ours-Itr-1 · Adult, bag sizes 8, 32, 128, 1024, and 2048 | Test AUROC: 89.32 -> 89.47; 87.75 -> 87.82; 86.70 -> 86.87; 83.61 -> 83.88; 84.69 -> 84.95 | Helped |
| Run a second BP and embedding-refinement iteration instead of stopping after one | Ours-Itr-1 · Marketing, bag sizes 8, 32, 512, 1024, and 2048 | Test AUROC: 85.76 -> 86.26; 84.18 -> 84.23; 77.71 -> 81.68; 80.56 -> 81.66; 78.63 -> 81.01 | Helped |
| Run a second BP and embedding-refinement iteration | Ours-Itr-1 · Criteo, bag sizes 8, 32, and 128 | Test AUROC: 74.96 -> 74.97; 73.36 -> 73.43; 70.45 -> 70.81 | Mixed |
| Use 1-nearest-neighbor rather than a hyperparameter-selected higher k for BP covariate factors (ablation) | Proposed method · Multiple datasets | Test AUROC | No clear effect |
| Retain only 10% of the pairwise covariate-similarity constraints (ablation) | BP pseudo-labeling · Marketing | Test performance: 18% | Hurt |
| Add the bag-loss head to the aggregate embedding loss (ablation) | Proposed method · Multiple datasets and bag sizes | Instance-wise performance | Helped |
| Replace average pooling with Multi-Head-Attention pooling (ablation) | Aggregate embedding loss · Multiple datasets | Instance-wise performance | Hurt |
| Use soft BP labels (directly or as weights) rather than hard-thresholded labels (ablation) | Pseudo-label training · Multiple datasets and bag sizes | MLP AUC | No clear effect |
| Use cosine rather than L2 distance to construct the neighbor graph (ablation) | BP covariate-neighbor graph · Multiple datasets and bag sizes | Downstream performance | Helped |
| Use the Matern kernel rather than the RBF kernel for similarity (ablation) | BP covariate factors · Multiple datasets and bag sizes | Test AUC | Helped |
| Continue from iteration 2 to iteration 3 (ablation) | Proposed method · Adult and Marketing, bag sizes 8, 32, 128, and 512 | Test AUC: Adult: -0.29, -1.26, 0.49, 0.71; Marketing: -0.26, -0.94, -0.13, -1.05 | Mixed |
| Use Max Product BP rather than Sum Product BP (ablation) | BP pseudo-labeling · Adult and Marketing | Test AUC | Hurt |
Surprising findings
- Using only 1-nearest-neighbour constraints in the BP step recovers most of the performance of tuned larger k.
- MaxProduct BP (MAP decoding) gives noisy and inconsistent performance compared to sum-product marginalization.
Limitations
- BP could not be run on Criteo at large bag sizes due to integer-overflow issues in PGMax.
- Gains are not uniform: DLLP, GenBags or LLP-FC win in several settings, e.g. CIFAR-B at small bags and Criteo at bag size 128.
- Iterating beyond two rounds gives inconsistent gains, and hyperparameters are tuned extensively with Vizier on validation AUC.
Experimental setup
Datasets: Adult Bank Marketing Criteo CIFAR-10
Benchmarks: Adult Bank Marketing Criteo CIFAR-B CIFAR-S
Metrics: AUROC accuracy
Baselines: DLLP EasyLLP GenBags LLP-FC LLP-VAT
Builds on: DLLP Belief Propagation SimCLR PGMax
Closest papers by meaning
- Rethinking Learning from Label Proportions via Moment Matching (NeurIPS 2026 · similarity 0.91)
- Forming Auxiliary High-confident Instance-level Loss to Promote Learning from Label Proportions (CVPR 2025 · similarity 0.91)
- Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.88)
- L2B: Learning to Bootstrap Robust Models for Combating Label Noise (CVPR 2024 · similarity 0.87)
- Learning from Noisy Labels via Conditional Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.87)
- Predicting Label Distribution from Ternary Labels (NeurIPS 2024 · similarity 0.86)
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.