Source-linked AI summary
Class-prior Estimation for Learning from Positive and Unlabeled Data
Marthinus C. du Plessis, Gang Niu, Masashi Sugiyama
TL;DR
The paper addresses class-prior estimation when only positive and unlabeled data are available, rather than labeled samples from both classes. It uses penalized divergences to correct the overestimation caused by partial matching, and shows that penalized L1-distance provides an efficient analytic estimator supported by theoretical and experimental analyses.
Problem
Class-prior estimation is needed for classifier training from positive and unlabeled data, but existing mixture-matching methods require labeled positive and negative samples.
Method
The paper penalizes f-divergences to correct partial-matching bias and develops a sample-based penalized L1-distance estimator using convex duality.
Results
The proposed approach correctly estimates the class prior, while penalized L1-distance yields an analytic, computationally efficient estimator with theoretically analyzed consistency, stability, and estimation error.
Takeaways & Limitations
Positive and unlabeled samples can suffice for class-prior estimation, enabling classification without negative data under the proposed penalized matching approach.
Takeaways & Limitations
The deviation bounds require the class-prior parameter to be fixed before observing the data; choosing it afterward can make the bounds unusable.
Abstract
from arXiv · showhide
We consider the problem of estimating the class prior in an unlabeled dataset. Under the assumption that an additional labeled dataset is available, the class prior can be estimated by fitting a mixture of class-wise data distributions to the unlabeled data distribution. However, in practice, such an additional labeled dataset is often not available. In this paper, we show that, with additional samples coming only from the positive class, the class prior of the unlabeled dataset can be estimated correctly. Our key idea is to use properly penalized divergences for model fitting to cancel the error caused by the absence of negative samples. We further show that the use of the penalized $L_1$-distance gives a computationally efficient algorithm with an analytic solution. The consistency, stability, and estimation error are theoretically analyzed. Finally, we experimentally demonstrate the usefulness of the proposed method.
1 Introduction
The paper estimates an unlabeled dataset’s class prior using positive and unlabeled data, where the unlabeled distribution mixes positive and negative samples. It addresses the absence of negative samples by penalizing divergences used for distribution matching.
- The unlabeled dataset combines positive and negative samples, while the additional dataset contains positive samples only.
- Estimating the class prior from positive and unlabeled data enables classifier training without negative data.
- Existing divergence-based methods require labeled samples from both positive and negative classes and therefore do not directly apply here.
- The paper shows that partial matching overestimates the class prior, whereas appropriately penalized f-divergences can recover it correctly.
- Penalized L1-distance yields an analytic, computationally efficient estimator, with theoretical analyses of consistency, stability, and estimation error.
2 Class-prior estimation via penalized f-divergences
The paper analyzes why partial distribution matching overestimates the class prior and introduces penalized f-divergences to correct this error. Penalized L1-distance estimation can then be evaluated from samples efficiently, with an analytic solution obtained through a suitable model formulation.
- 2.2 Partial distribution matching via penalized f-divergences: The L1 distance does not necessarily overestimate the prior, motivating a penalized L1 divergence that removes overestimation.The penalty is chosen so that the true prior satisfies the required subgradient condition.
- 2.1 Over-estimation of the class prior: Partial matching under general f-divergences overestimates the class prior when the positive and negative class distributions overlap.The derivative is negative under class overlap, and convexity places the minimizer above the true prior.
- 2.3 Direct evaluation of penalized f-divergences: Penalized f-divergences can be estimated directly from samples using Fenchel duality, without density estimation.Replacing expectations by sample averages produces an optimization problem that is convex when the density-ratio model is linear in parameters.
- 2.4 Penalized L1-distance estimation: For penalized L1-distance, the estimator becomes computationally efficient because part of the optimization decouples across coefficients.The resulting coefficient solution can be calculated with a max operation, while the class prior minimizes the estimated distance.
- 2.4 Penalized L1-distance estimation: A nonnegative basis-function linear model with regularization leads to a quadratic optimization problem solvable by an off-the-shelf quadratic solver.Gaussian kernels centered at sample points are used as basis functions in practice.
3 Theoretical analysis
Theoretical analysis establishes consistency, stability, and estimation-error guarantees for penalized L1-distance estimators, covering infinite and finite settings. The finite case can converge more slowly unless an additional support-boundary condition stabilizes the feasible region.
- 3.1 Consistency: The analysis studies consistency of penalized L1-distance estimates for fixed θ in both infinite and finite cases.The finite case requires handling a changing feasible region in addition to the absence of an analytic solution.
- 3.1 Consistency: The infinite-case estimate converges at the optimal parametric rate Op(1/√n′).
- 3.1 Consistency: The finite-case convergence rate is much worse because dϕ(X′, X∗) may vanish extremely slowly without strong assumptions on p(x).
- 3.1 Consistency: If sup_x∈X∗ α∗_F · ϕ(x) < 1 + c, the estimated finite-case solution eventually remains inside the population feasible region.This stabilization removes dependence on the convergence of the perturbed feasible region and supports optimal-rate behavior.
- 3.2 Stability: Uniform deviation bounds hold simultaneously for all θ ∈ [0,1], while fixed-θ deviation bounds remain in the optimal parametric rate.Uniform bounds address the problem that selecting θ after observing the data can invalidate fixed-θ bounds.
- 3.3 Estimation error: Theorem 8 establishes optimal-parametric-rate estimation-error bounds for the class-prior estimator ˆθ.
4 Related work
Earlier approaches estimate the class prior through divergence matching or ROC-based methods, but many require labeled positive and negative samples or can overestimate under class overlap. ROC endpoint instability and uncertain curve-fitting effects create an additional practical concern.
- Pearson-divergence methods can estimate the class prior from partially labeled data, including positive and unlabeled samples combined.
- Existing divergence, L2, and MMD approaches generally require labeled samples from both classes and therefore do not directly fit this setup.
- Partial matching methods based on Pearson or related divergences may overestimate the true class prior when class-conditional densities overlap.
- Scott–Blanchard methods avoid overestimation by reducing estimation to a ROC-based problem involving false-negative rates on the unlabeled data.
- Empirical ROC curves can be unstable at the right endpoint in high dimensions, and the effect of fitting that endpoint on class-prior estimates is unclear.
5 Experiments
Experiments compare prior estimators on synthetic overlapping densities and MNIST. The proposed penalized L1 method gives accurate class-prior estimates and classification accuracy close to using the true prior, while some baselines overestimate or vary with the prior.
- The experiments compare EN, PE, SB, penalized L1 with an analytic solution, and ordinary penalized L1 solved by quadratic programming.
- Ordinary penalized L1 is extremely slow because it requires solving a quadratic program for every candidate class prior.
- Numerical Illustration: For overlapping uniform densities, the experiments examine systematic overestimation by unconstrained f-divergence minimization as overlap varies with γ.
- Benchmark datasets: MNIST uses one-versus-rest digit classification after reducing inputs to four PCA dimensions to increase class overlap.
- Benchmark datasets: The proposed pen-L1 method overall gives accurate class-prior estimates, whereas EN and PE are less accurate for small priors and more accurate for higher priors.
- Benchmark datasets: PenL1 classification accuracy is generally close to accuracy obtained with the true class prior, and more accurate prior estimates usually correspond to lower misclassification rates.
- Benchmark datasets: In one result, PE and EN outperform the true-prior reference in misclassification rate, possibly because shared data estimation and compensating regularization effects influence the comparison.
6 Conclusion
The paper addresses class-prior estimation from positive and unlabeled data by correcting partial-matching overestimation with penalized divergences. Penalized L1 yields an efficient analytic estimator supported by theory and experiments.
- Partial distribution matching under f-divergences systematically overestimates the class prior in positive-unlabeled estimation.
- Penalized f-divergences rectify this overestimation, and penalized L1 provides a computationally efficient algorithm with an analytic solution.
- Uniform deviation and estimation-error bounds theoretically support the proposed method, while experiments show favorable comparisons with existing approaches.
A Proofs
The appendix proves consistency, compactness, continuity, stability, concentration, and estimation-error results for the proposed estimators. It also derives bounded-difference and Rademacher-complexity bounds used in the theoretical analysis.
- Foundational properties: The proofs establish compactness and continuity properties for the feasible parameter sets and objective functions used by the estimators.These properties support existence of extrema and subsequent perturbation analyses.
- Stability: The feasible-set correspondence is Lipschitz continuous, with Hausdorff distance bounded by Kδ times the feature-distribution distance.This result follows from symmetric bounds on the directed distances between feasible parameter sets.
- Consistency: The appendix shows that sufficiently large samples place the empirical optimizer in the population feasible set and preserve its minimizing property.The argument uses sample-size thresholds N and N′ and an unperturbed feasible region.
- Concentration: Replacing one sample changes the relevant bounded-difference term by at most θ^2/n^2 + 2θ/n, and correspondingly perturbs the penalized L1 objective by a sample-size-dependent bound.The proof applies McDiarmid’s inequality after bounding changes from replacing samples in each dataset.
- Estimation error: The estimation-error proofs decompose objective differences into optimization and sampling terms, then control them through strong convexity, bounded differences, and empirical-process arguments.The appendix uses ghost samples, Rademacher variables, symmetrization, and concentration inequalities to obtain high-probability bounds.