Positive-Unlabeled Learning using Random Forests via Recursive Greedy Risk Minimization
Authors: Jonathan Wilton
Abigail Koay
Ryan Ko
Miao Xu
Nan Ye
Venue: NeurIPS 2022 Accept (2022)

Abstract: The need to learn from positive and unlabeled data, or PU learning, arises in many applications and has attracted increasing interest. While random forests are known to perform well on many tasks with positive and negative data, recent PU algorithms are generally based on deep neural networks, and the potential of tree-based PU learning is under-explored. In this paper, we propose new random forest algorithms for PU-learning. Key to our approach is a new interpretation of decision tree algorithms for positive and negative data as \emph{recursive greedy risk minimization algorithms}. We extend this perspective to the PU setting to develop new decision tree learning algorithms that directly minimizes PU-data based estimators for the expected risk. This allows us to develop an efficient PU random forest algorithm, PU extra trees. Our approach features three desirable properties: it is robust to the choice of the loss function in the sense that various loss functions lead to the same decision trees; it requires little hyperparameter tuning as compared to neural network based PU learning; it supports a feature importance that directly measures a feature's contribution to risk minimization. Our algorithms demonstrate strong performance on several datasets. Our code is available at \url{https://github.com/puetpaper/PUExtraTrees}.

Positive-Unlabed Learning using Random Forests via Recursive Greedy Risk Minimization
Jonathan Wilton', Abigail M. Y. Koay?, Ryan K. L. Ko², Miao Xu Nan Ye! School of Mathematics and Physics, The University of Queensland School of Information Technology and Electrical Engineering, The University of Queensland RIIKNN, Japan 103-0027
Abstract
The need to learn from positive and unlabeled data, or PU learning, arises in many applications and has attracted increasing interest. While random forests are known to perform well many tasks with positive and negative data, recent PU algorithms are generally based on deep neural networks, and the potential tree-based PU learning is under-explored. In this paper, we propose new random forest algorithms for PU-learning. Key to our approach is a new interpretation of decision tree algorithms for positive and negative data as recursive greedy risk minimization algorithms. We extend this perspective to the PU setting to develop new decision tree learning algorithms that directly minimizes PU-data based estimators for the expected risk. This allows us to develop an efficient PU random forest algorithm, PU extra trees. Our approach features three desirable properties: it is robust to the choice of the loss function in the sense that various loss functions lead to the same decision trees; requires little hyperparameter tuning as compared to neural network based PU learning; it supports a feature importance that directly measures feature's contribution to risk minimization. Our algorithms demonstrate strong performance on several datasets. Our code is available https: /gi thub. wtt.coooompaaeeee petppppppppe//UBttteerreeee.
Introduction
Positive and unlabeled learning (PU learning) has attracted increasing interest recently, due to its broad applications, including disease gene identification [24], landslide susceptibility modeling [29], inference of transcriptional regulatory network [23], cybersecurity [30] and many others [2].
Existing algorithms generally reduce PU learning to solving one or more supervised learning problems. A naive approach is simply learn classifier by treating all unlabeled examples negative, but unlabeled examples can be either positive or negative. Various approaches have been developed to better handle the uncertainty the labels of the unlabeled examples. A common approach follows iterative two-step learning process: the first step identifies reliable negative examples, then the second step learns model using the positive examples, the reliable negative examples and possibly unlabeled examples [22, 15]. Another common approach transforms the PU dataset into a weighted fully labeled dataset [20, 12, 11, 16]. The transformed dataset is often constructed so that the empirical risk on the transformed dataset provides good estimate of the true risk. Depending on the assumptions on how PU data generated, different transformations have been developed.
While random forests are known to perform well for many supervised learning problems and in principle tree-based learning methods be applied in the above approaches, little work has been done to explore the potential of tree-based methods for PU learning. On the other hand, current state-of-the-ar PU learning methods are often based deep neural networks [16, 6]. This is partly due to the recent advances of deep learning, which allows training of powerful neural network models
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

with relatively little effort. In addition, while it is easy to train neural network to minimize different loss functions, it is not clear how this can be done for tree-based methods (without overfitting the dataset), because existing tree-based methods have not been designed to directly minimize the loss. In particular, it not clear how this can be done for nonstandard risk estimators such the non-negative PU risk (nnPU), which has already been observed to work well with neural networks [16).
We fill this gap by providing a theoretically justified approach, which we call recursive greedy risk minimization, to learn random forests from PU data in this paper. Our contributions are as follows
new interpretation to existing decision tree learning algorithm that links the impurity reduction based learning algorithms to empirical risk minimization.
Efficient new decision tree and random forest algorithms that directly minimize PU-data based estimators for the expected risk.
Our approach has three desirable properties: it is robust to the choice of the loss function in the sense that various loss functions lead to the same decision trees; it requires little hyperparameter tuning compared to neural network based PU learning; it supports feature importance that directly measures a feature's 's contribution to risk minimization.
Our algorithms demonstrate strong performance on several datasets.
We briefly review decision tree learning and PU learning in Section 2, introduce our recursive greedy risk minimization approach for decision tree learning in Section and the PU version of extra trees in Section 4, present experiment results in Section 5, discuss related works in Section 6, and conclude Section
Background
Decision tree learning from positive and negative data A decision tree is generally constructed by recursively partitioning the training set so that we can quickly obtain subsets which are more or less in the same class.
Algorithm 1: LearnDT(K,, S)
Algorithm shows generic decision tree learning algorithm. We start with single node associated with the entire set of train- threshold;
Notations: x - node; S dataset; / feature; /.
ing examples. When we encounter a node s associated with a set of training ex- amples, compute the prediction value at A the termination criterion met. If not, we first compute optimal split (f.t) for the dataset S, where split (f, tests whether feature is larger than value t, and the quality of a split is usually mea- end sured by its impurity reduction. Based
if termination criterion is met then
Compute the prediction value using S:
else
Choose an optimal split (f,t);
Create two child nodes Kyzt and Ryst for n;
LearnDT(Ns>>:: (w
the test's outcome, we create two child nodes Ky>z and Kygt, split S into two subsets StSt and Sist. and finally continue the learning process with (,y>,,,)>) and (Kyst, Sy5ı).
Given an impurity measure Impurity(S).. split t)'s impurity reduction is
IR(f,t; S) = Impurity(S)) - |S Impurity(Spze)
|S Impurity(Srsi))
|S|
|S]
Typically, the Gini impurity G(S) and the entropy H()) are used as the impurity measure:
H(S) = -4+ In - q Ing-, where 4+ and q- the proportions of positive and negative examples in S respectively.
G(S) = 2 - x2 24+ (1 g+);
We will use [R ft, S) and IReenrop (f,, t; S) to denote the impurity reduction when using the Gini impurity and the entropy impurity respectively.
PU learning We assume that the input æ E Rdd and label y E (-1,+1} follow an unknown joint distribution p(æ, y) p(æ y) p(y). In the fully supervised case, the training data is generally

---

assumed to be independently sampled from p(a, y). In the PU setting, one common assumption
on the data generation mechanism [11, 10, 16] is that the positive examples P = f ( 2 sampled independently from the P marginal (z == p( y = 1), and the unlabeled examples
F are
U' = { (w) Ma are sampled independently from the marginal p(x) = p(æ, +1) + p(x, -1). Clearly, we have p(x) = π (p(x) + (1 - TT) pn()), where π == ply +1) is the positive rate and pa (x) == p(æ| y = -1) is the marginal.
The objective is to learn score function y Rd - R (which corresponds to classifier that outputs +1 iff g(x) > 0) such that it minimizes its expected risk
R(g)= ((...))-((..) {gg(x).)),
where e: R. (-1, + R is a loss function that gives the loss L(v, y) incurred by predicting score U when the true label y. We focus on the quadratic loss (qua((), y) = (1 vy)² the logistic
loss (logisti((; 3) In (1 + (xp(- the savage loss Lavago y) 41 + exp(vy))2 and the sigmoid loss Esigmoia (v, y) = 1/( + exp(vy)) in this paper.
The risk can be written in terms of positive and unlabeled data as [11]
R(g)= = т Ba>p,(=) (((()), +1) + Bepp(() {(g(z), -1) - a E Earp,(a) {(g(()), -1).
(4)
This gives the following unbiased PU-data based risk estimator
R = Σ up (pp(g(z),+1) - Σ P
upl(g(x)) -1) + Σ wul(g(x)) -1),
(5)
P
aEU
where w/p x n/n, and Wi = 1/nn.
While the uPU risk estimator is unbiased, it has negative component that provides extra incentive for the classifier to try hard to fit to the positive examples, thus potentially making the risk negative and leading to overfitting. The non-negative risk estimator
( = =up((g())++) + max 0, L Ewlllo(z) -1)
Σ #EP
Cupl( ())((( -1 (6)
ØEP
=EU
alleviates this problem by forcing the sum of the negative term and the term defined on the unlabeled data to be non-negative, the sum acts an estimate for risk on negative examples
3 Recursive Greedy Risk Minimization
3.1 Decision trees for positive and negative data
We first introduce our recursive greedy risk minimization approach in the fully labeled case. Consider the empirical risk of g : Ed + E on labeled training set D = {(x1 vi)...., (In. Mn)]: R(g)
E( wl(g(x), y), where w = 1/ If predicts a constant on a subset S = (2, y} of the training examples, then the contribution to the total empirical risk is the partial empirical risk R(e; 9) == Ei.w)e wl(v, v). The optimal constant value prediction is r argmin R (v: S) with minimum partial empirical risk (S) = R (uz:
If we switch from a constant value prediction rule to decision stump that uses the split (f,t) then the minimum partial empirical risk for such a decision stump is R (S)s() + R (S)gt), thus the risk reduction for the split (f,t) is
(c Ret (St5t).
In the following, when we need to make the loss function explicit, we will use subscript to indicate that. For example, R Ri (S) and RRqusa (f, S), are the minimum partial empirical risk for a constant-valued prediction on S and the risk reduction for the split (f, t) on S when using the quadratic loss.
When we choose the (J,4) with maximum risk reduction in Algorithm 1, we obtain a recursive greedy risk minimization algorithm that recursively zooms in to an input region with constant prediction,
3

---

then improves the prediction rule in greedy manner by replacing it with the decision stump with minimal empirical risk in that region.
The first main result shows that the Gini impurity reduction and entropy reduction of a split are just scaled versions of the risk reductions when using the quadratic loss and the logistic loss respec- tively. This implies that the standard impurity reduction based decision learning algorithm is in fact performing recursive greedy risk minimization. All proofs are in the appendix.
Theorem 1. (a) For any S D, we have R Rquaa (5) = 2[S), As a consequence, for any S D and any split (t)) [4].
RR (S,15)) = (f. ().
(b) For any S S D, we have R Rogistic (S) (S)) As a consequence, for any S S D and any split (f,t),
Rigiittt (f, (f) = |S| 1 |SIe:Rentropy (f
(10)
3.2 Decision trees for positive and unlabeled data
We are now ready to introduce a recursive greedy risk minimization approach to PU learning. We do this by making two changes to Algorithm 1: the fully labeled dataset S is replaced by a set P' P positive examples and a set U" S U of unlabeled examples, and the split (S, t) chosen to optimize PU version of the risk reduction.
uPU risk reduction We first consider the simpler case of the uPU estimator. Similarly the fully labeled case, if g predicts a constant v on P' and U', then the contribution to the total empirical uPU risk is
Luuu = E wp Wpl(v,+1)
Σ wpl(u,-11 -1)
Σ w wallv, -1).
PEP!
mEU!
The optimal constant value prediction is v'r..' argmin R Ripu (v; P', PU,'") with minimum empirical risk R Ripc (P", = Ripulypern Pi, U'). The uPU risk reduction for the split (f,t) on P",
(P',U") is (f,t; (P - (P/ - R.Pu (P U Ug.)).
(8)
The following result shows that the optimal risk Ripoo (P',U" has closed-form formula and is thus efficiently computable. As a consequence, the uPU risk reduction for a split (f,t) f) is efficiently computable.
Proposition 1. Consider arbitrary p' C and U' C U". Let W, = 1P' W, = |U' wwo -PP' and v²
W₂ W.+Wo'
(a) When using the quadratic loss, we have
R. (P''')
1-00 { 14W +
2² = +00 AAW,+WW)o. W.)o" (1-0"), otherwise.
(11)
(b) When using the logistic loss, we have
(Wp W.) In(")) - (1 v²) In(1 - -a(1-))),, 0< <1, v" E (0, 1].
RP,u(P",U' 0
(12)
-00
v" > 1.
Intuitively, if p' C and U" C U are the examples in a node in the decision tree, then the weights W. and W, serve unbiased estimates of the probabilities p(æ E K, = 1) and p(æ E K, y -1) respectively. See Appendix C for details. Thus x" w,+W, serves as an estimate of the probability of positive examples. Note that Wp [0, 1]. while W, < is unusual in that it contains a negative component and hence can be negative. Consequently, 8" non-negative, but can be larger than though. In particular, if W, p + W, [U'|w, 0, then e +00.
W,

---

unPU risk reduction
For the case of the nnPU estimator, define
RumPu(y; (v; P'U))= Eup((r++1) max 0, Σ wul(u,-1)
Σ upl(u - 11
#EP
æEU"
aeE P
We can then similarly define the risk reduction for the nnPU estimator.
The following result shows that in the nnPU case, the optimal risk RMPu(P (P', U²) also has a closed- form formula and is thus efficiently computable.
Proposition 2. Using the same notations as Proposition we have the following results. (a) When using the quadratic loss, we have
[0, [4WW, W.)'" (1 11-07 -0)",, otherwise.
0" >>
RamPU (U',"")
(14)
(b) When using the logistic loss, we have
RiaPe Caaec(P', (P, Un) { (Wp + W.) W.) (-v0 - (1-""" -n)1) 0< <1
(15)
otherwise.
It is important to note that while in the uPU case, if P' is partitioned into Pf and Ps and U" into Ui and U22 then we have RuPu (u; P', U*) RuPU(u, P4, U1) + (ur P4, U2), we only have (u; P', U*) I RumPu(u, Pt, U1) + REnPU(u. (u. P/. U2)) Thus recursive greedy risk minimiza- tion minimizes upper bound of the partial empirical risk rather than the partial empirical risk. This can be considered the uPU risk in our experiments, which is consistent with the findings in [16].
regularization mechanism. fact, we observe nnPU risk to work better than
Optimizing the split With the above closed-form formula, can then efficiently compute the risk reduction for a given split (f. on (P", "", While there are infinitely many possible / values choose from, note that they often split the dataset in the same way, and if I"s values split IR into multiple intervals, we only need to consider 1 < 1/ < < Imm each chosen from an interval so that we cover all possible cases. While computing the risk reduction for each (f, tt) takes O(IP1) + (U'l) time, we can efficiently get the risk reductions for all of (f, (f,t1)...... (f, tm in O((IP" + (U'D) In([P"| (0"I) + m) time, by sorting the examples according to their values, and going through the thresholds in sorted order. See Appendix E for details.
Invariance properties An interesting property of the greedy recursive learning approach is that is robust to the choice of the loss function in the sense that different loss functions can lead to identical decision trees, as shown in the result below.
Proposition 3. The R' (S) value is the same for the quadratic loss and the savage loss.
Another interesting property is that the optimal prediction among -1 and +1 are often the same when we use different estimators and different loss functions.
Proposition 4. If a node contains the examples P' C and U' CU, v² is as defined in Proposition 1, and the prediction is chosen from {-1,+1} to minimize the empirical risk estimate on P' and U', then the optimal prediction is 21(v" 0.5) 1 for both the uPU and nnPU risk estimate and all the loss functions in Section Intuitively, we predict +1 iff the estimated proportion of positive data at the current node is larger than 0.5.
4 PU Extra Trees
With our PU decision tree algorithms, we can obtain PU random forest algorithm by adapting the random forest algorithm [3] for positive and negative data: repeatedly obtain bootstrap samples for both the positive data and the unlabeled data, then train a PU decision tree for each sample with optimal split chosen over randomly sampled subset of features each time. While choosing the optimal split from a subset of features makes training each decision tree faster, is still the most expensive part in the tree construction process and can potentially be very slow on large dataset. We describe more efficient version that we used in our experiments below. In addition, we introduce a new feature importance score that directly measures a feature's contribution to risk minimization.
5

---

ET (Extra Trees) We develop a more efficient random forest algorithm by using the random- ization trick in the Extra Trees algorithm [13] further reduce the computational cost for finding an optimal split below. Besides sampling only subset of features, only one random threshold for each sampled feature is considered. We implemented a more general version which allows sampling multiple random thresholds for a sampled feature. A complete pseudocode for PU ET is given in Appendix H.
Termination criteria Decision trees can overfit the training data if allowed to grow until each leaf has just one example. Learning is generally terminated early to alleviate overfitting. In our implementation. we terminate when all feature values are constant, when maximum tree depth dmax reached, when the node size falls below threshold Smin. or when the node is pure. node said to be pure if the impurity measure takes value -o in the uPU setting, or value 0 in the nnPU setting.
Risk reduction importance Our feature importance, called risk reduction importance, is the total risk reduction for a feature across all nodes in all the trees. The risk reduction importance a feature is defined as EkEk, K, RR(Js, 4x; Pk, Ux), where K is the of nodes using f splitting feature, (fx: tx.) is the split for node x, and (Px, U,) is the set of PU data at K. This can be averaged across multiple trees in random forest. The risk reduction importance in PU learning is similar to the Gini importance as defined in, for example, [4], whereby the size of the nodes is taken into account. This is beneficial otherwise features often used in splitting small datasets may appear very important as compared to features used in splitting large datasets, even though it does not contribute much reducing the risk and improving classification performance. To demonstrate the effect of taking data size into account, a normalized risk reduction can be defined by dividing the risk reduction by the total weight of the examples.
5 Experiments
In this section we compare PU Extra Trees with several other PU learning methods. Selected tree- based methods include NaivePUET whereby ET is trained on the PU dataset by simply treating data as N data; PUBaggingET which uses PUBagging from [23] with ET base classifier; and SupervisedET where ET is trained on the original fully labeled dataset (expected to be upper bound for tree based PU methods). To further study the effectiveness of our PU Extra Trees algorithm also compare against neural network based methods including baseline method uPU [11, 10] and two state of the art methods nnPU [16] and Self-PU [6]. We ran experiments on heterogeneous devices. In particular, random forests Intel i7-1 1700 or AMD Epyc 7702p CPU. Neural networks were trained on one of NVIDIA RTX A4000 NVIDIA RTX A6000 GPU due to the lack of identical devices. While the running times are not always comparable and thus not provided in the main text, experiments show that our current implementation of PU ET takes seconds to train single-tree random forest on modest hardware. See Appendix for details.
trained using 32GB RAM and one of Intel 17-10700,
Datasets We consider a selection of common datasets for classification from LIBSVM [5], as well as MNIST digits [19], the intrusion detection dataset UNSW-NB15 [25] and CIFAR-10 [17] to demonstrate the versatility of our method. Table is summary of the benchmark datasets.
Table 1: Benchmark datasets. *; random 80%-20% train-test split was used train-test splits were provided.
Name
Train
Test
Feature
π
mushrooms*
6499
1625
112
0.52
20News
11 314
7 532
300
0.56
covtype. binary
464 809
116 203
54
0.51
epsilon
400 000
100 000
2 000
0.5
MNIST
60 000
10 000
784
0.5
CIFAR-10
000
10 000
3
0.4
UNSW-NB15
175 340
82 331
39
0.68
The 20News, epsilon, MNIST and CIFAR- 10 datasets were processed in the same way as in [16] for consistency. Definitions of labels ('positive' 'negative") are follows: For 20News. 'alt.,

---

comp., misc., rec.' vs 'sci., soc., talk.;; for MNIST, '0,2,4,6,8'' vs ',,3,5,7,9' for CIFAR-10, "airplane, automobile, ship, truck' vs 'bird, cat, deer, dog, frog, horse'; for UNSW-NB15, all attack types make up the P class and the benign data makes up the N class; for mushroom and covtype, the most prominent class makes up the P class; and epsilon dataset is provided with P and N classes. GloVe pre-trained word embeddings [27] were used for 20News with average pooling over each document. Each feature in the covtype and UNSW-NBI5 15 datasets was scaled between O and when using uPU and nnPU there is large mismatch in scales between the features which seemed to significantly reduce performance of the methods. No such scaling of the data is required for PU ET as performance does not seem to be affected in such cases.
To convert the PN data to PU data we follow the experimental setup in [16] whereby 1000 positive examples are randomly sampled to form the P set, and the entire dataset is used for the U set. In practice it may be the case that π is not known a-priori, in which case there are methods for estimating using only PU data, for example, in [7]. or [28].
Model hyperparameters Following common practice [26, 13], the default hyperparameters for PU ET are: 100 trees, no explicit restriction on the maximum tree depth, sample F = [V features out of total of d features and sample 7 = threshold value when computing an optimal split. The size of the bootstrap sample for PUBaggingET is set to the default value of the dataset size.
The architectures for the neural networks used in uPU, nnPU and Self-PU were copied from [16] for the 20News, epsilon, MNIST and CIFAR-10 10 datasets. A 6 layer MLP with ReLU was used for MNIST, Covtype, Mushroom and UNSW-NB15; similar model was used for ep- silon while the activation was replaced with Softsign; a 5 layer MLP with Softsign was used for 20News. All hidden layers had width 300 for the MLPs. The model for CIFAR-10 was the 13 layer CNN: (32*32*3, ()((C,))))133336,,... (003)))))2 where the input is 32*32 RGB image, C(3*3,96,1) means
192, 3, 192,))
1(1$1,192,1) (1, 10,10)00000-000000000000 96 channels of 3*3 convolutions with stride followed by ReL.U, [.1*2 means there are two such layers. For the remaining datasets we used 6-layer MLP with ReLU [18, 14] (more specifically, 1:300-300-3003000
For each dataset the neural networks were trained for 200 epochs. The batch size, learning rate, use of batch-norm (for datasets not included in [16]), weight decay and choice of optimiser were tuned for each dataset.
It is noteworthy that spend little effort to tune PU ET hyperparameters and simply use the same hyperparameters on all datasets. In addition, PU ET seems to be robust to hyperparameter choice in that the default selection tends to result in strong predictive performance with decreased training times. See Appendix for results from hyperparameter tuning experiment. On the other hand, neural nets sensitive hyperparameter choice, and significant tuning is often needed for each dataset.
5.1 Classification performance
To take into account of the randomness in the learning algorithms, we train each model five times on the same dataset, then report the mean and standard deviation of the accuracy and the F-score. Results for uPU, nnPU and Self-PU were reproduced to the best of our ability, particularly on the datasets that were included in the original results section of the respective papers.
Effect of loss function and risk estimator on PU ET We first evaluate the effect of different loss functions and risk estimators for PU ET. The results are shown in Table 2 and Table 3. PU ET with nonnegative risk estimator seems to perform about as well using either quadratic or logistic loss. Unbiased risk estimator seems to lead to overfitting, but less so with logistic loss. Logistic loss leads to better performance than quadratic loss when using unbiased risk estimator. Note that (11) implies that quadratic loss encourages aggressive splitting until all examples are positive as a loss of -oo can be achieved in this case, while (12) implies that logistic loss has less aggressive splitting behavior as loss of ooo is achieved when the total weight of positive examples exceeds the total weight of unlabeled examples. As discussed previously, once we achieve an impurity value of ooo in uPU, we stop splitting. The more aggressive splitting behavior of quadratic loss leads to deeper trees that tend to overfit more than the logistic loss in general. This is consistent with results from additional experiments in Appendix K.
Comparison of PU ET with other tree-based PU learning methods We now compare our PU ET algorithm with several tree-based basclines to further study the effectiveness of our novel PU tree
7

---

Table 2: Accuracy mean% (sd) on the test set for PU ET using various PU data based risk estimators.
Unbiased risk estimator
Nonnegative risk estimator
Dataset
Quadratic Loss
Logistic Loss
Quadratic Loss
Logistic Loss
Epsilon
50.04 (0.00)
50.67 (0.08)
57.39 (0.76)
57.83 (0.70)
20News
43.64 (0.05)
73.44 (0.87)
83.34 (0.22)
83.34 (0.31)
Covtype
48.72 (0.00)
72.63 (0.87)
76,51 (0.52)
75.63 (0.52)
Mushroom
0.607 (0.48)
99.02 (0.32)
99.70 (0.24)
99.36 (0.48)
MNIST
50.74 (0.0)
89.05 (0.61)
93.60 (0.39)
94.01 (0.19)
CIFAR-10 10
(0.0.(0.01)
75.30 (0.66)
79.74 (0.37)
79.86 (0.39)
UNSW-NB15
47.18 (0.15)
83.89 (1.03)
82.24 (0.86)
81.51 (1.58)
Table 3: F mean% (sd) on the test set for PU ET using various PU data based risk estimators.
Unbiased risk estimator
Nonnegative risk estimator
Dataset
Quadratic Loss
Logistic Loss
Quadratic Loss
Logistic Loss
Epsilon
0.00 (0.00)
4.18 (0.59)
39.52 (1.19)
40.25 (1.38)
20News
0.43 (0.17)
72.65 (1.11)
85.33 (0.22)
85.26 (0.28)
Covtype
0.11 (0.01)
68.44 (1.25)
75.19 (0.37)
74.20 (0.58)
Mushroom
39.02 (1.19)
99.04 (0.32)
99.71 (0.24)
99.38 (0.47)
MNIST
0.00 (0.00)
88.06 (0.74)
93.49 (0.42)
93.90 (0.19)
CIFAR-10
0.02 (0.04)
61.33 (1.44)
71.31 (0.43)
71.67 (0.53)
UNSW-NB15
7.97 (0.47)
86.33 (0.87)
85.65 (0.59)
85.17 (1.15)
learning method. The results are shown in Table 4 and Table The results support the effectiveness of our algorithm. Our PU ET with nnPU risk estimator and quadratic loss significantly outperforms both NaivePUET and PUBaggingET, particularly in terms F-scores. PU ET shows strong performance even compared to SupervisedET, though often using a small proportion of the positive labels only.
Table 4: Accuracy mean% (sd) on the test set for various tree based methods. full supervision was used during training.
Original dataset with
Dataset
SupervisedET+
PU ET
NaivePUET
PUBaggingET
Epsilon
73.55 (0.08)
57.39 (0.76)
50.04 (0.00)
50.04 (0.00)
20news
85.39 (0.12)
83.34 (0.22)
43.63 (0.05)
43.75 (0.06)
Covtype
95.90 (0.02)
76.51 (0.52)
48.71 (0.00)
48.71 (0.0)
Mushroom
100 (0.00)
(0.24)
53.85 (0.32)
62.76 (0.84)
MNIST
98.11 (0.05)
93.60 (0.39)
50.74 (0.00)
50.74 (0.00)
CIFAR 10
85.02 (0.19)
79.74 (0.37)
60.00 (0.00)
60.0 (0.00)
UNSW-NB15
86.57 (0.05)
82.24 (0.86)
44.95 (0.01)
44.97 (0.02)
Table 5: F mean% (sd) on the test set for PU ET using various PU data based risk estimators. t: Original dataset with full supervision was used during training.
Dataset
SupervisedETt
PU ET
NaivePUET
PUBaggingET
Epsilon
72.96 (0.08)
39.52 (1.19)
0.00 (0.00)
0.00 (0.00)
20news
87.40 (0.11)
85.33 (0.22)
0.38 (0.19)
0.82 (0.18)
Covtype
95.97 (0.02)
75.19 (0.37)
0.05 (0.01)
0.06 (0.01)
Mushroom
100 (0.00)
99.71 (0.24)
19.68 (2.04)
45.3 (0.84)
MNIST
98.09 (0.05)
93.49 (0.42)
0.00 (0.00)
0.00 (0.00)
CI
80.30 (0.24)
71.31 (0.43)
0.01 (0.02)
0.02 (0.02)
UNSW-NB15
88.96 (0.04)
85.65 (0.59)
0.08 (0.06)
0.11 (0.06)
Comparison of PU ET with neural network methods We compare PU ET with nnPU risk estimator and quadratic loss against uPU neural nets, nnPU neural nets and Sel The results are shown in Table 6 and Table 7. PU ET shows strong performance in terms of both accuracy and score wide variety of datasets compared to neural network based models.
8

---

Table 6: Accuracy% mean (sd) on the test set for PU ET with nonnegative risk estimator and quadratic loss and three neural network based PU learning methods. Self-PU was run without self-calibration due to limitations with available hardware.
Neural Network
Dataset
PU ET
uPU
nnPU
Self-PU
Epsilon
57.39 (0.76)
61.79 (2.57)
73.80 (0.49)
50.05 (0.0)
20News
83.34 (0.22)
44.95 (1.09)
74.11 (3.65)
62.87 (2.89)
Covtype
76.51 (0.52)
72.38 (1.23)
71.64 (0.66)
54.67 (0.40)
Mushroom
99.70 (0.24)
98.09 (1.03)
99.04 (0.54)
99.25 (0.61)
MNIST
93.60 (0.39)
55.95 (1.17)
93.08 (0.46)
93.13 (0.41)
CIFAR-10
79.74 (0.37)
62.68 (2.95)
81.87 (04.20)
88.22 (0.51)*
UNSW-NB15
82.24 (0.86)
76.62 (0.01)
76.63 (0.02)
76.73 (0.18)
Table 7: F mean% (sd) the test set for PU ET with nonnegative risk estimator and quadratic loss and three neural network based PU learning methods. *: Self-PU was run without self-calibration due to limitations with available hardware.
Neural Network
Dataset
PU ET
uPU
nnPU
Self-PU
Epsilon
39.52 (1.19)
43.44 (8.14)
71.53 (0.46)
0.00 (0.00)
20News
85.33 (0.22)
12.95 (3.82)
78.05 (3.81)
71.78 (6.85)
Covtype
75.19 (0.37)
69.56 (1.77)
68.29 (0.93)
0.501 (2.55)
Mushroom
99.71 (0.24)
98.13 (1.02)
99.06 (0.53)
99.27 (0.60)
MNIST
93.49 (0.42)
19.13 (3.82)
92.77 (0.60)
92.96 (0.47)
CIFAR-10
71.31 (0.43)
32.43 (25.03)
76.01 (7.62)
85.51 (0.60)*
UNSW-NB15
85.65 (0.59)
82.47 (0.01)
82.48 (0.02)
80.18 (0.28)
5.2 Feature Importance
Interpretability a desirable property of machine learning algorithm, but neural networks are often hard to interpret. In contrast, tree based methods generally casier to interpret. We illustrate risk reduction importances of both PU ET and PN (positive-negative) ET on the UNSW-NB15 and the MNIST datasets (lighter color indicates higher score) in Figure and Figure 2 respectively.
0.20
0.20
Importacce
0.15
Impurfance
0.05
dt rett... Soot
ct sv
trans
3
sic
repporta
Figure Risk reduction importances on UNSW-NB15. Left: PU ET. Right: PN ET.
For MNIST, the plot of the importance scores for PU ET for each digit often suggests the shape of the digit. On the other hand, the Appendix provides some additional figures that show that the normalized risk reduction importance makes many more pixels more important. This observation consistent with our discussion in Section 4. Interestingly, the importances for PU ET appear to be very similar to those for PN ET (visually similar importance maps for MNIST, and qualitatively

---

similar importance values which give similar feature rankings for UNSW-NB15), This suggests that the PU model is likely quite similar to the PN model.
Figure 2: Risk reduction importances learnt from ET classifier on MNIST digits. Top: PU ET with nonnegative risk estimator and quadratic loss. Bottom: PN ET with Gini impurity.
6
Related Work
PU learning was initially studied in [9, 21], and many approaches have been developed based on different assumptions the data generation mechanism.
The two-step approach discussed in the introduction have been adopted in many papers with numerous instantiations. We refer the readers to [2] for comprehensive list.
Another important line of work, which is most related the-art performance recently, minimizes a risk estimate hased on a weighted dataset of positive and negative examples obtained by transforming the PU dataset [20, 12, 11, 16]. Our work follows the risk minimization approach, but we develop general risk minimization algorithms for learning tree models, that allows exploiting the under-explored potential of random forests.
work and has achieved the state-of-
Numerous works have been done on tree-based methods, and random forest algorithms are among the most successful ones [3. 13, 1]. In the PU learning literature, PU decision trees were explored in early works [8, 21], and PU bagging [23] has been explored for SVMs [23] and decision trees [29]. All of these approaches do not aim to directly minimize the risk.
Our recursive greedy risk minimization framework gives new interpretation to existing tree learning algorithms for positive and negative data, and allows us to develop new algorithms for positive and unlabeled data. In addition, our approach allows us to formulate a new feature importance score that directly measures feature's contribution to risk minimization.
7 Conclusions
Random forests perform very well on fully supervised learning methods, but its potential in PU learning has been under-explored due to the strong emphasis on neural networks and the lack of principled method for learning decision trees from PU data. We fill this gap in this paper. We first consider learning from positive and negative data, and develop a recursive greedy risk minimization approach for learning decision trees, and show that with suitable choice of loss functions, its instantiations are equivalent to standard impurity-based decision tree learning algorithms. We extend this approach to the PU setting, and develop very efficient random forest algorithm which requires little hyperparameter and yet strong performance against the state-of-the-an PU learning algorithms. Our approach supports new feature importance score that directly measures feature's 's contribution to risk mnimization.
Our work opens up some new opportunities to build tree models. First, decision trees can easily overfit the training set, and various heuristics have been used practice alleviate overfitting. Our recursive greedy risk minimization framework provides an alternative way to control the size of the learned decision by always expanding the node with the largest risk reduction until the risk reduction is smaller than a threshold or when the tree size is larger than threshold. Second, we focused on quadratic loss and logistic loss our experiments, but we can also study alternative losses such as the hinge loss, or double hinge loss.
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Dr Miao Xie from AARNet for his valuable suggestions. This work was funded by The University of Queensland Cyber Security Seed Funding.
References
[1] Susan Athey, Julie Tibshirani, and Stefan Wager. Generalized random forests. arXiv preprint: urXiv.1610.0122 2016.
[2] Jessa Bekker and Jesse Davis. Learning from positive and unlabeled data: A survey. Machine Learning, 109(4):719-760, 2020.
[3] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[4] Leo Breiman, Jerome H Friedman, Richard A Olshen, and Charles J Stone. Classification and regression trees. Routledge, 2017.
[5] Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM Iransactions intelligent systems and technology (TIST), 2(3):1-27, 2011.
[6] Xuxi Chen, Wuyang Chen, Tianlong Chen, Ye Yuan, Chen Gong, Kewei Chen, and Zhangyang Wang. Self-pu: Self boosted and calibrated positive-unlabeled training. International Conference Machine Learning, pages 1510-1519. PMLR, 2020.
[7] Marthinus Christoffel, Gang Niu, and Masashi Sugiyama. Class-prion estimation for learning from positive and unlabeled data. In Asian Conference on Machine Learning, pages 221-236.
PMLR, 2016.
[8] Francesco De Comité, François Denis, Rémi Gilleron, and Fabien Letouzey. Positive and unlabeled examples help learning. In International conference on algorithmic learning theory, pages 219-230. Springer, 1999.
[9] François Denis. PAC learning from positive statistical queries. In International conference on algorithmic learning theory, pages 112-126. Springer, 1998.
[10] Marthinus Du Plessis, Gang Niu, and Masashi Sugiyama. Convex formulation for learning from positive and unlabeled data. International conference on machine learning, pages 1386-1394. PMLR, 2015.
[11] Marthinus C Du Plessis, Gang Niu, and Masashi Sugiyama. Analysis of learning from positive and unlabeled data. Advances in neural information processing systems, 27, 2014.
[12] Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In Proceedings of the 14th ACM SIGKDD international conference Knowledge discovery and data mining, pages 213-220, 2008.
[13] Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63(1):3-42. 2006.
[14] Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXivv/710.1 /278, 2017.
[15) Fengxiang He, Tongliang Liu, Geoffrey I Webb, and Dacheng Tao. Instance-dependent pu learning by bayesian optimal relabeling. arXiv preprint arXiv: 02180, 2018.
[16] Ryuichi Kiryo, Gang Niu, Marthinus C du Plessis, and Masashi Sugiyama. Dositive-unlabele learning with non-negative risk estimator. arXiv preprint arXiv: 2017.
[17] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[18] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.

---

[19] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227--2) 1998.
[20] Wee Sun Lee and Bing Liu. Learning with positive and unlabeled examples using weighted logistic regression. In ICML, volume 3, pages 448 2003.
[21] Fabien Letouzey, François Denis, and Rémi Gilleron. Learning from positive and unlabeled examples. International Conference on Algorithmic Learning Theory, pages 71-85. Springer, 2000.
[22] Bing Liu, Yang Dai, Xiaoli Li, Wee Sun Lee, and Philip Yu. Building text classifiers using positive and unlabeled examples. In Third IEEE international conference on data mining, pages 179-186. IEEE, 2003.
[23] Fantine Mordelet and J-P Vert. bagging svm to learn from positive and unlabeled examples. Pattern Recognition Letters, 37:201-209, 2014.
[24] Fantine Mordelet and Jean- Shan-hillippe Vert. Prodige: Prioritization of disease genes with multitask machine learning from positive and unlabeled examples. BMC bioinformatics, 12(1))1-15, 2011.
[25] Nour Moustafa and Jill Slay. Unsw-nb15 15: a comprehensive data set for network intrusion detec- tion systems (unsw-nb15 network data set). In 2015 military communications and information systems conference (MilCIS), pages 1-6. IEEE, 2015.
[26] Pedregosa, G. Varoquaux, A. Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[27] Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532 1543, 2014.
[28] Harish Ramaswamy, Clayton Scott, and Ambuj Tewari. Mixture proportion estimation via kernel embeddings distributions. International conference on machine learning, pages 2052-2060. PMLR, 2016.
[29] Bangyu Wu, Weirong Qiu, Junxiong Jía, and Naihao Liu. Landslide susceptibility modeling using bagging-based positive-unlabeled learning. IEEE Geoscience and Remote Sensing Letters, 18(5):766-770. 2021.
[30] Zhiang Wu, Jie Cao, Yaqiong Wang, Youquan Wang, Zhang, and Junjie Wu. hpsd: hybrid pu-learning-baset spammer detection model for product reviews. IEEE transactions on cybernetics, 5095)11555-1666 2018
12


Reviews:
[{"review_id": "xhXsADCmBRp", "reviewer": "Reviewer_4GSs", "summary": "This paper adapts the decision tree growing algorithm to handle positive-unlabeled learning, i.e. learning with only positive and unlabeled examples. The authors first note that the standard tree growing algorithm can be interpreted as recursive greedy risk minimization. They thus propose to adapt this idea to grow a tree that minimizes two specific risk estimators for the positive and unlabeled settings, namely uPU and nnPU. For these two risks, they propose a closed-form solution of the minimum risk and the optimum solution in a nodes that can be exploited to efficiently find the best split points at a tree node. Experiments are carried out random forests of such trees on several classification tasks, where the approach is shown to be competitive with neural networks algorithm based on the minimization of similar risk estimates.", "questions": "See the previous point.\n", "limitations": "Given the lack of a comparison against other competitors for PU learning with trees or forests, I think the paper does not position well the proposed method in the existing literature. I would suggest to at least add the two simple baselines suggested above in the comparison.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and easy to follow.\n\nThe idea explored in the paper is interesting. The adaptation of decision tree splits to minimize the PU risks (uPU and nnPU) is sound and original to the best of my knowledge. The resulting algorithm is as computationally efficient as the standard tree growing algorithm, which is a very nice result. I think the mathematical developments are sound (I quickly checked the supplements and proofs).\n\nSome comments on the method part:\n\n- I would have appreciated some more discussions about uPU and nnPU. I'm not sure why uPU can cause overfitting and how nnPU solves this issue.\n\n- Results in Theorem 1 were already known to me and I thought they were widely known. In the case of quadratic loss and GINI entropy, this is shown in the CART book (see Sections 4.6.2 and 11.2):\nBreiman et al., Classification and regression trees, Taylor and Francis, 1984.\nIn the case of logistic loss and entropy however, I could not find a reference.\n\n- I noted the few mistakes in the propositions that were corrected in the supplement. They need to be corrected in the paper obviously. I think that you should make it clear in the paper that $v^*_{P',u'}$ is not equal to what is denoted by $v^*$ in the case of logistic loss also. The notation $v^*$ is a bit confusing. It should be clear that the exact form of $v^*_{P',u'}$ is only given in the supplement in this case.\n\n- I'm a bit puzzled by the fact that the risk can be equal to $-\\infty$ in the case of uPU as soon as $v^*$ becomes higher than 1. Does it mean that as soon as $v^*$ in a given node is greater than 1, one can not split a node anymore (because the risk can not be reduced further)? Since this can happen when there are still positive and unlabeled example in a node, this is a bit counterintuitive to me. Overall, I think that more discussion is needed to explain the consequence on tree growing of using these two risks uPU and nnPU. When do we stop splitting a branch for example?\n\n- About PU ET, the authors mentioned that they implemented a more general version which allows sampling multiple random thresholds for sampled feature. This is not what is done in the pseudocode in the appendix and this version does not seem to be tested in the experiment.\n\n- The discussion about risk reduction importance is confusing. I think the exact formulas used to compute feature importances should be provided because what the authors suggest in their last sentence as a generalization of Gini importance (i.e., summing the risk reduction divided by the total weight of the examples) does not correspond to what is done in Gini importance. In the CART book, the Gini importance of a feature (or more generally the mean decrease of impurity importance) is the sum over all nodes where the feature is used to split of the impurity reduction (Equation (1) in the paper) multiplied by the proportion of training examples that fall into that node. Thus, unlike what is said in the paper, the size of the node is taken into account. As a consequence also, Gini importance also measure a feature's contribution to risk minimization.\n\nThe experimental part is interesting for comparing the different proposed implementations, as well as for comparing them against neural networks. They are lacking along several lines however.\n\nFirst, I'm missing an explanation as to why quadratic loss with unbiased risk estimator is performing so poorly. In standard trees, changing Gini index for entropy does not make strong differences. Quadratic loss is also working well with the nonnegative risk estimator. I'm wondering if there is not a bug somewhere. In any case, this counterintuitive result should be discussed.\n\nSecond, some baselines are missing in the experiments that would allow to better understand how good the approach is. The comparison with neural networks is interesting but not very informative. One could change the complexity of the networks to reach better performance (or switch to CNN on the MNISTand CIFAR10 problems). I think that the comparison should include more baselines or competitors based on trees or forests to really assess how good the new impurity measures is with respect to common approaches to deal with PU learning.\n\nFor example, I would include at least a standard ET model trained on the fully labeled training set, as well as a standard ET model trained by treating all unlabeled examples as negative. This would allow to see where PU ET lies between these two extremes. I think that the comparison should actually also include some popular competitors such as those presented in [11] (as a simple improvement of the second naive baseline), [22] (as a simple adaptation of forests), and also [7]. This latter method, and the others, are excluded in the related work discussion because they are not based on the same risk estimators as PU ET in the paper. I think this is not a valid argument. One would like precisely to see whether there is any benefit in using the new risk with respect to existing approaches that can be applied with the same family of classifiers.\n\nTwo other more minor limitations of the experiments: \n- Only artificial PU problems are considered that perfectly match the theoretical setting and the impact of the size of the unlabeled set is not studied.\n- Only the Extra-Tree algorithm is considered. Because of its extreme randomization of the split points, the impact of the impurity measure should be very much reduced. I think it would be interesting to experiments with standard trees or RF. Even if PU ET works well, PU+DT or PU+RF could be actually worse because of some unexpected bias introduced by the new impurity measures.\n\nUpdate after the authors' rebuttal:\n\nI'm very impressed by the authors' response, which addresses almost all my complaints. I think the comparison against the baselines that I suggested proves that the approach is very strong empirically (in addition to be very well motivated theoretically). The only downside is that including all these new experiments and discussions will result in important changes with respect to the paper that we have reviewed but I'm confident that the authors will implement these changes properly.\n\nI already recommended acceptance but I'm happy to raise my score further after this rebuttal.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X3BhwOWafHp", "reviewer": "Reviewer_xssD", "summary": "This paper proposes a decision tree learning algorithm in PU framework. In this setup only (a subset of) positive class labels are provided, whereas the remaining data is considered unlabeled (it may contain both negative and positive class samples). The algorithm is heavily based on CART-style greedy tree growing procedure where splitting (or purity) criterion is replaced by PU-specific loss. They extend it to train ensemble of trees via Extra Trees framework. ", "questions": "Please address weaknesses in the previous section and limitations in the section below.", "limitations": "I am not sure how the method is extended to multiclass setting. I imagine it will one-vs-one. In this case, computational runtime might be an issue since K trees need to be induced (i.e., one per class).", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Nice and clear presentation;\n- Experiments contains important ablation studies, such as comparison of different losses;\n- It is nice to see that the method is relatively robust to different factors, such as the choice of loss function;\n- Derivation of the empirical risk specifically to quadratic and logistic losses is definitely a valuable contribution.\n\nWeaknesses:\n- Novelty. I am not familiar with PU literature but it looks there have been previous works on the topic of PU learning for DTs. Authors claim that the proposed approach is \"new DT learning algorithm that directly minimizes PU-data expected risk\". However, the algorithm itself resembles CART + \"modified purity criterion\". By \"modified purity criterion\", I mean instead of using gini index or cross-entropy (which will be inapplicable in PU setting), authors use PU specific loss which requires a minor modification and straightforward extension to the existing tree growing procedure. On top of that, in order to construct ensemble of trees, authors use well known framework -- ExraTrees.\n- Experiments. Authors compare against neural net only which is fine. However, it is critical to have other tree-based baselines given that authors mention previous works on this topic.\n\n\n\n---- After Rebuttal --------\n\nExperiments. Afters addressed my concerns regarding comparison with tree-based baselines. Thanks!\n\nNovelty. I still think that the method can be summarized as a modified impurity criterion + regularization. Although there seem to be no literature of such approaches for PU, but semi-supervised learning (SSL) trees use such greedy procedure (see below Levatić et al.).\n\nJ. Levatić, M. Ceci, D. Kocev, and S. Džeroski. Semi-supervised classification trees.\n\nGiven all these, I still think that the paper lacks a significant level of contribution in terms of novelty. I will keep my original score.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BHPHqG0AtJ", "reviewer": "Reviewer_Jd1V", "summary": "In the present paper, the authors focus on the problem of PU learning, a peculiar ML setting where the dataset of a binary classification problem only contains positive and unlabeled samples (no negative ones). The main goal is to derive an algorithm for training ensembles of decision trees in this setting (the authors choose the ExtraTrees as a simple and efficient solution), and the required step is a connection between the usual impurity reduction schemes used in normal decision trees and the modified risk minimization problem of the PU setting. Once the ad hoc splitting method is defined, the authors proceed to compare the novel method with some NN baselines. Moreover, they argue that the ExtraT setting allows an interpretation of the learned model through the typical feature importance evaluation, in this case directly connected to the PU risk minimization problem.\n\nAFTER REBUTTAL\nThe empirical evaluation of the proposed method has been improved in the revised version and most of the concerns raised by the reviewers have been adequately addressed.", "questions": "- lines 92-93-94: it is not clear where these alternative losses are employed in this paper. Are these definitions truly necessary?\n- in the nnPU risk, the authors propose enforcing a non-negative contribution to the negative examples. This was already proposed in another paper, but it is necessary for a new reader to have some explanation on why this assumption is useful, and when it may fail or cause even more over-fitting than the unbiased estimator.\n- 147-151 : these lines are a little confusing as unbiased estimates of probabilities seem not to fall in the correct interval 0<p<1. could the authors clarify this passage?\n- 226-233: this paragraph seems to assume that the reader is familiar with the previous work of the authors, but the explanation of the problem setting where the method was assessed should be self-contained.\n- 271-275 and figure 2: this result seems very surprising, especially given that the performance in the PU setting cannot be as good as the one in the PN setting. Can the authors expand on the sentence \"the PU model is likely quite similar to the PN model\" and look at this more thoroughly?\n\nI believe the authors need to find some way to access better computational resources in order to offer better numerical support for their results:\n- 220-222: Assessing the computational cost of a novel learning method should be one of the important points of the paper that introduces it. The short comment provided here seems very vague.\n- in lines 238-240 the authors state that the standard parameters for extra trees were employed, however, in the tables (e.g. 2-3) the parameters seem to differ. Again, it seems that the computational constraints were too many for the authors to perform their numerical tests thoroughly.\n- Self-PU seems to work very well (and possibly better than the ET alalgorithm), but the authors admit that the self-calibration was not implemented due to computational constraints. Without it a proper assessment becomes somewhat hard.\n- in lines 286-289, the authors mention other attempts at employing decision trees in the PU setting, but none is tested and compared against the novel method.\n-Hyperparameter tuning (through crossvalidation) is often key in the context of ensembles of trees but the authors completely skip it due to the lack of computational resources.", "limitations": "The authors do not comment on the possible limitations of this work. Please read above for my comments and perplexities.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Given the simplicity and interpretability of decision trees, and their effectiveness when employed in ensembling methods, the contribution of the authors seems pretty relevant: the definition of the learning step in the PU setting is not completely trivial. Moreover, if the connection between typical impurity reduction and risk minimization was not previously shown in other works (which would be rather surprising), the framework presented by the authors could help employ these methods in diverse settings where the typical learning strategy would not be applicable. \n\nHowever, this work heavily builds (and often relies) on previous work [10,15], and most of the presented content seems not to be very surprising or complicated. All the results follow straightforwardly from the definition of the uPU and the nnPU risks, which however are not novel. The biggest limitation of this work, in my view, is in the numerical experiments presented by the authors, which did not thoroughly explore the potential of their new method, nor compare it with optimized competitors due to a lack of computational power.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ACVjXFY8oGe", "reviewer": "Reviewer_J3hT", "summary": "This paper proposes new random forest algorithms for PU-learning and further gives a new interpretation of decision tree algorithms for positive and negative data as recursive greedy risk minimization algorithms. Specifically, the authors extend the popular risk estimator on PU data to split criteria of tree-based methods. Conclusively, it is an interesting trial for both PU-learning and tree-based methods.\n\nAFTER REBUTTAL:  Authors have solved most of my concerns. I plan to increase my score and suggest acceptance of this work.", "questions": "Questions/suggestions\n1. Could authors provide more detailed experimental settings to verify the results. It’s acceptable that a tree-based method could not outperform deep neural network with lower time cost or better interpretability.\n2. Authors may add the missing computational time details and a comparison of computational considerations between the proposed PU ET and recent PU learning methods. I am more concerned of actual time consumption compared with deep neural networks.\n3. More settings in PU learning may be explored.\n4. Could authors provide a better illustration of interpretability other than feature importance, maybe from the perspective of the decision-making path.\n5. In the Introduction (Section 1), the authors claim that “Existing tree-based methods have not been designed to directly minimize the loss.”. Combined with the propositions in Recursive Greedy Risk Minimization (Section 3) such declaration and theorem seem a bit hand-wavy since the nature of a decision tree could be perceived as utilizing different loss functions that evaluate the split based on the purity of the resulting nodes.\n", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The motivation of this paper is strong. The extension of popular risk estimator on PU data to the tree-based methods is also very interesting at least for me.\n2. This paper provides complete theories and is easy to follow.\n\nWeaknesses\n1. Several promising properties of tree-based methods like fastness and interpretability are not fully illustrated in the paper. No significant advantages are showed compared with existing PU methods. Especially for the perspective of interpretability, only feature importance is not convincing enough considering similar works could be also be done by neural networks. \n2. The reported performances of uPU, nnPU and Self-PU in this paper have a large gap compared with other recent papers [1][2][3] and this makes me confused. Could authors provide more detailed experimental settings to verify the results?\n3. Several important data settings in PU learning like data imbalance are not mentioned. Plus, does the proposed approach rely on the \"selected completely at random\" (SCAR) assumption?\n\n[1] Li, Changchun, et al. \"Who Is Your Right Mixup Partner in Positive and Unlabeled Learning.\" International Conference on Learning Representations. 2021.\n[2] Chen, Hui, et al. \"A variational approach for learning from positive and unlabeled data.\" Advances in Neural Information Processing Systems 33 (2020): 14844-14854.\n[3] Chen, Xuxi, et al. \"Self-pu: Self boosted and calibrated positive-unlabeled training. \"International Conference on Machine Learning. PMLR, 2020.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept