Tree in Tree: from Decision Trees to Decision Graphs
Authors: Bingzhao Zhu
Mahsa Shoaran
Venue: NeurIPS 2021 Poster (2021)
Keywords: Decision graph
decision tree
classifier
ensemble

Abstract: Decision trees have been widely used as classifiers in many machine learning applications thanks to their lightweight and interpretable decision process. This paper introduces Tree in Tree decision graph (TnT), a framework that extends the conventional decision tree to a more generic and powerful directed acyclic graph. TnT constructs decision graphs by recursively growing decision trees inside the internal or leaf nodes instead of greedy training. The time complexity of TnT is linear to the number of nodes in the graph, therefore it can construct decision graphs on large datasets. Compared to decision trees, we show that TnT achieves better classification performance with reduced model size, both as a stand-alone classifier and as a base-estimator in bagging/AdaBoost ensembles. Our proposed model is a novel, more efficient and accurate alternative to the widely-used decision trees.

Tree in Tree: from Decision Trees to Decision Graphs
Bingzhao Zhu EPFL
Mahsa Shoaran EPFL
Lausanne, Switzerland
Lausanne, Switzerland mahsa. shoaran@epfl.ch
Cornell University
Ithaca, NY, USA b2323@cornell. edu
Abstract
Decision trees have been widely used classifiers in many machine learning applications thanks to their lightweight and interpretable decision process. This paper introduces Tree in Tree decision graph (TnT), framework that extends the conventional decision tree to a more generic and powerful directed acyclic graph. TnT constructs decision graphs by recursively growing decision trees inside the internal or leaf nodes instead of greedy training. The time complexity of TnT is linear the number of nodes in the graph, and it can construct decision graphs on large datasets. Compared to decision trees, we show that TnT achieves better classification performance with reduced model size, both as a stand-alone classifier and as base estimator in bagging/ Bagging/AdaBosttt ensembles. Our proposed model is novel, more efficient, and accurate alternative the widely-used decision trees.
Introduction
Decision trees (DTss and tree ensembles widely used in practice, particularly for applications that require few parameters [155,, fast inference [68] and good interpretability [ 10). DT, the internal and leaf nodes are organized in binary structure, with internal nodes defining the routing function and leaf nodes predicting the class label. Although DTs are easy to train by recursively splitting leaf nodes, the structure be suboptimal for the following reasons: (1) DT' can grow exponentially large as the depth of the tree increases. Yet, the root-leaf path can be short even for large DTs, limiting the predictive power. (2) In a DT, the nodes are not shared across different paths, reducing the efficiency of the model.
Decision trees similar neural networks (NNs) in that both models composed of basic units. possible way to enhance the performance of DT's or NNs is to replace the basic units with more powerful models. For instance, "Network in Network" builds micro NNs with complex structures within local receptive fields to achieve state-of-the-art performances on image recognition tasks (T]. As for DTs, previous work replaced the axis-aligned splits with logistic regression linear support vector machines to construct oblique trees [ 3 6 12 The work in [5] further incorporates convolution operations into DTs for improved performance on image recognition tasks, while replaces the leaf predictors with linear regression to improve the regression performance. Unlike the greedy training algorithms used for axis-aligned trees (e.g.. Classification and Regression Trees or CART [15)), oblique trees are generally trained by gradient-based [ 13 or alternating [T] 6 optimization algorithms.
Inspired by the concepts of Network in Network 11 and oblique trees 6 12]. model, Tree in Tree (TnT), recursively replace the internal and leaf nodes with micro decision trees. In contrast to a conventional tree structure, the nodes in a TnT form a Directed Acyclic Graph (DAG) address the aforementioned limitations and construct a more efficient model. Unlike previous oblique trees that were optimized on predefined tree structure
we propose a novel
[ TnTT can learn graph
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

connections from scratch. The major contributions of this work are as follows: (1) We extend decision trees to decision graphs and propose a scalable algorithm to construct large decision graphs. (2) We show that the proposed algorithm outperforms existing decision trees/graphs, either as a stand-alone classifier or base estimator in an ensemble, under the same model complexity constraints. (3) Rather than relying on predefined graph/tree structure, the proposed algorithm is capable of learning graph connections from scratch (i.e., starting from a single leaf node) and offers a fully interpretable decision process. We provide Python implementation of the proposed TnT decision graph at https://gituu..com hattr//inngnaoo////Tiiiiiiiiooo
2
Related work
Decision graph (DG) is a generalization of the conventional decision tree algo- rithm, extending the tree structure to a directed acyclic graph [7). Despite similarity in using a sequential inference scheme, training and optimizing DGs is more challenging due to the large search space for the graph structure. The work in [16] and [18) proposed greedy algo- rithm to train DGs by tentatively joining pairs of leaf nodes at each training step
Algorithm 1: Naive decision graph (NDG) [16]
G < initialize graph with a leaf node;
2 for i < 1 to N do
3
for each leaf node (lx) E G do Find the maximum gain (g:) if we 4 for each pair of leaf nodes (1, ( E G do Record gain (gt,) if we merge 4 and 4y; Split/merge nodes to maximize gain;
$
7
8
Note: The split operation has model complexity penalty (C) for creating an internal node.
(NDG, Algorithm 1). [9 constructed
the DG as a Markov decision process, where base estimators were cascaded in the form of a data- dependent AdaBoost ensemble. [20] combined multiple binary classifiers construct DAG for efficient multi-class classification. While [19 and [20] constructed DAGs with specific settings (e.g.. Adaboost [99 and multi-class classification
(20) , these methods do not provide general extension of decision trees. [2I] improved NDG by jointly optimizing split nodes and their connections to next-layer nodes. However, simultancously learning the split and branching structure has no exact solution and relies scarch- based algorithms to reach local minimum. Alternatively, in this work, we revisit the concept of decision graphs by exploiting recent advances in non- non-greedy tree optimization algorithms 6 12 14 22]. Our proposed Tree in Tree algorithm construct DGs more accurate and efficient alternative to the widely- uueed decision trees, both as stand-alone classifiers and as weak learners in the ensembles.
Conventional decision tree learning algorithms such as CART [5] and its variations follow a greedy top-down growing scheme. Recent work has focused optimizing the structure of the tree [22
However, constructing an optimal binary DT NP-hard 25) and optimal trees are not scalable to large datasets with many samples and features 122 24 Recent studies have further developed scalable algorithms for non-greedy decision tree optimization, with no guarantce on tree optimality
I 3 6 14). Such scalable approaches can be categorized into two groups: tree alternating optimization (TAO) [ 6 and gradient- gradient-based optimization B 12]
TAO decomposes the tree optimization problem into set of reduced problems imposed at the node levels. The work in 6 applied the alternating optimization to both axis-aligned trees and sparse oblique trees. Later, extended TAO to regression tasks and ensemble methods. Unlike TAO, gradient-based optimization requires a differentiable objective function, which can be obtained by different methods. For example, [12 derived a convex-concave upper bound of the empirical loss. [13 and [3] considered a soft (i.c., probabilistic) split at the internal nodes and formulated a global objective function. The activation function for soft splits was refined in [14] to enable conditional inference and parameter update. Both TAO and gradient- based optimization operate on a predefined tree structure and optimize the parameters of the internal nodes.
The proposed Tree in Tree algorithm aims to optimize the graph/tree structure by growing micro decision trees inside current nodes. Compared to the greedy top-down tree induction [15, Tree in Tree solves a reduced optimization problem at each node, which is enabled via non-greedy tree alternating optimization techniques (6). Compared to NDG, Tn' employs a non-greedy process to construct decision graphs, which leads to an improved elassification performance (discussed in later sections). Compared to axis-aligned decision trees (c.g.. TAO 66. CART [15 TnT extends the

---

tree structure to a more accurate and compact directed acyclic graph, in which nodes are shared across multiple paths.
3 Methods
In this work, we consider a classification task with input and output spaces denoted by X' C RD and y {1, }) respectively. Similar to conventional decision trees, decision graph classifier G consists of internal nodes and leaf nodes. Each internal node is assigned a binary split function s(;;0) X (eiildd right_child parametrized by 0, which defines the routing function of graph. For axis-aligned splits, indicates a feature index and a threshold. The terminal nodes (with no children) are named leaf nodes and indicate the class labels.
3.1 Decision graph
As an extension to the tree structure, decision graphs organize the nodes into a more generic directed acyclic graph. In this work, we limit our discussion to axis-aligned binary DTs/DGs in which each internal node compares feature value to a threshold to select one of the two child nodes. Similar to the sequential inference process DTs, the test samples successively select path at the internal nodes until a leaf node is reached. The main differences between binary DTs and DGs are the following: (1) In DTs, each child node has one parent node. However, DGs allow multiple parent nodes to share the same child node. Therefore, DG can combine the nodes with similar behaviors (e-g.. similar split functions) to reduce model complexity. (2) In binary DT's, the number of leaf nodes is always greater than the internal nodes by one. In DGs, however, # Leaves I # nntrnals + 1, since multiple internal nodes can share the same leaf node. Furthermore, there exists unique path to reach each leaf node in a tree structure, which does not hold within DGs. (3) The model complexity of a DT is often quantified by the number of internal or leaf nodes. However, we can post-process DG by merging the leaf nodes with the same class label. As a result, DGs have a minimum leaf node count equal to the number of classes. Therefore, we use the number of splits (i.e., internal nodes) to quantify the model complexity of DG.
DG start from the root and
3.2 Tree in Tree
(a)
(b)
1
We propose novel algorithm named Tree in Tree scalable method to construct large decision graphs. Conventional DT training algorithms (e.g., CART) are greedy and re- cursively split the leaf nodes to grow a deep structure, without optimizing the previously learned split functions. The key difference between the proposed TnT model and con- ventional approaches lies in the optimiza- tion of the internal nodes. TnI fits new deci- sion trees in place of the internal/leaf nodes and employs such micro DT's to construct directed acyclic graph. Overall, the pro- posed TnT model a novel extension the conventional decision trees and generates accurate predictions by routing samples through a directed acyelic graph.
1
left
right
2
5
(a) The growing phase of TnT. The micro decision tree (in dashed box) replaces an internal node (dashed circle). Compared to single node, the substitute micro tree can provide a more powerful split function. (b) The merging phase of TnT. We merge the fitted micro tree into the current structure to create a directed acyclic graph.
Figure 1:
F shows the high-level procedure for training a decision graph with the proposed Tn' algorithm. Assuming a starting decision graph (c.g.. decision tree or single leaf node), our goal grow larger model with improved predictive power. In the growing phase of TnT (Fig. aa), we replace a node (dashed circle) with micro decision tree with multiple splits to enable more accurate decision boundaries. In the merging phase (Fig. [b)), the micro decision tree is merged into the starting model to construct a TnT decision graph, in which child node (node 2) may have multiple parent nodes (node 4 and 5).
Growing the graph from internal nodes We consider the training of a decision graph as an optimization problem with the aim of minimizing the loss function on the training data:
min Σ
L (y, G(a;; O)).
3

---

TnT grows the decision graph G-:: Q) from an arbitrary internal node E G with the split function s(-;8,). 02 denotes the trainable parameters of n, including feature index and threshold for axis-aligned splits. The overall goal is to replace n, with a decision tree la and minimize the loss function as indicated in ① All other nodes remain unchanged as we train 4.-
Let us consider a subset of samples (Isubeet E split function s(: 0t). as defined by the following expression:
Xsubset: Voubset E euddett that is sensitive to the
Cii-llefeTTaabaeee ())):) # Frigh O)))))
where 0%0; denotes the parameters of all nodes in G' excluding n,, Growing the graph from n, does not change θ%0; since all other nodes are fixed we solve the reduced optimization problem at nlg Gn.-left sends the samples to the left child at n, (i.e., s(;; 0,) + lefl_child) while Gz,-rright routes the samples to the right child n,. With O,0 being fixed, the output of decision graph only depends on 0g (i.c., (:)
G(x; θ) { (n O,),)
if sf; 0,) left_child if s(;; 0,) + right_child.
(3)
G Gnn (z; O)0,)
Since Lyy GR, ft (x; ()0,)) * L(y, Gn. Gx, (x, ()),) only if the incquality 2 holds, can solve the reduced optimization problem at node n, based on the subset (Xsubeet, Y sudeet) instead of using the entire training set:
min
L(y Lly.G(x;)))
(4)
VE Kaubact
Having Equation 3 the optimization problem 44 has closed-form solution follows:
4 (x) = [left_che child if L(y, Gn, 0.)) < L(y, Gig if L(y, Gn. ())))) < L(y, (n. (x;
(5)
(right_chill chiid
Equation (5) defines the optimal split function at the internal node n; which is used fit the micro decision tree t.. With other nodes being fixed, we show that the overall loss function of G can be minimized by pursuing the optimal spilt function an arbitrary internal node n4;- Rather than using simple axis-aligned split, the proposed TnT algorithm learns a complexity-constrainee decision tree to better approximate the optimal split function (Equation (5
Growing from the leaf nodes is a standard practice in greedy training algorithms, where we recursively split the leaf nodes to achieve a deeper tree with better fit on the training data [15]. In TnT. we replace the leaf predictors with decision trees, Let G-: +) be decision graph and ny G an arbitrary leaf node with a constant class label 6:) = c. Our goal is to minimize the overall loss function L (Y, G(X; θ)) by replacing the leaf predictor I(-; 0t) with a micro decision tree (z)).
Growing the graph from leaf nodes
Consider the subset of samples (Xuubset, Wsubset) that visit the leaf node ny. Minimization of the loss function (T) can be expressed
min O:
Σ Ll,t((x)),
DEXeubeer WEY
where the minimum is simply achieved at t/ (x) y for x, y E Xsubsets Y Suceet (i.e., the ideal Ieaf predictor). We build a decision tree to approximate the ideal leaf predictor.
3.3 Learning procedure
Unlike the learning procedures in L which require a predefined tree structure, our proposed TnT algorithm grows decision graph from single leaf node. The training of Tn'T decision graphs is an iterative process that follows a grow-merge-groww pseudocode to train Tn' decision graph. Lines 9-14 find the subset of data samples X Vuddect that is sensitive to the internal split functions or leaf predictors at each node, and grow micro decision trees. In the internal nodes, Vsubset represents binary labels for the left or right child (i.c., not the label of the training set). Line 17 grows micro decision trees according to the growing phase of the TnT. Line 18 merges the trees into the graph structure. In Algorithm 2, N₁ is the number of merging phases that micro trees are merged into the graph. N₂ is the number of rounds to grow and optimize micro trees, similar to the number of iterations in the tree alternating optimization algorithm [ 6
-merge alternation. Algorithm 2 shows the

---

Regularization Regularization is critical to limit model complexity and prevent overfitting of decision tree and similarly required for TnT decision graphs. In the growing phase of TnT (either from internal or leaf nodes), the subsets of samples Xeubset, Voubset at different nodes may have various sizes. Therefore, we need a robust regularization technique to operate across all nodes of the TnT and to train the micro decision trees without overfitting on small subsets. In this work, we propose to use the sample-weighted cost complexity pruning approach [26 27). We prune micro decision trees by minimizing R(t.) + C, where R((+) is the misclassification measurement and |t;] denotes the tree complexity. We calculate R(t;) using Gini impurity and measure [ts] by counting the number of splits [15]. C2 is the comple-weighted regularization coefficient calculated by
#
C C # #usbsett.
where #uKauhset, is the sample count of subset at node ni, C' hyperparameter of the TnT and is used to control the pruning strength and tune the model complexity (# splits). For a smaller subset, need to apply stronger cost complexity pruning to prevent overfitting.
(a)
(b)
(c)
k,tt?
A
O
A
frbs
1000
fabe
tt
X,
false
x
O
O
1r0e
110
N t,?
x,
A
x,tt?
O
A
O
A
1966
10ke
1
Figure 2: Comparison of DT and TnT decision graph on synthetic data; (a) A toy classification task denote two features and four thresholds,
with desired axis-aligned boundaries. 31, and respectively. Different markers represent binary class labels. (b) A decision tree requires at least six splits to classify the data. (c) A TnT decision graph only requires four binary splits on the same task.
Fine-tune and post pruning The TnT decision graphs are compatible with Tree Alternating Optimization (TAO (6), previously proposed to optimize decision trees. We used TAO to fine-tune the TnT decision graphs which led slight improvements in classification accuracy. The pseudocode for TnT fine-tund tune algorithm is provided in the supplementary materials. A post pruning process is further applied to TnT decision graphs to remove the dead nodes. A node is pruned if no training
Algorithm 2: Tree in Tree (TnT)
Data: Training set X,
Result:
TnT decision graph G fitted on the training set
(in X)) denotes the forward inference of data X' starting from node n);; [Nodes are visited in the breadth-firt order);
3 G + initialize graph with a leaf node;
for i1 < to N₁ do
for 1/ + to N₂ do for each node (n,) G do
Samples that visit nę: X, C N.Y:
if n4 is internal node then
Viteft +-
fe_hild X;);
Viright <-
X));
11
inder left_effff (Ji Viteet and y: * (irght)
index mridt t (J1 Varight and V, o Viteftt)
13
Xeabaet, Veubsct &- copy samples from X, V1 at Lidex_leff ft or index_ ridet)right);
14
Voudset lindx_leftt left) + 0. Doubset (inder (indei_rigtt t 1;
else if nı is leaf node then
16
Xonhact &- X, Y Voutset +- Y;:
Grow micro tree on subset Xsubset; Vsuhset in place of nú;
18
Merge into the current decision graph G for all nodes (ng E G)
5

---

samples travel through that node. Post pruning can result in a more compact decision graph and reduce the number of splits without affecting the training accuracy.
Time complexity Compared to decision trees, decision graphs offer enriched model structure, which increases the complexity of learning the graph structure. Previous work constructed decision graphs by tentatively merging two leaf nodes at each training step, with time complexity of (N?)) where N2 is the number of leaf nodes [[6]. Since the proposed TnT algorithm generates new splits by growing micro decision trees inside the nodes, the dataset is initially sorted in (mkloog(m) for m samples and k features. The time complexity for creating a new split depends on the dataset (i.e., ((mk)) and not the size of the graph. As the graph grows larger, the TnT algorithm optimizes each node for N1 N2 times in the worst case (Algorithm 2). Since N1 and N2 are hyperparameterss that were fixed in this work (N1 2, N2- 5, the choice of N1 and N2 will be discussed the following section), TnT exhibits a linear time complexity to the number of nodes, O(nmk + mklog(m) (m)) with n being the number of nodes. Testing our Python implementation on an Intel i7-9700 CPU, it took 325.3 seconds to build TnT of 1k splits on the MNIST dataset (60k samples, 784 features, 10 classes).
Synthetic data We first construct a synthetic classification dataset to show the potential benefits of TnT over conventional decision tree algorithms (c.g., CART). Figure. 2aa visualizes the two- dimensional data distribution with one class the corners and the other class elsewhere. To achieve optimal decision boundaries, a conventional decision tree requires six splits (Fig. (2))), whereas ThT only requires four splits to generate the same decision boundaries (Fig. [c)). By sharing nodes among different decision paths in graph, TnT enables a more compact model with fewer splits compared a conventional DT.
4 Experiments: TnT as stand-alone classifier
We test the TnT decision graph as stand-alone classifier and benchmark it against several state-of- the-art decision tree/graph algorithms with axis-aligned splits, including classification and regression trees (CART (15),, tree alternating optimization (TAO (6). and the naive decision graph (NDG [6). We did not include decision jungles [21] in our comparison since no implementation was provided by the authors. We also implemented the TnT algorithm in two different settings: with or without Ene-tuning. We observed that the proposed TnT algorithm consistently achieves a superior performance under similar complexity constraints on multiple datasets.
(a)
(b)
(d)
neet Auourmty (N)
Spitts
400
400
8
200
200
CAN
10
25
10
10
2
75
200
400
1000
75
400
500
1000
Root Parth
Figure 3: (a) The number of splits as function of the root-leaf path length. The standard deviation across different samples is shown by shaded areas. (b) The number of splits vs. regularization coefficient C. (c. d) Test performance using different hyperparameter settings on the MNIST dataset. The default setting (N1 2, N₂ = 5) plotted in both figures for comparison.
In the worst-case scenario, the number of nodes increases exponentially with the depth of a tree, which prevents DTs from growing very deep. However, this limitation does not apply TnT decision graphs. Figure 3 () illustrates the average length of the root-leaf path as a function of model complexity for TnI and CART. With 1000 splits, the average decision depth of the best-first CART is 12.3, whereas the TnT decision graph has mean depth of 27.3. In the best-first decision tree induction, we add the best split in each step to maximize the objective 28.. Therefore, TnT can achieve a much " "deeper" " model without significantly increasing the number of splits. The regularization coefficient C' is used to control the complexity of decision graphs in TnT. The number of splits decreases as we increase the pruning strength C (Fig. 3b)). Figures 3lc d) compare the effect of different hyperparameter settings (N1, N2). We note that the proposed Tní decision graph is a superset of decision trees and that TrT can reduce to a DT learning algorithm under certain conditions. With N₁ 1, Algorithm 2 replaces

---

TnT (ffe
TAO CART
NDG
MNIITT (6067704 10)
NNNIST (1087784 10)
Connect-4 (45, (45.34126,
Connect-4 (22 12,3 31
Toal Accusscy (96)
Toun Accurazy (90)
Tesl Accusssy (h6
-8
8
80
75
70
72
600
1000
200
400
600
8.0
1000
1000
1000
1500
Epilts
(8 (8A8M16,, 24)
recognition
10)
Optical recognition (1.8k1
100
100
Text www.hacrryyy (1h)
Toxt Aczumay (K)
It t
00
16
Accursce
0
300
1000
1500
2000
500
1000
1500
2000
50
100
100
200
50
100
120
200
&Bylla
Bpoill
3. &.Bolb
Bylllls
Pendigits (7.5k118, 10)
Pendigits (3.9K118, 10)
Protein (11.96/367) 11..96667,.. 31
Protsin (6.90-957, 31
Tish Accuraay (6)
Test Aoturary (54)
8
14
18
22
08
04
1Splis
Sphtt
Sphts USPS (247256, 21
SenselT (78.86-100.) 3)
SenselT (19.7k-100. 3)
USPS (7.31"256,
01
Tran Aucus May 230)
Trest Acnuurrry (4)
90
80
B
9
88
8
70
150
150
20
Epilits
Figure 4: Model comparison in terms of train and test accuracy on multiple classification tasks. The following axis-aligned decision trees/graphs are included: TnT (this work): We implement the proposed TnT decision graph at various complexity levels. Hyperparameters are fixed at N1 = 2, N2₂ on all tasks. TnT (fine-tuned): The alternating optimization algorithm used to fine-tune the TnT. TAO: The tree alternating optimization algorithm is applied to axis-aligned decision trees CART: Classification and regression trees trained in best-first manner to assess the optimal tree structure under certain complexity constraint [5] 28 NDG: The naive decision graph trained with Algorithm [16). The complexity penalty fixed at C 3e on all tasks. Dataset statisties are indicated on top of each figure with the following format (# Train/Test samples # Features,
29
# Classes).
a single leaf node with a decision tree, which is equivalent to training a CART with cost complexity pruning. In general, higher values of N2 and Nr2 can lead to a better classification performance. the following experiments, we set the hyperparameters as N₁ = 2, N2 5. A marginal improvement in classification performance can be obtained by increasing N₂ and N2, at the cost of increased training time.
Figure 4
compares comparee the proposed TnT decision graphs with axis-aligned decision trees/graphs previ- ously reported. We include the following datasets: MNIST, Connect-4, Letter, Optical reconstruction, Pendigits, Protein, SenseIT, and USPS from the UCI machine learning repository [30] and LIBSVM Dataset (31) under Creative Commons Attribution-Shan including the number of train/test instances, number of attributes, and number of classes are shown in Fig. 4 If separate test set is not available for some tasks, we randomly partition 33% of the entire data as test set. For all models, we repeat the training procedure five times with different random seeds. The mean classification accuracy is plotted in Fig. 4 with shaded area indicating the standard deviation across trials. The proposed Tree Tree (TnT) algorithm outperforms axis-aligned decision trees such as TAO 6 29 and CART 15, as well as NDG which is also based on axis-aligned decision graphs [6]. We also present the results for (fnneett-ddddd which employs alternating optimization to fine-tune the TnI and slightly improve the classification performance.
Alike 3.0 license. The statistics of datasets
7

---

Table 1:
Comparison of TnT and CART at optimal split count (#S, determined by cross-validation). Mean test accuracy (#standard deviation) are calculated on 5 independent trials.
MNIST
Connect-4
Letter
Optical recognition
model
accuracy
#S
accuracy
#S
accuracy
#S
accuracy
#S
TnT CART
90.8711..11 88.59+0.14
78.65-10.46
8.002:10.02
1.2k
86.3
174
1.lk
77.23+00.01
931
86.26+0.15
1.3k
0..56
193
Pendigits
Protein
SenselT
USPS
model
accuracy
#S
accuracy
#S
accuracy
#S
accuracy
#S
TnT CART
92.61=0.533
125
57.26
69
0..48:00.2
198
88.76=1.36
31
91.7410..1
166
55.30
76
79.40
345
87.35
109
The node-sharing mechanism in TnT effectively regularizes the growth of the graph and can increase test performance compared to greedy training of trees (e.g., CART). To show the reduction of variance in TnT decision graphs, we removed the complexity constraints on both models and selected the hyperparameters that achieve the highest cross-validation accuracy on the training set. Table [ compares the proposed TnT method with greedy training of trees. Overall, TnT achieves better test accuracy with reduced model complexity compared to CART.
Visualization Similar to decision trees, TnTT decision graphs enjoy fully interpretable and visual- izable decision process. (eeuressJa-c visualize the TnT decision graphs with 20, 129, and 1046 splits, respectively. We use different node colors to indicate the dominant class labels. A node will have a dominant class if most samples at that node belong to the same class. We show the nodes in blue class labels are mixed (i.e., no class label contributes to greater than 50% of the samples visiting that node). As the graph grows larger, TnT performs better on the MNIST dataset, achieving improved classification accuracy on both training and testing sets.
(a)
(b)
root (c)
root
Figure 5: Visualization of Tn'T decision graphs at various complexity levels. (a) Tn' with 20 internal nodes and 16 leaf nodes (train/test accuracy: 70.41% on MNIST classification task). (b) 129 internals and 75 leaves (train/test accuracy: 85.54%
(c) 1046 internals and 630 leaves (train/test accuracy: 96. 06.04%/90.56%% Different node colors represent dominant class labels (more than 50% samples belong to the same class). Nodes are shown blue no dominant class is found.
5 Experiments: TnT in the ensemble
Decision trees are widely used as base estimators ensemble methods such as bagging and boosting. Random Forests apply a bagging technique to decision trees to reduce variance (32). in which each
base estimator is trained using a randomly drawn subset of data with replacement [33]. As opposed
to bagging, boosting is used as a bias reduction technique where base estimators incrementally added to the ensemble to correct the previously misclassified samples. Popular implementations of the boosting methods include AdaBoost Bd and gradient boosting [3]] Both AdaBoost and bagging use classifiers as base estimators, whereas the gradient boosting methods require regressors B5 36]. Although we argue that the proposed TnT algorithm be applied to regression tasks with a slight modification in the objectives, it is beyond the scope of this paper to demonstrate TnTs as regressors.
Here, we use the TnT decision graphs as base estimators the bagging (Tn'-haaging) and AdaBoost Addaoodoooss) ensembles. Our goal is replace decision trees with the proposed TnI classifiers in
8

---

ensemble methods and compare the performance under various model complexity constraints. The ensemble methods are implemented using the scikit-lear library Python (under the 3-Clause BSD license) 37 We change the ensemble complexity by tuning the number of base estimators E# and the total number of splits (i.e., internal nodes, #S). For Random Forest with 100 trees, we remove the limit on #S. Thus, the trees are allowed to grow as large as possible to better fit on training data. Note that TnT has additional hyperparameters such as N1 and N2. We set the hyperparameters as Ni = 2, N2 = 5 throughout the experiments so that the TnT and tree ensembles share similar hyperparameter exploration space.
Table 2: Comparison of Tn T-bsedd ensembles with conventional random forest and AdaBoost. Mean
train and test accuracy (#: standard deviation) are calculated across 5 independent trials. We tune the ensemble size (#E, the number of base estimators) and split count (#S) to change the complexity of the ensemble. Dataset statistics given in the format: Dataset name (# Train/Test samples # Features, # Classes). Six additional datasets are included in the supplementary materials.
model
#E
#S
train
test
#E
#S
train
test
TuT-baggiig
4.8k
93.65.10.24 96.55++0.36
97.46110.16
4.6k
80.6110.18 84,42::0.19
Random Forest
4.8k
92.31+0.57
Connect-4 (45.31/22 3k 126, 3)
4.6k
83.60+0.12
79.21+00.19
MNIST (60k/10k* 784, 10)
TnT-AdaBoost
5
640
90.26
88.38
450
77.75.0.16
77.39
AdaBoost
6400
89.75
88.61
450
77.28
76.74
Tn TnT-bagging
10
9.6k
98,28 0.06
94.92-10.20
10
9.2k
85.11 0.05
81,44:0.14
Random Forest
10
9.6k
97.44=0.11
03.64+0.38
10
9.2k
84.21=0.12
79.85+#0.20
TnT-AdaBoost
10
1.4k
95.09+00099
0,.36+0.13
10
940
80.10-0.23
78.94+0.29
AdaBoost
10
1.4k
94.28
91.49
10
940
79.69
78.37
TnT-bagging
20
19.2k
08064+00006
95.57=+0.14
20
18.3k
85,66=0012
01.93++0.13
Random Forest
20
19.2k
97.9010.12
94.3610.19
20
18.3k
84.57=0.08
80.39:10.09
TnT-AdaBoost
20
2.9k
98.03.1..11
94,4911..21
20
1.8k
82.46:10.41
80.53:10.50
AdaBoost
20
2.9k
97.70
94.04
20
1.8k
82.77
81.14
TnT-bagging
100
11lk
99.09++0.03
96. 96.11+0.009
100
143k
88.44+0.07
82.84+00022
Random Forest
100
292k
100
95.72+00.7
100
718k
100
82.33++0.10
Table 2 compares the performance of TnT ensembles with that of decision tree ensembles on two datasets. A complete comparison table on eight datasets is included in the supplementary materials. Since the bagging method can effectively reduce variance, we use large models (i.e., TnTs/decision trees with many splits) as the base estimator. On the contrary. TnTs/decision trees with few splits used in the AdaBoost ensemble, given that boosting can decrease the bias error. According to Table 1, TnT-bagging is almost strictly better than Random Forest under the same model complexity constraints, indicating that TnT decision graphs outperform decision trees base estimators. Tn'-- AdaBoost also outperforms AdaBoost in most cases, showing the advantage of Tn' over decision trees. However, we observe few exceptions in the TnT-AdaBoost weak learners with high bias (e.g., decision stumps) are also suitable for boosting ensembles. Overall, the TnT ensembles (Tn T-baggigg TnT-AdaBoost) achieve higher classification accuracy compared to decision trees when used in similar ensemble methods (Random Forest, AdaBoost).
AdaBoost comparison, as
Discussions
Broader impact Recently, the machine learning community has seen different variations of deci- sion trees (13 12 14). In this paper, we present the TnT decision graph as a more accurate and efficient alternative to the conventional axis-aligned decision tree. However, the core idea of TnT (i.e., growing micro trees inside nodes) is generic and compatible with many existing algorithms. For example, Sinear-combinatin
(oblique) splits can be easily incorporated into the proposed TnT framework. Specifically, we can grow oblique decision trees inside the nodes to construct an oblique TnT decision graph (Line 17 of Algorithm 2). In addition to oblique TnTs, the proposed TnT framework is also compatible with regression tasks. As suggested ①. we may grow decision tree regressors (rather than DT classifiers) inside the leaf nodes to construct Tn'T regressors, which remains as our future work. Overall, our results show the benefits of extending the tree structure to directed acyclic graphs, which may inspire other novel tree-structured models in the future.

---

Limitations The proposed TnT decision graph is scalable to large datasets and has linear time complexity the number of nodes in the graph. However, the training of TnT considerably slower than CART. The current ThT algorithm is implemented in Python. It takes about 5 minutes to construct TnT decision graph with ~Ik splits on the MNIST classification task (train/test accuracy: 95.9%/90.4%) Training a CART with the same number of splits requires 12.6 seconds (train/test accuracy: 93.6%/88.3% TnT has a natural disadvantage in terms of training time since each node is optimized multiple times (in this work Ni * N2 10), similar to other non-greedy tree optimization algorithms (e.g., I-4 minutes for TAO (6). The Python implementation may also contribute the slow training, and expect that the training time would significantly improve with an implementation in C. The longer training time prevents us from constructing large TnT--daboost ensembles that follow sequential training process, where the training time increases linearly to the number of base estimators. We also observe that Tn'T decision graphs have longer decision paths compared to CART (Figure a)), a)), which may raise concern on increased inference time. Since Tn'T uses a pruning factor (C) to control the model complexity, we can not precisely control the number of nodes as in CART. In the experiments, we searched over range of C' values to meet the model complexity constraints.
Parallel implementation Algorithm 2 presents a sequential algorithm to construct TnT decision graphs by visiting the nodes in the breadth-fin order. However, it is also possible to concurrently grow micro decision trees inside multiple nodes, which could lead to parallel implementation of Tn'T. Specifically, only those nodes in the graph that are non-descendant of each other can be optimized in parallel. Parallel optimization is not applicable to the nodes on the same decision path, since the parent node optimization may alter the samples visiting the child node. The parallel optimization of non-descendant nodes follows the separability condition of TAO [1 The separability condition also holds for the proposed TnT decision graph, enabling parallel implementation.
7 Conclusion
In this paper, we propose the Tree in Tree decision graph as an effective alternative to the widely used decision trees. Starting from a single leaf node, the TnT algorithm recursively grows decision trees to construct decision graphs, extending the tree structure to more generic directed acyclic graph. We show that the TnT decision graph outperforms the axis-aligned decision trees on a number of benchmark datasets. We also incorporate TnT decision graphs into popular ensemble methods such as bagging and AdaBoost, and show that in practice, the ensembles could also benefit from using Tn''s as base estimators. Our results suggest the use of decision graphs rather than conventional decision trees to achieve superior classification performance, which may potentially inspire other novel stre-structure models in the future.
Acknowledgments and Disclosure of Funding
We thank Dr Masoud Farivar from Google for his valuable feedback and comments on this manuscript. This work was partially supported by a Google faculty research award in machine learning.
References
[1] Arman Zharnagambetov and Miguel Perpinan. Smaller, more accurate regression forests using tree alternating optimization. In International Conference Machine Learning, pages 11398-1140S PMLR, 2020.
[2] Ashish Kumar, Saurabh Goyal, and Manik Varma. Resource-efficient machine learning in 2 kb ram for the internet of things. In International Conference on Machine Learning, pages 1935-1944. PMLR, 2017.
[3] Bingzhao Zhu, Masoud Farivar, and Mahsa Shoaran. Resot: sesource-efficienn oblique trees for neural signal classification. IEEE Transactions Biomedical Circuits and Systems, 14(4):692 704, 2020.
[4] Mahsa Shoaran, Benyamin Allahgholizadeh Haghi, Milad Taghavi, Masoud Farivar, and Azita Emami- Neyestanak. effegyeefficient classification for constriiied biomedical applications. IEEE Journal Emerging and Selected Topics in Circuits and Systems, 8(4))693-777) 2018.
10

---

[5] Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference Machine Leurning, pages 6166-6175. PMLR, 2019.
[6] Miguel A Carreira-Peryee Perpinán and Pooya Tavallali. Alternating optimization of decision trees. with applica- tion to learning sparse oblique trees. Advances in Neural Information Processing Systems, 2018.
[7] Charles Mathy, Nate Derbinsky, José Bento, Jonathan Rosenthal, and Jonathan Yedidia. The boundary forest algorithm for online supervised and unsupervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
leaming
[8] Bingzhao Zhu, Uisub Shin, and Mahsa Shoaran. Closed-loop neural prostheses with on-chip intelligence: review and low-latency machine learning model for brain state detection. IEEE Transactions on Biomedical Circuits and Systems, 2021.
[9] Andrew Silva, Matthew Gombolay. Taylor Killian, Ivan Jimenez, and Sung-Hyun Son. Optimization methods for interpretable diffeernntablee decision trees applied to reinforcement learninng.... In International Conference on Artificial Intelligence and Statistixs, pages 1855-1865. PMLR, 2020.
[10] Scott Lundberg and Su-In I.ce. A unified approach interpreting model predictions. arXiv preprint 1705.0777 2017.
[11] Min Lin, Qiang Chen, and Shuicheng Yan. Network in network. arXiv preprint arXiv:1312.4400, 2013.
[12] Mohammad Norouzi, Maxwell D Collins, Matthew Johnson, David J Fleet. and Pushmeet Kohli. Efficient non-greedy optimization of decision trees. arXiv preprint arXiv: 11111111100000 2015.
[13] Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. Deep neural decision forests. In Proceedings of the IEFE international conference computer vision, pages 1467-1475, 2015.
[14] Hussein Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan, and Rahul Mazumder. The tree ensemble layer: Differentiability meets conditional computation. In International Conference on Machine Learning, pages 4138 4148. PMLR, 2020.
[15] Dan Steinberg and Phillip Colla, Cart: classification and regression trees. The top ten algorithuss in data mining, 9:179, 2009.
[16] Jonathan Oliver. Decision graphs: an extension of decision trees. Citeseer, 1992.
[17] Hiroki Sudo, Koji Nuida, and Kana Shimizu. An efficient private evaluation of decision graph. In International Conference on Information Security and Cryptology, pages 143-160. Springer, 2018.
[18] Djamel Abdelkader Zighed. Induction Graphs for Data Mining, pages 419-430. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007.
[19] Djalel Benbouzid, Röbert Busa-Fekete,, and Balázs Kégl. Fast classification using sparse decision dags. arXiv preprint 1rXiv:1206.6387 2012.
[20] John C Platt, Nello Cristianini, John Shawe-Taylor, et al. Large margin dags for multiclass classification. In nips, volume 12, pages 547-553, 1999.
[21] Jamie Shotton, Toby Sharp, Pushmeet Kohli, Sebastian Nowozin, John Winn, and Antonio Criminisi. Decision jungles: Compact and rich models for classification. In NIPS'13 Proceedingy of the 26th International Conference on Neural Information Processing Systems, pages 234-242, 2013.
[22] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. International Conference Machine Learning, pages 6150-6160. PMLR, 2020.
[23] Haoran Zhu, Pavankumar Murali, Dzung T Phan, Lam M Nguyen, and Jayant R Kalagnanam. A scalable masedased method for learning optimal multivariate decision trees. arXiv preprint arXi::201..3337. 2020.
[24] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[25] Hyafil I Laurent and Ronald I. Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
[26] Jeffrey P Bradford, Clayton Kunz, Ron Kohavi, Cliff Brunk, and Carla E Brodley. Pruning decision trees with misclassificattin costs. In European Conference on Machine Learning, pages 131- Springer, 1998.
11

---

[27] B Ravi Kiran and Jean Serra. Cost-complexity pruning of random forests. In International Symposium on Mathematical Morphology and Its Applications to Signal and Image Processing, pages 222-232. Springer, 2017.
[28]
Haijian Shi. Best-first decision learning. PhD thesis. The University of Waikato, 2007.
[29] Arman Zharmagambetov, Suryabhan Singh Hada, Miguel Á Carreira-Perpihán, and Magzhan Gabidolla.
An experimental comparison old and new decision tree algorithms. arXiv preprint 1rXiv:1911.0305.
2019.
[30] irvine machine learning repository, h http:///aaareieesssssuuuucoiiiii Accessed: 2021-05-02.
[31] Libsvm data. wttp://www....uuuu/////oo/oooooa Accessed: 2021-05-
02.
[32] Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
[33] Leo Breiman. Bagging predictors. Machine learning, 24(2):123 140. 1996.
[34] Yoav Freund and Robert E Schapire. A decision-theeretic generalization of on-line learning and an application boosting. Journal of computer and system sciences, 55(1):119-13,, 1997.
[35] Tianqi Chen and Carlos Guestrin. Xghoost: A scalable tree boosting system. In Proceedings of the 22nd sigkdd international conference knowledge discovery and data mining, pages 785-794 2016.
[36] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. Advances neural information processing systems, 30:3 146 3154, 2017.
[37] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel. B. Thirion, O. Grisel. M. Blondel, P. Prettenhofer. R. Weiss, Dubourg. J. Vanderplas, A. Passos, Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-lear: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2838 2011.
12


Reviews:
[{"review_id": "uhvzO5sBjLJ", "reviewer": "Reviewer_GefL", "summary": "This paper proposes an algorithm to build decision graphs. The idea of this algorithm is to recursively replace internal nodes as well as leaf nodes in a decision tree by a small decision tree. In the case of internal nodes, this decision tree is grown to optimally direct the examples falling into that node to the left or right successor of the replaced node. In the case of leaf nodes, the small tree is grown to predict the target. Experiments compare the approach with standard CART tree and ensembles.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of building decision graphs is not new but it is interesting. The way the authors motivate them in the paper is however not very convincing. They draw a parallel between TnT and oblique trees, which suggest that TnT are more expressive that standard trees and that's the reason they are expected to be more accurate. This is actually not the case, since any decision graph can indeed be represented by a (more complex) decision tree. In my opinion, the main interest of graphs instead of trees is the reduced size of the model and the potential reduction of variance (because using a graph allows to avoid the sample size reduction effect inherent to tree partitioning).\n\nThe proposed algorithm to grow graphs is original to the best of my knowledge. The related work section is however incomplete. There are a number of other decision graph training algorithms, such as the following two (and several other references therein):\n* Zighed D.A. (2007) Induction Graphs for Data Mining. In: Brito P., Cucumel G., Bertrand P., de Carvalho F. (eds) Selected Contributions in Data Analysis and Classification. Studies in Classification, Data Analysis, and Knowledge Organization. Springer, Berlin, Heidelberg.\n* Jamie Shotton, Sebastian Nowozin, Toby Sharp, John Winn, Pushmeet Kohli, and Antonio Criminisi. 2013. Decision jungles: compact and rich models for classification. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1 (NIPS'13).\n\nI think the proposed method should be discussed and compared more thoroughly with this literature.\n\nIn the end, I think I managed to understand the main idea of the algorithm but the description could have been clearer. What confused me the most was how internal splits are expanded into micro-trees, i.e., the way labels are constructed to train these micro-trees (as explained in 3.1). Part of the confusion comes from the fact that some notations are not clearly explained (e.g., in (5) what is $G_{n_i\\rightarrow left}$  and why does it take as its first argument a subset $X$, and not a single $x$ as $G$).\n\nIn Section 3.3, a discussion and motivation for the introduction of the parameters $N_1$ and $N_2$ in Algorithm 2 is missing and this added to my confusion (there is more discussion of these parameters in the supplementary material however). Why wait for $N_2$ steps of node expansion before merging? Actually, why not merging after each micro tree construction inside the \"for each node ($n_i$)\" loop? In line 17, there is a reference to $t_i$ while we are outside the loop over $n_i$. What does it mean to merge $t_i$ there? Is the indentation correct?\n\nAlso, if I understand correctly, the order in which the nodes are considered in the loop in Line 5 matters (since changing an internal node into a replacement micro-tree will change the prediction for the samples falling into that node and thus will have an impact on its ancestors). If this is correct, it's not clear from the paper which order is used in practice.\n\nOverall, the algorithm to construct these graphs makes sense and I like the idea of trees in trees. One drawback of the approach however is the introduction of the three hyper-parameters $N_1$, $N_2$, and $C$, whose interplay is not very clear. The authors seem also to put more emphasis on setting $C$ than on setting $N_1$ and $N_2$, which are mainly fixed to arbitrary default values. I have the feeling that it would be possible to have a single hyper-parameter. For example, why setting $N_2$ to 1 is not enough?\n\nThe experiments show that there is a benefit in using graphs in terms of accuracy. Methods are compared however at fixed number of splits and I don't think it's appropriate (or at least enough). First, there is no mechanism in TnT to set precisely the number of nodes and thus, this is not a very natural comparison (in practice, this is not how the method will be used). Second, one of the main benefits of CART is that it's a non-parametric method that can adapt model complexity to the problem at hand (using pruning). I would thus compare both methods at their optimum complexity (determined by CV), in terms of accuracy, number of splits and inference time.\n\nThe same comment applies for the comparison within ensembles. The number of ensemble terms and the number of nodes is arbitrarily set to small numbers in the experiment, while in practice, RF are used with unpruned trees and ensembles of hundreds of trees are averaged. Showing that TnT ensembles are better than suboptimal forests is not a very convincing result in my opinion. \n\nMinor remarks:\n* Equation (4) is said to be an optimisation problem, which closed-form solution is (5). I don't understand notations in (5). What is optimized? Why is the sum over all examples? What is the value of $G_{n_i\\rightarrow left/right}(x)$ for samples that do not reach $n_i$? \n* The synthetic examples show indeed the potential benefit of using a DAG instead of a tree, if one wants to reduce the number of splits. It's not clear however whether the proposed algorithm is able to produce the graph in 2(c) for such problem given the heuristic nature of the algorithm. If not, then I think presenting this example after having presented the algorithm is a bit misleading.\n* In Figure 4, are CART trees fully grown when the maximum number of splits is reached or would it be possible to grow them further? I was expecting the accur I'm not sure that the maximum number of splits.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "cd6pF76Vaag", "reviewer": "Reviewer_Vnre", "summary": "The paper proposes an algorithm to build decision acyclic graphs with properties similar to those of decision trees: each node has a split condition to route instances and terminal nodes of the graph (i.e. those without children) provide the classification labels.  This model is trained by creating embedded decision trees inside decision the graph nodes iteratively. The algorithm starts with a single leave node in which, a small decision tree is build to route the examples to left/right. Then the decision tree internal decision tree of the node is flattened to create a graph. The acyclic graph structure appears since all left/right decisions of the embedded tree are routed to the same left/right graph node. Then, for each node the same process is applied iteratively.\n\nThe method is used as the base classifier of bagging and Adaboost ensembles and compared on 8 datasets against standard decision trees with RF and Adaboost using the same over all complexity (complexity measured as number of splits).", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and quite clear, although some aspects could be further clarified (see below).\n\nI have some issues/doubts bout the paper:\n* The description of algorithm 1 is partial and a bit unclear. For instance, N1 and N2 are not described when the algorithm is introduced. I believe that N1 is the number of times the DT in the nodes of the graph are flattened. N2 remain unclear, why does the algorithm goes N2 times over all nodes of the graph to build a DT at each node? Also in line 2, t subscript appears but it is not defined before, Should be 0 instead of t? In addition, infer function is only explained with a comment in the algorithm. I suppose it is related to eq (6). \n* One unclear aspect to me is how he complexity of the models are gauged for the experiments. I understand that there is a C hyper-param that could be used to limit the complexity of the mini decision trees but it is unclear to me how to limit the over all complexity of the decision graph. For intance, are the curves in Fig3(c,d) obtained modifying C or do they use a fixed C? If so, which one? if not, how the C is modified? Idem for Fig4. Also in Fig4, how are the complexity of CART controlled? Using C? max_depth? other? A curious aspect is that for most plots, there is o over-fitting with the increment of the complexity of trees and graphs.\n* The article says \"With 1000 splits, the average decision depth of the best-first CART is 12.3,whereas the TnT decision graph has a mean depth of 27.3.\" Is it a good thing that the paths are longer? How about the performance of DT and DG at equal path lengths?\n* The comparison of TnT +bagging/adaboost with standard RF and adaboost is done in the context of equal complexity in terms of number of base models and overall number of splits. Again, the process to achieve this equal complexity is unclear. Is the C set for TnT ensembles and then using the obtained complexity, the standard ensembles are created with different max_depth (?) until they reach the same complexity? Any way I believe the comparison has to be done also without constrains for both methods. Using a maximum number of base DT of 20 (#E) is clearly suboptimal for RF and adaboost. Also using a limiting number of split for RF is suboptimal. The results of a fully trained RF (#E=100-200, and no splits limit) and adaboost should also be reported.\n\nMinor aspects:\n* Sometimes the paper is a bit repetitive (e.g. lines 164-171). \n* Figure 2 plots (N 1 = 2, N 2 = 5) in c) and d) with different colour. it would be clearer to use the same colour.\n* Fig 5: It could be interesting to mark the root node in the plots. Also plot b) could be unentanled a bit to better visualize.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "_M0ePTnWGo", "reviewer": "Reviewer_nBwC", "summary": "The authors present a new algorithm for large decision graphs. Tree in a tree is a scalable method that fits new decision trees in place of the internal/leaf nodes and constructs a directed acyclic graph. The authors show that their method outperforms other learning models in different datasets with different configurations.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* Positive points:\n- The paper is well written and well structured. The authors are clear and objective in their communication.\n- The experimental procedure sounds robust, with various datasets and classification methods (decision trees/graphs).\n- The time complexity sounds good, even though the authors state very clearly that CART and TAO would be more efficient.\n\n* Negative Points:\n- Since the authors are using accuracy to quantify the power of their method, I believe more classification methods should be used in their study.  If the authors were accessing the readability of the final graph, it would be understandable to only use other decision trees and graphs as the benchmark. However,  accuracy-wise, other classification methods (e.g., neural networks and kernel machines) should be used as well.\n- Considering that decision trees are sometimes used for their explainability, I would have liked to see each dataset's result. Figure 5 is not readable or understandable.\n- I do not believe that the limitations written by the authors are limitations at all. A trade-off is clear for me in terms of accuracy versus training time. I would have like to see more limitations on this work or a more robust argumentation on why this limitation is essential for TnT.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "_JjjfBTiZmP", "reviewer": "Reviewer_gGfV", "summary": "Inspired from Network in Network the paper proposes an extension of decision trees that replaces internal and leaf nodes with micro decision trees, thus extending decision trees to decision graphs.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In particular the authors propose a learning algorithm for decision graphs adopting a simple and effective iterative algorithm.\n\nIt should be interesting to explain why a decision graph has an accuracy greater than that of decision tree. Since there are shared decision paths, it seems that the decision power of a graph is lower than that of a tree. Probably it is due to deeper models involving more splits on the path to the leaf. A discussion should be interesting.\n\nThe learning approach presented in section 3 is clear and well presented.\n\nFinally, the experimental evaluation proves that the TnT decision graph outperforms the axis-aligned decision trees on a number of benchmark datasets.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation regards the time complexity of the proposed approach.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a way to to grow decision graphs by using decision trees as the splitting criterion of another tree. Reviewers praised the simplicity of the idea and its effectiveness on classification tasks.

During the reviewing and rebuttal phase, some criticisms regarding missing references and more crucially missing experiments with suitable comparisons were raised.
Authors provided additional convincing results in the rebuttal and managed to convince one reviewer to upgrade its weak rejection score into a weak acceptance.

The paper is accepted, subject to including the missing comparisons to the literature, and the additional baselines and experiments discussed in the rebuttal.
Decision: Accept (Poster)