A Neural Tangent Kernel Perspective of Infinite Tree Ensembles
Authors: Ryuichi Kanoh
Mahito Sugiyama
Venue: ICLR 2022 Poster (2022)
Keywords: Neural Tangent Kernel
Tree Ensemble
Soft Tree

Abstract: In practical situations, the tree ensemble is one of the most popular models along with neural networks. A soft tree is a variant of a decision tree. Instead of using a greedy method for searching splitting rules, the soft tree is trained using a gradient method in which the entire splitting operation is formulated in a differentiable form. Although ensembles of such soft trees have been used increasingly in recent years, little theoretical work has been done to understand their behavior. By considering an ensemble of infinite soft trees, this paper introduces and studies the Tree Neural Tangent Kernel (TNTK), which provides new insights into the behavior of the infinite ensemble of soft trees. Using the TNTK, we theoretically identify several non-trivial properties, such as global convergence of the training, the equivalence of the oblivious tree structure, and the degeneracy of the TNTK induced by the deepening of the trees.

Published as a conference paper at ICLR 2022
A NEURAL TANGENT KERNEL PERSPECTIVE OF INFINITE TREE ENSEMBLES
Ryuichi Kanoh Mahito Sugiyama 1.2 National Institute of Informatics The Graduate University for Advanced Studies, SOKENDAL (kanoh, mahito) @nii.ac. jp
ABSTRACT
In practical situations, the tree ensemble is one of the most popular models along with neural networks. A soft tree is variant of decision tree. Instead of using greedy method for searching splitting rules, the soft tree is trained using a gradient method in which the entire splitting operation is formulated in differentiable form. Although ensembles of such soft trees have been used increasingly in recent years, little theoretical work has been done to understand their behavior. By considering an ensemble of infinite soft trees, this paper introduces and studies the Tree Neural Tangent Kernel (TNTK), which provides new insights into the behavior of the infinite ensemble of soft trees. Using the TNTK, we theoretically identify several non-trivial properties, such as global convergence of the training, the equivalence of the oblivious tree structure, and the degeneracy of the TNTK induced by the deepening of the trees.
INTRODUCTION
Tree ensembles and neural networks are powerful machine learning models that are used in various real-world applications. A soft tree ensemble is one variant of tree ensemble models that inherits characteristics of neural networks. Instead of using greedy method (Quinlan 1986 Breiman et al.) 1984) to search splitting rules, the soft tree makes the splitting rules soft and updates the entire model's parameters simultaneously using the gradient method. Soft tree ensemble models are known have high empirical performance (Kontschieder et al. 2015 Popov et al.) [020)] Hazimeh et al., 2020).
especially for tabular datasets. Apart from accuracy, there are many reasons why one should formulate trees in a soft manner. For example, unlike hard decision trees, soft tree models can be updated sequentially (Ke et al., 2019) and trained in combination with pre-training (Arik & Pfister 2209)). resulting in characteristics that are favorable in terms of real-world continuous service deployment. Their model interpretability, induced by the hierarchical splitting structure, has also attracted much attention (Frosst & Hinton| 2017; Wan et al. 1021 Tanno et al. 2019). In addition, the idea of the soft tree is implicitly used in many different places; for example, the process of allocating data to the appropriate leaves Shazeer et al.) 2017) Lepikhin et al. 2021). a technique for balancing computational complexity and prediction performance.
be interpreted as special of Mixture-of-Expert (Jordan & Jacobs 1993
Although various techniques have been proposed to train trees, the theoretical validity of such techniques is not well understood sufficient depth. Examples of the practical technique include constraints on individual trees using parameter sharing (Popov et al. 2020), adjusting the hardness of the splitting operation (Frosst & Hinton| 2017 Hazzmeh et 2020). and the use of overparame- terization (Belkin et al. [2019] Karthikeyan et al. (021)) To better understand the training of tree ensemble models, we focus on the Neural Tangent Kernel (NTK) (Jacot al. 2018), a powerful tool that has been successfully applied to various neural network models with infinite hidden layer nodes. Every model architecture is known to produce a distinct NTK. Not only for the multi-layer perceptron (MLP), many studies have been conducted across various models, such as for Convolutional Neural Networks (CNTK) (Arora et al. 2019 Li et al. 2019), Graph Neural Networks (GNTK) (Du et al. 2019b), and Recurrent Neural Networks (RNTK) (Alemohammad al. (021). Although number of findings have been obtained using the NTK, they are mainly for typical neural networks, and is still not clear how apply the NTK theory to the tree models.

---

Published as a conference paper at ICLR 2022
M1
Juln, w.t.w..... vu)
f(, 1, x)
V. Σ
Smite Wm, Tes))
Figure 1: Schematics of an ensemble of M soft trees. Tree internal nodes indexed according to the breadth-first ordering.
In this paper, by considering the limit of infinitely many trees, we introduce and study the neural langent kernel for tree ensembles, called the Tree Neural Tangent Kernel (TNTK), which provides new insights into the behavior of the ensemble of soft trees. The goal of this research is to derive the kernel that characterizes the training behavior of soft tree ensembles, and to obtain theoretical support for the empirical techniques. Our contributions are summarized as follows:
First extension of the NTK concept to the tree ensemble models. We derive the analytical form for the TNTK at initialization induced by infinitely many perfect binary trees with arbitrary depth (Section I.T. We also prove that the TNTK remains constant during the training of infinite soft trees, which allows to analyze the behavior by kernel regression and discuss global convergence
training using the positive definiteness of the TNTK (Section 4.1.2 4.1.3).
Equivalence of the oblivious tree ensemble models. We show the TNTK induced by the oblivious tree structure used in practical open-source libraries such CatBoost (Prokhorenkova al. (018) and NODE (Popov et al. 2020) converges to the same TNTK induced by a non-oblivious one in the limit of infinite trees. This observation implicitly supports the good empirical performance of oblivious trees with parameter sharing between tree nodes (Section 1.2.1I)
Nonlincarity by adjusting the tree splitting operation. Practically, various functions have been proposed to represent the tree splitting operation. The most basic function is sigmoid. We show that the TNTK is almost linear kernel in the basic case, and when we adjust the splitting function hard, the TNTK becomes nonlinear (Section 4.2.2)
Degeneracy of the TNTK with deep trees. The TNTK associated with deep trees exhibits degeneracy: the TNTK values are almost identical for deep trees even if the inner products of inputs are different. As result, poor performance in numerical experiments is observed with the TNTK induced by infinitely many deep trees. This result supports the fact that the depth of trees is usually not large in practical situations (Section 4.2.3).
Comparison to the NTK induced by the MLP. We investigate the generalization performance of infinite tree ensembles by kernel regression with the TNTK on 90 real-world datasets. Although the MLP with infinite width has better prediction accuracy average, the infinite tree ensemble performs better than the infinite width MLP in more than 30 percent of the datasets. We also showed that the TNTK superior to the MLP-induced NTK in computational speed (Section 5).
BACKGROUND AND RELATED WORK
Our main focus in this paper is the soft tree and the neural tangent kernel. We briefly introduce and review them.
2.1 SOFT TREE
Based on Kontschieder et al. (2015), we formulate a regression by soft trees. Figure D is a schematic image of ensemble of M soft trees. We define data matrix E FxN for N training samples
2

---

Published as a conference paper at ICLR 2022
{Ei,. ØN with F features and define tree-wise parameter matrices for internal nodes wm R PPW and leaf nodes Tm E x for each tree m E [M] = {1,..., M as
Wm.NN ) 7m = (Tm, Tm, c),
21
NN
Wm =
Wm,1
where internal nodes (blue nodes in Figure T and leaf nodes (green nodes Figure I are indexed from 1 to N and 1 to L, respectively. .N and L may change across trees in general, while assume that they are always fixed for simplicity throughout the paper. We also write horizontal concatenation of (column) vectors
x (#1,.... .v,) E IR and Wmm [w0m1 Wm.NN .N) R
Unlike hard decision trees, we consider a model in which every single leaf node /' of a tree holds the probability that data will reach it. Therefore, the splitting operation at an intermediate node n E [M] = [1, does not definitively decide splitting to the left or right. To provide an explicit form of the probabilistic tree splitting operation, we introduce the following binary relations that depend on the tree's structure: l / (resp. n > f), which is true if leaf belongs to the left (resp. right) subtree of a node n and false otherwise. We can now exploit em,e (2),, Wm) R x IR FxX + [0, 1]. function that returns the probability that sample æ; will reach a leaf& & of the tree m, as follows:
(1...,
(mi, Wm) II Im.n (Iii Wm,n) Aeco
(1 Beco 9m, m (ar W.m,n) tasse
where I is an indicator function conditioned on the argument Q. i.e., 1 = and latse = 0, and Im.n : R x R [0, is a decision function at each internal node n of a tree m. To approximate decision tree splitting, the output of the decision function Im.n should be between 0.0 and 1.0. If the output of a decision function takes only 0.0 or 1.0, the splitting operation is equivalent to hard splitting used in typical decision trees. We will define explicit form of the decision function Jm.n in Equation
5 in the next section.
The prediction for each æ; from tree with nodes parameterized by w. and nm is given by
fm( Wm, Tm) mmm eL Wm))
where fm : IRF, X FFN, x Rixc - R, and Tm, denotes the response of a leaf é of the tree m. This formulation means that the prediction output is the average of the leaf values um, weighted by (m, Wm... probability of assigning the sample æ; the leaf l. If e wm) takes only 1.0 for one leaf and 0.0 for the other leaves, the behavior is equivalent to a typical decision tree prediction. In this model, Wm. and n. are updated during training with a gradient method.
(a,,
While many empirical successes have been reported, theoretical analysis for soft tree ensemble models has not been sufficiently developed.
2.2 NEURAL TANGENT KERNEL
Given N samples E IR FxN, the NTK induced by any model architecture at a training time is formulated matrix H; NNN in which each (i.j) E [N] [N] component is defined as
I = (; = ① Sustiiraayy (I,, 0z) futbitary (x.,. 0-)
(3)
00,
a0
where ( denotes the inner product and 0, E R is concatenated vector of all the P trainable model parameters т. An asterisk tion Sathirray R R + I used in Equation (3) is expected to be applicable to variety of model structures. For soft tree ensembles introduced Section 2.1 the NTK formulated as 2n=1
indicates that the model is arbitrary. The model func-
.M - (..T) af(=,,w.))) Jwm.n
+ .M
2mm Σf_ /af(m..w.. of(,,w,.)
Dwm.n
OKm.t
Within the limit infinite width with a proper parameter scaling, a variety properties have been discovered from the NTK induced by the MLP. For example, Jacot et al. (018)) showed the Jacot
convergence of MLP (æ;; Ry), which can vary with respect parameters, to the unique limiting
3

---

Published as a conference paper at ICLR 2022
kernel MT.. (z,, xy) initialization in probability. Moreover, they also showed that the limiting
kernel does not change during training in probability:
lim width
@ (zi, (t) width
lim
G (2i, 2;) Q MLP (0o 21))
This property helps in the analytical understanding of the model behavior. For example, with the squared loss and infinitesimal step size with learning rate 7), the training dynamics of gradient flow in function space coincides with kernel ridge-less regression with the limiting NTK. Such a property gives data-depent dettadddeeddenttt generalization bound (Bartlett & Mendelson 2003) related to the NTK and the prediction targets. In addition, if the NTK is positive definite, the training can achieve global convergence (Du al. 2019a Jacot et al. 2018).
Although a number of findings have been obtained using the NTK, they are mainly for typical neural networks such MLP and ResNet (He et al., a (016)) and the NTK theory has not yet been applied to tree models. The NTK theory is often used in the context of overparameterization which is subject of interest not only for the neural networks, but also for the tree models (Belkin al. 2019
Karthikeyan et al. 2021
Tang et al. 2018).
3 SETUP
We train model parameters and π to minimize the squared loss using the gradient method, where = (w...... W.r and π (T....., M). The tree structure is fixed during training. In order to use a known closed-form solution of the NTK (Williams) 1996 Lee et al. 2019), we use a scaled error function ø R (0, 1), resulting in the following decision function:
0.8-
0.5
(a, wm,n) (w (wm,.z.)
= erf (aw (aw,n ..) +
(5)
-2
2
2'
where er((p) 3 10 e-² de for p E TR. This scaled error function approximates a commonly used sigmoid function. Since the bias term for the input of can be expressed inside of w by adding an element that takes a fixed constant value for all input of the soft trees æ, do not consider the bias for simplicity. The scaling factor is introduced by FFosst Hinton| (2017) to avoid overly soft splitting. Figure shows that the decision function becomes harder as a increases (from blue to red), and in the limit -> oo it coincides with the hard splitting used in typical decision trees.
Figure 2: The scaled error function. We draw 50 lines with varying a by 0.25, dotted magenta line shows sigmoid function, which is close to scaled error function with 0.5.
When aggregating the output of multiple trees, we divide the sum of the tree outputs by the square root of the number of trees
M
f (x: W. π
fm Wm, Tm).
(6)
This 1/v / scaling is known to be essential in the existing NTK literature to use the weak law of the large numbers (Jacot et al. 2018). On top of Equation (6). we initialize each of model parameters Wm. and Tm. with zero-mest mero-mman i.idd Gaussians with unit variances. We refer such parameterization as NTK initialization. In this paper, we consider a model such that all M trees have the same perfect binary tree structure, common setting for soft tree ensembles (Popov et al. 2020 Kontschieder et al. 2015 Hazimeh et al., 2020).
THEORETICAL RESULTS
4.1 BASIC PROPERTIES OF THE TNTK
The NTK in Equation 3 induced by the soft tree ensembles is referred to here as the TNTK and denoted by @)d)) (æ,, my) the TNTK initialization induced by the ensemble of trees with depth d.
4

---

Published as a conference paper at ICLR 2022
de% 2,0
Change wniih froed di
Change of with ficed om
14
10
1.5
1.0
6.5
Figure Left: An empirical demonstration of convergence of (00(2,,000 22) ) the fixed limit ((x; 2y) as M increases. Two simple inputs are considered: æ; = {1.0) and æj {cos(3), sin( with 3 = [0, T.. The TNTK (1;; (xx; æ;)) with a = 2.0 is calculated re-initialization for each of the M = 16, 64, 256, 1024, and 4096. Center and Right: Parameter dependency of the convergence. The vertical axis corresponds to the averaged error between the Hu and the H == limm-+e -
times with parameter
Hp for 50 random unit vectors of length F = 5. The dashed lines are plotted only for showing the slope. The error bars show the standard deviations of 10 executions.
In this section, we show the properties of the TNTK that are important for understanding the training behavior of the soft tree ensembles.
4.1.1 TNTK FOR INFINITE TREE ENSEMBLES
First, show the formula of the TNTK initialization, which converges when considering the limit of infinite trees (M + CO).
Let u E F be any columa vector sampled from zero-mean i..dd Gaussians with unit variance. The TNTK for ensemble of soft perfect binary trees with tree depth d converges in probability to the following deterministic kernel as M - 0c.
Theorem 1.
( 2,) = lim @ (x),
M
2dd (E, v2 (T 1 x2,) (2T 2,,)
contribution from inner nodes
contribution from leaves
where E(xi, x. æj ((w; = Elo(u x: w æz)). and T( az))
(lō(uT ((z)uT))) [)))) Moreover, T T(x,; mz) and I T(x;, 2.)) are analytically obtained the closed- form as
a² a²5(xs, m.)) Vaa 23i) +
T( x,) = aresin
+
(8)
2n
+ 0.5)
a²
xx);
π / (1 22 I1, xz)) 2a>> 2,)) 4a + x ((,, x,)2
The dot used in ouu" x;) means the first derivative: ae (ou" mx) /V and [B|] means the expecta- tion. The scalar ı in Equation (8) and Equation ( is the circular constant, and u corresponds to Wm.n at an arbitrary internal node. The proof is given by induction. We can derive the formula of the limiting TNTK by treating the number of trees in MLP, although the MLP and the soft tree ensemble are apparently different models. Due to space limitations, detailed proofs are given the supplementary material.
ensemble like the width of the hidden layer
We demonstrate convergence of the TNTK in Figure 3 We empirically observe that the TNTK induced by sufficiently many soft trees converges to the limiting TNTK given in Equation 77. The kernel values induced by finite ensemble are already close to the limiting TNTK if the number of trees is larger than several hundreds, which is a typical order of the number of trees in practical applications Therefore, it is reasonable to analyze soft tree ensembles via the TNTK.
For example, Popov al. 2020 uses 2048 trees.
5

---

Published as a conference paper at ICLR 2022
By comparing Equation and the limiting NTK induced by two-layer perceptron (shown in the supplementary material), we can immediately derive the following when the tree depth is 1.
Corollary 1. If the splitring function at the tree internal node is the same the activation function of the neural network, the limiting TNTK obtained from a soft tree ensemble of depth is equivalent the limiting NTK generated by two-layer perceptron up constant multiple.
For any tree depth larger than 1, the limiting NTK induced by the MLP with any number of layers (Arora et al., 2019] shown the supplementary material) and the limiting TNTK do not match. This implies that the hierarchical splitting structure is a distinctive feature of soft tree ensembles.
4.1.2 POSITIVE DEFINITENESS OF THE LIMITING TNTK
Since the loss surface of a large model expected to be highly non-convex, understanding the good empirical trainability of overparameterized models remains an open problem (Dauphin et al. 2014). The positive definiteness of the limiting kernel is one of the most important conditions for achieving global convergence (Du
2019a Jacot | 1 for all E [ and 2; æj (i 7 are necessary for the positive definiteness of the NTK induced by the MLP for an input set. As for the TNTK, since the formulation (Equation is different from that of typical neural networks such as an MLP, it is not clear whether or not the limiting TNTK is positive definite.
2018). Jacot al.) (2018) showed that the conditions
We prove that the TNTK induced by infinite trees is also positive definite under the same condition for the MLP.
Proposition 1. For infinitely many soft trees with any depth and the NTK initialization, the limiting TNTK is positive definite if ||x,|l2= for all E [N] and x; # I3 (i ().
The proof is provided in the supplementary material. Similar to the discussion for the MLP (Du et al. 2019a; Jacot et al. 2018), the limiting TNTK constant during training, the positive definiteness of the limiting TNTK initialization indicates that training of the infinite trees with a gradient method can converge to the global minimum. The constantness of the limiting TNTK during training is shown in the following section.
4.1.3 CHANGE OF THE TNTK DURING TRAINING
We prove that the TNTK hardly changes from its initial value during training when considering an ensemble of infinite trees with finite a (used Equation (
Let Amin and Amas. be the minimum and maximum eigenvalues of the limiting TNTK. Assume that the limiting TNTK is positive definite for input sets. For soft tree ensemble models with the NTK initialization and positive finite scaling factor trained under gradient flow with learning rate 1) < (Amin + )max), ) we have, with high probability,
Theorem 2.
sup ( (I,, @00 (I))2)) O
(10)
M
The complete proof is provided in the supplementary material. Figure 4 shows that the training trajectory analytically obtained (Jacot et al. 2018 Lee et al., 2019) from the limiting TNTK and the trajectory during gradient descent training become similar as the number of trees increases, demonstrating the validity of using the TNTK framework to analyze the training behavior.
Remarks. In the limit of infinitely large a, which corresponds to a hard decision tree splitting (Figure 2 it should be noted that this theorem does not hold because of the lack of local Lipschitzness (Lee al., (201)), which is the fundamental property for this proof. Therefore the change in the TNTK during training is no longer necessarily asymptotic to zero, even if the number of trees is infinite. This means that understanding the hard decision tree's 's behavior using the TNTK is not straightforward.
4.2 IMPLICATIONS FOR PRACTICAL TECHNIQUES
In this section, from the viewpoint of the TNTK, we discuss the training techniques that have been used in practice.

---

Published as a conference paper at ICLR 2022
Triin sciput
Teat cuppoi
-10
-15
20
2.5
Figure 4: Output dynamics for train and test data points. The color of each line corresponds each data point. Soft tree ensembles with d = 3, = 2.0 are trained by full-batch gradient descent with a learning rate of 0.1. Initial outputs are shifted to zero (Chizat et al., (019).. There are 10 randomly generated training points and 10 randomly generated test data points, and their dimension
F = 5. The prediction targets also randomly generated. Let H (xx æ²) E RN*''' be the limiting NTK matrix for two input matrices and I an identity matrix. For analytical results, we draw the trajectory f(v, (+) H(v x: H x 2-)
e a: (r)r)) (Lee al. (219)) using the
limiting TNTK (Equation 7 where a E R an arbitrary input and œ E R and y E R are
the training dataset and the targets, respectively.
W1
U1
UP
shared
100
Skarei
S7
Figure 5: Left: Normal Tree, Right: Oblivious Tree. The rules for splitting in the same depth are shared across the same depth in the oblivious tree, while m. on leaves can be different.
4.2.1 INFLUENCE OF THE OBLIVIOUS TREE STRUCTURE
An oblivious free is a practical tree model architecture where the rules across decision tree splitting are shared across the same depth as illustrated in Figure 5 Since the number of the splitting decision calculation can be reduced from O(2d) to (d), the oblivious tree structure is used in various open-source libraries such as CatBoost (Prokhorenkova et al., 2018) and NODE (Popov et al. 2020). However, the reason for the good empirical performance of oblivious trees is non-trivial despite weakening the expressive power due to parameter sharing.
We find that the oblivious tree structure does not change the limiting TNTK from the non-oblivious one. This happens because, even with parameter sharing at splitting nodes, leaf parameters æ are not shared, resulting in independence between outputs of left and right subtrees.
Theorem 3.
The TNTK with the perfect binary free ensemble and the TNTK of its corresponding oblivious tree ensemble obtained via parameter sharing converge to the same kernel in probability in the limit of infinite trees (M + oo).
The complete proof is in the supplementary material. Note that leaf values π do not have to be the same for oblivious and non-oblivious trees. This theorem supports the recent success of tree ensemble models with the oblivious tree structures.
4.2.2 EFFECT OF THE DECISION FUNCTION MODIHICATION
Practically, based on the commonly used sigmoid function, a variety of functions have been pro- posed for the splitting operation. By considering large scaling factor in Equation (5), can envisage situations in which there are practically used hard functions, such as two-class sparsemax, (xx) sparsemax( [z. 0)) (Martins & Astudiilo, (2016). and two-class entmax, (x) entmax (x, 0)) (Peters et al. 2019). Figure shows a dependencies of TNTK param- eters. Equation 7 means that the TNTK is formulated by multiplying T(x,, 2z) and 7 T( æz) to the linear kernel E(,;, 2,)) On the one hand, T( 225) and T(x,, a2.) with small almost con-
7

---

Published as a conference paper at ICLR 2022
Mx. g)
Nommelized (P
Nommalized Vr..).
0.5
0.4
675-
1/3
020
0.33
02
025
0.25
0,
8.0
1007 www.eiot ixpec
product of
lenc proket apeb
Ixxr proded of apxa
11
10
15
20
Figure 6: Parameter dependencies (a,,; f(x, Nyy), and (a)) xr,). The vertical axes are normalized that the value is 1 when the inner product of the inputs is 1. The input vector size is normalized to one. For the three figures on the left, the line color determined by a, and for the figure the right, it is determined by the depth of the tree.
stant, even for different input inner products, resulting in the almost linear TNTK. On the other hand, the nonlinearity increases as increases. For Figure 2 the original sigmoid function corresponds to a scaled error function for a ~ 0.5, which induces almost the linear kernel. Although closed-form TNTK using sigmoid as a decision function has not been obtained, its kernel is expected to be almost linear. Therefore, from the viewpoint of the TNTK, an adjustment of the decision function (Frosst
Hinton 2017, PPopo et al. 2020. Hazimeh et al. 2020) can be interpreted as an escape from the linear kernel behavior.
4.2.3 DEGENERACY CAUSED BY DEEP TREES
As the depth increases, T T(x;, œÿ) defined in Equation (8) which consists of the arcsine function, multiplied multiple times to calculate the limiting TNTK in Equation 7 Therefore, when increase the depth too much, the resulting TNTK exhibits degeneracy: its output values are almost the same as each other's, even though the input's inner products are different. The rightmost panel of Figure shows such degeneracy behavior. In terms of kernel regression, models using kernel that gives almost the same inner product to all data except those that are quite close to each other expected to have poor generalization performance. Such behavior is observed in numerical experiments (Section S). practical applications, overly deep soft or hard decision trees are not usually used because overly deep trees show poor performance (Luo et al. 2021). which is supported by the degeneracy of the TNTK.
NUMERICAL EXPERIMENTS
Setup. We present our experimental results on 90 classification tasks the UCI database (Dua & Graff 2017), with fewer than 5000 data points, as in Arora al. (2020). We performed kernel regression using the limiting TNTK defined in Equation
with varying the tree depth (d) and the scaling (a) of the decision function. The limiting TNTK does change during training for infinite ensemble of soft trees (Theorem [); therefore, predictions from that model are equivalent to kernel regression using the limiting TNTK (Jacot al.) 2018). To consider the ridge-less situation, regularization strength is set to be 1.0 x 10-5, a very small constant. By way of comparison, performances of the kernel regression with the MLP-induced NTK (Jacot et al. 2018) and the RBF kernel are also reported. For the MLP- induuedd NTK, we use ReLU for the activation function. We follow the procedures of Arora al. (2020) and FeeFnndeez-Delgaddee cross-validation performance with random data splitting. To tune parameters, all available training samples are randomly split into one training and one validation set, while imposing that each class has the same number of training and validation samples. Then the parameter with the best validation accuracy is selected. Other details are provided in the supplementary material.
al. (2014): We report 4-fold
Comparison to the MLP. The left panel of Figure 7 the averaged performance of the depth. Although the TNTK with properly tuned parameters tend to be better than those obtained with the RBF kernel, they often inferior to the MLP-induced NTK. The results support the good performance of the MLP-in innduced NTK (Arora et al. (2220). However, it should be noted that when look at each dataset one by one, the TNTK is superior the MI. Pinduudde NTK by more than
function
8

---

Published as a conference paper at ICLR 2022
Awerged sccurcy
Computational Time (eoonds)
231
0.10
0.25
3.7
0.04
+4.2
0.22
3.78
15
0.00
Dapts
Dapth
Figure 7: Left: Averaged accuracy over 90 datasets. The performances of the kernel regression with the MLP-induced NTK and the RBF kernel are shown for comparison. Since the depth is not a hyper- parameter of the RBF kernel, performance shown by a horizontal line. The statistical significance is also assessed in the supplementary material. Right: Running time for kernel computation. The imput dataset has 300 samples with features. Feature values are generated by zero-mean i.i.d Gaussian with unit variance. The error bars show the standard deviations of 10 executions.
Table 1: Performance win rate against the MI.Pindduedd NTK. We tune the depth from d = 1 to 29 for the dataset- wise comparison for both the TNTK and the MI.P-induced NTK. For the RBF kernel, 30 different hyperparameters are tried. Detailed results are in the supplementary material.
TNTK
RBF
0.5
1.0
2.0
4.0
8.0
16.0
32.0
64.0
Win rate (%)
13.6
18.8
22.2
28.6
32.5
31.6
34.9
27.2
11.8
30 percent of the dataset, as shown in Table This is case where the characteristics of data and the inductive bias of the model fit well together. In addition, although the computational cost of the MLP-induced NTK is linear with respect to the depth of the model because of the recursive computation (Jacot et al. 2018),
computational cost of the TNTK does not depend on the depth, as shown in Equation (7). This results in much faster computation than the MLP-induced NTK when the depth increases, as illuttaated in the right panel of Figure 7 Even if the MLP-induced NTK is better in prediction accuracy, the TNTK may be used in practical cases as a trade-off for computational complexity. Arora et al. (2019) proposed the use of the NTK for a neural architecture search (Elsken et al. 2019) Chen et al. 2021 In such applications, the fast computation of the kernel in various architectures can be a benefit. We leave extensions of this idea to tree models as future work.
Consistency with implications from the TNTK theory. When increase the tree depth, initially observe an improvement in performance, after which the performance gradually decreases. This behavior consistent with the performance deterioration due degeneracy (Section 4.2.3) similar to that reported for neural networks without skip-comnection (Huang et al. 2020). shown by dotted yellow line. The performance improvement by adjusting in the decision function (Frosst & Hinton| 2017) is also observed. Performances with hard (a >> 0.5) decision functions are always better than the sigmoid-like function (a 0.5, as shown in Figure
CONCLUSION
In this paper, we have introduced and studied the Tree Neural Tangent Kernel (TNTK) by considering the ensemble of infinitely many soft trees. The TNTK provides new insights into the behavior of the infinite ensemble of soft trees, such as the effect the oblivious tree structure and the degeneracy of the TNTK induced by the deepening of the trees. In numerical experiments, we have observed the degeneracy phenomena induced by the deepening of the soft tree model, which is suggested by theoretical results. To date, the NTK theory has been mostly applied neural networks, and our study is the first to apply it to the tree model. Therefore our study represents a milestone in the development of the NTK theory.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
This work was supported by JSPS KAKENHI (Grant Number JP21H03503d, Japan), JST PRESTO (Grant Number JPMJPRI888 1855, Japan), and JST FOREST (Grant Number JPMJFR206J, Japan).
ETHICS STATEMENT
We believe that the TNTK's theoretical analysis will not have a negative impact on society as our work does directly lead harmful applications.
REPRODUCIBILITY STATEMENT
Proof' of all theoretical results are provided in the supplementary material. For the numerical experiments and figures, we share our reproducible source code in the supplementary material.
REFERENCES
Sina Alemohammad, Zichao Wang, Randall Balestriero, and Richard Baraniuk. The Recurrent Neural Tangent Kernel. In International Conference on Learning Representations, 2021.
Sercan Ömer Arik and Tomas Pfister. TabNet: Attentive Interpretable Tabular Learning. CoRR, abs/1908.07440 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, volume 32, 2019.
Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu. Har- nessing the Power of Infinitely Wide Deep Nets on Small-data Tasks. In International Conference Learning Representations, 2020.
Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. Journal of Machine Learning Research, 3, 2003.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32), 2019.
Lco Breiman, Jerome Friedman, Charles J. Stone, and R.A. Olshen. Classification and Regression Trees. Chapman and Hal//CRC, 1984.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective. In International Conference on Learning Representations, 2021.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On Lazy Training in Differentiable Programming. In Advances Neural Information Processing Systems, volume 32, 2019.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high- digensimen non-convex optimization. In Advances in Neural Information Processing Systems, volume 27, 2014.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient Descent Finds Global Minima of Deep Neural Networks. Proceedings of the 36th International Conference on Machine Learning, 2019a.
Simon Du, Kangeheng Hou, Russ R Salakhutdinov, Barnabas Poezos, Ruosong Wang, and Keyulu Xu. Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels, In Advances in Neural Information Processing Systems, volume 32, 2019b.
Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017. URL ics. ucl. edu/ml
10

---

Published as a conference paper at ICLR 2022
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural Architecture Search: A Survey. Journal of Machine Learning Research, 20(55):1-21, 2019.
Manuel Fernnndez Demández-Delgado, Eva Cernadas, Senén Barro, and Dinani Amorim. Do we Need Hundreds of Classifiers to Solve Real World Classification Problems? Journal of Machine Learning Research, 15, 2014.
Nicholas Frosst and Geoffrey E. Hinton. Distilling Neural Network Into Soft Decision Tree. CoRR, 2017.
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 on Machine Learning, volume 119, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2016.
Kaixuan Huang. Yuqing Wang, Molei Tao, and Tuo Zhao. Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? Neural Tangent Kernel Perspective. In Advances in Neural Information Processing Systems, volume 33, 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural Tangent Kernll: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems 31. 2018.
M.I. Jordan and R.A. Jacobs. Hierarchical mixtures of experts and the EM algorithm. In Proceedings of 1993 International Conference on Neural Networks, volume 2, 1993.
Ajaykrishna Karthikeyan, Naman Jain, Nagarajan Natarajan, and Prateek Jain. Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent. CoRR, 2021.
Guolin Ke, Zhenhui Xu, Jia Zhang, Jiang Bian, and Tie- Yan 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 Buld. Deep Neural Decision Forests. In 2015 IEEE International Conference Computer Vision, 2015.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. In Advances in Neural Information Processing Systems, volume 32, 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 Conditional Computation and Automatic Sharding. In International Conference Learning Representations, 2021.
Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S. Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. Enhanced Convolutional Neural Tangent Kernels. CoRR, 1.0000,,, 2019.
Haoran Luo, Fan Cheng, Heng Yu, and Yuqi Yi. SDTR: Soft Decision Tree Regressor for Tabular Data. IEEE Access, 9, 2021.
Andre Martins and Ramon Astudillo. From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification. In Proceedings of The 33rd International Conference on Machine Learning, volume 48, 2016.
Ben Peters, Vlad Niculae, and André F. T. Martins. Sparse Cestuennce-t-Sequenee Models. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 2019.
Sergei Popov, Stanislav Morozov, and Artem Babenko. Neural Oblivious Decision Ensembles for Deep Learning Tabular Data. In International Conference Learning Representations, 2020.

---

Published as a conference paper at ICLR 2022
Liudmila Prokhorenkova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. CatBoost: unbiased boosting with categorical features. In Advances Neural Information Processing Systems, volume 31, 2018.
J. R. Quinlan. Induction of Decision Trees. Machine Learning, 1(1), 1986.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe V. Le, Geoffrey E. Hinton, and Jeff Dean. Outrageously Large Neural Networks: The Sparsely- Gated Layer. International Conference on Learning Representations, 2017.
Cheng Tang, Damien Garreau, and Ulrike von Luxburg. When do random forests fail? In Advances in Neural Information Processing Systems, volume 31, 2018.
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adap- tive Neural Trees. In Proceedings of the 36th International Conference on Machine Learning, volume 97, 2019.
Alvin Wan, Lisa Dunlap, Daniel Ho, Jihan Yin, Scott Lee, Suzanne Petryk, Sarah Adel Bargal, and Joseph E. Gonzalez. NBDT: Neural-Backed Decision Tree. In International Conference Learning Representations, 2021.
Christopher K. I. Williams. Computing with Infinite Networks. Advances in Neural Information Processing Systems, 1996.
A PROOF OF THEOREM
Proof. The model output from certain depth tree ensemble ((d can be written alternatively using an incremental formula as
(x; W. (1))
1
σ (w pld-1) (xi, wi TT!!)
VM
+ 01- (w), f(d-1) (xi, wolh (12))
(A.1)
where indices (I) and (r) used with model parameters wm and Tm mean the parameters at the (l)eft subtree and the (r)ight subtree, respectively, and used in Wm,t denotes the node at (t)op of
(Wm.2, Wm,4; Wm.5), (l) the tree. For example, for trees depth 3, as shown Figure Win ( (r) (Wm.3, Wm,6, Wm,7), and Wm.: Wm.1.
prove the theorem by induction. When d 1,
M Σ
(10 (o; w. T)
(oww 100)mmm + oww,, (t)m,,))))mm..
(A.2)
M
mu
Derivatives are
( (Ki, w.
1
(Tm,1 T,, 2,0 (z))
(A.3)
Dwm.1
VM
(1) (1), w. T))
1
(w,T. xx;)
(A.4)
0mm.1
M
O1(1) (2,, W. π)
(1 (w
(wm11x,) xx)
(A.5)
VM
12

---

Published as a conference paper at ICLR 2022
Therefore, since there is only one internal node per single tree, from the definition of the NTK, the TNTK is obtained as
M 05 (0i, w; T)
0f (æj, w. T)
( (I;; mz))
110,1
0m0,11
m=1
Of (Is; w. ) Of (zz, w. π
O (,, Of (zz, w, T
0Tm,1
@tm.1
0Tm,2
0Tm,2
Σ (Tm,) Tm, a. æ ( (w wz;) + 20(w (wm, xz) ( 1 M
1
(A.6)
Since we are considering the infinite number of trees (M oo), the average in Equation A.6 can be replaced by the expected value by applying the law of the large numbers:
( (z), x;) Em ( Tm,2)² x; 1
(w 22,), (w 223))
-({ T x;) + T(x,;;
(A.7)
which is consistent with Equation 7. Here, Em (Tm,. - Tm,
because the variance of m.
1.0, and Wm,1 corresponds to Theorem For d >> 1, we divide the TNTK into four components:
(d)) (z;, x.) (d).(0 (x;, 2;) + (d)(() (æ,, 2.) + ((d).(r) (z;, x,)) ((d).(t) (z; æz))
where the indices (1), (1) and (r) mean the parameters of the (t)pp of the tree, (l)eft subtree, and (r)ight subtree, respectively. The index (b) implies the (b)ottom of the tree: tree leaves. With Equation A.7
we have
(1).00 (z,, 2E(x,, 2z) TT,,)
(A.8)
())00 (x;, m.)) = 0,
(A.9)
9 (1).(r) (z;; 4.)) = 0,
(A.10)
(1))bb) (x,, x.y) 2T 2T(2x;; 2z))
(A.11)
For each component, we show the following lemmas:
Lemma 1.
(d++1).0 (z), 2T 20,00.10 (z),
(A.12)
Lemma 2.
(d+1))(0) (x), 0;) ((d+1).(r) (a:;, 2r,))
(2,,, (x,, (z,, (d).(1) x,) + ((d).()) x;)
(A.13)
Lemma 3.
(d+1),(0 (x., ())) = 2T (ax;, (0 (x))
(A.14)
Combining them, derive Equation
13

---

Published as a conference paper at ICLR 2022
A.1 PROOF OF LEMMA
Proof. An incremental formula for the model output with a certain depth tree ensemble is
M
(o,, w, w. TT)
Σ
a aas) lm 1(d-1) 1) 1445 w T!!!
VM
m==1
+ (1 xi:) fm fld-1)
(I,, th T(())
(A.15)
where used in Wm,t implies the node at the top of the tree. With Equation (A.15).
1)(++1) (z), w, w.)
(w
(1a (x,, will (1)
(a,,, w T((1))
(A.16)
(ait,
1 M
Σ
m, 20 (w (T a 2
Bis (il)
(I.,,
w0
m=1
f(d)
Ty. w
(1) m
f
(((r)
(r)
T
(r)
m
m
((d)
(r)
(r)
f(())
T.j. w π (1)
2; w
m
m
+ f p(d)
22 w
(r)
(r)
p((
Bj w
(r) π (r)
(A.17)
m
Since fm Di Wm (r)
Tm
and
fm
Wm
are independent of each other because of the initialization of Tm Zz, wm
π
and have zero-mean Gaussian
distribution
with zero-mean iidd Gaussians
E
(d)
Ts. wm
(1)
( fm
(r) (x) and
E Im 2i wm,
(r) Tm)) p(d)
(1)
(E) 7im
zero Therefore, considering the infinite are
number of trees (M + 00),
+ (d+1),.0 (x,,,,) = x 2j T 2m (fle (I., w π f(d) T) w((h x!
+ p(d) xi whr) T!! fold Ty (x,, win x =
(A.18) From Equation (A.18). what we need to prove is Enn [1h (x:;, Wins o Tmn) s/hl (zoj. Wm. mmm) = (27 (æ,, a.)) We do this by induction. In the base case with d = 1,
Em
p(1) m (x;, Wms Tm) ( ((1) (xzz Wm: Tm)
=E =Em
(owwT,,1i 12)) + (1 o xx)) mm2) (o(wm,, 12))mm11111 + (1
ow T xz,)) Tm.
=Em
(Tm.1 Tm.2) o (w,,, 1x; (0:) (w.,
+2
Mm, 2m. ( (w wi:) + a (w (ww,,
= ( 2i) + ow azi)) -1)
-2T (z;, Wj),
(A.19)
where we use the property
E [[((r)) 0.5
(A.20)
for any v generated from a zero-mean Gaussian distribution. The subscript arrows (-)) show what the expected value will be.
"This holds because the model output weighted average of mm.
14

---

Published as a conference paper at ICLR 2022
Next, when the depth is d +
Em
fld+1) (x,, Wm, TT kmmsttt)
Im
(zys Wm: Tm)
0 (ww (0)))) Et, w TT/ + (1- (2 f(d (xx, (r) ग
=Em
20; 10,
(w
(1.,, with - + (1 o oww m. 2b (/m (2 win Ti
=Em
plo)
0i, (!! Tmm) - p(d) (I,, whi T!= o olw (w + f(d) (I (I,, with ग (11)
(A)
(8)
(lit)
Zj. (! T
pla))
w T(())
+ f(hl) (zz, w() (1))
By.
(C)
(D)
(A.21)
where the last equality sign is just a simplification separate components (A), (B), (C), and (D).
Since ((dl (x,, whn), ((2) and fm (zzj w nm are independent of each other and have zero-mean
ii.d Gaussian distribution, we obtain
Em ((A) (C)) T (2) xt) 1mm
p(u))
De w
nm
f(o))
Dzj w
T((1
+
xi, (r)
(()
f(d)
Jy w π (r)
(A.22)
Em (B) x (C)) = 0.5 Em
((d)
Tx. (r)
T
Fz.
m
(A.23)
Em [AA X (D)) = 0.5 Em
f(d)
2ss (T)) T
p(())
2z. w
गI (r)
(A.24)
Em (B) x (D) = Emm
((d)
Wis w m
(r)
π m
(1))
p(d)
7
(A.25)
Equation
A.23), Equation
A.24
and Equation A.25 cancel each other out. Therefore, we obtain
E
c(d+ 1) (a;; Win; Fmm) ((d+)) (m. Wms Tm)
f(d) =27 (a,, xby) Em ((el) (x,, wms Tm ) ) (z). Wms Tm)
(A.26)
By
induction
hypothesis
and
Equation
A.19).
we
have
Em f (xi, Wms mm ( (x,,, Wm, nm)) (27 (z,,, Therefore, the original lemma also
follows.
A.2 PROOF OF LEMMA
When the depth is d + 1, the derivatives of the parameters in the left subtree and the right subtree
Proof.
ad(++1) (ai, TT) or (w (m
x;, wm
m
(A.27)
@wm.
@wm,1
(xi win
(r)
(r)
af(d+1) (xi, w. π
Am
(1 o ( a.))
(A.28)
Owmn
Dwm.
where and r used in Wm., and Wm.r implies the node at the left subtree and right subtree, respectively. Therefore, the limiting TNTK for the left subtree
e (d+1). (I,, 2.y) T(x,, xy (6 (æ;, mr)) + (d)) (ax;, 2x,) (d),(()) (z), (A.29)
15

---

Published as a conference paper at ICLR 2022
Similarly, for the right subtree, since
[ ou T m1)(1 o(u xz)] = aall ((uTap aa))aa)))))) oa x;) to a2)o((uT0 23))
+0.5
-0.55
Eloo(u T wijor xr)),
[x,)),,
(A.30)
we can also derive
g(d+1),(r) (I,; my) = T(x, my (e (m, 2.)) + ((d).(1) (.)) + (d),(r) (æ;, 0;)) (A.31)
Finally, we obtain the following by combining with Equation (A.29) and Equation (A.3
(d++1),)) (z;, #5) ((d+1))()) (z;;
27 (z)) (O (()))(() (x,,, mzy) ((d),(0) x;) + ((d).(r) (ætr
(A.32)
A.3 PROOF LEMMA 3
Proof. With Equation and Equation (6).
0f (I,; w. T))
VM Hm,,eee,, wm)
@Tm.l
N II VM n=1
[ooww (w xi)
le/n (1 (w (w xii) Lave
(A.33)
When we focus leaf for a tree with depth of d, L or Lin equals d times. There- fore, by Equation (A.30), we can say that there is T(x,, contribution to the limiting kernel (d).1b) (I., (r)) per leaf index E [C]. Since there are 2d leaf indices in the perfect binary tree,
(d+1))()) (x,, 2z,) = (2T(x;;) xx)))*
(A.34)
In other words, since the number of leaves doubles with each additional depth, we can say
[d+1)) (z) = 2T; x., (2;,, ((d)))) (x;,
(A.35)
A.4 CLOSED-FORM FORMULA FOR THE SCALED ERROR FUNCTION
Since we are using the scaled error function as a decision function defined as
Jm,n (Wm,n Ø3²) =
(w (w.T.. a3:)
1
1
erf (ow x..) + 2
(A.36)
2
T and T in Theorem can be calculated analytically. Closed-form solutions for the error function Williams 1996 Lee al. 2019) are known to be
E(x,, x.,)
Ter 2.)) Elerf(u erf(u æ;)] aresin
[x;; σ;) + (.5)( xt, + 0.5)
(A.37)
4 Tort 2;,) = Elerf(u w:)erf(u" x;)]] /(1 2E(x, xz)) (1 2X(x,, 4 x
1
(xx,, xr,)²
(A.38)
16

---

Published as a conference paper at ICLR 2022
Using the above equations, calculate T and T with the scaled error function
T(x;, 2.)) = E
erf(ou' ax) erf( x.)) + E
orf(au T x;)) + 4 erf(au may))
+
1
4
4
1
1
E [erf(ou' 2;) erf(au x;)]
4
1
a a 22, 23
1
aresin
(A.39)
2m
Ki, L;) D(a 0.5)aa 0.5)
4
a²
E [eil(cuu) (x))ei((u") m;
4
a²
(A.40)
π
(11 2a² 2;)) 2a (x), 4a La;,, xT)²
B NEURAL TANGENT KERNEL FOR MULTI-LAYER PERCEPTRON
B.1 EQUIVALENCE BETWEEN THE TWO-LAYER PERCEPTRON AND TREES OF DEPTH
In the following, we describe two-layer perceptron using the same symbols used in soft trees (Section 2.1) to make it easier to see the correspondences between a two-layer perceptron and a soft tree ensemble, A two-layer perceptron is given as
1
fMLP (2) w,
Σ am (w a.)).
(B.1)
VM
where we use as the number the hidden layer nodes, a as a nonlinear activation function, and (Wi...., WM) Fx and (A1....,ay) R RIxM M parameters at the first and second layers initialized by zero-mean Gaussians with unit variances. Since
i (MLP w,, w.a)
1
a, (w
(B.2)
Own
VM 1
i f w. a)
(w)
(B.3)
80m
VM
we have
MIPP (2) (ii ..))
1 M
Σ
2n æz (r)) ) (w
(w.)) (wTTer))
contribution from the first layer
contribation from the second layer
(B.4)
Considering the infinite width limit (M + o0), we have
MLP (2) (zx xz) aI 2,) + +T(x,,
(B.5)
which is the same as the limiting TNTK shown in Equation 7 with d = up to constant multiple.
B.2 FORMULA FOR THE MLP-INDUCED NTK
Based on Arora al. 2019), we defined the T--hidden-laye perceptror as
(ML, W) = ((++))
W(L).
(((1-)
(w()x:)
VML
VMr-1
VM,
(B.6)
where ( E M (h)) E M, 1, and W(++1) E R M are trainable parameters. We initialize all the weights W = (W(1) ..... ((.1)) to values independently drawn from the
Note that the two-layer perceptron is the single-hiddennllyer perceptron.
17

---

Published as a conference paper at ICLR 2022
standard normal distribution. Considering the limit of the infinite width M1, M2..... ........ M - oo, the formula for the limiting NTK of L-hidden-layer MLP is known to be
L++1
L+11
(MLP(L) (2;, D3
1(h-1) my)
II M==h
((') (x;, 13.))
(B.7)
where
(0) (x) = 2; Zj.
(B.8)
Σ [(-1l) (2;
1(h-1) (z; (z)
A (h) (x:; x.)) =
E 1=2x2
(B.9)
Σ (h-1)) x3
[(h-1)
(R) (are, mz1) = u,roNormal
(u(o (w))),
(B.10)
(() (z) = E u.
[ (u)ō (v))]-
(B.11)
(0,A (M))
We let (((+1) (It, z3j) := 1 for convenience. See Arora et al. (2019) for derivation. There is correspondence between ( (z), xz)) and Σ (æ,, x;) in Theorem
5 (æ), xJ) and T (x,, 2zy in
Theorem and (1) (z)) and T (æ; 23) in Theorem respectively.
Since the recursive calculation is needed in Equation (B.7). the computational cost increases as the layers get deeper. It can be that the effect of increasing depth is different from that of the limiting TNTK, in which the depth the tree affects only the value of the exponential power as shown in Equation 7 Therefore, for any tree depth larger than 1, the limiting NTK induced by the MLP with any number of layers and the limiting TNTK do not match.
C PROOF OF PROPOSITION
Proof. As shown in Section 4.1.1 there is close correspondence between the soft tree ensemble of depth 1 and the two-layer perceptron. On one hand, from Equation (A.7). the limiting TNTK induced by infinite trees with the depth of 1 is 2(I(x; xz) (x,,, xz) + T( Tt )). On the other hand, if the activation function used in the two-layer perceptron is same induced by the infinite width two-layer MLP is E(x; a,) (xx æz) TTx,, æ;) (Jacot et al. 2018 Lee et al. 2019). Hence these are exactly the same kernel up to constant multiple.
defined in Equation (5). the NTK
The conditions under which the MLP-induced NTK are positively definite have already been studied.
Lemma 4 Jacot et al. 2018)). For a non-polynomial Lipschitz nonlinearity o, for any input dimension F. the NTK induced by the infinite width MLP is positive definite if ||x;||2= for all i E [N] and x; # xz (i
Note that defined in Equation (5) has the non-polynomial Lipschitz nonlincarity, Since the positive definite kernel multiplied by a constant is a positive definite kernel, it follows that the limiting TNTK (2), x,) for the depth also positive definite.
As shown in Equation C.1 as the trees get deeper, T(x;, my defined in Equation g is multiplied multiple times in the limiting TNTK:
(d) (zi (x;, 2r,) 2 E(a,, x. (T -- ((xi 2r.)) + (2T (2T zz))
contribution nodes
contribution leaves
(22 (2;,, (d E(x, x, ( x.)) + (I;,,
(C.1)
NTK induced by two-layer perceptron (if
The positive definiteness of T 2.,) has already been proven.
Lemma 5 Jacot et al. 2018)). For a non-polynomial Lipschitz nonlinearity o, for any input dimension F. the T (x,, | 2= for all E [N] and æ; f xj (i ( j).
Ejo("" x,)or(" x;)] defined in Theorem 1 is positive definite if
Note that d E(x;, 2; ) (x,,, x. + T( æι) for d E N is positive definite. Since the product of the positive definite kernel is positive definite, for infinite trees of arbitrary depth, the positive definiteness of (d)) (ar,, m.)) holds under the same conditions as in MI.P
18

---

Published as a conference paper at ICLR 2022
D PROOF OF THEOREM 2
Proof. We use the following lemmas in the proof.
Lemma 6. Let a R be a random vector whose entries are independent standard normal random
variables. For every v 2 O, with probability at least 2 22 we have:
|| 1 S un.
(D.1)
Lemma 7. Let 0g E R20 We have
Vos S Vn
O3.
(D.2)
In addition, our proof is based on the strategy used in Lee al. (011)), which relies the local
Lipschitzness of the model Jacobian at initialization J (xx 0), whose (i.j) entry 0f(m:.0) is a j-th component of A:
where 0
00,
Theorem (Lee et al. (2019)). 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 a learning rate 1j 2(Amin + Amax),
we have with high probability:
sup θ (a,, O% (z,,
(D.3)
VM
It is obvious whether or the soft tree ensemble's Jacobian is local Lipschitz. Therefore, prove Lemma & to prove Theorem 2
Lemma 8. For soft tree ensemble models with the NTK initialization and positive finite scaling factor o, there is > O such that for every C > 0, with high probability, the following holds:
{ [ 0) J(zz 1F
(2, ||
S K
011 v0, 0 E B (00. C)
(D.4)
K k
where
B (06, C)= = (0: ||0 0 <)-
(D.5)
By proving that the soft tree ensemble's Jacobian under the NTK initialization is the local Lipschitz with high probability, we extend Theorem for the TNTK.
D.1 PROOF OF LEMMA 6
Proof. By use of the Chebyshev's inequality, for some constant c, we obtain
P([|a]]> c) & /llellalll
= ( (2 +er((7/V22) /
(D.6)
where P means a probability. Since erl er(((//11/)))) (/ < 1, when we use 7 c/n, we get
P([|a] |> c) < ( (-e(-c²/2m)
(D.7)
Lemma 6 can be obtained by assigning un to
Figure shows the right-hand side of the Equation D.7 with c == 5n. when n 1, probability is 7.45 x TO-6 As becomes larger, the probability becomes even smaller.
19

---

Published as a conference paper at ICLR 2022
Probability
10
10 16
10 16
10 116
10"
10'
Figure 8: Right-hand side of the Equation
D.7
where
5n (in other words, in Lemma 6
D.2 PROOF OF LEMMA 7
Proof. By use of Cauchy-Schwarz Schwarz inequality, for p. q, x, R20. we have
PVI + qV S 1(p² + +z)
(D.8)
With Equation (D.8 we prove the lemma by induction. the base case,
vat + V0z S v2 a1 + +22,
(D.9)
which is consistent to the lemma. Next, when we assume
V0 + vak S Vhvai +...
(D.10)
have
Vai + ..... + vak + Vax+i (Va1 + .... + vak) + vak+1
S Vlva1 a1
ax + v ax+1
S Vk + 1 01 + +... a2 + ax+1-
(D.11)
D.3 PROOF OF LEMMA g
Proof. Consider the contribution of the leaf parameters at first: 1
Of w. T))
e0, wm).
(D.12)
Oxm,
MM
Next, the contribution from the leaf parameters is
0f(3; W. iwmn
apm. Wm)
Tm,
M
Sn. (XD,, Wm )zzū (w),n
(D.13)
VM
t=1
where
Su,e(x, wm) =
II
(w)) :D;) t/ (1 (x)) Lcod soacaasss (-1jlane,
nn==l
(D.14)
20

---

Published as a conference paper at ICLR 2022
and & is logical conjunction. For any real scalar p and q, the scaled error function defined in Equation (5) bounded as follows:
0 S (p)) 1 (o(p) - (4)) s 1p al, 0 ) S (ö(p) ا(4) S alp al- (D.15)
Therefore, the absolute value of Sn,e does not exceed 1. With Equation D.15). we can obtain
e Wm) Wwmn
[[ wm m mwmmnn) 1l2 s aa|la|122
(D.16)
with high probability. Therefore, with Lemma in probability.
((xx = [II (x,, w)] π )|?-)
M
e Wm)
c
+
(um,e( wm)²)
Ww
M
3 22 12,11 Σ
m=1
n=l
Σ La M1
(D.17)
Next, we will consider the Jacobian difference, Since em,,(0;; Wm) is multiple multiplication of the decision function, by use of
S [p: qil
for 1p:l,19/ S 1,
(D.18)
we obtain
|mm. (IE Wm) e20, wm)l
II (t
1e/0 (1 (wi, Jnne
N II n=l
1e/0 (1 - (w i xi) Iaye
w m. Iz)
N
(w m, 2;
1// (1- (. haye
==
(w (mm,n 2i)
Ie/" (1 mm x:)) lase
w mn Di w wn 2i
|ay [mmm - 2mm.nll2
(D.19)
where it should be noted that (e n) & (n > 2) must be false.
21

---

Published as a conference paper at ICLR 2022
E (æ,, Wm) Sn,e (3,; Wm) can be bound in the same way Equation D.19 Therefore, also obtain
e2 Wm)
Op (Ri, Wm)
= ||Sn (ma, w.) az (w mii) - Spgt (at,, umm) az (i0 m. ll2
||a lla Sn,t (ar,, wm) (w (mm,n 2.) Sn,e (Ii, (m (i m Fii)
| ll ((Sn, (ats wm) - Sn,e (æi, Wm / (wmm ais)
+ l( (wm,n - à (w 2i) Snnt (Ei, (m)) < || la [a(Sn, (1 wm) - Sn,t (1 wm))
+ (a - 2 to x2))l
N
$ 20 x;,
W
1m,
(D.20)
n=1
To link Equation D.19) and Equation D.20 to the 11-00) 12. we use Lemma inequalities:
to obtain the following
N
Wm.n Wm,ul12 VN - vm 125 VN -0112,
(D.21)
Km, #m,el S VC 7ml125 VC100 -
(D.22)
8=1
With Equation D.I. Equation (D16)), Equation (D.19), Equation (D200), Equation (D21 ), Equation D.22).
and
[1 0) - (2x,0)1²
[1) w) J(x,, w) 1| TT) - [xx (
apm,e Wm)
Opm.e(an (xts, Tm
m.
Owmm
Am.
Orim
n=1
(mm.el ( Wm) e (mm))))
+
N
M
(Tm, - #m.e) Opm, ( wm)
@pp. wm)
Opm, (x vm))
Am.e) 1?)
ΣΣ
Σ
Iw0m,
Iwmmm
Iwi
(mm,elats, Wm) (x,, mmm)
22

---

Published as a conference paper at ICLR 2022
M
N
im 1200 )) 2
(Tm.e
=m.elal(z0;11)) +
2cx 2x1| x
Wm.
n=
N
a Wmm. aim.alle llz
M
N
01120(110:12) + 20ll -0llvc)) [VV
m=
2
V/112111211 -0112 0112
N
N (aVDlllzz 22a 1 (VNO)) CN\[
110 0
(D.23)
By considering the square root of both sides in Equation D.17 and Equation (D.23). we conclude the proof for Lemma g
E PROOF OF THEOREM 3
Proof. We can use the same approach with the proof of Theorem Using an incremental formula, the output from the oblivious tree ensembles can be written as follows:
Σ o (wT, f(d-1) (xi w =
( (2,,
(x) w. TT)
VM
+ (1- (w), f(d-1) (xn,w(e) (0)) T m
(E.1)
where (s) of wm means (s)hared parameters at subtrees. Intuitively, the fundamental of Theorem that the outputs of the left subtree and right subtree still independent with the oblivious tree structure. Even with parameter sharing at the same depth, since the leaf parameters π are not shared, the outputs of the left subtree and right subtree are independent.
We will see that Lemmal and 3 are also valid for oblivious tree ensembles.
Correspondence to Lemma 1 To show the correspondence to Lemma [ is sufficient show
that Equation A.22 Equation A.23 Equation (A.24). and Equation (A.25) hold when
Em
(d++)) m
(2++)(x,
(x,, Wm, Tmm
((++1) (xy, Wm:: Tm)
=Fm
((())
Di, (0/ Tml
p(d)
(a,, w(()) (1(1 o mm v.)) ) + p(d)
Di w( mr(r)
(A)
(B)
p(d))
Fijs (o) T0
p(d)
xe (s) TT(()) ( (0;)) + p/a)) azy, (s)
mm
(D)
(F.2)
This equation corresponds to Equation A.21 Here, since the leaf parameters π are not shared, the outputs of the left subtree and right subtree are still independent with the oblivious tree structure. Therefore, we can obtain the correspondences to Equation (A.22). Equation (A.23). Equation (A.24).
and Equation (A255) with the same procedures.
23

---

Published as a conference paper at ICLR 2022
Correspondence to Lemma 2 For the depth + since
0fml
Ii, whi) Tmm) Owm,s
afldt1) (xi w. a)
o(w,, x;;
wwm.s
Bi winh amm
(x)
+ (1 o2wm
(E.3)
Wwm,
the corresponding limiting TNTK is
(dd+1)(++) 2;))
0fth!
Iii winh nm
0fma
(r) 2is winh nr
Bm
o (w (t))
+ (1 -w x;))
iw m.
mw.m,
a
, win mm
(r)
5 Dwm.
(r) (x)
7
o(w
+ (1 (w m. x
wwm.o
d
Dis wii
(8)
7m
(1)
as!a)
a;; whah mm
(r)
as(d)
Wis woo? mm iw
Bm
wwm,s
2=2
(A)
!1)
2jj win
a win
Tm 3) wm
mm
a a.
Owm,s
Owm,
Owm,
(D)
(E.4)
a (wi
Since
and
m.
ml
for s 3 d} are independent to each other
8t0 d and have zero-mean Gaussian distributior similar calculation used for Equation (A.22). Equa-
8tem.
*For single oblivious tree, the number splitting rule d hecause of the parameter sharing.
24

---

Published as a conference paper at ICLR 2022
tion A.23 Equation (A.24) and Equation
A.25 gives
afm
æi, wmi
Tm
Øj Wmn Tim
Em (A) x (C) T (æt, 2ÿ) Em
wwmm
ow
@05m
Ti Win Tm
J wmn's mm Öw
Ow
(E.5)
T
Ci wint
(r)
O pldd
Øj wim Tm Owm,s
Em (B) x (C)] -0.5 Bm
(E.6)
iwm,e
@afm
(a) Tee
a fm
Dj Wm ww
n7
Em (A) x (D)] -0.5 Bm
(E.7)
iwm,e
( @0fh
(r) Is. wmm
(r) (5)
J. Wmm mm mw
Em (B) x (D) Em
(E.8)
Own,s
As in the previous calculations, Equation E.6). Equation out. As result, we obtain
F.7 and Equation
E.8
cancel each other
(d++1)(+) 2z), = 2T (a; m.y) (e(d))(0)) (æ,, 0.)) (d).(o) (ot (x),
(E.9)
Correspondence to Lemma 3 Considering Equation A.33) once we focus on a leaf f, it is not
possible for both 1 and 1, to This means that a leaf cannot belong to both the right subtree and the left subtree. Therefore, even with the oblivious tree structure, there no influences. Therefore, we get exactly the same result for the Lemma
F DETAILS OF NUMERICAL EXPERIMENTS
F.1 SETUP
F.1.1 DATASET ACQUISITION
We use the UCI datasets Dua & Grafi 2017 preprocessed by Femmndezz-eeladoo et (2014). which are publicly available at http: http:p://perrrooe de sgado/papett
jm r/data.aaa... wwtppperr.a....... wwt.iiiiuu...... usc. weteeee/maangg ws/manuell.... eetsssee//auleleereeee.... fernendeeende
gz. Since the size of the kernel is square of the dataset size and too many data make training impractical, we use preprocessed UCI datasets with the number of samples smaller than 5000, Arora et al. (2020) reported the bug in the preprocess when the explicit training/test split is given. Therefore, we do not use that dataset with explicit training/test split. As a consequence, 90 different datasets are available.
F.1 KERNEL SPECIFICATIONS
TNTK. See Theorem I the detailed definitions. We change the tree depth from 29 and change in (0.5, 1.0, 2.0. 4.0, 8.0, 16.0, 32.0, 64.0).
MI.P-induced NTK. We assume the MI.P activation function as ReLU. Our implementation based on the publicly available code used in Arora et al. (2020). For detailed definitions, see Arora ct al. (2020). The hyperparameter this kernel is the model depth. We change the depth from to 29. Here, depth- means there is no hidden layer in the MLP.
https: wtt.:ttw.ccom/e////eeeeeeeeeeeee tangent kerne1-UCi
25

---

Published as a conference paper at ICLR 2022
75
Axcraned Aacranedaccss acounay
13
73
Figure 9: The y dependency of the RBF kernel performance.
RBF kernel. We use seikit-learn implementation The hyperparameter of this kernel is 7 in- verse of the standard deviation of the RBF kernel (Gaussian function). For Figure 3 we tune 7 in (0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08, 0.09, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 20.0, 30.0). resulting in 30 candidates in total. In our experi-
ments, 7 2.0 performs the best on average (Figure
F.1.3 MODEL SPECIFICATIONS
We used kernel regression implemented in scikit-learr? To consider ridge-less situation, regulariza- tion strength set to be 1.0 x 10-8, a very small constant.
F.1.4 COMPUTATIONAL COSTS
Since the training and inference algorithms of the kernel regression are common across different kernels, we analyze the computational cost of computing single value in gram matrix of the corresponding kernels in the following. The time complexity of the MLP-induced NTK is linear with respect to the layer depth, while that of the TNTK remains be constant. Such a trend can be seen in the right panel of Figure 7. For the RBF kernel, the computational cost remains the same with respect changes hyperparameters, thus its trend is similar the TNTK. In terms of the space complexity, when considering a multi-layered MIP, since it is not necessary to store all past calculation results in memory during the recursive computation, the MLP-induced NTK computation consumes certain amount of memory regardless of the depth of the layers. Therefore, the memory usage almost the same across the RBF kernel, TNTK, and MLP-induced NTK.
F.1.5 COMPUTATIONAL RESOURCE
We used Ubuntu Linux (version: 4.15.0- 17-generic) and ran all experiments on 2.20 GHz Intel Xeon ES-2698 CPU and 252 GB of memory.
F.2 RESULTS
F.2.1 STATISTICAL SIGNIFICANCE OF THE PARAMETER DEPENDENCY
A Wilcoxon signed rank test is conducted to check the statistical significance of the differences between different a. Figure [0] shows the p-values for the depth of 3 and 20. As shown in Figure 7 when the tree is shallow, the accuracy started deteriorate after around a 8.0, but as the tree becomes deeper, the deterioration became less apparent. Therefore, statistically significantly different pairs for deep tress and shallow trees are different. When the tree is deep, large shows significant difference over those with small a. However, when the tree is shallow, the best performance is achieved with a of about 8.0, and too large, the performance deteriorates predominantly.
http:pp//.kkkkkkaa../////...aaaa //tp::::////ikitt1eeaa Kerne1Rl6ge..ttl
pai pairwises mairwiee.rb htm.
26

---

Published as a conference paper at ICLR 2022
001
R01
001
5.19
0.86
05
16
26
46
*.
160
32.0
66.
95
20
46
30
156
32.9
68.8
Figure 10: P-values of the Wilcoxon signed rank test for different pairs of a.
10
24
101t
11TE
1015
Figure 11: Performance comparisons between the kernel regression with MIPPinducce NTK and the TNTK on the UCI dataset.
1112
113
Figure 12: Performance comparisons between the kernel regression with RBF kernel and the TNTK on the UCI dataset.
0.9600
Peatonk creebbatto codeficenn
0.9760
0.9725
0.9700
0.9875
0.930
MLP induced NTK
10'
Figure 13: Pearson's 's correlation coefficients with predicted values of the TNTK with different a.
27

---

Published as a conference paper at ICLR 2022
F.2.2 DATASET-WISH RESULTS
For each a, scatter-plots shown in Figures [1 and 12 As shown Figure 13 the correlation coefficients with the TNTK are likely to be higher for the MLP-induced NTK than for the RBF kernel. Tables and are dataset-wise results of the comparison between the TNTK, the MLP-induced NTK. and the RBF kernel. For each depth is tuned for each dataset. In terms of the depth, the best performers from kernel, 7 is tuned in each dataset from 30 candidate values as described in Section F.2 Therefore, the number of tunable parameters is the same across all methods. All parameter-wise results are visualized in Figures 14 and 15
29 are compared with the TNTK and the MI.P-induced NTK. For the RBF
28

---

Published as a conference paper at ICLR 2022
RBF
87.500
93.750
87.500
53.125
56.818
58.696
83.000
99.000
89. 39.000
74.038
59.615
88 18.462
93.269
71.154
100.000
100. 00.0000
$7.903
78. 78.030
86.486
96.622
60.526
85.256
98.295
67.222
49.479
95. 25.408
78.571
29.000
87-500
95.673
MLP-NTK
100.000 000
100.000
87.500
65.625
69.318
65.217
89.000 99.000
99.000
87.000
74.038
68.269
90.385
94.231
69.231
100.000
100.000
47.581
85.606
88.514
87.162
63.158
83.974
99.432
72.222
53.646
93.878
85.204
36.500
87.981
96.154
n=
87.500
87.500
87.500
59.375
69.318
67.391
89.000
99.000
88.000
75.962
65.385
87,500
94.231
74.038
100.000
100.000
44.355
85.606
86.486
87.162
67.763
85.256
97.727
72.222
53.125
93.367
83.673
43.000
86.538
91.827
Table Comparison between TNTK and ML P-induced NTK for a half of the dataset (1/3).
a=
87.500
87.500
87. 77.500
59.375
68. 182
66.30 16.304
89. .00000
99.000
88 88.000
75.962
66.346
87.500
94.231
75.000
100.000
100.000
44.355
85 606
86 66.486
87 7.838
67.105
84.615
98.295
72.222
53.125
93.367
83.673
40.500
86.538
91 12.827
x=
87.500
$7.500
87.500
56.250
68. 18.182
66.304
89. 19.000
99.000
89 $9.000
75.962
66.346
87.500
94.231
72.115
100. 00.000
100.000
44.355
85.606
87.162
87.162
67.105
84.615
98.295
72.222
53.125
92.857
83.673
39,000
86.538
92.308
a=8.0
87.500
87.500
87.500
53.125
69.318
65.217
99.000
99.000
89.000
75.962
66.346
87,500
94.231
72.115
100.000
100.000
50.000
85.606
87.838
86,486
64.474
84.615
98.864
71.667
53.646
92.857
83.673
37.500
86.538
92.308
0x4..0
87.500
87.500
87.500
53.125
69.318
67.391
89.000
99.000
89.000
74.038
66.346
87.500
94.231
70.192
100.000
100.000
47.581
84.091
88.514
88.514
60.526
84.615
98.864
71.667
53.125
93.367
83.673
36.000
86.538
91.827
Q=2.0
87.500
93.750
87.500
53.125
67.045
58.696
89.000
99.000
87.000
75.000
64.423
87.500
94.231
67.308
100.000
100.000
48.38 18.87
84.848
88.514
96.622
58.553
85.256
98. 38.864
70.000
53.646
92.857
83.673
36.000
87.019
93.269
a=1.0
87.500
100.000
87.500
53.125
64.773
57.609
08.000
99.000
84.000
74.038
59.615
88.465 46.462
94.231
68.269
100.000
100.000
43.548
81.061
88.514
97.973
57.895
85.256
99.432
65.556
53.646
94.388
83.673
34,000
86.538
93.750
a=0.5
87.500
87.500
$7.500
56.250
63.636
55.435
84.000
100.000
81 1.000
67.308
57.692
90.385
93.269
65.385
100.000
100.000
37.097
81 31.061
88.514
95.946
56.579
83.974
98.864
62.222
52.083
93.878
82.143
31.000
86.538
30.865
size
10
24
32
90
92
100
101
102
103
105
106
106
106
120
120
123
131
148
150
151
155
178
182
194
195
198
200
208
210
pittsburg- bridges- T-OR-D D
piusburg- bridges- REL-L
pittsbrgg bridges- TYPE
pittsburg- Tridges-MATERY
breast- cancer wisc- prog
seench-sonar-mmneese
pittsburg bridges-SPAN fertility
molee- hiol-boo-g promoter
occut--in in-iiflllmaaioon
heart- www-swwitzzerarrr land
ocute- nephritis
post-operative
rchocardiogran
lymphography
breast-tissun tissue
lung-cancer
parkinsons
balloons
teaching
hepatitis
planning
heart-va va
name
trains
lenses
breast-He
wine
flags
seeds
ZOO
iris
10
11
12
13
14
15
16
17
18
19
20
22
24
26
27
28
29
0
7
9
29

---

Published as a conference paper at ICLR 2022
RBF
69.811
82.463
65.845
82.877
53.618
70.395
11.494
81.169
45.427
81.250
92.330
85.278
97.253
62.156
69.248
90.756
79.688
90.226
95.599
70.377
99.333
90.865
59.302
81.686
96.714
78.075
90.755
69.661
96.484
77.488
MLP-NTK
70. 00.283
86.567
71.831
85.616
57.895
71.053
83.117
81.818
52.134
85.417
91.761
83.889
97.802
61.697
71.239
89.706
80.273
91.353
97.007
71.918
98.833
93.269
66.279
87.064
98.000
74.064
88. 88.281
75.000
92.708
81.398
a=64.0
71.226
87.313
75.000
85 85.274
59.539
73.684
82.792
81.169
50.000
86.905
88.352
80.833
97.253
61.697
64.823
89.076
78.320
87.218
96.479
72.603
96.667
85.256
68.023
87.355
98.000
77.005
87.630
76.693
90.234
72.038
Table 3: Comparison between TNTK and ML i-nduced NTK for a half of the dataset (2/3).
a=32.0
71.226
87.687
75.000
85.274
59.211
73.684
84.091
81.494
50.305
86.905
58.352
80.833
97.253
61.697
64.823
89.076
78.320
87.218
96.479
72.603
97.000
85.256
68.023
87.791
98.000
75.802
87.630
77.083
90.234
72.038
a=
71.698
88.433
74.648
65.274
58.553
71.711
84.091
81.818
50.610
86.607
38.352
80.833
97.253
61.697
64.823
89.076
78.320
87.782
96.831
71.747
97.833
90.064
68. 08.023
87.791
98.000
73.529
87.630
76.302
90.104
72.156
a=8.0
71.698
88.433
72.887
85.616
59.539
68.421
82.792
80.844
52.744
86.012
88.352
81.111
97.253
61.927
64.823
89.286
78.516
88.534
97.359
71.062
98.333
91.346
67.151
87.645
98.000
72.727
88.151
76.042
90.234
72.986
0=4.0
70.755
88.4 38.433
70.423
84.589
59.211
66.447
80.844
80.844
53.049
84.524
87.784
80.833
97.527
61.927
64.823
89.286
78.320
89.474
97.359
72.260
98.833
89.90 99.904
66.279
87.209
97.857
69.786
87.891
73.307
90.495
73.578
a=2.0
70.755
87.687
69.718
84.247
83.882
61.842
8..571
81.169
53.134
83.036
90.341
80.556
97.527
61.927
64.602
89.076
78. 18.125
90. 60.
97.359
70.719
99. 167
88.782 782
64.099
86.628
97.857
63.369
88.021
71.354
93.229
76.540
58.88
0=1.0
67.453
87.313
67.254
83.904
58.224
61.513
77.273
78.247
60.305
79.167
91.477
81.389
97.802
61.697
65 25.265
89.076
78.125
91.353
96.655
99.521
99.333
84.615
60.610
85.174
97.286
65.775
89.453
70.182
93.620
77.014
a=0.5
60. 849
83.209
64.789
83.219
55.263
59.539
69.805
.0.805
71.753
47.561
71.429
90.057
82.778
97.802
61.697
69.469
89.076
79.883
91.729
96.127
64.897
99.333
81.250
59.012
82.558
96.286
67.513
89.583
68.229
93.750
78.318
size
214
270
286
294
303
306
310
310
330
336
351
360
366
435
452
476
512
531
569
583
600
625
690
690
699
748
768
768
768
846
vertebral -column----- 2clases
vertebral columm-3elasee 3elases
breast-canee caaat-cance--wee caccer-wisc-diiieee wiineer--s--iagg
statlog-ause aaalog-austraaiann-eeeee -iteeei
congressional- voting
haberman-survee survival
ilpd-in ies--indian---- -ndian-liver liver
synthetic-com control
control
heart- heart-hungard hun aunnaaiian
heart-cled ceeeelceeelaadd
primary-tuie ttumor
credit- appiitapproval
creast-cancer-wee
statlog hhattog-heart heart
mreast-canced
ionosphere
dermatology
orrhythmia
cylinder-bande
low-res-spes. spect
balance scale
statlog-vchict
energy-y2
energy-yl
musk-1
name
glass
ecoli
libras
blood
pima
30
31
32
33
34
35
36
37
38
39
41
42
43
44
45
46
47
48
50
51
52
53
54
55
56
57
58
59
30

---

Published as a conference paper at ICLR 2022
RBF
79.605
91.228
100.000
78.750
73.700
73.000
75.490
92.059
43.207
54.380
95.603
64.438
85.625
83.875
68.000
98.032
75.103
92.043
79.143
78.955
97.200
86.418
98.999
64.152
88. 18.
90.652
65.748
85. .60
84.640
96.44
MLP-NTK
84.978
94.189
98. 78.640
80.000
77.500
72.900
83.725
93.039
50.272
59.636
96.168
69.625
86.125
84.875
66.250
97.743
78.351
93.173
84.181
78.955
97.660
97.397
86.920
99.406
63.410
89.735
94.913
69.097
86.540
86.340
a=
77.851
89.693
99.268
79.271
75.400
72.500
76.765
90.490
51.155
60.849
93.405
70.312
77.625
78.563
55.937
96.123
76.495
91.855
79.614
78.955
95.624
97.200
82.371
95.307
65.086
89.159
93.348
68.913
85.520
86.520
P-inuuced NTK for a half of the dataset (3/3).
a=32.
78.070
89 99.693
99.268
78.958
75.500
72.300
76.961
90.784
52.514
60.445
93.467
70.312
77.750
78.938
56.375
96. 12.123
76.598
91.996
79.661
78. 98.95
95 15.884
97.200
82.371
95.307
64.943
89.181
91.478
68. 08.995
85. 55.900
36.740
n=16.0
78. 78. 72.
90.022
99. .9.268
78.854
75.500
72.500
77.255
10.784
52.038
60.243
93.467
70.375
77.625
79. 79.500
57.062
96.181
76.753
91.855
79.896
88.955
95.927
97.200
82. 82.403
95.526
64.200
89. 159
89. 89.630
68.975
86.500
36.700
a=8.0
80.811
91.667
99. 99.268
77.604
76.200
72.300
79.412
91.373
51.155
60.040
93.467
70.625
77.688
80.750
58.312
96.354
77.062
91.949
79.896
78.955
96.231
97.200
82.465
96.902
62.548
89.358
93.130
69.158
86.720
86.660
n=4.0
82.675
93.092
99.268
75.625
77.300
72.500
80.686
92.157
50.068
58.154
93.467
70.000
77.938
81.875
60.375
96.701
77.423
11.902
80.744
78.955
96.750
97.200
83.093
97.872
60.010
89.513
90.652
68.791
86.540
86.500
a=2.0
82,456
93.640
99.268
72.083
77.800
72.600
80.686
92.157
47.147
54.380
93.405
68.812
79.438
82.938
62.438
97.164
77.938
92.043
82.250
78.955
97.097
97.200
84.536
98.655
55.532
89.358
92.435
67.545
86.520
86.300
Table 4: Comparison between TNTK and ML
a=1.0
82.566
92.982
99.163
71.250
76.500
72.300
80.588
91.961
44.293
49.326
93.467
65.938
81.812
83.938
63.562
97.569
77.320
92.514
82.957
78.955
96.967
97.240
85.947
98.905
49.880
89.336
91.174
66.810
86.340
85.780
a=0.5
22.456
92.325
99 99.268
72.708
75.200
72.400
81.078
92.353
40.082
42.588
93.719
63.062
83.812
84.750
64.812
97.454
76.289
92.232
03.838
78 955
97.358
86.731
12.124
50,407
88.6 08.628
91.478
63 63.623
86.360
85 45.440
96.3
size
912
912
958
961
1000
1000
1022
1022
1473
1484
1593
1599
1599
1600
1600
1728
1941
2126
2126
2201
2310
2536
3190
3196
4177
4521
4601
4898
5000
5000
oocytes trisopterus, nucleus 2
66 oocytes merluccius nucleus 4d
61 oocytes trisopterus states 5b
oocytes merluccius states 2 contrac
cardiotocograply 10clases
cardiotocography- 3elases
statlog- wewlloogggaa--ceeee
wine-quality. red
molec-biol bic-siio--
87 wine-quality-white
63 manmographic
88 waveform-noise
led-display
plant- texture
plant margin
shape plant- plant-shape
steel-plates
statlog statlog-image image
chess-Krvkp
62 tic fic-tac-tee
spambase
waveform
semeion
obalone
name
69 yeast
titanic
ozone
bank
car
60
64
65
67
68
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
89
31

---

Published as a conference paper at ICLR 2022
traits
balloons
leraes
Turn June-canzer
posi opera--eerivve
Neessy
pillshee--ee www.eee--riiia----------
piltsbur--hee R.
20
30
10
Doyt
Depo
gromoser
pinnbuug bridges MATERIAL
noule-nephriis
Aeessyy
1.55
20
Day
Depth
Depla
Dopfi
Dxpl
scubs-infaammmiiin
cehocardingram
ini
1.25
2.50
0.35
0.75
Teyth
Depth
Dopt
Dopo
teaching
bepusit
wine
planning
flags
Depta
cunn--bench--e
12
20
Deyth
Dept
Dopt t-ungartia
Depo
statloy
brrest-cancer
2.475
0.300
0..25
20
Dapth
Deph
Depta
Deph
Depta
babermon survival
vertebrll colurn 2clases
verterral columo Jebsss
primary numor
ecoli
Agungy
0.58
Deghh
Deyth
Dept
Depn
Depo
lonosphere
libras
demmtooogy
congressi ceneresiinnalloo vodia
aythyihmii
Ketred:
0u550
Dept3
Figure 14: Dataset-wise comparison for half of the dataset (1/2).
32

---

Published as a conference paper at ICLR 2022
musk-1
Wiinder-enndd
Low-res-iper
brcent waa.---ccccc------aae.e-
Hpl Ind-indan--ivee
2.55
Depl
syrthetie-mitrel
crelit-appnall
brced-canecswviee
6775
20:65
0.50
20.55
2225
13
20
30
10
Depo
Dopt
Depo
pinsa
energyyy
statlog vehicle
26:55
0.
Dayh
Dephi
Dep
Dopii
Dupl
Duestes triuplate madea 20
aurylce iispiinos states
mamnonggghi
stad gememeeetett
0.75
3.70
Diggh
Dayth
Dept
Doph
Depo
Led-dis dister
tocytes merlaccius madeus 44
oocytes met luscis EES 20
contrac
yeast
plas--dupe
0.00
325
20
Dopt
Depo
plate
cundosocopupbbyydeee 3dlee
cardlotseagrphy
0.70
2.78
Dapph
Deph
Depta
Dept
Depta
stadlg image
ozone
molec splice
chess levipp
abolone
3.55
0.35
0.50
2.255
Teyth
Dept
Dupn
Depn
bank
spumbase
inc quilitywhite
wavefoomm soos
wav comm
Figure 15: Dataset-wise comparison for half of the dataset (2/2).
33


Reviews:
[{"review_id": "v7JltVzQeqh", "reviewer": "Reviewer_r8ZN", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The work attempts to generalize the recently proposed Neural Tangent\nKernel method to trees and forests, and attempts to use that to\nanalyze certain properties and training behavior of a special type of\ndecision trees (the so-called soft trees) and their infinite ensembles.\nThis could be of interest to followers of the Neural Tangent\nKernel method and its use in analyzing neural-network-like tree\nstructures.\n\nFor the rest of the audience, the paper has not made an attempt to\nclearly lay out all the basics and the logic.  It relies heavily on\nexternal references for many critical concepts and results.\n\nFor a start, the notion of a \"soft tree\" involves some mixing of the\nfollowing properties of trees:\n(1) whether the splitting function is fixed in one shot (e.g. by\ninformation theoretic choices) or adjustable and trainable (e.g. by\ngradient descent) during learning, \n(2) during or after training, whether the split is deterministically\napplied to every input, and\n(3) whether the splitting function parameters are frozen by training or\ncontinue to be samples from some probabilistic distribution that has\nparameters estimated during training.\nThese concepts are never clarified in the paper, so when additional\nnotions like ensembles and infinitely large ensembles are brought in,\nthe confusion just grows.\n\nOne may wonder how the chosen definition of soft trees is related to\nthose of probabilistic decision trees [1] and neural trees [2].\n\n[1] Michael I. Jordan,\n A Statistical Approach to Decision Tree Modeling,\n Machine Learning Proceedings 1994, Morgan Kaufmann, 1994, 363-370,\n https://www.sciencedirect.com/science/article/pii/B9781558603356500519\n\n[2] J A Sirat & J-P Nadal,\n Neural trees: A New Tool for Classification,\n Network: Computation in Neural Systems, 1:4, 1990, 423-438,\n https://www.tandfonline.com/doi/abs/10.1088/0954-898X_1_4_003\n\nGiven that the work builds on a key concept in prior art, for the\npaper to be self-contained, the notion of \"Neural Tangent Kernel\"\nshould first be explained (why it is called a Kernel, why Tangent, why\nNeural, what is its significance, what new insight it has contributed,\n...).   A basic understanding of this is important for the proposed\nextension to have a sound footing. It should also be stated upfront\nwhat is expected of the proposed extension.   What insight contributed\nby the NTK do you expect to reproduce for tree ensembles?  What new\ninsight do you want it to bring on?\n\nMany other improvements are needed in the presentation of the logic,\nespecially on the sudden appearance of certain claims and arguments\naround or against them.  For example, when it is declared that trees\nof depth larger than 1 have some distinctive feature from MLPs of any\nnumber of layers, what assumption is being argued against?  Did\nsomeone conjecture that they are the same, and why was there such a conjecture?\n\nThe paper is not readable due to its lack of clarity in the basic\ndefinitions, a severe lack of connections in the logic, heavy\nreliance on external references, and a lack of explanation of the\nsignificance of the results. \n", "summary_of_the_paper": "The paper presents an extension of a neural network analytic tool\ncalled Neural Tangent Kernels to its use for decision trees and\nforests.  The focus is a previously proposed notion of soft trees.\nA few analytical results are presented about the properties of the\nextended notion, called Tree Neural Tangent Kernel, such as the\nexistence of some limiting deterministic form, how alternative\nprobabilistic tree ensembles would have their kernels converging to\nthis deterministic form, that this limiting kernel is positive\ndefinite, and that the kernel remains stable during training,\nequivalence of the kernels for one-level tree ensembles to those of two-layer perceptrons, etc.\nSome support for the analytical claims is provided by simulation experiments.\n", "summary_of_the_review": "The paper may have some new results but is better fitting for a forum for theoretical analysis and\npreferably a journal where more space is available to fully elaborate on\nthe detailed definitions, assumptions, claims and their implications.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MWujIGVOCuF", "reviewer": "Reviewer_yf2B", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper proposed a new method called TNTK to ensemble infinite soft trees. It provides non-trivial theoretical studies of the TNTK. Their numerical experiments support their theoretical results. This paper is well-written and clearly organized. \n\nCompared with MLP-induced NTK and RBF, one of the advantages of TNTK will be the low computational complexity. It would be better to provide a detailed complexity analysis (e.g., memory cost, training time complexity, and inference time complexity) of the proposed TNTK. \n", "summary_of_the_paper": "This paper proposed the Tree Neural Tangent Kernel (TNTK) for tree ensembles. The proposed idea extends the NTK concept to tree ensemble models and enables ensembles of infinite soft trees. This paper provides theoretical studies to analyze the properties of the proposed TNTK. They also provide comprehensive experimental results to show the effectiveness of the proposed method. ", "summary_of_the_review": "Please refer to my main review.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "GijynEU2Ioa", "reviewer": "Reviewer_3ieY", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 authors define the TNTK and prove a number of properties which one would like to know about the kernel. \nSuch as positive definiteness, and change during training.\nThe kernel shares some of the properties of the NTK, indicating that the TNTK can be used to understand training behavior. This is not surprising, considering that soft trees can be viewed as a neural network. This work offers some novelty in computing the kernel in the limit of infinite size of the ensemble, whereas naive application of NTK to large ensembles would be computationally intractible. \n\nThe depth degeneracy property is a result with practical utility. The TNTK framework offers a clear understanding of this phenomenon and can help select model hyperparameters.\n\nIt is often unclear how to initialize soft-tree ensembles. Many works use classical greedy algorithms to initialize, while others fix the structure of the tree and randomly initialize the weights. It would be nice if the authors can remark whether TNTK can shed some light on initialization strategies.", "summary_of_the_paper": "The authors derive a neural tangent kernel for soft trees, and prove several properties of the kernel. These include the stability of the kernel in the large ensemble limit, applicability to oblivious tree ensembles, degeneracy with large tree depth, and comparison to NTK. They then evaluate the utility of the kernel on 90 UCI classification data sets using a kernel regression classifier. ", "summary_of_the_review": "This paper represents the development of an important tool for understanding tree ensembles. ", "strength_and_weaknesses": "", "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": "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:

Meta-review: The paper investigates the neural tangent kernel NTK of infinitely wide ensembles of soft trees having a particular 
soft decision functions in their internal nodes. A closed form of the NTK is presented as well as a result bounding
the changes of the NTK during training. Implications for practical training procedures are briefly discussed and 
some experiments are also reported. 

The review and discussion phase were difficult with two rather uninformative but positive reviews and a negative 
but detailed review. The latter had, however, some serious flaws. For these reasons I carefully read the paper on my own,
too. In turned out that the criticized flaws in the presentation mentioned by the negative reviewer are baseless as long as 
one already knows what an NTK is. Given the title of the paper and the history of NTKs, I personally think that 
such knowledge can and should be assumed. 
Overall, I find the paper be actually very well written. The main issue I see is that the results are not overwhelmingly 
surprising. Nonetheless, this is a solid contribution, which deserves to be published.
Decision: Accept (Poster)