Research map / Learning theory and algorithms / Combinatorial and search optimization
A General Framework for Learning from Weak Supervision
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 GLWS, a unified EM framework that models arbitrary weak supervision as an NFA and solves the complete EM in linear time via forward-backward, evaluated on 11 weak supervision settings.
Problem
Weakly supervised learning methods are specialized per weak supervision type and scale poorly (quadratic or factorial complexity, or conditional-independence simplifications) on long sequences and aggregate observations.
Approach
Treat the latent precise labels as a sequence, model any weak supervision as a non-deterministic finite automaton whose accepted labelings are the valid ones, and compute the complete EM objective with a forward-backward pass over the NFA-by-prediction trellis in linear time.
Key results
- On partial label learning, GLWS reaches 82.66% on ImageNet-100 (ratio 0.01), beating RCR (81.52%), and 94.31% on CIFAR-10 at ratio 0.5.
- On MultiIns with multi-class labels, GLWS improves over Count Loss by 12.93% on CIFAR-100 (N(10,2) bags is reported as 52.29 vs 30.66 for N(20,5)-style settings in the main table).
- On CIFAR-100 pairwise comparison, GLWS improves the previous best by 10.23% and on similarity confidence by 14.03%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GLWS instead of RCR for partial-label learning | Partial-label classification · ImageNet-100 | accuracy: 81.52 -> 82.66 | Helped |
| Use GLWS instead of Count Loss for multiple-instance learning | MultiIns · CIFAR-100, N(5,1) | accuracy: 52.04 -> 56.28 | Helped |
| Use GLWS instead of Count Loss for label-proportion learning | LProp · CIFAR-100, N(5,1) | accuracy: 54.13 -> 58.25 | Helped |
| Use GLWS instead of Rank Pruning for pairwise comparison | PComp · CIFAR-100, prior 0.8 | accuracy: 71.51 -> 80.50 | Helped |
| Use GLWS instead of the strongest reported baseline for positive-unlabeled learning | PosUlb · CIFAR-10, 500 positive examples | accuracy: 88.65 -> 91.67 | Helped |
| Use GLWS instead of Count Loss for binary MultiIns learning | MultiIns · MNIST and F-MNIST | accuracy | No clear effect |
| Use GLWS instead of Count Loss for aggregate observations | MultiIns and LProp · MNIST and F-MNIST | accuracy | Mixed |
| Use GLWS forward-backward NFA computation instead of quadratic Count Loss computation | Aggregate observations · Long sequences | runtime: quadratic -> linear | Helped |
Surprising findings
- The UUM baseline collapses to near chance (about 1% accuracy) on several MultiIns settings in the main table, showing oversimplified conditional-independence modeling fails on larger bags.
Limitations
- Experiments are limited to image classification benchmarks with synthetically generated weak supervision.
- Noisy weak supervision with a learnable noise model is left for future work.
- Binary NFA modeling is used for multi-class aggregate observations via one-vs-rest, which is an approximation of the complete EM.
Experimental setup
Datasets: CIFAR-10 CIFAR-100 STL-10 ImageNet-100 MNIST Fashion-MNIST
Benchmarks: CIFAR-10 CIFAR-100 STL-10 ImageNet-100 MNIST Fashion-MNIST
Metrics: accuracy runtime per iteration
Baselines: CC LWS PRODEN PiCO RCR Count Loss UUM LLP-VAT PComp Rank Pruning RiskSD CVIR
Builds on: expectation-maximization non-deterministic finite automaton universal unbiased method (UUM) count loss
Closest papers by meaning
- Universalizing Weak Supervision (ICLR 2022 · similarity 0.89)
- Training Subset Selection for Weak Supervision (NeurIPS 2022 · similarity 0.89)
- Training Complex Models with Multi-Task Weak Supervision (AAAI 2019 · similarity 0.89)
- Characterizing the Impacts of Semi-supervised Learning for Weak Supervision (NeurIPS 2023 · similarity 0.88)
- Weak Supervision Performance Evaluation via Partial Identification (NeurIPS 2024 · similarity 0.88)
- A Unified Framework for Generalization Error Analysis of Learning with Arbitrary Discrete Weak Features (ICML 2025 · 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.