Analyzing Tree Architectures in Ensembles via Neural Tangent Kernel
Authors: Ryuichi Kanoh
Mahito Sugiyama
Venue: ICLR 2023 poster (2023)
Keywords: Neural Tangent Kernel
Tree Ensemble
Soft Tree

Abstract: A soft tree is an actively studied variant of a decision tree that updates splitting rules using the gradient method. Although soft trees can take various architectures, their impact is not theoretically well known. In this paper, we formulate and analyze the Neural Tangent Kernel (NTK) induced by soft tree ensembles for arbitrary tree architectures. This kernel leads to the remarkable finding that only the number of leaves at each depth is relevant for the tree architecture in ensemble learning with an infinite number of trees. In other words, if the number of leaves at each depth is fixed, the training behavior in function space and the generalization performance are exactly the same across different tree architectures, even if they are not isomorphic. We also show that the NTK of asymmetric trees like decision lists does not degenerate when they get infinitely deep. This is in contrast to the perfect binary trees, whose NTK is known to degenerate and leads to worse generalization performance for deeper trees.

Published as a conference paper at ICLR 2023
ANALYZING TREE ARCHITECTURES IN ENSEMBLES VIA NEURAL TANGENT KERNEL
Ryuichi Kanoh Mahito Sugiyama" 1.2 Nattional Institute of Informatics The Graduate University for Advanced Studies, SOKENDAL kaanoh, mahito J@nii ac.
ABSTRACT
A seft free is actively studied variant of decision tree that updates splitting rules using the gradient method. Although soft trees can take various architec- tures, their impact is not theoretically well known. In this paper, formulate and analyze the Neural Tangent Kernel (NTK) induced by soft tree ensembles for arbitrary tree architectures. This kernel leads to the remarkable finding that only the number of leaves at each depth is relevant for the tree architecture in ensemble learning with an infinite number of trees. In other words, if the number of leaves at each depth is fixed, the training behavior in function space and the generaliza- tion performance are exactly the same across different tree architectures, even if they are not isomorphic. We also show that the NTK of asymmetric trees like decision lists does not degenerate when they get infinitely deep. This contrast to the perfect binary trees, whose NTK is known to degenerate and leads to worse generalization performance for deeper trees.
INTRODUCTION
Ensemble learning is one of the most important machine learning techniques used in real world applications. By combining the outputs of multiple predictors, it is possible to obtain robust re- sults for complex prediction problems. Decision trees are often used as weak learners in ensemble learning (Breiman 2001] Chen & Guestrin 2016 Ke et al., (017), and they can have a variety of structures such as various tree depths and whether or not the structure symmetric. In the training process of tree ensembles, even decision stump (Iba & Langley] 1992). decision tree with the depth of 1, is known to be able to achieve zero training error as the number of trees increases (Freund & Schapire 1996). However, generalization performance varies depending cct al.] 2017), J. and the theoretical properties of their impact are not well known, which results in the requirement of empirical trial-and-erro adjustments of the structure of weak learners.
weak learners (Liu
In this paper, we focus on a soft tree (Kontschieder et al., 2015 Frosst & Hinton 2017) as a weak learner. A soft tree is variant of decision tree that inherits characteristics of neural networks. Instead of using a greedy method (Quinlan 1986; Breiman et al., 1984) to search splitting rules, soft trees make decision rules soft and simultaneously update the entire model parameters using the gradient method. Soft trees have been actively studied in recent years in terms of predictive performance (Kontschieder et al., [2015] Popov al. 2020 Hazimeh al.) 2020), interpretabil- ity (Frosst & Hinton] 2017] Wan et al. 2021), and potential techniques in real world applications like pre-training and fine-tumin ine-tunnng (Ke al. 2019 Arik & Phister 2019). In addition, a soft tree can be interpreted as a Mixture-or of of-Experts (Jordan & Jacobs 1993] Shazeer et al. 2017 Lepikhin et al.)
2021. practical technique for balancing computational cost and prediction performance.
To theoretically analyze soft tree ensembles, Kanoh & Sugiyama (0022) introduced the Neural Tan- gent Kernel (NTK) (Jacot et al., (0188) induced by them. The NTK framework analytically describes the behavior of ensemble learning with infinitely many soft trees, which leads to several non-trivia properties such as global convergence of training and the effect of parameter sharing in an obliv- ious tree (Popov et al. 2020 Prokhorenkova et al. 2018). However, their analysis is limited to specific type of trees, perfect binary trees, and theoretical properties of other various types of tree architectures are still unrevealed.

---

Published as a conference paper at ICLR 2023
Figure Iillustrates representatives of tree archi- tectures and their associated space partitioning in the case of two-dimensional space. Note that each partition is not the axis parallel di- rection only symmetric trees, as shown in (a) and (b), but also asymmetric trees (Rivest 1987). as shown in (c), are often used in practical ap- plications (Tanno et al.) 2019). Moreover, the structure in (d) corresponds to the rule sel en- sembles (Friedman Popescu 2008), a combi- nation of rules to obtain predictions, which can be viewed as a variant of trees. Although each of these architectures has different space par- titioning and is practically used, is not theo- retically clear whether not such architectures make any difference in the resulting predictive performance in ensemble learning.
considering soft trees. Not
Figure 1: Schematic image of decision bound- aries in an input space split by the (a) perfect bi- nary tree, (b) oblivious tree, (c) decision list, and (d) rule set.
In this paper, we study the impact of free architectures of soft tree ensembles from the NTK view- point. We analytically derive the NTK that characterizes the training behavior of soft tree ensemble with arbitrary tree architectures and theoretically analyze the generalization performance. Our con- tributions can be summarized as follows:
The NTK of soft tree ensembles is characterized by only the number of leaves per depth. We derive the NTK induced by an infinite rule ensemble (Theorem 2 Using this kernel, we obtain formula for the NTK induced by an infinite ensemble of trees with arbitrary architectures (Theorem 3). which subsumes (Kanoh & Sugiyamal 2022, Theorem 1) as special case (perfect binary trees). Interestingly, the kernel is determined by the number of leaves at each depth, which means that non-isomorphic trees can induce the same NTK (Corollary [T].
The decision boundary sharing does not affect to the generalization performance.
Since the kernel determined by the number of leaves at each depth, infinite ensembles with trees and rule sets shown in Figure aaa and (d) induce exactly the same NTKs. This means that the way which decision boundaries are shared does not change the model behavior within the limit of an infinite ensemble (Corollary 2).
The kernel degeneracy does not occur in deep asymmetric trees.
The NTK induced by perfect binary trees degenerates when the trees get deeper: the kernel values become almost identical for deep trees even if the inner products between input pairs are different, resulting in poor performance in numerical experiments. In contrast, we find that the NTK does not degenerate for trees that grow in only one direction (Proposition T hence generalization performance does not worsen even if trees become infinitely deep (Proposition 2 Figure 8)
2
PRELIMINARY
We formulate soft trees, which we use as weak learners ensemble learning, and review the basic properties of the NTK and the existing result for the perfect binary trees.
2.1
SOFT TREES
Let us perform regression through an ensemble of M soft trees. Given a data matrix æ E PxN composed of N training samples æ1...., ., EN with F' features, each weak learner, indexed by m
[M] = {1...., ..... M). has parameter matrix wm E RR FxN for internal nodes and nm E R x for leaf nodes. They are defined in the following format:
Wm,N'' ). n... (Tm,1. Tm,c)
EN
Wm
Wm.1
where internal nodes and leaf nodes are indexed from 1 to N and to L, respectively. For simplicity, assume that A and are the same across different weak learners throughout the paper.
2

---

Published as a conference paper at ICLR 2023
2.1.1 INTERNAL NODES
In a soft tree, the splitting operation at an intermediate node E [W] {l, [I,...,AN ,N pletely binary. To formulate the probabilistic splitting operation, we introduce the notation / (resp. > E), which is a binary relation being true if leaf & [c] {I.....4) belongs to the left (resp. right) subtree of node and false otherwise. We also use an indicator function 1ą on the argument Q: that is, l the probability that data reach to it, which is formulated function jun. : IR. RR [0.1] defined as
not com-
Q true and Q otherwise. Every leaf node l [4] holds
Pm,ee (224, wm) = II
a (w 2i Ar (1 - (w m, m.)))
(1)
==1
right
where [0, 1] represents softened Boolean operation at internal nodes. The obtained value (2, Wm) is the probability of a sample e; reaching a leaf & in soft tree m with its parameter matrix Wm. If the output of decision function takes only 0.0 or 1.0, this operation realizes the hard splitting used in typical decision trees. We do not explicitly use the bias term for simplicity as can be technically treated as an additional feature.
Internal nodes perform as a sigmoid-like decision function such as the scaled error function (p) crf(ap) 1 2 S0 e- dt) + 2 the two-class sparsemax function a(p) sparsemax[[ap, 0]) (Martins & Astudillo 2016), or the two-class entmaxx function op) = entmax( (ap, 0j) (Peters al. 2019). More precisely, any continuous function is possible if it tationally symmetric about the point (0, 1/2) satisfying limp-ses (p) = limp---oo (p) = 0. and (0) 0.5. Therefore, the theoretical results presented in this paper hold for variety of sigmoid- like decision functions. When the scaling factor a E IR+ (Frosst & Hinton 2017) is infinitely large, sigmoid-like decision functions become step functions and represent the (hard) Boolean operation.
Equation [ applies to arbitrary binary tree architectures. Moreover, the flow to the right node [.,) }) is replaced with it clear that the resulting model corresponds to rule set (Friedman & Popescul 2008), which can be represented as linear graph. Note that the value
(1 (ww ".
2== Mm,p(a;; W..) is always guaranteed to be for any soft trees, while it is not guaranteed for rule sets.
2.1.2 LEAF NODES
The prediction for each æ; from weak learner m parameterized by wm. and Tm, represented function fm 1º x IR FXN x RIxE + IR, is given by
fm (Biy Wm, Tm)
Σ Emm. e Wm):
where Tm, denotes the response of a leaf of the weak learner m. This formulation means that the prediction output is the average of leaf values Tm. weighted by Mm,e M Wm), the probability of assigning the sample æ; to the leaf e. In this model, wm and Tm are updated during training with gradient method. If pm, (3:, w..) takes the value of only 1.0 for one leaf and 0.0 for the other leaves, the behavior of the soft tree is equivalent to typical decision tree prediction.
2.1.3 AGGREGATION
When aggregating the output of multiple weak learners in ensemble learning, we divide the sum of the outputs by the square root of the number of weak learners, which results in
M
f(x,, w. πT)
Σ m==1
fm( Wm. Tm).
(3)
This 1/VM scaling is known to be essential in the existing NTK literature to use the weak law of the large numbers (Jacot et al. 2018). Each of model parameters Wm., and Tm, & initialized with zero-mean i..dd Gaussians with unit variances. We refer such an initialization as the NTK initialization.
3

---

Published as a conference paper at ICLR 2023
2.2 NEURAL TANGENT KERNEL
For any learning model function y, the NTK induced by at training time т is formulated as matrix H E RRNN,, in which each (i.j) E [N] x [N] component is defined as
= ( (g((z, x. 0-) 0g(z,, H = (c,,,
00, (
(4)
a0,
where θ IR XF + R. The bracket (. denotes the inner product and 0- E R is concatenated vector of all trainable parameters at the training time T. An asterisk that the model is arbitrary. The model function 9 R. x IRP - lE used in Equation 4 is not limited neural networks, and expected be a variety of models. we use soft trees introduced in (f(a..w.T) 0f(a,,wm O.mm.
indicates
Section 2.1 weak learners, the NTK is formulated Σm En=1 (
mmm..
ΣM
(. m== @f(x..w.T) dam. 8m...
If the NTK does not change from its initial value during training, one could describe the behavior of functional gradient descent with an infinitesimal step size under the squared loss using kernel ridge- less regression with the NTK (Jacot et al. 2018 Lee et al.) 2019), which leads to the theoretical understanding of the training behavior. Such property gives us data-dependent generalization bound (Bartlett & Mendelson) 2003), which is important in the context of veee-parametteizztion. The kernel does not change from its initial value during the gradient descent with an infinitesimal step size when considering an infinite width neural network (Jacot et al. 2018) or infinite number of soft perfect binary trees (Kanoh & Sugiyama, 2022) under the NTK initialization. Models with the same limiting N7K, which is the NTK induced by model with infinite width infinitely many weak learners, have exactly equivalent training behavior in function space.
The NTK induced by soft ensemble with infinitely many perfect binary trees, that is, the NTK when M > 00, is known to be obtained in closed-form at initialization:
Theorem (Kanoh Sugiyama (2022))- Let u R be any column vector sampled from zero- mean i.i.d. Gaussians with unit variance. The NTK for an ensemble of soft perfect binary trees with tree depth converges probability to the following deterministic kernel as M - 0C,
(I,, (DD,)) = lim (D.PB)
(Is, 2z)
M -00
2 D E(a;, 2t (T) (w 2,) 20,) + (2T (x 1;))
(5)
contribution from internal nodes
contribution from leaves
= where E(x;, 20)) = x; T(x:, 2zj) = Elo (u" xe do:)o( xz))). and T(x 2r,)) Elō(u" v,)ā(uu wz)]. Moreover, when the decision function is the scaled error function, T(x,, x.2)) and T(,;, a;) are analytically obtained in the closed-form
1
a²E(z,, x.,)
T(x,, = arcsin
+
(6)
2n
Vaa x;i 0.5) 0. + 0.5)
T( = a²
π / 2a (z, 2; (1+
4a (2, 0,,,
Here, "PB" stands for "P"erfect "B"inary tree. The dot used in ou TTTT Tx;) means the first derivative, and E[] means the expectation. The scalar ı in Equation 6 and Equation is the circular constant, and u corresponds Wm.n at any internal nodes. We can derive the formula of the limiting kernel by treating the number of trees in a tree ensemble like the width of the neural network, although the neural network and the soft tree ensemble appear be different models.
THEORETICAL RESULTS
We first consider rule ensembles shown in Figure d and provide its NTK in Section 3.1 This becomes the key component to introduce the NTKs for trees with arbitrary architectures in Section 3.2 Due to space limitations, detailed proofs given in the Appendix.
4

---

Published as a conference paper at ICLR 2023
0.0.0
0009
0.000
9-0-00
9.0.0
0-0-0-
0-0-0-0
000
0
g
or 0
Figure 2: Correspondence between rule sets and binary trees. The top shows the corresponding rule sets for the bottom tree architectures.
3.1 NTK FOR RULE SETS
We prove that the NTK induced by a rule set ensemble is obtained in the closed-form as M + 0o at initialization:
Theorem 2.
The NTK for an ensemble of M soft rule sets with the depth D converges in probability the following deterministic kernel as M oc,
e (D Rule) [)) = lim t (D.lle)
(z), 23))
M-
D (( (a,, P-
(x)),
contribution from internal nodes
contribution from leaves
We can see that the limiting NTK induced by an infinite ensemble of 2 rules coincides with the limiting NTK of the perfect binary tree in Theorem |
(D. (æ;; x;) = ( (x., mz). Here, 2D corresponds the number of leaves in a perfect binary tree. Figure gives us an intuition: by duplicating internal nodes, we always construct rule sets that correspond to given tree by decomposing paths from the root to leaves, where the number of rules the rule set corresponds to the number of leaves in the tree.
3.2 NTK FOR TREES WITH ARBITRARY ARCHITECTURES
Using our interpretation that a tree is combination of multiple rule sets, we generalize Theorem include arbitrary architectures such as an asymmetric shown in the right panel of Figure 2
Theorem 3. Let Q N + N U {0} be function that receives any depth and returns the number of leaves connected to internal nodes at the input depth. For any tree architecture, the NTK for an ensemble of soft trees converges in probability to the following deterministic kernel as M +
+ ((Abbirrayyree)) (2:,, = lim
(x)
6 (ArbitraryTooc (x; 1.)
Σ Q(d) (dd.Rule) d=1
(x:; 2.))
(9)
M-000
We can see that this formula covers the limiting NTK for perfect binary trees 2 2D, (x,, Rz)) special case by letting Q(D) 2 and otherwise.
Kanoh & Sugiyama 2022) used mathematical induction to prove Theorem T However, this tech- nique is limited to perfect binary trees. Consequently, have now invented alternative way of deriving the limiting NTK: treating a tree as a combination of independent rule sets using the sym- metric properties of the decision function and the statistical independence the leaf parameters.
is also possible to show that the limiting kernel does not change during training:
Theorem 4. Let Amin and \max be the minimum and maximum eigenvalues of the limiting NTK. Assume || [xi||== for all E [N] and x; + wj (i j). For ensembles of arbitrary soft trees with the NTK initialization trained under gradient flow with a learning rate < 2/ 2/(miin + Amax) and positive finite scaling factor a, have, with high probability.
sup Q GArbittrryTree Tree) (I, x.2))
G (ArbitraryTro)))
(x; x.))
=
(10)
VM
Therefore, analyze the training behavior based kernel regression.
5

---

Published as a conference paper at ICLR 2023
Figure 3: Non-isomorphic tree architectures used in ensembles that induce the same limiting NTK.
Mf = 16
M 4096
Shape Shape
Stape: Stape B
2001
400
600
500
1000
0
200
410
600
100
1000
(lenation)
(itesdioo)
Figure 4: Output dynamics for test data points. Each line color corresponds to each data point.
Each rule set corresponds to a path to a leaf tree, as shown in Figure 2 Therefore, the depth of rule set corresponds to the depth at which a leaf is present. Since Theorem 3 tells us that the limiting NTK depends on only the number of leaves at each depth with respect to tree architecture, the following holds:
Corollary 1. The same limiting NTK can be induced from trees that are not isomorphic.
For example, for two trees illustrated in Figure Q(1) O, Q(2) 2, and Q(3) = 4. There- fore, the limiting NTKs are identical for ensembles of these trees and become (2.Rul))) (x, æz)) + (3.Ru) (xx,, 2.)) Since they have the same limiting NTKs, their training behaviors in function space and generalization performances are exactly equivalent when we consider infinite ensembles, although they are not isomorphic and were expected to have different properties.
To see this phenomenon empirically, we trained two types of ensembles; one is composed of soft trees in the left architecture in 3igure3aand the other is in the right-hand-side architecture in Figure We tried two settings, .M = 16 and M = 4096, to see the effect of the number of trees (weak learners). The decision function a scaled error function with during full- gradient descent with a learning rate of 0.1. Outputs at initialization are shifted zero (Chizat al., 2019). There are 10 randomly generated training points and 10 randomly generated test data points with dimension F 5. Each line corresponds to each data point, and solid and dotted lines denote ensembles of left and right architecture, respectively. This result shows that two trajectories (solid and dotted lines for each color) become similar if M is large, meaning that the property shown in Corollary [ is empirically effective.
2.0. Figure shows trajectories
When compare rule set and tree under the same number of leaves shown in Figure I a) and (d), it is clear that the rule set has larger representation power as has more internal nodes and no decision boundaries in a tree the same as the corresponding rule set as shown in Figure 2 their limiting NTKs are equivalent. Therefore, the following corollary holds:
shared. However, when the collection of paths from the root to leaves
Corollary 2. Sharing of decision boundaries through parameter sharing does not affect the limiting NTKs.
This result generalizes the result in (Kanoh & Sugiyama 2022). which shows that the kernel induced by an oblivious tree, shown in Figure lJb), converges to the same kernel induced by non- oblivious one, as shown in Figure [a), in the limit of infinite trees.
4 CASE STUDY: DECISION LIST
As a typical example asymmetric trees, we consider a tree that grows in only one direction, shown in Figure 5] often called decision list (Rivest) 1987) and commonly used in practical applications (Letham et al.] (015). this architecture, one leaf exists at each depth, except for leaves at the final depth, where there are leaves.

