Convex Polytope Trees
Authors: Mohammadreza Armandpour
Ali Sadeghian
Mingyuan Zhou
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian Methods
Logical Disjunction
Probabilistic Models
Decision Tree
Oblique tree

Abstract: A decision tree is commonly restricted to use a single hyperplane to split the covariate space at each of its internal nodes. It often requires a large number of nodes to achieve high accuracy. In this paper, we propose convex polytope trees (CPT) to expand the family of decision trees by an interpretable generalization of their decision boundary. The splitting function at each node of CPT is based on the logical disjunction of a community of differently weighted probabilistic linear decision-makers, which also geometrically corresponds to a convex polytope in the covariate space. We use a nonparametric Bayesian prior at each node to infer the community's size, encouraging simpler decision boundaries by shrinking the number of polytope facets. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given. We empirically demonstrate the efficiency of CPT over existing state-of-the-art decision trees in several real-world classification and regression tasks from diverse domains.

Convex Polytope Trees
Mohammadreza Armandpour
Ali Sadeghian
Department of Statistics Texas A&M University armand@stat. tam
Department of Computer Science
University of Florida
asadeghian@ufl. edu
Mingyuan Zhou
McCombs School of Business
The University of Texas at Austin mingyuan www.wzcccobsb...o.oooooo www.utteeecccoo..o edu
Abstract
A decision tree is commonly restricted to single hyperplane split the covariate space at each its internal nodes. often requires a large number nodes to achieve high accuracy. In this paper, propose convex polytope trees (CPT) to expand the family of decision trees by an interpretable generalization of their decision boundary. The splitting function each node of CPT is based on the logical disjunction of community of differently weighted probabilistic linear decision-make makers, which also geometrically corresponds convex polytope in the covariate space. We use nonparametric Bayesian prior at each node to infer the community's ' size, encouraging simpler decision boundaries by shrinking the number of polytope facets. We develop greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given. We empirically demonstrate the efficiency of CPT over existing state-of-the-ar decision trees in several real-world classification and regression tasks from diverse domains.
Introduction
Decision trees are highly interpretable models, which make them favorable in high-stakes domains and criminal justice [6. They are also resistant, if not completely immune, the inclusion many irrelevant predictor variables. However, trees usually do not have high accuracy, which somewhat limits their use in practice. Current main approaches to improve the performance decision trees are making large trees or using ensemble methods [2 [8 53), such as bagging [ and boosting [K 16 which come with the price of harming model interpretability. There is trade-off challenge between the accuracy and interpretability of a decision tree.
such as medicine 32 4
Prior work has attempted to address the aforementioned challenge and improve the performance of trees by introducing oblique tree models 119 34 These families of models are generalizations of classical trees, where the decision boundaries are hyperplanes that are not constrained to be axis- parrallllll and can have an arbitrary orientation. This change in the decision boundaries has been shown to reduce the size of trees. However, the tree size often remains too large in real datasets to make it amenable to interpretation. There has been an extensive body of research to improve the training of the oblique trees and enhance their performance 5 remains a challenge.
46), yet their large size
In this paper, we propose convex polytope decision trees (CPT) to expand the class of oblique trees by extending hyperplane cuts to more flexible geometric shapes. To be more specific, the decision
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

tht-hh-rt art methods with higher (a) CART: depth 10 tree
(b) LCN: depth 10
(c) CPT. depth tree
Figure I: A visual comparison of the decision boundaries of CART, LCN and CPT on the synthetic 2D dataset. As demonstrated by plots @ and b CART and LCN need to partition the space into many subspaces to achieve reasonable performance. This results in a multitude of smaller partitions which render the model harder to interpret. By contrast, as shown in plot ( CPT successfully partitions the data with much simpler scheme (depth 2).
boundaries induced by each internal node of CPT are based on noisy-OR [36 of multiple linear classifiers. And since noisy-OR has been widely accepted as an interpretable Bayesian model (77) generalization keeps the interpretability of oblique trees intact. Furthermore, CPT's decision boundaries geometrically resemble a convex polytope (i.e., high dimensional convex polygon). Therefore, the decisions at each node have both logical and geometrical interpretation. We use the gamma process [14. 25 52 51] nonparametric Bayesian prior, to infer the number of polytope facets adaptively at each internal tree node and regularize the capacity of the proposed CPT. A realization of the gamma process consists of countably infinite atoms, each of which used to represent weighted hyperplane of convex polytope. The shrinkage property of the gamma process helps us to encourage having simpler decision boundaries, therefore help resist overfitting and improve interpretability. Figure provides illustrative example of our model for toy data.
Note, our main goal for proposing CPT is not to improve interpretability by having a smaller number of leaves rather it is pushing accuracy limits of decsion trees methods while staying in the class of interpretable models. Neural networks, with more than two layers, are often considered black-box models (not in the class of interpretable models). However, or complex (but interpretable) decision boundaries, decision trees would still remain in the class of interpretable models. Our proposed CPT offers higher accuracy than previously studied tree models and remains interpretable (noisy-OR decision boundaries are widely considered interpretable). While it is hard to objectively compare the interpretability ("Interpretability is domain-specifie notion so there cannot be an all-purpose definition"
with larger depth, lots of leaves,
(38) of convex polytope trees vs. oblique trees, they offer an alternative where the ease of interpretability of the decision boundaries at each node be traded for shallower trees with sigmificantly fewer leaves. Choosing one over the other is often application dependent, with the added advantage that convex polytope trees often offer higher accuracy.
The training of CPT, like that of oblique trees, challenging task because it requires learning both the structure (i.e., the topology of the tree and the cut-off off for the decision boundaries) and the parameters (i.c., parameters of noisy-OR). The structure is a discrete optimization problem, involving potentially large problem space. In this work, present two fully differenniable approaches for learning CPT models, one based on mutual information maximization, applicable for both binary and multi-class classification, and the other based variance minimization, applicable for regression. The differentiable training allows one to use modern stochastic gradient descent (SGD) based programming frameworks and optimization methods for learning the proposed decision trees for both classification and regression.
the search
Experimentally, we compare the performance of CPT to state-of-the-art decision tree algorithms 9 27 on a variety of representative tasks in both regression and classification. We experiment with several real-world datasets from diverse domains, such computer vision, tabular data, and chemical property data. Experiments demonstrate that CPT outperforms state-of- wate-of-the--ad accuracy and smaller size.
Our main contributions include: 1) We propose an interpretable generalization to the family of oblique decision trees models; 2) We regularize the expressive power of CPT, using nonparametric Bayesian

---

shrinkage prior for each node split function: 3) We provide two scalable and differentiable ways of learning CPT models, one for classification and the other for regression, which efficiently search for the optimal tree; 4) We experimentally evaluate CPT on several different types of predictive tasks, illustrating that this new approach outperforms the prior work in having higher accuracy achieved with smaller size.
2 Related work
Most decision tree literature focuses training single or an ensemble of trees making decision boundaries more flexible. One reason for this lack of research is the increase in the problem's computational complexity, even for simple generalizations of the decision boundary. For example, with as the number of data points and as the dimension of the input space, generalizing the coordinate-wise an oblique hyperplane cut, increases the number of possible splits of data points from Nd to Σi=o (?) just for a single node
[S instead of
To have more flexible decision boundaries, some methods perform hyperplane cuts in an extended feature space, created by concatenating the original and newly generated features M. These new features are engineered or kernel-based and not designed for interpretability. Therefore unlike CPT, they are not an interpretable extension of the decision tree. We follow this section with a literature review of the recent training algorithms for axis- axis-aligned and oblique trees.
Conventional methods for decision tree induction greedy, where they grow the tree nodes one at time. The greedy construction of oblique trees can be done by using coordinate descent to learn the parameters of each split (34) or by projection of the feature space to lower dimension then using coordinate-cut
3 However, the greedy procedure often leads to sub-optimal trees.
There have been several attempts non- non-greedy optimization, which rely on either fuzzy prob- abilistic split functions 22 decision trees 17
26 4I] The probabilistic trees are sometimes referred to as soft In these methods, the assignment of single sample to the leaf is fuzzy or probabilistic. and gradient descent used to optimize the tree. Most of these algorithms remain probabilistic test time, leading uninterpretable models as the prediction for each sample will be based on multiple leaves of the tree instead of just one.
20
26
Other advances towards the training of an oblique tree are based on constructing neural networks that reproduce decision trees 28 Yang al. [48] use neural network with argmax activations for the representation of classic decision tree with coordinate cuts, but they are not scalable to high- dimensional data. Lee and Jaakkola [X]] use the gradient of a ReLU network with single hidden unit each layer and skip-connections to construct an oblique decision tree. They achieve state-of-the-art results on some datasets but have to make complete trees with a high depth, consequently having a large number of leaves.
In contrast our method, there are other training algorithms that require the tree's structure the beginning. Some of the works in this direction like Bennett 4 and Bertsimas and Dunn [ use linear programming, or mixed-integer linear programming, to find an optimum global tree. Therefore, these methods are computationally expensive and not scalable. Norouzi et al. 355 derive a convex-concave upper bound on the tree's empirical loss and optimize that loss using SGD. A recent work proposes tree alternating optimization, where one directly optimizes the misclassification error over separable subsets of nodes, achieving the state-of-the-an empirical performance on several datasets in comprehensive comparison
40
We conclude this section by connecting our splitting rule at each internal node relevant classification 30,
51]. The two most related works are convex polytope machine (CPM) 2 and infinite support hyperplane machine (iSHM) [5]]. which both exploit the idea of learning convex polytope associated decision boundary. iSHM is like a single hidden layer NN and restricted the binary classification task.
algorithms 2
23
31
45
3 Convex Polytope Tree and Its Inference Algorithms
Suppose we are given the training data (X, Y) = ((z,, yn) W where pairs of (æ,, vn) are drawn independently from an identical and unknown distribution D. Each D, E Rdd is ddddimensional data with corresponding label yn E y. In the classification setting, y {1.-... ...,K .K} and in regression
3

---

scenario y' = R. The aim is to learn function F : R y that will perform well in predicting the label on samples from D. Decision tree methods construct the function F by recursively partitioning the feature space to yield number of hierarchical, disjoint regions and assign single label (value) to each region. In what follows, we will explain how we move beyond the oblique decision trees.
3.1 Convex Polytope Constrained Decision Boundary
By extending the idea of disjunctive interaction (noisy-OR, probabilistic-OR) 39 21 50 51 from probabilistic reasoning to the decision tree problem, we make the decision boundaries more flexible while preserving interpretability. To that end, we transform the problem of splitting at each node (right or left) to a committee experts that make individual binary decisions ("Yes" or "No"). The committee votes "Yes" if and only if at least one expert votes "Yes," otherwise it votes "No." Thus, the final vote at each node is
k
vote
vote;,
where V denotes the logical OR operator. We model each expert as linear classifier who votes "Yes" with probability
P(eote; = "Yes" (r., = -1)
(1)
where ri 2 and B, E Rd are parameters of expert i. Now assuming that each expert votes independently, we can express the probability the committee voting "Yes" as
P (ri, B,),, x) = 1 p4) =
where p: is the probability of expert i voting "Yes" and K the total number of experts. We can now define the split function at each node by thresholding the committee voting probability:
Aug == {xr x E IRd, P(vole = "Yes" (rk,))),,)) S gor)
where Aug and Anight = Rdd Augh are the related splits of the space.
To elaborate the geometric shape and interpretability of the decision boundaries, consider K 1 (i.e., single expert). In this scenario, the decision boundary becomes hyperplane, which is perpendicular to G.. In fact, the probability function for each expert is based on the signed distance of x to the hyperplane perpendicular to B. Moreover, the parameter r controls how smoothly the probability transitions from 0 to 1, where larger leads to sharper changes. This class of models with
and = 1 are identical to oblique trees, which are interpretable. Furthermore, when K 1, the interpretability is provided by the fact that linear classifiers and probabilistic operation are both interpretable [37].
To geometrically analyze the implied decision regions, we provide the following theorem. Theorem 1. For any {ri, (,),, such that R4 and Bi Rdd let:
Aug tx x F Rd, f(x) S qar), where:f(x) =1 e- Σ* re (1+6(())
(4)
then Asg is a convex set, confined by convex polytope.
The proof is provided in the Appendix.
The above theorem shows that for K > 1, the decision region (Ateft) is a convex set confined by convex K-sided polytope. More precisely, each facet of the convex polytope hyperplane corresponding to an expert perpendicular to its f3. Also worth noting, an expert with larger has more effect on the decision boundary, making sharper changes the probability function. This can also be perceived as the value of their decision in the committee. Therefore, our method not only has a strong relationship with probabilistic-OR type models that provide interpretability for the model parameters [ but also has decision boundaries with interpretable geometric characteristics. We propose a class of models, Convex Polytope Trees (CPT), where each tree node follows the above splitting function.

---

3.2 Gamma Process Prior
To regularize CPT and motivate simpler decision boundaries, we use nonparamteric Bayesian shrinkage prior. Specifically, we put the gamma process prior 14 25 51 on the splitting function of each node in the tree. Each realization of the gamma process, consisting of countably infinite weighted atoms whose total weight is finite gamma random variable, can be described as
G= G=E
T:OB, such that B E RR, E
(5)
where 3, represents an atom with weight rú. More details about the gamma process can be found in Kingman [2]] and Zhou and Carin [22] We put the prior the CPT by considering (3 and r; the parameters of the splitting function related to Equation 2 Due to the gamma process's ' inherent shrinkage property, just small finite number of experts will have non-negligible weights ry each node. This behavior encourages the model to have simpler decision boundaries (i.e., smaller number of experts or equivalently fewer polytope facets) at each node. This improves the interpretability and regularization of the model. The gamma process allows a potentially infinite number of experts at each node. For the convenience implementation, truncate the gamma process a large finite number of atoms.
To further encourage simpler models at each node of the tree, also put shrinkage prior B3 of each expert. In particular, we consider the prior:
B, II - [N 0, of.) InnGamma(off ag, 1 1/bbs) )do3,
and b3: ~ Gamma(eo. 1/f which motivates sparsity due to the InyGamma distribution on the variance parameter 42 51
3.3 Training Algorithm
Finding an optimal CPT requires solving a combinatorial, non-differentiable optimization problem. This due to the large number of possibilities that any single node can separate the data. We propose continuous relaxation of the splitting rule at each node to alleviate this computationally challenging task. Each internal node makes probabilistic rather than deterministic decisions send samples to its right or left branch. We set the probability of going right equal to Equation @ or any monotonic function it. We use this probabilistic version to train the tree in differentiable manner. Furthermore, at the test time, we threshold the splitting functions to provide deterministic tree. In the following subsections, we explain in detail the proposed training algorithm for the splitting parameters (Section 3.3.I and structure of the tree (Section 3.3.2
3.3.1 Learning Split Parameters
Assuming the tree structure is given, we explain how to infer the tree parameters for each task.
optimization problem by considering the mutual information between the two random variables (category label) and L (leaf id) as objective function. This differs from the previous work on learning a classical decision tree in two main ways: 1) we develop and optimize the mutual information for probabilistic rather than deterministic tree, and in a greedy fashion. In terms of learning split parameters, the closest paper is Hehn et al. (00;: however, it uses an EM algorithm learn the parameters opposed to novel method, where optimize a probabilistic version of mutual information for classification. Additionally, the method in 2 is only applicable classification tasks.
Classification. For this task, formulate the training
leam the parameters of all nodes jointly rather than learning them
Hehn al.
We model our probabilistic tree by letting
(o x.)
such that E Steef
where Stoof is the set of leaf nodes and Po xn) the probability of arriving at leaf given the sample feature æn. We assume each internal node makes decisions independent of the others and use the probabilities in Equation g when sending a data sample to the left or right branch. This assumption lets derive formula for Pe as
5

---

Po(e Po(e|2n) 2a)
(v,du) Eur 90. qo.(d, xn);
(8)
where
(d, 11)xn) - 90, (d. = =01 xm
=1 ER ( (1+e
and Ve is a path from the root to leaf and de E {0. encodes the right or left (0 or 1) direction taken at node v. The mutual information between and can be expressed as
I(Y. L) = H(Y) - H(Y L) H(Y) EiEs p(L E E),
(10)
where V((-) indicates the entropy of a random variable, and Y L follows a categorical distribution. Notice that, since H(Y) does not depend on the tree parameters, to optimize mutual information, we only need to minimize H(Y L). However, the evaluation of the conditional entropy term requires
knowledge of the entire data distribution, thus we can not directly optimize Equation TT
To make the training possible, we approximate the true data distribution with the empirical one to get
pL = =
(11)
Denote 11j] as an indicator function. By using Bayes' rule, we derive * (#f. .., #t),, the estimated probability vector of the categorical distribution for Y === l, as
j 1...., C Σn 1 1pm= Po [n..
(12)
Σn Po(e xn))
Now by using Equation 12
approximate the entropy term H(Y L E)
A == =) # lfg(#t))
(13)
Therefore, we can provide an estimator for the H(Y [L) as
H E
P(L () L
(14)
By minimizing H( [L) with respect to 0, we are in fact maximize the mutual information Z L).
As discussed in Section 3.2 we also regularize CPT by adding penalty term Equation T4. We consider the negative log probability of the gamma process prior truncated with K atoms by letting
Ti...., TK itd
Gamma (oaimaaao/K,LLLL 1/co)
where P1,-.., F' the parameters of internal nodes splitting function. The penalty term for each internal node can be mathematically formulated as
1) + toorle)) + (as + 1/2) E/2) I Ek + / (2bb, (15)
C
K
Am
The above procedure provides a differentiable way of learning branch node parameters. At the end of the training algorithm, we also need to assign the leaf node parameters (that determine the tree's predictions at each leaf). We pass the whole training set through the tree and assign the empirical distribution of all categories each leaf as its parameters. This way of determining the leaf Algorithm
parameters has been shown to achieve the highest AUC binary-clasiifeation summarizes the training method.
15]
Regression. For this task, we replace the mutual information optimization by a variance reduction criterion. To be more specific, we learn the tree parameters with
argmin E, n (o xn Zn p. (25
(16)
such that

---

Algorithm Stochastic gradient descent training of the tree splitting parameters for classification task.
Input: Data {(x("),
I initial tree T()) from Topology-Leane algorithm, maximum number polytope sides K, haper-parameters of the gamma process prior ag. bo, co. 70
for number of training iterations do
Sample batch of m data samples {( vi),..., ................................ (Im Bm)}
Send the data samples to the current probabilistic tree to get probability of each samples being
in any leaf Paco = e xn) for all n. E [1 m), f E Steuf using eq. 3
For each leaf, calculate the vector # [#1 [=f:-... # which represent for the current batch
what is the proportion of each data label the leaf é using eq. 12
Estimate the entropy of the data labels Y, conditioned on the leaf id L as H(Y [L) by using
eq. 14
Calculate the regularization term related to the gamma process prior by using eq. 15 as
reg EveSmmnn 2%
Update the tree parameters by descending their stochastic gradient:
Vei (RI(Y I))
+ Crg))
end for
Send all the data samples the to the tree, and for each leaf set its parameter A².
Use the threshold of 0.5 for the probabilistic decision function at each branch node to achieve deterministic tree.
A En Pe ( Zn)yn
(17)
Σn Pe (..)
and the calculation of Pe is exactly the same as in the classification case. The leaf parameters are set the mean response of the points arriving that leaf.
Note for both scenarios, we use the threshold of 0.5 to do deterministic splits at the test time. Now that we know how to train tree given its structure and how use it at the test time, the next section will describe how to find an optimal topology and initial parameters.
3.3.2 Topology Learning
We start by assuming the tree structure to be just a root node and its two child leaf nodes. We train this tree using the algorithm explained in Section 3.3.T After training, we split the training set to two subsets (right and left), by thresholding the assigned probability. We calculate this threshold in the classification (regression) task, which achieves maximum mutual information (variance reduction) in the deterministic tree. To be more specific, for the classification task, we set the threshold gitr, such that it minimizes
no
N H(( 12
N nop
N
where
P(no)
S 9oto S P(n
The P(s) is the i'th smallest probability assigned by the root node to the data samples. We further split each child node by considering it as root and applying the above algorithm using its data samples. We stop splitting a node with very few data samples and stop growing the tree when we reach a certain predefined maximum depth.
Note, Section I. titled as "Learning Split Parameters" " (LSP) presents our algorithm for learning parameters when the structure given. During both final refining and greedy training, LSP used but on different structures. More specifically, at each step of greedy training, each leaf is turned into a stump (a tree with one root and two child nodes), and LSP is applied to learn only the parameters of the root node of the newly added stump, using only data points that had reached the stump's 's root. Then, after the greedy training, LSP is applied to the entire tree to jointly learn all the parameters, which is essentially full tree parameter refining. We do not apply LSP to all the parameters of the tree when growing the tree during greedy training. Emphasizing that we only use L.SP train the parameter of the newly added stump, freezing the rest of the tree in deterministic mode.
7

---

Experiments
In this section, we empirically assess the qualitative and quantitative performances of CPT on datasets from various domains. We show that CPT learns significantly smaller trees than its counterparts and makes more accurate predictions. That partly due to the high variance of the leaf node's 's prediction in classical (oblique) trees, resulting from fewer data samples in each partition. However, since CPT usually has fewer leaf nodes, each partition has a significant proportion of the dataset.
Table I: Dataset statistics
Dataset
MNIST SensIT
Connect4
Letter
PDBbind
Bace
HIV
Task Number of classes
Multi-class classification
Regression
Binary classification
10
3
3
26
2
Number of data
70,000
98.528
67.557
20,000
11,908
1,513
41.127
Feature dimension
784
100
126
16
2,052
2,048
2,048
4.1 Synthetic Dataset
In this section compare CPT and other tree based approaches toy examples to better demonstrate why CPT achieves better performance. We consider a dataset of 2,000 points, as shown in Figure [ The data samples independent draws of the uniform distribution on two-dimensional space
1] [-1,
x [], with the data points labeled as red they lay between two concentric circles, and blue otherwise.
We compare CPT with LCN 28 which is a state-of-the-art oblique tree method, and CART []] which is canonical axis-aligned tree algorithm. Figure T shows the decision boundaries of all three methods. CART and LCN are trained with a maximum depth of 10, and CPT is trained with maximum depth of 2. It is worth noting that both LCN and CART are restricted to partition the feature space into disjoint convex polytopes and assign each region to leaf node. However, CPT does not have such limitation, and each region be the result of applying any set of logical operations on a set of convex polytopes. Figure clearly shows that both LCN and CART need a large depth to successfully classify the data, while CPT only needs two splits. To be more specific, the AUC results for CART is 0.901 with 9 leaves, and 0.959 for LCN with 479 leaves.
By contrast, CPT achieves the AUC of 0.962 (the highest score) with just 3 leaf nodes a maximum depth of 2. However, one limitation of our method is that can not yet achieve competitive AUC to multi-layer neural network.
Figure Ic shows that CPT uses a 8-sided 2D convex polytope for the first split and 5-sided one for the second split to partition the space. This number was not fixed at training time, we only limit the maximum number of polytope sides to K 50. The model owes this adaptive shrinkage to the gamma process prior, which improves the simplicity and interpretability of the model.
4.2 Classification and Regression
We evaluate the performance CPT for regression, binary classification, and multi-class classi- fication tasks. For regression and binary classification, we conduct experiments on datasets from MoleculeNet [77]. We follow the literature construct the features 47 27 and use the same training, validation, and testing split as Lee and Jaakkola [27]. For multi-class classification, we perform experiments on four benchmark datasets from LibSVM [+], including MNIST, Connect4, SensIT, and Letter. We employ the provided training, validation, and testing sets when available; otherwise, we create them under the criterion specified in previous works
20 The datasets statistics are
summarized in Table II
4.2.1 Compared Baselines
We evaluate the performance CPT against several state-of-the-ard decision tree methods, including FTEM (Hehn et al. 20 "End-to-end learning of decision trees and forests"), Tao (Carreira-Perpine
"Oblique decision trees trained via alternating optimization"). and L.CN (Lee and Jaakkola ? "Oblique decision trees from derivatives of ReLU networks"). We also consider several
and Tavallali 9

---

Table 2: The performance of decision tree algorithms on regression (RMSE, lower is better) and classification (ACC or AUC, higher is better). The superscripts and iis used to to show the source of the quoted results as
49
127 and [20]
Dataset
CART
HECART
GUIDE
CO2
FTEM
TAO
LCN
CPT (K=1)
CPT
MNIS
88 054000"
90.111
78.524020'
90s."
96. 16.124
94,74gm11
9381
95.74g
97.01=m31
SeadT (ACC)
81.71000""
79.25
82+.'
81611
85.12=n20"
84.06=0.22
84,87=n27
85.77=0.55
Connect4 (ADC)
78.291001"
22.01
78a-
80.51a-1
81.09
80.79an12
78.892035
81.16 8551
Letter (ACO)
86.0740044
83.1203
82.65
87s-
86.31
89.15-00"
89.64a075
84.13
90.51=881
PDBbind (RMSE)
1.5735000"
1,3000000
1.508=000"
1.453=0.006
1413:00044
Bace
65.2u24
14.5
81.03
734400
83.9
82.06.344
84.7:114
HIV (ADO)
54,4009'
63.62un
71 71.09=10
62.7400
72.8=13'
71.12
73.1+14
Table 3: Number of leaves and (the depth of trees)
Dataset
CART
HHCART
GUIDE
C02
FTEM
TAO
LCN
CPTıK=1)
CPT
MNIST
(D19))
39 (D15)'
(D14y'
357 (D12)
178 (D8)
65536 (D16)
501 (DII)
98 (DS)
SensIT
152 (D12)'
(D11)
(D6)"
(D7))
69 (D7)
256 (D8)
81 (DS)
36 (D6)
Connect4
5744 (D33)'
27 (D18)
(D16)'
257 (D10)
210 (DB)"
65536 (D16)
342 (D10)
4 (D2)
Letter
1580 (D27)"
673 (D28)"
-D12))
543 (D16)
1078 (DI1)*
65536 (D16)
705 (D17)
463 (D11)
PDBhind
Appiicable
2048 (D11)'
16 (D4)
15 (D4)
Bace
23 (D8)
4096 (D12)'
19 (D9)
21 (D7)
HIV
21 (D7)
128 (D7)
25 (D7)
24 (D5)
additional baselines, including CART [.) HHCART Ab. GUIDE 29 and CO2 35 Another related probabilistic tree work on decision trees is ANT (Tanno et al. where they apply transformation at each decision tree layer to the input data, therefore they are not as interpretable as other methods. However, they achieve more than 99 percent accuracy on datasets like MNIST. We did not iclude them in the comparison table because of their non-intreprable decsion boundries. Moreover, to empirically show the importance of flexible boundaries, we also added a baseline CPT, where K = 1, with hyperplane cuts.
"Adaptive neural tree"),
Our algorithm is implemented in PyTorch and can be trained by gradient- based methods. We use Adam 244] optimization for inferring the tree split parameters. A 10-fold cross-validation on the combined train and validation set is used to learn the hyperparameters, namely the maximum number of polytope sides, number of training epochs, learning rate, and batch-size. However, we decide the depth of the tree based on the performance of CPT on the validation set during training, which can be perceived as early stopping for trees. Following the literature, we use the Area Under the receiver operating characteristic Curve (AUC) on the test set as the evaluation metric for binary classification, accuracy (ACC) for multi-class classification, and root-mean- -quared error (RMSE) for regression.
Finally, we report the average and standard error of each method's performance by repeating our experiments for 10 random seed initializations. More details about our implementation and the exact values of hyperparameters for each dataset are presented in the Appendix. Our code to reproduce the results is provided at http://ggttoo.oooo//aaaaaaaaaaaa
Polytooooooooptlleeeeeeeeeeeeeee Trees
4.2.2 Experimental Results
Tables [n present the results for a variety of decision tree based algorithms. Some results
quoted from previous works 27 20 The depth and leaf numbers are averaged over 10 repetitions of training, and then rounded. For some large datasets, namely MNIST, SensIT. Connect4, and Letter, we fix the depth parameter as opposed to adaptively tuning it based on the validation set on each run. The reason for some missing values in Table 2 is some methods like TAO did not provide their code, so we could not provide their performance on the datasets that they had not experimented. Regarding the hyper-pane papee-prrretter tuning for CPT. the total number of different hyper- paramm-e tuning setups for each dataset was less than 25 (5*5) cases. For the baseline methods, we quote the best results tuned and reported by the authors (e.g., LCN, according to their paper, does at least (3* 11 1) hyperparameter tuning). Also, for TAO, we report the best results by the authors. For each dataset, the best result and those with no statistically significant difference (by using two sample (-test and p-value of 0. 0.05) are highlighted.

---

From the results, it is evident that the added flexibility in splitting rules combined with efficient training algorithm allows CPT outperform the baseline algorithms. Our method achieves the state-of-the-ar performance, while, notably, using significantly shallower trees. For instance, CPT obtains the best performance in Connect4 with only depth 2 and leaves, while other methods need depth of at least 8.
also improves the regression performance on the PDBbind dataset by large margin. Although LCN achieves competitive results in terms of accuracy on some datasets, it needs to grow the tree's size exponentially, significantly sacrificing the model interpretability. That is mainly because LCN, in contrast to our model, always learns complete tree and generally needs to have considerably large depth to achieve competitive results. For instance, consider its enormous size when trained on MNIST and Connect4 in Table g
4.3 Potential Negative Societal Impact
One often-neglected side effect of improving the interpretability a machine learning model risk of automation bias and false sense of trust in models. The ease of understanding the system increases the risk of misinterpretation, overtrust, and even incorrect use of the outputs. Our model's improvement of interpretability and accuracy of decision trees, which is usually employed in high stake domains, may further increase the chance that risk.
Conclusion
We propose convex polytope trees (CPT) as generalization to the class of oblique trees that improves their accuracy and shrinks their size, which consequently provides better predictions. CPT owes its performance two main components: flexible decision boundaries and an efficient training algorithm. The proposed training algorithm well addresses the challenge to learn not only the parameters of the tree but also its structure. Moreover, we demonstrate the efficacy and efficiency CPT on a variety of tasks and datasets. The empirical successes of CPT show promise for further research on other interpretable generalizations of decision boundaries. This can lead a significant performance gain for the family of decision tree models. Another promising direction for future work is investigating the combination CPT with various ensemble learning methods, such as boosting.
Acknowledgements
M. Zhou acknowledges the support of NSF I1S-181,,9,, the APX 2019 project sponsored by the Office of the Vice President for Research at The University of Texas at Austin, and the support of gift fund from ByteDance Inc.
References
[1] A. Ahmad. Decision tree ensembles based on kernel features. Applied intelligence, 41(3): 855-869, 2014.
[2] Aiolli and A. Sperduti. Multiclass classification with multi- puott-prot support vector machines. Journal of Machine Learning Research, 6(May):817-850, 2005.
[3] R. G. Almond, R. J. Mislevy, L. S. Steinberg, D. Yan, and D. M. Williamson. Bayesian networks in educational assessment. Springer, 2015.
[4] K. P. Bennett. Global tree optimization: A non-greedy decision tree algorithm. Computing Science and Statistics, pages 156-156, 1994.
[5] D. Bertsimas and J. Dunn. Optimal classification trees. Machine Learning, 106(7)1039--1092 2017.
[6] S. Bitzer, O. Ribaux, N. Albertini, and O. Delémont. To analyse trace or not? Evaluating the decision-making process the criminal investigation. Forensic science international, 262:1-10. 2016.
10

---

[7] L. Breiman. Random forests. Machine learning, 45(1):5-33) (-0)), 2001. 2001.
[8] L. Breiman, J. Friedman, C. Stone, and R. A. Olshen. Classification and regression trees. CRC press, 1984.
[9] M. A. Parreira-Perpinán and P. Tavallali. Alternating optimization of decision trees, with application to learning sparse oblique trees. In Advances in Neural Information Processing Systems, pages 1211-1221, 2018.
[10] C.-C. Chang and C.-J. Lin. LIBSVM: library for support vector machines," 2001. software available at http://www. csie. ntu. edu. tw/" cjlin/libsvm. 2001.
[11] G. Dietterich. Ensemble methods in machine learning. International workshop on multiple classifier systems, systems pages 1-15. Springer, 2000.
[12] T. G. Dietterich. An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization. Machine learning. 40(2):139-13 1579999----111 2000.
[13] H. Drucker and C. Cortes. Boosting decision trees. In Advances in neural information processing systems, pages 479-485, 1996.
[14] S. Ferguson. A Bayesian analysis of some nonparametric problems. The annals of statistics, pages 209-230, 1973.
[15] C. Ferri, P. Flach, and J. Hernández-Oralle Learning decision trees using the area under the ROC curve. In Icml, volume 2, pages 139-146, 2002.
[16] Y. Freund and R. E. Schapire. A decision-theoretii generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-133) 1997.
[17] N. Frosst and G. Hinton. Distilling a neural network into soft decision tree. arXiv preprint arXiv: 171.0077 2017.
[18] T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science & Business Media, 2009.
[19] D. Heath, S. Kasif, and S. Salzberg. Induction of oblique decision trees. In IJCAI, volume 1993, pages 1002-1007, 1993.
[20] M. Hehn. Kooij, and A. Hamprecht. End-to-end learning of decision trees and forests. International Journal of Computer Vision, pages 1-15, 2019.
[21] T. S. Jaakkola and M. I. Jordan. Variational probabilistic inference and the QMR-DT network. Journal of artificial intelligence research, 10:291-322, 1999.
[22] M. Jordan. statistical approach to decision tree modeling. In Machine Learning Proceedings 1994, pages 363-370. Elsevier, 1994.
[23] A. Kantchelian, M. C. Tschantz, I.. Huang, P. L.. Bartlett, A. D. Joseph, and D. Tygar. Large- margin convex polytope machine. In Advances in Neural Information Processing Systems, pages 3248-3256. 2014.
[24] D. P. Kingma and Ba. Adam: A method for stochastic optimization. arXiv preprint 14/2v: 2014.
[25] J. Kingman. Poisson Processes. Oxford Studies in Probability. Clarendon Press, 1992. ISBN 9780191591242.
[26] P. Kontschieder, M. Fiterau, A. Criminisi, and S. Rota Bulo. Deep neural decision forests, In Proceedings of the IEEE international conference on computer vision, pages 1467-1475, 2015.
[27] G.-H. Lee and T. S. Jaakkola. Locally constant networks. ICLR, 2020.
[28] G.-H. Lee and Jaakkola. Oblique decision trees from derivatives of ReLU networks. ICLR, 2020.

---

[29] W.-Y. Loh. Fifty years of classification and regression trees. International Statistical Review, ((3))329-348, 2014.
[30] N. Manwani and P. Sastry. Learning polyhedral classifiers using logistic function. In Proceedings of 2nd Asian Conference Machine Learning, pages 17-30, 2010.
[31] N. Manwani and P. Sastry. Polyceptron: A polyhedral learning algorithm. arXiv preprint arXiv: 2011.
[32] A. Martinez-Nicolas, J. A. Madrid, F. García, M. Campos, M. T. Moreno-Cashar P. F. Almaida- Pagán, A.
and M. A. Rol. Circadian monitoring as an aging predictor. Scientific
reports, 8(1):1-11, 2018.
[33] B. H. Menze, B. M. Kelm, D. N. Splitthoff, U. Koethe, and F. A. Hamprecht. On oblique random forests. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 469. Springer, 2011.
[34] S. K. Murthy, S. Kasif, and S. Salzberg. system for induction of oblique decision trees. Journal of artificial intelligence research, 2:1-32, 1994.
[35] M. Norouzi, M. Collins, M. A. Johnson, D. J. Fleet, and P. Kohli. Efficient non- non-greedy optimization of decision trees. In Advances in neural information processing systems, pages 1729-1737,2 2015.
[36] J. Pearl. Probubilistic reasoning in intelligent systems: networks of plausible inference. Elsevier, 2014.
[37] J. G. Richens, C. M. Lee, and S. Johri. Improving the accuracy of medical diagnosis with causal machine learning. Nature communications, 11(1):1-9, 2020.
[38] C. Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-21) 2019.
[39] M. A. Shwe, B. Middleton, D. E. Heckerman, M. Henrion, E, J. Horvitz, H. P. Lehmann, and G. F. Cooper. Probabilistic diagnosis using a reformulation of the intermist- 1/qmrr knowledge base. Methods of information Medicine, 30(04):241-25 1991.
[40] A. Suárez and J. F. Lutsko. Globally optimal fuzzy decision trees for classification and regression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(12):1297-133 1999.
[41] R. Tanno, K. Arulkumaran, D. Alexander, A. Criminisi, and A. Nori. Adaptive neural trees. In International Conference on Machine Learning, pages 61 66-6175. PMLR, 2019.
[42] M. E. Tipping. Sparse Bayesian learning and the relevance vector machine. Journal of machine learning research, 1(Jun):211-244 2001.
[43] G. Valdes, J. M. Luna, E. Eaton, C. B. Simone II, L. H. Ungar, and T. D. Solberg. Medi A patient stratification tool for interpretable decision making in the era of precision medicine. Scientific reports, 6:37854, 2016.
[44] V. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events their probabilities. Theory of Probability & Its Applications, 16(2):264 280, 1971.
[45] Z. Wang. N. Djuric, K. Crammer, and S. Vucetic. Trading representability for scalability: Adaptive multi-hyperplane machine for nonlinear classification. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 24-32, 2011.
[46] D. Wickramarachchi, B. Robertson, M. Reale, C. Price, and Brown. HHCART: An oblique decision tree. Computational Statistics & Data Analysis, 96:12-23, 2016.
[47] Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(): 513-530, 2018.
12

---

[48] Y. Yang, I. G. Morillo, and T. M. Hospedales. Deep neural decision trees. arXiv preprint (env::886008888 2018.
[49] A. Zharmagambetov, S. Hada, and M. A. Carreira-Perpiidán, An experimental comparison of old and new decision tree algorithms. arXiv preprint vrXiv:/911.03082 2019.
[50] M. Zhou, Infinite edge partition models for overlapping community detection and link prediction. In Artificial intelligence and statistics, pages 1135-1143. PMLR, 2015.
[51] M. Zhou. Parsimonious Bayesian deep networks. In Advances in Neural Information Processing Systems, pages 3190-3200, 2018.
[52] M. Zhou and L. Carin. Negative binomial process count and mixture modeling. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 37(2):30--320, 2013.
[53] Z.-H. Zhou. Ensemble methods: foundations and algorithms. CRC press, 2012.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the experiment section; our results, in term of accuracy, is sub-optimal to neural networks.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 4.3.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section S
(b) Did you include complete proofs of all theoretical results? [Yes] See Section and Appendix A
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] See the linked
GitHub page.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix B
(c) Did you report error bars (e-g-, with respect the random seed after running experi- ments multiple times)? [Yes] We reported the standard deviation of reported results in
Table x
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix B
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix B
(b) Did you mention the license of the assets? [Yes] We used publicly available datasets.
(c) Did you include any new assets either in the supplemental material
URL.? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "xlAE1FtDiFI", "reviewer": "Reviewer_5qk9", "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.\nIt further shows how to apply the tree learning procedure to tackle three downstream tasks (classification, regression and density estimation with VAEs).\nAn 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The 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.\nThis 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.\nThe 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.\n**Directly learning convex splits is an interesting idea and novel in the context of decision trees**, to the best of my knowledge.\n\nThe paper is generally well written, with assumptions and method derivations generally well reported. However, **two key points need clarification**:\n\n1. 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.\nThis 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. \n\n2. 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.\nMoreover, the reasons for choosing the specific form for the expert probabilities (Equation 1) is never discussed. \n\n**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:\n\n3. 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. \n\n4. 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.\n\n5. The values or ranges of the hyper-parameters of the baselines are not reported, in particular the maximal tree depth.\n\n6. No comparison is provided with soft tree baselines, which are the methods most closely related to this work.\n\nFinally, 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.\n\n### UPDATE\nThe 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.\n\nOverall, 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.\nI hence increased my rating to 6, with the hope that the authors will revise the paper according to all our suggestions.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "pSfL1ReaGrI", "reviewer": "Reviewer_pRjS", "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.\n\nOne 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.\n\nAs they show via experiments, this leads to requiring fewer trees/leaf nodes, which could potentially lead to more interpretable models.\n\nIn 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.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nOverall, 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This seems to be a useful technique both for improving accuracy (and potentially) for improving interpretability.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "YD9hG_a1UJj", "reviewer": "Reviewer_54hJ", "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", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think it is a strong paper since \na)It is well written \nb) 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). \nc)The methodology is original and sensible.\nd)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.\ne)Figure 2 is really nice and striking. I would even recommend to move it upwards so the point is made earlier in the paper.\n\n\nI have some concerns, that I would like to be addressed\n1)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\n\n\n2)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.\n3)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.\n\n\n[1]https://arxiv.org/abs/1909.13488\n[2]https://www.nature.com/articles/s42256-019-0048-x", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "PzUhy1pLiG", "reviewer": "Reviewer_HSsp", "summary": "The paper proposes a  new convex polytope trees to build the family of decision trees.", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The 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.\n1, 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.\n2, 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.\nhow do define expert i? what is q_thr?\n3, 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? \n4, In MNIST data set, in table 1, the proposed method achieves 97.01, the performance is significantly below SODA method.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n2, 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.\nhow do define expert i? what is q_thr?\n3, 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? \n4, In MNIST data set, in table 1, the proposed method achieves 97.01, the performance is significantly below SODA method.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "0.5"}, "extra_text": {}}]

Author rebuttal:

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)