# Learning Decision Trees with Gradient Descent

Sascha Marton
Institute for Enterprise Systems
University of Mannheim
<EMAIL_ADDRESS>
&Stefan Lüdtke
ScaDS.AI
University of Leipzig
<EMAIL_ADDRESS>
&Christian Bartelt
Institute for Enterprise Systems
University of Mannheim
<EMAIL_ADDRESS>
&Heiner Stuckenschmidt
Data and Web Science Group
University of Mannheim
<EMAIL_ADDRESS>

###### Abstract

Decision Trees (DTs) are commonly used for many machine learning tasks due to
their high degree of interpretability. However, learning a DT from data is a
difficult optimization problem, as it is non-convex and non-differentiable.
Therefore, common approaches learn DTs using a greedy growth algorithm that
minimizes the impurity locally at each internal node. Unfortunately, this
greedy procedure can lead to suboptimal trees. In this paper, we present a
novel approach for learning hard, axis-aligned DTs with gradient descent. The
proposed method uses backpropagation with a straight-through operator on a
dense DT representation to jointly optimize all tree parameters. Our approach
outperforms existing methods on binary classification benchmarks and achieves
competitive results for multi-class tasks.

##  1 Introduction

Decision trees (DTs) are one of the most popular machine learning models and
are still frequently used today. In particular, with the growing interest in
explainable artificial intelligence (XAI), DTs have regained popularity due to
their interpretability. 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 an NP-complete problem [19]. Therefore, the common
approach to construct a DT based on data is a greedy procedure that minimizes
the impurity at each internal node [8]. The algorithms that are still used
today, such as CART [8] and C4.5 [34], were developed in the 1980s and have
remained largely unchanged since then. Unfortunately, a greedy algorithm only
yields to locally optimal solutions and therefore can lead to suboptimal
trees, as we illustrate in the following:

(a) Greedy DT (CART)

(b) Gradient-Based DT (GDT)

Figure 1: Greedy versus Gradient-Based DT. Two DTs learned on the
Echocardiogram dataset. While the CART DT (left) only makes locally optimal
splits, the GDT (right) performs a joint optimization of all parameters, which
results in a significantly higher performance.

_Example 1_ The Echocardiogram dataset [11] deals with predicting one-year
survival of patients after a heart attack based on tabular data from an
echocardiogram. Figure 1 shows two DTs. The left tree is learned by a greedy
algorithm (CART) and the right tree is learned with our gradient-based
approach. We can observe that the greedy procedure leads to a suboptimal tree
with a significantly lower performance. Splitting on the _wall-motion-score_
is the locally optimal split (see Figure 1(a)), but globally, it is beneficial
to split based on the _wall-motion-score_ with different values conditioned on
the _pericarcial-effusion_ in the second level (Figure 1(b)).

In this paper, we propose a novel approach for learning hard, axis-aligned DTs
based on a joint optimization of all tree parameters with gradient descent,
which we call gradient-based decision trees (GDTs). Using a gradient-based
optimization, we can overcome the limitations of greedy approaches, as
indicated in Figure 1(b). Specifically, our contributions are:

  * •

We introduce a dense DT representation that enables a gradient-based
optimization of all tree parameters (Section 3.2).

  * •

We present a procedure to deal with the non-differentiable nature of DTs using
backpropagation with a straight-through operator (Section 3.3).

  * •

We propose a novel tree routing that allows an efficient, parallel
optimization of all tree parameters with gradient descent (Section 3.4).

We empirically evaluate GDTs on several real-world benchmark datasets (Section
4). GDTs outperform existing approaches and a greedy DT induction for binary
classification tasks and achieve competitive results on multi-class datasets.
On several benchmark datasets, the performance difference between GDTs and
other methods is substantial. Furthermore, GDTs are less prone to overfitting.
A gradient-based optimization method as used in GDTs also provides more
flexibility, since splits can be adjusted during training, and custom loss
functions can be easily incorporated.

##  2 Related Work

Greedy DT Algorithms The most prominent and still frequently used algorithms,
namely CART [8] and C4.5 [34] as an extension of ID3.0 [33], 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 [18] and
GUIDE [23, 24]. However, until today, none of these algorithms was able to
consistently outperform CART and C4.5 as shown for instance by Zharmagambetov
et al. [40].

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 [35]. However, Murthy [27] argue that those methods not only
suffer from an enormous increase in computational complexity, but also suffer
from pathology, i.e., they frequently produce worse trees in terms of
accuracy, tree size and depth. One explanation is that lookahead trees,
especially without regularization, are prone to overfitting.

Optimal DTs Optimal DTs try to optimize an objective (e.g., the purity) using
approximate brute force search to find a globally optimal tree with a certain
specification [40]. OCT [6] defines the optimization as a mixed integer
optimization (MIO) problem which is solved using a MIO solver. DL8.5 [3] and
GOSDT [21] approximate a brute force search using a branch-and-bound algorithm
to remove irrelevant parts from the search space. MurTree [10] further uses
dynamic programming, which reduces the runtime significantly. However, state-
of-the-art approaches still require binary data and therefore a discretization
of continuous features [6, 3, 10] which can lead to information loss.

Genetic DTs Another way to learn DTs in a non-greedy fashion is using
evolutionary algorithms. Evolutionary algorithms perform a robust global
search in the space of candidate solutions based on the concept of survival of
the fittest [4]. This usually results in a better identification of feature
interactions compared to a greedy, local search [12].

Oblique DTs In contrast to vanilla DTs that make hard decision at each
internal node, many approaches to hierarchical mixture of expert models [16]
have been proposed. They usually make soft splits, where each branch is
associated with a probability [14, 13]. Further, the models do not comprise
univariate, axis-aligned splits, but are oblique with respect to the axis.
These adjustments to the tree architecture allow the application of further
optimization algorithms, including gradient descent [14, 13]. Blanquero et al.
[7] try to increase the interpretability of oblique trees by optimizing for
sparsity using fewer variables at each split and simultaneously fewer splits
in the whole tree. Tanno et al. [36] combine the benefits of neural networks
and DTs using so-called adaptive neural trees (ANTs) allowing a gradient-based
end-to-end optimization. They employ a stochastic routing based on a Bernoulli
distribution where the mean is a learned parameter. Furthermore, ANTs utilize
non-linear transformer modules at the edges, making the resulting trees
oblique. Norouzi et al. [28] proposed an approach for efficient non-greedy
optimization of DTs that overcomes the need of soft decisions to apply
gradient-based algorithms. They perform a joint optimization of all split
functions and leaf parameters by minimizing a convex-concave upper bound on
the tree’s empirical loss. While this allows the use of hard splits, the
approach is still limited to oblique trees. Zantedeschi et al. [39] use argmin
differentiation to simultaneously learn all tree parameters by relaxing a
mixed-integer program for discrete parameters to allow a gradient-based
optimization. This allows a deterministic tree routing which is similar to
GDTs. However, they require a differentiable splitting function (e.g., a
linear split function which results in oblique trees). In contrast to oblique
DTs, GDTs make hard, axis-aligned splits that only consider a single feature
at each split, which provides a significantly higher interpretability,
especially at a split-level. This is supported by Molnar [26] where the
authors argue that humans cannot comprehend explanations involving more than
three dimensions at once.

Deep Neural Decision Trees (DNDTs) Yang et al. [37] propose DNDTs which
realize tree models as neural networks, utilizing a soft binning function for
splitting. Therefore, the resulting trees are soft, 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 classes (and the number of bins). As the authors
discussed, this results in poor scalability w.r.t. the number of features,
which currently can only be solved by using random forests for high-
dimensional datasets ($>12$ features). Our approach, in contrast, scales
linearly with the number of features, making it efficiently applicable for
high-dimensional datasets. Furthermore, using the Kronecker product to build
the tree prevents splitting on the same feature with different thresholds in
the same path. For GDTs, not only the split threshold, but also the split
index is a learned parameter which inherently allows splitting on the same
feature multiple times.

##  3 Gradient-Based Axis-Aligned Decision Trees

In this section, we propose gradient-based decision trees (GDTs) as a novel
approach to learn DTs. We introduce a new DT representation and a
corresponding algorithm that allows learning hard, axis-aligned DTs with
gradient descent. More specifically, we will use backpropagation with a
straight-through (ST) operator (Section 3.3) on a dense DT representation
(Section 3.2) to adjust the model parameters during the training. Furthermore,
our novel tree routing (Section 3.4) allows an efficient optimization of all
parameters over a complete batch with a single set of matrix operations.

###  3.1 Arithmetic Decision Tree Formulation

In the following, we will introduce a notation for DTs 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 is
necessary for the gradient-based learning in Sections 3.2-3.4. Note that our
notation and training procedure requires balanced DTs. As this in only
required during training, we simply apply a basic post-hoc pruning to reduce
the tree size for the application.

The parameters of a DT of depth $d$ comprise one split threshold and one
feature index for each internal node, which we denote as vectors
$\boldsymbol{\tau}\in\mathbb{R}^{2^{d}-1}$ and
$\boldsymbol{\iota}\in\mathbb{N}^{2^{d}-1}$ respectively, where $2^{d}-1$
equals the number of internal nodes in a balanced DT.Additionally, each leaf
node comprises a class membership in the case of a classification task, which
we denote as the vector $\boldsymbol{\lambda}\in\mathcal{C}^{2^{d}}$, where
$\mathcal{C}$ is the set of classes and $2^{d}$ equals the number of leaf
nodes in a balanced DT.Figure 2 shows our tree representation in comparison to
a common tree representation for an exemplary DT.

(a) Vanilla DT Representation

(b) Adjusted DT Representation

Figure 2: DT Representations. Exemplary DT representations with depth $2$ for
a dataset comprising $3$ variables and $2$ classes. The DT at the right can be
represented using the vectors $\boldsymbol{\iota}=[0,2,1]$,
$\boldsymbol{\tau}=[2.0,-1.2,0.9]$ and $\boldsymbol{\lambda}=[0,0,0,1]$.

Formally, we can express a DT as a function
$DT(\cdot|\boldsymbol{\tau},\boldsymbol{\iota},\boldsymbol{\lambda}):\mathbb{R}^{n}\rightarrow\mathcal{C}$
with respect to its parameters:

$DT(\boldsymbol{x}|\boldsymbol{\tau},\boldsymbol{\iota},\boldsymbol{\lambda})=\sum_{l=0}^{2^{d}-1}\lambda_{l}\,\mathbb{L}(\boldsymbol{x}|l,\boldsymbol{\tau},\boldsymbol{\iota})$
(1)

Here, $\mathbb{L}$ is a function that indicates whether a sample
$\boldsymbol{x}\in\mathbb{R}^{n}$ belongs to a leaf $l$. It can be defined as
a multiplication of the split functions of the preceding internal nodes.

We define a split function $\mathbb{S}$ as a Heaviside step function defined
as

$\mathbb{S}_{\text{Heaviside}}(\boldsymbol{x}|\iota,\tau)=\begin{cases}1,\text{if
}x_{\iota}\geq\tau\\\ 0,\text{otherwise}\end{cases}$ (2)

where $\iota$ is the index of the feature considered at a certain split and
$\tau$ is the corresponding split threshold.

Enumerating the internal nodes of a balanced tree with depth $d$ in a breadth-
first order, we can now define the indicator function $\mathbb{L}$ for a leaf
$l$ as follows:

$\mathbb{L}(\boldsymbol{x}|l,\boldsymbol{\tau},\boldsymbol{\iota})=\prod^{d}_{j=1}\left(1-\mathfrak{p}(l,j)\right)\,\mathbb{S}(\boldsymbol{x}|\tau_{\mathfrak{i}(l,j)},\iota_{\mathfrak{i}(l,j)})+\mathfrak{p}(l,j)\,\left(1-\mathbb{S}(\boldsymbol{x}|\tau_{\mathfrak{i}(l,j)},\iota_{\mathfrak{i}(l,j)})\right)$
(3)

Here, $\mathfrak{i}$ is the index of the internal node preceding a specific
leaf node $l$ at a certain depth $j$ and can be calculated as

$\mathfrak{i}(l,j)=2^{j-1}+\left\lfloor\frac{l}{2^{d-(j-1)}}\right\rfloor-1$
(4)

Further, $\mathfrak{p}$ defines whether the left branch ($\mathfrak{p}=0$) or
the right branch ($\mathfrak{p}=1$) was taken at the internal node preceding a
leaf node $l$ at a certain depth $j$ . We can calculate $\mathfrak{p}$ as

$\mathfrak{p}(l,j)=\left\lfloor\frac{l}{2^{d-j}}\right\rfloor\bmod 2$ (5)

As becomes evident, DTs involve non-differentiable operations in terms of the
split function including the split feature selection (Equation 2), which
precludes the application of backpropagation 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 $\iota$ for the split feature selection is defined as
$\iota\in\mathbb{N}$. However, the index $\iota$ is a parameter of the DT and
a standard optimization with gradient descent requires $\iota\in\mathbb{R}$.

  * C2

The split function $\mathbb{S}(\boldsymbol{x}|\iota,\tau)$ is a Heaviside step
function with an undefined gradient for $x_{\iota}=\tau$ and $0$ gradient
elsewhere, which precludes an efficient optimization.

  * C3

The leafs in a vanilla DT comprise only the class membership as
$\lambda\in\mathcal{C}$. To optimize the leaf parameters, we need
$\lambda\in\mathbb{R}$ to apply gradient descent and calculate an informative
loss.

The calculation of the internal node index $\mathfrak{i}$ and path position
$\mathfrak{p}$ also involve non-differentiable operations. However, since we
only focus on balanced trees, the resulting values are constant and can be
calculated upfront and independent of the optimization.

###  3.2 Dense Decision Tree Representation

In this subsection, we propose a differentiable representation of the feature
indices $\boldsymbol{\iota}$ to allow a gradient-based optimization, which is
visualized in Figure 3. Therefore, we extend the vector
$\boldsymbol{\iota}\in\mathbb{R}^{2^{d}-1}$ to a matrix
$I\in\mathbb{R}^{2^{d}-1}\times\mathbb{R}^{n}$. This is achieved by one-hot
encoding the feature index as $\boldsymbol{\iota}\in\mathbb{R}^{n}$ for each
internal node. This adjustment is necessary for the optimization process to
account for the fact that feature indices are categorical instead of ordinal.

We further propose using a similar representation for the split thresholds as
$T\in\mathbb{R}^{2^{d}-1}\times\mathbb{R}^{n}$ by storing one value for each
feature as $\boldsymbol{\tau}\in\mathbb{R}^{n}$ instead of a single value for
all features. 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 et al. [25] used for predicting
a DT as a numeric output of a neural network. Further, our matrix
representation for the feature selection is similar to the one proposed by
Popov et al. [31] but does additionally include a 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.
Therefore, we reformulate the Heaviside split function in Equation 2 as
follows:

$\displaystyle\mathbb{S}_{\text{logistic}}(\boldsymbol{x}|\boldsymbol{\iota},\boldsymbol{\tau})=S\left(\sum_{i=0}^{n}\iota_{i}x_{i}-\sum_{i=0}^{n}\iota_{i}\tau_{i}\right)$
(6)
$\displaystyle\mathbb{S}_{\text{logistic\\_hard}}(\boldsymbol{x}|\boldsymbol{\iota},\boldsymbol{\tau})=\left\lfloor\mathbb{S}_{\text{logistic}}(\boldsymbol{x}|\boldsymbol{\iota},\boldsymbol{\tau})\right\rceil$
(7)

where $S(x)=\frac{1}{1+e^{-x}}$ is the logistic function and
$\lfloor\cdot\rceil$ stands for rounding to the closest integer. For our case,
where $\boldsymbol{\iota}$ is one-hot encoded,
$\mathbb{S}_{\text{logistic\\_hard}}(\boldsymbol{x}|\boldsymbol{\iota},\boldsymbol{\tau})=\mathbb{S}_{\text{Heaviside}}(\boldsymbol{x}|\iota,\tau)$
holds.

(a) Vanilla DT Representation

(b) Dense DT Representation

Figure 3: Standard vs. Dense DT Representation. Exemplary DT representations
with depth $2$ for a dataset comprising $3$ variables and $2$ classes. Here,
$\mathbb{S}_{\text{lh}}$ stands for $\mathbb{S}_{\text{logistic\\_hard}}$
(Equation 7).

###  3.3 Backpropagation of Decision Tree Loss

While the dense DT representation introduced in the previous section
emphasizes an efficient learning of axis-aligned DTs, it does not solve C1-C3.
Therefore, in this subsection, we will explain how we solve those challenges
by using a ST operator during backpropagation.

For the function value calculation in the forward pass, we need to assure that
$\boldsymbol{\iota}$ is a one-hot encoded vector. This can be achieved by
applying a hardmax function on the feature index vector for each internal
node. However, applying a hardmax is a non-differentiable operation, which
precludes gradient computation. To overcome this issue, we use the ST operator
[5]: 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 $\boldsymbol{\iota}$. Accordingly, we can optimize the parameters of
$\boldsymbol{\iota}$ where $\boldsymbol{\iota}\in\mathbb{R}$ while still using
axis-aligned splits during training (C1). However, this procedure introduces a
mismatch between the forward and backward pass. To reduce this mismatch, we
additionally perform an entmax transformation [30] to generate a sparse
distribution over $\boldsymbol{\iota}$ before applying the hardmax.

Similarly, we use the ST operator to assure hard splits (Equation 7) by
excluding $\lfloor\cdot\rceil$ for the backward pass (C2). Using the sigmoid
logistic function before applying the ST operator (see Equation 6) utilizes
the distance to the split threshold as additional information for the gradient
calculation. If the feature considered at an internal node is close to the
split threshold for a specific sample, this will result in smaller gradients
compared to a sample that is more distant.

Furthermore, we need to adjust the leaf nodes of the DT to allow an efficient
loss calculation (C3). Vanilla DTs comprise the predicted class for each leaf
node and are functions $DT:\mathbb{R}^{n}\rightarrow\mathcal{C}$. We use a
probability distribution at each leaf node and therefore define DTs as a
function $DT:\mathbb{R}^{n}\rightarrow\mathbb{R}^{c}$ where $c$ is the number
of classes. Accordingly, the parameters of the leaf nodes are defined as
$L\in\mathbb{R}^{2^{n}}\times\mathbb{R}^{c}$ for the whole tree and
$\boldsymbol{\lambda}\in\mathbb{R}^{c}$ for a specific leaf node. This
adjustment allows the application of standard loss functions. For
classification tasks, we use a cross-entropy loss including a focal factor
[22] (see Appendix D for further details).

###  3.4 Deterministic Tree Routing and Training Procedure

In the previous subsections, we introduced the adjustments that are necessary
to apply gradient descent to decision trees. During the optimization, we
calculate the gradients with backpropagation implemented using automatic
differentiation based on the computation graph of the tree pass function. The
tree pass function to calculate the function values is summarized in Algorithm
1 and utilizes the adjustments introduced in the previous sections. Our tree
routing allows calculating the tree pass function over a complete batch as a
single set of matrix operations, which allows an efficient computation. We
also want to note that our dense representation can be converted into an
equivalent vanilla DT representation at each point in time. Similarly, the
balanced nature of GDTs is only required during the gradient-based
optimization and standard pruning techniques to reduce the tree size are
applied post-hoc.

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 [17] with weight averaging
[15] (further details can be found in the Appendix A). Moreover, we implement
early stopping and random restarts to avoid bad initial parametrizations,
where the best parameters are selected based on the validation loss.

Algorithm 1 Tree Pass Function

1:function pass($I,T,L,\boldsymbol{x}$)

2: $I\leftarrow\text{entmax}(I)$ $\triangleright$ ST operator

3: $c^{*}_{1}\leftarrow I_{i}-\text{hardmax}(I_{i})$

4: $I\leftarrow I-c^{*}_{1}$

5: $\hat{\boldsymbol{y}}\leftarrow{[0]}^{c}$

6: for $l=0,\dots,2^{d}-1$ do

7: $p\leftarrow 1$

8: for $j=1,\dots,d$ do

9: $\mathfrak{i}\leftarrow
2^{j-1}+\left\lfloor\frac{l}{2^{d-(j-1)}}\right\rfloor-1$ $\triangleright$
Equation 4

10: $\mathfrak{p}\leftarrow\left\lfloor\frac{l}{2^{d-j}}\right\rfloor\bmod 2$
$\triangleright$ Equation 5

11: $s\leftarrow
S\left(\sum\limits^{n}_{i=0}T_{\mathfrak{i},i}\,I_{\mathfrak{i},i}-\sum\limits^{n}_{i=0}x_{i}\,I_{\mathfrak{i},i}\right)$
$\triangleright$ Equation 6

12: $c^{*}_{2}=s-\lfloor s\rceil$ $\triangleright$ ST operator

13: $s\leftarrow s-c^{*}_{2}$

14: $p\leftarrow p\,\left((1-\mathfrak{p})\,s+\mathfrak{p}\,(1-s)\right)$
$\triangleright$ Equation 3

15: end for

16: $\hat{\boldsymbol{y}}\leftarrow\hat{\boldsymbol{y}}+L_{l}\,p$
$\triangleright$ Equation 1

17: end for

18: return $\sigma\left(\hat{\boldsymbol{y}}\right)$ $\triangleright$ Apply
softmax function $\sigma$ to get predicted probability distribution

19:end function

##  4 Experimental Evaluation

The following experiments aim to evaluate the predictive capability of GDTs
against existing methods.

###  4.1 Experimental Setup

Datasets and Preprocessing The experiments were conducted on several benchmark
datasets, mainly from the UCI Machine Learning repository [11]. For all
datasets, we performed a standard preprocessing: We applied leave-one-out
encoding to all categorical features.Similar to Popov et al. [31], we further
perform a quantile transform, making each feature follow a normal
distribution. We use a random $80\%/20\%$ train-test split for all datasets.
To account for class imbalance, we rebalanced datasets using SMOTE [9] if the
minority class accounts for less than $\frac{25}{c-1}\%$ of the data points,
where $c$ is the number of classes. For GDTs and DNDTs we use $20\%$ of the
training data as validation data for early stopping. As DL8.5 requires binary
features, we discretized all numeric features using quantile binning with $5$
bins and one-hot encoded all categorical features. Further information on the
datasets along with the data sources can be found in the Appendix B.

Methods We focus on hard, axis-aligned DTs and compare GDTs to the following
methods:

  * •

CART: We use the sklearn [29] implementation, which uses an optimized version
of the CART algorithm. While CART usually only uses Gini as impurity measure,
we also allow information gain/entropy as an option during our hyperparameter
optimization. Since this is also the relevant difference between CART and
C4.5, we decided to only use optimized CART, which is also the stronger
benchmark.

  * •

Evolutionary DTs: We use GeneticTree [32] which implements an efficient
learning of DTs with a genetic algorithm.

  * •

DNDT [37]: We use the official DNDT implementation [38]. For a fair
comparison, we enforce binary trees by setting the number of cut points to
$1$. Furthermore, since DNDTs are soft during the training, we enforced hard
splits during inference to ensure comparability.Due to scalability issues,
DNDTs were only applied to datasets with a maximum of $12$ features, as
suggested by Yang et al. [37].

  * •

DL8.5 [3]: We use the official DL8.5 implementation [2] for learning optimal
DTs including improvements from MurTree [10] which reduces the runtime
significantly.

GDTs are implemented in Python using TensorFlow [1]111The code of our
implementation is available under
https://github.com/s-marton/GradientBasedDecisionTrees.. For GDTs, we further
applied a simple post-hoc pruning to remove all branches with zero samples
based on one pass of the training data.

Hyperparameter Optimization To select the optimal hyperparameters, we
conducted a random search with cross-validation. The complete list of relevant
hyperparameters for each approach along with additional details on the
selection can be found in the Appendix D.

###  4.2 Results

GDTs are competitive to existing DT learners  First, we evaluated the
performance of GDTs against existing approaches on the benchmark datasets in
terms of the macro F1-Score, which also accounts for class imbalance (Table
1). We note the mean and mean reciprocal rank (MRR), similar to Yang et al.
[37]. Overall, GDTs outperformed existing approaches for binary classification
tasks (best MRR of $0.771$) and achieved competitive results for multi-class
tasks (second-best MRR of $0.619$). More specifically, GDTs outperformed
state-of-the-art non-greedy DT approaches for both, binary and multi-class
tasks. In addition, GDTs outperformed DNDTs on $12$ out of $16$ datasets,
making it the substantially better gradient-based approach. For binary
classification tasks, GDTs demonstrated superior performance over CART,
achieving the best performance on $13$ datasets as compared to only $6$
datasets for CART. Notably, the performance difference between GDTs and
existing methods was substantial for several datasets, as for instance on
_Echocardiogram_ , _Heart Disease_ and _Absenteeism_.

For multi-class datasets, GDTs only achieved the second-best overall
performance. Especially for high-dimensional datasets with a high number of
classes, CART achieved the highest performance. This result can be explained
by the dense DT representation required for the gradient-based optimization.
Using our representation, the difficulty of the optimization task increases
with the number of features (more parameters at each internal node) and the
number of classes (more parameters at each leaf node). Therefore, in future
work, we aim to optimize the proposed dense representation, e.g., by using
parameter sharing techniques.

Table 1: Performance Comparison. We report macro F1-scores (mean $\pm$ stdev
over $10$ trials). We also report the rank of each approach in brackets. The
datasets are sorted by the number of features. The top part comprises binary
classification tasks and the bottom part multi-class datasets.