---

Published as a conference paper at ICLR 2023
Figure 5: Decision list: binary tree that grows in only one direction.
Perfect binary
Decision list
2.5
2.5
Komel valus, D.2.0.-11
Mw64
M-14
M-256
M52
1.5
1224
1.5
M
0.5
0.5
-0.5
1.0
Inner product of the inputs
Tneer product of the inputs
Figure 6: An empirical demonstration for (Left) perfect binary tree and (Right) decision list ensem- bles on the convergence of ((.P)) (x,, (z,, and (5. (I:,, ..) as M increases. The kernel induced by finite trees is numerically calculated and plotted 10 times with parameter re-initialization.
and 6) (x; xzy) to the fixed limit (5,PB) (æ; z;)
4.1 NTK FOR DECISION LISTS
We show that the NTK induced by decision lists is formulated in closed-form as M - oo at initial- ization:
The NTK for an ensemble of soft decision lists with the depth D converges in prob- ability the following deterministic kernel as M
Proposition
OC.
(D.LL) (Is, x.j) = lim (D.LL) (I:; 23;)
M +00
(1. (,), + ( (2;; 2.)) ... 20 (D.Rul) (2x;; 22y)
D
= V (x,, xx) (x;
Σ
(d (aT (T (2,, x,)) D-1
contribution from internal nodles
+
((T (zi, (2i, + (T D.
(1I)
contribution from leaves
In Proposition "DL" stands for a "D'ecision "L"ist. The first equation comes from Theorem
We numerically demonstrate the convergence of the kernels for perfect binary trees and decision lists in Figure ( when the number and æ, [3))(3), si)))))))))))))))))))))))))))))) with [0, . The scaled error function used decision function.
trees gets larger. We use two simple inputs: æ; = {1.0)
The kernel induced by finite trees is numerically calculated 10 times with parameter re-initialization for each of M 16. 64, 256, 1024, and 4096. We empirically observe that the kernels induced by sufficiently many soft trees converge to the limiting kernel given in Equation 3 and Equation [T]] shown by the dotted lines in Figure 6 The kernel values induced by finite ensemble are already close to the limiting NTK if the number of trees is larger than several hundred, which is a typical order of the number of trees in practical applications (Popov et al., 2020). This indicates that our NTK analysis is also effective in practical applications with finite ensembles.
4.2 DEGENERACY
Next, we analyze the effect of the tree depth to the kernel values. is known that overly deep soft perfect binary trees induce the degeneracy phenomenon (Kanoh Sugiyama 2022), and
7

