Feature Learning for Interpretable, Performant Decision Trees
Authors: Jack Henry Good
Torin Kovach
Kyle Miller
Artur Dubrawski
Venue: NeurIPS 2023 poster (2023)
Keywords: explainability
interpretability
decision tree
feature learning

Abstract: Decision trees are regarded for high interpretability arising from their hierarchical partitioning structure built on simple decision rules. However, in practice, this is not realized because axis-aligned partitioning of realistic data results in deep trees, and because ensemble methods are used to mitigate overfitting. Even then, model complexity and performance remain sensitive to transformation of the input, and extensive expert crafting of features from the raw data is common. We propose the first system to alternate sparse feature learning with differentiable decision tree construction to produce small, interpretable trees with good performance. We benchmark against conventional tree-based models and demonstrate several notions of interpretation of a model and its predictions.

Feature Learning for Interpretable, Performant Decision Trees
Jack H. Good, Torin Kovach, Kyle Miller, Artur Dubrawski Carnegie Mellon University
(jhgood, tkovach mille866, avddeend cmu, edu
Abstract
Decision trees are regarded for high interpretability arising from their hierarchical partitioning structure built on simple decision rules. However, in practice, this not realized because axis-aligned partitioning of realistic data results in deep trees, and because ensemble methods are used to mitigate overfitting. Even then, model complexity and performance remain sensitive transformation of the input. and extensive expert crafting of features from the raw data is common. We propose the first system to alternate sparse feature learning with differentiable decision tree construction to produce small, interpretable trees with good performance. It benchmarks favorably against conventional free-based models and demonstrates several notions interpretability of a model and its predictions.
1 Introduction
In recent years, Al has made its way into increasingly critical applications, leading to the popu- larization of the topic of Trustworthy AI; Al should not only perform well in its primary task, but exhibit properties that earn trust, such as robustness, provable adherence to safety specifications, and interpretability to humans. For example, predictors that assist medical diagnosis are more useful and more likely to be trusted if their predictions are easily understood by medical personnel.
Interpretability is highly subjective and application-dependent by nature, and there is no universal standard of what makes a system highly interpretable. However, within machine learning (ML). there are some generally agreed-uper uppn rules of thumb; for example, smaller models are considered more interpretable than structurally similar but larger ones, and rule-based representations such as decision trees are considered more interpretable than "black box" models such as neural networks.
Decision trees in particular often used the quintessential example of interpretable MI:; they can be interpreted holistically (also called global interpretation) as a hierarchical partitioning of the input based on simple decision rules, and individual predictions can be interpreted (also called called local interpretation) as series of such rules on a path from the tree's root to leaf. Conventionally, these decision rules have the form x; E for some feature i of input vector x and decision threshold t, thus representing axis-aligned hyperplanes in the input space, but many other decision rules are possible. For example, rules of the form Σ, a,T; b for some a, b are called oblique splits, and the trees using them oblique decision trees (ODTs).
In practice, however, there barriers the practical application of decision models. First, due to various factors such as greedy growth, axis-aligned decision rules, and the lack of any objective promote robust, large-margin predictions, they tend generalize poorly yet-unseen data; while this can be somewhat alleviated by pruning, the most effective and popular solution use large ensembles with strategies such bagging as Random Forests (2, random thresholds as in ExtraTrees [22]] or boosting as in XGBoost [.]. In addition, decision trees often grow quite deep and many decision rules for any given prediction, even for extremely simple data. Together, these make both global and local interpretation much more difficult.
interpretable
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a) A decision tree is relatively complex and generalizes poorly.
(b) random forest is very complex and gen- eralizes better, but not perfectly.
(c) After rotation, de- cision tree is simple and generalizes per- feetly.
(d) Other needs a different transforma- tion to learn simple, general tree.
Figure I: An example of trees fitted to toy data to motivate the potential benefit of learning simple feature transforms. Points were sampled uniformly in the bands denoted by dashed lines.
We posit that these barriers are due, at least in part, to the sensitivity of decision trees transfor- mations of the input resulting from greedy construction and simple decision rules. Of these, key limitation the latter; even if we replace greedy construction with a perfect tree learner, simple distributions can nonetheless require an arbitrarily large axis-aligned tree to fit. However, after transformation of that distribution, even a greedy algorithm can produce a small tree, as shown in Sec- tion 3.5 Figure gives motivating example of case where trees do poorly interpretable learners on simple data, but succeed after a transformation. The sensitivity to the feature representation also related to other limitations of rree-based models, such as their dependence features hand-crafted using expert knowledge to achieve good performance on some problems, and their overall weakness on other problems, such image classification.
This motivates the idea of learning transformations of the input features, or equivalently, more expressive decision rules such oblique splits, to strike balance between complexity of the rules and complexity of the overall model. This learning problem not easy; axis-aligned decision rule learning, as in the popular CART algorithm [8]. is only practical because the search is restricted to finite set candidate rules that is efficiently exhaustively scarchable. However, finding even optimal oblique splits, which are among the simplest decision rules, is NP-Hard (26). and even oblique splits may not be considered interpretable unless they are sparse, that is, having few nonzero coefficients.
Nonetheless, methods have been developed to learn such trees, either by heuristically choosing splits in a tree construction process, or by constructing an axis-aligned tree and then optimizing the parameters of the splits (see Section 2 for examples). However, these suffer from either greedy, suboptimal choice split, or from keeping the original structure of the tree. They are also usually restricted to certain kind of split, such as oblique splits.
Here we propose a novel, flexible framework that is the first alternate optimization of feature transformation parameters with complete regrowth of the tree. This is made possible by recent advances in fuzzy decision tree methods. Refitting the tree completely throughout training reshapes the tree and moves thresholds as needed; it also maintains the property that each splitting rule is maximally informative given the available features and data. Together these result in smaller, more interpretable trees for a given performance. Moreover, the flexibility of this framework to support various feature transformations provides a foundation for future work focusing on interpretable prediction with other data modalities, such as images and time series.
Related Work
Decision trees are one of the oldest techniques in machine learning still widely in use today. has long been known that constructing optimal binary decision trees is NP-Complete 229. so most algorithms use greedy approach "grow" a tree from root leaf by successively partitioning the data by choosing the split that maximally improves the purity of labels in each partition. The partitions are usually axis-aligned, that is, involving only one feature of the input, to make the search practical. One of the most popular decision tree algorithms today is Classification And Regression Trees (CART) [8) Unconstrained decision trees can always fit separable data perfectly, but are prone to overfitting; to improve generalization, growth can be constrained, but more often, trees used in

---

