Mixture Proportion Estimation and PU Learning: A Modern Approach
Year: 2022

Abstract:
Given only positive examples and unlabeled examples (from both positive and negative classes), we might hope nevertheless to estimate an accurate positiveversus-negative classifier. Formally, this task is broken down into two subtasks: (i) Mixture Proportion Estimation (MPE)—determining the fraction of positive examples in the unlabeled data; and (ii) PU-learning—given such an estimate, learning the desired positive-versus-negative classifier. Unfortunately, classical methods for both problems break down in high-dimensional settings. Meanwhile, recently proposed heuristics lack theoretical coherence and depend precariously on hyperparameter tuning. In this paper, we propose two simple techniques: Best Bin Estimation (BBE) (for MPE); and Conditional Value Ignoring Risk (CVIR), a simple objective for PU-learning. Both methods dominate previous approaches empirically, and for BBE, we establish formal guarantees that hold whenever we can train a model to cleanly separate out a small subset of positive examples. Our final algorithm (TED), alternates between the two procedures, significantly improving both our mixture proportion estimator and classifier1.

heading: 1 Introduction
text: When deploying k-way classifiers in the wild, what can we do when confronted with data from a previously unseen class (k ` 1)? Theory dictates that learning under distribution shift is impossible absent assumptions. And yet people appear to exhibit this capability routinely. Faced with new surprising symptoms, doctors can recognize the presence of a previously unseen ailment and attempt to estimate its prevalence. Similarly, naturalists can discover new species, estimate their range and population, and recognize them reliably going forward.
To begin making this problem tractable, we might make the label shift assumption [37, 41, 29], i.e., that while the class balance ppyq can change, the class conditional distributions ppx|yq do not. Moreover, we might begin by focusing on the base case, where only one class has been seen previously, i.e., k “ 1. Here, we possess (labeled) positive data from the source distribution, and (unlabeled) data from the target distribution, consisting of both positive and negative instances. This problem has been studied in the literature as learning from positive and unlabeled data [8, 27] and has typically been broken down into two subtasks: (i) Mixture Proportion Estimation (MPE) where we estimate α, the fraction of positives among the unlabeled examples; and (ii) PU-learning where this estimate is incorporated into a scheme for learning a Positive-versus-Negative (PvN) binary classifier.
Traditionally, MPE and PU-learning have been motivated by settings involving large databases where unlabeled examples are abundant and a small fraction of the total positives have been extracted. For example, medical records might be annotated indicating the presence of certain diagnoses, but the unmarked passages are not necessarily negative. This setup has also been motivated by protein and
1Code is available at https://github.com/acmi-lab/PU_learning
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
gene identification [16]. Databases in molecular biology often contain lists of molecules known to exhibit some characteristic of interest. However, many other molecules may exhibit the desired characteristic, even if this remains unknown to science.
Many methods have been proposed for both MPE [16, 12, 39, 35, 21, 4, 36, 20] and PU-learning [14, 11, 23]. However, classical MPE methods break down in high-dimensional settings [35] or yield estimators whose accuracy depends on restrictive conditions [12, 39]. On the other hand, most recent proposals either lack theoretical coherence, rely on heroic assumptions, or depend precariously on tuning hyperparameters that are, by the very problem setting, untunable. For PU learning, Elkan and Noto [16] suggest training a classifier to distinguish positive from unlabeled data followed by a rescaling procedure. Du Plessis et al. [11] suggest an unbiased risk estimation framework for PU learning. However, these methods fail badly when applied with model classes capable of overfitting and thus implementations on high-dimensional datasets rely on extensive hyperparameter tuning and additional ad-hoc heuristics that do not transport effectively across datasets.
In this paper, we propose (i) Best Bin Estimation (BBE), an effective technique for MPE that produces consistent estimates pα under mild assumptions and admits finite-sample statistical guarantees achieving the desired Op1{ ? nq rates; and (ii) learning with the Conditional Value Ignoring Risk (CVIR) objective, which discards the highest loss pα fraction of examples on each training epoch, removing the incentive to overfit to the unlabeled positive examples. Both methods are simple to implement, compatible with arbitrary hypothesis classes (including deep networks), and dominate existing methods in our experimental evaluation. Finally, we combine the two in an iterated Transform-Estimate-Discard (TED)n framework that significantly improves both MPE estimation error and classifier error.
We build on label shift methods [29, 3, 2, 34, 17], that leverage black-box classifiers to reduce dimensionality, estimating the target label distribution as a functional of source and target pushforward distributions. While label shift methods rely on classifiers trained to separate previously seen classes, BBE is able to exploit a Positive-versus-Unlabeled (PvU) target classifier, which gives each input a score indicating how likely it is to be a positive sample. In particular, BBE identifies a threshold such that by estimating the ratio between the fractions of positive and unlabeled points receiving scores above the threshold, we obtain the mixture proportion α.
BBE works because in practice, for many datasets, PvU classifiers, even when uncalibrated, produce outputs with near monotonic calibration diagrams. Higher scores correspond to a higher proportion of positives, and when the positive data contains a separable sub-domain, i.e., a region of the input space where only the positive distribution has support, classifiers often exhibit a threshold above which the top bin contains mostly positive examples. We show that the existence of a (nearly) pure top bin is sufficient for BBE to produce a (nearly) consistent estimate pα, whose finite sample convergence
rates depend on the fraction of examples in the bin and whose bias depends on the purity of the bin. Crucially, we can estimate the optimal threshold from data.
We conduct a battery of experiments both to empirically validate our claim that BBE’s assumptions are mild and frequently hold in practice, and to establish the outperformance of BBE, CVIR, and (TED)n over the previous state of the art. We first motivate BBE by demonstrating that in practice PvU classifiers tend to isolate a reasonably large, reasonably pure top bin. We then conduct extensive experiments on semi-synthetic data, adapting a variety of binary classification datasets to the PU learning setup and demonstrating the superior performance of BBE and PU-learning with the CVIR objective. Moreover, we show that (TED)n, which combines the two in an iterative fashion, improves significantly over previous methods across several architectures on a range of image and text datasets.

heading: 2 Related Work
text: Research on MPE and PU learning date to [9, 8, 27] (see review by [5]). Elkan and Noto [16] first proposed to leverage a PvU classifier to estimate the mixture proportion. Du Plessis and Sugiyama [13] propose a different method for estimating the mixture coefficient based on Pearson divergence minimization. While they do not require a PvU classifier, they suffer the same shortcoming. Both methods require that the positive and negative examples have disjoint support. Our requirements are considerably milder. Blanchard et al. [6] observe that without assumptions on the underlying positive and negative distributions, the mixture proportion is not identifiable. Furthermore, [6] provide an irreducibility condition that identifies α and propose an estimator that converges to the true α. While their estimator can converge arbitrarily slowly, Scott [39] showed faster convergence (Op1{ ? nq) under stronger conditions. Unfortunately, despite its appealing theoretical properties Blanchard et al. [6]’s estimator is computationally infeasible. Building on Blanchard et al. [6], Sanderson and Scott [38] and Scott [39] proposed estimating the mixture proportion from a ROC curve constructed for the PvU classifier. However, when the PvU classifier is not perfect, these methods are not clearly understood. Ramaswamy et al. [35] proposed the first computationally feasible algorithm for MPE with convergence guarantees to the true proportion. Their method KM, requires embedding distributions onto an RKHS. However, their estimator underperforms on high dimensional datasets and scales poorly with large datasets. Bekker and Davis [4] proposed TIcE, hoping to identify a positive subdomain in the input space using decision tree induction. This method also underperforms in high-dimensional settings.
In the most similar works, Jain et al. [21] and Ivanov [20] explore dimensionality reduction using a PvU classifier. Both methods estimate α through a procedure operating on the PvU classifier’s output. However, neither methods has provided theoretical backing. [20] concede that their method often fails and returns a zero estimate, requiring that they fall back to a different estimator. Moreover while both papers state that their method require the Bayes-optimal PvU classifier to identify α in the transformed space, we prove that even when hypothesis class is well specified for PvN learning, PvU training can fail to recover the Bayes-optimal scoring function. Furthermore, we also show that the heuristic estimator in Scott [39] can be thought of as using PvU classifier for dimensionality reduction. While this heuristic is similar to our estimator in spirit, we show that the functional form of their estimator is different from ours and note that their heuristic enjoys no theoretical guarantee. By contrast, our estimator BBE is theoretically coherent under mild conditions and outperforms all of these methods empirically.
Given α, Elkan and Noto [16] propose a transformation via Bayes rule to obtain the PvN classifier. They also propose a weighted objective, with weights given by the PvU classifier. Other propose unbiased risk estimators [14, 11] which require the mixture proportion α. Du Plessis et al. [14] proposed an unbiased estimator with non-convex loss functions satisfying a specific symmetric condition, and subsequently Du Plessis et al. [11] generalized it to convex loss functions (denoted uPU in our experiments). in our experiments. Noting the problem of overfitting in modern overparameterized models, Kiryo et al. [23] propose a regularized extension that clips the loss on unlabeled data to zero. This is considered the current state-of-the-art in PU literature (denoted nnPU in our experiments). More recently, Ivanov [20] proposed DEDPUL, which finetunes the PvU classifiers using several heuristics, Bayes rule, and Expectation Maximization (EM). Since their method only applies a post-processing procedure, they rely on a good domain discriminator classifier in the first place and several hyperparameters for their heuristics. Several classical methods attempt to learn weights that identify reliable negative examples [30, 28, 26, 31, 44]. However, these earlier methods have not been successful with modern deep learning models.
Algorithm 1 Best Bin Estimation (BBE)
input : Validation positive (Xp) and unlabeled (Xu) samples. Blackbox model classifier pf : X Ñ r0, 1s. Hyperparameter 0 ă δ, γ ă 1.
1: Zp, Zu “ fpXpq, fpXuq. 2: pqupzq, pqppzq “ ř ziPZp Irziězs np , ř ziPZu Irziězs nu for all z P r0, 1s. 3: Estimate pc :“ argmincPr0,1s ˆ pqupcq pqppcq ` 1`γ pqppcq ˆ b logp4{δq 2nu ` b logp4{δq 2np ˙˙ .
output : pα :“ pquppcq pqpppcq

heading: 3 Problem Setup
text: By ||¨|| and x¨, ¨y, we denote the Euclidean norm and inner product, respectively. For a vector v P Rd, we use vj to denote its jth entry, and for an event E, we let I rEs denote the binary indicator of the event. By |A|, we denote the cardinality of set A. Let X P Rd be the input space and Y “ t´1,`1u be the output space. Let P : X ˆ Y Ñ r0, 1s be the underlying joint distribution and let p denote its corresponding density.
Let Pp and Pn be the class-conditional distributions for positive and negative class and pppxq “ ppx|y “ `1q and pnpxq “ ppx|y “ ´1q be the corresponding class-conditional densities. Pu denotes the distribution of the unlabeled data and pu denotes its density. Let α P r0, 1s be the fraction of positives among the unlabeled population, i.e., Pu “ αPp ` p1 ´ αqPn. When learning from positive and unlabeled data, we obtain i.i.d. samples from the positive (class-conditional) distribution, which we denote as Xp “ tx1, x2, . . . , xnpu „ P np p and i.i.d samples from unlabeled distribution as Xu “ txnp`1, xnp`2, . . . , xnp`nuu „ Pnuu . MPE is the problem of estimating α. Absent assumptions on Pp, Pn and Pu, the mixture proportion α is not identifiable [6]. Indeed, if Pu “ αPp ` p1´ αqPn, then any alternate decomposition of the form Pu “ pα´γqPp`p1´α`γqP1n, for γ P r0, αq and P1n “ p1´α`γq´1pγPp`p1´αqPnq, is also valid. Since we do not observe samples from the distribution Pn, the parameter α is not identifiable. Blanchard et al. [6] formulate an irreducibility condition under which α is identifiable. Intuitively, the condition restricts Pn to ensure that it can not be a (non-trivial) mixture of Pp and any other distribution. While this irreducibility condition makes α identifiable, in the worst-case, the parameter α can be difficult to estimate and any estimator must suffer an arbitrarily slow rate of convergence [6]. In this paper, we propose mild conditions on the PvU classifier that make α identifiable and allows us to derive finite-sample convergence guarantees.
With PU learning, the aim is to learn a classifier f : X Ñ r0, 1s to approximate ppy “ `1|xq. We assume that we are given a loss function ` : r0, 1s ˆ Y Ñ R, such that `pz, yq is the loss incurred by predicting z when the true label is y. For a classifier f and a sampled set X “ tx1, x2, . . . , xnu, we let pL`pf ;Xq “
řn i“1 `pfpxiq,`1q{n denote the loss when predicting the samples as positive and
pL´pf ;Xq “ řn i“1 `pfpxiq,´1q{n the loss when predicting the samples as negative. For a sample set X each with true label y, we define 0-1 error as pEypf ;Xq “ řn i“1 I rypfpxiq ´ tq ď 0s {n for some predefined threshold t . Unless stated otherwise, the threshold is assumed to be 0.5.

heading: 4 Mixture Proportion Estimation
text: In this section, we introduce BBE, a new method that leverages a blackbox classifier f to perform MPE and establish convergence guarantees. All proofs are relegated to App. B. To begin, we assume access to a fixed classifier f . For intuition, you may think of f as a PvU classifer trained on some portion fo the positive and unlabeled examples. In Sec. 5, we discuss other ways to obtain a suitable classifier from PU data.
We now introduce some additional notation. Assume f transforms an input x P X to z P r0, 1s, i.e., z “ fpxq. For given probability density function p and a classifier f , define a function qpzq “ ş
Az ppxqdx, where Az “ tx P X : fpxq ě zu for all z P r0, 1s. Intuitively, qpzq captures the
cumulative density of points in a top bin, the proportion of input domain that is assigned a value larger than z by the classifier f in the transformed space. We now define an empirical estimator pqpzq given a
set X “ tx1, x2, . . . , xnu sampled iid from ppxq. Let Z “ fpXq. Define pqpzq “ řn i“1 I rzi ě zs {n. For each pdf pp, pn and pu, we define qp, qn and qu respectively.
Without any assumptions on the underlying distribution and the classifier f , we aim to estimate α˚ “ mincPr0,1s qupcq{qppcq with BBE. Later, under one mild assumption that empirically holds across numerous PU datasets, we show that α˚ “ α, i.e., α˚ matches the true mixture proportion α. Our procedure proceeds as follows: First, given a held-out dataset of positive (Xp) and unlabeled examples (Xu), we push all examples through the classifier f to obtain one-dimensional outputs Zp “ fpXpq and Zu “ fpXuq. Next, with Zp and Zu, we estimate pqp and pqu. Finally, we return the ratio pquppcq{pqpppcq at pc that minimizes the upper confidence bound (calculated using Lemma 1) at a pre-specified level δ and a fixed parameter γ P p0, 1q. Our method is summarized in Algorithm 1. For theoretical guarantees, we multiply the confidence bound term with 1` γ for a small positive constant γ. Refer to App. B.1 for details. We now show that the proposed estimator comes with the following guarantee:
Theorem 1. Define c˚ “ argmincPr0,1s qupcq{qppcq. For minpnp, nuq ě 2 logp4{δq qppc˚q and for every δ ą 0, the mixture proportion estimator pα defined in Algorithm 1 satisfies with probability 1´ δ:
|pα´ α˚| ď c qppc˚q
˜
d
logp4{δq nu `
d
logp4{δq np
¸
,
for some constant c ě 0.
Theorem 1 shows that with high probability, our estimate is close to α˚. The proof of the theorem is based on the following confidence bound inequality: Lemma 1. For every δ ą 0, with probability at least 1´ δ, we have for all c P r0, 1s∣∣∣∣ pqupcq
pqppcq ´ qupcq qppcq ∣∣∣∣ ď 1 pqppcq ˜ d logp4{δq 2nu ` qupcq qppcq d logp4{δq 2np ¸ .
Now, we discuss the convergence of our estimator to the true mixture proportion α. Since, pupxq “ αpppxq ` p1´ αqpnpxq, for all x P X , we have qupzq “ αqppzq ` p1´ αqqnpzq, for all z P r0, 1s. Corollary 1. Define c˚ “ argmincPr0,1s qnpcq{qppcq. Assume minpnp, nuq ě 2 logp4{δq qppc˚q . For every δ ą 0, pα (in Algorithm 1) satisfies with probability 1´ δ:
α´ c1 qppc˚q
˜
d
logp4{δq nu `
d
logp4{δq np
¸
ď pα , and
pα ď α` p1´ αqqnpc ˚q
qppc˚q ` c2 qppc˚q
˜
d
logp4{δq nu `
d
logp4{δq np
¸
,
for some constant c1, c2 ě 0.
Algorithm 2 PU learning with Conditional Value Ignoring Risk (CVIR) objective input : Labeled positive training data (Xp) and unlabeled training samples (Xu). Mixture proportion
estimate α. 1: Initialize a training model fθ and an stochastic optimization algorithm A. 2: Xn :“ Xu. 3: while training error pE`pfθ;Xpq ` pE´pfθ;Xnq is not converged do 4: Rank samples xu P Xu according to their loss values `pfθpxuq,´1q. 5: Xn :“ Xu,1´α where Xu,1´α denote the lowest ranked 1´ α fraction of samples. 6: Shuffle pXp, Xnq into B mini-batches. With pXip, Xinq we denote i-th mini-batch. 7: for i “ 1 to B do 8: Set the gradient ∇θ ” α ¨ pL`pfθ;Xipq ` p1´ αq ¨ pL´pfθ;Xinq ı
and update θ with algo. A. 9: end for
10: end while output : Trained classifier fθ
As a corollary to Theorem 1, we show that our estimator pα converges to the true α with convergence rate minpnp, nuq´1{2, as long as there exist a threshold cf P p0, 1q such that qppcf q ě p and qnpcf q “ 0 for some constant p ą 0. We refer to this condition as the pure positive bin property. Note that in a more general case, our bound in Corollary 1 captures the tradeoff due to the proportion of negative examples in the top bin (bias) versus the proportion of positives in the top bin (variance).
Empirical Validation We now empirically validate the positive pure top bin property (Fig. 2). We observe that as PvU training proceeds, purity of the top bin improves for a fixed fraction of samples in the top bin. Moreover, this behavior becomes more pronounced when learning a PvU classifier with the CVIR objective proposed in the following section.
Comparison with existing methods Due to the intractability of Blanchard et al. [6] estimator, Scott [39] implements a heuristic based on identifying a point on the AUC curve such that the slope of the line segment between this point and (1,1) is minimized. While this approach is similar in spirit to our BBE method, there are some striking differences. First, the heuristic estimator in Scott [39] provides no theoretical guarantees, whereas we provide guarantees that BBE will converge to the best estimate achievable over all choices of the bin size and provide consistent estimates whenever a pure top bin exists. Second, while both estimates involve thresholds, the functional form of the estimates are different. Corroborating theoretical results of BBE, we observe that the choices in BBE create substantial differences in the empirical performance as observed in App. C. We work out details of comparison between Scott [39] heuristic and BBE in App. C.
On the other hand, recent works [21, 20] that use PvU classifier for dimensionality reduction, discuss Bayes optimality of the PvU classifier (or its one-to-one mapping) as a sufficient condition to preserve α in transformed space. By contrast, we show that the milder pure positive bin property is sufficient to guarantee consistency and achieve Op1{ ? nq rates. Furthermore, in a simple toy setup in App. D, we show that even when the hypothesis class is well specified for PvN learning, it will not in general contain the Bayes optimal PvU classifier and thus PvU training will not recover the Bayes-optimal scoring function, even in population. Contrarily, we show that any monotonic mapping of the Bayesoptimal PvU scoring function induces a positive pure top bin property. We leave further theoretical investigations concerning conditions under which a pure positive top bin arises to future work.

heading: 5 PU-Learning
text: Given positive and unlabeled data, we hope not only to identify α, but also to obtain a classifier that distinguishes effectively between positive and negative samples. In supervised learning with separable data (e.g., cleanly labeled image data), overparameterized models generalize well even after achieving near-zero training error. However, with PvU training over-parameterized models can memorize the unlabeled positives, assigning them confidently to the negative class, which can severely hurt generalization on PN data [43]. Moreover, while unbiased losses exist that estimate the PvN loss given PU data and the mixture proportion α, this unbiasedness only holds before the loss is optimized, and becomes ineffective with powerful deep learning models capable of memorization.
Algorithm 3 Transform-Estimate-Discard (TED)n
input : Positive data (Xp) and unlabeled samples (Xu). Hyperparameter W, δ. 1: Initialize a training model fθ and an stochastic optimization algorithm A. 2: Randomly split positive and unlabeled data into training X1p , X 1 u and hold-out set (X 2 p , X 2 u).
3: X1n :“ X1u. {// Warm start with domain discrimination training} 4: for i “ 1 to W do 5: Shuffle pX1p , X1nq into B mini-batches. With pX1p i , X1n
iq we denote i-th mini-batch. 6: for i “ 1 to B do 7: Set the gradient ∇θ ” pL`pfθ;X1p iq ` pL´pfθ;X1n iq ı
and update θ with algorithm A. 8: end for 9: end for
10: while training error pE`pfθ;X1pq ` pE´pfθ;X1nq is not converged do 11: Estimate pα using Algorithm 1 with pX2p , X2uq and fθ as input. 12: Rank samples xu P X1u according to their loss values lpfθpxuq,´1q. 13: X1n :“ X1u,1´pα where X1u,1´pα denote the lowest ranked 1´ pα fraction of samples. 14: Train model fθ for one epoch on pX1p , X1nq as in Lines 4-7. 15: end while output : Trained classifier fθ
A variety of heuristics, including ad-hoc early stopping criteria, have been explored [20], where training proceeds until the loss on unseen PU data ceases to decrease. However, this approach leads to severe under-fitting (results in App. G.2). On the other hand, by regularizing the loss function, nnPU Kiryo et al. [23] mitigates overfitting issues due to memorization.
However, we observe that nnPU still leaves a substantial accuracy gap when compared to a model trained just on the positive and negative (from the unlabeled) data (ref. experiment in App. G.1). This leads us to ask the following question: can we improve performance over nnPU of a model just trained with PU data and bridge this gap? In an ideal scenario, if we could identify and remove all the positive points from the unlabeled data during training then we can hope to achieve improved performance over nnPU. Indeed, in practice, we observe that in the initial stages of PvU training, the model assigns much higher scores to positives than to negatives in the unlabeled data (Fig. 2(b)).
Inspired by this observation, we propose CVIR, a simple yet effective objective for PU learning. Below, we present our method assuming an access to the true MPE. Later, we combine BBE with CVIR optimization, yielding (TED)n, an alternating optimization that significantly improves both the BBE estimates and the PvU classifier.
Given a training set of positives Xp and unlabeled Xu and the mixture proportion α, we begin by ranking the unlabeled data according the predicted probability (of being positive) by our classifier. Then, in every epoch of training, we create a (temporary) set of provisionally negative samples Xn by removing α fraction of the unlabeled samples currently scored as most positive. Next, we update our classifier by minimize the loss on the positives Xp and provisional negatives Xn by treating them as negatives. We repeat this procedure until the training error on Xp and Xn converges. Likewise nnPU, note that this procedure does not need early stopping. Summary in Algorithm 2.
In App. E, we justify our loss function in the scenario when the positives and negatives are separable. For a more general scenario, we show that each step of our alternating procedure in CVIR cannot increase the population loss and hence, CVIR can only improve (or plateau) after every iteration.
(TED)n Integrating BBE and CVIR We are now ready to present our algorithm Transfer, Estimate and Discard (TED)n that combines BBE and CVIR objective.
First, we observe the interaction between BBE and CVIR objective. If we have an accurate mixture proportion estimate, then it leads to improved classifier, in particular, we reject accurate number of prospective positive samples from unlabeled. Consequently, updating the classifier to minimize loss on positive versus retained unlabeled improves purity of top bin. This leads to an obvious alternating procedure where at each epoch, we first use BBE to estimate pα and then update the classifier with CVIR objective with pα as input. We repeat this until training error has not converged. Our method is summarized in Algorithm 3.
Note that we need to warm start with PvU (positive versus negative) training, since in the initial stages mixture proportion estimate is often close to 1 rejecting all the unlabeled examples. However, in next section, we show that our procedure is not sensitive to the choice of number of warm start epochs and in a few cases with large datasets, we can even get away without warm start (i.e., W “ 0) without hurting the performance. Moreover, recall that our aim is to distinguish positive versus negative examples among the unlabeled set where the proportion of positives is determined by the true mixture proportion α. However, unlike CVIR, we do not re-weight the losses in (TED)n. While true MPE α is unknown, one natural choice is to use the estimate pα at each iteration. However, in our initial experiments, we observed that re-weighted objective with estimate pα led to comparatively poor classification performance due to presence of bias in estimate pα in the initial iterations. We note that for deep neural networks (for which model mis-specification is seldom a prominent concern) and when the underlying classes are separable (as with most image datasets), it is known that importance weighting has little to no effect on the final classifier [7]. Therefore, we may not need importancereweighting with (TED)n on separable datasets. Consequently, following earlier works [23, 11] we do not re-weight the loss with our (TED)n procedure. In future work, a simple empirical strategy can be explored where we first obtain an estimate of pα by running the full (TED)n procedure till convergence and then discarding the (TED)n classifier, we use estimate pα to train a fresh classifier with CVIR procedure.
Finally, we discuss an important distinction with Dedpul which is also an alternating procedure. While in our algorithm, after updating mixture proportion estimate we retrain the classifier, Dedpul fixes the classifier, obtains output probabilities and then iteratively updates the mixture proportion estimate (prior) and output probabilities (posterior). Dedpul doesn’t re-train the classifier.

heading: 6 Experiments
text: Having presented our PU learning and MPE algorithms, we now compare their performance with other methods empirically. We mainly focus on vision and text datasets in our experiments. We include results on UCI datasets in App. G.7.
Datasets and Evaluation We simulate PU tasks on CIFAR-10 [24], MNIST [25], and IMDb sentiment analysis [32] datasets. We consider binarized versions of CIFAR-10 and MNIST. On CIFAR-10 dataset, we consider two classification problems: (i) binarized CIFAR, i.e., first 5 classes vs rest; (ii) Dog vs Cat in CIFAR. Similarly, on MNIST, we consider: (i) binarized MNIST, i.e., digits 0-4 vs 5-9; (ii) MNIST17, i.e., digit 1 vs 7. IMDb dataset is binary. For MPE, we use a held out PU validation set. To evaluate PU classifiers, we calculate accuracy on held out positive versus negative dataset. For baselines that suffer from issues due to overfitting on unlabeled data, we report results with an oracle early stopping criterion. In particular, we report the accuracy averaged over 10 iterations of the best performing model as evaluated on positive versus negative data. Note that we use this oracle stopping criterion only for previously proposed methods and not for methods proposed
in this work. This allows us to compare (TED)n with the best performance achievable by previous methods that suffer from over-fitting issues. With nnPU and (TED)n, we report average accuracy over 10 iterations of the final model.
Architectures For CIFAR datasets, we consider (fully connected) multilayer perceptrons (MLPs) with ReLU activations, all convolution nets [40], and ResNet18 [19]. For MNIST, we consider multilayer perceptrons (MLPs) with ReLU activations For the IMDb dataset, we fine-tune an offthe-shelf uncased BERT model [10, 42]. We did not tune hyperparameters or the optimization algorithm—instead we use the same benchmarked hyperparameters and optimization algorithm for each dataset. For our method, we use cross-entropy loss. For uPU and nnPU, we use Adam [22] with sigmoid loss. We provide additional details about the datasets and architectures in App. F.
Mixture Proportion Estimation First, we discuss results for MPE (Table 1). We compare our method with KM2, TiCE, DEDPUL, AlphaMax and EN. Following earlier works [20, 35], we reduce datasets to 50 dimensions with PCA for KM2 and TiCE. We use existing implementation for other methods2. For BBE, DEDPUL and Alphamax, we use the same PvU classifier as input. On CIFAR datasets, convolutional classifier based estimators significantly outperform KM2 and TiCE. In contrast, the performance of KM2 is comparable to DEDPUL on MNIST datasets. On all datasets,
2DEDPUL: https://github.com/dimonenka/DEDPUL, KM: https://web.eecs.umich.edu/~cscott/code.html#kmpe, TiCE: https://dtai.cs.kuleuven.be/software/tice, and AlphaMax: https://github.com/Dzeiberg/AlphaMax
(TED)n achieves lowest estimation error. With the same blackbox classifier obtained with oracle early stopping, BBE performs similar or better than best alternate(s). Since overparamterized models start memorizing unlabeled samples negatives, the quality of MPE degrades substantially as PvU training proceeds for all methods but (TED)n as in Fig. 3 (epoch-wise results for on other tasks in App. G.3).
Classification with known MPE Now, we discuss results for classification with known α. We compare our method with uPU, nnPU3, DEDPUL and PvU training. Although, we solve both MPE and classification, some comparison methods do not. Ergo, we compare our classification algorithm with known MPE (Algorithm 2).
To begin, first we note that nnPU and PvU training with CVIR doesn’t need early stopping. For all other methods, we report the best performance dictated by the aformentioned oracle stopping criterion. On all datasets, PvU training with CVIR leads to improved classification performance when compared with alternate approaches (Table 2). Moreover, as training proceeds (Fig. 3), the performance of DEDPUL, PvU training and uPU substantially degrade. We repeated experiments with the early stopping criterion mentioned in DEDPUL (App. G.2), however, their early stopping criterion is too pessimistic resulting in poor results due to under-fitting.
Classification with unknown MPE Finally, we evaluate (TED)n, our alternating procedure for MPE and PU learning. Across many tasks, we observe substantial improvements over existing methods. Note that these improvements often are over an oracle early stopping baselines highlighting significance of our procedure.
In App. G.5, we show that our procedure is not sensitive to warm start epochs W, and in many tasks with W “ 0, we observe minor-to-no differences in the performance of (TED)n. While for the experiments in this section, we used fixed W “ 100, in the Appendix we show behavior with varying W. We also include ablations with different mixture proportions α.

heading: 7 Conclusion and Future Work
text: In this paper, we proposed two practical algorithms, BBE (for MPE) and CVIR optimization (for PU learning). Our methods outperform others empirically and BBE’s mixture proportion estimates leverage black box classifiers to produce (nearly) consistent estimates with finite sample convergence guarantees whenever we possess a classifier with a (nearly) pure top bin. Moreover, (TED)n combines our procedures in an iterative fashion, achieving further gains. An important next direction is to extend our work to the multiclass problem [38], bridging work on label shift and PU learning. Here, we imagine that a deployed k-way classifier may encounter not only label shift among previously seen classes ([29, 17]) but also, potentially, instances from one previously unseen class. We also plan to investigate distributional properties under which we can hope to reliably or approximately satisfy the pure positive bin property with an off-the-shelf classifier trained on PvU data. While we improve significantly over previous PU methods, there is still a gap between (TED)n’s performance and PvN training. We hope that our work can open a pathway towards further narrowing this gap.

heading: Acknowledgements
text: We thank anonymous reviewers for their feedback during NeurIPS 2021 review process. This material is based on research sponsored by Air Force Research Laboratory (AFRL) under agreement number FA8750-19-1-1000. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation therein. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of Air Force Laboratory, DARPA or the U.S. Government. SB acknowledges funding from the NSF grants DMS-1713003, DMS-2113684 and CIF-1763734, as well as Amazon AI and a Google Research Scholar Award. ZL acknowledges Amazon AI, Salesforce Research, Facebook, UPMC, Abridge, the PwC Center, the Block Center, the Center for Machine Learning and Health, and the CMU Software Engineering Institute (SEI) via Department of Defense contract FA8702-15-D-0002, for their generous support of ACMI Lab’s research on machine learning under distribution shift.
3uPU and nnPU: https://github.com/kiryor/nnPUlearning

Review summaries:
The paper proposes two methods for PU learning. First, a method for estimating the fraction of positives among unlabeled examples, named Best Bin Estimation (BBE). Secondly, an approach for PU learning called Conditional Value Under Optimism (CVuO). The BBE works on top of the decision score of a given pretrained classifier. The score is used to find a region of the instance space with the minimal ratio of the portion of unlabeled and the portion of positive examples. The ratio is an upper bound on the fraction of positives being estimated. In case there exists a region populated only by positive examples (the condition called pure positive bin property), the bound is tight. The authors provide a finite sample bound for their estimator. The CVuO turns any supervised method to PU learning algorithm. The approach assumes the fraction of positive examples to be known. The idea is to rank the unlabeled examples by a score of a pretrained classifier and remove it the fraction of positive examples. The remaining examples are taken as true negatives and then used with the true positives to re-train the classifier. The procedure is repeated until convergence. Besides, the authors propose an algorithm, called $TED^n$, combining BBE and CVuO. The methods are empirically shown to outperform several recent methods on semisynthetic problems created from CIFAR, MNIST, and IMDB datasets. 

This paper tackles the well known problem of mixture proportion estimation and Positive-Unlabelled (PU) learning. The authors propose a a (new) estimator for MPE based on the assumption of a PU classifier having a "pure" top bin. The authors then develop a novel  iterative outlier-removal-like algorithm for learning a classifier separating the positives and negatives from PU data assuming access to the true MPE. Finally, they combine these two approaches to create a novel alternating algorithm that estimates MPE based on a current PvN classifier, and use the MPE estimate to learn a better PvN classifier from PU data.

This paper proposes a unified framework for learning from positive-unlabeled (PU) data, including BBE for mixture proportion estimation (MPE)  and CVuO for PU learning. In the literature there are important and elegant works exists that analyze the consistency of the mixture proportion without the irreducibility assumption. They formalize their analyses based on an assumption that the percentage of a blackbox classifier's output for positive samples greater than a fixed value is higher than that for negative samples. I suggest a brief introduction of the conditions that this assumption satisfies, maybe the inductive bias or something, while intuitively such an assumption is quite reasonable. They provide finite sample guarantee for BBE and also empirically verify it. In the PU learning stage, the authors use an iterative manner to progressively identify and remove all the positive points from the unlabeled data during training. This is again quite a reasonable way of thinking because of the memorization of neural networks. The combination of BBE and CVuO is called (TED)^n. The authors provide a lot of supportive experiments to verify their methods.

This paper targets the problems of mixture proportion estimation and PU learning. The authors propose two simple but effective methods to address two problems. Also, the combination of two methods is proposed to train an accurate binary classifier under mild conditions. A series of experiments are conducted to verify the effectiveness of the proposed method.