---

Published as a conference paper at ICLR 2023
Perfect binary tree
Decision
Nomalizd kemell valus, a=
1,00
1.00
Infiniie depth kmi
0.75
0.75
0.50
0.50
0.25
0.25
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
Inser the inputs
Inser product the inputs
10
15
Figure 7: Depth dependency of (Left) (DD.PB) (æi, mz) and (Right) @(D.DL) (xc;, ær)) For decision lists, the limit of infinite depth indicated by the dotted line.
analyzed whether or not this phenomenon also occurs in asymmetric trees like decision lists. Since < (a,, 22,) < 0.5, replacing the summation Equation 11 with an infinite series, we can obtain the closed-form formula when the depth D in the case of decision lists:
Proposition 2. The NTK for ensemble of soft decision lists with an infinite depth converges in probability the following deterministic kernel as M > oc,
lim (.D.L) (I), = 2 (2;, T (1 23)) D-000
T (x,, zg)
(12)
(1 - T ( x x)
1- T Dzz)
contribution From internal nodes
from
Thus the limiting NTK (D.DL) of decision lists neither degenerates nor diverges as + oc.
Figure 7 shows how the kernel changes as depth changes. In the case of the perfect binary tree, the kernel value sticks to zero as the inner product of the input gets farther from 1.0 (Kanoh & Sugiyama 2022 whereas in the decision list case, the kernel value does not stay zero. In other words, deep perfect binary trees cannot distinguish between vectors with 90-degree difference in angle and vectors with 180-degree difference in angle. Meanwhile, even if the decision list becomes infinitely deep, the kernel does not degenerate as shown by the dotted line in the right This implies that deterioration in generalization performance is likely to
panel of Figure occur even if the model gets infinitely deep. We can understand such behavior intuitively from the following reasoning. When the depth of the perfect binary tree is infinite, all splitting regions become infinitely small, meaning that every data point falls into a unique leaf. In contrast, when decision list is used, large splitting regions remain, so not all data are separated. This can avoid the phenomenon of separating data being equally distant.
4.3 NUMERICAL EXPERIMENTS
We experimentally examined the effects of the degeneracy phenomenon discussed in Section
Setup. We used 90 classification tasks in the UCI database (Dua & Graffi 2017) each of which has fewer than 5000 data points as in (Arora et al. 2020). We performed kemel regression us- the infinite ensemble ing the limiting NTK defined Equation and Equation IT] equivalent
of the perfect binary trees and decision lists. We used /) in (2, 4, 8, 16, 32, 64, 128} and in (1.0, 2.0, 4.0, 8.0, 16.0, 32.0). The scaled error function is used as a decision function. To consider the ridge-less situation, regularization strength is fixed to 1.0 10 8 We report four-fold cross- validation performance with random data splitting as in Arora et al. 2020 and Fernández-Delpeee Delgado al. (004)). Other details are provided in the Appendix.
Figure shows the averaged performance in classification accuracy on 90 datasets. The generalization performance decreases the tree depth increases when perfect binary trees used as weak learners. However, no significant deterioration occurs when decision lists are used as weak learners. This result is consistent with the degeneracy properties as discussed in Section 4.2
Performance.
8

---

Published as a conference paper at ICLR 2023
Averggal sccussy 10)
Avenged accuncy (am2.))
A Averged acouncy (om4A))
0.50
Dep
Poyt
Dayak
(r
Avarapal (om
Axerpu seuuncy
Dest
binary
depth
Figure 8: Averaged accuracy over 90 datasets. Horizontal dotted lines show the accuracy of decision lists with the infinite depth. The statistical significance is assessed in the Appendix.
The performance of decision lists already becomes almost consistent with their infinite depth limit when the depth reaches around 10. This suggests that we will no longer see significant changes in output for deeper decision lists. For small a, asymmetric trees often perform better than symmetric trees, but the characteristics reverse for large a.
Computational complexity of the kernel. Let U U= Edn @(d)> the number of depths con- nected to leaves. In general, the complexity for computing each kernel value for pair of samples is O(U). However, there are cases in which we can reduce the complexity to O(1), such as in the case of an infinitely deep decision list as shown in Proposition 2 although 0c.
DISCUSSIONS
Application to Neural Architecture Search (NAS). Arora et al. (2019) proposed using the NTK for Neural Architecture Search (NAS) (Elsken have been active in recent years (Chen et al. 2021 Xu el al. 2021 Mok et al.) 2022). Our findings
2019) for performance estimation. Such studies
allow us to reduce the number of tree architecture candidates significantly. Theorem 3 tells us the existence of redundant architectures that do not need to be explored in NAS. The numerical experiments shown in Figure Sgguressugggss that we not need to explore extremely deep tree structures even with asymmetric tree architecture.
Analogy between decision lists and residual networks. Huang et al. (2000) showed that al- though the multi-layer perceptron without skip-comeection (He et al. 2016 exhibits the degeneracy phenomenon, the multi-layer perceptron with skip-connection does not exhibit This is common to our situation, where skip-connection for the multi-layer perceptron corresponds to asymmetric structure for soft trees like decision lists. Moreover, Veit et al. (2016) proposed an interpretation of residual networks showing that they can be seen collection of many paths of differing lengths. This is similar to our case, because decision lists can be viewed as a collection of paths, i.e., rule sets, with different lengths. Therefore, our findings in this paper suggest that there may be common reason why performance does not deteriorate easily as the depth increases.
CONCLUSIONS
We have introduced and studied the NTK induced by arbitrary tree architectures. Our theoretical analysis via the kernel provides new insights into the behavior the infinite ensemble of soft trees: for different soft trees, if the number of leaves per depth is equal, the training behavior of their infi- nite ensembles in function space matches exactly, even the tree architectures are not isomorphic. We have also shown, theoretically and empirically, that the deepening of asymmetric trees like deci- sion lists does not necessarily induce the degeneracy phenomenon, although occurs in symmetric perfect binary trees.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work was supported by JSPS, KAKENHI Grant Number HO3503, Japan and JST, CREST Grant Number JPMJCR22D3,
ETHICS STATEMENT
We believe that theoretical analysis of the NTK does not lead to harmful applications.
REPRODUCIBILITY STATEMENT
Proofs are provided in the Appendix. For numerical experiments and figures, reproducible source codes shared in the supplementary material.
REFERENCES
Serean Ömer Arik and Tomas Pfister. TabNet: Attentive Interpretable Tabular Learning. CoRR, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang- On Exact Computation with an Infinitely Wide Neural Net. In Advances in Neural Information Processing Systems, 2019.
Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks. In International Con- ference Learning Representations, 2020.
Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research, 2003.
Leo Breiman. Random Forests. In Machine Learning, 2001.
Leo Breiman, Jerome Friedman, Charles J. Stone, and R.A. Olshen. Classification and Regression Trees. Chapman and Hall/CRC, 1984.
Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural Architecture Search on ImageNet in Four GPU Hours: Theoretically Inspired Perspective. In International Conference Learning Representations, 2021.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Program- ming. Advances in Neural Information Processing Systems, 2019.
Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017. TRUhtttp:/archive ics. uci, edu/ml
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural Architecture Search: A Survey. Journal of Machine Learning Research, 2019,
Manuel Femández-Delgadde Eva Cernadas, Senén Barro, and Dinani Amorim. Do we Need Hun- dreds of Classifiers to Solve Real World Classification Problems? Journal of Machine Learning Research, 2014.
Yoav Freund and Robert E. Schapire. Experiments with New Boosting Algorithm, In Proceedings of the 13th International Conference on Machine Learning, 1996.
Jerome H. Friedman and Bogdan E. Popescu. Predictive learning via rule ensembles. The Annals of Applied Statistics, 2008.
Nicholas Frosst and Geoffrey Hinton. Distilling a Neural Network Into a Soft Decision Tree. CoRR, 2017.
10

---

Published as a conference paper at ICLR 2023
Hussein Hazimeh, Natalia Ponomareva, Petros Mol, Zhenyu Tan, and Rahul Mazumder. The Tree Ensemble Layer: Differentiability meets Conditional Computation. In Proceedings of the 37th International Conference Machine Learning, 2020.
Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In IEEE Conference Compuler Vision and Paltern Recognition, 2016.
Kaixuan Huang, Yuqing Wang, Molei Tao, and Tuo Zhao. Why Do Deep Residual Networks Gen- eralize Better than Deep Feedforward Networks? - A Neural Tangent Kernel Perspective. In Advances in Neural Information Processing Systems, 2020.
Wayne Iba and Pat Langley. Induction One-Level Decision Trees. In Machine Learning Proceed- ings. Morgan Kaufmann, 1992.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems, 2018.
M.I. Jordan and R.A. Jacobs. Hierarchical mixtures of experts and the EM algorithm. Proceedings of International Conference Neural Networks, 1993.
Ryuichi Kanoh and Mahito Sugiyama. A Neural Tangent Kernel Perspective of Infinite Tree En- sembles. In International Conference on Learning Representations, 2022.
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. In Advances in Neural Information Processing Systems, 2017.
Guolin Ke, Zhenhui Xu, Jia Zhang, Jiang Bian, and Tie- Liu. DeepGBM: Deep Learning Framework Distilled by GBDT for Online Prediction Tasks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulò. Deep Neural Decision Forests. IEEE International Conference on Computer Vision, 2015.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve Linear Models Under Gradient Descent. In Advances in Neural Information Processing Systems, 2019.
Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. GShard: Scaling Giant Models with Condi- tional Computation and Automatic Sharding. In International Conference Learning Represen- tations, 2021.
Benjamin Letham, Cynthia Rudin, Tyler H. McCormick, and David Madigan. Interpretable classi- fiers using rules and Bayesian analysis: Building a better stroke prediction model. The Annals of Applied Statistics, 2015.
C. H. Bryan Liu, Benjamin Paul Chamberlain, Duncan A. Little, and Ángelo Cardoso. Generalising Random Forest Parameter Optimisation to Include Stability and Cost. In Machine Learning and Knowledge Discovery in Databases, 2017.
Andre Martins and Ramon Astudillo. From Softmax to Sparsemax: Sparse Model of Attention and Multi-Label Classification. In Proceedings of The 33rd International Conference on Machine Learning. 2016.
Jisoo Mok, Byunggook Na, Ji-Hoon Kim, Dongyoon Han, and Sungroh Yoon. Demystifying the Neural Tangent Kernel from a Practical Perspective: Can be trusted for Neural Architecture Search without training? In IEEE Conference on Computer Vision and Pattern Recognition, 2022.
Ben Peters, Vlad Niculae, and André F. T. Martins. Sparse serrencceto-Sequenee Models. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
11

---

Published as a conference paper at ICLR 2023
Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural Oblivious Decision Ensembles for Deep Learning on Tabular Data. In International Conference on Learning Representations, 2020.
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorohev, Anna Veronika Dorogush, and Andrey Gulin. CatBoost: unbiased boosting with categorical features. In Advances in Neural Information Processing Systems, 2018.
J. R. Quinlan. Induction of Decision Trees. Machine Learning, 1986.
Ronald I.. Rivest, Learning Decision Lists. Machine Language., 1987.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe V. Le, Geoffrey E. Hinton, and Jeff Dean. Outrageously Large Neural Networks: The Sparsely- Gated Mixture-of-Expert Layer. In International Conference Learning Representations, 2017.
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive Neural Trees. In Proceedings of the 36th International Conference on Machine Learning, 2019.
Andreas Veit, Michael Wilber, and Serge Belongie. Residual Networks Behave Like Ensembles of Relatively Shallow Networks. In Advances in Neural Information Processing Systems, 2016.
Alvin Wan, Lisa Dunlap, Daniel Ho, Jihan Yin, Scott Lee, Suzanne Petryk, Sarah Adel Bargal, and Joseph E. Gonzalez. NBDT: -eckkl-Backed Decision Tree. International Conference on Learming Representations, 2021.
Jingjing Xu, Liang Zhao, Junyang Lin, Rundong Gao, Xu Sun, and Hongxia Yang. KNAS: Green Neural Architecture Search. In Proceedings of the 38th International Conference Machine Learning. 2021.
A PROOFS
A.1 PROOF THEOREM 2
Theorem 2. The NTK for an ensemble of M soft rule sets with the depth D converges in probability the following deterministic kernel as M DC,
Rule) (x) = lim θ (ule)))
(xi, 22))
M-+00
D a(z,,,z) (1 (1.,
(T(),,
contribution from internal nodes
contribution from leaves
Proof. We consider the contribution from internal nodes ( and the contribution from leaves (D (.D.Rul,leaves) separately, such that
(D.Ru))) (x,, æ.y) = (D.Rule.ooos)) (x), xt) + DD, Rull.leew)))) (z))
(A.1)
As for internal nodes, we have
((D.ulle) (I;, w. π
( (1, (I,, Wm,-1, Tm)
(A.2)
Own,
VM
where we consider the derivative with respect to a node I, and wm,-t denotes the internal node parameter matrix except for the parameters of the node l. Since there are D possible locations for 4 we obtain
(ulle, (x., (F, D E(x,, az θ
(A.3)
where
Em
Rule) (I,, Wm: Tm) ((D.Rule) (x,, Wm, km)) m
=Em (w 1 1 (w v.,)) (u m. 20 jar (wo mm ) al (um Dar)) )o (. , m.
=T(
=T(2,
=(((2,
(A.4)
12

---

Published as a conference paper at ICLR 2023
is used. Here, the subscription "->" means that the expected value of the corresponding term will be.
Similarly, for leaves,
(Dll))) (2s, w. π
((D,Rlle) (xi, Wm,s Tmn)
(A.5)
0m
Tm,1 M m
resulting in
D Rule,eeaves) (z)
(T(x;; v.)))
(A.6)
Combining Equation
A.3 and Equation
A.6
we obtain Equation
A.2 PROOF OF THROREM 3
Theorem 3. Let : NU (0} be function that receives any depth and returns the number of leaves connected to internal nodes at the input depth. For any tree architecture, the NTK for an ensemble of soft trees converges in probability to the following deterministic kernel M - 00,
D
(AAbbirryyioo (ree) (xi, ( 2.)) = lim
6
( Tree) (x:; 2z2) = Σ ((d) (dd.Rule)
M000
d=1
Proof. We separate leaf and inner node contributions.
Contribution from Internal Nodes. For soft Boolean operation, the following equations hold:
Em (1 o (w (w 21) Tw +,))
Em
00.5
00.
a [o (w x; 2i) wn
Em [o m. nt ( æ;)]
(A.7)
0(1 - a oww 0(1 - o (T
E
Enn
a ay (w m 3t / (w m a3y)]
Owm,n
Öwm,
No (w T 2.) Bo (w m. Swm
Em
(A.8)
@wm.
Since each or ( (;) becomes 0.5, although the term 1-o(wTT m. w.) is used instead of a (n x:)) the rightward flow the tree, exactly the same limiting NTK can be obtained by treating a (w,,, 2;) as o 2;).
As for an inner node contribution, the derivative is obtained as
b (lrrbitrrrryTees (I,; W. T
ppm,e Wm)
Tm.t
Wwm.n
VM
Wwmnn
8=1
Tm, Em, wm )x (t))
(A.9)
VM
E=1
where
Su,e(x, Wm) =
II nn==l
(w) (D;) (/ (1 a (x)) tco Aoteentesn (-1jtnne,
(A.10)
13

---

Published as a conference paper at ICLR 2023
and & is logical conjunction. Since Tm, is initialized as zero-mean i.id. Gaussians with unit variances,
Em [mm = 0 if o
(A.11)
Therefore, the inner node contribution for the limiting NTK is
( mrees giAniiraryTree.auuee) (I.,, 27,))
c
Em
"m Sn, um Snn (1.j, um )m] æz (w Ri) ā (w (w
= E(x,, ( (2 xz 1m
Σ Sn,e(x; wm wm) Sn, (2, wm)
(A.12)
Suppose leaf is connected to an internal node of depth d. With Equation A.7 and Equation A.8 obtain
Em ((,,, wm) (m,)), Wm)l = (T x2)
(A.13)
Therefore, considering all leaves,
glAbbinaryyTsssodddsll [1,, (x,; (d) (dRuul,noddss
(A.14)
where (d. (ddeel is introduced Equation A.3
Contribution from Leaves. As for the contribution from leaves, the derivative is obtained as
2 (ArbiirrryTiee)) (æi, W, π
VM Mm,,e ( Wm).
(A.15)
Since wm.n used em,e wm) initialized as zero-mean i.i.d. Gaussians, contribution from leaves on the limiting NTK induced by arbitrary tree architecture is:
+ AArbitary/Tec..ewee
[z TT) Em
um, Wm (mm))m..ea Wm)
D
Σ
Q(d) Rule.leves)
(A.16)
d=1
where (d. is introduced in Equation A.6
A.3 PROOF OF THEOREM 4
Theorem 4. Let Amin and Amax be the minimum and maximum eigenvalues of the limiting NTK. Assume |0,||2= for all E [N] and x; + 22 (i + j). For ensembles of arbitrary soft trees with the NTK initialization trained under gradient flow with a learning rate 2/ (Xmia >max) and positive finite scaling factor we have, with high probability.
sup θ (Areitrayyroe)) (x,,
@ (ArbitraryTres Tree)
(xi, 2x, 0
(A.17)
VM
Proof. To prove that the kernel does not move during training, we need to show the positive def- initeness of the kernel and the local Lipschitzness of the model Jacobian at initialization J ( 0), whose (i.j) entry is 0f(a.0) where 0j is j-th component of 0:
00,
Lemma Lee et al. (019)). Assume that the limiting NTK induced by any model architecture is
positive definite for input sets æ, such that minimum eigenvalue of the NTK Amin O. For models with local Lipschitz Jacobian trained under gradient flow with learning rate l < 2(Amin + Amax), we have with high probability:
sup θ (I,, (I,, - G (2.; =
(A.18)
VM
14

---

Published as a conference paper at ICLR 2023
The local Lipschitzness of the soft tree ensemble's Jacobian initialization is already proven, with arbitrary tree architectures:
Lemma Kanoh & Sugiyama (2022)). For soft tree ensemble models with the NTK initialization and positive finite factor the following holds:
factor there is K > such thatfor every C > O, with high probability,
{
0)) ((z 0)le
$ K
K| 0||2 v0, 0 E B ( C)
(A.19)
where
B (0,, 0) = (0: 10 -0-000 0012 <C}.
(A.20)
As for the positive definiteness, ( (x, x,) is known to be positive definite.
Lemma (Kanoh & Sugiyama (2022), For infinitely many perfect binary soft trees with any depth and the NTK initialization, the limiting NTK is positive definite if ||æ:||2= for all [N] and 2; + ④ (1+)) j).
Since (B) (ai, positive definite under the same assumption. Besides, since ((ArbitrayyTre))) (xr, 2X,) represented by the summation of ( ((D,) (z,, (.)) as in Theorem (ArbitrayyTien (x;, Dyy is also positive definite under the same assumption.
2. (xx;
is equivalent to (DD.ulle) (x;, myy) up to constant multiple, (D. (D,,ule) (æ., 2zy) is
These results show that the limiting NTK induced by arbitrary tree architecture also does not change during training.
B DETAILS OF NUMERICAL EXPERIMENTS
B. DATASET ACQUISITION
We used the UCI datasets (Dua & Graff 2017 preprocessed by Feráández-Delgadoo al. 2014 We selected 90 datasets with less than 5000 data points as Arora et al. (2020) and Kanoh & Sugiyama 2022).
B.2 MODEL SPECIFICATIONS
We used scikit-leam to perform kernel regression. The regularization strength is set be tiny value (1.0 x 10-*) so that it becomes almost ridge-less regression.
B.3 COMPUTATIONAL RESOURCE
We ran all experiments on 2.20 GHz Intel Xeon E5-2698 CPU and 252 GB of memory with Ubuntu Linux (version: 4.15.0-1 17-generic).
B.4 STATISTICAL SIGNIFICANCE
We conducted Wilcoxon signed rank test for 90 datasets to check the statistical significance of the differences between performances on a perfect binary tree and a decision list. Figure shows the p-values. Statistically significant differences large in Fi such as when a is small and is large. We used Bonferroni correction to account for multiple testing, and the resulting significance level of the p-value is about 0.0012 for percent confidence level. An asterisk ugp is placed in Figure A.I with statistically significant result even
be observed for areas where the differences appear
.ar..tar.g ridge. Kew.e www.eeeeeidde....mm htm] html
kernel
15

---

Published as a conference paper at ICLR 2023
0.1119
E:42702
0.54931
0
3-21221
2.15009
031312
0.25945
0 1.9940
0:00340
8-
5:0000
01390012
0.04443
E.006]
0.99554
0 6C651
1,00006
0.33339
0 6C4C3
640231
0,50267
18
4.0
5.0
16.3
32.0
Figure A.1: P-values of the Wilcoxon signed rank test for results on perfect binary trees and decision lists with different parameters.
D=
Dw4.a=20
Dw6.aw6.0
0.5
83
81
02
02
05
05
18
03
05
05
11
03
84
0/5
Acceacy (Podid bod
Asarao (Pertan Bear bo0)
Acnuny (Potice ind
Dad,
Dm
9.6
90
Figure A.2: Performance comparisons between the kernel regression with the limiting NTK induced by the perfect binary tree and the decision list on the UCI datasets with D 4.
De
22
Do 128..mmi..
Socuunn Diggkto BC
40
AextscydPooott bost
Astoncy inod
De 128 am00
Di 16660
ar 120
(Docaa caccaaaaaeee
96
85
1.0
8.4
05
1.
Ascuaayy Cod)
Ascataa (Partac Meary T000
Assutay (Potecclaa Redl
Figure A.3: Performance comparisons between the kernel regression with the limiting NTK induced by the perfect binary tree and the decision list on the UCI datasets with D 128.
16

---

Published as a conference paper at ICLR 2023
Stape
4.5
11
Figure A.4: Output dynamics for test data points. Each line color corresponds each data point. Analytical trajectories are the same for both shapes A and B.
Ell. 4p2::
t: 000 xbareee 18.m0 4p22
000
1: Col. 06
1r 8000
1r
1r ndwadd 05 Jayk
Ir 800), Kchampi
5200
0.075
0.799
0,125
Arciaged
Figure A.5: Averaged gradient boosting decision tree accuracy over 90 datasets. The random seeds are changed five times and their averaged performance is shown. Their maximum and minimum performance is shown by the error bars. The vertical dotted line shows the performance of the infinitely deep decision list with 4.0.
after correction. For cases where the symmetry of the tree does not produce large difference, such as at the depth of 2, the difference in performance is often not statistically significant.
Figures A.2 and A.3 show scatter-plots between the performance of the kernel regression with the limiting NTK induced by the perfect binary tree and the decision list. The deeper the tree, the larger the difference between them.
C ADDITIONAL NUMERICAL EXPERIMENTS
C.1 COMPARISON TO THE ENSEMBLES OF FINITE SOFT TREES
Figure A.4 iillustrates output trajectories for two different tree architectures shown in 3 gradient descent training with analytical trajectories obtained from the limiting kernel: f(u, 0,) H (v. x) H (x, x -1 exp[-n (x, x)r])y (Lee al. 2019), where v E RR is arbitrary input and x E RF FxN and y R N are the training dataset and targets, respectively. The setup is the same with Figure 4 Since the limiting kernel is the same for both architectures, analytical trajectories are the same for both left and right panels. As the number of trees increases, we can see that the behavior of finite trees approaches the analytical trajectory obtained by the NTK.
17

---

Published as a conference paper at ICLR 2023
C.2 COMPARISON TO THE GRADIENT BOOSTING DECISION TREE
For reference information, we show experimental results for the gradient boosting decision tree. The experimental procedure is the implementation. As for hyperparameters, we used max_depth in {2, 6), subsampl e in {0.6, 0.8, 1.0]. learning rate in {0.1, 0.01, 0.001}, and n_ esstimators (the number of trees) in {100, 300, 5003. Other parameters were set to be default values of the library.
that in Section 4.3 We used scikit-learr for the
Figure A.5 shows the averaged accuracy over 90 datasets. We used five random seeds {0, 1,,,, 4] and their mean, minimum, and maximum performances are reported. When we use the best param- eter, its averaged accuracy is 0.8010, which is slightly better than the performance of infinitely deep decision list: 0. 7889 with 4.0 as shown in the dotted line in Figure A.5 When we look at each dataset, however, the infinitely deep decision list is superior to the gradient boosting decision tree for 35 out of 90 datasets. One is not necessarily better than the other, and their inductive biases may or may not be appropriate for each dataset.
iordiieennt html
18


Reviews:
[{"review_id": "rAP54Bjx8H_", "reviewer": "Reviewer_AJRY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "While existing work (Kanoh & Sugiyama, 2022) has introduced NTK to analyze the ensemble behavior of an infinite number of soft trees, such a study has mainly targeted the perfect binary tree, leaving the theoretical understanding of other types of widely used soft trees (e.g., decision list, rule set) unknown yet. To this end, this paper follows this line of work to provide theoretical analyses for other types of widely used soft trees via NTK and provides many interesting insights.", "summary_of_the_review": "Overall, I am quite interested in this work and excited to see that NTK has inspired the theoretical analysis in other fields, e.g., the soft tree ensembles studied in this paper. However, as I am not professional in this area, currently I can only deliver a score of 6 for this work with small confidence. But I believe that this paper is already of good quality.", "strength_and_weaknesses": "Strengths:\n1. This paper extends the theoretical study of (Kanoh & Sugiyama, 2022) on the perfect binary trees to many other types of soft trees in the literature, which is important to provide a more practical theoretical understanding in this field.\n2. The theoretical results and insights of this paper are quite interesting and usually have been validated using empirical experiments. These results also provide certain implications for the application of these tree ensembles, which can be helpful in practice.\n3. The whole paper is well-written and easy to follow.\n\nweaknesses:\n1. If I understand correctly, the theoretical analysis of this paper is based on the ensemble of the same type of soft trees with the same depth. So, will the theoretical results in this paper be also applicable to the ensemble of the different types of soft trees with various depths (even only empirical verification will be enough)? Because such an ensemble seems to be common in practice.\n2. More interpretation for theorem 3 (e.g., how \"theorem 3 tells us that the limiting NTK depends on only the number of leaves at each depth with respect to tree architecture\" specifically) can make the importance of theorem 3 clearer as theorem 3 is the first and also the most fundamental contribution of this paper.\n3. For the interpretation of Figure 3, it's unclear why NTK can be connected with the training behavior and generalization performance of tree ensembles. Any theoretical support for this, like the ones in (Jacot et al., 2018) and [1,2], but with respect to the soft tree ensemble models? I think more explanations need to be provided here since it's an important insight drawn from theorem 3, which also serves as the second contribution shown in the introduction. \n4. Mentioning \"ensemble\" in the caption of figure 3 can make this result easier to be understood. There are many lines (w/ different colors) without labels in figures 4 and 6. I hope the authors can further polish these results to make them more readable.\n\n[1] Arora, Sanjeev, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. 2019. “Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks.”\n[2] Cao, Yuan, and Quanquan Gu. 2019. “Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks.”", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "kvOg8bkt-B", "reviewer": "Reviewer_gydX", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studies the TNTK, i.e., neural tangent kernel induced by soft tree ensembles. The authors first provide a closed-form expression of the TNTK with arbitrary architecture. This is a generalization of the previous work (Kanoh and Sugiyama, 2022), which only studies the perfect binary tree. The underlying idea is to decompose a tree structure to rule sets, and to utilize their superposition property. Hence, the TNTK is the weighted summation of that of each rule set. This also implies that only the number of leaves at each depth affects the TNTK. Hence, different tree structures can have identical training behaviors and generalization performance under the infinite ensemble limit. Second, they deeply analyze a corner case, i.e., a tree growing in only one direction called a decision list. In particular, the TNTK of the decision tree does not degenerate while that of the perfect binary tree does. Such non-degeneracy property makes the performance of the TNTK not decrease when the depth becomes large. Experimental results also well support their result. \n", "summary_of_the_review": "This paper well generalizes the previous results on the perfect binary tree, but the novelty is weak, and more concrete justification on the TNTK would be needed.", "strength_and_weaknesses": "Strength:\n\nThis paper generalizes the previous result on the perfect binary tree to the arbitrary ones. This result gives us that only the number of leaves at each depth affects the TNTK. As the authors suggested, this is useful for the neural architect search (NAS) where the candidate models are infinite ensemble of soft trees. \n\n\nWeakness:\n\nAlthough the results of this paper are concrete, a justification of the TNTK is weak and it is still unclear which tasks/applications require the TNTK. The contribution would be much stronger if it shows some practical applications, e.g., Neural Architecture Search (NAS).\n\nA performance gap between the perfect binary tree and the decision list comes from the depth degeneracy. The authors give a simple intuition on the behavior of region split, but this intuition is not sufficient to explain the performance gap. It would be better if more rigorous reasoning is provided.\n\nThe performance of the TNTK in section 4.3 depends on the choice of scaling factor ``alpha’’. Does this alpha control degeneracy of the TNTK? If so, it would be great to compare the degeneracy to practical performance (with different choices of alpha). And it would be better to compare the TNTK with other (sigmoid-like) activations.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dV4U8aioD2J", "reviewer": "Reviewer_ck6w", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper deals with ensemble learning where the weak learners are soft trees. More precisely, it aims to study from a theoretical perspective soft tree ensembles when the number of weak learners goes to infinity. To this end, the authors investigate the NTK (Neural Tangent Kernel) induced by them and prove several non-trivial results, which seems to me of great interest, without any assumption on the topology of the soft trees. They are in addition validated from numerical experiments. The paper is an extension of an article published in ICLR 2022 by Kanoh and Sugiyama hereafter referred to as [Kanoh and Sugiyama, 2022].", "summary_of_the_review": "My opinion on this paper is very positive: it is well written and organized, improves recent results, and the theoretical and numerical results are non-trivial and in agreement with each other.", "strength_and_weaknesses": "This paper extends in a non-trivial way the understanding of infinite soft tree ensembles that was previously limited to binary trees. In particular, it is shown that the tree topology has an effect only through the number of leaves at each depth. The conclusion on the degeneracy effect observed for binary trees but not for decision list is also highly informative. Finally, the numerical results support the theoretical findings.\n\nI have the two following questions only:\n- If I understood correctly, all the soft trees in Theorem 3 share the same topology. Would it not be relevant to study the case where not all trees have the same topology? I think this could encompass some interesting practical cases.\n- Theorem 3 generalizes Theorem 1 of [Kanoh and Sugiyama, 2022] established for binary trees to any tree architecture. The idea of the proof is to see trees as combinations of independent rule sets, which is quite different from the proof developed in [Kanoh and Sugiyama, 2022]. Can the authors comment on the differences between the two proofs, both their advantages and drawbacks?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "0J8RnES-mI", "reviewer": "Reviewer_RPPM", "summary": "", "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": "", "summary_of_the_paper": "The paper analyses tree architectures for neural trees ensembles via NTK. Authors provide important insights on how the structure of trees affects NTK and consider depth limit of NTK. Experimental results are based on kernel regression with arising NTK.", "summary_of_the_review": "Theoretical results are novel for literature but the novelty is limited by the fact that results slightly extend analysis of R Kanoh et al (ICLR 2022). Paper has rigorous theoretical analysis but lacks more detailed experimentations. Nevertheless, results are interesting and worth presenting as provide interesting insight on the kernel structure.", "strength_and_weaknesses": "Strength:\n-- rigorous theoretical analysis\n-- comparison of different architectures\n-- discussion of connection with residual networks\n\nWeaknesses:\n-- experimental validation is mostly absent, since authors claim that kernel is non degenerate seeing how stochastic gradient optimization is able to overfit on arbitrary function and it's generalisation gaps (especially compared to classical gradient boosting) are desired to support theoretical claims in the situation of limited novelty.\n-- experiments that are present are done on top of Kernel Regression with kernel defined by NTK, it is interesting to see how stochastic gradient descent results are aligned with Kernel Regression results as in practical setting applications of Kernel Regression is limited due to necessity to invert kernel matrix.\n-- No link with classical gradient boosting", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster