Source-linked AI summary
Theoretical Comparisons of Positive-Unlabeled Learning against Positive-Negative Learning
Gang Niu, Marthinus Christoffel du Plessis, Tomoya Sakai, Yao Ma, Masashi Sugiyama
TL;DR
PU learning can sometimes outperform PN learning, but the conditions explaining this phenomenon had not been established. The paper compares PN, PU, and NU estimation-error bounds and finds that either PU or NU can improve on PN when U data grows sufficiently faster than labeled data.
Problem
The paper asks when PU learning can outperform PN learning despite lacking negative data, addressing an open theoretical and experimental question.
Method
The paper establishes and compares estimation-error bounds for risk minimizers in PN, PU, and NU learning using statistical learning theory.
Results
Either PU or NU has a tighter asymptotic bound than PN when U data grows faster than P and N data, and the findings agree with experiments on artificial and benchmark data.
Takeaways & Limitations
The comparison yields simple conditions, based on the class prior and sample sizes, for when PU or NU may outperform PN.
Takeaways & Limitations
The theoretical comparisons assume a mild condition on the function class and data distributions, with the class-prior probability π treated as known.
Abstract
from arXiv · showhide
In PU learning, a binary classifier is trained from positive (P) and unlabeled (U) data without negative (N) data. Although N data is missing, it sometimes outperforms PN learning (i.e., ordinary supervised learning). Hitherto, neither theoretical nor experimental analysis has been given to explain this phenomenon. In this paper, we theoretically compare PU (and NU) learning against PN learning based on the upper bounds on estimation errors. We find simple conditions when PU and NU learning are likely to outperform PN learning, and we prove that, in terms of the upper bounds, either PU or NU learning (depending on the class-prior probability and the sizes of P and N data) given infinite U data will improve on PN learning. Our theoretical findings well agree with the experimental results on artificial and benchmark data even when the experimental setup does not match the theoretical assumptions exactly.
1 Introduction
The paper addresses when PU learning can outperform PN learning despite lacking negative data. It compares risk bounds for PN, PU, and NU learning and derives finite-sample and asymptotic conditions favoring PU or NU.
- Problem settings: The study focuses on the two-sample PU setting, where independent P and U samples are drawn from the positive marginal and overall marginal distributions.This setting is slightly more general than the one-sample formulation.
- Problem settings: The paper compares PU against ordinary supervised PN learning, including PN sampling with or without matching the class-prior probability.NU learning is treated as the analogous alternative using negative and unlabeled data.
- Contributions: The paper establishes risk bounds for empirical minimizers in PN, PU, and NU learning to compare their estimation errors.The analysis uses uniform deviation bounds and Rademacher complexities, then derives estimation-error and excess-risk bounds.
- Main results: For finite samples, PU improves on PN when π/√n+ + 1/√nu < (1 −π)/√n−, while NU improves under the corresponding reversed condition.These conditions depend only on the class prior and the sizes of P, N, and U data.
- Main results: With P and N sample sizes growing in the same order and U data growing faster, either PU or NU asymptotically improves on PN.Which method improves depends on π, n+, and n−.
2 Unbiased estimators to the risk
The paper constructs unbiased empirical risk estimators for PN, PU, and NU learning. These estimators have convergence rates governed by the labeled and unlabeled sample sizes, enabling direct risk-bound comparisons.
- Risk formulation: The paper defines positive and negative partial risks using marginal densities p+(x)=p(x | Y=+1) and p−(x)=p(x | Y=−1).
- Risk formulation: The risk of a decision function is expressed through partial risks under the positive and negative class-conditional distributions.
- PN estimator: The PN estimator is unbiased and consistent, with convergence rate O_p(1/√n+ + 1/√n−).
- PU estimator: The PU estimator remains unbiased and consistent despite treating U data as negative, with convergence rate O_p(1/√n+ + 1/√nu).Its construction uses positive and unlabeled samples to estimate the overall risk without directly observing negative data.
- Loss function: The scaled ramp loss is used as a surrogate, and the paper proves that it is classification-calibrated.This supports controlling excess classification risk through the surrogate risk.
3 Theoretical comparisons based on risk bounds
The paper compares PN, PU, and NU empirical risk minimizers through estimation-error bounds and derives conditions determining when PU or NU bounds are tighter. These comparisons depend on class-prior probability and sample sizes, with asymptotic results showing that one unlabeled-data approach can improve on PN under stated growth conditions.
- 3.1 Risk bounds: The bounds for PU converge at O_p(1/√n+ + 1/√nu) for fixed G, while growing G can yield slower convergence toward the Bayes classifier.Classification calibration connects the surrogate-risk guarantee to excess 0–1 risk.
- 3.2 Finite-sample comparisons: Theorem 6 states that PU or NU has a tighter estimation-error bound than PN exactly when αpu,pn < 1 or αnu,pn < 1, respectively.The comparison uses simplified upper bounds under the paper’s assumption on the function class and data distributions.
- 3.2 Finite-sample comparisons: The comparison ratios depend only on π, n+, n−, and nu, not on the specific function class or distributions when the stated assumption holds.This makes the finite-sample comparison conditions independent of G, p(x,y), p(x), p+(x), and p−(x).
- 3.2 Finite-sample comparisons: αpu,pn increases with ρpu and decreases with ρpn, so relatively more unlabeled data favors PU while relatively more negative data favors PN.Here ρpu and ρpn encode sample-size ratios under proportional-growth conditions.
- 3.2 Finite-sample comparisons: When ρpn = π/(1 −π), PU can have a tighter bound only if unlabeled data is sufficiently larger than positive data, such as ρpu < 0.04.The ratio αpu,pn decreases with π below a threshold and increases above it.
- 3.3 Asymptotic comparisons: As n+ and n− grow in the same order while nu grows faster, either PU or NU eventually improves on PN’s bound, depending on π and the P-to-N sample-size ratio.The exceptional equality case is n+/n− = π^2/(1 −π)^2; the paper presents this as its second main result.
4 Experiments
Experiments on artificial and benchmark data tested theoretical comparisons by varying unlabeled-sample size and class-prior probability. Benchmark results were highly consistent with theory despite differences between the experimental setup and theoretical assumptions.
- The benchmark suite included datasets from the IDA and UCI repositories, a semi-supervised learning book, and the European ESPRIT 5516 project.Table 2 reports feature counts, dataset sizes, and positive-class ratios.
- Benchmark datasets required a Gaussian-kernel model with hyperparameters selected by five-fold cross-validation for each risk minimizer and sampling.
- Benchmark results were highly consistent with the theoretical findings across experiments varying n_u and π.The benchmark experiments varied n_u from 10 to 300 and π from 0.05 to 0.95, using means with standard errors over 100 random samplings.
- Only the PU classifier's errors decreased with n_u on benchmark data, while NU errors fluctuated because n_− = 5 was insufficiently informative.The paper attributes this benchmark-specific behavior to the greater difficulty of benchmark data compared with artificial data.
5 Conclusions
The paper concludes that PU or NU learning can outperform PN learning when their estimation-error bounds are tighter. With unlabeled data growing faster than labeled data, at least one of the PU or NU asymptotic bounds improves on the PN bound, and experiments validate these findings.
- PU or NU learning has a tighter bound than PN learning when its comparison quantity α is smaller than one.
- When the U-data size increases faster than the P- and N-data sizes, either the PU or NU asymptotic bound improves on the PN bound.
- Experiments on one artificial dataset and nine benchmark datasets validated the theoretical findings.
A Proofs
The appendix proves selected theoretical results and omits proofs of two theorems because they are essentially similar to the proof of Theorem 2.
- The appendix proves Theorem 1, Lemma 8, Theorem 2, and Corollary 5 from the main text.
- Proofs of Theorems 3 and 4 are omitted because they rely on slightly different uniform-deviation bounds but are essentially similar to Theorem 2.
A.1 Proof of Theorem 1
The proof establishes that the scaled ramp loss is classification-calibrated by minimizing its conditional risk at the Bayes classifier.
- The conditional risk is expressed as a class-probability-weighted sum of the positive- and negative-label losses.
- The conditional-risk minimum is achieved by g(x) = sign(π_+(x) − π_−(x)), which is the Bayes classifier.
- Therefore, the scaled ramp loss is classification-calibrated.
A.2 Proof of Lemma 8
The proof decomposes the PU empirical risk into positive and unlabeled components, bounds their uniform deviations separately, and combines them to establish Lemma 8.
- A.2 Proof of Lemma 8: The PU empirical-risk deviation is bounded by the positive-risk deviation and the unlabeled-negative-risk deviation.Sub-additivity of supremum operators reduces the proof to separate uniform deviation bounds.
- A.2 Proof of Lemma 8: Replacing one positive sample changes the bounded empirical positive risk by at most 1/n+, enabling McDiarmid’s inequality.The surrogate loss is bounded between 0 and 1.
- A.2 Proof of Lemma 8: Rademacher-complexity uniform deviation bounds provide the high-probability controls needed for the decomposed risk terms.The proof applies the bound with probability at least 1 − δ/2.
- A.2 Proof of Lemma 8: Talagrand’s contraction lemma transfers the complexity bound from the composite loss class to the function class when the loss is Lℓ-Lipschitz.The resulting relation is Rn+,p+(ℓ◦G) ≤ LℓRn+,p+(G).
A.3 Proof of Theorem 2
The theorem’s estimation-error bound follows from Lemma 8 and empirical-risk minimization, while classification calibration converts it into an excess-risk bound.
- A.3 Proof of Theorem 2: The estimation-error bound is obtained from Lemma 8 and the empirical-risk minimizer’s defining inequality.The proof uses bRpu(ĝpu) ≤ bRpu(g∗).
- A.3 Proof of Theorem 2: Classification calibration converts the estimation-error bound into an excess-risk bound through a convex, invertible, nondecreasing transformation ψℓ.The transformation satisfies ψℓ(0) = 0.
A.4 Proof of Corollary 5
The corollary specializes the estimation bounds to a function class whose Rademacher complexity decreases as the inverse square root of sample size.
- A.4 Proof of Corollary 5: The estimation-error bound is rewritten using the previously established bound.This yields the stated corollary relations, with the analogous derivations obtained in the same way.
- A.4 Proof of Corollary 5: For the specified function class, the Rademacher complexity satisfies Rn,q(G) ≤ CwCφ/√n.The result follows by bounding empirical complexity and taking its expectation.