Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors propose an alternative decision tree model, where the splitting criteria/decision boundary are convex polytopes instead of axis aligned halfplanes or even more general oblique hyperplanes.

One advantage of this is that it gives us another mechanism to add model capacity (for traditional decision trees, model capacity is typically controlled by adding trees or increasing depth). The proposed approach adds capacity by making the splitting criterion/decision boundary more flexible.

As they show via experiments, this leads to requiring fewer trees/leaf nodes, which could potentially lead to more interpretable models.

In addition, their technique can use SGD based techniques allowing it to be used in conjunction with other (differentiable) downstream techniques, not to mention potentially being used for larger datasets.

main_review: The paper is well written and clear. The technique presented seems to be novel, and applicable to a variety of use cases that decision trees have not been traditionally used for. And the results presented show that the technique is effective.

Overall, this seems like a solid paper. One downside though is that the need for fewer leaves is motivated by the need for interpretability. However, the experiments are primarily about accuracy (the assumption seems to be that smaller number of leaves will automatically lead to better interpretability, but that is not shown experimentally). Figure 1 seems to indicate that the VAE use case will result in splitting up the density region into interesting/interpretable regions, but it is not clear if that is borne out by the experiments.

limitations_and_societal_impact: This seems to be a useful technique both for improving accuracy (and potentially) for improving interpretability.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Authors develop a generalization of oblique trees, convex polytope trees. They are able to implement them in a differentiable, end-to-end, scalable way. In their formulation. Authors compare against competitive baselines and obtain state of the art results
main_review: I think it is a strong paper since 
a)It is well written 
b) it addresses a relevant topic: trees are important objects and there are still a growing literature in how to learn trees using more modern paradigms (e.g. differentiable programing). 
c)The methodology is original and sensible.
d)The experimental validation is quite strong; beyond standard tree formulations, authors also compare against the recent LCN [1], producing better results. Then, this paper can be understood as improving upon [1]. Although the improvement may be a bit marginal (it goes on the same direction, but extending the class of sets used at each split and introducing regularization), it is still significant and praise deserving.
e)Figure 2 is really nice and striking. I would even recommend to move it upwards so the point is made earlier in the paper.


I have some concerns, that I would like to be addressed
1)Interpretability: One of the main reasons for why trees are popular is because the original regions X>=a were easy to interpret. I am not surprised that the increased expressive power of oblique or polytope leafs would lead to improves in accuracy and shortening the depth of the tree. However, I believe this methodology has the drawback of being inherently less interpretable. For example, for a practitioner trying to use trees for a diagnosis. Having polytope regions would appear much more black-box-ish than the original trees. I am surprised tthat the authors promote the idea that their method is more interpretable than alternatives. While some of the aspects are more interpretable, I think having a polytope in the split hurts interpretability and this is not being commented. Authors should comment more about interpretability and the possible tradeoff/relation between complexity of each split, depth of the resulting tree, and capabilities to interpret. Perhaps trying to incorporate elements from [2] into the discussion would help


2)Is the method for learning split parameters new? how does it compare to [1] (and all previous work)? If  it is new, authors should highlight this novelty. If not, authors should cite the original reference.
3)Authors talk about "Robustness" in predictions. But I don't see any formal treatment of robustness in the paper. Therefore, the claim appears unsubstantiated. I would appreciate that the authors make more explicit what they mean by robustness here or otherwise change the word.


[1]https://arxiv.org/abs/1909.13488
[2]https://www.nature.com/articles/s42256-019-0048-x
limitations_and_societal_impact: Regarding societal impacts and limitations" I believe the commentary on interpretability should be improved. Currently, the loss of interpretability due to a more complex region are not being put into the interpretability discussion (which only focuses on the  regularization aspects, which are nonetheless appreciated)
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a method for learning decision trees with convex splits. It does so by replacing the common linear splits by a noisy-OR operation over a learned set of linear splits with a shrinkage prior to limit the size of this set.
It further shows how to apply the tree learning procedure to tackle three downstream tasks (classification, regression and density estimation with VAEs).
An empirically evaluation is also provided comparing the obtained method with several baselines, showing that it generally allows to obtain good (or better) performance with a smaller amount of nodes.
main_review: The proposed CPT could be viewed as learning trees with oblique splits but where some branches are pruned. Indeed, a pruned tree can be expressed in a more compact form by replacing a particular branch by a single node with a convex split defined by the hyper-planes of the nodes of that branch.
This is because in trees with oblique splits a branch can be interpreted as a sequence of AND decisions, and some of the sequences define a convex set.
The advantage of the proposed approach is in automatically choosing a single branch among the multitude of combinations of splits, which makes the tree more interpretable without having to prune and rearrange it afterwards.
**Directly learning convex splits is an interesting idea and novel in the context of decision trees**, to the best of my knowledge.

The paper is generally well written, with assumptions and method derivations generally well reported. However, **two key points need clarification**:

1. It is not clear whether while the tree is grown greedily, the parameters of all the nodes are updated jointly every time the tree is expanded. This confusion stems from an apparent contradiction between paragraph 231-234, stating that no parameter refinement is performed, and what previously stated in line 166-167, that the parameters of all nodes are learned jointly.
This is a key point to clarify, as it would be a limitation of the work. If the tree is grown greedily, it is not optimal, as opposed to other soft tree learning techniques or MIP-based methods. 