| Gradient-Based | Non-Greedy | Greedy
---|---|---|---
| GDT (ours) | DNDT | GeneticTree | DL8.5 | CART
Blood Transfusion | 0.628 $\pm$ 0.036 (1) | 0.543 $\pm$ 0.051 (5) | 0.575 $\pm$ 0.094 (4) | 0.590 $\pm$ 0.034 (3) | 0.613 $\pm$ 0.044 (2)
Banknote Authentication | 0.987 $\pm$ 0.007 (1) | 0.888 $\pm$ 0.013 (5) | 0.922 $\pm$ 0.021 (4) | 0.962 $\pm$ 0.011 (3) | 0.982 $\pm$ 0.007 (2)
Titanic | 0.776 $\pm$ 0.025 (1) | 0.726 $\pm$ 0.049 (5) | 0.730 $\pm$ 0.074 (4) | 0.754 $\pm$ 0.031 (2) | 0.738 $\pm$ 0.057 (3)
Raisins | 0.840 $\pm$ 0.022 (4) | 0.821 $\pm$ 0.033 (5) | 0.857 $\pm$ 0.021 (1) | 0.849 $\pm$ 0.027 (3) | 0.852 $\pm$ 0.017 (2)
Rice | 0.926 $\pm$ 0.007 (3) | 0.919 $\pm$ 0.012 (5) | 0.927 $\pm$ 0.005 (2) | 0.925 $\pm$ 0.008 (4) | 0.927 $\pm$ 0.006 (1)
Echocardiogram | 0.658 $\pm$ 0.113 (1) | 0.622 $\pm$ 0.114 (3) | 0.628 $\pm$ 0.105 (2) | 0.609 $\pm$ 0.112 (4) | 0.555 $\pm$ 0.111 (5)
Wisconcin Breast Cancer | 0.904 $\pm$ 0.022 (2) | 0.913 $\pm$ 0.032 (1) | 0.892 $\pm$ 0.028 (4) | 0.896 $\pm$ 0.021 (3) | 0.886 $\pm$ 0.025 (5)
Loan House | 0.714 $\pm$ 0.041 (1) | 0.694 $\pm$ 0.036 (2) | 0.451 $\pm$ 0.086 (5) | 0.607 $\pm$ 0.045 (4) | 0.662 $\pm$ 0.034 (3)
Heart Failure | 0.750 $\pm$ 0.070 (3) | 0.754 $\pm$ 0.062 (2) | 0.748 $\pm$ 0.068 (4) | 0.692 $\pm$ 0.062 (5) | 0.775 $\pm$ 0.054 (1)
Heart Disease | 0.779 $\pm$ 0.047 (1) | $n>12$ | 0.704 $\pm$ 0.059 (4) | 0.722 $\pm$ 0.065 (2) | 0.715 $\pm$ 0.062 (3)
Adult | 0.743 $\pm$ 0.034 (2) | $n>12$ | 0.464 $\pm$ 0.055 (4) | 0.723 $\pm$ 0.011 (3) | 0.771 $\pm$ 0.011 (1)
Bank Marketing | 0.640 $\pm$ 0.027 (1) | $n>12$ | 0.473 $\pm$ 0.002 (4) | 0.502 $\pm$ 0.011 (3) | 0.608 $\pm$ 0.018 (2)
Congressional Voting | 0.950 $\pm$ 0.021 (1) | $n>12$ | 0.942 $\pm$ 0.021 (2) | 0.924 $\pm$ 0.043 (4) | 0.933 $\pm$ 0.032 (3)
Absenteeism | 0.626 $\pm$ 0.047 (1) | $n>12$ | 0.432 $\pm$ 0.073 (4) | 0.587 $\pm$ 0.047 (2) | 0.564 $\pm$ 0.042 (3)
Hepatitis | 0.608 $\pm$ 0.078 (2) | $n>12$ | 0.446 $\pm$ 0.024 (4) | 0.586 $\pm$ 0.083 (3) | 0.622 $\pm$ 0.078 (1)
German | 0.592 $\pm$ 0.068 (1) | $n>12$ | 0.412 $\pm$ 0.006 (4) | 0.556 $\pm$ 0.035 (3) | 0.589 $\pm$ 0.065 (2)
Mushroom | 1.000 $\pm$ 0.001 (1) | $n>12$ | 0.984 $\pm$ 0.003 (4) | 0.999 $\pm$ 0.001 (2) | 0.999 $\pm$ 0.001 (3)
Credit Card | 0.674 $\pm$ 0.014 (4) | $n>12$ | 0.685 $\pm$ 0.004 (1) | 0.679 $\pm$ 0.007 (3) | 0.683 $\pm$ 0.010 (2)
Horse Colic | 0.842 $\pm$ 0.039 (1) | $n>12$ | 0.496 $\pm$ 0.169 (4) | 0.708 $\pm$ 0.038 (3) | 0.786 $\pm$ 0.062 (2)
Thyroid | 0.905 $\pm$ 0.010 (2) | $n>12$ | 0.605 $\pm$ 0.116 (4) | 0.682 $\pm$ 0.018 (3) | 0.922 $\pm$ 0.011 (1)
Cervical Cancer | 0.521 $\pm$ 0.043 (1) | $n>12$ | 0.514 $\pm$ 0.034 (2) | 0.488 $\pm$ 0.027 (4) | 0.506 $\pm$ 0.034 (3)
Spambase | 0.903 $\pm$ 0.025 (2) | $n>12$ | 0.863 $\pm$ 0.019 (3) | 0.863 $\pm$ 0.011 (4) | 0.917 $\pm$ 0.011 (1)
Mean | 0.771 $\pm$ 0.142 (1) | - | 0.671 $\pm$ 0.196 (4) | 0.723 $\pm$ 0.154 (3) | 0.755 $\pm$ 0.154 (2)
Mean Reciprocal Rank | 0.758 $\pm$ 0.306 (1) | 0.370 $\pm$ 0.268 (3) | 0.365 $\pm$ 0.228 (4) | 0.335 $\pm$ 0.090 (5) | 0.556 $\pm$ 0.293 (2)
Iris | 0.938 $\pm$ 0.057 (1) | 0.870 $\pm$ 0.063 (5) | 0.912 $\pm$ 0.055 (3) | 0.909 $\pm$ 0.046 (4) | 0.937 $\pm$ 0.046 (2)
Balance Scale | 0.593 $\pm$ 0.045 (1) | 0.475 $\pm$ 0.104 (5) | 0.529 $\pm$ 0.043 (3) | 0.525 $\pm$ 0.039 (4) | 0.574 $\pm$ 0.030 (2)
Car | 0.440 $\pm$ 0.085 (3) | 0.485 $\pm$ 0.064 (2) | 0.306 $\pm$ 0.068 (4) | 0.273 $\pm$ 0.063 (5) | 0.489 $\pm$ 0.094 (1)
Glass | 0.560 $\pm$ 0.090 (3) | 0.434 $\pm$ 0.072 (5) | 0.586 $\pm$ 0.090 (2) | 0.501 $\pm$ 0.100 (4) | 0.663 $\pm$ 0.086 (1)
Contraceptive | 0.496 $\pm$ 0.050 (1) | 0.364 $\pm$ 0.050 (3) | 0.290 $\pm$ 0.048 (5) | 0.292 $\pm$ 0.036 (4) | 0.384 $\pm$ 0.075 (2)
Solar Flare | 0.151 $\pm$ 0.033 (3) | 0.171 $\pm$ 0.051 (1) | 0.146 $\pm$ 0.018 (4) | 0.144 $\pm$ 0.034 (5) | 0.157 $\pm$ 0.022 (2)
Wine | 0.933 $\pm$ 0.031 (1) | 0.858 $\pm$ 0.041 (4) | 0.888 $\pm$ 0.039 (3) | 0.852 $\pm$ 0.022 (5) | 0.907 $\pm$ 0.042 (2)
Zoo | 0.874 $\pm$ 0.111 (3) | $n>12$ | 0.782 $\pm$ 0.111 (4) | 0.911 $\pm$ 0.106 (2) | 0.943 $\pm$ 0.076 (1)
Lymphography | 0.610 $\pm$ 0.191 (1) | $n>12$ | 0.381 $\pm$ 0.124 (4) | 0.574 $\pm$ 0.196 (2) | 0.548 $\pm$ 0.154 (3)
Segment | 0.941 $\pm$ 0.009 (2) | $n>12$ | 0.715 $\pm$ 0.114 (4) | 0.808 $\pm$ 0.013 (3) | 0.963 $\pm$ 0.010 (1)
Dermatology | 0.930 $\pm$ 0.030 (2) | $n>12$ | 0.785 $\pm$ 0.126 (4) | 0.885 $\pm$ 0.036 (3) | 0.957 $\pm$ 0.026 (1)
Landsat | 0.807 $\pm$ 0.011 (2) | $n>12$ | 0.628 $\pm$ 0.084 (4) | 0.783 $\pm$ 0.008 (3) | 0.835 $\pm$ 0.011 (1)
Annealing | 0.638 $\pm$ 0.126 (3) | $n>12$ | 0.218 $\pm$ 0.053 (4) | 0.787 $\pm$ 0.121 (2) | 0.866 $\pm$ 0.094 (1)
Splice | 0.873 $\pm$ 0.030 (2) | $n>12$ | 0.486 $\pm$ 0.157 (3) | > 60 min | 0.881 $\pm$ 0.021 (1)
Mean | 0.699 $\pm$ 0.240 (2) | - | 0.547 $\pm$ 0.252(4) | 0.634 $\pm$ 0.268(3) | 0.722 $\pm$ 0.255 (1)
Mean Reciprocal Rank | 0.619 $\pm$ 0.303 (2) | 0.383 $\pm$ 0.293 (3) | 0.288 $\pm$ 0.075 (5) | 0.315 $\pm$ 0.116 (4) | 0.774 $\pm$ 0.274 (1)

GTDs have a small effective tree size The effective tree size (= size of the
tree after pruning) of GDTs is smaller than CART for binary and slightly
larger for multi-class tasks (see Table 2). Only the tree size for GeneticTree
is significantly smaller, which is caused by the complexity penalty of the
genetic algorithm. DL8.5 also has a smaller average tree size than CART and
GDT. We can explain the comparatively small average tree sizes by the fact
that DL8.5 was only feasible up to a depth of $4$ (maximum of $31$ total
nodes) due to the high computational complexity.The tree size for DNDTs scales
with the number of features (and classes) which quickly results in large
trees. Furthermore, pruning DNDTs is non-trivial due to the use of the
Kronecker product (it is not sufficient to prune subtrees bottom-up), which is
why we did not apply pruning for DNDTs.

GDTs are robust to overfitting We can observe that gradient-based approaches
were more robust and less prone to overfitting than a greedy optimization with
CART and alternative non-greedy approaches. We measure overfitting by the
difference between the mean train and test performance (see Table 2). GDTs
have a difference between the train and test performance of $0.051$ for binary
tasks, which is significantly smaller than CART ($0.183$), GeneticTree
($0.204$) and DL8.5 ($0.202$). DNDTs, which are also gradient-based, achieved
an even smaller difference of $0.039$. For multi-class tasks, the difference
was significantly smaller for GDTs compared to any other approach. For DL8.5,
we can observe very strong overfitting (second-highest difference for binary
and highest for multi-class tasks) which can also explain why optimal DTs did
not achieve superior results on test data. These findings are similar to those
reported by Zharmagambetov et al. [40].

Table 2: Summarized Results. Left: Tree size after HPO. Mid: Difference
between train and test performance as overfitting indicator. Right: Impact of
HPO by measuring the performance difference with and without HPO. The complete
results for each dataset are listed in the Appendix C.

| Tree Size | Train-Test Difference | HPO Impact
---|---|---|---
binary | multi-class | binary | multi-class | binary | multi-class
GDT |  054.2 |  086.2 |  0.051 |  0.174 |  -0.007 |  -0.036
DNDT |  886.7 |  906.9 |  0.039 |  0.239 |  -0.051 |  -0.000
GeneticTree |  006.9 |  020.2 |  0.204 |  0.258 |  -0.001 |  -0.018
DL8.5 |  027.5 |  028.9 |  0.202 |  0.260 |  - |  -
CART |  066.7 |  076.0 |  0.183 |  0.247 |  -0.007 |  -0.016

GDTs do not rely on extensive hyperparameter optimization An advantage of DTs
over more sophisticated models, besides their interpretability, is that greedy
approaches do not rely on extensive hyperparameter optimization (HPO) to
achieve good results. In this experiment, we show that the same is true for
GDTs. We evaluated the performance of the approaches with their default
configuration and compared it with the performance after HPO (see Table 2).
Overall, the impact of HPO was rather small for all approaches. For multi-
class tasks, HPO even resulted in a decrease of the average test performance
for CART and GeneticTree. This observation can be explained by the strong
overfitting of those approaches, which makes estimating the test performance
difficult, even when using cross-validation. Thus, suboptimal parameters can
be selected based on the validation performance, resulting in a decrease of
the average test performance. Furthermore, when using the default parameters,
GDTs still outperform on binary tasks (highest MRR and most wins) and achieve
competitive results for multi-class tasks (second-highest MRR and second-most
wins). Detailed results with default parameters for all datasets are listed in
the Appendix C.

GTDs can be learned efficiently for large and high-dimensional datasets Greedy
optimization with CART was significantly faster than any other approach (less
than a second) for each dataset. Nevertheless, for most datasets, learning a
GDT took less than $30$ seconds (mean runtime of $35$ seconds).DNDT achieved
similar runtimes to GDT. DL8.5 had a low runtime $<10$ seconds for most
datasets. However we can observe scalability issues with the number of
features and number of samples, as DL8.5 had a significantly higher runtime
than GDT for several datasets (e.g., $\sim 300$ seconds for _Credit Card_ and
$>830$ seconds for _Landsat_). For _Splice_ , DL8.5 did not converge after
$60$ minutes and the optimization was terminated. The complete runtimes for
each approach are listed in the Appendix C.

##  5 Conclusion and Future Work

In this paper, we proposed a novel method for learning hard, axis-aligned DTs
based on a joint optimization of all tree parameters with gradient descent. We
use backpropagation with a ST operator to deal with the non-differentiable
nature of DTs. We further introduced a dense DT representation and a novel
tree pass function which allows an efficient optimization. Using a gradient-
based optimization, GDTs are not prone to locally optimal solutions, as it is
the case for standard, greedy DT induction methods like CART. We empirically
showed that GDTs outperformed existing approaches on binary classification
tasks and achieved competitive results on multi-class tasks. The performance
increase when using our approach was substantial for several datasets, which
makes GDTs an important extension to existing approaches for DT learning.
Moreover, GDTs significantly outperformed DNDTs as gradient-based benchmark.

Furthermore, a gradient-based optimization provides more flexibility. It is
straightforward to use a custom loss function that is well-suited for the
specific application scenario. Another advantage is the possibility to relearn
the threshold value as well as the split index. This makes GDTs suitable for
dynamic environments, as for instance online learning tasks.

