AUL is a better optimization metric  in PU learning
Authors: Shangchuan Huang
Songtao Wang
Dan Li
Liwei Jiang
Venue:  (2021)

Abstract: Traditional binary classification models are trained and evaluated with fully labeled data which is not common in real life. In non-ideal dataset, only a small fraction of positive data are labeled. Training a model from such partially labeled data is named as positive-unlabeled (PU) learning. A naive solution of PU learning is treating unlabeled samples as negative. However, using biased data, the trained model may converge to non-optimal point and its real performance cannot be well estimated. Recent works try to recover the unbiased result by estimating the proportion of positive samples with mixture proportion estimation (MPE) algorithms, but the model performance is still limited and heavy computational cost is introduced (particularly for big datasets). In this work, we theoretically prove that Area Under Lift curve (AUL) is an unbiased metric in PU learning scenario, and the experimental evaluation on 9 datasets shows that the average absolute error of AUL estimation is only 1/6 of AUC estimation. By experiments we also find that, compared with state-of-the-art AUC-optimization algorithm, AULoptimization algorithm can not only significantly save the computational cost, but also improve the model performance by up to 10%.

Under review as a conference paper at ICLR 2021
AUL IS A BETTER OPTIMIZATION METRIC IN PU LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Traditional binary classification models are trained and evaluated with fully la- beled data which not common real life. In non-ideal dataset, only a small fraction of positive data are labeled. Training model from such partially labeled data named as positive-unlabeled (PU) learning. naive solution of PU learn- ing is treating unlabeled samples negative. However, using biased data, the trained model may converge to non-optimal point and its real performance cannot be well estimated. Recent works try to recover the unbiased result by estimat- ing the proportion of positive samples with mixture proportion estimation (MPE) algorithms, but the model performance is still limited and heavy computational cost is introduced (particularly for big datasets). In this work, we theoretically prove that Area Under Lift curve (AUL) is unbiased metric in PU learning scenario, and the experimental evaluation on 9 datasets shows that the average ab- solute error of AUL estimation is only 1/6 of AUC estimation. By experiments we also find that, compared with state-of-the-ar AUC-optimization algorithm, AUL- optimization algorithm can not only significantly save the computational cost, but also improve the model performance by up 10%.
INTRODUCTION
Classic binary classification tasks in machine learning usually assume that all data are fully labeled as positive negative (PN learning). However, in real-world applications, dataset is usually non- ideal and only a small fraction of positive data are labeled. Training model from such partially labeled positive data called positive-unlabeled (PU) learning. Take financial fraud detection as an example. Some fraudulent manners are found and can be labeled as positive, but we cannot simply regard the remaining data as negative, because in most cases only a subset of fraud manners detected and the remaining data may also contain undetected positive data. As result, the remaining data can only be regarded as unlabeled. Other typical PU learning applications include text classification, drug discovery, outlier detection, malicious URL detection, online advertise, etc
Yu et al. (2002). Li & Liu (2003). Li et al. (0099) [Blanchard et al. (2010), Zhang et al. (2017). Wu al. (2018).
naive way for PU learning is treating unlabeled data as negative and using traditional PN learning algorithms. But the model trained in this way biased and its prediction results
reliable
(Elkan & Noto (2008)). Some early works try to recover labels for unlabeled data by heuristic algorithms, such as S-EM (Liu et al. (2002). 1-DNF (Yu et al. (2002)) Rocchio (Li Liu (2003). ). k-means (Chaudhari & Shevade ). But the performance of heuristic algorithms, which is critical these works, is not guaranteed. Some other kind of methods introduce an unbiased risk estimator to eliminate the bias (Du Plessis et (2014). Du Plessis et al. (2015) Kiryo et al. (217))
However, these methods rely on the knowledge of the proportion of positive samples unlabeled samples, which is also unknown in practice.
Another annoying problem of PU learning is how to accurately evaluate the model's performance. Model performance is usually evaluated by some metrics, such as accuracy, precision, recall, F- score, AUC (Area Under ROC Curve), etc. During the life cycle of a model, its performance is usu- ally monitored ensure that the model is keeping desired level of performance, with the variance and growth of data. In PU learning. the metrics above are also biased due to the lack of proportion of positive samples. Although Menon al. (2015) proves that the ground-truth AUC (AUC) and

---

Under review as a conference paper at ICLR 2021
the AUC estimated from PU data (AUCPU) is linearly correlated, which indicates that AUCPU can be used to compare the performances between two models, it's still not possible to evaluate the true performance of single model. Consider situation when model is evaluated two different PU datasets generated from the same PN dataset but with different positive sample proportions. The ground-truth AUC which indicates the true performance of the model two datasets the same, but the AUC on the two datasets are different. Hence, AUC cannot be used to directly evaluate the model's performance. JJinn et al. (0117) and Ramola al. (2019) show that they can correct AUCPU, accuracyPl PC, balanced accuracy PD F-score" and Matthews correlation coefficient, with the knowledge of proportion of positive samples. However, this proportion is difficult to obtain in practice.
Recently many works focus on estimating the proportion of positive samples Du Plessis Sugiyama 2014), Christoffel et al. (2016). [Ramaswamy et al.] (2016). Jain et al. (2016), Bekker & Davis 20188) Zeiberg et al. (2020), which are called mixture proportion estimation (MPH) algorithms. Yet according to our experiments on datasets, the estimation methods still introduce some errors and thus make the corrected metrics inaccurate. Besides, the MPE algorithms may also introduce non-trivial computational overhead (by up to 2,000 seconds per proportion estimation in exper- iments), which slows down the evaluation process.
is discriminating, unbiased and computation-friende metric for PU learning. We make the following contributions. a). We theoretically prove that AUL estimation is unbiased to the ground-truth AUL and calculate theoretical bound of the estimation error. b). We carry out experimental evaluation on 9 datasets and the results show that the average absolute error of AUL estimation is only 1/6 of AUC estimation, which means AUL estimation is more accurate and more stable than AUC estimation. c). By experiments we also find that, compared with state-of-the-re art optimmiinnnntion algorithm, AUL- AUL-optimization algorithm can not only significantly save the computational cost, but also improve the model performance by up to 10%.
In this work, we find that Area Under Lift chart (AUL) (Vuk & Curk (2006). Tufféry (011
The remaining of this paper is organized as follows. Section 2 describes the background knowledge. Section@@theoreticall proves the unbiased feature of AUL estimation in PU learning. Section Aeval- uates the performance of AUL estimation by experiments on 9 datasets. Section experimentally shows the performance of AUL-optimization algorithm by applying AUL in PU learning. Section concludes the whole paper.
2 BACKGROUND
Binary Classification Problem: Let D== == (< 0i, >,1= be positive and negative (PN) dataset which has n instances. Each tuple < 24, 9: >> is a record, in which x, E Rd the feature vector and yı E {1, 0} is the corresponding ground-truth label.
Let X², N be the feature vectors set of positive, negative samples respectively, and n", n be the number of samples in these sets respectively.
X
far; ly: 1, 1=:..,...
x
(x)ly): = 0, 1.... N
In PU learning, we use bn samples.
n" to indicate the proportion of positive samples in all
Confusion Matrix: confusion matrix is used to discriminate the model performance of different binary classification algorithms. In confusion matrix, true positive (TP) (actual label and predicted label are both positive), true negative (TN) (actual label and predicted label are both negative), false positive (FP) (actually negative but predicted positive), and false negative (FN) (actually positive but predicted as negative) are counted according to model's outputs. Obviously, nTP + n PN
n. n + n FF n.
ROC: Since the numbers of TP, TN, FP and FN in a confusion matrix are highly related to the classification threshold (0). Receiver Operating Characteristic (ROC) curve (Fawcett & Tom 2003) is proposed to plot (x, y) = (fpr(0), (f))()))p)(()) tpr( over all possible classification thresholds 8. In some literature, fpr is also known sensitivity and the value of 1 fpr is called specificity.
2

---

Under review as a conference paper at ICLR 2021
n TP n false positive rate (Spr)
n FN n N
true positive rale (4pr)
AUC: As curve, ROC is not convenient enough to describe the model performance. Consequently, the Area Under ROC Curve (AUC), which is a single value, is proposed and widely used as a metric to evaluate binary classification algorithm. AUC provides summary of model performance under all possible classification thresholds. It also provides an elegant probabilistic interpretation that AUC is the probability of correct ranking between random positive sample and random negative sample Hanley & McNeil 1982). which is kind of ranking capability. According to Vuk & Curk
2006
for model g R" R. AUC can be computed as follows.
AUC
Σ Σ
(g(zz))
(I)
nt Pnn' n
Ø.EXP BFEXN
where
a > b
S(a, b) =
1
a = b
2
0
< b
It is worth noting that, there are other ways to calculate AUC, but they are essentially the same.
AUL: Lift curve, which is popular in econometrics decide suitable marketing strategy (Tufféry (201 Vuk & Curk ), has not been well studied in machine learning field. Lift curve can be seen as a variant of ROC and it illustrates (I, y) (Yrate (f). t0)( over all possible classification
thresholds 0. Yrate represents the proportion of samples predicted as positive.
n TP + n FP
Yrate
In the curve figure, Lift curve has the same y-axis as ROC curve, but a different x-axis.
Area Under Lift chart (AUL) (Vuk & Curk (2006), Tufféry (201)), can also be used as metric to evaluate the model performance. One way to compute AUI.
AUL -
1 Σ
Σ
(g(x))
(2)
2, EEEN
Essentially, AUL can be regarded the probability of correct ranking between random positive sample and random sample. AUL L and AUC is lincarly related (Tuffery 2011). i.c.
AU 0.5a (1 A)C
which shows that AUL has the same discriminating power with AUC.
3 UNBIASEDNESS OF AUL ESTIMATION IN PU LEARNING: THEORETICAL PROOF
PU dataset DD = {< 0i, 00, 8; >,8; E i.,..n is generated by sampling a subset of positive data as labeled and leaving remain as unlabeled from D. In D' S; the observed label and is the ground-truth label which may be unknown. If s; 1, we can confirm yi (positive). If 8; 0, y/ would be or O. In this paper, we assume that the labeled data Select Completely At Random (SCAR) (Bekker & Davis 2018) from positive data. Therefore the distribution of labeled samples in ID' the same the distribution of positive samples in D. Let X x be the feature vectors set of labeled and unlabeled samples respectively, and n² n the number of samples in these sets respectively.
x {x [s; = 1, 1i==1.... 1....
x {a:]s: -. -0i=1,....
We use 3 -= 4 पe to indicate the proportion of labeled samples in positive samples.
AUC Estimation is Biased

---

Under review as a conference paper at ICLR 2021
To calculate AUC with PU dataset (AUCPL)),
unlabeled data is regarded negative, thus we have
AUC
Σ
Σ
((g(z)).
(3)
n=
2,Ex my xy
where function S is the same as in I The expectation of AUC over the distribution of D is
E|AUC
a (AUC- - + 0.5
a
This formula is slightly different from the one in Menon et al. (2013). Here define AUC specific dataset but not on distribution. This formula indicates that AUC an biased estimation of AUC. We demonstrate the bias on example dataset (Ta), which contains 20 samples sorted by prediction score. Figure Ib illustrates two ROC curves on this dataset. curve-ROC ground-truth label and curve-RCCP is ploted with observed label s. We can see that curve-ROC is almost above curve-ROC' The corresponding AUC is AUC 0.740 and AUC = 0.653 respectively. There is big difference (0.087) among the two measurements.
ploted with
As we discussed in section [ (Jain et al. 2017) tries to recover AUC from AUCPU from the 1-a estimation of 1-03- To estimate 1-0.8 some works(Elkan & Noto 2008). Du Plessis Sugiiyma
2014), Sanderson & Scott (2014), Jain et al.
(0166) Ramaswamy et al. Christooel et al. 2020 develop their mixture proportion estimation
2016 Bekker & Davis (2018), Zeiberg et al.
(MPE) algorithms. But according to our experiment on 9 datasats, these algorithms are neither
accurate enough nor time saving.
AUL Estimation is Unbiased
Similar to AUCPU AUL with PU dataset PAU can be calculated as
AUL PU
Σ Z.EXL EYEXLUX0
Σ
S (gg(z))
(4)
n'
Unlike PU PU is unbiased estimation of AUL. In contrast to Figure lb Figure lc illustrates two lift curves which very close to each other. curve-lift is ploted with ground-truth label and curve-lift" is ploted with observed label s. The corresponding AUL, AUL = 0.620 and AU 0.615, very close. We then prove the unbiasedness.
Theorem For given classifier 9 Rd + R. PN dataset D with the proportion of labeled samples in positive samples 3 a²
a PU dataset ID can be generated following SCAR, the expectation and variance of AUL PU over the distribution of D' are as follows,
E|AUL PU] = AUL
Var[AUL PU n n a²
n² - n
where a² the variance of Ex (g(xx,,
g(( g(2e 1,...o0!
Proof Let
tz:
Σ
((1)))
Σ
((g(z)).
n
n
2, EXP JNN
EX
then,
AUL Σ la
n.
2, 2,EXP
PU
lm:
nt
Z,EXL
X!. I. is generated by random sampling without replacement from X., hence PUL is the estima- tion the mean of (Ie,, F. E XP} which is AU L. According the theory of simple random sampling
4

---

Under review as a conference paper at ICLR 2021
without replacement (Lohr (209)) ), the estimated population mean LU is an unbiased estima- = LU and variance of AU PU is
for of the population mean AUL, i.e. E|AUL
n1 Exxexp (lzz - 7)22
Var Lar P =
n2 nz
nº -1
nP n 1
Ex,exo (las - -)2
n - n
np
nº n o² n - nL
According to Theorem applying Chebyshev's inequality, we have
P (IAUT. AUT 2 c) = Var o²
n
(1 B) n
n.
where Var is the variance of AU note that < Lm;
1, hence
o² = - -
< E (1 - 1)² (0 ()(( 1)]
E [-217 +
[ + +1]
= -
then
P (IAUT- 1 1 3 n
1-8
4n nP - 4n
This equation gives a theoretical bound for the eπтоr between AUL L and AU PU labeled samples n can reduce the error to an acceptable level.
Hundreds of
Score
0.92
0.82
0.73
0.66
0.6
0.58
0.54
0.5
0.45
0.43
1
1
0
1
1
1
1
0
0
0
8
0
score
0.41
0.39
0.38
0.36
0.35
0.3
0.25
0.2
0.15
0.1
y/
0
1
0
0
0
0
0
0
1
0
0
(a)
RBC
lift
life
0.6-
1pr
0.4
0.2
8.2
8.0
0.0
0.4
9.6
6.8
1.8
9.9
8.2
0.4
9.6
8.8
1.8
fpr
Vrate
(b)
(c)
Figure 1: AUC and AUL estimation example dataset Ia (20 instances, 0.5, 3 0.5). Each instance has a prediction score (score) given by a certain model, a ground-trutt label y and an observed label s.
5

---

Under review as a conference paper at ICLR 2021
4 EXPERIMENTAL EVALUATION OF AUL ESTIMATION
4.1 DATASETS
The experiment involves 9 real-life datasets from UCI Machining Learning Repository (Dua & Graff 2017). which are listed in table [ To create binary classification datasets we do little modification on the original datasets' "target'. If it's a regression dataset we take a proper threshold and transfer it to binary classification dataset. For multi-class dataset, we chose one class as positive and the remaining as negative. We also transfer categorical features to numerical features using one-hot encoding. Considering the computing overhead of MPE algorithm, we limit the size of PN dataset around 4,000. In order to generate PU dataset, we use random sampling without replacement method to select a subset of positive samples as labeled data and the remaining regarded as unlabeled data. There are three settings of B = {0.1, 0.2, 0.43. For each dataset setting, 50 PU datasets generated.
4.2 COMPARISON AMONG AUC&AUL ESTIMATION METHODS
High estimating accuracy and low cost two important indexes for AUC/AUL estimation. Accu- racy indicates how close the estimated AUC/AUL is to the ground-truth AUC/AUL. Cost indicates how much time (computation power) an estimation process takes. AUC and AUL estimation rely on a model's output. Therefore, for each dataset, we train a classifier using lightGBM (Ke et al.) (017) to simulate the classifier to be evaluated. The performance of this classifier is rational, not too bad nor totally perfect.
To compare accuracy, we firstly compute the ground-truth value of AUC (AUC) and AUL (AUL) on fully labeled PN dataset. Then we calculate the estimated AUC (AUC and AUL (AULPU) on PU dataset and compare them with AUC and AUL. To calculate AU Cest we use the direct con- version method following Jain et al. (201)) This method firstly obtains AUC which is calculated by treating unlabeled data as negative and then estimates AU with it. The estimating step needs mixture proportion estimation (MPE) algorithm to estimate the proportion of positive samples in unlabeled samples. Three MPE algorithms are used in this experiment. Ramaswamy et al. (2016)
provides two algorithms named as KM1 and KM2. Zeiberg et al. (2020) which is based distance curve is named as Distance. It's worth noting that Zeiberg et al. (2000) has compare their solution with all the existing MPE algorithms and claim themselves the best far. The corresponding estimated AUC of the three algorithms are AUCK AUC and AU Distance respectively. We use the codes provided by the two papers.
Table D shows the Mean Absolutely Error (MAE) results for each dataset. AUC and AUL ground-truth value computed on fully labeled datasets. The estimation processes run 50 times for each dataset setting and get AUCH AUCRM AUC Distaaaec and AULPU MAEKMI. MAEKM² AUC MAEDiston Distance M are the mean values of AU KMC AUC), JAUCR AUC
AUCCK2 AUCI, PA - AU respectively. In all settings, MAE of AUL es-
AUC), AU Distaneee timation outperforms AUC estimation. The average MAE of AUL estimation on all 3*9 dataset settings is only 1/6 of the best AUC estimation (DistanD))
Figure 2 iilluttrates the error (AUCest AUC or L - LU distributions of 150 estimation results (3 3 settings for each dataset, each setting run estimation for 50 times) per dataset using boxplot. Each boxplot plots the minimum, the first quartile, the sample median, third quartile and the maximum value in ascending order by five horizontal lines. The mean value is ploted with black diamond. This figure shows that the mean value of AUI. estimation error is the closest to O and the interquartile range (range between first and third quartile) of AUL estimation error is the smallest. It indicates that AUL estimation is more accurate and stable than AUC estimation. We also noticed that when 9 becomes larger, the interquartile range gets smaller. This is consistent with our conclusion in section 3.
4kmpe

---

Under review as a conference paper at ICLR 2021
Table Mean Absolutely Error (MAE) of AUC/AUL estimation methods on 9 datasets.
Dataset
#n
AUC
AUL
MAEACC
MAEANE
MAE
MAEAUL
Ahalone
4177
0.498
0.1
0.807
0.654
0.065
0.035
0,037
0.014
Ahalone
4177
0.498
0.2
0.807
0.654
0.043
0.043
0,031
0.008
Abalone
4177
0.498
0.4
0.807
0.654
0.027
0.054
0.034
0.005
Airfoil
1503
0.483
0.845
0.678
0.110
0.088
0.093
0.019
Airfoil
1503
0.483
0.845
0.678
0.087
0.048
0.064
0.012
Airfoil
1503
0.483
0.4
0,845
0.678
0.057
0.026
0,041
0.009
Anuran
4000
0.614
0.1
0.887
0.649
0.058
0.070
0,073
Anuran
4000
0.614
0.2
0.887
0.649
0.054
0.040
0.065
0.007
Anuran
4000
0.614
0.4
0.887
0.649
0.055
0.024
0.026
0.004
Concrete
1030
0.472
0.1
0.875
0.698
0.091
0.113
0.100
0.022
Concrete
1030
0.472
0.2
0.875
0.698
0.096
0.066
0.061
0.016
Concrete
1030
0.472
0.4
0.875
0.698
0.105
0.041
0.083
0.009
Landsat
4435
0.242
0.1
0.756
0.694
0.018
0.018
0.049
0.015
Landsat
4435
0.242
0.2
0.756
0.694
0.014
0.012
0.030
0.011
Landsat
4435
0.242
0.4
0.756
0.694
0.010
0.008
0.010
0.00 007
Mushroom
4000
0.518
0.1
0.942
0.713
0.028
0.066
0,042
0.011
Mushroom
4000
0.518
0.2
0.942
0.713
0.021
0.028
0.030
0 006
Mushroom
4000
0.518
0.4
0.942
0.713
0.027
0.018
0.026
0.004
Pageblock
4000
0.898
0.1
0.891
0.54
0.177
0.300
0.201
0.011
Pageblock
4000
0.898
0.2
0.891
0.54
0.110
0.249
0.183
0.008
Pageblock
4000
0.898
0.4
0.891
0.54
0.111
0.159
0.163
0.005
Spamhase
4601
0.394
0.1
0.841
0.706
0.111
0.068
0.037
0.014
Spamhase
4601
0.394
0.2
0.841
0.706
0,084
0.106
0.018
0.008
Spamhase
4601
0.394
0.4
0.841
0.706
0.056
0.131
0.008
0.005
Waveform
4000
0.329
0.1
0.926
0.785
0.074
0.073
0.105
0.009
Waveform
4000
0.329
0.2
0.926
0.785
0.073
0.074
0.025
0.005
Waveform
4000
0.329
0.4
0.926
0.785
0.064
0.074
0.028
0.004
AIC 3P1
AIC 3912
ALT Distance
A1L
Airfoi
Anuran
0.25
6.15
9.10
0.00
8.50
0.05
0.00
9.35
Ni2
0.95
9.92
0..05
8.80
6..25
-0.09
-0.15
-0.00
-0.25
0.4
Pageblock
Spanbaase
0.0
0.05
0.30
8:90
0.80
Figure 2: Estimation error distribution datasets.

---

Under review as a conference paper at ICLR 2021
The cost of AUC estimation includes AUC calculation cost and MPE algorithm's calculation cost. The cost of AUL estimation includes AUL calculation cost only, which is nearly the same as AUCPU calculation cost and it is negligible (less than 1 second). However, the MPE algorithms cost is much larger. We conducted an experiment to count the time cost of MPF. algorithms. For a dataset with 8,000 instances and 117 features, the time cost of Ramaswamy et al. (20T6)'s 's method grows fast when the dataset's 's size grows (4 seconds for 1,000 samples, 2,000 seconds for 8, 8,000 samples). Zeiberg et al. (2020) introduces an univariate transform to reduce the dimensionality of data. Therefor, their MPE method get a significant acceleration (16 seconds for 8,000 samples). But the selection of univariate transform another time consuming problem. A careless selection of the transform will make the estimating result inaccurate. In the work of Zeiberg et al. (2020), lot of effort was made to select the optimal transform for each PU dataset.
5 EXPERIMENTAL EVALUATION OF AUL-OPTIMIZATION ALGORITHM
Optimizing AUC is direct and popular way for training binary classifier models. (Sakai et al. (2018) develops a AUC-optimization algorithm named as PU in PU learning scenario. Following this idea we also implement an AUL-optimization algorithm named as PULAUL in similar way of PULAUC. PU and PULAUL share the same Gaussian kernel basis function, which is adopted by Sakai et al. (2018). The datasets we used in this section are the same with that in section excepting 3 is fixed at 1. Because PU AUC algorithm requires the proportion of positive samples estimated by MPE algorithms, we choose the best performed MPE algorithm for PU_AUC in each dataset. The metric used for model performance comparison is AUC which is calculated on ground- truth PN data.
Figure shows that PULAUL achieves better performance on 8/9 datasets (average 2.5% improve- ment). Because PULAUC may suffer from the error of MPE algorithm, on 'Concrete' dataset, PULAUL outperforms PULAUC by 10%. Because MPE calculation is not required in PULAUL, it runs much faster.
PU_AUC
PU AUL
0.95
8.98
0.85
AUC
0.80
8.75
8.78
8.65
0.60
Abslone
Airfoll
Anuran
Concrete
Landset
Rustroom
Pageblock
Spunbase
Havefors
Figure 3: PU AUL outperforms PU AUC by up to 10% on 9 datasets.
6 CONCLUSION
In this paper, we suggest replacing AUC by AUL for both model evaluation and model training in PU learning scenario. Comparing with AUC, AUL is an unbiased metric and can be computed efficiently. Existing MPE algorithms, which is necessary for AUC-optimization algorithms. have been proved to be inaccurate and high cost. Besides, choosing a good set of parameters for MPE algorithms in order to get good estimation result may even take more time.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jessa Bekker and Jesse Davis. Estimating the class prior in positive and unlabeled data through decision tree induction. In Proceedings of the 32th AAAI conference on artificial intelligence, pp. 2712-2719, AAAI Press, 2018.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Semi-supervised novelty detection. The Journal of Machine Learning Research, 11:2973-3009, 2010.
Sneha Chaudhari and Shirish Shevade. Learning from positive and unlabelled examples using max- imum margin clustering. In International Conference Neural Information Processing, pp- 465-473. Springer, 2012.
Marthinus Christoffel, Gang Niu, and Masashi Sugiyama. Class-prior estimation for learning from positive and unlabeled data. In Asian Conference Machine Learning, pp. 221-236, 2016.
Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. In International conference on machine learning, pp. 1386-1394, 2015.
Marthinus C Du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. In Advances in neural information processing systems, pp. 703-711, 2014.
Marthinus Christoffel Du Plessis and Masashi Sugiyama. Class prior estimation from positive and unlabeled data. IEICE TRANSACTIONS on Information and Systems, 1365) 2014.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://rchhii ics. wuu.ccii. edu/ml
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 213-220, 2008.
Fawcett and Tom. Roe graphs: Notes and practical considerations for data mining researchers. Pattern Recognition Letters, 31(8):1-38, 2003.
James A Hanley and Barbara McNeil. The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology, 143(1):29-36. 1982.
Shantanu Jain, Martha White, and Predrag Radivojac. Estimating the class prior and posterior from noisy positives and unlabeled data. In Advances in neural information processing systems, pp- 2693 2693-2701, 2016.
Shantanu Jain, Martha White, and Predrag Radivojac. Recovering true classifier performance in positive-unlabeled learning, arXiv preprint arXiv: 2017.
Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in neural information processing systems, pp. 3 3146-3154, 2017.
Ryuichi Kiryo, Gang Niu, Marthinus C Du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. Advances in neural information processing systems, pp. 1675-1685, 2017.
Xiao-Li Li, Philip S Yu, Bing Liu, and See-Kiong Ng. Positive unlabeled learning for data stream classification. Proceedings of the 2009 SIAM International Conference on Data Mining, pp- 259-270. SIAM, 2009.
Xiaoli Li and Bing Liu. Learning to classify texts using positive and unlabeled data. In IJCAI, volume 3. pp. 587-592, 2003.
Bing Liu, Wee Sun Lee, Philip S Yu, and Xiaoli Li. Partially supervised classification of text documents. In ICML, volume 2, pp. 387-394, 2002.
Sharon I. Lohr. Sampling: design and analysis. Nelson Education, 2009.

---

Under review as a conference paper at ICLR 2021
Aditya Menon, Brendan Van Rooyen, Cheng Soon Ong, and Bob Williamson. Learning from rupted binary labels via class- probbbiity estimation. In International Conference on Machine Learning. pp. 125-134, 2015.
Harish Ramaswamy, Clayton Scott, and Ambuj Tewari. Mixture proportion estimation via kernel embeddings of distributions. In International conference on machine learning, pp. 2052-2060, 2016.
Rashika Ramola, Shantanu Jain, and Predrag Radivojac. Estimating classification accuracy in positive-unlabeled learning: characterization and correction strategies. In PSB, pp. 124-135. World Scientific, 2019.
Tomoya Sakai, Gang Niu, and Masashi Sugiyama. Semi-supervised auc optimization based on positive-unlabeled learning. Machine Learning, 107(4):777-794, 2018.
Tyler Sanderson and Clayton Scott. Class proportion estimation with application to multiclass anomaly rejection. In Artificial Intelligence and Statistics, pp. 850-858, 2014.
Stéphane Tufféry. Data mining and statistics for decision making. John Wiley & Sons, 2011.
Miha Vuk and Tomaz Curk. Roc curve, lift chart and calibration plot. Metodoloski zvezki, 3(1):89, 2006.
Zhiang Wu, Jie Cao, Yaqiong Wang, Youquan Wang, Lu Zhang, and Junjie Wu. hpsd: A hybrid pu- learning-based spammer detection model for product reviews. IEEE transactions on cybernetics, 2018.
Hwanjo Yu, Jiawei Han, and Kevin Chen-Chuan Chang. Pebl: positive example based learning for web page classification using svm. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 239-248, 2002.
Daniel Zeiherg, Shantanu Jain, and Predrag Radivojac. Fast nonparametric estimation of class pro- portions in the positive-unlabeled classification setting. In AAAI, pp. 6729-6736, 2020.
Ya-Lin Zhang, Longfei Li, Jun Zhou, Xiaolong Li, Yujiang Liu, Yuanchao Zhang, and Zhi-Ha tha Zhou. Poster: pu learning based system for potential malicious url detection. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 2599-2601, 2017.
10


Reviews:
[{"review_id": "WMJ_hYScKhM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper argues that AUL is a better metric than AUC under the PU (positive and unlabeled data) learning setup in the sense that it leads to an unbiased estimator in this setting, which is not the case for the commonly used and known metric - AUC. It is also argued that it leads to better performance than those methods which directly optimize an AUC based metric and computationally efficient to evaluate than methods which attempt to estimate the unknown parameters (\\alpha, \\beta in the paper). The appropriateness of this setting in the PU learning setting is demonstrated on the UCI datasets.\n\nThe main contribution of the paper is to bring in the AUL metric in the context of PU learning, which seems rather new from the ML perspective. However, there are following concerns regarding the methodology and experimentation :\n\n- The paper repeatedly makes the claim that existing work, including recent ones, which work on estimation of \\frac{1-\\alpha}{1-\\alpha\\beta} do not work well on their setup, without discussing why that happens. It is not discussed if there is something wrong in these papers. In my opinion, one needs to give reasonable arguments why these methods do not work, instead of simply saying these did not work.\n\n- The proof of Theorem 1 is not quite clear, and in particular, how equality defining the t_{x_i} holds. Is it related to the SCAR assumption made in the paper. The proof needs to be more details, and it should be clarified where the SCAR assumption is used.\n\n- The SCAR assumption is vaguely defined in words. In the context of the paper, it should be formally defined in terms of quantities already metioned such as \\alpha and \\beta. Also, is the assumption not too strong, and do other papers make this assumption. How to verify that this assumption holds in practice. \n\n- The paper argues about the computational advantage of their method compared to other methods. However, it is evaluated on small scale UCI datasets,\n\n- There seem to be incorrect usage of PU/PN learning in various places : (i) When defining \\alpha in section 2, the sentence says \"In PU learning, we ...\", should it not be \"In PN learning, we ...\", (ii) In the statement of Theorem 1, \"a PN dataset \\mathbb{D} with the proportion of labeled samples in positive samples \\beta= ...\" - does it make sense to talk about labeled and unlabeled data when talking about PN dataset.\n\n- Comparison with a recent related work is missing - Class Prior Estimation with Biased Positives and Unlabeled Examples - AAAI 2020", "extra_scores": {}, "extra_text": {}}, {"review_id": "E1UPIIm_VD6", "reviewer": "AnonReviewer6", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the author proposed to use Area Under Lift chart (AUL) as a new optimization metric for positive unlabeled (PU) learning. The proposed AUL can be estimated unbiasedly from PU data, without the need to estimate the mixture proportions. Experiments on several datasets show that the proposed method outperforms AUC optimization algorithms.\n\nIt seems that the authors consider AUC as the evaluation metric of PU learning algorithms. Why not use the classification error to evaluate the learned models? For example, after the mixture proportions are estimated, a simple importance reweighting method could be used to train a classifier.\n\nFrom the theoretical analysis in the paper, we can only see that the AUL_PU is an unbiased estimator of AUL. However, the link between AUC on the classifier learned by optimizing AUL and the classifier learned directly by AUC is not clear. The authors claim that this might be due to the error in mixture proportion estimation. Does this imply that AUL_PU has no advantages if the mixture proportion is correctly estimated? The author could do some ablation study, for example, training AUC by using ground-truth mixture proportion,  to further analyze the accuracy of the classifier trained by AUC and AUL.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9a3sNQhJchC", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper examines the positive-unlabeled (PU) learning setting, and recommends the usage of the area under the lift curve, or AUL, as an unbiased estimate of the AUL under the fully labeled setting. This justifies proposing to use an AUL-optimization algorithm to train binary classifiers.\n\nAlthough I am not entirely sure this is fitting for a conference focused on representation learning, this is a question of interest in machine learning at large.\n\nI think this is an interesting proposition, supported by the experimental results. However, I do have a number of concerns that make me think this work is too premature and I lean towards rejection.\n\n1) I do not understand where the bias of $AUC^{PU}$ comes from in the equation below equation (3). Indeed, it is not obvious how it is derived from (3), and Jain et al. (2017) obtain \n$$\n   (\\beta-\\alpha) (AUC - \\frac12) + \\frac12. \n$$\n\n2) I disagree with the bound on $P(|AUL - AUL^{PU}| \\geq \\epsilon)$. Indeed, applying Chebychev's inequality, I think this should be upper bounded by $\\frac{\\text{Var}}{\\epsilon^2}$ and not $\\frac{\\text{Var}}{\\epsilon}$. Hence the final bound should be\n$$\n    P(|AUL - AUL^{PU}| \\geq \\epsilon) \\leq \\frac{1 - \\beta}{4 n^L \\epsilon^2}.\n$$\nThis is unfortunate, because taking $\\epsilon = 1\\%$, and for example $\\beta = 0.5$, \n$$\n   \\frac{1-\\beta}{4 \\epsilon^2} = 1250,\n$$\nso the sentence \"Hundreds of labeled samples can reduce the error to an acceptable level\" does not hold any longer -- it's now \"tens of thousands of samples\".\nOn the numerical experiments of Table 1, you can indeed check that for the Airfol data set, with $\\beta = 0.1$, \n$$\n    \\frac{1-\\beta}{4 n^L \\epsilon^2} = \\frac{1-\\beta}{4 \\alpha \\beta n \\epsilon^2} \\approx \\frac{1.8 \\times 10^{-3}}{\\epsilon^2},\n$$\nso $P(|AUL - AUL^{PU}| \\geq 10^{-2})$ can only be bounded by 18, and indeed $MAE_{AUL}=0.019$.\n\n3) Although some of the papers that are cited also use UCI data sets, I am wondering whether the values of $\\alpha$ that are being tested are realistic. Indeed, it is my impression that PU settings occur mostly when the relative proportion of positive examples in the data is really small (fraud or outlier detection, malicious URL detection, drug discovery), which is why it makes sense to treat the unlabeled as negative, but here $\\alpha$ is between 0.3 and 0.9.\n\n5) The AUL-optimization algorithm is an interesting proposal, and I think the paper would greatly benefit from having more details about this algorithm, even if it is \"only\" an adaptation of the algorithm of Sakai et al. (2018).\n\n6) On Figure 3, while for some of the data sets (Pageblock, Concrete) it is obvious that PU_AUL is performing much better than PU_AUC, it is not clear for all of them (in particular Landset, Anuran, Abalone, Airfoil) whether the difference in performance is significative. I would recommand plotting error bars on multiple cross-validation runs and/or computing statistical tests.\n\nIn addition, I have several minor comments.\n\n1) The work is conducted under the assumption that labeled examples are selected completely at random among the positives and I think this should be mentioned explicitly in the abstract and Introduction. Indeed, this assumption may not hold in practice, for example in biological applications (the molecules or interactions labeled as positives are those that have been biologically investigated, and these investigations did not occur uniformly at random). \n\n2) I don't think the proof that $\\sigma^2$ is less than 1/4 is correct. The result is known as Popoviciu's inequality on variances, and if you want to prove it you should use \n$$\n   \\mathbb{E}[(t - \\bar{t})^2] \\leq \\mathbb{E}[(t - \\bar{t})^2 - t(t-1)],\n$$\nwhich is correct because $t(t-1) < 0$. The equation that is given in the paper,\n$$\n   \\mathbb{E}[(t - \\bar{t})^2] \\leq \\mathbb{E}[(t - \\bar{t})^2 - (0-\\bar{t})(\\bar{t}-1)],\n$$\nis not true because $(0-\\bar{t})(\\bar{t}-1) > 0$.\n\n3) There are a number of typos in the text. \"online advertise\", \"Select Completely at Random\", etc.\nThe definition of fpr in Section 2, paragraph \"ROC\", should be \n$$\n   \\frac{n^{FP}}{n^N}.\n$$\n\n4) In Section 4.2, I find it odd to compare $|AUC^{est}-AUC|$ to $|AUL^{PU}-AUL|$, because $AUC$ and $AUL$ don't take the same values. I think these two quantities should be normalized by $AUC$ and $AUL$ respectively, reporting $|AUC^{est}-AUC|/AUC$ and $|AUL^{PU}-AUL|/AUL.$ The same holds, of course, for $AUC^{KM1}$ and $AUC^{KM2}$. \nI note that it does not seem to change the conclusions that can be drawn from Table 1.\n\n5) In biological and drug discovery applications, it has become rather mainstream to evaluate the performance of PU-learning algorithms using the cumulative distribution function of the ranking of positive samples among all test samples in a leave-one-out setting as in Mordelet and Vert (2011). I think it would be warranted to discuss this method as well.\nAnother relevant reference seems to be Jiang et al. (2020).\n\nReferences\nMordelet and Vert, BMC Bioinformatics 2011, 12:389 http://www.biomedcentral.com/1471-2105/12/389\nLiwei Jiang, Dan Li, Qisheng Wang, Shuai Wang, Songtao Wang. Improving Positive Unlabeled Learning: Practical AUL Estimation and New Training Method for Extremely Imbalanced Data Sets.  https://arxiv.org/abs/2004.09820\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new metric, AUL, for classification problems with unbalanced data. The paper proves that it is unbiased and it does not need to estimate the mixture proportions, a traditional approach. Empirical results show improvement.
While the results are novel, the referees pointed out several concerns
1. Positioning of the results in the context of existing work. It would be helpful if the paper can establish theoretical links to existing metrics such as  AUC,
make a very precise statement about what is lacking in those approaches
2. Some of the results, may have bugs in the proof.
3. More ablation studies are needed 

In summary the paper has good ideas but maybe premature for publication.

Decision: Reject