Learning Axis-Aligned Decision Trees with Gradient Descent
Authors: Sascha Marton
Christian Bartelt
Stefan Lüdtke
Venue: Submitted to ICLR 2023 (2023)
Keywords: Decision Trees
Gradient Descent

Abstract: Decision Trees are commonly used for many machine learning tasks due to their high interpretability. However, learning a decision tree from data is a difficult optimization problem, since it is non-convex and non-differentiable. Therefore, common approaches learn decision trees using a greedy growth algorithm that minimizes the impurity at each internal node. Unfortunately, this greedy procedure can lead to suboptimal trees.

In this paper, we present a novel approach for learning univariate, axis-aligned decision trees with gradient descent. This is achieved by applying backpropagation with an adjusted gradient flow  on a dense decision tree representation that optimizes all decision tree parameters jointly. We show that our gradient-based optimization outperforms existing baselines on several binary classification benchmarks and achieves competitive results for multi-class tasks. To the best of our knowledge, this is the first approach that attempts to learn univariate, axis-aligned decision trees with gradient descent.

Under review as a conference paper at ICLR 2023
LEARNING AXIS-ALIGNED DECISION TREES WITH GRADIENT DESCENT
Anonymous authors Paper under double-blind review
ABSTRACT
Decision Trees are commonly used for many machine learning tasks due to their high interpretability. However, learning a decision tree from data is a difficult optimization problem, since it is non-convex and non-differentiable. Therefore, common approaches learn decision trees using a greedy growth algorithm that minimizes the impurity at each internal node. Unfortunately, this greedy proce- dure can lead to suboptimal trees.
In this paper, we present a novel approach for learning hard, axis aligned decision trees with gradient descent. This is achieved by applying backpropagation with a straight-throug! operator on a dense decision tree representation that jointly opti- mizes all decision tree parameters. We show that our gradient-base -based optimization outperforms existing baselines on several binary classification benchmarks and achieves competitive results for multi-class tasks. To the best of our knowledge, this is the first approach that attempts to learn hard, axis- axis-aligned decision trees with gradient descent without restrictions regarding the structure.
INTRODUCTION
Decision trees (DTss) are one of the most popular machine learning models and are still frequently used today. Especially with the increasing interest in explainable artificial intelligence (XAI), DT's regained popularity. However, learning a DT is a difficult optimization problem, since it is non- convex and non-differentiable. Finding an optimal DT for a specific task is NP-complete prob- lem (Laurent & Rivest, (1766). Therefore, the common approach to construct DT based on data is greedy procedure (Breiman al., 1984, Quinlan 1993) that minimizes the impurity at each internal node. The algorithms that are still used today, namely Bremmnn et al. (1984) and C4.5 Quin- Breiman
lan (1993), date back until the 1980s and since then remained mostly unchanged. Unfortunately, greedy algorithm only yields to locally optimal solutions and therefore can lead to suboptimal trees. We illustrate the issues that can arise when learning DTs with a greedy algorithm in the following example:
Example The Echocardiogram datase deals with predicting one-year survival of patients after heart attack based on tabular data from an echocardiogram. Figure T shows two decision trees. The left tree is learned using a greedy algorithm (CART) and the right tree is learned using our gradient-based approach. We can observe that the greedy procedure leads suboptimal tree with a significantly lower performance. Splitting on the wall-motion-scom is the locally optimal split (see Figure la), but globally, it is beneficial split based the wall-motion-score with different values conditioned on the pericarcial-effssiee in the second level (Figure lb).
The contribution of this paper is novel approach for learning hard, axis-aligned DTs based on joint optimization of all parameters with gradient descent, which we call gradient-based decision trees (GDTs). Using gradient-based optimization, we can overcome the limitations of greedy approaches, as indicated in Figure [b] We propose a suitable dense DT representation that allows a gradient-based optimization of the tree parameters (Section 3.2). We further present an algorithm that allows us to deal with the non-differentiable nature of DTT,, while still allowing an efficient optimization using backpropagation with a ttraight-through (ST) operator (Section 3.3
Available under: https://archh wuu.uii..cc..................... http://m//aattattt//eeeee rd ogram (last accessed 16.08.2022)

---

We empirically evaluate GDTs several real-world benchmark datasets (Section 4 GDTs out- Under review as a conference paper at ICLR 2023
Fi Score:
wall mobton-scort 23.5
Fi Score:
perierdial 65
pesticnciial offusion 0.
wall motioti-ccree
Wal mnotion Score
22.2
21.0
Class
Class
Class
Class
Class
Class
Class
(a) Greedy DT (CART)
(b) Seadient-Baseee DT (GDT)
Figure 1: Greedy versus Gradient- DT. Two DTs learned on the Echocardiogram dataset. While the CART DT (left) only makes locally optimal splits, the GDT (right) performs joint optimization of all parameters, which results in a significantly higher performance.
perform existing baselines on several benchmark datasets and achieves competitive results for DT learning. Furthermore, the resulting trees are less prone to overfitting and represent more accurate quantification uncertainty, since they comprise probability distributions at the leafs. A gradient- based optimization also provides more flexibility, since splits can be adjusted during the training. This allows an application of GDTss to dynamic scenarios, as for instance online learning.
2 RELATED WORK
Greedy DT Algorithms The most prominent and still frequently used algorithms, namely CART (Breiman et al., 1984) and C4.5 (Quinlan 1993) an extension of ID3.0 (Quinlan 1986), data back to 1980s and both follow a greedy procedure to learn a DT. Since then, many variations to those algorithms have been proposed, for instance C5.0 (Kuhn et al. (003) and GUIDE (Loh) 2002 2009). However, until today, none of these algorithms was able to consistently outperform CART and C4.5 shown by Zharmagammbeoo al. (202T).
Lookahead DTs To overcome the issues of a greedy DT induction, many researchers focused on finding an efficient alternative. One solution to mitigate the impact of a greedy procedure are methods that look ahead during the induction (Sarkar et al. 1994). However, MMrthy| (1996) argue that those methods not only suffer from an enormous increase in the computational complexity, but also suffer from pathology, i.e., they frequently produce worse trees in terms of accuracy, tree size and depth. One explanation could that lookahead trees, especially without regularization, are prone to overfitting.
Optimal DTs Optimal DTss try to optimize an objective (e.g., the purity) using approximate brute force search to find globally optimal tree with certain specification (Zharmagambetov et al. 2021 OCT (Bertsimas & Dunn, 2017) defines the optimization as a mixed integer optimization (MIO) problem which is solved using MIO solver. In contrast, DL8.5 (Aglin et al. (0200) and GOSDT (Lin et al. 2020) approximate a brute force search using a branch-and-boun remove irrelevant parts from the search space. MurTree (Demirović et al., 2022) further
algorithm
dynamic programming to reduce the runtime significantly. However, state-of-the-ar approaches still require binary data and therefore a discretization of continuous features (Aglin al. 2020
Demirović et al. 2022, Bertsimas & Dunn, 2017).
Genetic DT's Another way learn DT's in non- non-greedy fashion is using evolutionary algorithms for DT induction. Evolutionary algorithms perform robust global search in the space of candidate solutions based on the concept of survival of the fittest (Barros et al. (01T). This usually results in better identification of feature interactions compared to greedy, local search (Freitas 2002).
Oblique DTs In contrast to vanilla DTs that make hard decision at each internal node, many ap- proaches to hierarchical mixture of expert models (Joraan & Jacobs 1994) have been proposed. They make soft decisions where each branch is associated with probability (Isoy et al., 2012] Frosst & Hinton 2017). The resulting models do not comprise axis-aligned splits, but are oblique
2

---

Under review as a conference paper at ICLR 2023
respect to the axis. These adjustments in the tree architecture allow the application of further op- timization algorithms, as for instance the expectatonnmmxxiiizttonn (EM) algorithm for maximum likelihood estimation (Dempster et al. 1977| Jordan & Jacobs 1994] or gradient descent Irsoy et al.) 2012 Frosst & Hinton| 2017). Blanquero et al. (2000) try to increase the interpretability of oblique trees by optimizing for sparse splits using fewer predictor variables at each split and simultane- ously fewer splits along the whole tree. Tanno et al. (2019) combine the benefits of neural networks and DTs using so-called adaptive neural trees (ANTs) that allow a gradient- based end-to-end opti- mization. They employ a stochastic routing based on Bernoulli distribution where the mean is a learned parameter. Furthermore, ANTs utilize one or more non-linear transformer modules at the edges, making the resulting trees oblique. Norouzi et al. (2015) proposed an approach for efficient non-greedy optimization of DTs that overcomes the need of soft decisions to apply gradient-based algorithms. This includes joint optimization of the split function at all levels and leaf parameters by minimizing a convex-concar upper bound on the trec's 's empirical loss. While this allows the use of hard splits, the approach is still limited to oblique trees. Zantedeschi et al. (202I) use argmin differentiation to simultaneously learn all tree parameters by relaxing a mixed-integen program for discrete parameters allow maadient-based optimization. This allows deterministic tree routing which is similar to GDTs. However, they require a differentiable splitting function (e.g. linear split function which results in oblique trees). In contrast to oblique DTs, GDTs make axis-aligned splits that only consider single feature at each split, which provides a significantly higher interpretabil- ity for individual splits. This is supported by Moonar 2020) where the author argues that humans cannot comprehend explanations involving more than three dimensions at once.
Deep Neural Decision Trees (DNDTs) Yang al. (2018) propose DNDTs which realize tree models as neural networks, utilizing a soft binning function for splitting. Therefore, the resulting trees are soff] but axis-aligned which makes this work closely related to our approach. Since the tree is generated via Kronecker product of the binning layers the structure depends on the number of features (and the number of bins). As the authors discussed, this results in poor scalability with the number of features, which can currently only be solved by using random forests for high- dimensional datasets (2 12 features). Our approach, in contrast, scales linearly with the number of features, making it applicable for high-dimensional datasets as well.
GRADIENT-BASED AXIS-ALIGNE DECISION TREES
In this section, we propose gradient- based decision trees (GDTs) as a novel approach to learn DTs. Therefore, we introduce a novel DT representation and a corresponding algorithm that allows learn- ing hard, axis-aligned DTs with gradient descent. More specifically, we will use backpropagation with a traiighttthruugh (ST) operator (Section 3.3) on a dense DT representation (Section 3.2) to adjust the model parameters during the training, as we will explain in Section 3.4
3.1 ARITHMETIC DECISION TREE REPRESENTATION
In the following, we will introduce a notation for DT's with respect to their parameters. We formulate DTs as an arithmetic function based on addition and multiplication instead of a nested concatenation of rules. This formulation will be useful for describing the gradient- based learning in Sections 3.. 3.4 Note that we focus on learning fully-grown DT's within this paper.
The parameters of DT of depth d comprise one split threshold and one feature index for each internal node, which we denote as vectors T E 2²2-1 and & E N22-1 respectively, where 2d equals the number of internal nodes in fully-grown DTT.ddiitionally each leaf node comprises class membership in the case of a classification task or a value in the case of regression tasks, which
we denote as the vector X E C² where C is the set of classes and 2d equals the number of leaf nodes in a fully-grown DTss. Figure 2 shows our tree representation in comparison to a common tree representation for exemplary DT.
The authors also propose using ST Gumbel-Softmne as alternative to generate hard trees, which is similar our approach.
3