Currently, GDTs use a standard post-hoc pruning. In future work, we want to
consider pruning already during the training, for instance through a learnable
choice parameter to decide if a node is pruned, similar to Zantedeschi et al.
[39]. While we focused on stand-alone DTs to generate intrinsically
interpretable models, GDTs can be extended to ensembles as a performance-
interpretability trade-off, which is subject to future work.

## References

  * Abadi et al. [2015] 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, Yangqing 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, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  URL https://www.tensorflow.org/.  Software available from tensorflow.org.
  * Aglin et al. [2022] G. Aglin, S. Nijssen, and P. Schaus.  Pydl8.5.  https://github.com/aia-uclouvain/pydl8.5, 2022.  Accessed 13.11.2022.
  * Aglin et al. [2020] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus.  Learning optimal decision trees using caching branch-and-bound search.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 3146–3153, 2020.
  * Barros et al. [2011] 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.
  * Bengio et al. [2013] Yoshua Bengio, Nicholas Léonard, and Aaron Courville.  Estimating or propagating gradients through stochastic neurons for conditional computation.  _arXiv preprint arXiv:1308.3432_ , 2013.
  * Bertsimas and Dunn [2017] Dimitris Bertsimas and Jack Dunn.  Optimal classification trees.  _Machine Learning_ , 106(7):1039–1082, 2017.
  * Blanquero et al. [2020] 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.
  * Breiman et al. [1984] 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://lyle.smu.edu/~mhd/8331f06/cart.pdf.
  * Chawla et al. [2002] Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer.  Smote: synthetic minority over-sampling technique.  _Journal of artificial intelligence research_ , 16:321–357, 2002.
  * Demirović et al. [2022] 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–47, 2022.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Freitas [2002] Alex A Freitas.  _Data mining and knowledge discovery with evolutionary algorithms_.  Springer Science & Business Media, 2002.
  * Frosst and Hinton [2017] Nicholas Frosst and Geoffrey Hinton.  Distilling a neural network into a soft decision tree.  _arXiv preprint arXiv:1711.09784_ , 2017.
  * Irsoy et al. [2012] Ozan Irsoy, Olcay Taner Yıldız, and Ethem Alpaydın.  Soft decision trees.  In _Proceedings of the 21st international conference on pattern recognition (ICPR2012)_ , pages 1819–1822. IEEE, 2012.
  * Izmailov et al. [2018] Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson.  Averaging weights leads to wider optima and better generalization.  _arXiv preprint arXiv:1803.05407_ , 2018.
  * Jordan and Jacobs [1994] Michael I Jordan and Robert A Jacobs.  Hierarchical mixtures of experts and the em algorithm.  _Neural computation_ , 6(2):181–214, 1994.
  * Kingma and Ba [2014] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Kuhn et al. [2013] Max Kuhn, Kjell Johnson, et al.  _Applied predictive modeling_ , volume 26.  Springer, 2013.
  * Laurent and Rivest [1976] Hyafil Laurent and Ronald L Rivest.  Constructing optimal binary decision trees is np-complete.  _Information processing letters_ , 5(1):15–17, 1976.
  * Leng et al. [2022] Zhaoqi Leng, Mingxing Tan, Chenxi Liu, Ekin Dogus Cubuk, Xiaojie Shi, Shuyang Cheng, and Dragomir Anguelov.  Polyloss: A polynomial expansion perspective of classification loss functions.  _arXiv preprint arXiv:2204.12511_ , 2022.
  * Lin et al. [2020] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer.  Generalized and scalable optimal sparse decision trees.  In _International Conference on Machine Learning_ , pages 6150–6160. PMLR, 2020.
  * Lin et al. [2017] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2980–2988, 2017.
  * Loh [2002] Wei-Yin Loh.  Regression tress with unbiased variable selection and interaction detection.  _Statistica sinica_ , pages 361–386, 2002.
  * Loh [2009] Wei-Yin Loh.  Improving the precision of classification trees.  _The Annals of Applied Statistics_ , pages 1710–1737, 2009.
  * Marton et al. [2022] Sascha Marton, Stefan Lüdtke, Christian Bartelt, Andrej Tschalzev, and Heiner Stuckenschmidt.  Explaining neural networks without access to training data.  _arXiv preprint arXiv:2206.04891_ , 2022.
  * Molnar [2020] Christoph Molnar.  _Interpretable machine learning_.  Lulu. com, 2020.
  * Murthy [1996] Kolluru Venkata Sreerama Murthy.  _On growing better decision trees from data_.  The Johns Hopkins University, 1996.
  * Norouzi et al. [2015] 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.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. 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–2830, 2011\.
  * Peters et al. [2019] Ben Peters, Vlad Niculae, and André FT Martins.  Sparse sequence-to-sequence models.  _arXiv preprint arXiv:1905.05702_ , 2019.
  * Popov et al. [2019] Sergei Popov, Stanislav Morozov, and Artem Babenko.  Neural oblivious decision ensembles for deep learning on tabular data.  _arXiv preprint arXiv:1909.06312_ , 2019.
  * Pysiak [2021] Karol Pysiak.  Genetictree.  https://github.com/pysiakk/GeneticTree, 2021.  Accessed 17.08.2022.
  * Quinlan [1986] J. Ross Quinlan.  Induction of decision trees.  _Machine learning_ , 1(1):81–106, 1986.
  * Quinlan [1993] J. Ross Quinlan.  _C4.5: programs for machine learning_.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993.  ISBN 1-55860-238-0.  URL http://portal.acm.org/citation.cfm?id=152181.
  * Sarkar et al. [1994] UK Sarkar, PP Chakrabarti, Sujoy Ghose, and SC DeSarkar.  Improving greedy algorithms by lookahead-search.  _Journal of Algorithms_ , 16(1):1–23, 1994.
  * Tanno et al. [2019] Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori.  Adaptive neural trees.  In _International Conference on Machine Learning_ , pages 6166–6175. PMLR, 2019.
  * Yang et al. [2018] Yongxin Yang, Irene Garcia Morillo, and Timothy M Hospedales.  Deep neural decision trees.  _arXiv preprint arXiv:1806.06988_ , 2018.
  * Yang et al. [2022] Yongxin Yang, Irene Garcia Morillo, and Timothy M. Hospedales.  Deep neural decision trees.  https://github.com/wOOL/DNDT, 2022.  Accessed 13.11.2022.
  * Zantedeschi et al. [2021] Valentina Zantedeschi, Matt Kusner, and Vlad Niculae.  Learning binary decision trees by argmin differentiation.  In _International Conference on Machine Learning_ , pages 12298–12309. PMLR, 2021.
  * Zharmagambetov et al. [2021] Arman Zharmagambetov, Suryabhan Singh Hada, Magzhan Gabidolla, and Miguel A Carreira-Perpinán.  Non-greedy algorithms for decision tree optimization: An experimental comparison.  In _2021 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–8. IEEE, 2021.

##  Appendix A Gradient Descent Optimization

We use stochastic gradient descent (SGD) to 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 [17]. We further apply
weight averaging [15] over 5 consecutive checkpoints, similar to Popov et al.
[31]. Our novel tree pass function allows formulating Line 7-9 as a single
matrix operation for a complete batch, which results in a very efficient
optimization. Moreover, we implement an early stopping procedure. To avoid bad
initial parametrizations during the initialization, we additionally implement
random restarts where the best parameters are selected based on the validation
loss.

Algorithm 2 Gradient Descent Training for Decision Trees

1:function trainDT($I,T,L,X,\boldsymbol{y},n,c,d,\xi$)

2:
$I\sim\mathcal{U}\left(-\sqrt{\frac{6}{2^{2d-1}+n}},\sqrt{\frac{6}{2^{2d-1}+n}}\right)$

3:
$T\sim\mathcal{U}\left(-\sqrt{\frac{6}{2^{2d-1}+n}},\sqrt{\frac{6}{2^{2d-1}+n}}\right)$

4:
$L\sim\mathcal{U}\left(-\sqrt{\frac{6}{2^{2d}+c}},\sqrt{\frac{6}{2^{2d}+c}}\right)$

5:

6: for $i=1,\dots,\xi$ do

7: $\boldsymbol{\hat{y}}\leftarrow\emptyset$

8: for $j=1,\dots,|X|$ do

9: $\hat{y}_{j}=$ pass($I,T,L,X_{j}$)

10: $\boldsymbol{\hat{y}}\leftarrow\boldsymbol{\hat{y}}\cup\hat{y}_{j}$

11: end for

12: $I\leftarrow I+\eta\frac{\partial}{\partial
I}\mathcal{L}(\boldsymbol{y},\boldsymbol{\hat{y}})$ $\triangleright$ Calculate
gradients with backpropagation

13: $T\leftarrow T+\eta\frac{\partial}{\partial
T}\mathcal{L}(\boldsymbol{y},\boldsymbol{\hat{y}})$$\triangleright$ Calculate
gradients with backpropagation

14: $L\leftarrow L+\eta\frac{\partial}{\partial
L}\mathcal{L}(\boldsymbol{y},\boldsymbol{\hat{y}})$$\triangleright$ Calculate
gradients with backpropagation

15: end for

16:end function

##  Appendix B Datasets

The datasets along with their specifications and source are summarized in
Table 3. For all datasets, we performed a standard preprocessing: We applied
Leave-one-out encoding to all categorical features.Similar to Popov et al.
[31], we further perform a quantile transform, making each feature follows a
normal distribution. We use a random $80\%/20\%$ train-test split for all
datasets. To account for class imbalance, we rebalanced datasets using SMOTE
[9] when the minority class accounts for less than $\frac{25}{c-1}\%$ of the
data points, where $c$ is the number of classes. Since GDTs and DNDTs requires
a validation set for early stopping, we performed another $80\%/20\%$ split on
the training data for those approaches. For DL8.5 additional preprocessing was
necessary since they can only handle binary features. Therefore, we one-hot
encoded all categorical features and discretized numeric features by one-hot
encoding them using quantile binning with $5$ bins.

Table 3: Dataset Specifications.

Dataset Name |  Number of Features |  Number of Samples |  Samples by Class |  Number of Classes |  Link
---|---|---|---|---|---
Blood Transfusion |  4 |  748 |  178 / 570 |  2 |  https://archive.ics.uci.edu/ml/datasets/Blood+Transfusion+Service+Center
Banknote Authentication |  4 |  1372 |  610 / 762 |  2 |  https://archive.ics.uci.edu/ml/datasets/banknote+authentication
Titanic |  7 |  891 |  342 / 549 |  2 |  https://www.kaggle.com/c/titanic
Raisin |  7 |  900 |  450 /450 |  2 |  https://archive.ics.uci.edu/ml/datasets/Raisin+Dataset
Rice |  7 |  3810 |  1630 / 2180 |  2 |  https://archive.ics.uci.edu/ml/datasets/Rice+%28Cammeo+and+Osmancik%29
Echocardiogram |  8 |  132 |  107 / 25 |  2 |  https://archive.ics.uci.edu/ml/datasets/echocardiogram
Wisconsin Diagnostic Breast Cancer |  10 |  569 |  212 / 357 |  2 |  https://archive.ics.uci.edu/ml/datasets/breast+cancer+wisconsin+(diagnostic)
Loan House |  11 |  614 |  422 / 192 |  2 |  https://www.kaggle.com/code/sazid28/home-loan-prediction/data
Heart Failure |  12 |  299 |  96 /203 |  2 |  https://archive.ics.uci.edu/ml/datasets/Heart+failure+clinical+records
Heart Disease |  13 |  303 |  164 / 139 |  2 |  https://archive.ics.uci.edu/ml/datasets/heart+disease
Adult |  14 |  32561 |  7841 / 24720 |  2 |  https://archive.ics.uci.edu/ml/datasets/adult
Bank Marketing |  14 |  45211 |  5289 / 39922 |  2 |  https://archive.ics.uci.edu/ml/datasets/bank+marketing
Congressional Voting |  16 |  435 |  267 / 168 |  2 |  https://archive.ics.uci.edu/ml/datasets/congressional+voting+records
Absenteeism |  18 |  740 |  279 / 461 |  2 |  https://archive.ics.uci.edu/ml/datasets/Absenteeism+at+work
Hepatitis |  19 |  155 |  32 / 123 |  2 |  https://archive.ics.uci.edu/ml/datasets/hepatitis
German |  20 |  1000 |  300 / 700 |  2 |  https://archive.ics.uci.edu/ml/datasets/statlog+(german+credit+data)
Mushrooms |  22 |  8124 |  4208 /3916 |  2 |  https://archive.ics.uci.edu/ml/datasets/mushroom
Credit Card |  23 |  30000 |  23364 / 6636 |  2 |  https://archive.ics.uci.edu/ml/datasets/default+of+credit+card+clients
Horse Colic |  26 |  368 |  232 / 136 |  2 |  https://archive.ics.uci.edu/ml/datasets/Horse+Colic
Thyroid |  29 |  9172 |  2401 / 6771 |  2 |  https://archive.ics.uci.edu/ml/datasets/thyroid+disease
Cervical Cancer |  31 |  858 |  55 / 803 |  2 |  https://archive.ics.uci.edu/ml/datasets/Cervical+cancer+%28Risk+Factors%29
Spambase |  57 |  4601 |  1813 / 2788 |  2 |  https://archive.ics.uci.edu/ml/datasets/spambase
Iris |  4 |  150 |  50 / 50 / 50 |  3 |  https://archive.ics.uci.edu/ml/datasets/iris
Balance Scale |  4 |  625 |  49 / 288 / 288 |  3 |  https://archive.ics.uci.edu/ml/datasets/balance+scale
Car |  6 |  1728 |  384 / 69 / 1210 / 65 |  4 |  https://archive.ics.uci.edu/ml/datasets/car+evaluation
Glass |  9 |  214 |  70 / 76 / 17 / 13 / 9 / 29 |  6 |  https://archive.ics.uci.edu/ml/datasets/glass+identification
Contraceptive |  9 |  1473 |  629 / 333 / 511 |  3 |  https://archive.ics.uci.edu/ml/datasets/Contraceptive+Method+Choice
Solar Flare |  10 |  1389 |  1171 / 141 / 40 / 20 / 9 / 4 / 3 / 1 |  8 |  http://archive.ics.uci.edu/ml/datasets/solar+flare
Wine |  12 |  178 |  59 / 71 / 48 |  3 |  https://archive.ics.uci.edu/ml/datasets/wine
Zoo |  16 |  101 |  41 / 20 / 5 / 13 / 4 / 8 /10 |  7 |  https://archive.ics.uci.edu/ml/datasets/zoo
Lymphography |  18 |  148 |  2 / 81 /61 /4 |  4 |  https://archive.ics.uci.edu/ml/datasets/Lymphography
Segment |  19 |  2310 |  330 / 330 / 330 / 330 / 330 / 330 / 330 |  7 |  https://archive.ics.uci.edu/ml/datasets/image+segmentation
Dermatology |  34 |  366 |  112 / 61 / 72 / 49 / 52 / 20 |  6 |  https://archive.ics.uci.edu/ml/datasets/dermatology
Landsat |  36 |  6435 |  1533 / 703 / 1358 / 626 / 707 /1508 |  6 |  https://archive.ics.uci.edu/ml/datasets/Statlog+(Landsat+Satellite)
Annealing |  38 |  798 |  8 / 88 / 608 / 60 / 34 |  5 |  https://archive.ics.uci.edu/ml/datasets/Annealing
Splice |  60 |  3190 |  767 / 768 / 1655 |  3 |  https://archive.ics.uci.edu/ml/datasets/Molecular+Biology+(Splice-junction+Gene+Sequences)

