Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: The paper is well written and easy to follow.

The 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).

Some comments on the method part:

- 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.

- 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):
Breiman et al., Classification and regression trees, Taylor and Francis, 1984.
In the case of logistic loss and entropy however, I could not find a reference.

- 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.

- 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?

- 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.

- 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.

The 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.

First, 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.

Second, 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.

For 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.

Two other more minor limitations of the experiments: 
- 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.
- 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.

Update after the authors' rebuttal:

I'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.

I already recommended acceptance but I'm happy to raise my score further after this rebuttal.
questions: See the previous point.

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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: Strengths:
- Nice and clear presentation;
- Experiments contains important ablation studies, such as comparison of different losses;
- It is nice to see that the method is relatively robust to different factors, such as the choice of loss function;
- Derivation of the empirical risk specifically to quadratic and logistic losses is definitely a valuable contribution.

Weaknesses:
- 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.
- 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.



---- After Rebuttal --------

Experiments. Afters addressed my concerns regarding comparison with tree-based baselines. Thanks!

Novelty. 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.).

J. Levatić, M. Ceci, D. Kocev, and S. Džeroski. Semi-supervised classification trees.

Given all these, I still think that the paper lacks a significant level of contribution in terms of novelty. I will keep my original score.
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).
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

AFTER REBUTTAL
The 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.
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. 

However, 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.
questions: - lines 92-93-94: it is not clear where these alternative losses are employed in this paper. Are these definitions truly necessary?
- 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.
- 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?
- 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.
- 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?

I believe the authors need to find some way to access better computational resources in order to offer better numerical support for their results:
- 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.
- 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.
- 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.
- 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.
-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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

AFTER REBUTTAL:  Authors have solved most of my concerns. I plan to increase my score and suggest acceptance of this work.
strengths_and_weaknesses: Strengths
1. 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.
2. This paper provides complete theories and is easy to follow.

Weaknesses
1. 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. 
2. 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?
3. 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?

[1] Li, Changchun, et al. "Who Is Your Right Mixup Partner in Positive and Unlabeled Learning." International Conference on Learning Representations. 2021.
[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.
[3] Chen, Xuxi, et al. "Self-pu: Self boosted and calibrated positive-unlabeled training. "International Conference on Machine Learning. PMLR, 2020.

questions: Questions/suggestions
1. 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.
2. 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.
3. More settings in PU learning may be explored.
4. Could authors provide a better illustration of interpretability other than feature importance, maybe from the perspective of the decision-making path.
5. 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.

limitations: Yes
review_title: null

Meta-review: metareview: This paper proposes a decision tree learning approach with only positive and unlabeled examples. The reviewers are concerned that the novelty of the proposed approach is not high. However, they appreciate that the paper is clearly written, the idea of the proposed approach is reasonable, and comprehensive experiments are conducted. Therefore, I recommend accepting the paper. 
confidence: Certain
Decision: Accept