Convex Polytope Trees
Year: 2021

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.

heading: 1 Introduction
text: Decision trees [8] are highly interpretable models, which make them favorable in high-stakes domains such as medicine [32, 43] and criminal justice [6]. They are also resistant, if not completely immune, to the inclusion of 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 of decision trees are making large trees or using ensemble methods [11, 12, 18, 53], such as bagging [7] and boosting [13, 16], which come with the price of harming model interpretability. There is a trade-off challenge between the accuracy and interpretability of a decision tree.
Prior work has attempted to address the aforementioned challenge and improve the performance of trees by introducing oblique tree models [19, 34]. These families of models are generalizations of classical trees, where the decision boundaries are hyperplanes that are not constrained to be axis-parallel 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, 9, 28, 46], yet their large size remains a challenge.
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 (NeurIPS 2021).
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 [37], our 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], a 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 is used to represent a weighted hyperplane of a 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 1 provides an illustrative example of our model for a 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, even with larger depth, lots of leaves, 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 a domain-specific notion so there cannot be an all-purpose definition” [38]) of convex polytope trees vs. oblique trees, they offer an alternative where the ease of interpretability of the decision boundaries at each node can be traded for shallower trees with significantly 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, is a challenging task because it requires learning both the structure (i.e., the topology of the tree and the cut-off for the decision boundaries) and the parameters (i.e., parameters of noisy-OR). The structure is a discrete optimization problem, involving the search over a potentially large problem space. In this work, we present two fully differentiable approaches for learning CPT models, one based on mutual information maximization, applicable for both binary and multi-class classification, and the other based on 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.
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 as computer vision, tabular data, and chemical property data. Experiments demonstrate that CPT outperforms state-of-the-art methods with higher 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 a 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 a smaller size.

heading: 2 Related work
text: Most decision tree literature focuses on training a single or an ensemble of trees [18] instead of 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 N as the number of data points and d as the dimension of the input space, generalizing the coordinate-wise to an oblique hyperplane cut, increases the number of possible splits of data points from Nd to Pd i=0 N i just for a single node [44].
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 [1]. 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-aligned and oblique trees.
Conventional methods for decision tree induction are greedy, where they grow the tree nodes one at a time. The greedy construction of oblique trees can be done by using coordinate descent to learn the parameters of each split [34], or by a projection of the feature space to a lower dimension then using coordinate-cut [33, 46]. However, the greedy procedure often leads to sub-optimal trees.
There have been several attempts to non-greedy optimization, which rely on either fuzzy or probabilistic split functions [22, 26, 40, 41]. The probabilistic trees are sometimes referred to as soft decision trees [17, 20, 26]. In these methods, the assignment of a single sample to the leaf is fuzzy or probabilistic, and gradient descent is used to optimize the tree. Most of these algorithms remain probabilistic at test time, leading to uninterpretable models as the prediction for each sample will be based on multiple leaves of the tree instead of just one.
Other advances towards the training of an oblique tree are based on constructing neural networks that reproduce decision trees [28, 48]. Yang et al. [48] use a neural network with argmax activations for the representation of classic decision tree with coordinate cuts, but they are not scalable to highdimensional data. Lee and Jaakkola [28] use the gradient of a ReLU network with a single hidden unit at 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 to our method, there are other training algorithms that require the tree’s structure at the beginning. Some of the works in this direction like Bennett [4] and Bertsimas and Dunn [5] 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. [35] derive a convex-concave upper bound on the tree’s empirical loss and optimize that loss using SGD. A recent work [9] proposes tree alternating optimization, where one directly optimizes the misclassification error over separable subsets of nodes, achieving the state-of-the-art empirical performance on several datasets in a comprehensive comparison [49].
We conclude this section by connecting our splitting rule at each internal node to relevant classification algorithms [2, 23, 30, 31, 45, 51]. The two most related works are convex polytope machine (CPM) [23] and infinite support hyperplane machine (iSHM) [51], which both exploit the idea of learning a convex polytope associated decision boundary. iSHM is like a single hidden layer NN and is restricted to the binary classification task.

heading: 3 Convex Polytope Tree and Its Inference Algorithms
text: Suppose we are given the training data (X,Y) = {(xn, yn)}Nn=1, where pairs of (xn, yn) are drawn independently from an identical and unknown distribution D. Each xn 2 Rd is a d-dimensional data with a corresponding label yn 2 Y . In the classification setting, Y = {1, · · · ,K} and in regression
scenario Y = R. The aim is to learn a function F : Rd ! 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 a number of hierarchical, disjoint regions and assign a single label (value) to each region. In what follows, we will explain how we move beyond the oblique decision trees.

heading: 3.1 Convex Polytope Constrained Decision Boundary
text: 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 of 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
vote = _K
i=1 votei,
where W
denotes the logical OR operator. We model each expert as a linear classifier who votes “Yes” with probability
P (votei = “Yes” | {ri, i},x) = 1 (1 + e 0 ix) ri , (1)
where ri 0 and i 2 Rd are parameters of expert i. Now assuming that each expert votes independently, we can express the probability of the committee voting “Yes” as
P (vote = “Yes” | {ri, i}i,x) = 1 QK i=1(1 pi) = 1 e PK i=1 ri ln (1+e 0ix), (2)
where pi is the probability of expert i voting “Yes” and K is the total number of experts. We can now define the split function at each node by thresholding the committee voting probability:
Aleft := {x |x 2 Rd, P (vote = “Yes” | {ri, i}i,x)  qthr} (3)
where Aleft and Aright := Rd \Aleft are the related splits of the space. To elaborate on the geometric shape and interpretability of the decision boundaries, consider K = 1 (i.e., a single expert). In this scenario, the decision boundary becomes a hyperplane, which is perpendicular to . In fact, the probability function for each expert is based on the signed distance of x to the hyperplane perpendicular to . Moreover, the parameter r controls how smoothly the probability transitions from 0 to 1, where a larger r leads to sharper changes. This class of models with K = 1 and r = 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-OR operation are both interpretable [37].
To geometrically analyze the implied decision regions, we provide the following theorem.
Theorem 1. For any {ri, i}Ki=1, such that ri 2 R+ and i 2 Rd, let:
Aleft = {x |x 2 Rd, f(x)  qthr}, where:f(x) = 1 e PK i=1 ri ln (1+e 0ix) (4)
then Aleft is a convex set, confined by a convex polytope.
The proof is provided in the Appendix.
The above theorem shows that for K 1, the decision region (Aleft) is a convex set confined by a convex K-sided polytope. More precisely, each facet of the convex polytope is a hyperplane corresponding to an expert perpendicular to its . Also worth noting, an expert with a larger r has more effect on the decision boundary, making sharper changes to 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 [3] 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.

heading: 3.2 Gamma Process Prior
text: To regularize CPT and motivate simpler decision boundaries, we use a 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 a finite gamma random variable, can be described as
G = X1
i=1 ri i , such that i 2 R d, ri 2 R+ (5)
where i represents an atom with weight ri. More details about the gamma process can be found in Kingman [25] and Zhou and Carin [52]. We put the prior on the CPT by considering i and ri as the parameters of the splitting function related to Equation (2). Due to the gamma process’s inherent shrinkage property, just a small finite number of experts will have non-negligible weights ri at 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 of implementation, we truncate the gamma process to a large finite number of atoms.
To further encourage simpler models at each node of the tree, we also put a shrinkage prior on of each expert. In particular, we consider the prior:
i ⇠ Yd
j=0
R N ( ji; 0, 2ji)InvGamma( 2ji; a , 1/b i)d 2ji (6)
and b i ⇠ Gamma(e0, 1/f0) which motivates sparsity due to the InvGamma distribution on the variance parameter [42, 51].

heading: 3.3 Training Algorithm
text: Finding an optimal CPT requires solving a combinatorial, non-differentiable optimization problem. This is due to the large number of possibilities that any single node can separate the data. We propose a continuous relaxation of the splitting rule at each node to alleviate this computationally challenging task. Each internal node makes probabilistic rather than deterministic decisions to send samples to its right or left branch. We set the probability of going right equal to Equation (2), or any monotonic function of it. We use this probabilistic version to train the tree in a differentiable manner. Furthermore, at the test time, we threshold the splitting functions to provide a deterministic tree. In the following subsections, we explain in detail the proposed training algorithm for the splitting parameters (Section 3.3.1) and structure of the tree (Section 3.3.2).