##  Appendix C Additional Results

Table 4: Performance Comparison Default Hyperparameters. We report macro
F1-scores (mean $\pm$ stdev over $10$ trials) with default parameters. We also
report the rank of each approach in brackets. The datasets are sorted by the
number of features. The top part comprises binary classification tasks and the
bottom part multi-class datasets.

| Gradient-Based | Non-Greedy | Greedy
---|---|---|---
| GDT (ours) | DNDT | GeneticTree | DL8.5 | CART
Blood Transfusion | 0.627 $\pm$ 0.056 (1) | 0.558 $\pm$ 0.059 (5) | 0.574 $\pm$ 0.093 (3) | 0.590 $\pm$ 0.034 (2) | 0.573 $\pm$ 0.036 (4)
Banknote Authentication | 0.980 $\pm$ 0.008 (2) | 0.886 $\pm$ 0.024 (5) | 0.928 $\pm$ 0.022 (4) | 0.962 $\pm$ 0.011 (3) | 0.981 $\pm$ 0.006 (1)
Titanic | 0.782 $\pm$ 0.035 (1) | 0.740 $\pm$ 0.026 (4) | 0.763 $\pm$ 0.041 (2) | 0.754 $\pm$ 0.031 (3) | 0.735 $\pm$ 0.041 (5)
Raisins | 0.850 $\pm$ 0.025 (2) | 0.832 $\pm$ 0.026 (4) | 0.859 $\pm$ 0.022 (1) | 0.849 $\pm$ 0.027 (3) | 0.811 $\pm$ 0.028 (5)
Rice | 0.926 $\pm$ 0.006 (2) | 0.902 $\pm$ 0.018 (5) | 0.927 $\pm$ 0.005 (1) | 0.925 $\pm$ 0.008 (3) | 0.905 $\pm$ 0.010 (4)
Echocardiogram | 0.648 $\pm$ 0.130 (1) | 0.543 $\pm$ 0.117 (5) | 0.563 $\pm$ 0.099 (3) | 0.609 $\pm$ 0.112 (2) | 0.559 $\pm$ 0.075 (4)
Wisconsin Breast Cancer | 0.902 $\pm$ 0.029 (3) | 0.907 $\pm$ 0.037 (1) | 0.888 $\pm$ 0.021 (5) | 0.896 $\pm$ 0.021 (4) | 0.904 $\pm$ 0.025 (2)
Loan House | 0.695 $\pm$ 0.035 (1) | 0.475 $\pm$ 0.043 (4) | 0.461 $\pm$ 0.093 (5) | 0.607 $\pm$ 0.045 (3) | 0.671 $\pm$ 0.056 (2)
Heart Failure | 0.745 $\pm$ 0.063 (2) | 0.580 $\pm$ 0.077 (5) | 0.740 $\pm$ 0.055 (3) | 0.692 $\pm$ 0.062 (4) | 0.755 $\pm$ 0.060 (1)
Heart Disease | 0.736 $\pm$ 0.069 (1) | $n>12$ | 0.704 $\pm$ 0.059 (3) | 0.722 $\pm$ 0.065 (2) | 0.670 $\pm$ 0.090 (4)
Adult | 0.749 $\pm$ 0.028 (2) | $n>12$ | 0.478 $\pm$ 0.068 (4) | 0.723 $\pm$ 0.011 (3) | 0.773 $\pm$ 0.008 (1)
Bank Marketing | 0.626 $\pm$ 0.017 (1) | $n>12$ | 0.473 $\pm$ 0.002 (4) | 0.502 $\pm$ 0.011 (3) | 0.616 $\pm$ 0.007 (2)
Congressional Voting | 0.953 $\pm$ 0.021 (1) | $n>12$ | 0.932 $\pm$ 0.034 (3) | 0.924 $\pm$ 0.043 (4) | 0.933 $\pm$ 0.032 (2)
Absenteeism | 0.620 $\pm$ 0.050 (1) | $n>12$ | 0.417 $\pm$ 0.035 (4) | 0.587 $\pm$ 0.047 (2) | 0.580 $\pm$ 0.045 (3)
Hepatitis | 0.609 $\pm$ 0.103 (2) | $n>12$ | 0.486 $\pm$ 0.074 (4) | 0.586 $\pm$ 0.083 (3) | 0.610 $\pm$ 0.123 (1)
German | 0.584 $\pm$ 0.057 (2) | $n>12$ | 0.412 $\pm$ 0.005 (4) | 0.556 $\pm$ 0.035 (3) | 0.595 $\pm$ 0.028 (1)
Mushroom | 0.997 $\pm$ 0.003 (3) | $n>12$ | 0.984 $\pm$ 0.003 (4) | 0.999 $\pm$ 0.001 (1) | 0.999 $\pm$ 0.001 (2)
Credit Card | 0.676 $\pm$ 0.009 (4) | $n>12$ | 0.685 $\pm$ 0.004 (1) | 0.679 $\pm$ 0.007 (3) | 0.679 $\pm$ 0.007 (2)
Horse Colic | 0.842 $\pm$ 0.033 (1) | $n>12$ | 0.794 $\pm$ 0.042 (2) | 0.708 $\pm$ 0.038 (4) | 0.758 $\pm$ 0.053 (3)
Thyroid | 0.872 $\pm$ 0.015 (2) | $n>12$ | 0.476 $\pm$ 0.101 (4) | 0.682 $\pm$ 0.018 (3) | 0.912 $\pm$ 0.013 (1)
Cervical Cancer | 0.496 $\pm$ 0.047 (3) | $n>12$ | 0.514 $\pm$ 0.034 (1) | 0.488 $\pm$ 0.027 (4) | 0.505 $\pm$ 0.033 (2)
Spambase | 0.893 $\pm$ 0.015 (2) | $n>12$ | 0.864 $\pm$ 0.014 (3) | 0.863 $\pm$ 0.011 (4) | 0.917 $\pm$ 0.011 (1)
Mean | 0.764 $\pm$ 0.144 (1) | - | 0.678 $\pm$ 0.197 (4) | 0.723 $\pm$ 0.154 (3) | 0.747 $\pm$ 0.153 (2)
Mean Reciprocal Rank | 0.670 $\pm$ 0.289 (1) | 0.306 $\pm$ 0.262 (5) | 0.427 $\pm$ 0.287 (3) | 0.371 $\pm$ 0.164 (4) | 0.571 $\pm$ 0.318 (2)
Iris | 0.938 $\pm$ 0.039 (1) | 0.870 $\pm$ 0.051 (5) | 0.912 $\pm$ 0.038 (3) | 0.909 $\pm$ 0.046 (4) | 0.937 $\pm$ 0.036 (2)
Balance Scale | 0.575 $\pm$ 0.031 (2) | 0.542 $\pm$ 0.062 (3) | 0.539 $\pm$ 0.026 (4) | 0.525 $\pm$ 0.039 (5) | 0.581 $\pm$ 0.025 (1)
Car | 0.389 $\pm$ 0.062 (3) | 0.426 $\pm$ 0.065 (2) | 0.321 $\pm$ 0.069 (4) | 0.273 $\pm$ 0.063 (5) | 0.571 $\pm$ 0.133 (1)
Glass | 0.484 $\pm$ 0.099 (5) | 0.498 $\pm$ 0.096 (4) | 0.566 $\pm$ 0.152 (2) | 0.501 $\pm$ 0.100 (3) | 0.668 $\pm$ 0.085 (1)
Contraceptive | 0.472 $\pm$ 0.039 (1) | 0.324 $\pm$ 0.045 (3) | 0.311 $\pm$ 0.053 (4) | 0.292 $\pm$ 0.036 (5) | 0.450 $\pm$ 0.064 (2)
Solar Flare | 0.145 $\pm$ 0.017 (3) | 0.142 $\pm$ 0.025 (5) | 0.150 $\pm$ 0.026 (2) | 0.144 $\pm$ 0.034 (4) | 0.180 $\pm$ 0.026 (1)
Wine | 0.895 $\pm$ 0.035 (3) | 0.853 $\pm$ 0.042 (4) | 0.898 $\pm$ 0.041 (2) | 0.852 $\pm$ 0.022 (5) | 0.907 $\pm$ 0.042 (1)
Zoo | 0.827 $\pm$ 0.162 (3) | $n>12$ | 0.802 $\pm$ 0.094 (4) | 0.911 $\pm$ 0.106 (2) | 0.943 $\pm$ 0.076 (1)
Lymphography | 0.472 $\pm$ 0.192 (3) | $n>12$ | 0.397 $\pm$ 0.211 (4) | 0.574 $\pm$ 0.196 (2) | 0.606 $\pm$ 0.176 (1)
Segment | 0.921 $\pm$ 0.014 (2) | $n>12$ | 0.736 $\pm$ 0.064 (4) | 0.808 $\pm$ 0.013 (3) | 0.950 $\pm$ 0.006 (1)
Dermatology | 0.876 $\pm$ 0.041 (3) | $n>12$ | 0.818 $\pm$ 0.161 (4) | 0.885 $\pm$ 0.036 (2) | 0.951 $\pm$ 0.024 (1)
Landsat | 0.791 $\pm$ 0.012 (2) | $n>12$ | 0.647 $\pm$ 0.054 (4) | 0.783 $\pm$ 0.008 (3) | 0.835 $\pm$ 0.011 (1)
Annealing | 0.632 $\pm$ 0.155 (3) | $n>12$ | 0.198 $\pm$ 0.050 (4) | 0.787 $\pm$ 0.121 (2) | 0.873 $\pm$ 0.092 (1)
Splice | 0.869 $\pm$ 0.017 (2) | $n>12$ | 0.611 $\pm$ 0.095 (3) | > 60 min | 0.878 $\pm$ 0.028 (1)
Mean | 0.638 $\pm$ 0.244 (2) | - | 0.565 $\pm$ 0.256 (4) | 0.634 $\pm$ 0.268 (3) | 0.738 $\pm$ 0.235 (1)
Mean Reciprocal Rank | 0.470 $\pm$ 0.239 (2) | 0.295 $\pm$ 0.106 (5) | 0.315 $\pm$ 0.104 (4) | 0.331 $\pm$ 0.128 (3) | 0.929 $\pm$ 0.182 (1)

Table 5: Train Performance Comparison. We report macro F1-scores (mean $\pm$
stdev over $10$ trials) on the training data. We also report the rank of each
approach in brackets. The datasets are sorted by the number of features. The
top part comprises binary classification tasks and the bottom part multi-class
datasets.

| Gradient-Based | Non-Greedy | Greedy
---|---|---|---
| GDT (ours) | DNDT | GeneticTree | DL8.5 | CART
Blood Transfusion | 0.686 $\pm$ 0.032 (3) | 0.552 $\pm$ 0.085 (5) | 0.615 $\pm$ 0.122 (4) | 0.711 $\pm$ 0.045 (2) | 0.832 $\pm$ 0.040 (1)
Banknote Authentication | 0.995 $\pm$ 0.003 (2) | 0.907 $\pm$ 0.012 (5) | 0.933 $\pm$ 0.016 (4) | 0.967 $\pm$ 0.003 (3) | 0.999 $\pm$ 0.001 (1)
Titanic | 0.761 $\pm$ 0.128 (5) | 0.791 $\pm$ 0.025 (4) | 0.908 $\pm$ 0.023 (3) | 0.970 $\pm$ 0.006 (1) | 0.949 $\pm$ 0.012 (2)
Raisins | 0.892 $\pm$ 0.024 (1) | 0.829 $\pm$ 0.027 (5) | 0.863 $\pm$ 0.004 (4) | 0.889 $\pm$ 0.004 (2) | 0.866 $\pm$ 0.004 (3)
Rice | 0.925 $\pm$ 0.003 (3) | 0.913 $\pm$ 0.012 (5) | 0.920 $\pm$ 0.002 (4) | 0.930 $\pm$ 0.002 (1) | 0.927 $\pm$ 0.002 (2)
Echocardiogram | 0.827 $\pm$ 0.088 (4) | 0.817 $\pm$ 0.034 (5) | 0.844 $\pm$ 0.032 (3) | 0.935 $\pm$ 0.013 (2) | 0.981 $\pm$ 0.009 (1)
Wisconsin Breast Cancer | 0.947 $\pm$ 0.015 (2) | 0.936 $\pm$ 0.015 (3) | 0.907 $\pm$ 0.009 (5) | 0.964 $\pm$ 0.005 (1) | 0.915 $\pm$ 0.006 (4)
Loan House | 0.735 $\pm$ 0.009 (4) | 0.712 $\pm$ 0.010 (5) | 0.897 $\pm$ 0.012 (3) | 0.969 $\pm$ 0.006 (1) | 0.938 $\pm$ 0.009 (2)
Heart Failure | 0.785 $\pm$ 0.038 (4) | 0.773 $\pm$ 0.053 (5) | 0.795 $\pm$ 0.024 (3) | 0.912 $\pm$ 0.008 (1) | 0.818 $\pm$ 0.021 (2)
Heart Disease | 0.851 $\pm$ 0.027 (4) | $n>12$ | 0.902 $\pm$ 0.020 (3) | 0.990 $\pm$ 0.005 (1) | 0.964 $\pm$ 0.010 (2)
Adult | 0.875 $\pm$ 0.050 (4) | $n>12$ | 0.932 $\pm$ 0.013 (3) | 0.967 $\pm$ 0.001 (2) | 0.973 $\pm$ 0.001 (1)
Bank Marketing | 0.603 $\pm$ 0.029 (4) | $n>12$ | 0.971 $\pm$ 0.003 (3) | 0.981 $\pm$ 0.001 (2) | 0.984 $\pm$ 0.001 (1)
Congressional Voting | 0.971 $\pm$ 0.019 (4) | $n>12$ | 0.978 $\pm$ 0.005 (3) | 1.000 $\pm$ 0.001 (2) | 1.000 $\pm$ 0.000 (1)
Absenteeism | 0.778 $\pm$ 0.050 (4) | $n>12$ | 0.842 $\pm$ 0.011 (3) | 0.920 $\pm$ 0.009 (2) | 0.952 $\pm$ 0.008 (1)
Hepatitis | 0.931 $\pm$ 0.038 (4) | $n>12$ | 0.967 $\pm$ 0.011 (3) | 1.000 $\pm$ 0.000 (1) | 0.998 $\pm$ 0.003 (2)
German | 0.589 $\pm$ 0.048 (4) | $n>12$ | 0.891 $\pm$ 0.010 (3) | 0.958 $\pm$ 0.002 (1) | 0.940 $\pm$ 0.013 (2)
Mushroom | 1.000 $\pm$ 0.000 (1) | $n>12$ | 0.993 $\pm$ 0.005 (4) | 1.000 $\pm$ 0.000 (1) | 1.000 $\pm$ 0.000 (1)
Credit Card | 0.651 $\pm$ 0.020 (4) | $n>12$ | 0.691 $\pm$ 0.002 (3) | 0.710 $\pm$ 0.003 (2) | 0.758 $\pm$ 0.008 (1)
Horse Colic | 0.882 $\pm$ 0.033 (4) | $n>12$ | 0.913 $\pm$ 0.019 (3) | 1.000 $\pm$ 0.000 (1) | 0.963 $\pm$ 0.008 (2)
Thyroid | 0.914 $\pm$ 0.012 (4) | $n>12$ | 0.927 $\pm$ 0.014 (3) | 0.937 $\pm$ 0.002 (2) | 0.987 $\pm$ 0.002 (1)
Cervical Cancer | 0.593 $\pm$ 0.128 (4) | $n>12$ | 0.691 $\pm$ 0.046 (3) | 0.767 $\pm$ 0.020 (2) | 0.925 $\pm$ 0.027 (1)
Spambase | 0.905 $\pm$ 0.020 (2) | $n>12$ | 0.858 $\pm$ 0.020 (4) | 0.879 $\pm$ 0.002 (3) | 0.965 $\pm$ 0.003 (1)
Mean | 0.823 $\pm$ 0.132 (4) | - | 0.874 $\pm$ 0.098 (3) | 0.925 $\pm$ 0.087 (2) | 0.938 $\pm$ 0.065 (1)
Mean Reciprocal Rank | 0.358 $\pm$ 0.226 (3) | 0.220 $\pm$ 0.045 (5) | 0.305 $\pm$ 0.044 (4) | 0.712 $\pm$ 0.263 (2) | 0.754 $\pm$ 0.282 (1)
Iris | 0.978 $\pm$ 0.017 (2) | 0.926 $\pm$ 0.030 (5) | 0.947 $\pm$ 0.008 (4) | 0.996 $\pm$ 0.004 (1) | 0.973 $\pm$ 0.010 (3)
Balance Scale | 0.793 $\pm$ 0.034 (2) | 0.602 $\pm$ 0.142 (5) | 0.665 $\pm$ 0.034 (4) | 0.700 $\pm$ 0.022 (3) | 0.932 $\pm$ 0.010 (1)
Car | 0.807 $\pm$ 0.048 (4) | 0.681 $\pm$ 0.087 (5) | 0.863 $\pm$ 0.055 (3) | 0.885 $\pm$ 0.029 (2) | 0.974 $\pm$ 0.010 (1)
Glass | 0.785 $\pm$ 0.045 (4) | 0.804 $\pm$ 0.020 (3) | 0.699 $\pm$ 0.049 (5) | 0.837 $\pm$ 0.009 (2) | 0.978 $\pm$ 0.007 (1)
Contraceptive | 0.545 $\pm$ 0.067 (5) | 0.591 $\pm$ 0.105 (4) | 0.723 $\pm$ 0.030 (3) | 0.822 $\pm$ 0.016 (2) | 0.865 $\pm$ 0.018 (1)
Solar Flare | 0.833 $\pm$ 0.090 (3) | 0.729 $\pm$ 0.080 (5) | 0.794 $\pm$ 0.123 (4) | 0.904 $\pm$ 0.047 (2) | 0.943 $\pm$ 0.061 (1)
Wine | 0.995 $\pm$ 0.009 (3) | 0.996 $\pm$ 0.006 (2) | 0.931 $\pm$ 0.019 (5) | 0.978 $\pm$ 0.004 (4) | 1.000 $\pm$ 0.000 (1)
Zoo | 0.990 $\pm$ 0.029 (3) | $n>12$ | 0.831 $\pm$ 0.129 (4) | 1.000 $\pm$ 0.000 (1) | 1.000 $\pm$ 0.000 (2)
Lymphography | 0.974 $\pm$ 0.018 (2) | $n>12$ | 0.915 $\pm$ 0.072 (4) | 0.957 $\pm$ 0.130 (3) | 0.988 $\pm$ 0.004 (1)
Segment | 0.959 $\pm$ 0.005 (2) | $n>12$ | 0.715 $\pm$ 0.109 (4) | 0.799 $\pm$ 0.003 (3) | 0.987 $\pm$ 0.002 (1)
Dermatology | 0.965 $\pm$ 0.014 (2) | $n>12$ | 0.792 $\pm$ 0.110 (4) | 0.954 $\pm$ 0.007 (3) | 0.986 $\pm$ 0.005 (1)
Landsat | 0.824 $\pm$ 0.010 (2) | $n>12$ | 0.630 $\pm$ 0.083 (4) | 0.792 $\pm$ 0.004 (3) | 0.939 $\pm$ 0.005 (1)
Annealing | 0.885 $\pm$ 0.089 (4) | $n>12$ | 0.974 $\pm$ 0.013 (3) | 0.999 $\pm$ 0.001 (2) | 0.999 $\pm$ 0.001 (1)
Splice | 0.886 $\pm$ 0.026 (2) | $n>12$ | 0.783 $\pm$ 0.062 (3) | > 60 min | 0.992 $\pm$ 0.004 (1)
Mean | 0.873 $\pm$ 0.123 (3) | - | 0.804 $\pm$ 0.110 (4) | 0.894 $\pm$ 0.097 (2) | 0.968 $\pm$ 0.038 (1)
Mean Reciprocal Rank | 0.389 $\pm$ 0.121 (3) | 0.269 $\pm$ 0.113 (4) | 0.267 $\pm$ 0.047 (5) | 0.494 $\pm$ 0.242 (2) | 0.952 $\pm$ 0.178 (1)

Table 6: Tree Size Comparison. We report the average tree size based on the
optimized hyperparameters (mean $\pm$ stdev over $10$ trials). We also report
the rank of each approach in brackets. The datasets are sorted by the number
of features. The top part comprises binary classification tasks and the bottom
part multi-class datasets.

| Gradient-Based | Non-Greedy | Greedy
---|---|---|---
| GDT (ours) | DNDT | GeneticTree | DL8.5 | CART
Blood Transfusion |  029.200 $\pm$ 008.219 (3) |  0,024.000 $\pm$ 0,000.000 (2) |  05.200 $\pm$ 03.027 (1) | 24.000 $\pm$ 01.612 (3) | 165.600 $\pm$ 021.837 (5)
Banknote Authentication |  060.000 $\pm$ 011.216 (5) |  0,024.000 $\pm$ 0,000.000 (2) | 12.800 $\pm$ 05.325 (1) | 26.800 $\pm$ 00.600 (3) |  044.800 $\pm$ 004.686 (4)
Titanic |  039.600 $\pm$ 010.161 (3) |  0,142.000 $\pm$ 0,000.000 (5) | 10.400 $\pm$ 03.105 (1) | 28.200 $\pm$ 00.980 (3) |  021.600 $\pm$ 000.917 (2)
Raisins | 114.800 $\pm$ 033.686 (4) |  0,142.000 $\pm$ 0,000.000 (5) |  03.600 $\pm$ 01.800 (2) | 29.400 $\pm$ 01.497 (3) |  003.000 $\pm$ 000.000 (1)
Rice |  041.000 $\pm$ 010.040 (4) |  0,142.000 $\pm$ 0,000.000 (5) |  03.000 $\pm$ 00.000 (2) | 30.200 $\pm$ 00.980 (3) |  003.000 $\pm$ 000.000 (1)
Echocardiogram |  043.200 $\pm$ 012.820 (4) |  0,272.000 $\pm$ 0,000.000 (5) |  09.000 $\pm$ 03.098 (1) | 30.000 $\pm$ 01.342 (2) |  036.200 $\pm$ 005.810 (3)
Wisconsin Breast Cancer |  061.800 $\pm$ 013.363 (4) | 1,044.000 $\pm$ 0,000.000 (5) |  04.000 $\pm$ 01.612 (2) | 29.400 $\pm$ 00.800 (3) |  003.000 $\pm$ 000.000 (1)
Loan House |  019.200 $\pm$ 005.250 (2) | 2,070.000 $\pm$ 0,000.000 (5) |  06.800 $\pm$ 02.750 (1) | 28.200 $\pm$ 01.327 (4) |  026.200 $\pm$ 002.040 (3)
Heart Failure |  027.200 $\pm$ 009.442 (3) | 4,120.000 $\pm$ 0,000.000 (5) |  03.200 $\pm$ 00.600 (1) | 30.800 $\pm$ 00.600 (4) |  014.200 $\pm$ 000.980 (2)
Heart Disease |  036.800 $\pm$ 007.454 (4) | $n>12$ | 11.000 $\pm$ 04.099 (1) | 27.600 $\pm$ 01.562 (3) |  024.600 $\pm$ 003.072 (2)
Adult | 128.000 $\pm$ 037.194 (3) | $n>12$ |  09.400 $\pm$ 04.964 (1) | 25.200 $\pm$ 00.600 (2) | 156.600 $\pm$ 023.079 (4)
Bank Marketing |  006.800 $\pm$ 003.027 (2) | $n>12$ |  03.400 $\pm$ 01.200 (1) | 27.200 $\pm$ 02.272 (3) | 110.600 $\pm$ 010.500 (4)
Congressional Voting |  005.600 $\pm$ 002.375 (2) | $n>12$ |  05.600 $\pm$ 00.917 (1) | 20.400 $\pm$ 06.696 (4) |  019.200 $\pm$ 006.416 (3)
Absenteeism | 148.800 $\pm$ 018.187 (4) | $n>12$ |  07.800 $\pm$ 00.980 (1) | 30.600 $\pm$ 00.800 (2) |  043.200 $\pm$ 002.750 (3)
Hepatitis |  012.200 $\pm$ 003.600 (2) | $n>12$ |  05.800 $\pm$ 02.713 (1) | 14.800 $\pm$ 02.088 (4) |  012.600 $\pm$ 001.744 (3)
German |  027.600 $\pm$ 004.104 (2) | $n>12$ |  06.200 $\pm$ 00.980 (1) | 30.400 $\pm$ 00.917 (3) |  034.600 $\pm$ 005.713 (4)
Mushroom |  025.600 $\pm$ 005.731 (4) | $n>12$ |  05.200 $\pm$ 01.661 (1) | 21.200 $\pm$ 02.750 (3) |  014.000 $\pm$ 001.342 (2)
Credit Card |  092.600 $\pm$ 039.636 (3) | $n>12$ |  03.000 $\pm$ 00.000 (1) | 31.000 $\pm$ 00.000 (2) | 354.800 $\pm$ 031.603 (4)
Horse Colic |  022.400 $\pm$ 004.737 (3) | $n>12$ |  04.000 $\pm$ 01.612 (1) | 29.400 $\pm$ 01.200 (4) |  012.600 $\pm$ 001.200 (2)
Thyroid |  096.800 $\pm$ 016.863 (4) | $n>12$ |  05.600 $\pm$ 01.800 (1) | 30.600 $\pm$ 00.800 (2) |  066.400 $\pm$ 004.652 (3)
Cervical Cancer |  034.000 $\pm$ 023.669 (3) | $n>12$ | 14.000 $\pm$ 07.550 (1) | 30.800 $\pm$ 00.600 (2) |  099.000 $\pm$ 008.532 (4)
Spambase | 120.200 $\pm$ 037.010 (3) | $n>12$ | 12.400 $\pm$ 05.800 (1) | 29.600 $\pm$ 00.917 (2) | 201.000 $\pm$ 014.642 (4)
Mean |  054.245 $\pm$ 042.824 (3) |  0,886.667 $\pm$ 1,387.861 (5) |  06.882 $\pm$ 03.457 (1) | 27.536 $\pm$ 04.146 (2) |  066.673 $\pm$ 086.224 (4)
Mean Reciprocal Rank |  000.331 $\pm$ 000.102 (4) |  0,000.267 $\pm$ 0,000.132 (5) |  00.932 $\pm$ 00.176 (1) |  00.367 $\pm$ 00.098 (3) |  000.430 $\pm$ 000.252 (2)
Iris |  014.400 $\pm$ 002.538 (3) |  0,024.000 $\pm$ 0,000.000 (4) | 9.000 $\pm$ 03.098 (1) | 29.200 $\pm$ 01.400 (5) |  009.400 $\pm$ 001.497 (2)
Balance Scale | 118.600 $\pm$ 027.097 (4) |  0,024.000 $\pm$ 0,000.000 (1) | 25.400 $\pm$ 11.307 (2) | 31.000 $\pm$ 00.000 (3) | 161.200 $\pm$ 008.920 (5)
Car |  047.000 $\pm$ 013.565 (3) |  0,076.000 $\pm$ 0,000.000 (5) | 32.600 $\pm$ 21.350 (1) | 29.800 $\pm$ 00.980 (2) |  057.000 $\pm$ 013.023 (4)
Glass |  056.800 $\pm$ 011.007 (3) |  0,530.000 $\pm$ 0,000.000 (5) | 21.800 $\pm$ 11.531 (1) | 30.600 $\pm$ 00.800 (2) |  068.000 $\pm$ 006.340 (4)
Contraceptive |  040.600 $\pm$ 011.482 (3) |  0,530.000 $\pm$ 0,000.000 (5) | 12.800 $\pm$ 03.842 (1) | 30.000 $\pm$ 01.342 (2) |  048.600 $\pm$ 007.144 (4)
Solar Flare |  049.800 $\pm$ 009.304 (4) | 1,044.000 $\pm$ 0,000.000 (5) | 38.400 $\pm$ 21.411 (3) | 26.800 $\pm$ 03.280 (1) |  032.000 $\pm$ 003.130 (2)
Wine |  024.000 $\pm$ 004.123 (3) | 4,120.000 $\pm$ 0,000.000 (5) | 11.200 $\pm$ 04.771 (1) | 28.200 $\pm$ 01.600 (4) |  013.400 $\pm$ 002.332 (2)
Zoo |  025.000 $\pm$ 003.899 (3) | $n>12$ | 32.600 $\pm$ 19.304 (4) | 24.600 $\pm$ 00.800 (2) |  018.000 $\pm$ 001.342 (1)
Lymphography |  036.200 $\pm$ 006.337 (4) | $n>12$ | 14.400 $\pm$ 06.815 (1) | 27.000 $\pm$ 01.265 (3) |  016.800 $\pm$ 001.887 (2)
Segment | 133.000 $\pm$ 021.854 (4) | $n>12$ | 24.400 $\pm$ 11.421 (1) | 31.000 $\pm$ 00.000 (2) |  079.600 $\pm$ 003.800 (3)
Dermatology |  033.600 $\pm$ 007.269 (4) | $n>12$ | 20.000 $\pm$ 07.759 (1) | 28.000 $\pm$ 01.844 (2) |  028.000 $\pm$ 001.844 (2)
Landsat | 360.600 $\pm$ 021.124 (3) | $n>12$ | 16.000 $\pm$ 07.335 (1) | 31.000 $\pm$ 00.000 (2) | 425.600 $\pm$ 018.527 (4)
Annealing |  019.600 $\pm$ 002.835 (2) | $n>12$ | 12.600 $\pm$ 03.323 (1) | 28.400 $\pm$ 02.010 (4) |  024.400 $\pm$ 002.010 (3)
Splice | 247.400 $\pm$ 052.997 (3) | $n>12$ | 11.800 $\pm$ 06.400 (1) | $n>12$ |  081.400 $\pm$ 010.688 (2)
Mean |  086.186 $\pm$ 101.070 (4) |  0,906.857 $\pm$ 1,464.942 (5) | 20.214 $\pm$ 9.310 (1) | 28.946 $\pm$ 01.983 (2) |  075.957 $\pm$ 108.423 (3)
Mean Reciprocal Rank |  000.315 $\pm$ 000.067 (5) |  0,000.321 $\pm$ 0,000.300 (4) |  00.863 $\pm$ 0.277 (1) |  00.451 $\pm$ 00.202 (2) |  000.419 $\pm$ 000.206 (3)

Table 7: Runtime Comparison. We report runtime without restarts based on the
optimized hyperparameters (mean $\pm$ stdev over $10$ trials). We also report
the rank of each approach in brackets. The datasets are sorted by the number
of features. The top part comprises binary classification tasks and the bottom
part multi-class datasets.

| Gradient-Based | Non-Greedy | Greedy
---|---|---|---
| GDT (ours) | DNDT | GeneticTree | DL8.5 | CART
Blood Transfusion |  013.007 $\pm$ 01.000 (5) |  03.704 $\pm$ 01.000 (3) |  010.514 $\pm$ 04.000 (4) |  000.031 $\pm$ 0.000 (2) | 0.002 $\pm$ 0.000 (1)
Banknote Authentication |  013.209 $\pm$ 02.000 (4) | 34.425 $\pm$ 01.000 (5) |  010.318 $\pm$ 03.000 (3) |  000.025 $\pm$ 0.000 (2) | 0.003 $\pm$ 0.000 (1)
Titanic |  029.579 $\pm$ 01.000 (5) |  06.815 $\pm$ 00.000 (4) |  003.677 $\pm$ 01.000 (3) |  000.259 $\pm$ 0.000 (2) | 0.002 $\pm$ 0.000 (1)
Raisins |  030.611 $\pm$ 02.000 (5) |  08.495 $\pm$ 01.000 (4) |  000.619 $\pm$ 00.000 (3) |  000.198 $\pm$ 0.000 (2) | 0.004 $\pm$ 0.000 (1)
Rice |  021.487 $\pm$ 04.000 (5) | 11.955 $\pm$ 01.000 (4) |  001.329 $\pm$ 00.000 (3) |  000.475 $\pm$ 0.000 (2) | 0.013 $\pm$ 0.000 (1)
Echocardiogram |  009.038 $\pm$ 01.000 (4) |  09.564 $\pm$ 02.000 (5) |  000.304 $\pm$ 00.000 (3) |  000.093 $\pm$ 0.000 (2) | 0.002 $\pm$ 0.000 (1)
Wisconsin Breast Cancer |  029.246 $\pm$ 02.000 (5) |  06.837 $\pm$ 01.000 (4) |  001.187 $\pm$ 00.000 (3) |  000.461 $\pm$ 0.000 (2) | 0.003 $\pm$ 0.000 (1)
Loan House |  010.798 $\pm$ 01.000 (4) | 52.793 $\pm$ 07.000 (5) |  006.751 $\pm$ 02.000 (3) |  000.524 $\pm$ 0.000 (2) | 0.002 $\pm$ 0.000 (1)
Heart Failure |  028.395 $\pm$ 01.000 (5) | 23.747 $\pm$ 10.000 (4) |  001.473 $\pm$ 00.000 (3) |  000.201 $\pm$ 0.000 (2) | 0.002 $\pm$ 0.000 (1)
Heart Disease |  015.565 $\pm$ 02.000 (4) | $n>12$ |  004.446 $\pm$ 01.000 (3) |  000.636 $\pm$ 0.000 (2) | 0.002 $\pm$ 0.000 (1)
Adult |  086.241 $\pm$ 12.000 (4) | $n>12$ |  026.012 $\pm$ 07.000 (3) |  022.321 $\pm$ 1.000 (2) | 0.071 $\pm$ 0.000 (1)
Bank Marketing | 153.494 $\pm$ 38.000 (4) | $n>12$ | 129.428 $\pm$ 08.000 (3) |  054.545 $\pm$ 1.000 (2) | 0.072 $\pm$ 0.000 (1)
Congressional Voting |  032.935 $\pm$ 03.000 (4) | $n>12$ |  006.503 $\pm$ 01.000 (3) |  004.100 $\pm$ 7.000 (2) | 0.002 $\pm$ 0.000 (1)
Absenteeism |  028.941 $\pm$ 01.000 (4) | $n>12$ |  014.045 $\pm$ 03.000 (3) |  003.893 $\pm$ 0.000 (2) | 0.003 $\pm$ 0.000 (1)
Hepatitis |  028.427 $\pm$ 01.000 (4) | $n>12$ |  002.273 $\pm$ 01.000 (3) |  000.023 $\pm$ 0.000 (2) | 0.002 $\pm$ 0.000 (1)
German |  012.307 $\pm$ 02.000 (4) | $n>12$ |  003.141 $\pm$ 01.000 (2) |  010.288 $\pm$ 0.000 (3) | 0.003 $\pm$ 0.000 (1)
Mushroom |  058.810 $\pm$ 70.000 (4) | $n>12$ |  012.507 $\pm$ 02.000 (3) |  000.507 $\pm$ 0.000 (2) | 0.007 $\pm$ 0.000 (1)
Credit Card | 111.425 $\pm$ 36.000 (3) | $n>12$ |  004.416 $\pm$ 00.000 (2) | 298.572 $\pm$ 6.000 (4) | 0.351 $\pm$ 0.000 (1)
Horse Colic |  009.811 $\pm$ 01.000 (4) | $n>12$ |  000.316 $\pm$ 00.000 (2) |  002.365 $\pm$ 2.000 (3) | 0.002 $\pm$ 0.000 (1)
Thyroid |  035.965 $\pm$ 13.000 (2) | $n>12$ |  038.287 $\pm$ 15.000 (3) | 109.123 $\pm$ 3.000 (4) | 0.013 $\pm$ 0.000 (1)
Cervical Cancer |  013.465 $\pm$ 02.000 (4) | $n>12$ |  002.760 $\pm$ 01.000 (3) |  000.126 $\pm$ 0.000 (2) | 0.006 $\pm$ 0.000 (1)
Spambase |  041.983 $\pm$ 05.000 (4) | $n>12$ |  019.289 $\pm$ 06.000 (3) |  004.576 $\pm$ 0.000 (2) | 0.036 $\pm$ 0.000 (1)
Mean | 44.745 $\pm$ 38.655 (4) | - | 13.618 $\pm$ 27.539 (2) |  023.334 $\pm$ 66.445 (3) | 0.027 $\pm$ 0.075 (1)
Mean Reciprocal Rank |  00.244 $\pm$ 00.037 (4) |  00.243 $\pm$ 00.042 (5) |  00.352 $\pm$ 00.063 (3) |  000.462 $\pm$ 00.084 (2) | 1.000 $\pm$ 1.000 (1)
Iris |  07.245 $\pm$ 01.000 (5) |  02.959 $\pm$ 00.000 (4) |  00.968 $\pm$ 00.000 (3) |  000.016 $\pm$ 00.000 (2) | 0.001 $\pm$ 0.000 (1)
Balance Scale | 11.614 $\pm$ 02.000 (5) | 10.123 $\pm$ 09.000 (4) |  08.180 $\pm$ 01.000 (3) |  000.038 $\pm$ 00.000 (2) | 0.002 $\pm$ 0.000 (1)
Car | 23.721 $\pm$ 03.000 (3) | 46.910 $\pm$ 43.000 (5) | 29.688 $\pm$ 10.000 (4) |  000.239 $\pm$ 00.000 (2) | 0.005 $\pm$ 0.000 (1)
Glass | 30.142 $\pm$ 02.000 (5) |  05.486 $\pm$ 00.000 (3) | 12.975 $\pm$ 05.000 (4) |  000.180 $\pm$ 00.000 (2) | 0.002 $\pm$ 0.000 (1)
Contraceptive | 13.165 $\pm$ 02.000 (5) | 12.670 $\pm$ 02.000 (4) |  03.952 $\pm$ 01.000 (3) |  000.262 $\pm$ 00.000 (2) | 0.003 $\pm$ 0.000 (1)
Solar Flare | 22.108 $\pm$ 02.000 (4) | 25.652 $\pm$ 03.000 (5) | 14.733 $\pm$ 02.000 (3) |  000.544 $\pm$ 00.000 (2) | 0.004 $\pm$ 0.000 (1)
Wine | 30.096 $\pm$ 01.000 (4) | 58.486 $\pm$ 10.000 (5) |  00.128 $\pm$ 00.000 (2) |  000.543 $\pm$ 00.000 (3) | 0.002 $\pm$ 0.000 (1)
Zoo | 19.259 $\pm$ 07.000 (4) | $n>12$ |  09.560 $\pm$ 03.000 (3) |  000.015 $\pm$ 00.000 (2) | 0.002 $\pm$ 0.000 (1)
Lymphography |  07.890 $\pm$ 01.000 (4) | $n>12$ |  04.359 $\pm$ 01.000 (3) |  000.143 $\pm$ 00.000 (2) | 0.002 $\pm$ 0.000 (1)
Segment | 16.178 $\pm$ 03.000 (4) | $n>12$ |  02.967 $\pm$ 01.000 (2) |  014.315 $\pm$ 01.000 (3) | 0.016 $\pm$ 0.000 (1)
Dermatology |  09.909 $\pm$ 03.000 (3) | $n>12$ |  01.722 $\pm$ 01.000 (2) |  020.708 $\pm$ 06.000 (4) | 0.003 $\pm$ 0.000 (1)
Landsat | 38.134 $\pm$ 11.000 (3) | $n>12$ | 33.831 $\pm$ 11.000 (2) | 830.055 $\pm$ 09.000 (4) | 0.052 $\pm$ 0.000 (1)
Annealing | 36.187 $\pm$ 03.000 (3) | $n>12$ |  01.364 $\pm$ 00.000 (2) | 104.566 $\pm$ 24.000 (4) | 0.007 $\pm$ 0.000 (1)
Splice | 19.203 $\pm$ 02.000 (3) | $n>12$ |  02.877 $\pm$ 01.000 (2) | > 60 min | 0.019 $\pm$ 0.000 (1)
Mean | 20.347 $\pm$ 10.214 (3) | - |  09.093 $\pm$ 10.632 (2) |  074.740 $\pm$ 228.754 (4) | 0.009 $\pm$ 0.014 (1)
Mean Reciprocal Rank |  00.266 $\pm$ 00.056 (4) |  00.241 $\pm$ 00.048 (5) |  00.393 $\pm$ 00.100 (2) |  000.383 $\pm$ 000.126 (3) | 1.000 $\pm$ 1.000 (1)