---

Under review as a conference paper at ICLR 2023
2.0
Spteantaras (1,2)
9,
1-
2 -12
2
Spaptiside (X.2 1.2)
Sy Sprevssitee 1,09)
1-8
Class 0
Class 0
Class
Class
Class 0
Class 0
Class
Class
(a) Vanilla DT Representation
(h) Adjusted DT Representation
Figure 2: DT Representations. Exemplary DT representations with depth for dataset comprising 3 variables and 2 classes. The DT at the right can be represented using the vectors t [0, 2, 1], 2.0, 1.2, 0.9] and À [0, 0, 0, 1].
Formally, we can express DT as a function (T,,,, 2) IR" - with respect its parameters:
2d
() = Σ d L(E),T,,
(1)
1=
L function that indicates whether sample Rn belongs leaf
The indicator function L. can be defined as a multiplication of the split functions the preceding internal nodes. We define split function S as a Heaviside step function defined as:
ff, 2T
Steaviside (a)e, r)
(0, otherwise
where i is the index of the feature considered at a certain split and is the corresponding split threshold.
Enumerating the internal nodes of fully-grown tree with depth d in breadth-first order, we can now define the indicator function L as:
( II -l,((,,).)) S(almaa))) ((.45)
(3)
1=1 +p(1, (1 ((..)) 4(...))))
Here, is the index of the internal node preceding specific leaf node at a certain depth j. Further, defines whether the left branch (p 0) the right branch 1) taken certain internal node to reach leaf node I. Both values, i and p. are constant for a certain architecture and can be calculated straightforward (see Appendix I..I.
As becomes evident, DTs involve non-differentiable operations (Equation 2}. which precludes the application of the backpropagation algorithm for learning the parameters. More specifically, there are three challenges we need to solve if we want to use backpropagation to efficiently learn a DT:
C1 The index for the selection of the considered feature in certain split is defined as parameter of the DT and standard optimization with 1 N. However, the index gradient descent requires E RR.
C2 The split function S(æ, i, r) is Heaviside step function with undefined gradient for x, and gradient elsewhere, which precludes an efficient optimization.
C3 The leaf node in vanilla DT comprises only the class membership and therefore À C. To optimize the leaf node parameters, we need e to apply gradient descent and calculate informative loss value cost function.

---

Under review as a conference paper at ICLR 2023
The main difference of GDTs to standard DT algorithm is that we dense representation for the internal node parameters (T and 1) to jointly optimize the split thresholds and the selection the corresponding features for all internal nodes (Section 3.2). Furthermore, the backpropagation to allow the use of hard and axis-aligned DT's during training (Section 3.3
ST operator during
3.2 DENSE DECISION TREE REPRESENTATION
In this subsection, we propose a differentiable representation of the feature indices & to allow gradient-based optimization. Therefore, we extend the vector & E R²"
- to a matrix, where I E
2=2 x RR. This is achieved by one-hot encoding the feature index as R" for each internal node. This adjustment necessary for the optimization process to account for the fact that feature indices are categorical instead of ordinal.
We further propose using similar representation for the split thresholds T IR22- x R by storing one value for each feature as T E I2" instead of a single feature. This adjustment is designed to support the optimization procedure, since the split thresholds are not interchangeable for different features: A split threshold that is reasonable for one feature might not be reasonable for another feature. By storing one split threshold for each feature, we support exploration during the optimization.
This representation is inspired by the DT representation of Marton al. (2022) used for predicting a DT as a numeric output of a neural network. Further, our matrix representation for the feature selection similar to the one proposed by Popov et al. (2019) but does additionally include matrix representation for the split thresholds.
Besides the previously mentioned advantages, using a dense DT representation allows the use of matrix multiplications for an efficient computation, as we will show in the following. Therefore, reformulate the Heaviside split function in Equation 2 follows:
Jogistic (xe, b, T== =0
Σ 1=1
4:44
4T
(4)
i=0
Stogistic hard (xC, T)
Stogistic (x), L, T)
(5)
where [.1 stands for rounding to the closest integer. For our case, where is one-hot encoded vector for the feature index, Spogistic (x: L, T) Heeaviside (x, T) holds.
3.3 BACKPROPAGATION OF DECISION TREE Loss
While the dense DT representation introduced in the previous section emphasizes an efficient learn- ing of axis-aligned DT's, it does not solve C1-C3. Therefore, in this subsection, we will explain how solve those challenges by using ST operator during the backpropagation when optimizing with gradient descent.
For the function value calculation in the forward pass. we need assure that is one-hot encoded vector. This can be achieved by applying a hardmax function on the feature index vector of each internal node. However, applying a hardmax is non-differentiable operation, which precludes gradient computation. To overcome this issue, we use the ST operator (Bengio et al.) (013): For the forward pass, we apply the hardmax as is. For the backward pass, however, we exclude this operation and directly propagate back the gradients of Accordingly, we can optimize the parameters of where & E R while still using axis-aligned splits during training (C1).
Similarly,
the ST operator assure hard splits (Equation by excluding L-1 for the backward pass (C2). Using the sigmoid logistic function before applying the ST operator (see Equation 4 utilizes the distance the split threshold additional information for the gradient calculation. If
the feature considered at an internal node for a specific sample is close to the split threshold, this
will result in smaller gradients compared to a sample that is more distant to the split threshold.
Furthermore, we need to adjust the leaf nodes of the DT to allow an efficient loss calculation (C3). Vanilla DT's comprise the predicted class for each leaf node and functions DT R - C. We use
5

---

Under review as a conference paper at ICLR 2023
[10
0.0
0.01
2 2.0
20
0.0
0.0]
[0.0
1.0]
0..0
10
0.0]
-1.2
10.0
122
Class
Class 0
Class
Class
11.0
0.00
04
[0.0
100
(a) Vanilla DT Representation
(b) Dense DT Representation
Figure 3: DT Representations. Exemplary DT representations with depth for a dataset comprising 3 variables and classes. Here, Sn, stands for Stogistic hard (Equation
probability distribution each leaf node and therefore define DTs function DT's : R" R. Accordingly, the parameters of the leaf nodes are defined as L E IR2" x Re for the whole tree and A R for specific leaf node. This adjustment allows the application of standard loss functions, as for instance the cross-entropy, during the optimization.
Figure visualizes our dense tree representation in comparison standard tree representation for an exemplary DT.
3.4 TRAINING PROCEDURE
In the previous subsections, introduced the adjustments that are necessary to apply gradient- based optimization for DTs. We implement this optimization using a gradient descent algorithm. During the gradient descent optimization, calculate the gradients using backpropagation (see Algorithm 2) We implement backpropagation using automatic differentiation based on the com- putation graph of the pass function, which used to calculate the function values. The tree pass function is summarized in Algorithm| [ and utilizes the adjustments introduced the previous sections. Furthermore, our tree routing allows calculating the tree pass function as a joint matrix operation for all tree nodes and all samples. We also want to note that the sophisticated dense rep- resentation which necessary during the training can be converted into an equivalent vanilla DT representation at each point in time.
Furthermore, our implementation optimizes the gradient descent algorithm by exploiting common stochastic gradient descent techniques, including mini-batch calculation and momentum using the Adam optimizer (Kingma & Bal 2014). Moreover, we implement an early stopping procedure and to avoid bad initial parametrizations during the initialization, we additionally implement random restarts where the best model is selected based on the validation loss.
4 EXPERIMENTAL EVALUATION
The goal of experiments is to evaluate the predictive performance of GDTs against existing approaches to learning DTs. We focus on axis-aligned DTs and compare GDTs to the following baseline algorithms:
We the sklearn (Pedregosa et al. 2011 implementation, which uses opti- mized version of the CART algorithm. While CART usually only uses Gini as impurity measure, also allow information gain/entropy as option during our hyperparameter optimization (HPO). Since the impurity measure is also the relevant difference between both algorithms as benchmark, but only the opti-
CART:
CART and C4.5, we decided to mized CART algorithm which is also the stronger benchmark to compare against.
Evolutionary DTs:: We use the GeneticTree (Pysiak 2021 implementation for evolution- ary DT's that implements an efficient learning DT's using genetic algorithm.
DNDT (Yang et al.) 2018): We use the official impmementation (Yang et al., 2022 for learning DT's with gradient descent.

---

Under review as a conference paper at ICLR 2023
Algorithm Tree Pass of Training Sample
1: function PASS(I, T,, L,
2:
G + 1; hardmax
for 0,....11
b Excluded in the backward pass
3:
T I-
b Excluded in the backward pass
4:
y [0]
5:
for [ = 0, ..... 2d do
6:
x+1 1
7:
for j 1,
d do
8:
i f 2
b Equation
2 2--0-11
9:
p
mod 2
Equation
10:
Ti, I1,1 I2
Equation
11:
2
b. Excluded in the backward pass
Excluded in the backward pass
13:
p ((1-p) (1-s))
>> Eqquaiin
end for
15:
ÿ g LIP
Equation
end for
17:
return ş
18:
end function
DL8.5 (Aglin et al. 2020): We use the official implementation (Aglin et al. 2022) for learning optimal DT's which includes improvements from MurTree (Demirović 2022) reducing the runtime significantly. As required, we discretized the data for DL8.5 as de- scribed the Appendix A.4
GDTs are implemented in Python using TensorFlow (Abadi et al. 2015 The experiments were conducted several benchmark datasets, mainly from the UCI Machine Learning repository (Dual Graff 2017). The dataset specifications and source are listed in Table 7 80%/20 /20 split train and test data for all datasets. Since GDTs and DNDT' requires validation set for early stopping, we performed another 80%/20% split on the training data. The remainder of the approaches utilize the complete training data. Further information on the hyperparameters given in the Appendix(A.5 A.5
We use random
4.1 RESULTS
GDTs are competitive to baseline DT learners First, evaluated the performance of GDTs against the baseline approaches on the mentioned benchmark datasets in terms of the F1-Score. We noted the mean reciprocal rank (MRR), similar Yang et al. (2018). The results are shown in Table Overall, GDTs outperformed state-of-the-ard non-greedy DT approaches for binary classifi- cation tasks (MRR of 0.648 for GDT vs. 0.454 for GeneticTree as best non-greedy benchmark) and achieved competitive results for multi-class tasks (0.512 for GDT vs. 0.490 for DNDT). Compared to greedy DTT trained by improved CART, GDTs achieved slightly higher performance on binary classification tasks (0.648 vs. 0.623) but underperformed on multi-class tasks (0.512 vs. 0.685). Considering the stdev of the reciprocal rank, we can observe that GDTs (0.275 and 0.213) are more robust than to CART (0.323 and 0.282).
Further, we can observe that for several datasets a greedy optimization achieved very poor results and was significantly outperformed by non-greedy optimization, as for instance on the Wisconsin Diagnostic Breast Cancer, Heart Disease and Lymphography datasets.
In general, it stands out, that GDTs achieved the best results for binary classification datasets with a lower dimensionality (n < 15). We can explain this by the dense DT representation required for the gradient-based optimization. Using representation, the difficulty of the optimization task increases with the number of features (more parameters at each internal node) and the number of
The code of our implementation is available to all reviewers in the supplementary material to assure anonymity. We will make it publically available here upon acceptance.

---

Under review as a conference paper at ICLR 2023
GDT
Greedy (CART)
GenetieTree
DNDT
DL8.5
Blood Trancfusion
0.763 1.63.100 0.029 (1) 0.743 1 0,042 (2)
0,684 1 0.049 (5)
0.726 1 0,046 (3)
0.725 0.030 (4)
Banknote Authentication
0,988 0.008 (1) 0.82 + 0.006 (2)
0,928 0.004 (5)
0.945 + 0.015 (4)
0,963
0.011 (3)
Titanic
0,808
0.030 (2) 0,802 1 0,033 (3)
0.779 0.033 (4)
0.736 4 0,069 (5)
0.816
0.027 (1)
Raisins
0,015 (3) 0.853 0.017
(1)
0.852 0.032
(5)
Rice
0,928 : 0.006 (2) 0.928 = 0.004 (3)
0.928 2 0.005 (4)
0,929 = 0.006 (1)
0,926 = 0.008 (5)
Echocardiogram
0.722 0.109
0.730 0.086
0.723 0.079
0.728 0.073
0.679 0,100
Wisconsin Diagnostic Breast Cancer
0.920 0.029 (1) 0.894 + 0.025 (5)
0.901 0.024 (4)
0.918 + 0.028 (2)
0.903 0.021 (3)
Loan House
0.769 0.030 (1) 0.767 0,036 (3)
0.769 0.033 (2)
0.665 0.052
0,757 0.026 (4)
Heart Failure
0.791 0.040 (I) 0.778 0.057 (3)
0.779 0.062 (2)
0.627
0.074 (5)
0.720 0.060 (4)
Heart Disease
0.798 0.042 (2) 0.755 0.064 (4)
0.803 0.043(1)
0.771 0.050 (3)
Adult
0.839
(2)
0.848 0.004
0.794
(4)
0.819 0.003 (3)
Bank Marketing
0,859 = 0.011 (3)
0.868 = 0.004 (1)
0.827 = 0.004 (4)
0.864 = 0.004 (2)
Cervical Cancer
0,920 0.019
0.917 0.022
0.920 0.019
0 0.022
Congressional Vating
0,949 0.021 (3)
0,960 0.017 (1)
0.960 0.017 (I)
0.941 0.025 (4)
Absenteeism
0.691 0.039 (I)
0,688
0.031 (2)
0,662 0.043 (4)
0,676 0.035 (3)
Heparitis
0.785 0.1 (2)
0.782
0.071 (4)
0,782 0.071 (3)
0.795
(1)
German
0,690 1 0.038 (2)
0.699 0.026 (1)
0,636 1 0.038 (4)
0.687 1 0.028 (3)
Mushroom
1,000 0,000
0.000
0,967 0,013 (4)
1,000
Crodic Card
0,798 = 0.006 (2)
0.799 + 0.005 (1)
0,795 = 0.005 (4)
0.796 = 0.007 (3)
Horse Colie
0,840 0.047
0,840 0,034 (3)
0,868 0.027
0,831 0.035 (4)
Thyroid
0.957 0.007 (2)
0,963 = 0.003 (1)
0,851 0.081 (3)
0.797 0.008 (4)
Spambase
0,892 0.012 (2)
0.923 0.011 (I)
0,874 + 0.017 (3)
0,869
0.012 (4)
Mean Reciprocal Rank
0.648 0.275 (1)
0.623 + 0.323 (2)
0.454 + 0.306 (3)
0.381 +: 0,246 (5)
0.383
0.254 (4)
Iris
0.944 0.947 (1) 0,930 1 0.032 (3)
0.890
0.061 (5)
0.933
0.034 (2)
0.913
0.043 (4)
Balance Scale
0.737 0.029 (3)
0,773 + 0.022 (2)
0.713
0.049 (4)
0.776 + 0.024 (1)
0,661
0.045 (5)
Car
0,852 0.038 (2)
0.975
0,715
0.044 (4)
0,701 (5042
0,827
0.024
Glass
0.678 1 0.074 (2)
0.681 1 0.076 (1)
0.587 1 0.100 (5)
0.671 1 0.082 (3)
0.634 1 0.069 (4)
Contracoptive
0.531
(3)
0.559 0.025
(4)
0.477 = 0.048
0.568
Solar Flare
0,793 = 0.027 (3)
0.795 + 0.024 (2)
0.793 = 0.026 (4)
0.801
= 0.028 (1)
0,790 = 0.026 (5)
Wine
0,923 0.041 (I)
0.914 0.032
0,891 0.055
0.847
0.046
0,856 0.018
Zoo
0,946 0.054 (2)
0,970 1 0.050 (1) 0,850
041
0,929 0.087 (3)
Lymphography
0,769 0.050 (2)
0.724 + 0,075 (4)
0,740 + 0.071 (3)
0.824 0.102 (I)
Segment
0,943 0.009 (2)
0,966 0.M05
0,770 0.049 (4)
0,810 0.013 (3)
Dermatology
0,934 1 0.032 (2)
0,965 + 0.023 (1)
0.894 0.102 (4)
0.929 1 0.026 (3)
Landsat
0,852
(2)
0.856 = 0.008
0,674 (4)
0.808
Annealing
0,970 0.014 (3)
0,973 + 0.011 (2)
0,821 + 0.091 (4)
0.985 0.007 (1)
Splice
0,883 0.011
0.918
0.006
0.667
0.066
0.923 (I)
Mean Reciprocal Rank
0,512 0.213 (2)
0.685 1 0.282 (1)
0.255 0.036 0.490 1. 0.337 (3) 0.487 0.328 (4)
Table 1: Performance Comparison. We report Fi-scores (mean + stdev over 10 trials). We also report the ranking of each approach in brackets. The top part comprises binary classification tasks and the bottom part multi-class datasets. The datasets are sorted by the number of features. Due to scalability issues, DNDTs were only applied to datasets with maximum of 12 features, as suggested by Yang et al. 2011))
classes (more parameters at each leaf node). Therefore, in future work, we aim to optimize the proposed dense representation, c.g., by using parameter sharing techniques.
GDTs are robust to overfitting We can observe that GDTs were more robust and less prone to overfitting than a greedy optimization. We measure overfitting by the difference between the mean train and test performance (see Table 2). This difference was significantly smaller for GDTs (0.026 for binary and 0.038 for multi-class) compared to CART (0.042 and 0.085). An even higher overfitting can be observed for DNDT (0.081 and 0.062) and DL8.5 (0.069 and 0.059). Overfitting can also explain why optimal decision trees, do not achieve superior results on test data, which was also reported by Zharmagambetov et al. (202T). Similar to GDTs, GeneticTreess were less prone to overfitting (0.015 and 0.021).
GDTs do not rely on extensive HPO An advantage of DTs over more sophisticated models, besides their interpretability, is that greedy approaches are not reliant on an extensive HPO to achieve reasonable results. In this experiment, we wanted to show that the same is true for GDTs, We used the default parameter settings for each model and fixed the maximum depth to 5 for GDT's and CART. Overall, the performance gain of HPO was rather small for all approaches: The maximum average performance gain for binary tasks could be observed for CART, with an increase of only 0.007 (see Table 2. For multi-class tasks, the average performance gain was higher with a maximum of 0.049 for GDTs. However, this is mainly due to small number of datasets where HPO increased the performance significantly as for instance the Segment dataset with a performance increase of 0.111 for GDT' and 0.1 for CART (see Table 3 for details).
8

---

Under review as a conference paper at ICLR 2023
Train-Test Differential (Mean)
HPO Impact (Mean)
Model
binary
multi-class
binary
multi-class
GDT
0.026
0.038
0.006
0.049
Greedy (CART)
0.042
0.085
0.007
0.032
GeneticTree
0.015
0,021
0,000
0.004
DNDT
0.081
0.062
0,000
0,000
DL8.5
0.069
0.054
0.000
0.000
Table 2: Summarized Results. (1) The mean difference between the train and test performance of each approach as overfitting indicator (see Table complete results) and (2) the impact of НPО by measuring the difference of the model performance with and without HPO for each approach (see Table 3 for complete results).
Probabilities at the GDTs leaf nodes provide calibrated uncertainties Another advantage of GDTs (and similarly DNDTs) is the fact that they provide probabilities as a direct measure of the model's confidence. We compared the probability-based confidence with the purity measure in terms of the ROC AUC score (see Table 5). Comparing the probability-
approaches, GDTs achieved significantly higher MRR based the ROC AUC score of 0.818 for binary and 0.789 for multi-class tasks, compared to DNDT (0.628 and 0.655). Both of these probability- bbased ap- proaches significantly outperformed approaches that learn vanilla DTs, where CART achieved the highest MRR (0.460 and 0.458).
GTDs can be learned efficiently for large and high-dimensional datasets Considering the run- time of the different approaches listed in Table 4 it stands out, that a greedy optimization was significantly faster than any other approach for each dataset (perfect MRR of 1.00 based on the run- time). Nevertheless, for most datasets, learning a GDT took less than 60 seconds, with maximum of 122 seconds for the Congressional Voting dataset. DNDTs achieved similar runtimes compared to GDTs. This is also reflected by the MRR where GDTs achieved 0.254 for binary and 0.257 for multi-class and DNDT's achieved 0.228 and 0.221 respectively. DL8.5 has a low runtime < 10 sec- onds for most datasets, however
observe scalability issues with the number of features and number of samples as they require significantly higher runtime for certain datasets (c.g.. > 330 seconds for Credit Card and > 1800 seconds for Splice).
CONCLUSION AND FUTURE WORK
In this paper, we proposed a method for learning hard, axis-aligned DTTs based on a joint optimization of all parameters with gradient descent. We use backpropagation with a ST operator to deal with the non-differentiable nature of DTs and introduced dense DT representation that allows efficient optimization. Using gradient- as it is the case for standard, greedy DT induction methods like CART. We empirically showed that GDTs outperform existing baseline methods on several benchmark datasets. Additionally, GDTs provide calibrated uncertainties in terms of probability distributions the leaf nodes, which also increases the interpretability of the model.
optimization, GDTs are not prone to locally optimal solutions,
Furthermore, gradient-based optimization provides more flexibility. It is straightforward to a custom loss function that is well-suited to the specific application scenario. Another advantage of gradient-based optimization the possibility relearn the threshold value well the split index. This allows the application of GDTs to dynamic environments, as for instance online learning scenarios, without adjustments.
Currently, GDTs are fully-grown. In future work, we want to apply pruning mechanisms to re- duce the tree size for instance through learnable choice parameter to decide if node pruned, similar to Zantedeschi et al. (202T). While we focused on stand-alone DT's to generate intrinsi- cally interpretable models within this paper, GDTs can easily be extended random forests performance-inteerrttabilll trade-off, which is subject to future work.
'Commonly, probabilities are obtained from the purity ratio of each class gateway to the model's confidence for vanilla DT' (Pedregosa al. 2011.

---

Software Under review as a conference paper at ICLR 2023
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangging Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg. Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, llya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wat- tenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learn- ing on heterogencous systems, 2015. URL hitps: httt:p::/www..ennte www.wtwwswr.ww.....o org available from tensorflow.org.
G. Aglin, S. Nijssen, and P. Schaus. Pyd18.5. http:::/gittuub.commaaaaaa 3yd18.5| 2022. Accessed 13.11.2022.
Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branch-and and-bound search. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 34, pp. 31 3146-3153, 2020.
Rodrigo Coelho Barros, Márcio Porto Basgalupp, Andre CPLF De Carvalho, and Alex A Freitas. A survey of evolutionary algorithms for decision-tree induction. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(3):291-312, 2011.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients 2013.
through stochastic neurons for conditional computation. arXiv preprint
Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7):1039- 1082, 2017.
Rafael Blanquero, Emilio Carrizosa, Cristina Molero-Río, and Dolores Romero Morales. Sparsity in optimal randomized classification trees. European Journal of Operational Research, 284(1): 255-272, 2020.
Leo Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984. ISBN 0-534-98053-8. URL http: smu. www..eeaa/mmh///333111eee.
cart pdf
Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter J Stuckey. Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1 1-7,, 2022.
Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1); 1-22, 1977.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017, URL bttp:://acrr ics. adcieedumml
Alex A Freitas. Data mining and knowledge discovery with evolutionary algorithms. Springer
Science & Business Media, 2002.
Nicholas Frosst and Geoffrey Hinton. Distilling a neural network into soft decision tree. arXiv preprint arXiv:1711.09788 2017.
Ozan Irsoy, Olcay Taner Yildız, and Ethem Alpaydın. Soft decision trees. In Proceedings of the 21st international conference on patlern recognition (ICPR2012), pp. 1819-1822. IEEE, 2012.
Michael I Jordan and Robert A Jacobs. Hierarchical mixtures of experts and the em algorithm.
Neural computation, ((2):181-214 1994.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Max Kuhn, Kjell Johnson, al. Applied predictive modeling, volume 26. Springer, 2013.
10

---

Under review as a conference paper at ICLR 2023
Hyafil Laurent and Ronald L Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pp. 6150-6160. PMLR. 2020.
Wei- Yin Loh. Regression tress with unbiased variable selection and interaction detection. Statistica sinica, pp. 361-386, 2002.
Wei- Loh. Improving the precision of classification trees. The Annals of Applied Statistics, pp- 1710-1737, 2009.
Sascha Marton, Stefan Lüdtke, Christian Bartelt, Andrej Tschalzev, and Heiner Stuckenschmidt. Explaining neural networks without access training data. arXiv preprint arXiv:2206.0488 04499,, 2022.
Christoph Molnar. Interprelable machine learning. Lulu. com, 2020.
Kolluru Venkata Sreerama Murthy. On growing better decision trees from data. The Johns Hopkins University, 1996.
Mohammad Norouzi, Maxwell Collins, Matthew A Johnson, David J Fleet, and Pushmeet Kohli. Efficient non-greedy optimization of decision trees. Advances in neural information processing systems, 28, 2015.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2888 2830, 2011.
Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural oblivious decision ensembles for deep learning on tabular data. arXiv preprint arXiv:1909.06312, 2019.
Karol Pysiak. Genetictree. cessed 27.08.2022.
2021. Ac-
J. Ross Quinlan. Induction of decision trees. Muchine learning, 1(1):81-106, 1986.
Ross Quinlan. C4.5: programs for machine learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993. ISBN 1-55860-238-0. URL http:://oottallll..mm acm, acm.org/ org/
citation. citatiio..cffmmi 152181
UK Sarkar, PP Chakrabarti, Sujoy Ghose, and SC DeSarkar. Improving greedy algorithms by lookahead-search. Journal of Algorithms, 16(1):1-23, 1994.
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference on Muchine Leurning, pp. 6166-6175 PMLR, 2019.
Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales. Deep neural decision trees. arXiv preprint 1806 06988, 2018
Yongxin Yang, Irene Garcia Morillo, and Timothy M. Hospedales. Deep neural decision trees. peatps://qithann com WOoo///OO/DDDD 2022. Accessed 13. 11.202..
Valentina Zantedeschi, Matt Kusner, and Vlad Niculae. Learning binary decision trees by argmin differentiation. International Conference on Machine Learning, pp. 12309, PMLR, 2021.
Arman Zharnagambetov, Suryabhan Singh Hada, Magzhan Gabidolla, and Miguel Carreira- Perpinán. Non-greedy algorithms for decision tree optimization: An experimental comparison. In 202/ International Joint Conference on Neural Networks (IJCNN, pp. 1-8. IEFE, 2021.

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 CALCULATIONS
The index of an internal node preceding a specific leaf node I at a certain depth j can be calculated follows:
j. = -2 2d-
(6)
Additionally, for certain leaf node I, p defines whether the left branch (p 0) or the right branch (p 1) was taken the internal node We can calculate p as follows:
p((.
2d-j mod
The calculation of the internal node index as well as the specification the path position also involve con-differentiable operations. However, since only focus on fully-grown trees, the sulting values are constant and can be calculated independently of the optimization, which does not preclude the application of gradient-based optimization algorithm.
A.2 GRADIENT DESCENT OPTIMIZATION
We use stochastic gradient descent (SGD) minimize the loss function of GDTs, which is outlined in Algorithm 2
We use backpropagation to calculate the gradients in Line 11-13. Furthermore, our implementation optimizes Algorithm 2 by exploiting common SGD techniques, including mini-
batch calculation and momentum using the Adam optimizer Kingma & Bal (2014). We also formu- late Line 6-9 as a single matrix multiplication for efficiency reasons.
Algorithm Gradient Descent Training for Decision Trees function TRAINDT(1, T, L, y, n. C, d, E
2:
T~u
Glorot uniform initialization
1+
+1
3:
T~u
D Glorot uniform initialization
22d-1
2 +-72
4:
L~u U
> Glorot uniform initialization
20
22040
5:
for i =
1...., do
6:
+
7:
for j 1, ,..., X do
8:
0j + U
PASS(I, I,, X₁)
9:
10:
end for
11:
I 1 1 +1 C(y. ( 9)
Calculate gradients with backpropagation
T T 0T (ly.g)
Calculate gradients with backpropagation
13:
L L L+ at. Cly.0)
> Calculate gradients with backpropagation
14:
end for
15:
end function
A.3
ADDITIONAL RESULTS
A.4 DATASETS
The datasets along with their specifications and source are summarized Table For all datasets, performed standard preprocessing. We applied ordinal encoding to all non-numeric features so that they can be handled by DTs. We further standardized all datasets to zero mean and unit variance. This step however is only necessary for approach and DNDTs. While standard DT
12

---

Under review as a conference paper at ICLR 2023
GDT
Greedy (CART)
GenetieTree
DNDT
DL85
Blood Trancfusion
0.762 0.035 (1) 0.733 1 0,045 (2)
0.671
0.036 (5)
0.726 1 0,046 (3)
0.725
0.030 (4)
Banknote Authentication
0,973 0.006 (1) 0.911 + 0.010 (2)
0.929 0.00 (5)
0.945 + 0.015 (4)
0,96 0.01 (3)
Titanic
0,801 0.030 (2) 0.801 + 0,030 (3)
0.777 0.035 (4)
0.736 4 0,069 (5)
0.816
0.027 (1)
Raisins
0.019 (4)
0.021
0.022 (1)
0.852 0.032
0,027 (3)
Rice
0,929 = 0.007 (2) 0.924 = 0.008 (5)
0.928 2 0.005 (3)
0,929 = 0.006 (1)
0,926 = 0.008 (4)
Echocardiogram
0.732 0.093
0.717 0.093
0.724
(3)
0.728 0.073
0.679 0,100
Wisconsin Diagnostic Breast Cancer
0.911 0.017 (3) 0.917 + 0.029 (2)
0.897 0.021 (5)
0.918 0.028 (1)
0.903 0.021 (4)
Loan House
0,771 0.031 (2) 0.747 0,042 (4)
0.775 0.031 (1)
0.665
0.052
0,757 0.026 (3)
Heart Failure
0.774 0.063 (2) 0.776
(I)
0.767 0.049 (3)
0.627 0.074 (5)
0.720 0.060 (4)
Heart Disease
0,780 1 0.064 (2) 0.726 1 0,051 (4)
0.820 0.049 (I)
0.771 0.050 (3)
Adult
0,823 0.015 (2)
0.005
0,004 (4)
0.819 0.003 (3)
Bank Marketing
0,861 = 0.004 (3)
0.862 = 0.004 (2)
0.827 = 0.004 (4)
0.864 = 0.004 (1)
Cervical Cancer
0 0.018
0.916
0.021
0.920 0.019
0 0.022
Congressional Vating
0,939 0.029 (4)
0,948
0.019 (2)
0.960 0.017 (I)
0.941 0.025 (3)
Absenteeism
0,673 0.036 (4)
0.696 0.027 (I)
0,678 0.042 (2)
0,676 0.035 (3)
Heparitis
(.974((1) (I)
0.777 0.089
0.770 0.097 (4)
0,796 0.076 (2)
German
0,680 1 0.036 (3)
0.702 0.027 (1)
0.636 1 0.031 (4)
0.687 1 0.028 (2)
Mushroom
0 0.008 (2)
0.979 0.002
0,965 0,010 (4)
1,000 0,000
Crodic Card
0,795 = 0.004 (3)
0.798 = 0.005 (1)
0.795 = 0.005 (4)
0.796 = 0.007 (2)
Horse Colie
0,835 0.039 (3)
0,849 0.055
0,862 0.021
0,831 0.035 (4)
Thyroid
0,914 0.010 (2)
0.937 = 0.005 (1)
0,840 = 0,040 (3)
0.797 0.008 (4)
Spambase
0,887 0.015 (2)
0.910 0.009 (1)
0,870
0.014 (3)
0,869 0.012 (4)
Mean Reciprocal Rank
0,519 1: 0.245 (2)
0.567 + 0.311 (1)
0.478
0.326 (3)
0.465 + 0.307 (4)
0.411
0.249 (5)
Iris
0,927 0.036 (3)
0,937
0.035 (1)
0.914
0.039 (4)
0.933 1. 0.034 (2)
0,913
0.043 (5)
Balance Scale
0,722 0.051 (3)
0.736 + (,016
0,700
0.033 (4)
0.776 + 0.024 (1)
0,661 0.045 (5)
Car
0,781 0.019 (3)
0.848
0.011
0,729
0.016 (4)
0,701 (5042
0,827
0.024 (2)
Glass
0,512 0.126 (5)
0.678 1 0.074 (1)
0,574 1 0.062 (4)
0.671 1 0.082 (2)
0.634 1 0.069 (3)
Contracoptive
0.533 0.021 (3)
0.553 0.022
0.477 = 0.048
0.568
Solar Flare
0,793 = 0.027 (3)
0.794 + 0.031 (2)
0.793 = 0.026 (4)
0.801
= 0.028 (1)
0,790 0.026 (5)
Wine
0,902 + 0.035 (2)
0.914 0.032
0,889 0.045
0.847
0.046
0,856 0.018
Zoo
0.867 0.082 (3)
0,921 T 0.090 (2)
0,288 0,105 (4)
0,929 0.087 (1)
Lymphography
0,720 0.090 (4)
0,746 + 0,083 (2)
0,782 0.095 (3)
0.824 0.102 (I)
Segment
0.832 0.029 (I)
0.795
0.024
0.074
0.810
(2)
Dermatology
0,920 1 0.052 (3)
0,949 = 0.023 (1)
0.865 1 0.115 (4)
0.929 1 0.026 (2)
Landsat
(3)
0.009
0,040 (4)
Annealing
0 + 0.018 (3)
0,973 + 0.011 (2)
0,803
0.078 (4)
0.985 0.007 (1)
Splice
0,821 0.022
0,900
0.008
0.703
0.084(4)
0.923 (1)
Mean Reciprocal Rank
0.377 0.183 (4)
0.702 1 0.261 (1)
0,262 0.029 (5) 0.514 1 0.331 (3)
0.585 0.328 (2)
Table 3: Performance Comparison Default Hyperparameters. We report the Fi-score (mean + stdev over 10 trials) on the test data. We also report the ranking of each approach for the corre- sponding dataset in brackets. The top part comprises binary classification tasks and the bottom part multi-class datasets. The datasets are sorted based on the number of features. Due to scalability issues, DNDTs were only applied to datasets with a maximum of 12 features, as suggested by Yang et al. (2018).
learning algorithms are independent of the feature scale, GDTs and DNDTs are sensitive to the feature scale due to the gradient updates.
For DL8 additional preprocessing was necessary since they can only handle binary features. There- fore, we one-hot encoded all nominal and ordinal features and discretized numeric features by one- hot encoding them using quantile binning with 5 bins.
A.5 HYPERPARAMETERS
In the following, we report the hyperparameters used for each approach. The hyperparameters were selected based on random search over a predefined parameter range for GDT, CART and GeneticTree and are summarized in Table Table [0] All parameters that were considered are noted in the tables. The number of trials was equal for each approach. For GDTs, we did not optimize the batch size as well as the number of epochs, but used early stopping with a predefined patience. For DL885 there are no tunable hyperparameters except the maximum depth. However, the maximum depth strongly impacts the runtime which is why we fixed the maximum depth to 4, similar to the maximum depth used during the experiments of the authors (Demirović et al., 2022] Aglin et al. 2020). Running the experiments with higher depth becomes infeasible for many datasets. In preliminary experiments, we also observed that increasing the depth to 5 results in a decrease in the test performance. For DNDT, the number of cut points is the tunable hyperparameter of the model according to the authors (Yang et al., 2018). However, it has to be restricted to 1 in order generate binary trees for comparability reasons. The learning rate and temperature were
13

---

Under review as a conference paper at ICLR 2023
GDT
Groedy (CART)
GeneticTree
DNDT
Trandusion
27.706 9,000 (5)
0.002
0.000 (1)
1,000
8.235
(4)
0,027
0.000 (2)
Bonkzooe Authentication
46.912 + 8.000 (4)
0.003
0.000 (1)
1.152 + (.000
47,474
+-57000 (5)
0.023
0.000 (2)
Tiianic
20,803 1: 10,000 (5)
0,002
0,000 (1)
8.056 1 5,000 (3)
16.085
4,000 (9)
0.104
0.000 (2)
Ruisins
42 10909- + 9,090 (5)
0
0,000 (1)
0.831 + 0.000 (3)
22,533
7.000 (4)
0.231
0.000
Rice
36,612 1: 9,000
0.008
0,000
1.539 1 0.000
71.666 28,000
0.498
0.000
Echocardivgram
51,105 10,000
0.002
0.000
Wiscomsi Diagnostic Breast Cancer
24 24.790 4: 7,090 (4)
0.004
0.000 (8)
1,987
1,000 (3)
29.417
12.000
0.554
0.000 (2)
Loun House
76,309 J: 26,000 (5)
0.002
0.000 (1)
2.191 1. 1,000 (3)
22.476
7,000 (4)
0.194
0.000 (2)
Heaat Failure
30.5011 1. 4,000 (1)
0.002
0.000 (1)
0.132 1 0,000 (2)
35,570 1 22.000 (5)
0.293
0.000
Heart Disease
9.684 = 090 (3)
0.002
0,000 (1)
12.946 #
11.000 (4)
0.451 = 0.000 (2)
Adult
106.875 +: 26,000
0.086 0.000
42,549
12,000
19,426
7,000
Marketing
61,027 1. 23,000
0.083
0,000
9.339
Cervical Cancer
2,090 (4)
0.002 0.000 (1)
(2)
0.182
0.000
Congressional Vocing
122.195 =: 44,000 (4)
0.002 0.000 (1)
0.115 +: 0.000 (2)
0.432 =
0.000 (3)
Ahsenteciom
41 944 + 9,000 (4)
0,003
0.000 (1)
7,816 + 3,000 (1)
5,919
3.000
Hepotitis
93.652 + 62.090 (4)
0.002
0,000 (1)
0.429 + 0,000 (3)
0.217
0.000 (2)
German
15,399 3,000
0.005
0,000
6.228
4,000
Mushroom
54.558
0.00N
39.021
3,206
2,000
11,090 (3)
0.186
0.000 (8)
1,000 (2)
334,752-
Home Colie
45.138 24.000 (4)
0.003
0.000
(1)
8,329 1. 4,000 (2)
9.334
3.000 (3)
Thymid
75. 169 + 19,000 (3)
0.029
0.000
(1)
85.355 + 46.000 (4)
6.492
2,000 (2)
Sponhase
12.275
3,890
0.037
0.000 (1)
12.083 + 3,000 (3)
5,418
1.000 (2)
Mcun Reciprocal Rank
0.254
0.043 (4)
1.000
0,000
0,360 4 0,081 (3)
0.228
0.025
0.459
0.079
Iris
8.969 + 2,000 (5)
0.002
0.000 (1)
0.927 0.000 (3)
6,847
1.000(4
0.016
0.000 (2)
Halance Scale
32,529
3.000 (5)
0.002
0.000 (1)
6.254
2,000 (3)
11.067
5,000 (4)
0.35
0.000 (2)
Car
31,089 +: 2,000 (4)
0
0,000 (1)
6.013 2,000 (3)
173,529
185.000
0.084
0.000 (7)
Glass
11.030
1,000
0.002
1.628 0.000
(500
Contracoptive
0.002
0.000
4.129
3.000
(2)
Solar Flaro
8,492 1: 3,000 (4)
0.0012
0.000 (1)
0.345 0.000 (3)
32.101
4,000 (5)
0
0.000 (2)
Wine
20-892 + 2,000 (4)
0.002
0.000 (1)
0.407 0.000 (2)
43.946
27.000
0.549
0.000 (9)
Zoo
10L. 1. 61.000 (1)
0.002
0,000 (1)
3.660 1.000 (3)
0.016
0.000 (2)
Lymphography
22-461 1: 9,000
0.002
0,000 (1)
0.547 0,000
0.349 1
0,000 (2)
Segment
36,779
3.000
0.014
0,000
11,370 2,000
14,833
1.000
Dermatology
12.615
0.002
0,000
6.792 2,000 (2)
22,681
(4)
Landsai
63.481
7,000 (3)
0.046
0.000 (1)
2.285
0.000 (2)
871 171,353
11 11.000 (4)
Ansealing
10.094 = 3,000 (4)
0.002
0.000 (1)
2.648
1,000 (2)
2.857
0.000 (3)
Splice
16.807 1 3,000 (2)
0.018
0,000 (1)
3.659 2. 2,000 (2)
1818.241
4: 227.000 (4)
Moan Reciprocal Rank
0.257 + 0.044 (4)
1,000 1,000 (1)
0.405 0,082 (3)
0,221 + 0,025 (5)
0.411 + 0.107 (7)
Table 4: Runtime Comparison. We report runtime without restarts based on the optimized hyper- parameters (mean + stdev over 10 trials). We also report the ranking of each approach in brackets. The top part comprises binary classification tasks and the bottom part multi-class datasets. The datasets sorted by the number of features. Due scalability issues, DNDTs were only applied to datasets with a maximum of 12 features, as suggested by Yang et (0118).
set as suggested by the authors. However, we extended their implementation to use early stopping based on the validation loss, similar to GDTs, to reduce the runtime and prevent overfitting.
Further details can be found in the code, which we provided in the supplementary material. Further- more, we used random restarts only for GDTs We made this decision based on the fact that CART is deterministic and therefore does not benefit from additional restarts and for GeneticTree increasing the population size would achieve similar results. Therefore, both baseline approaches would suffer from the use of restarts, since less data can be used for the training.
14

---

Under review as a conference paper at ICLR 2023
GDT
Greedy (CART)
GeneticTree
DL8.5
Blood T'ranfuuion
0.704 1: 0.053 (1)
0.609 1 0,063 (3)
0.522
0.044 (5)
0.704 1. 0,053 (2)
0.565 1.003 (4)
Banknote Authenticatio
0.982
0.007
0.989
0.006
Titanic
0.839 = 0.039 (1)
0.786 = 0.037 (3)
0.764 0.037 (5)
0.779 = 0.058 (4)
0.798 0.029 (2)
Raisins
0.898 0.020
0,853 0.017
0,858 1 0.022
0.908 (1019())
0,850 + 0.027
Rice
0.952 0.009 (2) 0,925 0.004 (4)
0,930 0.005 (3)
0.978 0.003 (1)
0,923 0,008
Echocardiogram
0,575 0.077 (3) 0,560 + 0,086 (4)
0.603 + (21
0.758 + 0.091 (1)
0,544 + 0.084 (
Wisconsin Diagnostic Breast
(2) 0,891
(4)
(.013(())
Loun House
0.693 1: 0.031 (1) 0.688 1 0,031 (3)
0.691 1 0.029 (2)
0.607 1 0.105 (5)
0.688 1 0.028 (4)
Heart Failure
0.791
0.757
(3)
0.061
Heart Discase
0,868 0.057 (1)
0.760 + 0.066 (4)
0.801 = 0.045 (2)
0,772 = 0.048 (3)
Adult
0.893 0.003
0,766 0.008 (2)
0.679 0.015
0,724 0.005
Bank Marketing
0.683 0.011 (1)
0.604 + 0.009 (2)
0,500 0.000 (4)
0,585 0.008 (3)
Cervical Cancer
0.497 0.067 (3)
0.522 + 0.036 (I)
0.500 0.000 (2)
0.493 0.014 (4)
Congressional Vatting
(I)
0,961 0.019
0,019 (3)
Absenteeism
0.677 1 0.060 (1)
0.657 = 0.039 (2)
0.625 1 0.037 (4)
0.647 = 0.035 (3)
Hepatitis
0.668
German
0.710 + 0.033 (I)
0.621 + 0.037 (2)
0.544 + 0.034 (4)
0.609 0.027 (3)
Mushroom
1,000 0.000 (1)
1,000 = 0,000 (1) 0.967 = 0,012 (4)
1,000 0.000 (I)
Crodit Card
0.755 0.007 (1)
0.653 0.005 (3)
0,646 0,011 (4)
0,662 0.011 (2)
Honse Colle
0,864 0.037 (I)
0,816 + 0.037 (4)
0,849 0.026 (2)
0,826 0.034 (3)
Thyroid
0,962
0.955 0.002
0,051 (3)
0.715 (4)
Spambase
0,899 : 0.011 (2)
0.916 = 0.010 (1)
0.864 = 0.016 (3)
0,859 = 0.011 (4)
Mean Reciprocal Rank
0.818 0.270 (1) 0.460 = 0.239
0.112 (5)
0.628
0.349
0.217 (4)
(2)
0,948
0.025
(5)
0.986
0.014(1))
(4)
Balance Scale
0.809 : 0.039 (2)
0.727 = 0.017 (3)
0.699 : 0.032 (4)
0,885 = 0.029 (1)
0.662 : 0.026 (5)
Car
0,945 0.021
0,963
0,598 0.034
0.032
0,765 0.028
Glass
0.721 0.154 (2)
0.697 + 0.142 (3)
0.606 0.078 (5)
0.764 + 0.177 (1)
0.646 0.111 (4)
Contraceptive
0.669 0.021
0.655 0,021 (3)
0.622 0.028 (5)
0.653 0,030 (4)
0,663 0.015
Solar Flare
0.521 0.062 (I)
0,501
0.003 (3) 0,500 + 0.000 (5)
0,510 + 0.030 (2)
0,501 0.002 (4)
Wine
0.960 0.036 (I)
0.934 1 0,023 (3)
0.927 0.036 (4)
0.951 4 0.023 (2)
0,890 0.018 (5)
Zoo
0.596
(2)
0,200
0,594
(3)
Lymphography
0,516 : 0.047 (2)
0,508 = 0.023 (4)
0,511 0.033 (3)
0,516 = 0.048 (1)
Segment
0.990 0.002
0.980 0.003
0.874 0.024
0.889 0.008
Dermatology
0.991 0.006 (1)
0.964 0.026 (2)
0.928 0.054 (4)
0,942 0.028 (3)
Landsar
0.968 0.004 (I)
0,900
0.006 (2)
0,788 0.022 (4)
0,866 0.005 (3)
Annealing
0.888 0.194 (1)
0,831
0.169
0.640
0.101 (4)
0.869 0.186 (2)
Splize
0.960 0.005 (1)
0.936
0.006 (3)
0.759
0.048 (4)
0.943 (2)
Mean Reciprocal
0.786
(1)
0.458 0.233 (3)
(5)
0.655 0.310
(4)
Table 5: Performance Comparison Uncertainty Quantification. We report ROC AUC score (mean + stdev over 10 trials). We also report the ranking of each approach in brackets. The top part comprises binary classification tasks and the bottom part multi-class datasets. The datasets sorted by the number of features. Due to scalability issues, DNDTs were only applied to datasets with a maximum of 12 features, as suggested by Yang et al. (2018)
15

---

Under review as a conference paper at ICLR 2023
GDT
Greedy (CART)
GeneticTree
DL8.5
Blood T'ranfuuion
0,769 0.037 (2)
0.798 0.015 (1) 0,882 1 0.048 (5)
0.750 1. 0,046 (4)
0.767 1 0.007 (3)
Banknote Authenticatio
(2)
0.99
0.001
0.017 (5)
0.953
(3)
Titanic
0,824 = 0.014 (2)
0,821 = 0.008 (3)
0.790=0.015 (4)
0.763 = 0.051 (5)
0.846 = 0.007 (1)
Raisins
0,876 0.009 (2) 0,866 0.004 (3)
0,863 1663+000 0.004 (4)
0.854 (5019
0,889 0.004
Rice
0,927 0.005 (3) 0.929 0.002 (2)
0,922 0.002 (5)
0,926 0.004
0,931 0.002 (I)
Echocardiogram
0,822 0.023 (5) 0.829 0,050 (3)
0,827 + 0.028 (4)
0.929 + 0,023 (2)
0.969 0.009 (1)
Wisconsin Diagnostic Breast
0,958
(3) 0,920 0.006
0.011 (5)
0,965 0.010
0.967 0.004
Loun House
0.786 1: 0.024 (3) 0,800 1 0.009 (2)
0.779 1 0.014 (4)
0.773 1 0.056 (5)
0.832 0.007 (1)
Heart Failure
(5)
0.027
Heart Discase
0,840 = 0.030 (4)
0.891 + 0.007 (2)
0,845 = 0.011 (3)
0.914 0.007 (1)
Adult
0,840 0.003
0.861 0.002
0,793 0.004 (4)
0 0.001
Bank Marketing
0,862 0.010 (3)
0.82 0.001 (I)
0828 0.001 (4)
0,868 0.002 (2)
Cervical Cancer
0 0.011 (3)
0.922 + 0,010 (2)
0.901 0.005 (4)
0.932 0.005 (1)
Congressional Vatiing
0,965 0.013 (2)
0,956 0.004
0,004 (4)
0,991 0.002
Absenteeism
0.831 : 0.018 (1)
0.806 + 0.015 (2)
0.677 1 0.023 (4)
0.774 1 0.009 (3)
Hcpatitis
0,815
0,985
German
0.751 + 0.026 (3)
0.777 + 0.018 (2)
0.686 0.022 (4)
0.791 0.005 (1)
Mushroom
1,000 0,000 (I)
1,000 0.000 (1)
0.968 0.012 (4)
1,000 0,000 (I)
Crodit Card
0.797 0.003 (3)
0,801 0.002 (1)
0,794 0.002 (4)
0,798 0.002 (2)
Honse Colle
0,864 0.014 (4)
0.897
0,010 (2)
0,867 0.015 (3)
0.944 0.005 (1)
Thyroid
0,947
(2)
0,987
0.001
(3)
0.003 (4)
Spambase
0,882 = 0.008 (3)
0.966 = 0.002 (1)
0.874 = 0.017 (4)
0.886 = 0.003 (2)
Mean Reciprocal Rank
0.426 0.207 (3)
0.633
0.287
(5)
0.372 2: 0.250
0.754
(1)
0,964
(2)
0,964
0.009
(5)
0,960
0.014
0.996
Balance Scale
0,819 : 0.025 (2)
1.000
= 0.000 (1)
0.778 : 0.017 (4)
0.808 = 0.018 (3)
0.768 : 0.007 (5)
Car
0.868 0.037
0.995
0,725 0.036
0.007
Glass
0.773 0.037 (4)
0,995
0.006 (I)
0.593
0.038 (5)
0,803 + 0.067 (2)
0.785 0.011 (3)
Contraceptive
0.545 0.019 (4)
0,578
0,008
0.509
0.032
0.555 0.024 (3)
0,585 0.004
Solar Flare
0.770 : 0.012 (4)
0.825
0.M07
0,766
0.006
0.792 + 0.018
0,804 0.006 (2)
Wine
0,990 : 0.011 (3)
1.000
0.000 (1)
0.947 : 0.015 (5)
0.998 4 0.004 (2)
0.976 0.005 (4)
Zoo
0.978 0.011 (3)
0.000
(.064
1,000
Lymphography
0.905 : 0.038 (3)
0,993 = 0.012 (1)
0.816200044 (4)
0.969 = 0.008 (2)
Segment
0,956 0.009
0.997
0.002
0.763
0.799 0.004
Dermatology
0.974 0.019 (2)
0.988 0.003 (1)
0.900
0.064
0 0.005 (3)
Landsar
0,881 0.007 (2)
0.909
0.002 (I)
0.676
0.044 (4)
0,816 0.003 (3)
Annealing
0 0.005 (3)
0,987
0.004
0,842
0.062
0.996 0.001 (1)
Splize
0,888 0.009 (3)
0.957
0.003 (1)
0.670
0.068 (4)
0.925 0.003 (2)
Mean Reciprocal
0.387 (3)
0.881 0.231
(5)
0.357 0.097 (4)
(2)
Table 6: Train Performance Comparison. We report F1-score (mean + stdev over 10 trials) on the
training data. We also report the ranking of each approach for the corresponding dataset in brackets. The top part comprises binary classification tasks and the bottom part multi-class datasets. The datasets are sorted based on the number of features. Due to scalability issues, DNDTs were only applied to datasets with maximum of 12 features, as suggested by Yang et al. (2018).
16

---

Under review as a conference paper at ICLR 2023
Number of
Number
Number Classe
Dataset Name
Peatures
Samples
Samples by Class
Link
Blood Tranfusioon
748
178 /70
2
SEcoo: /occc//.. ics.uci add/ni/datasete
Lodd wranstossoooooee 1on+ ce-center
Authentication
Bunknote
4
1372
610/762
2
SEt05 senkaotera www.eraaaattttte...e. lcstion
htt Jarchi 1e 1c5 det /dd/mm wwtp////daaaaeeeeeeeeeeee /datasets/
Tisanic
7
891
342
2
Raisin
900
(450
2
ReigintDataset
Rice
38:0
1030/21000 /180
2
RELp8:/74T0m Ve. Jes.uci .edu/n /detasets/
Tipe 375t-amee continooonndd T0ananc
Echocardingrm
132
107 25
2
NEC 785ch1//reey 105, ver courT datasets/
wcbone
Wisconsin Diagnostic
560
212/
2
iess /du/nl/ /dstasets/// Preag scons st
Loun House
11
614
422/ 192
2
nEt Kagele a. con/ code/ 50210787
hone- -own--rod------oo ct data
Heart Failure
12
299
96 /203
2
nEEp5:/ 7000:778rch1pp We 105, get ctt. /datactts/
Heartr www.rrggluutttccooo In recrddd
Heart Disease
13
308
164/139 139
2
datasets/
32561
7841 224220
2
7/a-chive, Tet, Ledu/m /dntanet a Lado
DLL
Bank Markeiing
14
45211
$289 / 39922
2
TE 28:7 Fen v8. 10% del (80077 /dal 45pl
Sank-marict-ing
Cervical Cancer
15
858
803
2
les, /dd//n /datasets/
Congressional Voting
425
267
2
1e5, coo
consressions one inotingtreoorm
Alsentteisam
18
740
279 1461
2
3E4 77 Ve, Jel /attt//s//ttt/////////
Abzont wcwsn--t----oon
Hepatiiis
19
155
32/ 123
2
/twc////cc//.o/ aei www.nn/
German
1000
2
stal [garmant oredil tradit NE6551
add//n /datasets/
Mushroms
22
8124
4208 /3916
2
7/4-chive. lns aet /nth//m hath//////a/aaa /dstazet /mmanrnor
Credit Card
23
30000
23364/ / 6666
2
dot3g b-offored di bacard-
Colie
27
368
nEt
Hoxsc+-0118
Thyroid
29
9172
2401 /6771
2
SEt95: FEt55://aschiiwe
-hyzold 3 di 2ea5e
Spamhase
57
4001
1813 /7888
2
P/ezchive. los.uct /dd//nl /ww. spenbass
150
50/ 50
attes:
7/azchive, 1ct, www.oooooo..o.......o...... www.//////t/otooooo
Balance Scale
625
49/ 288 288
3
colance-
SLL
Car
6
1728
384/ 69/ 1210 65
4
nEEp5: 7erchiye 1es. wwt../c...d.mm///noe..
Casaevalun
Glass
214
70/ 17 /9/9
6
www.iie..esss.e........ Jes.uel www.//////nn.... dataastts
Contraceptive
1473
629 333
Cont 1we toctcho
Solar Flare
10
1389
B171 / 1111/1 441 20
9/4/3/L
8
co1ar=flazc
NET nEt::///rra ve 19 bot. eedlyy /dat
Wine
12
178
59/71/448
3
7/azchive.
edarml
13/20/511//4/
Zoo
101
/LO
7/azchivo. des, cmm/m/ /otteett/rooooooooo
Lymphography
18
148
2/81 /61
4
3e4 0945997770 4rdh Ve. 105. 000 aatast
Lymchoorsppy
Segment
19
2310
330/ / /30 330
/30 /30 /330
7
www.m//w.......ooo. Jos. aei. wwwp/////etaaaae
Dermatology
366
112/61 72
120 1533/ 703 1358 626/ / 707 51508
clwrmnl 9 logy
NEE
add/// /datasets/
Landsat
36
6435
6
Statt oge Landsar 1Sate 11661
Arnealing
38
798
88 / 608 /3
5
314 /wwni/e 105, Vel www./// /ittaattts/////
Annoaling
1EEp517/e
/edo/n /d
Splice
3190
768 1665
co.scular1Sioloyy (Sp11ce- Junct lontcens Sequence5)
Table 7: Dataset Specifications.
17

---

Under review as a conference paper at ICLR 2023
Datasel Name
depth
Ir indixx
Ir.vlluss
Jr
optimizer
batch_size
epochs
restarts
early hurlyysoppingg.eee epocchs
Blood Transfusion
0.1000
0.1000
0.0050
512
10000
200
Banknote
Authentication
11
0.0100
0.0100
0.0500
adam
512
10000
200
Titanic
0.0100
0.0500
0.0050
adam
512
10000
10
200
Raisins
11
0.0500
0.0010
0.0100
adam
512
10000
200
Rice
0.0100
0.0005
0.0005
adam
512
10000
200
Echocardiogram
0.0050 11
0,1000
0.0010
adam
512
10000
10
200
Wisconsin
Diagnostic Breast
0.0001
0.0005
0.0050
adam
512
10000
10
200
Loan House
0.0500
0.0500
0.0005
adam
512
10000
10
200
Heart Failure
0.0050
0.1000
adam
512
10000
200
Heart Discase
0.0500
0.0005
0.0100
adam
512
10000
10
200
Adalt
11
0.0500
0.0100
0.0050
adai
$12
10000
200
Bank Marketing
0.1000
0.0001
0.0010
adam
512
10000
200
Corvical Cancer
0.0500
0.0001
0.0500
adam
512
10000
10
200
Congressional
Voting
11
0.1000
0.0010
0.0005
adam
512
10000
200
0.0500
0.0010
Hepatitis
0.0001
0.1000
0.0001
adam
512
10000
10
200
German
0.0010
0.0100
0.0050
adam
512
10000
200
Mushroom
0.0050
0.0100
0.0500
adam
512
10000
10
200
Credit Card
0.0010
0.0100
0.0010
adam
512
10000
200
Horse Colic
0.0500
0.0005
0.0005
adam
512
10000
200
Thyroid
11
0.0050
0.0100
0.0050
adam
512
10000
10
200
Spanbase
0.0100
0.0100
0.01000
200
Iris
0.0500
0.1000
0.0500
adam
512
10000
10
200
Balance Scale
11
0.0005
0.0050
0.0050
adam
$12
10000
200
Car
0.0100
0.01000
0.0500
512
10000
200
Glass
0.1000
0.0010
0.1000
adam
512
10000
10
200
Contraceptive
0.1000
Solar Flare
0.0001
0.0050
0.1000
adam
512
10000
10
200
Wine
11
0.0500
0.1000
adam
512
10000
200
Zoo
7
0.0100
0.0005
0.0010
adam
512
10000
10
200
Lymphography
0.0100
0.0005
0.0010
adan
512
10000
10
200
Segment
11
0.1000
0.0500
0.0500
adam
512
10000
200
Dermatology
0.0100
0.0100
0.0500
adam
512
10000
10
200
Landsat
0.0100
0.0100
0.0500
512
200
Annealing
0.0500
0.1000
0.0500
adam
512
10000
10
200
Splice
Table 8: GDT Hyperparameters
18

---

Under review as a conference paper at ICLR 2023
max, depth
max Features
impurity decrease
imparity
samples
min samples. split
cep ulpha
split
Blood Transfusion
5
eutropy
None
0.0
Nooc
10
0.0
Authentication
7
gini
None
0.0
Nooc
10
Titanic
3
entropy
None
0.0
None
Raisins
3
entropy
None
0.0
Noac
50
Rice
3
gini
None
0.0
None
0.0
Fchocardiogram
None
0.0
None
50
Wisconsin
Diagnostic Breast
None
0.0
None
50
50
0.0
Loan House
3
gini
None
0.0
Nonc
50
0.0
Heart Failure
None
0.0
None
Heaut Discase
gini
None
0.0
Noac
Adult
11
None
0.0
None
10
50
0.0
Marketing
eutropy
Nonc
0.0
Neac
Cervical Cancer
5
entropy
None
0.0
None
Congressional
Vesting
None
0.0
None
50
Absentecism
7
gini
Nene
0.0
Neue
10
0.0
Hepalitis
3
None
0.0
None
50
German
5
entropy
None
0.0
Nene
Mushroom
9
gini
None
0.0
None
0.0
Credit Card
5
entropy
None
0.0
None
50
Horse Colic
5
entropy
None
0.0
None
10
0.0
Thyroid
None
0.0
Nooc
10
0.0
Spamhase
entropy
Tris
3
None
0.
None
50
0.0
Balance Seale
gini
None
0.0
Noac
Car
entropy
None
0.0
None
Glass
gini
None
0.0
Nosc
0.0
Contraceptive
5
entropy
Solar Flare
9
gini
Nene
0.0
Neuc
0.0
Wine
5
None
0.0
None
Zoo
7
gini
None
0.0
Nene
Lymphography
9
entropy
None
0.0
None
0.0
Segment
entropy
None
0.0
None
Dermatology
7
entropy
None
0.0
None
0.0
Landsat
9
entropy
None
0.0
None
10
0.0
Annealing
gini
None
Splice
9
gini
None
0.0
Nouc
0.0
Table CART Hyperparameters
19

---

Under review as a conference paper at ICLR 2023
Dataset Name
n.thresholds
n.trees
iter
cross_prob
mutation.prob
Blood Transfusion
10
250
100
1.0
0.5
Banknote
10
50
500
0.4
0.9
Authentication
Titanic
10
500
0.6
0.8
Raisins
10
100
1.0
Rice
10
100
0.4
Echocardiegram
10
500
0.0
0.7
Wisconsin
Diagnostic Breast
10
250
500
0.4
0.3
Cancer
Loan House
10
100
500
1.0
0.5
Heart Failure
10
100
10
0.4
0.7
Heart Discase
10
500
250
1.0
0.0
Adult
10
250
100
0.2
0.7
Bank Marketing
10
50
50
0.4
0.1
Cervical Cancer
10
50
50
0.4
0.1
Congressional
0.4
0.1
Voting
Absenteeism
10
500
250
0.2
0.5
Hepatitis
10
100
100
0.2
0.8
German
10
500
250
0.2
0.9
Mushroom
10
500
250
0.8
0.6
Credit Card
10
50
10
0.6
0.8
Horse Colic
10
500
250
0.6
0.8
Thyroid
10
500
250
1.0
0.5
Spambuse
10
100
500
0.8
0.9
Iris
10
100
250
1.0
0.1
Balance Scale
10
250
500
0.8
0.4
Car
10
250
500
0.6
0.4
Glass
10
250
500
0.2
0.7
Contraceptive
10
250
250
0.4
0.2
Solar Flare
10
50
50
0.4
0.1
Wine
10
100
100
0.6
0,3
7oo
10
500
250
0.2
0.8
Lymphography
10
50
500
0.4
0.9
Segment
10
500
500
0.2
0.7
Dermatology
10
500
500
0.2
0.8
Landsat
10
50
250
0.2
0.8
Annealing
10
250
500
0.2
0.7
Splice
10
100
500
0.6
0.8
Table 10: GeneticTree Hyperparameters
20


Reviews:
[{"review_id": "hZf1kkCRpA", "reviewer": "Reviewer_zziu", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The paper presents a new approach for computing interpretable, axis-aligned decision trees using gradient descent by applying backpropagation with adjusted gradient flow on dense representation of decision trees. Experimental evaluation finds improvement over two baselines (CART, GeneticTree) in binary classification datasets and competitive performance on multi-class datasets.", "summary_of_the_review": "The paper presents an interesting approach for computing interpretable, axis-aligned decision trees using gradient descent. The main weaknesses are the missing highly-related literature, the limited novelty, and the limited performance gains.", "strength_and_weaknesses": "Strengths:\n* Interesting approach for computing interpretable, axis-aligned decision trees using gradient descent\n* Experimental evaluation show the computed trees outperform decision trees computed by baselines in several binary classification benchmarks and are obtain competitive results on multi-class benchmarks. \n\nWeaknesses:\n* The main weakness is that the paper is missing several highly-related works on gradient-based decision trees. Several recent examples are [1], [2], [3]. While they are not identical to the propose approach (e.g., some focus on ensemble models), they all deal with computing decision trees using gradient descent algorithms. In particular, these approaches have considered similar ideas such as representing cuts as (relaxed) one-hot encoding (e.g., using sparse softmax variants in [1] [2]), computing membership of sample in a leaf using multiplication of logistic-based split functions, etc. In particular, [2] presents approach for temperature annealing that gradually turns the splits to one-hot (i.e., axis-aligned). These papers should be cited and discussed, the similarities and differences should be highlighted, and the novelty should be demonstrated compared to these approach.\n* Baselines: The papers mentioned above (specifically the computing of decision trees in these papers) represent natural baselines that should be compared to in the experimental evaluation.\n* The approach demonstrates relatively modest performance gain is in binary classification and underperforms compared to CART on multi-class datasaets.\n\nMinor question: The Adult dataset has many categorical variables. How were they encoded?\n\n\n[1] Popov, Sergei, Stanislav Morozov, and Artem Babenko. \"Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data.\" International Conference on Learning Representations. 2019.\n\n[2] Chang, Chun-Hao, Rich Caruana, and Anna Goldenberg. \"NODE-GAM: Neural Generalized Additive Model for Interpretable Deep Learning.\" International Conference on Learning Representations. 2021.\n\n[3] Blanquero, Rafael, et al. \"Sparsity in optimal randomized classification trees.\" European Journal of Operational Research 284.1 (2020): 255-272.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KAmJ7uj6V7w", "reviewer": "Reviewer_Dpk7", "summary": "", "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": "", "summary_of_the_paper": "The paper proposes a novel training algorithm for axis-aligned decision trees based on gradient descent. The tree is represented via three vectors: the first one is responsible for storing indices of nodes' split features, the second one responds the split value, and the third one stores leaf values. These vectors are represented in a contiguous form (in particular, a probability distribution for each index value) which can be further used for joint gradient descent optimization. The experimental results demonstrate comparable quality for binary classification tasks. It is highly debatable whether it is reasonable to apply the proposed method to multiclass problems.", "summary_of_the_review": "I like the direction of the proposed method, most of the ideas are sound and interesting. However, and I think there is still much work to do.\n\n- The statement \"this is the first approach that attempts to learn univariate, axis-aligned decision trees with gradient descent\" is too loud since several papers are solving the same task.\n\n- The paper lacks theoretical justification. It would be interesting to see under what conditions one can find a global optimum and examples of synthetic data on which this method will work better than greedy construction. In particular, is this model capable of solving the \"xor problem\"? I lacked intuition about what the solution to the optimization problem converges to before applying hardmax, and this aspect could be discussed more. For example, it seems that if GDT is used for a regression problem with MSE loss, then the solution should converge to hard splits (but not necessarily optimal) with mean values in the leaves. \n\n- I do not fully understand the trick described by Equation 7. Can it be interpreted as \"we do not care about soft and contiguous nature of \\iota and S during training but apply hard max at the end\"? If so, I do not see any problems with it; it could be written explicitly for more clarity.\n\n- The choice of baseline algorithms is not clear. Why were Evolutionary Decision Trees used but not some other differentiable trees? Results show that it is quite a weak baseline, even compared to classic CART trees.\n\n- The experimental part would be more solid if it consisted of examples of surfaces found by greedy tree and GDT and the plot demonstrating quality vs cardinality dependence.\n\n- I do not understand why potentially more expressive GDT is less prone to overfitting and, at the same time, has comparable or even lower quality. It can be due to the validation set used for GDT training. Other algorithms do not use them, but many pruning techniques could make them more robust, and at the same time, reducing the train set may be crucial for your model (especially with small datasets).\n\n* Questions\n\n- Unfortunately, the results are not so good for some datasets. What can you state about the limitations of applying the proposed method to real-world problems (how to decide whether to use it or not)?\n\n- Experience shows that using more expressive trees in ensembles (such as GBDT, for example) can lead to a decrease in the quality of such models due to overfitting on the level of individual trees. Have you tried using GDT in ensembles? Does it make sense, especially in the context of much longer training time?", "strength_and_weaknesses": "+ Interesting direction and ideas\n\n- Much work to do, the profit is questionable. According to Tavle 1, the proposed method does not outperform classical baseline CART. This is not consistent whit the claims in Introduction. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9KWNK4Sv69", "reviewer": "Reviewer_ePjz", "summary": "", "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": "", "summary_of_the_paper": "The paper proposes a method for learning fully-grown binary decision trees with axis-aligned splits by gradient descent.\nFor that, it first describes a formulation for determining a point route through the tree (based on an integer formulation of logical-ands and logical-ors) given the set of decision splits, and its output. The splits are parametrized by an index vector (that selects the features to evaluate at each branch node) and a threshold vector (that determines whether the point should go left or right), and the leaf nodes are each associated by a probability distribution over possible outputs.\n\nThen, the paper describes how to optimize the tree parameters. As the overall decision function is piece-wise constant, the authors make use of the straight-through operator to update the discrete parameters by gradient descent. \nAn empirical analysis assesses how the proposed method compares with CART and a genetic tree search method in terms of test accuracies, generalization gap, running times, prediction confidence, robustness to hyper-parameter changes.", "summary_of_the_review": "Overall the paper proposes a novel formulation for learning fully-grown axis-aligned decision trees. The presentation should be improved, starting from better placing the work within the relevant literature, providing a thorough discussion of the benefits of learning axis-aligned splits and including (at least) an optimal tree baseline in the empirical comparison. Also the misleading claim of page 2 (see Weaknesses) should be rectified. I would be happy to increase my score accordingly.\n\n**update after rebuttal**\nThe authors thoroughly revised the paper based on the feedback, and for this I raised my score.\n\nThe only remaining issue from my side is the motivation for learning axis-aligned split functions and for restricting the empirical comparison only to this type of trees. The interpretability of the learned trees (which is used to justify axis-aligned functions) should have been analyzed, for instance by comparing the number of decision functions needed by each method to achieve similar accuracies. Without such analysis, it is not clear why a practitioner would prefer this new method to existing ones, in particular as it learns only fully-grown trees.\n\n", "strength_and_weaknesses": "## Strengths\n\nThe formulation and method are described in great level of detail. The contributions are clearly stated from the beginning and the empirical analysis studies several aspects of the method's performance. Of particular interest is the study of the performance of all methods using the default values for the hyper-parameters, which shows that all studied methods are quite robust to non-optimal choices of hyper-parameters.\n\nTo the best of my knowledge, the proposed formulation of tree routing is novel. It is also easier to read and understand than those of existing methods, in particular of the cited work by [Bertsimas and Dunn, 2017] and of [3], and more practical, as it does not require constraints reflecting the hierarchy of the tree. \n\n\n## Weaknesses\n1. **The motivation for learning axis-aligned splits (as opposed to oblique) is weak**. In the paper it is said that axis-aligned trees are more interpretable than oblique ones. However one could argue that learning oblique splits allow to obtain trees shallower than with axis-aligned ones, hence with fewer decision rules. For this, trees with oblique splits could be easier to read and to interpret. Moreover, the proposed approach learns fully-grown trees, which are considered less interpretable than sparse ones (e.g., see discussion in [5]).\n\nIt would be valuable to develop this discussion in the paper, especially because:\n- the argument that axis-aligned trees are more interpretable is used to justify the choice of restricting the empirical comparison only to axis-aligned tree baselines;\n- the actual interpretability of the learned trees is not studied in the paper.\n\n 2. **The work should be better placed within the relevant literature**. \n\n- Some references are missing from the literature on optimal decision trees and the one on soft-trees, e.g. [2], [3], [4]. In particular, [3] also optimizes deterministic tree routings by gradient descent, hence it is possibly the closest related work. It would be valuable to discuss the differences between the two methods' formulations (e.g., see \"Strengths\") and of optimization choices (e.g., in which operations the biases are introduced, output nature, loss options). The current work could also take inspiration from the pruning procedure of [3] for extending the method to learning of sparse trees.\n\n- Several times in the main text the optimization procedure is described as \"an adjusted gradient flow\". However,  the updates are discrete so it is not clear why the procedure is described as a \"flow\". Also, the term \"straight-through operator\" should be preferred over \"adjusted\" because it is more specific and references the rich literature that leverages it, starting from the seminal work [1] that should be cited in the paper. Finally, it should be highlighted in the paper that the \"straight-through operator\" introduces a mismatch between forward and backward passes, hence the **claim that \"GDTs directly optimize the loss function\" (page 2) is not technically true**.\n\n- In page 6 an algorithm for performing gradient descent with momentum is mentioned but its name or reference is not provided.\n\n- The paper should be self-contained. However in Section 4 the results of four experiments are commented in the main text but reported in the appendix. I suggest to choose the most significant experiment to report and comment in the main text, and defer the remaining in the appendix. To gain some space, Sections 3.3 and 3.4 could be considerably compacted (e.g., Eq 7 and 8 are not needed once the term straight-through operator is used).\n\n3. To judge the potential impact of the method, the performance of existing differentiable tree learning methods and, when feasible, of optimal tree learning methods should be reported as well. The current empirical evaluation reports the results of baselines that are not always state-of-the-art in terms of accuracy, and it would be valuable to check whether the proposed method improve over the running times of these lines of works, even though it does not over greedy approaches.\n\n## Minors\n- page 3: $d$ is not defined\n\n[1] Yoshua Bengio, Nicholas Léonard, Aaron C. Courville: Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation, 2013\n\n[2] Ryutaro Tanno, Kai Arulkumaran, Daniel C. Alexander, Antonio Criminisi, Aditya V. Nori: Adaptive Neural Trees. ICML 2019\n\n[3] Valentina Zantedeschi, Matt J. Kusner, Vlad Niculae: Learning Binary Decision Trees by Argmin Differentiation. ICML 2021\n\n[4] Emir Demirovic, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, Peter J. Stuckey: MurTree: Optimal Decision Trees via Dynamic Programming and Search. J. Mach. Learn. Res., 2022.\n\n[5] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, Chudi Zhong: Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges, Statistics Surveys, 2022\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4oNHE4ePrv", "reviewer": "Reviewer_tioQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "The paper proposes a method for constructing decision tree classifiers that does not rely on performing greedy splits. Instead, the method constructs a soft decision tree approximation to conventional hard split axis-aligned decision trees, and then trains this soft tree with backpropagation and gradient-based optimisation algorithms. The performance of the algorithm is compared with conventional CART trees and an evolutionary optimisation induction algorithm on a variety of small tabular datasets. The proposed method had comparable performance with CART.", "summary_of_the_review": "Given the lack of acknowledgement and comparison with very related prior work, missing baselines, and minimally informative experimental results, I cannot recommend acceptance. I would also argue that since there is no representation learning in this paper, that ICLR is perhaps the wrong venue.", "strength_and_weaknesses": "### Strengths\n* Investigating alternatives to greedy splitting for constructing decision trees is an interesting problem, and the paper does a good job of highlighting why this is the case by including an example of where greedy splitting is not optimal.\n* The method is quite simple and the description is relatively easy to follow.\n\n## Weaknesses\n* This paper is not the first to use gradient-based optimisation for axis-aligned decision tree induction. For example, see work by Gouk et al. (2019), Yang et al. (2018), and Suarez and Lutsko (1999). The paper should include a more thorough discussion of relevant related work.\n* The authors assume that gradient descent performs global optimisation, but this is in general only true for some classes of functions. The authors should demonstrate that their decision tree representation belongs to one of these function classes if they want to make that claim.\n* Experimental results are quite limited. A comparison should be performed with more recent prior work (e.g., those listed above), and a neural network baseline should also be included. It would also be interesting if the paper included experiments on something beyond just classification accuracy on UCI-style tabular datasets; e.g., investigation of performance on regression datasets, or other tasks where the ability to specify an arbitrary loss function would be useful. The authors may also consider evaluating how well these decision trees are able to leverage standard ensembling techniques---something that standard decision trees are excellent candidates for.\n\n1. Gouk et al. Stochastic Gradient Trees. Asian Conference on Machine Learning, 2019.\n2. Yang et al. Deep Neural Decision Trees. ICML Workshop on Human Interpretability in Machine Learning, 2018.\n3. Suarez and Lutsko. Globally Optimal Fuzzy Decision Trees for Classificaiton and Regression. IEEE TPAMI, 1999.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject