Many real classification problems come with a few labeled examples from several known classes and a large unlabeled pool. That pool mixes those same classes with a background class nobody labeled. Examples include defect types on an inspection line, tumor subtypes in a scan archive, and entity types in distantly labeled text. To learn from such data, one first needs the class priors: the fraction of the unlabeled pool that belongs to each known class. When classes overlap in feature space, existing estimators overstate these fractions. The standard practical fix is to merge all labeled classes into one "positive" class and estimate a single number. We argue this merge does more than lose granularity. It produces a biased prior whenever the labeled pool's mix of classes differs from the unlabeled pool's mix, which is the usual case.
We propose to estimate the whole vector of class priors jointly. The required condition is that each known class has some region of feature space free of background examples. Different classes may use different regions, and those regions may still contain other known classes. Because the labeled data show how much of every known class falls in every region, contamination between known classes can be subtracted out exactly. That leaves only background contamination, which is what makes the problem hard. The estimates then feed a multi-class learner whose training risk is kept non-negative and whose sample discarding is done separately for each class.
Background and the gap
In positive-unlabeled (PU) learning, the unlabeled density is a mixture $p_U(x) = \sum_{k=1}^{K} \pi_k p_k(x) + \pi_0 p_0(x)$. Here $p_k$ is the density of known class $k$, $\pi_k$ its unknown share of the unlabeled pool, and $p_0$ the unseen background density with share $\pi_0 = 1 - \sum_k \pi_k$.
The binary literature explains why prior estimates inflate under overlap. Divergence-based partial matching (du Plessis et al., Niu et al.) fits a scaled positive density inside $p_U$. Learning from Positive and Unlabeled Data(2) shows that the objective's gradient at the true prior is negative, so the optimizer keeps pushing the estimate upward. Rethinking Class-Prior Estimation proves that without irreducibility the prior is unidentifiable and that irreducibility cannot be checked from PU data. Irreducibility means, informally, that no part of the positive density can be explained as negative.
Two binary methods supply the machinery we reuse. Best Bin Estimation (BBE) asks only for a "pure positive bin", a top-score region with no negatives, and pairs it with CVIR, which discards the top $\alpha$ fraction of unlabeled data during training. SuMPE relaxes purity further but needs a known contamination bound. Both are defined only for one positive component.
Four bridging papers motivate the gap without closing it:
- Multi-Positive and Unlabeled Learning (MPU) trains a direct multi-class PU classifier but assumes the priors are known. Its authors name relaxing this as future work.
- Sanderson & Scott estimate multi-class proportions from slopes at the endpoint of ROC curves (receiver operating characteristic curves). Their identifiability rests on irreducibility of every component, which overlap breaks.
- Conf-MPU feeds a scalar confidence from a binary PU stage into a multi-class loss. The binary stage carries exactly the overlap bias described above.
- PUJE bounds open-set risk with multi-class PU theory but treats the known/unknown proportion implicitly.
Core Claim
The claim has two parts.
The first is a negative result. Merge the labeled classes into one positive set whose class mix is $w_k$, and run a pure-bin estimator such as BBE. If the purest bin is dominated by a separable class $j$, the estimate converges to roughly $\pi_j / w_j$, not to $\sum_k \pi_k$. It is therefore biased in either direction whenever $w$ differs from the unlabeled positive mix, even when that bin is perfectly pure.
The second is a positive result. Take any $K$ regions $A_1, \dots, A_K$ that contain no background mass and whose matrix $M_{kj} = P_j(A_k)$ is invertible. Here $P_j(A)$ is the fraction of labeled class-$j$ data falling in region $A$, and $U(A)$ is the corresponding unlabeled fraction. Then the priors solve
$$U(A_k) = \sum_{j=1}^{K} \pi_j P_j(A_k), \qquad k = 1, \dots, K.$$
The background only needs to be absent from these regions. The known classes may overlap with each other freely, and no region needs to be pure in any one class. For any region that does contain background, the left side exceeds the right. Each candidate region therefore yields a valid one-sided inequality, and the inequalities can be combined.
The first part is a short calculation; we will state it formally and verify it. The second part is the method.
Research Program
Multi-class Best Bin Estimation. We call the estimator MBBE. Train a $(K+1)$-way network that separates each labeled class from the unlabeled pool. For class $k$, candidate regions are upper tails of its score $s_k$.
Threshold selection. BBE chooses thresholds by minimizing an upper confidence bound. We do the same, but the tail ratio for class $k$ is corrected by subtracting the other classes' contributions $\sum_{j \neq k} \pi_j P_j(A)$, all of which are observable from labeled data. This couples the $K$ estimates. We solve the coupled system by a fixed-point iteration started from the uncorrected per-class bounds. Each step keeps every estimate a valid upper bound, so the iteration is monotone.
Classes without a background-free region. For such a class the method reports an interval: the upper bound from its tightest region, and a lower bound of zero or a bound implied by the other constraints. It does not report a fake point estimate. This follows Yao et al.'s result that such classes are unidentifiable.
Training. The estimated priors enter a multi-class version of the unbiased PU risk. We clip the implied background risk at zero, as Lu et al. do for the binary two-unlabeled-sets case, where uncorrected risk drove MNIST accuracy to 53.34% against 90.34% with correction. Following Garg et al., we alternate estimation and training. The difference from CVIR is that each class discards the top $\pi_k$ share of unlabeled data ranked by its own score, rather than a single global $\alpha$ ranked by a scalar.
Analysis. We will prove consistency of MBBE under the per-class background-free condition and derive its rate from BBE's concentration argument. The finite-sample error should scale with the inverse of the smallest singular value of $M$, because inverting the linear system amplifies tail-estimate noise by that factor. This gives a measurable prediction of when cross-class overlap hurts.
Baselines
Naive reference. Treat all unlabeled data as background and train a standard $(K+1)$-way classifier. Garg et al. show deep networks then memorize the hidden positives. Conf-MPU reports that this kind of baseline (AutoNER) reaches only 48.50% recall on CoNLL2003, against 81.02% for PU training.
Strongest estimation competitor: binary union BBE. Merge all labeled classes, run BBE to get the total positive mass, then split that mass across classes. The split uses expectation-maximization reweighting of a classifier trained on labeled positives only. The reported reference is BBE's absolute estimation error of 0.026 on binarized CIFAR with a ResNet; for training, (TED)$^n$ reaches 82.7% accuracy versus 77.2% for nnPU (all from Garg et al.). Those are binary-task numbers, so we rerun BBE ourselves on our multi-class splits. The networks, augmentation and tuning budget will be identical to MBBE's, with the same number of hyperparameter trials, all selected on PU-only validation criteria.
One-versus-rest. Run BBE and ReCPE separately on each class. ReCPE's injection fraction gets the same tuning grid across methods.
Multi-class but irreducibility-based. We reimplement Sanderson & Scott's MPE-Joint and MPE-Incomplete estimators on frozen deep features. No reported multi-class result was found on Lacuna for their estimators on these benchmarks.
Downstream classification. - MPU given oracle priors serves as an upper reference. It reports 90.78% on MNIST, against 84.98% for Biased-SVM. - PUJE is the open-set baseline. It reports HOS 67.3 on Syn2Real-O and a 3.0-point gain in OS score on Office-Home.
Ablations isolating the key ingredients. - MBBE without the cross-class subtraction, which tests whether the coupling matters. - The full pipeline with a global rather than per-class discard.
What counts as beating the baselines. On estimation: lower mean absolute error on the prior vector than union BBE, outside seed confidence intervals, with the gap growing as label shift grows. On classification: matching or exceeding (TED)$^n$-style training on known-class accuracy while improving background rejection.
Why not just…?
Why not just merge the positives, run binary BBE, and split? This is the real threat. If the labeled class mix matches the unlabeled one, it should do as well as MBBE. Our claim is that it fails exactly when the two mixes differ. We will sweep the divergence between $w$ and the unlabeled positive mix from zero upward. If union BBE's error stays flat across the sweep, the first part of our claim is false. In that case we would recast the contribution as the training-side per-class discard only.
Why not just run one-versus-rest with a binary overlap corrector? Each "rest" contains the other $K-1$ known classes. Xu et al. note this adds overlap to every split. Each binary estimate then absorbs those classes' mass, and errors compound when the estimates are summed. The ablation without cross-class subtraction is essentially this baseline in shared code, so the comparison isolates the correction.
Why not just use SuMPE or ReCPE per class? SuMPE needs a known contamination bound for each class, and ReCPE needs a tuned injection fraction. In the multi-class case both quantities depend on the other classes' unknown priors. We include ReCPE with full tuning. We expect it to help where overlap with the background is mild and to fail where known classes overlap each other, and the overlap grid below tests this.
Proposed Experiments
Controlled image splits. On CIFAR-10 and MNIST, pick $K=3$ to $5$ known classes and use the remaining classes as background. Overlap is varied by pairing semantically close classes (cat/dog, truck/automobile) across the known/background boundary or within the known set. Label shift between the labeled and unlabeled positive mixes is set on a grid.
Office-Home. Use the 25 known / 40 unknown open-set protocol, a natural setting where the unknown share is unknown.
Applied check. Use the four-class laser-engraving defect data from Zhang et al., whose binary detector reached 96.72%. We label a few defect types and leave the rest unlabeled to test whether granular defect priors become recoverable.
Metrics. Per-class and total absolute prior error, interval coverage for unidentifiable classes, known-class accuracy, and background-rejection accuracy with their harmonic mean.
Decisive checks. - Union BBE's bias should grow with label shift while MBBE's stays flat. - MBBE's error should track the inverse smallest singular value of $M$. - Per-class discarding should beat global discarding mainly in the asymmetric-overlap configurations.
If none of these three hold, the proposal fails.
References
- Class Prior Estimation from Positive and Unlabeled Data
- Class-prior Estimation for Learning from Positive and Unlabeled Data
- Learning from Positive and Unlabeled Data(2)Computationally Efficient Estimation of Class Priors (情報論的学習理論と機械学習 情報論的学習理論ワークショップ)
- Rethinking Class-Prior Estimation for Positive-Unlabeled Learning
- Mixture Proportion Estimation and PU Learning:A Modern Approach
- Mixture Proportion Estimation Beyond Irreducibility
- Multi-Positive and Unlabeled Learning
- Class Proportion Estimation with Application to Multiclass Anomaly Rejection
- Distantly Supervised Named Entity Recognition via Confidence-Based Multi-Class Positive and Unlabeled Learning
- Open-Set Domain Adaptation via Joint Error Based Multi-class Positive and Unlabeled Learning
- Mitigating Overfitting in Supervised Classification from Two Unlabeled Datasets: A Consistent Risk Correction Approach
- Classification of Microscopic Laser Engraving Surface Defect Images Based on Transfer Learning Method