##  Appendix D Hyperparameters

In the following, we report the hyperparameters used for each approach. The
hyperparameters were selected based on a random search over a predefined
parameter range for GDT, CART and GeneticTree and are summarized in Table 8 to
Table 11. All parameters that were considered are noted in the tables. The
number of trials was equal for each approach. For GDT and DNDT, we did not
optimize the batch size as well as the number of epochs, but used early
stopping with a predefined patience of $200$. Additionally, we used $3$ random
restarts to prevent bad initial parametrizations and selected the best model
based on the validation loss. A gradient-based optimization allows using an
arbitrary loss function for the optimization. During preliminary experiments,
we observed that it is beneficial to adjust the loss function for specific
datasets. More specifically, we considered the binary crossentropy and the
focal loss [22] with a focal factor of $3$. Additionally, we considered using
PolyLoss [20] within the HPO to tailor the loss function for the specific
task. For DL8.5 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 Demirović et al. [10] and Aglin et al. [3]. Running the
experiments with a 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 Yang et al.
[37]. However, it has to be restricted to $1$ in order to generate binary
trees for comparability reasons. Therefore, we only optimized the temperature
and the learning rate. Furthermore, 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 Appendix D.

Table 8: GDT Hyperparameters

Dataset Name | depth | lr_index | lr_values | lr_leaf | index_activation | loss | polyLoss | polyLossEpsilon
---|---|---|---|---|---|---|---|---
Blood Transfusion | 8 | 0.010 | 0.100 | 0.010 | entmax | crossentropy | False | 2
Banknote Authentication | 7 | 0.050 | 0.050 | 0.100 | entmax | focal_crossentropy | True | 2
Titanic | 10 | 0.005 | 0.010 | 0.010 | entmax | crossentropy | False | 2
Raisins | 10 | 0.005 | 0.005 | 0.100 | entmax | crossentropy | True | 5
Rice | 7 | 0.050 | 0.010 | 0.010 | entmax | crossentropy | False | 2
Echocardiogram | 8 | 0.010 | 0.050 | 0.100 | entmax | crossentropy | True | 5
Wisconsin Diagnostic Breast Cancer | 10 | 0.050 | 0.010 | 0.100 | entmax | crossentropy | True | 2
Loan House | 8 | 0.005 | 0.100 | 0.010 | entmax | focal_crossentropy | False | 2
Heart Failure | 10 | 0.005 | 0.250 | 0.100 | entmax | crossentropy | False | 2
Heart Disease | 9 | 0.010 | 0.050 | 0.005 | entmax | focal_crossentropy | False | 2
Adult | 8 | 0.050 | 0.005 | 0.050 | entmax | crossentropy | True | 5
Bank Marketing | 8 | 0.250 | 0.250 | 0.050 | entmax | crossentropy | False | 2
Cervical Cancer | 8 | 0.005 | 0.010 | 0.100 | entmax | crossentropy | True | 2
Congressional Voting | 10 | 0.005 | 0.050 | 0.010 | entmax | focal_crossentropy | True | 5
Absenteeism | 10 | 0.050 | 0.010 | 0.050 | entmax | focal_crossentropy | True | 5
Hepatitis | 10 | 0.005 | 0.050 | 0.010 | entmax | focal_crossentropy | True | 5
German | 7 | 0.005 | 0.050 | 0.010 | entmax | crossentropy | True | 2
Mushroom | 9 | 0.010 | 0.010 | 0.050 | entmax | focal_crossentropy | False | 2
Credit Card | 8 | 0.050 | 0.100 | 0.010 | entmax | focal_crossentropy | False | 2
Horse Colic | 8 | 0.250 | 0.250 | 0.010 | entmax | focal_crossentropy | False | 2
Thyroid | 8 | 0.010 | 0.010 | 0.050 | entmax | crossentropy | False | 2
Spambase | 10 | 0.005 | 0.010 | 0.010 | entmax | crossentropy | False | 2
Iris | 7 | 0.005 | 0.005 | 0.05 | entmax | crossentropy | False | 2
Balance Scale | 8 | 0.050 | 0.010 | 0.10 | entmax | crossentropy | True | 5
Car | 9 | 0.010 | 0.010 | 0.01 | entmax | focal_crossentropy | False | 2
Glass | 10 | 0.050 | 0.050 | 0.05 | entmax | focal_crossentropy | True | 5
Contraceptive | 7 | 0.010 | 0.050 | 0.01 | entmax | crossentropy | False | 2
Solar Flare | 8 | 0.005 | 0.010 | 0.20 | entmax | focal_crossentropy | True | 2
Wine | 10 | 0.010 | 0.050 | 0.01 | entmax | focal_crossentropy | False | 2
Zoo | 9 | 0.050 | 0.010 | 0.10 | entmax | focal_crossentropy | True | 2
Lymphography | 8 | 0.050 | 0.010 | 0.05 | entmax | crossentropy | True | 2
Segment | 7 | 0.005 | 0.005 | 0.05 | entmax | crossentropy | False | 2
Dermatology | 7 | 0.010 | 0.010 | 0.10 | entmax | crossentropy | True | 2
Landsat | 8 | 0.005 | 0.010 | 0.05 | entmax | crossentropy | True | 5
Annealing | 10 | 0.250 | 0.050 | 0.01 | entmax | crossentropy | False | 2
Splice | 9 | 0.010 | 0.005 | 0.05 | entmax | crossentropy | False | 2

Table 9: DNDT Hyperparameters

Dataset Name | learning_rate | temperature | num_cut
---|---|---|---
Blood Transfusion | 0.050 | 0.100 | 1
Banknote Authentication | 0.001 | 0.100 | 1
Titanic | 0.050 | 0.001 | 1
Raisins | 0.050 | 0.001 | 1
Rice | 0.100 | 0.010 | 1
Echocardiogram | 0.005 | 1.000 | 1
Wisconsin Diagnostic Breast Cancer | 0.100 | 0.010 | 1
Loan House | 0.001 | 1.000 | 1
Heart Failure | 0.005 | 1.000 | 1
Iris | 0.050 | 0.100 | 1
Balance Scale | 0.005 | 0.100 | 1
Car | 0.010 | 0.010 | 1
Glass | 0.100 | 0.010 | 1
Contraceptive | 0.001 | 0.010 | 1
Solar Flare | 0.050 | 0.100 | 1
Wine | 0.001 | 0.100 | 1

Table 10: GeneticTree Hyperparameters

Dataset Name | n_thresholds | n_trees | max_iter | cross_prob | mutation_prob
---|---|---|---|---|---
Blood Transfusion | 10 | 500 | 500 | 1.0 | 0.2
Banknote Authentication | 10 | 500 | 500 | 0.8 | 0.6
Titanic | 10 | 500 | 250 | 0.2 | 0.3
Raisins | 10 | 100 | 50 | 1.0 | 0.6
Rice | 10 | 100 | 250 | 0.4 | 0.3
Echocardiogram | 10 | 50 | 100 | 0.8 | 0.4
Wisconsin Diagnostic Breast Cancer | 10 | 250 | 100 | 0.2 | 0.7
Loan House | 10 | 500 | 500 | 1.0 | 0.2
Heart Failure | 10 | 500 | 50 | 0.4 | 0.6
Heart Disease | 10 | 400 | 500 | 0.6 | 0.4
Adult | 10 | 100 | 500 | 0.6 | 0.6
Bank Marketing | 10 | 500 | 250 | 0.8 | 0.6
Cervical Cancer | 10 | 100 | 500 | 0.4 | 0.9
Congressional Voting | 10 | 500 | 500 | 1.0 | 0.7
Absenteeism | 10 | 500 | 500 | 1.0 | 0.7
Hepatitis | 10 | 500 | 250 | 0.2 | 0.3
German | 10 | 250 | 500 | 0.4 | 0.8
Mushroom | 10 | 400 | 500 | 0.6 | 0.4
Credit Card | 10 | 50 | 50 | 0.4 | 0.1
Horse Colic | 10 | 50 | 100 | 0.8 | 0.4
Thyroid | 10 | 500 | 500 | 1.0 | 0.7
Spambase | 10 | 250 | 500 | 0.8 | 0.6
Iris | 10 | 100 | 500 | 1.0 | 0.5
Balance Scale | 10 | 500 | 250 | 0.6 | 0.4
Car | 10 | 500 | 500 | 1.0 | 0.7
Glass | 10 | 500 | 500 | 0.8 | 0.6
Contraceptive | 10 | 250 | 500 | 0.4 | 0.5
Solar Flare | 10 | 500 | 250 | 0.6 | 0.4
Wine | 10 | 100 | 50 | 0.2 | 0.8
Zoo | 10 | 500 | 500 | 1.0 | 0.7
Lymphography | 10 | 500 | 250 | 0.6 | 0.4
Segment | 10 | 100 | 500 | 0.4 | 0.9
Dermatology | 10 | 100 | 500 | 1.0 | 0.5
Landsat | 10 | 500 | 500 | 1.0 | 0.7
Annealing | 10 | 100 | 500 | 0.4 | 0.9
Splice | 10 | 100 | 250 | 0.2 | 0.8

Table 11: CART Hyperparameters

Dataset Name | max_depth | criterion | max_features | min_samples_leaf | min_samples_split | ccp_alpha
---|---|---|---|---|---|---
Blood Transfusion | 9 | entropy | None | 1 | 5 | 0.0
Banknote Authentication | 9 | gini | None | 1 | 5 | 0.0
Titanic | 7 | entropy | None | 1 | 50 | 0.0
Raisins | 8 | gini | None | 5 | 2 | 0.2
Rice | 8 | gini | None | 5 | 2 | 0.2
Echocardiogram | 9 | entropy | None | 1 | 5 | 0.0
Wisconsin Breast Cancer | 7 | entropy | None | 5 | 2 | 0.4
Loan House | 10 | entropy | None | 10 | 2 | 0.0
Heart Failure | 9 | gini | None | 5 | 50 | 0.0
Heart Disease | 8 | entropy | None | 5 | 10 | 0.0
Adult | 10 | entropy | None | 10 | 2 | 0.0
Bank Marketing | 8 | entropy | None | 5 | 10 | 0.0
Cervical Cancer | 9 | entropy | None | 1 | 5 | 0.0
Congressional Voting | 10 | gini | None | 1 | 2 | 0.0
Absenteeism | 7 | entropy | None | 1 | 10 | 0.0
Hepatitis | 9 | entropy | None | 1 | 5 | 0.0
German | 7 | entropy | None | 1 | 10 | 0.0
Mushroom | 9 | entropy | None | 1 | 5 | 0.0
Credit Card | 9 | gini | None | 1 | 5 | 0.0
Horse Colic | 10 | entropy | None | 10 | 2 | 0.0
Thyroid | 10 | entropy | None | 10 | 2 | 0.0
Spambase | 10 | gini | None | 1 | 2 | 0.0
Iris | 8 | entropy | None | 5 | 10 | 0.0
Balance Scale | 9 | entropy | None | 1 | 5 | 0.0
Car | 9 | gini | None | 1 | 5 | 0.0
Glass | 9 | gini | None | 1 | 5 | 0.0
Contraceptive | 9 | entropy | None | 1 | 5 | 0.0
Solar Flare | 7 | entropy | None | 1 | 50 | 0.0
Wine | 9 | gini | None | 1 | 5 | 0.0
Zoo | 10 | gini | None | 1 | 2 | 0.0
Lymphography | 7 | entropy | None | 1 | 10 | 0.0
Segment | 9 | entropy | None | 1 | 5 | 0.0
Dermatology | 9 | gini | None | 1 | 5 | 0.0
Landsat | 10 | gini | None | 1 | 2 | 0.0
Annealing | 9 | gini | None | 1 | 5 | 0.0
Splice | 9 | gini | None | 1 | 5 | 0.0