randomized ensembles such as random forests [9] and ExtraTrees [22], or in boosted ensembles such as AdaBoost [9] and XGboost [T].
There is extensive work using decision trees extracted from more complex models either to entirely
replace the model, or as interpretable proxy. Examples include 12
37
4
3
35
36
25
Other work attempts to improve the interpretability of decision trees themselves by introducing new decision rules. These rules are more complex than the axis-aligned threshold rules, but compensate by improving performance single-tree models while reducing their size. For example, [6] uses a branch-and-bog aal-und---udddddd--- algorithm search for bivariate splits. [16 17 23 use parallel coordinates, which incorporate information from multiple data features while being easy to visualize. [13 uses bilevel
optimization to find nonlinear splits for growing trees.
The most common augmented decision rule, however, is linear splits, that is, splitting using arbitrary hyperplanes rather than axis-aligned hyperplanes. These are often called oblique splits, and the trees that use them oblique decision trees (ODTs). Algorithms for growing ODTs are first proposed along with CART and proposes a heuristic using randomization and deterministic hill climbing.
[
34 later discusses the difficulty of finding optimal linear splits due to local minima
Another approach is to grow an axis- axis-aligned tree, fix the structure, then treat it as parametric model in order learn coefficients for linear splits. This can be made possible using fuzzy splits, wherein a decision is weighted combination of both subtrees rather than wholly one or the other, to make the tree differentiable. These have gone by names such as fuzzy, soft, neural, or differentiable decision trees; we use fuzzy decision trees (FDTs) as an umbrella term. In the case of ODTs, a splitting function such as sigmoid is used to map a linear combination of feature values to the weight of each subtree. 42 is the first to train globally optimized trees in this way. Later, (32) proposes ensembles of such trees, both as standalone models and as the final layer of neural architecture, [33] presents various improvements such as balance and sparsity regularizations and dynamic learning rate adjustments, and 40) applies them to reinforcement learning.
Tree Alternating Optimization (TAO) is a recent and successful ODT learning algorithm that initializes similarly, but unlike FDTs, uses a linear discriminator each node, such as logistic regression or linear SVM, then alternates optimization over each depth level of the tree. It can be used with a sparsity penalty to produce sparse ODTs, that is, where many or most of the coefficients are 0, making linear splits more interpretable. While it is shown that this alternating optimization never causes the loss to increase, there are no convergence or approximation guarantees. was initially proposed for classification [10,, then extended in various ways, including regression ensembles [55; boosted ensembles [21]: clustering [20]; semi-supervised learning [46]; interpretable image classification 41: interpretable natural language processing [28 and as tool for understanding parts of neural
networks 27].
Our approach is different from any existing work in that we consider broader scope of feature types, but more importantly, in that we continually and completely refit the decision tree throughout the learning process; this requires an efficient differentiable decision tree. For this, we rely on Kernel Density Decision Trees (KDDTss) (24, a recently proposed FDT that represents uncertainty through kernels rather than splitting functions and learns axis-aligned fuzzy splits using a generalization of CART. The kernel representation also has the benefit avoiding redundant splitting that may occur in other FDT formalisms because repeating similar splits can make the division less "fuzzy" and therefore reduce loss by inflating the tree size. See the paper for background on axis-aligned FDTs. Our approach is also unique in that, for each output of the feature transformation. we weight the regularization by how much the feature is used for decisions in the training data, resulting in a more balanced enforcement of sparsity throughout the tree.
3 Methods
3.1 Alternating optimization trees and features
Given training data with features X E Rexp and regression targets or one-hot class label vectors Y E Raxg we aim to learn parameters 0 E Rd of feature transformation So IR + RRF and decision tree T ; I2p + R to minimize a loss function L( T, X, Y) for the composed predictive
3

---

model T' fo. The tree is typically subject to constraints such as a max depth, minimum sample weight per node, or cost-complexity pruning.
Viewed within this framework, the prevailing approach in prior work is equivalent to the following process: (1) initialize 0 such that fo is identity; (2) with 0 fixed, optimize T using greedy tree growth strategy such as CART; (3) with I' fixed, optimize 0 using gradient- optimization. Some methods use a growing and/or pruning heuristic during (3) so that the structure of 'I' may change.
Instead, we propose an approach inspired by alternating optimization, a common strategy to prag- matically solve difficult optimization problems. whereby alternate fitting a tree as in (2) with one or more gradient-base based updates to as in (3). In this case, alternating allows us to use different optimization strategies for the feature transform parameters 0 and the non-parametric decision tree T. At the end, we can use the fuzzy tree T, or replace its fuzzy splits with conventional crisp splits; the latter improves interpretability when predictions would otherwise take multiple paths, but can result in small drop in performance.
3.2 Efficient differentiable trees
Conventional decision trees are piecewise-consaant so there is no meaningful loss gradient with respect to Instead, we use kernel density decision trees (KDDTs) (4), type of fuzzy decision tree that interprets inputs with local uncertainty defined by kernel function. In essence, they fit using kernel density estimate computed from X rather than the raw values, and predictions are smoothed over the same kernel. This smoothing makes both the predictions and loss differentiable. KDDTs are fitted using an efficient generalization CART, making them suitable for applications such as this where frequently repeated fitting makes efficiency crucial.
Here we present a simplified formulation of KDDTs focus on this use case. KDDT T RP - is defined by underlying decision tree To RP +
IR" and product kernel k Re - IR with k(x) I (1:). and F; the marginal CDF of the kernel along each dimension í. For the KDDT fitting algorithm, each F' must be piecewise-constant, but this restriction does not apply for prediction; for example, one might use a histogram approximation of a Gaussian distribution for fitting and the Gaussian itself for prediction.
Then the KDDT is the output element-wise convolution T()) = T k: Suppose To partitions Rº into hyper-interval leaves L C R2P with bounds L1,i, ur.,i (which may be -o or oo) on each dimension i. Each leaf has value Vz. IR9, Then the prediction is
T (x) (I * k)(x) Σ (L(()
where μr, is the leaf membership function (x( = IhE Pi(xs Cr.s) - B(a;; un,;) and
VL E R9 is the leaf value v2 = Eignn (2 22 (X,)a The Jacobian is thus
VeyT(x) = [x)L
(x) = - -1,i) 1 Ff(2; u1,))) II F. (1,5) -F(x; u,,s) 8'
using the same traversal algorithm to compute from [24]. Trees are fitted using information gain based on an impurity measure, so the same impurity should be used as the loss function for feature learning. For classification, we use the Gini index; the resulting loss function, including the feature transformation f. is C( X, Y) n Σn w1(1 vf.vz) with wn = Σiein (foff(X)) the sample weight at leaf T.. Then we compute the loss gradient VoL in terms of μ., Vp, and VoJ. using the sparsity of yu for efficient computation during tree traversal. For regression, of regression target values as the impurity, which can be expressed as a shifted version of the Gini loss, the gradient computation is the same.
use variance
3.3 Kernel choice
In this context, the kernel is mainly used as smoother to make the tree differentiable, so the choice of shape is not crucial. Good choices a uniform (box) or Gaussian kernel. However, the size of

---

the kernel relative to the scale of the input is important: we adopt the term bandwidth from kernel density estimation describe kernel scaling. If the bandwidth is too small, KDDT is very close to a conventional decision tree, and the loss gradient is either zero or highly unstable because it results from very few data near split boundaries; if the bandwidth too large, however, splits are very soft, the tree grows large, the discriminative power is weak, and computation is slow due to dense membership of data in leaves. To control the bandwidth, we use one of two strategies: (I) design the feature transform that the output range is limited, for example, to [0, 1], and choose appropriate kernel bandwidth; or (2) use a regularization on the feature transform parameters to automatically scale the feature outputs appropriately relative to the kernel. We generally find the latter approach to be more effective and describe the use of regularizations in detail in Section 3.3
Another related consideration is the support of the kernel, that is, the size of the range on which has nonzero density. In general, the larger the support, the more decision paths that data belong to, increasing the cost of fitting, gradient computation, and prediction (if using kernel during prediction). For example, a Gaussian kernel truncated at standard deviations and another with the same variance but truncated at 6 standard deviations are nearly identical, but the latter is more computationally expensive to use with a KDDT.
3.4 Parameterized feature transforms
In principle, any differentiable parameterized class of feature transforms can be used, ranging from simple linear transforms as in ODTs to expressive classes of functions such as MLPs that have high discriminative power on their own. Generally, more expressive feature transforms result in smaller trees, but are probably less interpretable, depending on the application. The goal then is to choose expressive feature classes that remain interpretable in the desired context when conjoined into rule list, as in the decision path of a tree.
In this work, we focus primarily on tabular data, to which tree-based models are most successfully applied, and suggest some general feature transformation primitives based on feature engineering techniques typically used with tree-based models. These can be composed, or their outputs concate- nated so different kinds of transforms can be used together in the tree. We generally recommend starting with linear and prototype features, then proceeding with whatever improves performance while meeting interpretability requirements for the application.
Before describing the primitives, we note a general consideration for features used with decision trees: decision trees consider only the order of inputs and not the distance between values. While this is not strictly true for fuzzy decision trees such as KDDT's, it is best to avoid adding unnecessary feature complexity by using element- wise monotonic transformations of features, such as bias terms, monotonic activation functions, etc., on the final output of the feature transformation.
Identity. It may be beneficial include the original, unmodified features along with transformed features so that the simplest possible rules are considered during construction of the tree. This also, in some sense, safeguards against situations where transformed features may actually be less informative than the original features.
Element-wiss transformation. As noted above, element- wise monotonic transformations are largely meaningless on their own, but can be useful if composed with other transforms. For example, the composition of element-wise square with linear transformation allows for conic decision rules. Some element- wise mappings worth considering have no parameters, such as x ++ exp(x) and x -> log(:); others have parameters to be learned, such + x." A notable option is the element-wise shifted power transformation
sgnla+aa)) san(u+a)22ta"" M(+ta)+
A + 0
(a + az)sg((r + at log(z + a))
X = 0
which is used to alter distribution shape, typically to make values more normally distributed.
Linear transformation. The linear transformation is x +> Ax + b with weights A and bias b. The bias is used only if composing with another primitive. Using only a linear transformation results in an ODT. These can be initialized randomly, as identity, or using linear dimension reduction strategy such PCA.
5

---

data
LR
MLP
DT
RF
ET
XGB
linear
ours:
proto
R. P. g
fuzzy
crisp
fuzzy
crisp
iris [18]
0.960
0.953
0.947
0.947
0.953
0.947
0.960
0.960
0.947
0.927
150, 4 (4), 3
6.4
7.2c2
2.1e3
4.3e2
6.1
7.6
6.5
2.9
heart-disease 30
0.822
0.792
0.707
0.802
0.795
0.792
0.812
0.812
0.793
0.779
303, 13 (20). 2
13.9
4.8c3
1.1e4
7.9c2
21.6
19.4
5.0
3.9
dry-hcan 30
0.925
0.934
0.912
0.923
0.921
0.928
0.920
0.913
0,915
0.901
13611, 16 (16), 7
99.8
6.7c4
2.0c5
1.3e4
1.1c2
45.8
1.6c2
94.2
wine [1]
0.983
0.989
0.904
0.977
0.989
0.955
0.983
0.983
0.961
0.961
178, 13 (13), 3
8.5
9.4c2
3.3c3
2.4c2
2.0
2.0
2.3
2.3
car [
0.926
0.992
0.977
0,964
0,971
0.994
0.991
0,992
0,980
0.979
1728, 6 (21). 4
95.3
2.3e4
3.1e4
4.Se3
29.0
29.0
59.5
55.9
wdbc [4
0.974
0.975
0.935
0.965
0.970
0.968
0.972
0.972
0.961
0.961
569, 30 (30), 2
13.0
1.9e3
6.0e3
2.7e2
1.3
1.3
6.4
5.0
sonar (3
0.755
0.879
0.735
0.826
0,880
0.855
0.818
0.799
0.798
0.817
208, 60 (60),
14.1
2.0c3
5.6c3
3.0e2
5.7
3.9
10.3
10.3
pendigits 2
0.952
0.994
0.964
0.993
0.994
0.991
0.981
0.976
0,950
0.931
10992, 16 (16), 10
3.2c2
3.8c4
9.8c4
8,5c3
2.6c2
2,4c2
3.1c2
3.1c2
ionosphere [39
0.875
0.917
0.892
0.934
0.943
0.943
0.932
0.920
0.920
0.909
351, 34 (34), 2
15.5
2.2c3
5.9e3
3.4e2
3.9
5.5
10.0
6.3
Table 1: Results of tabular data benchmarks. Number of attributes p is listed before and after one-hot encoding categorical attributes. Each cell shows 10-fold cross-validation accuracy and average number of splits. The best accuracy for each data set is in bold.
Distance to prototype. Another feature type maps point to its distance to each of l prototypes Pá in this sense, decision rule d(x, p:: S,) can be interpreted simply "is x sufficiently similar to p,". We use Mahalanobis distance d(x, S.) (x P,) (x P:). where the learnable parameters are prototypes Pa and inverse covariance matrices S The covariance matrix can be reparameterized in various ways to restrict the measurement of distance"] for example, by making it diagonal, or by using the same for all prototypes. It should also be parameterized such that it is positive semidefinite; otherwise hyperbolic decision rules may be learned and the distance interpretation no longer applies. S,1 can be regularized for sparsity, so that the distance is based on few features. The parameters can be initialized randomly or by using a mixture modeling algorithm.
Fuzzy cluster membership. Clustering partitions data into k clusters with high internal similarity; usually each cluster defined by center C₁ and each point belongs to the cluster with the closest center. Conventional clustering is not differentiable, so we instead use fuzzy clustering, variant that assigns degree of membership to each cluster, with the membership values summing to Given distance functions de, E [M.). the membership in cluster i is
wx(xx)
E/=1
((xx.e.8.) d(x.,,,S,))
in
with m (1, oc) a hyperparameter determining the "softness" of the cluster assignment, usually just set to 2, and d the Mahalanobis distance as defined previously. In this way, soft clustering can be viewed as a transformation of the "distance to prototype" features so that the resulting transformed features are interdependent; decision rule (x(x)) > t interpreted as "x is sufficiently closer to e; than the other centers". The parameters can be initialized randomly or by using a fuzzy clustering algorithm such as fuzzy e-means [1 4 with all S, initialized as identity.
3.5 Regularization
For each transformed feature j E 'p'], the parameters 03 S used to compute the jth feature f may be subject to a regularization weighted by the total usage of feature j. that is, the sum of total training sample weights over nodes that split using feature j. This weighting serves to balance the effects of the loss and regularization; feature used in the decisions for relatively few data will have
For examples of different covariance types, see

---

relatively smaller loss gradient, and so should have proportionally smaller regularization, and vice versa.
One reason to apply regularization is to improve the interpretability of features. The L.1 regularization increases the sparsity of parameters, which can reduce the complexity of interpretation. Other regularizations might improve interpretability an application-speeifi way. Weight- ing by feature usage also ensures that often-used features are the most interpretable.
-0.46 flavanoids + -0.40 OD280/OD315
-0.30 hue
0.18 color intensity 0.65
Another reason to apply regularization is to automatically regulate kernel bandwidth. By using regularization that shrinks the output range of the features, such as a L.1 or 1.2 regularization on a linear transformation, effectively increase the bandwidth; meanwhile, minimizing the loss function shrinks the effective bandwidth because a smaller bandwidth allows fewer data have split decision paths, resulting in purer leaves, This makes the actual choice of kernel bandwidth relative to regularization strength so that only one or the other must be tuned, automatically adapts effective bandwidth individually for each feature, and overall improves performance compared using a fixed effective bandwidth.
-0.71 proline -0.52 alcohol
type 3
-0.11 ash
yes
no
type
type 2
Figure 2: Tree with sparse linear features on the wine data set.
Evaluation
This section contains evaluation and demonstration of inter- pretable models. Comprehensive results, as well as additional experiment details, are in the supplementary material. Unless otherwise noted, all results are from crisp trees.
feature
p1
p2
p3
alcohol
2.03 - -166
-0.15
malic acid
0.85
-0.35
1.15
ash alcalinity of ash
0.06 -1.00 -0.62
-1.16 0.11 0.22
magnesium
0.95 -2.06 -0.08
total phenols
1.27 0.70 -1.46
4.1 Benchmarks
flavanoids nonflav. phenols
0.04 2.69 -0.54
-0.86 -0.33 0.29
We compare various configurations of our algorithm against popular tree-based baselines including decision trees, random forests, and ExtraTrees. We report 10-fold cross validation accuracy and average number of splits in the model. Additional metrics, including average decision path length, feature sparsity, and inference time are shown in the supplementary material.
proanthocynanins
0.74 -0.24 0.57
color intensity
0.70 -1.95 2.51
hue OD280/OD315
0.43 1.10 -1.05
0.51 0.50 -131
proline
1.91 -1.55 -1.06
d(x. p1) 12.65
The data sets are selected from among the the most viewed tabular classification data sets on the UCI machine learning repository [14 at the time of writing. Categorical attributes are one-hot encoded, and the data normalized mean 0 and standard deviation 1. For our models, we show in the main paper results for linear features and eestance-to-prootyye fea- tures with diagonal inverse covariance. Each is regularized with L1 coefficient Å = .01 to promote sparsity. Our models and the conventional decision trees have cost-complexity pruning selected by cross-vas volssvvaliation.. Other hyperparameters are fixed and described in the supplementary material.
type
d(x. p2) 19.41
yes
no
type
d(x, p3) < 15.86
yes
n1
type 3
type
On every data set, at least one of our models matches comes close to the best baseline accuracy while being much smaller. Also note that, since we choose the pruning parameter a by cross-validation, there are many cases where a smaller tree than the one reported performs similarly. Especially for data sets where the ensembles greatly outperform the basic decision tree, the reduction in size for performant model by using our method is huge. This carries the additional benefit that inference is much faster for our models, as shown in the supplementary material. Models with linear features are often the best for given dataset, while prototype features lag slightly behind, suggesting that prototype features are best used to supplement linear features rather than on their own. We also note that these benchmarks all use the same hyperparametees; this shows that good performance does not require great tuning effort, but such effort will probably result in better model for most applications.
Figure 3: Tree with prototype fea- tures on the wine data set.
7

---

3
8
5
(a) The entire model.
(b) Interpretation of correct prediction.
(c) Interpretation of an incor- rect prediction.
Figure 4: An interpretable MNIST classifier with 92.19% test accuracy.
We also separately show results on MNIST and Aishion-MNIST, these experiments are described in Section 4.3 and the results are shown in Table
4.2 Example interpretation
We show two examples of interpretation for trees trained the wine data set. Both are trained with 0.01 as in the benchmarks and achieve 97.2% accuracy on a 20% test split.
A tree with linear features is shown in Figure 2 It has stronger sparsity regularizer A 0.1 compared to the benchmarks. Wines with low flavanoids, protein concentration, and hue are classified type 3. There is also smaller relationship between type 3 and high color intensity. Of the remaining wines, those with low proline and alcohol are type 2, and the rest are type 1. Similarly, there is also smaller relationship between ash content and type that may be important if the decision is not clear based on proline and alcohol.
A tree with prototype features is shown in Figure Here we use simple Euclidean distance for decision rules. Each prototype defines a certain wine profile; for instance, prototype and close to average in other attributes. Wines similar to prototype are type I; wines similar to prototype 2 are type 2; wines similar to prototype are type 3; the rest are type 2.
MNIST
fuzzy acc.
crisp acc. splits
path len.
10
.9266
.9119
9
4.33
high in alcohol and proline
10-3
.5500
.4199
36
5.91
10
.9664
.6100
162
7.68
10-6
9708
.9022
1659
10.05
fashion-MNIST
fuzzy acc.
crisp acc.
splits path len.
10 2
.8059
.8024
3.97
4.3 MNIST features
10
8439
8364
20
4.69
10
8669
8586
98
6.24
Next we fit models to MNIST and fashion-MNIST demonstrate performance on simple image classi- fication. Here linear features with some extra
10
.6755
.8472
2209
11.55
Table Results for MNIST trees.

---

constraints to improve interpretabilityy. First. in addition to a LI regularization to promote sparsity. we use a smoothness regularization which penalizes the average squared difference of each weight with its neighbors, not including diagonal. The idea here is that weight image with smooth shapes easier to understand than one with a handful of sparse pixels, while also being more expressive. We also constrain the tree's threshold values to be zero to ease local interpretation. In this way, we can interpret a decision rule by asking "do the pen strokes better match the blue, or the red"? For example, in the root node in Figure 4al we see that digits with ink primarily in a small near- vertical stroke in the center are classified as I, whereas those with more ink in the closely surrounding space other digits. Complete predictions are shown Figures 4b and 4c
The performance and size of models for various cosppexty pruning a are shown in Table 2 and the smallest MNIST models are shown in Figure g Larger models are shown in the supplementary material. Each internal node shows the linear feature's s weight image, with negative values in blue and positive in red. Each leaf shows the average of the training data belonging to it.
Testing on MNIST allows us make some comparison of our models to TAO [10], which seems to be the best existing method for learning trees with sparse linear features. Ultimately, while their smallest model achieves 89.81 % test accuracy with 16 splits, our smallest achieves 92.19% with just 9 splits. Likewise, their overall best-performing model achieves 94.31 1,, whereas ours achieves 96.10% without fuzzy splitting or 97.08% with The latter is on par with performance of random forests for MNIST, accomplished with single (albeit large) tree with interpretable features. This shows that our proposed approach can achieve state-of-the-an status for learning sparse oblique decision trees, while also having greater flexibility to choose different features and adapt them to application-speiffie interpretability needs.
4.4 Information hierarchy
An additional property of our models is that, differently from other ODTs such as TAO, we continually refit the tree using CART, which greedily chooses the most informative splits first. Each subtree's class labels are thus pure possible, and classes that are easy to separate are separated first. By contrast, in a tree which is trained globally without this greedy splitting, any particular split may not actually result in improvement in label purity, as long as it is in- formative to splits further down the tree.
A compelling example is shown in Figure 5 which shows the tree trained on fasSion-MNIST with a = 10-3 Without exception, the tree forms hierarchy of visual similarity of fashion items, as described in the caption. This allows us interpret predictions some extent with- out even knowing the features. For example, in Figure if the decision path for an image of tee shirt ends at the upper leftmost leaf (dress), instead of the one below it (tee shirt), we can tell by the leaf data alone that the model correctly thinks it is top without long sleeves, but mistakenly thinks that it is sleeveless instead of short-sleeved. A similar structure of visually cohesive subtrees is observed in our MNIST trees, as in Figure 4 but the trend is less obvious because digits are more visually distinct in general compared to the items that comprise MashiOn-MNIST. We do not observe this property in other ODTs; for example, in [41, TAO tree fitted to MaSHi does not exhibit this visual hierarchy property.
Figure 5: An interpretable MaahiOn-MNIST classi- fier. Because CART selects the most informative splits first, the tree is a visually intuitive hierarchy. For example, tops, bottoms, shoes, and bags each have a distinct subtree; within tops, there are sub- trees for sleeve length, collar shape, etc.
5 Discussion
We have proposed a new system for learning small, interpretable decision trees and showed examples under several notions of interpretability, including sparse linear combinations, similarity to prototypes, visual matching, and class-based hicrarchies. Compared to ensembles and deep models, our single-
9

---

tree models are interpretable because they are small, use sparse features, have sparsely activated hierarchical representation based on logical rules, and ultimately work by simply partitioning the data. Moreover, compared to other methods for single-tree models, ours are highly flexible to customize feature types to meet interpretability needs and produce smaller models with more meaningful hierarchical structure and better performance. The tradeoff is that the models can take relatively long to train due to repeated fitting of fuzzy trees, and while our results show that good models can be obtained without extensive hyperparameter tuning, the absolute best model for a given scenario certainly may require careful tuning of several hyperparameters.
Future work will incorporate new, more specialized feature types to extend the framework to differ- ently structured data such images (more challenging than MNIST), time series, and text. We will also work to improve the framework for regression tasks, which are not yet analyzed in this work because the piecewise-constant transformations are less than ideally suited for challenging regression tasks.
nature of decision trees means that small trees with simple feature
References
[1] Stefan Aeberhard and M. Forina. Wine. UCI Machine Learning Repository, 1991. DOI: 10. 24432/C5PC7]
[2] E. Alpaydin and Fevzi. Alimoglu. Pen-Based Recognition of Handwritten Digits. UCI Machine Learning Repository, 1998. DOI:
[3] Osbert Bastani, Carolyn Kim, and Hamsa Bastani. Interpretability via model extraction. arXiv preprint (XKv:00700.97733 2017.
[4] James C Bezdek. Pattern recognition with fuzzy objective function algorithms. Springer Science Business Media, 2013.
[5] Marko Bohanec. Car Evaluation. UCI Machine Learning Repository, 1997. DOL: 10. 24432/ C5JP48
[6] Ferdinand Bollwein and Stephan Westphal. A branch & bound algorithm to determine optimal bivariate splits for oblique decision tree induction. Applied Intelligence, 51(10)7552--552, Oct 2021.
[7] Valerio Bonsignori, Riccardo Guidotti, and Anna Monreale. Deriving a single interpretable model by merging tree-based classifiers. In Carlos Soares and Luis Torgo, editors, Discovery Science, pages 347-357, Cham, 2021. Springer International Publishing.
[8] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth International Group, 1984.
[9] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[10] Miguel A. Carreira-Perpinan and Pooya Tavallali. Alternating optimization of decision trees, with application to learning sparse oblique trees. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Pro- cessing Systems, volume 31. Curran Associates, Inc., 2018.
[11] Tianqi Chen and Carlos Guestrin. XGBoost: scalable tree boosting system. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '16, pages 785-794 New York, NY, USA, 2016. ACM.
[12] Mark Craven and Jude Shavlik. Extracting tree-structured representations trained networks. In D. Touretzky, M.C. Mozer, and M. Hasselmo, editors, Advances in Neural Information Processing Systems, volume 8. MIT Press, 1995.
[13] Yashesh Dhebar and Kalyanmoy Deb. Interpretable rule discovery through bilevel optimization of split-rules of nonlinear decision trees for classification problems. IEEE Transactions on Cybernetics, 51 51(11):5573-555 2021.
[14] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
10

---

[15] J. C. Dunn. A fuzzy relative of the isodata process and its use in detecting compact well- separated clusters. Journal of Cybernetics, 3(3):32-57, 1973.
[16] Vladimir Estivill-Castro, Eugene Gilmore, and René Hexel. Constructing interpretable decision trees using parallel coordinates. In Leszek Rutkowski, Rafal Scherer, Marcin Korytkowski, Witold Pedrycz, Ryszard Tadeusiewicz, and Jacek M. Zurada, editors, Artificial Intelligence and Soft Computing, pages 552-164, Cham, 2020. Springer International Publishing.
[17] Vladimir Estivill-Castro, Eugene Gilmore, and René Hexel. Human-in-the-loop construction of decision tree classifiers with parallel coordinates. In 2020 IEEE International Conference Systems, Man, and Cybernetics (SMC), pages 3852-3859, 2020.
[18] R. A. Fisher. Iris. UCI Machine Learning Repository, 1988. DOL: 10. 24432/C566777
[19] Yoav Freund and Robert Schapire. bessicion-theored generalization of on-line learning and an application to boosting. In Paul Vitányi, editor, Computational Learning Theory, pages 23-37, Berlin, Heidelberg. 1995. Springer Berlin Heidelberg.
[20] Magzhan Gabidolla and Miguel Á. Parreira-Perpiñan. Optimal interpretable clustering using oblique decision trees. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '22, page 400-410, New York, NY, USA, 2022. Association for Computing Machinery.
[21] Magzhan Gabidolla, Arman Zharmagambetov, and Miguel Á. Carreira-Perpincn Improved multiclass adaboost using sparse oblique decision trees. In 2022 International Joint Conference on Neural Networks (IJCNN), pages 1-8, 2022.
[22] Pierre Geurts. Damien Ersst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63(1):3-42, 2006.
[23] Eugene Gilmore, Vladimir Estivill-Castro, and René Hexel. More interpretable decision trees. In Hugo Sanjurjo González, Iker Pastor López, Pablo García Bringas, Héctor Quintián, and Emilio Corchado, editors, Hybrid Artificial Intelligent Systems, pages 280-292, Cham, 2021. Springer International Publishing.
[24] Jack H. Good, Kyle Miller, and Artur Dubrawski. Kernel density decision trees. In Proceedings of the AAAI Spring Symposium on Al Engineering. Curran Associates, Inc., 2022.
[25] Bogdan Gulowaty and Michat Wožniak, Extracting interpretable decision tree ensemble from random forest. In 202/ International Joint Conference on Neural Networks (IJCNN), pages
1-8. 2021.
[26] Venkatesan Guruswami and Prasad Raghavendra. Hardness of learning halfspaces with noise. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 066, pages 543-552, 2006.
[27] Suryabhan Singh Hada, Miguel Á oblique decision trees: A tool to understand and manipulate neural net features. Data Mining and Knowledge Discovery, pages 1-40, 2023.
and Arman Zharmagambetov. Sparse
[28] Suryabhan Singh Hada and Miguel Á. Carreira-Perpináán. Sparse oblique decision trees: tool to interpret natural language processing datasets. In 2022 International Joint Conference Neural Networks (IJCNN), pages 1-8, 2022.
[29] Laurent Hyafil and Ronald L.. Rivest. Constructing optimal binary decision trees np-complete. Information Processing Letters, 5(1):15-17, 1976.
[30] Andras Janosi, William Steinbrunn, Mathias Pfisterer, and Robert Detrano. Heart Disease. UCI Machine Learning Repository, 1988. DOL: 10. 24432/C52PXX
[31] M. Koklu and L.A. Ozkan. Dry Bean Dataset. UCI Machine Learning Repository, 2020.
[32] Peter Kontschieder, Madalína Fiterau, Antonio Criminisi, and Samuel Rota Buld. Deep neural decision forests. In 2015 IEEE International Conference on Computer Vision (ICCV), pages 1467-1475, 2015.
11

---

[33] Haoran Luo, Fan Cheng, Heng Yu, and Yuqi Yi. Sdtr: Soft decision tree regressor for tabular data. IEEE Access, 1955999-561111 2021.
[34] Sreerama K Murthy, Simon Kasif, and Steven Salzberg. system for induction of oblique decision trees. Journal of artificial intelligence research, 2:1-32, 1994.
[35] Duy T Nguyen, Kathryn E Kasmarik, and Hussein A Abbass. Towards interpretable anns: An exact transformation to multi-class multivariate decision trees. arXiv preprint arXiv:2003.04675, 2020.
[36] Omer Sagi and Lior Rokach. Approximating xgboost with an interpretable decision tree. Information Sciences, 572:522-542, 2021.
[37] M. Sato and H. Tsukimoto. Rule extraction from neural networks via decision tree induc- tion. IJCNN'01. International Join Conference on Neural Networks. Proceedings (Cat. No.0ICH37222), volume 3, pages 1870-1875 vol.3, 2001.
[38] Teryy Sejnowski and R. Gorman. Connectionist Bench (Sonar, Mines Rocks). UCI Machine Learning Repository. DOI: http://loroorr/02245555CCC111
[39] Wing S. Hutton L. Sigillito, V. and K. Baker. lonosphere. UCI Machine Learning Repository, 1989. DOI: http://bo..rr/10022444///11011
[40] Andrew Silva, Matthew Gombolay, Taylor Killian, Ivan Jimenez, and Sung-Hyun Son. Op- timization methods for interpretable differentiable decision trees applied to reinforcement learning. Silvia Chiappa and Roberto Calandra, editors, International Conference on Arti- ficial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 1855-1865. PMLR, 26 28 Aug 2020.
[41] Suryabhan Singh Hada and Miguel Á. Carreira-Perpinae Interpretable image classification using sparse oblique decision trees. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2759-2763, 2022.
[42] Alberto Suarez and James F. Lutsko. Globally optimal fuzzy decision trees for classification and regression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(12):: Dec 1999.
[43] Gilles Vandewiele, Olivier Janssens, Femke Ongenae, Filip De Turck, and Sofie Van Hoecke. Genesim: genetic extraction a single, interpretable model. arXiv preprint 1.007222, 2016.
[44] William Wolberg, Olvi Mangasarian, Nick Street, and W. Street. Breast Cancer Wisconsin (Diagnostic). UCI Machine Learning Repository, 1995. DOI: 2tt/11..4444 24432/C5DWD2 C5DWBB
[45] Arman Zharmagambetov and Miguel Carreira-Perpinan Smaller, more accurate regression forests using tree alternating optimization. In Hal Daumé III and Aarti Singh, editors, Proceed- ings of the 37th International Conference Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 11398-11408. PMLR, 13-18 Jul 2020.
[46] Arman Zharmagambetov and Miguel A. Carreira-Perpine Semi-supervised learning with deci- sion trees: Graph laplacian tree alternating optimization. S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages
Curran Associates, Inc., 2022.
12


Reviews:
[{"review_id": "oPYpVXAzn1", "reviewer": "Reviewer_vnHK", "summary": "The authors aim to learn small and interpretable decision trees with good predictive performance. To this end, the authors propose efficient differentiable trees based on the kernel density decision trees. To ensure the small size of the tree and increase the model's representability, the authors propose some parameterized feature transformations. Due to its differential structure, the model is capable of learning the parameters in both the tree and feature transformation simultaneously. The experimental results demonstrate the predictive performance and interpretability of the proposed model.", "questions": "1. In line 147, “we assume a single marginal F_i=F…”. Where is the assumption used in the following part? In the same line, what is F’?\n2. Is the feature transformation mentioned in line 172 the same as these described in Section 3.4? If so, how to guarantee the output range are limit for identiy and element-wise transformation?\n3.What is $\\alpha$ in Section 4? Is it the same as that in line 207? If so, please provide some discussion why larger $\\alpha$ leads to more sparse tree. If not, please provide details how to control the complexity of the model by tuning $\\alpha$?\n4. Is “ours:linear” in Table 1 the same with ODT? If not, please provide experiments results using ODT.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and easy to follow. The idea of learning a parametrized feature transformation is interesting as it enhances the model's expressiveness while still maintaining its interpretability. The authors provided extensive experimental results which demonstrate the interpretability of the model.", "weaknesses": "1. The main contribution of the paper is the proposed differentiable tree and parameterized transformation. Nevertheless, the differentiable tree is not a new concept. Although the idea of learning a transformation during training is interesting. Similar ideas, such as neural prototypes, have been previously proposed in the computer vision domain. See [1] for an example.\n2. No guideline is provided to recommend how to choose transformations in different tasks for users. \n3. The datasets used to show the prediction performance are relatively small.\n4. Some technique details are missing. For example, how these regularizations are used when learn the tree is unclear to me. \n\nRef: \n[1] Nauta, Meike, Ron Van Bree, and Christin Seifert. \"Neural prototype trees for interpretable fine-grained image recognition.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "In response to the weaknesses:\n1. What most clearly separates this work from existing work, methodologically speaking, is that we are the first to re-fit the tree continually throughout training. This is only possible because of recent advances in fuzzy decision tree techniques and results in the structure changing throughout training, resulting in desirable properties of the final model, as described in the paper. We are also the first to weight regularization by feature use in the tree, which results in more uniform sparseness.\n2. Transformations can be chosen by a combination of the interpretability needs of the application (some applications may have different standards for interpretability than others) as well as validation results that suggest which features result in the best performance. For this paper, we focus on tabular and simple image data, but plan to work on other modalities in the future.\n3. The tabular results contain some moderately sized data sets, such as dry-bean (13611 samples) and car (1728 samples). The results on MNIST and fashion-MNIST demonstrate use with relatively large data sets.\n4. If there are specific questions about the methods, we will be happy to answer them in the discussion and clarify in the revision.\n\nIn response to the questions:\n1. That assumption was just meant to simplify notation, but we ended up not using it. We removed the assumption in the revision. Thanks for catching this oversight. \n2. Yes, the strategies on line 172 are intended to be used with the feature transformations in section 3.4. Generally we use the other approach, but if we want to limit the output range of feature transformation, there are many possibilities. For identity, the output range is already limited to the range of the actual training data; in practice, we normalize the data. For element-wise, we can choose a transformation that maps a bounded domain to a bounded range, or apply an \"activation\" such as sigmoid.\n3. Alpha in section 4 is the cost-complexity pruning parameter. This is different from the alpha in section 3.4. We have changed notation to avoid confusion in the revision. Controlling size and overfitting using alpha is standard practice for decision trees, and it is used here as usual. In brief, larger alpha produces smaller trees by stopping growth sooner.\n4. ODT refers to any decision tree using linear splits. In that sense, \"ours: linear\" is indeed an ODT.\n"}, {"review_id": "AvWs2CWwL1", "reviewer": "Reviewer_b4Qh", "summary": "The paper proposes a novel approach that learns sparse features and constructs decision trees in a differentiable manner. This approach strikes a balance between the complexity of decision rules and the overall model, resulting in small, interpretable trees. Specifically, the authors apply (1)alternating optimization method for trees and features (2)kernel density decision trees (3)different parameterized feature transforms (4)regularization method.\nThey compare their method against popular tree-based baselines and demonstrate its comparable performance in terms of accuracy while producing smaller models. ", "questions": "1.I noticed that in Table 1, when α = 0.1, the accuracy on the dry-bean dataset significantly drops to 0.476/0.354. What could be the reason behind this sharp decline? I am somewhat concerned about the robustness of the method.\n\n2.The models using prototype features consistently fall behind the models employing linear features across all six datasets. In practical terms, what strategies can be employed to complement linear features with nonlinear features?", "limitations": "Yes，the authors have adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The approach proposed by the paper is novel that combines sparse feature learning with differentiable decision tree construction to produce small, interpretable trees. This approach is different from traditional decision tree models and provides a new perspective on feature learning for interpretable models.\n\n2. The paper provides a comprehensive empirical evaluation of the proposed approach on various datasets. The authors compare their method against popular tree-based baselines, including decision trees, random forests, and ExtraTrees. The results show that the proposed approach outperforms or comes very close to the best baseline's accuracy while being much smaller.\n\n3. The paper is well-written and gives detailed explanations for each technique used.", "weaknesses": "1. Lack of comparison with other models: The paper compares the proposed approach against only a few traditional tree-based models like decision trees, random forests, and ExtraTrees. Comparing with more classic baselines can better illustrate the effectiveness of the approach\n\n\n2. Clarity: The paper covers a variety of techniques (such as KDDT), many of which are improvements built upon previous work. It would be beneficial to clearly highlight the unique contributions made by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "In response to the weaknesses:\n1. The intention was to compare against structurally similar models with some degree of interpretability in the standard ML repertoire. After all, the methods are proposed as an alternative to traditional tree-based models. However, in the revision, we have added additional baselines. \n2. The final paragraphs of the introduction and related works specify the unique contributions. We have modified this text in the revision to make it clearer.\n\nIn response to the questions:\n1. This decline is expected. When alpha = 0.1, we are telling the model not to split unless the overall impurity (between 0 and 1) is improved by at least 0.1. When there are 7 different classes, it is not unexpected that none of the initially available splits results in this much gain, so the final tree is just a single node, or maybe has one or two splits. For data with several classes, alpha = 0.1 is just too large. This is why we don't report alpha = 0.1 for the MNIST results.\n2. These feature types can be used in conjunction in the same tree if desired. One would simply concatenate their respective outputs to get the input to the tree training algorithm. We do see that linear features usually outperform prototype features, but this is not true for every data set. In addition, one might choose one or the other based on which is more interpretable in a given application context.\n"}, {"review_id": "MW1l8he52k", "reviewer": "Reviewer_ejNS", "summary": "In this paper the authors study the problem of learning meaningful feature representation for decision trees. They propose to interleave the learning of parametrized feature representation by gradient descent, and the learning of tree structures by standard greedy method, e.g. CART. A kernel density decision tree is used for the former step for differentiability. \n\nThe authors propose a few practices to achieve better performance, which includes a couple of classes of feature transformation, regularization and the choice of KDDT kernel. They empirically show that the proposed method easily outperform similar existing methods, and the learned feature representation are visually meaning when the method is applied to image datasets.", "questions": "1. Regarding novelty, I wonder what is the key difference between the proposed method and prior work, as the phrasings in Line 128-131 and Line 132-135 sound almost the same.\n2. Both the study on the tabular data and on the image datasets suggest that the linear projection is the most important feature transformation, which is also the most compatible with the sparsity regularization. What exactly do other feature transformations, e.g. distance to prototype and fuzzy cluster membership, bring here? Any theoretical / empirical supporting evidence?\n3. Given the linear projection transformation is done in a fashion very similar to the learning of a NN dense layer, I wonder how stable the proposed method is, in particular\na. How's convergence in practice with respect to the learned linear projections? Is the learning robust / can we always reach the same linear features / interpretation of the resulting tree? \nb. How much does the tree T structure changes during model fitting? The introduction of growing / pruning methods (L131) actually prevent the tree structure from changing too much, and why do we not consider such strategies?\n4. The benchmarking against tree methods is less meaningful given the feature learning perspective of the proposed method. A closer comparison is probably between it and a shallow MLP. \n5. Line 126. T \\circ f_{\\theta}. \n\nI am open to raise my rating should the aforementioned questions be addressed.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper studies a legit and important research question, that it provides a convincing potential solution to the question of effectively applying decision trees on higher dimensional datasets with proper feature learning. \n2. The proposed method has good uses of modern decision tree techniques. I think the authors have exhausted the headroom in their scope, and there is no obvious theoretical improvement left to make. \n3. The writing quality is good. The paper is clear, concise and easy to follow.", "weaknesses": "One of my major concerns is the divergence of the proposed method from a traditional decision tree and its implied impact on model performance and interpretability. Kernel based fuzzy decision trees are a compromise to differentiability, which already results in a prediction pattern that is not the interpretable yes-no at each node, adding extra computation and more mental overhead. This plus the learned linear feature combination, about whose stability I have doubt, might push the proposed method more like a NN in the shell of a DT.  These observations might have undermined the significance of the submission.\n\nAnother concern is about novelty, that as mentioned by the authors, the interleaved learning of tree structure and feature representation has been studies. If so the novelty of the paper is the proposed of several practices of better feature representation learning, which might fail to justify as a NeurIPS publication.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "In response to the weaknesses:\n\nThe fuzzy decision component is really only important to achieve differentiability in this context. It can increase performance slightly, but the feature transformation is more important. While most KDDT decisions are the same as the corresponding crisp tree, we agree that those decisions that are fuzzy may be viewed as less interpretable. If this is a concern, one can simply not use fuzzy decisions for prediction. To reflect this, in the revision, we report results using crisp trees as the final predictor so that these models can be interpreted unambiguously as using a single decision path for each prediction. Most of the scores do not change much as a result. A notable exception is that the largest MNIST tree drops from 97.08% to 95.75% test accuracy.\n\nWith or without fuzzy decisions, we disagree that these models are comparable to a neural network. They are sparsely activated for a given prediction, and decisions are a logical series of rules rather than a composition of functions. The overall size is substantially less than a neural network, and the partitioning structure itself aids interpretation by grouping like data; a strongly illustrative example is the visual of the fashion-MNIST tree. The consensus of models like this being valuable for interpretability is backed up by a history of published work learning ODTs for the purpose of interpretability, including [9], which was published at NeurIPS.\n\nAs for novelty, we want to clarify that the interleaving of tree fitting with feature learning, as you put it, has not been studied before this work. Existing approaches fit a (crisp) tree at the start, then make it fuzzy and learn features without regrowing the tree.\n\nIn response to the questions:\n1. The difference described in the referenced lines is that existing approaches only grow the tree up-front, and they use a crisp tree growing algorithm. We fit continually throughout the feature learning process, which is a simple and principled way to revise the tree structure based on the changes in input; however, it requires an efficient and stable *fuzzy* decision tree growth algorithm, which we are the first to apply in this way.\n2. To keep the scope of the experiments reasonable, we only tested linear and prototype features, which we expect to be the most generally applicable in terms of performance and interpretability. The linear features do typically outperform prototype features, but there are cases where the opposite is true. We propose a variety of features in order to best meet modeling and interpretability needs for possible applications, and plan to study specialized domains in future work.\n3. This is, of course, nonconvex optimization. Convergence is not perfectly smooth, especially for small tabular data sets, but generally we consistently arrive at a good model. We did not look at the tree for every experiment, but for the ones we created visuals of (wine, MNIST, fashion-MNIST), the resulting tree structure and features were consistent over multiple runs with different initialization. For MNIST and fashion-MNIST, the convergence of the loss function was especially smooth and stable, maybe because of the large size of the data sets. Substantial changes to tree structure are frequent early during the learning process, but once the feature transformation parameters start to converge, tree structure changes are infrequent. The complete regrowth approach is desirable because it is not limited to trees that are similar to the previous iteration. Approaches that just trim and grow are not able to change the fundamental layout of the tree. We believe this is why we see smaller, better-performing trees on MNIST compared to TAO, a recent alternative. Also, while DT growth is a heuristic, it is a proven and widely accepted strategy for producing approximately minimal decision trees, and as demonstrated in the fashion-MNIST example, the property that splits are locally most informative can have interpretability benefits.\n4. We did not think it was important to compare against black-box models, but we have added MLP to the benchmarks in the revision. They are the best-performing model on about half the data sets.\n5. You are correct - thanks for catching this mistake. We have fixed it in the revision.\n"}, {"review_id": "QZx8XoLiux", "reviewer": "Reviewer_js5S", "summary": "The paper proposes a method to learn interpretable decision trees by keeping the tree depth limited without sacrificing the performance. Keeping the tree small is achieved through multiple iterations of feature transformation followed by regrowing the tree. Authors have utilized linear and distance to prototype feature transformation. They apply regularization to improve interpretability through increasing feature sparsity and shrinking the output range of the features which results in purer leaves. \nAuthors report empirical results evaluating their method against decision tree, random forests, and EstraTrees on a set of UCI repositories. Experiments report accuracy , average number of nodes in model, average decision path length, feature sparsity, and inference time (all metrics except accuracy are reported in supplementary material). Results show that in 4 out of 6 data sets, a version of the proposed method outperforms the baselines.", "questions": "- It would be useful to understand author(s)' perspective on linear transformation of input features on interpretability.\n- Can authors clearly explain the main rationale behind reporting MNIST data sets?\n- How would authors justify that the intermediate value of alpha for the most part has the highest performance, although the alpha values that represent highest complexity are expected to outperform the intermediate alpha value.\n- Can author shed more light into the big delta between their method's performance for various alphas and how this could be addressed practically so that a fixed programmatically selected alpha can be used with high confidence?", "limitations": "- Time complexity: As stated by the authors, proposed approach requires longer training time due to repeatedly fitting a tree to the data. It would have been more useful if experiments instead of inference time would have reported the training time.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Originality: The work builds on top of existing literature on feature transformation, oblique decision trees, CART, differentiable decision trees, etc. The proposed way of alternating through feature transformation and tree re-growth is fairly novel and the introduced regularizations make sense.\n- Quality: The quality of the paper is overall fair. Motivation is clear, related literature is well covered and experimental results are clearly reported with more details in supplementary materials. Refer to weaknesses for rationale on why overall quality is fair.\n- Clarity: The paper is written clearly for the most part. I was not able to completely follow the discussions on MNIST data sets and it is not clear to me how the proposed method reforms compared to the baseline approaches in terms of accuracy and explainability for MNIST.\n- Significance: The work is generally interesting with potentially significant applications. However, the shortcomings that I've listed in the weaknesses sections cast some doubt on the significance of the proposed method as presented.", "weaknesses": "- Interpretation of interpretability: Authors measure interpretability in terms of the tree size and use feature transformation and regularization to keep the tree size under control. However, one can argue that the feature transformation (e.g. as in application of ODT with non axis-aligned partitioning, or distance to prototype) can adversely impact interpretability. For example, consider figure 2 where a node contains a linear combination of a set of features as the decision criteria which is not very interpretable compared with an axis-aligned simple DT method. To get a better idea, consider a domain where raw features are more tangible and interpretable compared to the wine data set such as income prediction based on age where applying a coefficient to a well understood feature such as age and combining it with other scaled features make the whole tree less interpretable.\n- Limited and inconclusive competitive analysis: Authors have compared their method against DT, RF, and ET. Experimental results are limited because authors have not considered linear methods such as linear regression which are arguably comparable with the proposed methods in terms of interpretability. Reason is that linear methods provide one linear formula consisting of the input features whereas the proposed method (with linear transformation) consists of multiple nodes each with a linear combination of a limited set of features. They are inconclusive since, the performance of the proposed method varies drastically based on the alpha value which is not picked programmatically (based on cross validation) like what authors have done for DT. Lastly, the baseline methods do not help getting a clear idea about the delta in accuracy between non-interpretable high performing methods (e.g. xgboost) and more interpretable alternatives.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "In response to strengths - clarity: we did not include baseline results for MNIST and fashion-MNIST because they are widely studied and have a set train-test split. It is easy to find baseline results, but we can include them in the supplementary material if it is desired. We use MNIST for some comparison against TAO, a recent approach for training ODTs, but we cannot reproduce their methods, and so we reference their paper for the results. If you have specific concerns about the clarity of this discussion, we would be happy to answer questions and revise the text to improve understanding.\n\nIn response to the weaknesses:\n\nWe agree that sparse linear or prototype features on their own are less interpretable than single-feature splits used in conventional decision trees. However, we argue that the substantial reduction in tree size and, more importantly, the ability to perform well with a single tree instead of an ensemble more than make up for it. For example, you reference figure 2; a decision tree fit to the same data is on the order of 10x larger and performs very poorly, and an ensemble that performs well is hundreds of times larger and involves aggregating the decision from many models. This argument is generally accepted and is the basis for several of the referenced related works, one prominent of which ([9] in our submission) was published in NeurIPS.\n\nWe have added baselines to the experiments. Linear models are very interpretable, but do not perform well on data that is not linearly separable. Moreover, our method can be simpler for multi-class problems because linear models have one linear formula per class along with a softmax function. Because our trees are used sparsely during prediction, a balanced tree can separate n classes with as few as log(n) linear rules on average per prediction. MNIST is a good example; there are 10 classes, but our smallest tree uses far fewer than 10 linear rules per prediction on average. We also remind that the models in the benchmarks in the main paper are using *sparse* linear features.\n\nAs for variance of performance with alpha, this is expected. It is used to trade off size for expressive power via early stopping of tree growth. We showed different alpha values to demonstrate this. To make the comparison fairer, in the revision, we report benchmark results with each model having alpha chosen by cross-validation of the tree on the training data transformed with the final learned feature parameters.\n\nWe also added highly expressive models such as MLP and XGBoost to the experiments.\n\nIn response to the questions:\n- See the first paragraph of our response to the listed weaknesses.\n- The MNIST models are presented to (1) demonstrate performance on a large, many-featured data set; (2) establish the use case of our methods on simple image problems and motivate future work on more challenging image problems; (3) provide compelling visual examples of very small, interpretable trees for complex classification problems; (4) demonstrate the potential usefulness of the hierarchical structure resulting from greedy tree growth, as in the fashion-MNIST figure; and (5) provide some comparison against TAO, which is also benchmarked on MNIST in [9], since MNIST has a pre-determined train/test split and so such a comparison is valid.\n- It is not true that models with higher complexity always outperform models with lower complexity. While our trees are less prone to overfitting than standard decision trees, they can still overfit if allowed to grow too large, which is why we see reduced performance for large alpha on some data sets.\n- To expand on the prior point, alpha being too small results in underfitting, and alpha being too large results in overfitting. This is no different from conventional decision trees, though since our models with transformed features are more expressive, the ideal tree size is smaller and has better performance. Alpha can be efficiently selected programmatically by doing cross-validation on the training data with the final learned features. We have added benchmark results with alpha selected in this way in the revision.\n"}]

Author rebuttal:
Thanks to the reviewers for your feedback and insights.

The reviewers' main concerns relate to misunderstanding of the methods and their novelty, misgivings about the interpretability of the proposed models, and the limitations of the scope and presentation of the experiments. We have addressed these through our replies to the individual reviewers and a revision that we plan to submit once revisions are unlocked for the camera-ready version. Given our overall borderline scores, we strongly believe that this qualifies the paper for acceptance.

In particular, we highlight that (1) we are the first to alternate decision tree fitting with feature parameter learning, which is only made possible by recent advancements in fuzzy decision tree methods, and we are also the first to weight regularization of the feature parameters by the usage of each feature in the tree; and (2) models like these, especially ODTs, are generally accepted as being beneficial to interpretability compared to conventional tree-based models, as demonstrated by the related works. One of these, [9], was published in NeurIPS. 

A summary of changes made in the revision:
- Add experimental baselines.
- Modify some text in an effort to preclude misunderstandings and answer questions present in the reviews.
- Report performance for our models with programmatically selected hyperparameters.
- Report performance without fuzzy predictions to address doubts about interpretability with fuzzy trees.


Meta-review: The paper presents a new method for learning small decision trees, leveraging sparsity in differentiable tree learning. The reviewers praised the clear writing, the originality of the idea of a parametrized feature transformation and the comprehensive experiments showing near-sota performance with much smaller models. The reviewers also raised some concerns about baselines, differentiation compared to existing techniques and the metrics for interpretability. During the discussion period, the authors have added additional baselines, justified their metrics and convinced the reviewers of the distinction between their method and past methods using differentiable trees. Following the discussion section, all reviewers' scores are in the accept range. Given that the paper has a reasonably original idea, and that the experiments now have proper baselines, I recommend acceptance.
Decision: Accept (poster)