Mixture Proportion Estimation and PU Learning:A Modern Approach
Authors: Saurabh Garg
Yifan Wu
Alex Smola
Sivaraman Balakrishnan
Zachary Chase Lipton
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: PU learning
Mixture Proportion Estimation

Abstract: Given only positive examples and unlabeled examples (from both positive and negative classes), we might hope nevertheless to estimate an accurate positive-versus-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)$^n$, alternates between the two procedures, significantly improving both our mixture proportion estimator and classifier

Mixture Proportion Estimation and PU Learning: A Modern Approach
Saurabh Garg', Yifan Wu', Alex Smola', Sivaraman Balakrishnan', Zachary C. Lipton' CCarnegie Mellon University
2 Amazon Web Services
Abstract
Given only positive examples and unlabeled examples (from both positive and negative classes), might hope nevertheless estimate accurate positive- versus-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- -iienn such an estimate, learning the desired positive-versus-nege negatiiv 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 model to cleanly separate out small subset of positive examples. Our final algorithm (TED)", alternates between the two procedures, significantly improving both our mixture proportion estimator and classified]
Introduction
When deploying k-way classifiers in the wild, what do when confronted with data from previously unseen class (k + 1)? Theory dictates that learning under distribution shift 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 estimate its prevalence. Similarly, naturalists can discover 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
29
ie.. that while the class balance p(y) can change, the class conditional distributions p(a|y) do not. Moreover, we might begin by focusing 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 g 27 and has typically been broken down into subtasks: (i) Mixture Proportion Estimation (MPE) where estimate o, the fraction of positives among the unlabeled examples; and (ii) PU-learning where this estimate is incorporated into scheme for learning a Dositiie-versuu-Negaaiv (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 not necessarily negative. This setup has also been motivated by protein and
Code available at httt:://gghiua...ommmm/maaab/./p
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.0
1.0
80
0.8
75
0.6
Accuracy
70
0.6
Litimate
65
0.4
0.4
60
0.2
True MPE
55
(TED)*
Classification
X
BBE
MPE
50
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
100
200
300
400
500
fraction of samples in top bin
Epochs
Figure 1: Illustration of proposed methods. (left) Estimate of with varying fraction of unlabeled examples the top bin. The shaded region highlights the upper and lower confidence bounds. BBE selects the top bin that minimizes the upper confidence bound. (right) Accuracy and MPE estimate as training proceeds. Till 100-th epoch (vertical line), we perform PyU training, i.e., warm start for (TED)". Post 100-th epoch, continue with both (TED)" and PvU training. Note that (TED)" improves both classification accuracy and MPE compared to PyU training. Results with Resnet-1 on Sinary-CIFAR For details and comparisons with other methods, see Sec. 6
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.
gene identification 16
Many methods have been proposed for both MPE 16
12
39
35
36 20 and PU-learning [14]
11 23). However, classical MPE methods break down nigh-dimensional settings (35] or yield
estimators whose accuracy depends on restrictive conditions 12 (3]. 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 [6] suggest training a classifier to distinguish positive from unlabeled data followed by a rescaling procedure. Du Plessis al. [1] suggest unbiased risk estimation framework for PU learning. However, these methods fail badly when applied with model classes capable of overfitting and thus implementations high-dimensional datasets rely 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 under mild assumptions and admits finite-sample statistical guarantees achiev- ing the desired O(1/vm rates; and (ūi learning with the Conditional Value Ignoring Risk (CVIR) objective, which discards the highest loss â fraction examples on each training epoch, removing the incentive to overfit to the unlabeled positive examples. Both methods simple to implement, com- patible with arbitrary hypothesis classes (including deep networks), and dominate existing methods in experimental evaluation. Finally, we combine the in iterated Transform-Estee Sisitmate-Discard (TED)" framework that significantly improves both MPE estimation error and classifier error.
We build on label shift methods 29
34 17, that leverage black-box classifiers to reduce dimensionality, estimating target label distribution as a functional source and target push- forward distributions. While label shift methods rely on classifiers trained to separate previously seen classes, BBE is able to exploit a Positive-versuu uenttiveeversu--nnlallleedd (PvU) target classifier, which gives each input score indicating how likely it is to be 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
3
2
BBE works because in practice, for many datasets, PvU classifiers, even when uncalibrated, produce outputs with near monotonic calibration diagrams. Higher scores correspond to higher proportion of positives, and when the positive data contains a separable sub-domain, i.e., a region the input space where only the positive distribution has support, classifiers often exhibit threshold above which the top hin contains mostly positive examples. We show that the existence of (nearly) pure top bin is sufficient for BBE to produce (nearly) consistent estimate â 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 mild and frequently hold in practice, and establish the outperformance of BBF, CVIR, and (TED)" over the previous state of the art. We first motivate BBE by demonstrating that in practice PvU classifiers tend isolate 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 learnigg setup and demonstrating the superior performance of BBE and PU-leamiig with the CVIR objective. Moreover, we show that (TEDy", which combines the two in an iterative fashion, improves significantly over previous methods across several architectures on a range of image and text datasets.
2 Related Work
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 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 estimator that converges to the true a. While their estimator can converge arbitrarily slowly, Scott [39] showed faster convergence (O(1/) R)) under stronger conditions. Unfortunately, despite its appealing theoretical properties Blanchard et al. 66's 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 al. (35) proposed the first computationally feasible algorithm for MPE with convergence guarantees to the true proportion. Their method KM, requires embedding distributions onto RKHS. However, their estimator underperforms
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-dimensiona settings.
In the most similar works, Jain et al. 21 and Ivanov (20 explore dimensionality reduction using a PvU classifier. Both methods estimate a through procedure operating on the PvU classifier's 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 different estimator. Moreover while both papers state that their method require the Bayes-optimal PvU classifier to identify a in the transformed space, we prove that even when hypothesis class is well specified for PvN learning, PvU training can fail 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 similar 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 a, Elkan and Noto [16] propose a transformation via Bayes rule obtain the PvN classifier. They also propose a weighted objective, with weights given by the PyU classifier. Other propose unbiased risk estimators [14 [T] which require the mixture proportion a. Du Plessis al. [14 proposed an unbiased estimator with non-convex loss functions satisfying a specific symmetric condition, and subsequently Du Plessis et al. [II] generalized it to convex loss functions (denoted uPU in our experiments). in our experiments. Noting the problem of overfitting in modern overpa- rameterized models, Kiryo et al. (33 propose a regularized extension that clips the loss on unlabeled data to zero. This is considered the current state-of-ther -hetherrrt 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-processi
procedure, they rely on good domain discriminator classifier 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.
3

---

Algorithm Best Bin Estimation (BBE)
input Validation positive (Xp) and unlabeled (Xw) samples. Blackbox model classifier ʃ X:X [0. 1]. Hyperparameter 0 < ó, <1
1: Zp. Zu f(Xp), f().).
2: (u(2), (p()) Zz,ez [[,as] E,,ez, [=(30]]
for all 2 E [o, 1].
nu
))
3: Estimate 2 = arg arg cfja]]
Galc) (p(0)
+ 1+7 Tp(e)
log(1/62 2n
log log(1/6) 2ny
â = T. ( 4p (c)
output
3 Problem Setup
By |I-1 and (, we denote the Euclidean norm and inner product, respectively. For vector v R4, we use to denote its 1uhh entry, and for an event E, we let [[E] denote the binary indicator of the event. By |A], we denote the cardinality of set A. Let E Rd be the input space and y = {-1, + be the output space. Let : y [0, 1J be the underlying joint distribution and let p denote its corresponding density.
Let P. and P., be the class-conditional distributions for positive and negative class and Pp(x) p(zly = +1) and Pa (x) = p(aly -1) ) be the corresponding class-conditiona. densities. P.. denotes the distribution of the unlabeled data and Pu denotes its density. Let a [0. 1] be the fraction of positives among the unlabeled population, i.e., P., = aPp p + (1 a)P, When learning from positive and unlabeled data, we obtain i.i.d. samples from the positive (class-conditional) distribution, which we denote as X, T2,, Ing ~ P" and i.i.d samples from unlabeled distribution as +n.)
X, = (In,+ +1 +2
P
MPE is the problem of estimating a. Absent assumptions on Pp, Pn. and Pa. the mixture proportion
is not identifiable (6) Indeed, if Pf aP, + P n. then any alternate decomposition of the form P.. (a- P, (1 a + +-) P for 7 E (0, and P", (1 + 7) -'PP + (011-0) P.)). is also valid. Since we do not observe samples from the distribution PR. the parameter a is not identifiable. Blanchard et al. [6] formulate
irreducibility condition under which identifiable. Intuitively, the condition restricts Pa to ensure that it can not be a (non-trivial) mixture of Pp and any other distribution. While this irreducibility condition makes a 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 a identifiable and allows us to derive finie--smple convergence guarantees.
With PU learning, the aim is to learn classifier x - [0, 1] to approximate p(y +1/)) We assume that we are given a loss function é: [o, 1] x y - R, such that f(2,y) is the loss incurred by predicting z when the true label is y. For classifier f and sampled set X {x11 #2. 3n let ( ((
denote the loss when predicting the samples as positive and (x: (((=),,)))))))) the loss when predicting the samples as negative. For sample set X each with true label y, we define 0-1 error (f: Σ [2)(f(x)) t) < 0]/n /n for some predefined threshold f. Unless stated otherwise, the threshold is assumed to be 0.5.
4 Mixture Proportion Estimation
In this section, 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 fixed classifier For intuition, you may think of 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 e X' to 2 E [o, 1]. i.c., f(x). For given probability density function and classifier f. define function ((>) = SA, p(r)dd,, where A, = {x E X' fxx) > 2} for all z E [o, 1]. Intuitively, <(>) captures the cumulative density of points in top bin, the proportion of input domain that is assigned value larger than by the classifier in the transformed space. We now define empirical estimator @(2) given

