Research map / Learning theory and algorithms / Prediction and decision losses
Probably Approximately Precision and Recall Learning
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.
Introduces a PAC framework for learning set-valued hypotheses (precision and recall) from positive-only, one-random-label-per-input data, showing ERM fails and giving realizable and agnostic algorithms with theoretical guarantees.
Problem
Learning set-valued functions for multi-label-style tasks where only one randomly sampled positive label per input is observed, so precision loss cannot be estimated directly and ERM fails; the goal is to guarantee both precision and recall.
Approach
Defines a PAC model where hypotheses are set functions evaluated by counting-based precision and recall losses, learns from positive examples only, and uses a maximum-likelihood rule (minimum sum of log output sizes among consistent hypotheses) plus a surrogate distance over counterfactual label distributions to control precision.
Key results
- Realizable setting: maximum likelihood and surrogate-loss algorithms achieve precision and recall losses at most epsilon with sample size O(log(|H|/delta)/epsilon).
- Agnostic setting: additive error is impossible; surrogate-loss method achieves scalar loss within factor 5 of optimal, i.e. (p,r) => (5(p+r), r), with a lower bound of 1.05 for scalar loss.
- Pareto lower bound: with (p,r)=(7/16,1/4), output must have recall loss above 1/4 or precision loss at least 23/48, so (7/16,1/4) does not imply (7/16+0.01, 1/4+0.01).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use maximum likelihood to select a consistent hypothesis with minimum summed log output size | Set-function learning from positive-only feedback · Realizable setting | precision loss: \lp(g^{\text{output}}) \leq \varepsilon | Helped |
| Use maximum likelihood to select a consistent hypothesis with minimum summed log output size | Set-function learning from positive-only feedback · Realizable setting | recall loss: \lr( g^{\text{output}}) \leq \varepsilon | Helped |
| Minimize the surrogate metric between the observed hypothesis and candidate hypotheses | Set-function learning from positive-only feedback · Realizable setting | scalar loss: d_\mathcal{H}(g^{\text{target}},g)\leq 2\ls(g) \leq 4 d_\mathcal{H}(g^{\text{target}},g) + 2\min_{g'\in \mathcal{H}}\ls( | Helped |
| Use the surrogate loss to select a hypothesis | Set-function learning from positive-only feedback · Agnostic setting | scalar loss: \ls( g^{\text{output}}) \leq 5\cdot \min_{g\in \mathcal{H}} \ls(g)+\varepsilon | Helped |
| Replace ordinary maximum likelihood with recall filtering and log truncated output-size regulation | Set-function learning from positive-only feedback · Agnostic setting | precision loss: \lp(g^{\text{output}})\leq 28r+15p+ \varepsilon | Helped |
| Attempt additive-error learning in the agnostic setting | Any algorithm over the paper's two-hypothesis class · Agnostic setting | scalar loss: \EE{\ls(g^{\text{output}})}\geq 1.05\cdot \min_{g\in\mathcal{H}}(\ls(g)) | Hurt |
| Use the estimable gap to distinguish zero-precision-loss hypotheses | Set-function learning with a zero-precision-loss comparator · Semi-realizable setting | precision loss: \lp(g^{\text{output}})=0 | Helped |
Surprising findings
- ERM fails: a complete set function is consistent with all positive-only training data yet has high precision loss.
- Additive-error guarantees for precision and recall are impossible in the agnostic positive-only setting.
Limitations
- Only finite hypothesis classes are studied; infinite classes and VC-style dimensions are left open.
- Gap between upper bound (factor 5) and lower bound (1.05) on the optimal scalar-loss approximation factor remains open.
- Analysis restricted to the counting-measure definition of precision and recall; no experiments.
Experimental setup
Metrics: precision loss recall loss scalar loss (average of precision and recall losses)
Baselines: Empirical Risk Minimization
Builds on: PAC learning empirical risk minimization maximum likelihood estimation
Closest papers by meaning
- Online Set Learning from Precision and Recall Feedback (NeurIPS 2026 · similarity 0.88)
- Nearly Optimal Sample Complexity for Learning with Label Proportions (ICML 2025 · similarity 0.87)
- CGMatch: A Different Perspective of Semi-supervised Learning (CVPR 2025 · similarity 0.86)
- Rethinking Learning from Label Proportions via Moment Matching (NeurIPS 2026 · similarity 0.85)
- Imprecise Label Learning: A Unified Framework for Learning with Various Imprecise Label Configurations (NeurIPS 2024 · similarity 0.85)
- Enhanced Sample Selection with Confidence Tracking: Identifying Correctly Labeled Yet Hard-to-Learn Samples in Noisy Data (AAAI 2025 · similarity 0.85)
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.