2. The specific problem for learning the set of hyper-planes at each node is not sufficiently described. I understand that the Gamma process is a common shrinkage prior in the Bayesian community, but it is new in the tree learning context. It would be valuable to report more information (even in the appendix) on the convex split optimization, such as how the prior set of hyper-planes is chosen and how the Gamma process works.
Moreover, the reasons for choosing the specific form for the expert probabilities (Equation 1) is never discussed. 

**The empirical evaluation is the weakest point** of the work. The application of the method to three different tasks (classification, regression and density estimation) is valuable, however the comparison with state-of-the-art methods should be strengthened and some important details of the setup are missing:

3. In order for the comparison to be fair the total number of parameters of the trees should be reported, and not only the number of nodes. The number of nodes is indeed a good proxy measure for the interpretability of the model, but it does not account for the total number of hyper-planes needed for good accuracy. 

4. In this sense, the considered methods should be compared in terms of accuracy (or the other prediction scores) for same (or similar) number of hyper-planes. However this does not seem the case in the current evaluation.

5. The values or ranges of the hyper-parameters of the baselines are not reported, in particular the maximal tree depth.

6. No comparison is provided with soft tree baselines, which are the methods most closely related to this work.

Finally, it is claimed that an advantage of the method w.r.t. existing techniques is in not having soft decisions, so points traverse the tree deterministically. However this is true only at test/inference time, by thresholding the splits, hence the same reasoning can be applied to other soft tree techniques.

### UPDATE
The authors addressed well my concerns. In particular, they provided tree sizes in number of hyper-planes, and even though they do not compare models' accuracy for a same tree size, I am convinced by their argument that it is valuable to compare models in terms of best achievable performance. They also clarified the several points raised in the different reviews.

Overall, I think that the contributions are new in the tree learning literature and would be interesting to this community, even though they principally leverage existing tools in Bayesian learning.
I hence increased my rating to 6, with the hope that the authors will revise the paper according to all our suggestions.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The paper proposes a  new convex polytope trees to build the family of decision trees.
main_review: The paper proposes a  new convex polytope trees to build the family of decision trees, and combine VAEs for  generative modeling issues. The idea seems fine, but there are some major concerns.
1, The paper claims that existing tree methods produce large size tree and the  computational complexity is too high. But what is the resulting tree size and time cost of the proposed tree method? what is the comparisons with existing tree methods in terms of tree size and  training and testing time cost? There are no theory analysis and no experiment report.
2, what is vote_i?  why the probability of a linear classifier who votes "YES" can be shown as in Eq.(1)? I do not see any reasons.
how do define expert i? what is q_thr?
3, Theorem 1 shows that A_left is a convex set, confined by a convex polytope. what is the role of Theorem 1? why convex set is good? I do not see any benefit. Why use gamma process  prior? 
4, In MNIST data set, in table 1, the proposed method achieves 97.01, the performance is significantly below SODA method.
limitations_and_societal_impact: 1, The paper claims that existing tree methods produce large size tree and the  computational complexity is too high. But what is the resulting tree size and time cost of the proposed tree method? what is the comparisons with existing tree methods in terms of tree size and  training and testing time cost? There are no theory analysis and no experiment report.
2, what is vote_i?  why the probability of a linear classifier who votes "YES" can be shown as in Eq.(1)? I do not see any reasons.
how do define expert i? what is q_thr?
3, Theorem 1 shows that A_left is a convex set, confined by a convex polytope. what is the role of Theorem 1? why convex set is good? I do not see any benefit. Why use gamma process  prior? 
4, In MNIST data set, in table 1, the proposed method achieves 97.01, the performance is significantly below SODA method.
review_title: null

Meta-review: Reviewers were very split about this paper, so much so that they did not come to a consensus. After looking through the paper and discussion I have decided to vote to accept for the following reasons: (i) usefulness: trees are an important class of ML models due to their speed, interpretability, accuracy, and ability to handle data with different scales. This work is able to maintain these properties while improving accuracy over recent work; (ii) novelty: while convex polytopes have been used as decision boundaries before it is non-trivial to integrate them into a learning procedure for trees: the proposed approach frames it in a principled way as a maximization of mutual information; (iii) clarity: the paper clearly presents the ideas it introduces.
Alongside the recommendations made by reviewers (which the authors should carefully take into account when preparing the camera-ready version) I would urge the authors to consider the following things: (a) remove generative modeling: I don't think the generative modelling part of the paper adds much to the paper and I would consider removing this part and retitling the paper "Convex Polytope Trees". I think most readers interested in decision trees will not be interested in this aspect, and it detracts from the most important contributions (the new splitting function, the fully differentiable training). Instead I would emphasize (possibly with an instructive diagram) that your approach can be used as a drop-in NN layer (because it is fully differentiable). This will get the point across without distracting reviewers with additional experiments; (b) details on the gamma process prior: it would be nice to see an experiment of the effect of the gamma process prior. At the moment this is mentioned very briefly in the paper, but it would be very instructive to see the role it plays in the trees that are built (e.g., how do the trees change without this prior?); (c) algorithm: include a more succinct version of algorithm 1 in the main body of the paper, this will make the training of the method much clearer to the reader; (d) instructive figures: it would be nice to have another instructive figure explaining how the splits in this work differ from classical and modern tree methods; (e) additional baseline: it would be great for the authors to compare against Tanno, R., Arulkumaran, K., Alexander, D., Criminisi, A., and Nori, A. Adaptive neural trees. In Proc. of ICML, 2019 as it performs very competitively in prior work (I am not an author of this work). If the authors are able to make these changes and the ones mentioned by the reviewers it will make a good paper even better, and a nice contribution to the conference.
Decision: Accept (Poster)