heading: 3.3.1 Learning Split Parameters
text: Assuming the tree structure is given, we explain how to infer the tree parameters for each task.
Classification. For this task, we formulate the training as an optimization problem by considering the mutual information between the two random variables Y (category label) and L (leaf id) as our 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 a probabilistic rather than a deterministic tree, and 2) we learn the parameters of all nodes jointly rather than learning them in a greedy fashion. In terms of learning split parameters, the closest paper is Hehn et al. [20]; however, it uses an EM algorithm to learn the parameters as opposed to our novel method, where we optimize a probabilistic version of mutual information for classification. Additionally, the method in Hehn et al. [20] is only applicable to classification tasks.
We model our probabilistic tree by letting
` ⇠ P✓(` |xn) such that ` 2 Sleaf, (7)
where Sleaf is the set of all leaf nodes and P✓(` |xn) is the probability of arriving at leaf ` given the sample feature xn. We assume each internal node makes decisions independent of the others and use the probabilities in Equation (2) when sending a data sample to the left or right branch. This assumption lets us derive a formula for P✓ as
P✓(` |xn) = Y
(v,dv) 2⌫` q✓v (dv |xn), (8)
where
q✓v (dv = 1 |xn) = 1 q✓v (dv = 0 |xn)
= 1 e PK i=1 r (v) i ln (1+e (v)0 i ·x) (9)
and ⌫` is a path from the root to leaf ` and dv 2 {0, 1} encodes the right or left (0 or 1) direction taken at node v. The mutual information between Y and L can be expressed as
I(Y,L) = H(Y) H(Y |L) = H(Y) X
`2Sleaf p(L = `)H(Y |L = `), (10)
where H(·) 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 (10).
To make the training possible, we approximate the true data distribution with the empirical one to get
p̂(L = `) = PN
n=1 P✓(` |xn)/N. (11)
Denote 1[·] as an indicator function. By using Bayes’ rule, we derive ⇡̂ ` = (⇡̂`1, · · · , ⇡̂ ` C), the estimated probability vector of the categorical distribution for Y |L = `, as
⇡̂`j =
P n 1[yn=j]P✓(` |xn)P
n P✓(` |xn) , j = 1, . . . , C . (12)
Now by using Equation (12), we can approximate the entropy term H(Y |L = `) as
Ĥ(Y |L = `) = XC
j=1 ⇡̂`j log(⇡̂ ` j). (13)
Therefore, we can provide an estimator for the H(Y |L) as
Ĥ(Y |L) = X
`2Sleaf p̂(L = `)Ĥ(Y |L = `). (14)
By minimizing Ĥ(Y |L) with respect to ✓, we are in fact maximize the mutual information Î(Y,L). As discussed in Section 3.2, we also regularize CPT by adding a penalty term to Equation (14). We consider the negative log probability of the gamma process prior truncated with K atoms by letting
r1, . . . , rK iid ⇠ Gamma( 0/K, 1/c0)
where r1, . . . , rK are the parameters of internal nodes splitting function. The penalty term for each internal node can be mathematically formulated as
(15)L(⌫)reg = KX
k=1
⇣ (
0 K 1) ln r(⌫)k + c0r (⌫) k
⌘ + (a +1/2) Pd j=0 PK k=0[ln(1+ (⌫)2 jk /(2b k))].
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 at each leaf as its parameters. This way of determining the leaf parameters has been shown to achieve the highest AUC in binary-classification [15]. Algorithm 1 summarizes the training method.
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 ✓ { X n P✓(` |xn)(yn µ̂ `)2} (16)
such that
Algorithm 1 Stochastic gradient descent training of the tree splitting parameters for classification task. Input: Data {(x(n), y(n))}n=1:N , initial tree T (0) from Topology-Leaner algorithm, maximum number of polytope sides K, hyper-parameters of the gamma process prior a0, b0, c0, 0
for number of training iterations do • Sample a batch of m data samples {(x1, y1), . . . , (xm, ym)} • Send the data samples to the current probabilistic tree to get probability of each samples being in any leaf P✓(t)(`n = ` |xn) for all n 2 [1 : m], ` 2 Sleaf using eq. 8. • For each leaf, calculate the vector ⇡̂` = [⇡̂`1, . . . , ⇡̂`C ] which represent for the current batch what is the proportion of each data label in 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 Lreg = P ⌫2Sbranch L ⌫ reg
• Update the tree parameters by descending their stochastic gradient:
r✓(t) ⇣ Ĥ(Y |L) + Lreg ⌘
end for • Send all the data samples to the to the tree, and for each leaf set its parameter as ⇡̂`. • Use the threshold of 0.5 for the probabilistic decision function at each branch node to achieve a deterministic tree.
µ̂` = P n P✓(` |xn)ynP n P✓(` |xn)
(17)
and the calculation of P✓ is exactly the same as in the classification case. The leaf parameters are set as the mean response of the points arriving at 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 a tree given its structure and how to use it at the test time, the next section will describe how to find an optimal topology and initial parameters.

heading: 3.3.2 Topology Learning
text: 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.1. 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 qthr, such that it minimizes
n0 N · H({y(i)} n0 i=1) + N n0 N · H({y(i)} N i=n0+1),
where p(n0)  qthr  p(n0+1). The p(i) 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 3.3.1 titled as “Learning Split Parameters” (LSP) presents our algorithm for learning parameters when the structure is given. During both final refining and greedy training, LSP is 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 root. Then, after the greedy training, LSP is applied to the entire tree to jointly learn all the parameters, which is essentially a 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 LSP to train the parameter of the newly added stump, freezing the rest of the tree in a deterministic mode.

heading: 4 Experiments
text: 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 is partly due to the high variance of the leaf node’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.

heading: 4.1 Synthetic Dataset
text: In this section we compare CPT and other tree based approaches on toy examples to better demonstrate why CPT achieves better performance. We consider a dataset of 2,000 points, as shown in Figure 1. The data samples are independent draws of the uniform distribution on a two-dimensional space [ 1, 1]⇥ [ 1, 1], with the data points labeled as red if 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 [8], which is a canonical axis-aligned tree algorithm. Figure 1 shows the decision boundaries of all three methods. CART and LCN are trained with a maximum depth of 10, and CPT is trained with a 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 a leaf node. However, CPT does not have such a limitation, and each region can be the result of applying any set of logical operations on a set of convex polytopes. Figure 1 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 at a maximum depth of 2. However, one limitation of our method is that it can not yet achieve competitive AUC to a multi-layer neural network.
Figure 1c shows that CPT uses a 8-sided 2D convex polytope for the first split and a 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.

heading: 4.2 Classification and Regression
text: We evaluate the performance of CPT for regression, binary classification, and multi-class classification tasks. For regression and binary classification, we conduct experiments on datasets from MoleculeNet [47]. We follow the literature to 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 [10], 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 [35, 20]. The datasets statistics are summarized in Table 1.

heading: 4.2.1 Compared Baselines
text: We evaluate the performance of CPT against several state-of-the-art decision tree methods, including FTEM (Hehn et al. [20], “End-to-end learning of decision trees and forests”), TAO (Carreira-Perpinán and Tavallali [9], “Oblique decision trees trained via alternating optimization”), and LCN (Lee and Jaakkola [27], “Oblique decision trees from derivatives of ReLU networks”). We also consider several
additional baselines, including CART [8], HHCART [46], GUIDE [29], and CO2 [35]. Another related probabilistic tree work on decision trees is ANT (Tanno et al. [41], “Adaptive neural tree”), 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.
Our algorithm is implemented in PyTorch and can be trained by gradient-based methods. We use Adam [24] 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-squared 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 https://github.com/rezaarmand/Convex_Polytope_Trees.

heading: 4.2.2 Experimental Results
text: Tables 2 and 3 present the results for a variety of decision tree based algorithms. Some results are quoted from previous works [27, 20, 49]. 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-parameter tuning for CPT, the total number of different hyper-parameter 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) 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 t-test and p-value of 0.05) are highlighted.
From the results, it is evident that the added flexibility in splitting rules combined with an efficient training algorithm allows CPT to outperform the baseline algorithms. Our method achieves the state-of-the-art performance, while, notably, using significantly shallower trees. For instance, CPT obtains the best performance in Connect4 with only depth 2 and 4 leaves, while other methods need a depth of at least 8.
It also improves the regression performance on the PDBbind dataset by a 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 a complete tree and generally needs to have a considerably large depth to achieve competitive results. For instance, consider its enormous size when trained on MNIST and Connect4 in Table 3.

heading: 4.3 Potential Negative Societal Impact
text: One often-neglected side effect of improving the interpretability of a machine learning model is the risk of automation bias and a 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 of that risk.

heading: 5 Conclusion
text: We propose convex polytope trees (CPT) as a generalization to the class of oblique trees that improves their accuracy and shrinks their size, which consequently provides better predictions. CPT owes its performance to 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 of 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 to a significant performance gain for the family of decision tree models. Another promising direction for future work is investigating the combination of CPT with various ensemble learning methods, such as boosting.

heading: Acknowledgements
text: M. Zhou acknowledges the support of NSF IIS-1812699, 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 a gift fund from ByteDance Inc.

Review summaries:
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.

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. 

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