---

Epoch
Roach
oe
Purtyy of top big
0.9
Eoach 105
Boach 302
0.8
Output Prob
Output Prob Epoch 1060
Epoch 100
6.6
Density
Densityy
155
20
04 Output Prop
0.6
samples top
Output Prob
(a)
(b)
Figure 2: (a) Purity and size (in terms of fraction of unlabeled samples) in the top bin and (b)
Distribution of predicted probabilities (of being positive) for unlabeled training data as training proceeds with (TED)". Results with ResNet-18 on binary-CIFAR, As in Fig, [ App. G.4 we show that as PvU training proceeds, the purity top bin degrades and the distribution of predicted probabilities of positives and negatives become less and less separable.
we fix W at 100. In
set X {21, (2, 22, In sampled iid from p(x). Let Z = f(X). Define @(=) = >"_ 1[ 3 z| For each pdf Pp. Pn and Pus define qp. On and qu respectively.
Without any assumptions on the underlying distribution and the classifier f. we aim to estimate (c) with BBE. Later, under one mild assumption that empirically holds across numerous PU datasets, we show that a* i.e., a* matches the true mixture proportion
a* min 10. qu (u(c)/gp(c)
Our procedure proceeds as follows: First, given held-out dataset of positive (Xpp) and unlabeled examples (Xw). we push all examples through the classifier f to obtain one-dimensional outputs Z, - (Xx) and Z, = f(X.). Next, with Z, and Z.. we estimate G and G... Finally, return the ratio (c) [ at that minimizes the upper confidence bound (calculated using Lemma T at pre-specified level 8 and fixed parameter y E (0, 1). Our method summarized in Algorithm I For theoretical guarantees. we multiply the confidence bound term with 1 + for small positive constant y. Refer to App. for details. We now show that the proposed estimator comes with the following guarantee:
Theorem 1. Define c* arg ce (..lc)//pl For min(np; nu) > log(4/8) (c( and for every
8 the mixture proportion estimator defined Algorithm 7 satisfies with probability 1 5:
(v
log(4/8)
log(4/0)
ja - a 1=a1
(x(c*)
Thu
Ppp
for some constant c. O.
Theorem shows that with high probability, estimate is close to a* The proof of the theorem is based on the following confidence bound inequality:
Lemma 1. For every 8 > O, with probability at least 1 - 8, we have for all c e [o. 1]
(c) (p)
(c)
(og(4/8) qu(e)
1og(4/8)
(p(c)
(p(()
2n
(p(c)
2mp
Now, we discuss the convergence of our estimator to the true mixture proportion a. Since, Pu(x) = (2p(2) + (1 a. (a)) for all X, have (=(22) agp(2) (1 a)),(z), for all [0, 1].
Corollary 1. Define
arg min 9n (c) (c). Assume min (np, nw)
2log(4/6) For every qp(ck)
8 > 0, (in Algorithm
T satisfies with probability -5:
log(4/8)
1og(4/8)
& ā and
pp (p*)))
nu
np
In (x ap(c7
C2
log(4/0)
(og(4/0)
à E a
pp(c*)
for some constant C1, C2 0.
5

---

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 a.
1: Initialize training model fo and an stochastic optimization algorithm A.
2: X, :=x.-
3: while training error E (fo: xp) + 8 (fo: ) is not converged do
4: Rank samples Iie x, according to their loss values { ((fo(r)),
5: Xa := Xu,1-a where Xu,1-a denote the lowest ranked a fraction of samples.
6: Shuffle (Xp. xx) into B batche. With (Xp: ) we denote i-th mini-batcle
7: for = 1 to B do
8: Set the gradient Vo [a- T. x -0)) a) (Jo; xx) and update with algo. A.
9: end for
end while
output Trained classifier fe
As corollary to Theorem 1 we show that our estimator â converges to the true with convergence rate min(np, m/, as long as there exist a threshold oy E (0. 1) such that qp(cy) > cp and In (cy) for some constant 6p > 0. We refer to this condition as the pure positive bin property.
Note that in a more general case, our bound in Corollary cappuress 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. D. 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 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 similar 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 pure top bin exists. Second, while both estimates involve thresholds, the functional form the estimates different. Corroborating theoretical results of BBE, we observe that the choices in BBE create substantial differences 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 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 transformed space. By contrast, we show that the milder pure positive bin property is sufficient to guarantee consistency and achieve O(1/v/m rates. Furthermore, in simple toy setup in App. D we show that even when the hypothesis class is well specified for PvN learning, will not in general contain the Bayes optimal PvU classifier and thus PyU training will not recover the Bayes-optimal scoring function, even in population. Contrarily, we show that any monotonic mapping of the Bayes- optimal 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.
5 PU-Learning
Given positive and unlabeled data, we hope not only to identify a, 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 PyU training per-parraeterized 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 a, this unbiasedness only holds before the loss optimized, and becomes ineffective with powerful deep learning models capable of memorization.

---

Algorithm 3 Transforn-Essimatt-Diies
(TED)"
input Positive data (Xp) and unlabeled samples (X..). Hyperparameter W.8.
1: Initialize a training model fo and an stochastic optimization algorithm A.
2: Randomly split positive and unlabeled data into training X X, and hold-out set (X2: X23..
3: X; := :-x!-
(// Warm start with domain discrimination training]
4: for i= 1 W do
5: Shuffle (X] X,)) into B mini-batches. With (X7² xx.)) we denote i-th mini-batch.
6: for 1 to B do
7: Set the gradient Vo (T.t(Jo: X²²) + Z. (Jo X!') and update 0 with algorithm A.
8: end for
9:
end for
10: while training error E. Xp): x E- (fo; is not converged do
Estimate ā using Algorithm [ with (X2, X and fo as input.
12: Rank samples di E x according to their loss values ([fo(zu),-1)
13:
X == X 1-1 where X u- denote the lowest ranked 1 â fraction of samples.
14:
Train model fo for one epoch on (X), X as in Lines 4-7.
15:
end while
output Trained classifier Jo
A variety of heuristics, including ad-hoc early stopping criteria, have been explored 20 where training proceeds until the loss unseen PU data ceases to decrease. However, this approach leads to severe under-fitting (results in App. G.2p. 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.I. 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 idcal 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, 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. bb))
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)", an alternating optimization that significantly improves both the BBE estimates and the PvU classifier.
Given a training set of positives X, and unlabeled X,, and the mixture proportion o, 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 (temporary) set of provisionally negative samples X₂, by removing fraction of the unlabeled samples currently scored most positive, Next, we update our classifier by minimize the loss on the positives Xp and provisional negatives X,, by treating them as negatives. We repeat this procedure until the training error on Xp and X,, converges. Likewise nnPU, note that this procedure does not need early stopping. Summary in Algorithm
In App. E justify our loss function in the scenario when the positives and negatives 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)" Integrating BBE and CVIR We are now ready to present our algorithm Transfer, Estimate and Discard (TED)" 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 minimize loss on positive versus retained unlabeled improves purity of top bin. This leads to an obvious alternating procedure where each epoch, we first use BBE to estimate â and then update the classifier with CVIR objective with & as input. We repeat this until training enror has not converged. Our method is summarized in Algorithm

---

1.0
85
80
Mixture Proportion
75
Accuracy
70
65
0.4
60
ITEP
55
0.2
REDPUL
Apphamms le")
50
Pv0
Tuc MPE
0.0
500
1000
1500
2000
500
1000
1500
2000
Epochs
Epochs
Epoch wise results with ResNet- 18 trained on binary-CIFAR when a is 0.5. Parallel results on other datasets and architectures in App. G.3 For both classification and MPE, (TED)" substantially improves over existing methods. Additionally, (TED)" maintains the superior performance till convergence removing the need for early stopping. Results aggregated over 3 seeds.
Figure 3:
Note that need to warm start with PvU (positive versus negative) training, since in the initial stages mixture proportion estimate often close rejecting all the unlabeled examples. However, in next section, show that procedure is not sensitive to the choice of number of warm start epochs and 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 aim 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, do not re- weight the losses in (TEDY". While true MPE a is unknown, one natural choice is to use the estimate â at each iteration. However, in our initial experiments, we observed that re-weighted objective with estimate led comparatively poor classification performance due to presence of bias in estimate in the initial iterations. We note that for deep neural networks (for which model nis-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 no effect the final classifier 77. Therefore, we may not need importance- reweighting with (TED)" on separable datasets. Consequently, following earlier works (23 [1] we do not re-weight the loss with our (TED)" procedure. future work, a simple empirical strategy can be explored where we first obtain an estimate of & by running the full (TED)" procedure till convergence and then discarding the (TED)" classifier, we use estimate train a fresh classifier with CVIR procedure.
Finally, discuss important distinetion 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 't re-train the classifier.
6 Experiments
Having presented our PU learning and MPE algorithms, we now compare their performance with other methods empirically. mainly focus on vision and text datasets in our experiments. We include results 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-I0 and MNIST. On CIFAR-10 dataset, we consider two classification problems: (i) binarized CIFAR, i.c., 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 vs 7. IMDb dataset is binary. For MPE, we use 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 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 this oracle stopping criterion only for previously proposed methods and not for methods proposed

---

Dataset
Model
(TED)"
BBE*
DEDPUL*
AlphaMax*
EN
KM2 TiCE
ResNet
0.026
0.091
0.091
0.125
0.192
Binarized
All Conv
0.042
0.037
0.052
0.09
0.221
0.168
0.251
CIFAR
MLP
0.225
0.177
0.138
0.3
0.372
CIFAR Dog
ResNet 0.078
0.176
0.170
0.17
0,226
0.331
0.286
All Conv
0.066
0.128
0.115
0.19
0.250
Binarized MNIST
MLP 0.024
0.032
0.031
0.090
0.080
0.029
0.056
MNIST17
MLP
0.003
0.023
0.021
0.075
0.028
0.022
0.043
IMDb
BERT
0.008
0.011
0.016
0.07
0.12
Table 1:
Absolute estimation error when is 0.5. denote oracle early stopping as defined in Sec. (TED)" significantly reduces estimation error when compared with existing methods. Results reported by aggregating absolute eтror over 10 epochs and 3 seeds. For aggregate numbers with standard deviation see 6.p G.6
(TED)" (unknown o)
CVIR (known a)
PvU (known
DEDPUL (unknown o.)
nnPU (known ())
uP (known a)
Dataset
Model
ResNet
82.7
82.3
76.9
77.1
77.2
76.7
Binarized
All Conv
77.9
78.1
75.8
77.1
73.4
72.5
CIFAR
MLP
64.2
66.9
61.6
62.6
63.1
64.0
CIFAR Dog
ResNet
75.2
73.3
67.3
67.0
71.8
Cat
All Conv
73.0
71.7
70.5
69.2
67.9
67.5
Binarized
MLP
95.6
96.3
94.2
94.8
96.1
95.2
MNIST
MNIST17
MLP
98.7
98.7
96.9
97.7
98.4
98.4
IMDb
BERT
87.6
87.4
86.1
87.3
86.2
85.9
Table 2: Accuracy for PyN classification with PU learning. "*" denote oracle early stopping as defined in Sec. 6 Results reported by aggregating over 10 epochs and seeds. Both CVIR (with known MPE) and (TED)" (with unknown MPE) significantly improve over previous baselines with oracle early stopping and known MPE. For aggregate numbers with standard deviation App. G.6
in this work. This allows us compare (TED)" with the best performance achievable by previous methods that suffer from over-fitting issues. With nnPU and (TED)", 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, consider multilayer perceptrons (MLPs) with ReLU activations For the IMDb dataset, we fine-tune an off- the-shelf uncased BERT model [T0 42
We did not tune hyperparameters algorithm algorithm-instead instead we use the same benchmarked hyperparameters and optimization algorithm for each dataset. For our method, we cross-entropy loss. For uPU and nnPU, use Adam [22 with sigmoid loss. We provide additional details about the datasets and architectures App.
the optimization
Mixture Proportion Estimation
First, discuss results for MPE (Table D We compare
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 m 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,
DEEPUUL: http://ggiiia..cmmmmmmooe//DDDDD KM: https://webbeee TiCE: https://dtai.cc cs www.wweeebb/eeeeetwterreeeeeeeee and AlphaMax: https///gitub.com///eee/rrg////

---

(TED)" achieves lowest estimation error. With the same blackbox classifier obtained with oracle early stopping. BBE performs similar or better than best alternatess). Since overparamterized models start memorizing unlabeled samples negatives, the quality of MPE degrades substantially as PvU training proceeds for all methods but (TED)" as Fig. repoch-wise results for on other tasks in App. G.3)
Classification with known MPE Now, we discuss results for classification with known a. We compare our method with uPU, nnP 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 '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 (Ap). however, their early stopping criterion is too pessimistic resulting in poor results due to under-fitling.
Classification with unknown MPE Finally, we evaluate (TED)", 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 O, we observe minor-to-no differences in the performance of (TED)". 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
7 Conclusion and Future Work
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)" 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 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)"s performance and PvN training. We hope that our work can open pathway towards further narrowing this gap.
seen classes ([29)
Acknowledgements
We thank anonymous reviewers for their feedback during NeurlPS 2021 review process. This material is based on research sponsored by Air Force Research Laboratory (AFRL) under agreement number 148750-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 and CIF- CIF-1763734, as well as Amazon Al and Google Research Scholar Award. 71. 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 1--702-15---0000 for their generous support of ACMI Lab's research machine learning under distribution shift.
DMS-211 13684
UPU and pnPU: https//gittbbboo//ioo////aaUualp
10

---

References
[1] M. Abadi, Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, et al. Tensorflow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation, 2016.
[2] A. Alexandari, A. Kundaje, and A. Shrikumar. Adapting to label shift with bias-corrected calibration. arXiv preprint arXiv: 1tt.::909110085550 2019.
[3] K. Arizzadenesheli, A. Liu, F. Yang, and A. Anandkumar. Regularized learning for domain adaptation under label shifts. In International Conference on Learning Representations (ICLR), 2019.
[4] J. Bekker and J. Davis. Estimating the class prior in positive and unlabeled data through decision tree induction. Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[5] J. Bekker and J. Davis. Learning from positive and unlabeled data: a survey. Mach. Learn., 2020.
[6] G. Blanchard, G. Lee, and C. Scott. Semi-supervised novelty detection. The Journal of Machine Leurning Research, 11:2973-3009, 2010.
[7] Byrd and Z. C. Lipton. What is the effect of importance weighting in deep learning? In International Conference on Machine Learning (ICML), 2019.
[8] F. De Comité, F. Denis, R. Gilleron, and F. Letouzey. Positive and unlabeled examples help learning. In International Conference on Algorithmic Learning Theory, pages 219-230. Springer, 1999.
[9] Denis. Pac learning from positive statistical queries. In International Conference on Algorithmic Learning Theory, pages 12-122.. Springer, 1998.
[10] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1810.08810004800 2018
[11] M. Du Plessis, G. Niu, and M. Sugiyama. Convex formulation for learning from positive and unlabeled data. In International conference on machine learning, pages 1386-1394, 2015.
[12] M. C. Du Plessis and M. Sugiyama. Class prior estimation from positive and unlabeled data. IEICE TRANSACTIONS on Information and Systems, 97(5): 1362, 2014.
[13] M. C. Du Plessis and M. Sugiyama. Semi-supervised learning of class balance under class-prior change by distribution matching. Neural Networks, 50:110-111 2014.
[14] M. C. Du Plessis, G. Niu, and M. Sugiyama. Analysis of learning from positive and unlabeled data. Advances in neural information processing systems, 27:703-711, 2014.
[15] A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
[16] C. Elkan and K. Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 213 2-0, 2008
[17] S. Garg, Wu, Balakrishnan, and Z. C. Lipton. unified view of label shift estimation. arXiv preprint arXiv:2003.07554, 2020.
[18] X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
[19] K. He, X. Zhang, S. Ren, and Sun. Deep Residual Learning for Image Recognition. In Computer Vision and Pattern Recognition (CVPR), 2016.

---

[20] D. Ivanov. DEDPUL:
wwteeeeoo-sssttdddd-eeeee arXiv preprint arXiv: 1902.06660 2019.
positive-unled unlabeled learning.
[21] Jain, M. White, M. W. Trosset, and P. Radivojac. Nonparametric semi-supervised learning of class proportions. arXiv preprint 1xxiv1600.01944 2016.
[22] D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. arXiv Preprint ArXiv:1412.6998 2014.
[23] R. Kiryo, G. Niu, M. C. Du Plessis, and M. Sugiyama. Positive-unlaheled learning with non-negative risk estimator. In Advances in neural information processing systems, pages 1675-1685, 2017.
[24] A. Krizhevsky and G. Hinton. Learning Multiple Layers of Features from Tiny Images. Technical report, Citeseer, 2009.
[25] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-Baan Learning Applied to Document Recognition. Proceedings of the IEEE, 86, 1998.
[26] W. S. Lee and B. Liu. Learning with positive and unlabeled examples using weighted logistic regression. In ICML, volume 3, pages 448 0833-55,220 2003.
[27] Letouzey, Denis, and R. Gilleron. Learning from positive and unlabeled examples. In International Conference on Algorithmic Learning Theory, pages 71-85. Springer, 2000.
[28] X. Li and B. Liu. Learning to classify texts using positive and unlabeled data. In IJCAI. Citeseer, 2003.
[29] Z. C. Lipton, Y.-X. Wang, and A. Smola. Detecting and Correcting for Label Shift with Black Box Predictors. In International Conference on Machine Learning (ICML), 2018.
[30] B. Liu, W. S. Lee, Yu, and X. Li. Partially supervised classification of text documents. In ICML, 2002.
[31] B. Liu, Y. Dai, X. Li, W. S. Lee, and P. S. Yu. Building text classifiers using positive and unlabeled examples. In Third IEEE International Conference on Data Mining, pages 179-186. IEEE, 2003.
[32] A. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng. and C. Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pages 142-150, 2011.
[33] A. Paszke, S. Gross, F. Massa, Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. Vetito, M. Raison, A. Tejani, Chilamkurthy, B. Steiner, L. Fang, Bai, and S. Chintala. Pytorch: An imperative style, nigh-performance deep learning library. In Advances in Neural Information Processing Systems 32, 2019.
[34] S. Rabanser, S. Günnemann, and Z. C. Lipton. Failing loudly: An empirical study of methods for detecting dataset shift. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[35] H. Ramaswamy, C. Scott, and A. Tewari. Mixture proportion estimation via kernel embeddings of distributions. In International conference on machine learning, pages 2052-2060, 2016.
[36] H. Reeve and A. Kabán. Exploiting geometric structure in mixture proportion estimation with generalised blanchard-lee-sone estimators. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, pages 682-699. PMLR, 2019.
[37] M. Saerens, P. Latinne, and C. Decaestecker. Adjusting the Outputs of a Classifier to New Priori Probabilities: A Simple Procedure. Neural Computation, 2002.
[38] Sanderson and C. Scott. Class proportion estimation with application to multiclass anomaly rejection. In Artificial Intelligence and Statistics, pages 850-858, 2014.
12

---

[39] C. Scott. A rate of convergence for mixture proportion estimation, with application to learning from noisy labels. In Artificial Intelligence and Statisties, pages 838-846, 2015.
[40] T. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller. Striving for simplicity: The all convolutional net. arXiv preprint arXiv: 2014.
[41] A. Storkey. When Training and Test Sets Are Different: Characterizing Learning Transfer. Dataset Shift in Machine Learning. 2009.
[42] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz. J. Davison, S. Shleifer, von Platen, C. Ma. Y. Jernite, J. Plu, C. Xu, T. Scao, S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush. Transformers: Sfate-of-the-ar natural language processing. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38 45, Association for Computational Linguisties, 2020.
[43] C. Zhang, S. Bengio, Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.
[44] D. Zhang and W. S. Lee. A simple probabilistic approach to learning from positive and unlabeled examples. In Proceedings of the 5th annual UK workshop on computational intelligence (UKCI), pages 83-87, 2005.
13


Reviews:
[{"review_id": "pwntmX1K1Cv", "reviewer": "Reviewer_HMxc", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality. The idea of finding the \"pure positive bin\" and its usage for the estimation of the fraction of positives is to my knowledge novel. The CVuO is a straightforward heuristic to convert PU learning into supervised learning, however, I am not aware of its appearance in the literature. \n\nQuality. The paper is technically sound. \n\nClarity. I am missing a high level explanation of the core idea behind the BBE. The reader is in general left on its own to extract the ideas from a dense text. On the other hand, I understand it is not easy given the limited space. I would suggest to start with showing the equation $q_u(z)=\\alpha q_p(z) + (1-\\alpha) q_n(z)$ which is easy to understand, and one can immediately see form it that $q_u(z)/q_p(z)\\geq \\alpha$ and that the bound is tight if $q_n(z) = 0$. The function of the hyper-parameter $\\gamma$ of Algorithm 1 is unclear. I do not fully see the logic behind the name \"Conditional Value Under Optimism\". I had also an impression that the limits of the proposed method are not emphasized, namely, that it requires a prediction model nearly perfectly separating the classes for the top ranked instances.\n\nSignificance. The proposed methods are simple and on standard benchmarks outperform several recent approaches. On the other hand, the methods are tested only on data favourable for the proposed method, i.e., almost perfectly separable classes and the fraction of positives equal to 0.5. \n\nExperiments. As I already mentioned, the methods are tested in the simplest setting when the fraction of positives is just 0.5. It is known that PU methods tend to fail when the classes are imbalanced and it is important to know how the proposed method behaves. The errors are reported without any measure of uncertainty and hence it is hard to judge significance of the the observed differences. The evaluation protocol is not completely clear, but the details are perhaps in the appendix. \n\nTypos:\n- line 30: \"of of\"\n- line 114: \". in our experiments\"\n- Algo 3, line 4: the same iterator \"i\" is used in both loops\n- Algo 3, line 14: \"Lines 4-7\" -> \"Lines 4-9\" ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potentially negative societal impact of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4"}, "extra_text": {}}, {"review_id": "jRv-fbssv3N", "reviewer": "Reviewer_sRZG", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The CvUO algorithm and TED procedure are novel, interesting, and deserve credit.\n\nThe BBE algorithm, on the other hand, seems extremely similar to other approaches, e.g. Scott (2015) gives an approach of learning a PvU classifier, and using held-out data to estimate the ROC (with confidence intervals) and give the smallest slope of the ROC curve to (1,1) as an MPE estimate.  This is, essentially, the same as finding a threshold and taking the (confidence adjusted) ratio of q_p/q_u. There are some subtle differences, but they seem rather negligible. While Scott (2015) uses Kernel logistic regression to generate the ROC, there is nothing preventing the use of deep learning methods to generate the ROC curve. The assumptions of irreducibility, i.e. existence of a set S such that P_n(S)=0 but P_p(S)>0 is exactly the same as the existence of a pure top bin when the sets S are generated by thresholding a learned PvU classifier.\n\nThe CvUO algorithm seems to essentially assume equal class priors between positive and negative. For example, if alpha=0, CvUO should just return a standard PvN classifier, but the loss function used weights the total positive samples as equal to total negative samples regardless of the actual number of samples of each type. A similar issue exists with the proof of proposition 1 in appendix D. I am guessing this is a bug and can be fixed.\n\nSome guarantee of the sort to ensure that CvUO algorithm does not get progressively worse would be valuable. For example if in one iteration a majority of the alpha fraction of sample removed are not negative the classifier learned after that epoch might be even worse than the previous epoch and start a negative spiral. Can a guarantee be given for this to not happen? The proof in Appendix D does NOT take care of this.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No known negative social impact is conceivable for this work specifically, as it is primarily algorithmic in nature for solving a well-known problem. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "E1MLBHjQJ7p", "reviewer": "Reviewer_DmAg", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nTwo main tasks have been solved in this paper. The first relaxes the strong irreducibility assumption in MPE. Since we don't have any prior information about Pn, it is hard to be verified whether the assumption is satisfied in a specific problem. If not, the existing MPE methods may suffer from estimation bias. BBE is just a clever way of solving that. The second uses a simple manner establishing the state of the art. Overall, new theoretical results provide important insights on an important topic. The paper is clear and well written. There is a good balance of theoretical findings and empirical validations.\n\nMinor suggestions:\n- In Algorithm 1, \\hat{\\alpha} cause some doubts. How to intuitively get this equation? From the supplementary materials, it seems to be a derivation back from the theoretical result? Besides, it would be better to introduce the notions that appear for the first time, e.g., ()_{+}.\n- In (TED)^n, how to make a reasonable division between the training set and hold-out set? Should they be evenly split?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "7URS0pP3GYn", "reviewer": "Reviewer_31y4", "summary": "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Contributions and Novelty**\n\nThis paper proposes two advanced methods to tackle the problem of mixture proportion estimation and PU learning, i.e., BBE and CVuO. BBE produces consistent estimates $\\hat{\\alpha}$ under mild assumptions and achieves a $\\mathcal{O}(1/\\sqrt{n})$ convergence rate under some assumptions. Moreover, CVuO discards a certain proportion of training examples during training, which reduces the overfitting to the unlabeled positive ones. Finally, the method TED that combines the BBE and CVuO is presented to train a binary classifier under the settings of PU learning. The proposed methods are effective and somewhat novel. \n\n**Quality**\n- Theory. Detailed theoretical analyses are provided for the method BBE, which shows that, with high probability, the estimation is close to the ground truth. \n- Experiments. The experimental results are convincing. The proposed method outperforms baselines in most cases. \n\n**Clarity**\n\n- Motivation. Although the proposed method works well, the motivation of this paper needs a clearer explanation. \n- Comparison with related works. The authors state that the issues of the prior methods, e.g., complexity or strong assumptions, and aims to address these issues. However, a clearer explanation for their issues is expected to present. At the present stage (Section 2), it is still a bit hard to understand the weaknesses of the prior methods. The descriptions of experimental settings are appreciated.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The **limitations and concerns** in my view are as follows. \n- The authors argue the proposed method only relies on milder conditions. Such a description is somewhat not intuitive. A explanation at a high level is encouraged and expected. \n- More detailed analyses for experimental results are suggested. \n- The procedure of the proposed method is relatively simple. However, it still is comprised of some parts. Would the method bring a lot of extra computational consumption?\n- The method consists of some hyper-parameters needed to be determined. The analyses for them (e.g. an ablation study) should be added to discuss their influence in experiments. \n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
This paper proposes new methods for the related problems of mixture proportion estimation and positive-unlabeled learning, with theoretical support, and shows state of the art performance, especially for large scale problems. I tend to agree with one of the reviewers that the MPE method is not really that novel, sharing many conceptual similarities with previous ROC based methods. This should be clearly addressed in the final revision, as should all reviewer comments. In addition it would be desired to have some theory for the iterative scheme. Without such, the authors also need to address possible failure cases and limitations of $(TED)^n$. Nonetheless, there is still sufficiently novelty and merit to warrant publication.

Additional comments:

While the experimental contributions are clear, I'd like to ask the authors to comment on how the MPE theory compares to prior work. Is this theory merely "supporting", or does it offer advances in MPE theory in any substantive way?

Relevant reference: Henry Reeve and Ata Kaban. Exploiting geometric structure in mixture proportion estimation with generalised Blanchard-Lee-Scott estimators, ALT 2019
Decision: Accept (Spotlight)