A NEURAL TANGENT KERNEL PERSPECTIVE OF INFINITE TREE ENSEMBLES
Year: 2021

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 whole splitting operation is formulated in a differentiable form. Although ensembles of such soft trees have been increasingly used in recent years, little theoretical work has been done for understanding their behavior. In this paper, by considering an ensemble of infinite soft trees, we introduce and study the Tree Neural Tangent Kernel (TNTK), which provides new insights into the behavior of the infinite ensemble of soft trees. Using the TNTK, we succeed in theoretically finding 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.

heading: 1 INTRODUCTION
text: Tree ensembles and neural networks are powerful machine learning models used in various realworld applications. A soft tree ensemble is one of the variants of tree ensemble models that inherits characteristics of neural networks. Instead of using a greedy method (Quinlan, 1986; Breiman et al., 1984) for searching 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 to have high empirical performance (Kontschieder et al., 2015; Popov et al., 2020; Hazimeh et al., 2020), especially for tabular datasets. Besides accuracy, there are many additional reasons why one should formulate trees in a soft manner. For example, unlike hard decision trees, the model can be updated sequentially (Ke et al., 2019) and trained in combination with pre-training (Arik & Pfister, 2019), resulting in favorable characteristics 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., 2021; 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 can be interpreted as a special case of Mixture-of-Experts (Jordan & Jacobs, 1993; Shazeer et al., 2017; Lepikhin et al., 2021), a technique for balancing computational complexity and prediction performance.
Although various techniques have been proposed to train trees, the theoretical validity of such techniques is not well understood at 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; Hazimeh et al., 2020), and the use of overparameterization (Belkin et al., 2019; Karthikeyan et al., 2021). To better understand the training of tree ensemble models, we focus on the Neural Tangent Kernel (NTK) (Jacot et 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 performed 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 et al., 2021). The NTK theory is often used in the context of overparameterization of neural networks. In response to recent trends, overparameterization is also a subject of interest for tree ensembles (Belkin et al., 2019; Karthikeyan et al., 2021). Although a number of findings have been obtained using the NTK, they are mainly for typical neural networks, and it is still not obvious how to apply the NTK theory to the tree models.
In this paper, by considering the limit of infinitely many trees, we introduce and study the neural tangent 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 complete binary trees with arbitrary depth. (Section 4.1.1). We also prove that the TNTK remains constant during the training of infinite soft trees. This property allows us to analyze the behavior by kernel regression and discuss global convergence of 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 as CatBoost (Prokhorenkova et al., 2018) 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 4.2.1).
• Nonlinearity 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 a 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 a 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 so 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 on average, the infinite tree ensemble performs better than the infinite width MLP in more than 30% of the datasets. We also showed that the TNTK is superior to the MLP-induced NTK in computational speed (Section 5).

heading: 2 BACKGROUND AND RELATED WORK
text: Our main focus in this paper is the soft tree and the neural tangent kernel. We briefly introduce and review them.

heading: 2.1 SOFT TREE
text: Based on Kontschieder et al. (2015), we formulate a regression by soft trees. Figure 1 is a schematic image of an ensemble of M soft trees. We define a data matrix x ∈ RN0×N for N training
samples {x1, . . . ,xN} with N0 features and define tree-wise parameter matrices for internal nodes wm ∈ RN0×N and leaf nodes πm ∈ R1×L for each tree m ∈ [M ] = {1, . . . ,M} as
x = ( | . . . | x1 . . . xN | . . . | ) , wm = ( | . . . | wm,1 . . . wm,N | . . . | ) , πm = (πm,1, . . . , πm,L) ,
where internal nodes (blue nodes in Figure 1) and leaf nodes (green nodes in Figure 1) are indexed from 1 to N and 1 to L, respectively. N and L may change across trees in general, while we assume that they are always fixed for simplicity throughout the paper. We also write horizontal concatenation of (column) vectors as x = (x1, . . . ,xN ) ∈ RN0×N and wm = (wm,1, . . . ,wm,N ) ∈ RN0×N . Unlike hard decision trees, we consider a model in which every single leaf node ` ∈ [L] = {1, . . . ,L} of a tree m holds the probability that data will reach to it. Therefore, splitting operation at an intermediate node n ∈ [N ] = {1, . . . ,N} 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: ` ↙ n (resp. n ↘ `), which is true if a leaf ` belongs to the left (resp. right) subtree of a node n and false otherwise. We can now exploit µm,`(xi,wm) : RN0 ×RN0×N → [0, 1], a function that returns the probability that a sample xi will reach a leaf ` of the tree m, as follows:
µm,`(xi,wm) = N∏ n=1 gm,n(xi,wm,n) 1`↙n (1− gm,n(xi,wm,n))1n↘` , (1)
where 1Q is an indicator function conditioned on the argument Q, i.e., 1true = 1 and 1false = 0, and gm,n : RN0×RN0 → [0, 1] is a decision function at each internal node n of a treem. To approximate decision tree splitting, the output of the decision function gm,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 an explicit form of the decision function gm,n in Equation (5) in the next section.
The prediction for each xi from a tree m with nodes parameterized by wm and πm is given by
fm(xi,wm,πm) = L∑ `=1 πm,`µm,`(xi,wm), (2)
where fm : RN0 × RN0×N × R1×L → R, and πm,` denotes the response of a leaf ` of the tree m. This formulation means that the prediction output is the average of the leaf values πm,` weighted by µm,`(xi,wm), probability of assigning the sample xi to the leaf `. If µm,`(xi,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 πm are updated during training with a gradient method.
While many empirical successes have been reported, theoretical analysis for soft tree ensemble models has not been sufficiently developed.

heading: 2.2 NEURAL TANGENT KERNEL
text: Given N samples x ∈ RN0×N , the NTK induced by any model architecture at a training time τ is formulated as a matrix Ĥ∗τ ∈ RN×N , in which each (i, j) ∈ [N ]× [N ] component is defined as
[Ĥ∗τ ]ij := Θ̂ ∗ τ (xi,xj) :=
〈 ∂farbitrary (xi,θτ )
∂θτ , ∂farbitrary (xj ,θτ ) ∂θτ
〉 , (3)
where 〈·, ·〉 denotes the inner product and θτ ∈ RP is a concatenated vector of all the P trainable model parameters at τ . An asterisk “ ∗ ” indicates that the model is arbitrary. The model function farbitrary : RN0 × RP → R used in Equation (3) is expected to be applicable to a variety of model structures. For the soft tree ensembles introduced in Section 2.1, the NTK is formulated as∑M m=1 ∑N n=1 〈 ∂f(xi,w,π) ∂wm,n , ∂f(xj ,w,π) ∂wm,n 〉 + ∑M m=1 ∑L `=1 〈 ∂f(xi,w,π) ∂πm,` , ∂f(xj ,w,π) ∂πm,` 〉 .
In the limit of infinite width with a proper parameter scaling, a variety of properties have been discovered from the NTK induced by the MLP. For example, Jacot et al. (2018) showed the convergence of Θ̂MLP0 (xi,xj), which can vary with respect to parameters, to the unique limiting kernel Θ(xi,xj)
at initialization in probability. Moreover, they also showed that the limiting kernel does not change during training in probability:
lim width→∞ Θ̂MLPτ (xi,xj) = limwidth→∞ Θ̂MLP0 (xi,xj) =: Θ MLP(xi,xj). (4)
This property helps in the analytical understanding of the model behavior. For example, with the squared loss and infinitesimal step size with learning rate η, the training dynamics of gradient flow in function space coincides with kernel ridge-less regression with the limiting NTK. Such a property gives us a data-dependent 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 et 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 as MLP and ResNet, and the NTK theory has not been applied to tree models yet. The NTK theory is often used in the context of overparameterization, a subject of interest not only for the neural networks but also for the tree models (Belkin et al., 2019; Karthikeyan et al., 2021; Tang et al., 2018).
3 SETUP
We train model parametersw and π to minimize the squared loss using the gradient method, where w = (w1, . . . ,wm) and π = (π1, . . . ,π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:
gm,n(xi,wm,n) = σ ( w>m,nxi ) := 1
2 erf ( αw>m,nxi ) + 1 2 , (5)
where erf(p) = 2√ π ∫ p 0 e−t 2
dt for p ∈ R. This scaled error function approximates 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 x, we do not consider the bias for simplicity. The scaling factor α is introduced by Frosst &
Hinton (2017) to avoid too soft splitting. Figure 2 shows that the decision function becomes harder as α increases (from blue to red), and in the limit α→∞ it coincides with the hard splitting used in typical decision trees.
When aggregating the output of multiple trees, we divide the sum of the tree outputs by the square root of the number of trees
f(xi,w,π) = 1√ M M∑ m=1 fm(xi,wm,πm). (6)
This 1/ √ M 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,n and πm,` with zero-mean i.i.d. Gaussians with unit variances. We refer such a parameterization as NTK initialization. In this paper, we consider a model such that allM trees have the same complete binary tree structure, a common setting for soft tree ensembles (Popov et al., 2020; Kontschieder et al., 2015; Hazimeh et al., 2020).

heading: 4 THEORETICAL RESULTS

heading: 4.1 BASIC PROPERTIES OF THE TNTK
text: We call the NTK in Equation (3) induced by the soft tree ensembles the TNTK and denote by Θ̂
(d) 0 (xi,xj) the TNTK at initialization induced by the ensemble of trees with depth d. In this section,
Ĥ0 and theH := limM→∞ Ĥ0 for 50 random unit vectors of length N0 = 5. The dashed lines are plotted only for showing the slope. The error-bars show the standard deviations of 10 executions.
we show the properties of the TNTK that are important for understanding the training behavior of the soft tree ensembles.

heading: 4.1.1 TNTK FOR INFINITE TREE ENSEMBLES
text: First, we show the formula of the TNTK at initialization, which converges when considering the limit of infinite trees (M →∞). Theorem 1. Let u ∈ RN0×1 be any column vector sampled from zero-mean i.i.d. Gaussians with unit variance. The TNTK for an ensemble of soft complete binary trees with tree depth d converges in probability to the following deterministic kernel as M →∞,
Θ(d)(xi,xj) := lim M→∞ Θ̂ (d) 0 (xi,xj)
= d(2d)Σ(xi,xj)(T (xi,xj))d−1Ṫ (xi,xj)︸ ︷︷ ︸ contribution from inner nodes + (2T (xi,xj))d︸ ︷︷ ︸ contribution from leaves , (7)
where Σ(xi,xj) := x>i xj , T (xi,xj) := E[σ(u>xi)σ(u>xj)], and Ṫ (xi,xj) := E[σ̇(u>xi)σ̇(u>xj)]. Moreover, T (xi,xj) and Ṫ (xi,xj) are analytically obtained in the closedform as
T (xi,xj) = 1
2π arcsin
( α2Σ(xi,xj)√
(α2Σ(xi,xi) + 0.5)(α2Σ(xj ,xj) + 0.5)
) + 1
4 , (8)
Ṫ (xi,xj) = α2
π 1√ (1 + 2α2Σ(xi,xi)) (1 + 2α2Σ(xj ,xj))−4α4Σ(xi,xj)2 . (9)
The dot used in σ̇(u>xi) means the first derivative: αe−(αu >xi) 2 / √ π, and E[·] means the expectation. The scalar π in Equation (8) and Equation (9) 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 a tree ensemble like the width of the hidden layer in MLP, although the MLP and the soft tree ensemble are apparently different models. Due to the space limit, detailed proofs are given in the supplementary material.
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 (7). The kernel values induced by an 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 applications1. It is therefore reasonable to analyze soft tree ensembles via the TNTK.
1For example, Popov et al. (2020) uses 2048 trees.
By comparing Equation (7) and the limiting NTK induced by a two-layer perceptron (shown in the supplementary material), we can immediately derive the following when the tree depth is 1. Corollary 1. If the splitting function at the tree internal node is the same as the activation function of the neural network, the limiting TNTK obtained from a soft tree ensemble of depth 1 is equivalent to the limiting NTK generated by a two-layer perceptron up to 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 in the supplementary material) and the limiting TNTK do not match. It implies that the hierarchical splitting structure is a distinctive feature of soft tree ensembles.

heading: 4.1.2 POSITIVE DEFINITENESS OF THE LIMITING TNTK
text: Since the loss surface of a large model is expected to be highly non-convex, understanding the good empirical trainability of overparameterized models is still 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 et al., 2019a; Jacot et al., 2018). Jacot et al. (2018) have shown that the conditions ‖xi‖2= 1 for all i ∈ [N ] and xi 6= xj (i 6= j) 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 (7)) is different from that of typical neural networks such as an MLP, it is not obvious whether or not the limiting TNTK is positive definite.
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 ‖xi‖2= 1 for all i ∈ [N ] and xi 6= xj (i 6= j).
The proof is in the supplementary material. Similar to the discussion for the MLP (Du et al., 2019a; Jacot et al., 2018), if the limiting TNTK is constant during training, the positive definiteness of the limiting TNTK at initialization indicates that training of the infinite trees with a gradient method can converge to the global minimum. We show the constantness of the limiting TNTK during training in the next section.

heading: 4.1.3 CHANGE OF THE TNTK DURING TRAINING
text: We prove that the TNTK hardly changes from its initial value during training when considering an ensemble of infinite trees with finite α (used in Equation (5)). Theorem 2. Let λmin and λmax 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 a positive finite scaling factor α trained under gradient flow with a learning rate η < 2/(λmin + λmax), we have with high probability
sup ∣∣∣Θ̂(d)τ (xi,xj)− Θ̂(d)0 (xi,xj)∣∣∣ = O( 1√
M
) . (10)
The complete proof is 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 α, 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 et al., 2019), 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 behavior using the TNTK is not straightforward.

heading: 4.2 IMPLICATIONS FOR PRACTICAL TECHNIQUES
text: In this section, from the viewpoint of the TNTK, we discuss the training techniques that have been used in practice.

heading: 4.2.1 INFLUENCE OF THE OBLIVIOUS TREE STRUCTURE
text: An oblivious tree 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 O(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 complete binary tree 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 →∞).
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.

heading: 4.2.2 EFFECT OF THE DECISION FUNCTION MODIFICATION
text: Practically, based on the commonly used sigmoid function, a variety of functions have been proposed for the splitting operation. By considering a large scaling factor α in Equation (5), we can envisage situations in which practically-used hard functions such as two-class sparsemax, σ(x) = sparsemax([x, 0]) (Martins & Astudillo, 2016), and two-class entmax, σ(x) = entmax([x, 0]) (Peters et al., 2019). Figure 6 shows α dependencies of TNTK parameters. Equation (7) means that the TNTK is formulated by multiplying T (xi,xj) and Ṫ (xi,xj) to the linear kernel Σ(xi,xj). On the one hand, when we look at T (xi,xj) and Ṫ (xi,xj) with small α, they are almost constant even for
different input inner products, resulting in the almost linear TNTK. On the other hand, we can see that the nonlinearity increases as α increases. When we look at Figure 2, the original sigmoid function corresponds to a scaled error function for α ∼ 0.5, which is almost the linear kernel. Although a 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; Popov et al., 2020; Hazimeh et al., 2020) can be interpreted as an escape from the linear kernel behavior.

heading: 4.2.3 DEGENERACY CAUSED BY DEEP TREES
text: As the depth increases, T (xi,xj) defined in Equation (8), which consists of the arcsine function, is multiplied multiple times to calculate the limiting TNTK in Equation (7). Therefore, when we increase the depth too much, the resulting TNTK exhibits degeneracy: its output values are almost the same with each other even though the input’s inner products are different. The rightmost panel of Figure 6 shows such degeneracy behavior. In terms of kernel regression, models using a kernel that gives almost the same inner product to all data except those that are quite close to each other are expected to have poor generalization performance. Such behavior is observed in our numerical experiments (Section 5). In practical applications, one does not usually use too deep soft or hard decision trees as too deep trees show poor performance (Luo et al., 2021), which is supported by the degeneracy of the TNTK.

heading: 5 NUMERICAL EXPERIMENTS
text: Setup We present our experimental results on 90 classification tasks in the UCI database (Dua & Graff, 2017), with less than 5000 data points as in Arora et al. (2020). We performed kernel regression using the limiting TNTK defined in Equation (7) with varying parameters, the tree depth (d) and the scaling (α) of the decision function. The limiting TNTK does not change during training for an infinite ensemble of soft trees (Theorem 2), hence predictions from that model are equivalent to kernel regression using the limiting TNTK (Jacot et al., 2018). For considering the ridge-less situation, regularization strength is set to be 1.0× 10−8, a very small constant. For a 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-induced NTK, we use ReLU for the activation function. We follow the procedures of Arora et al. (2020) and Fernández-Delgado et al. (2014): We report 4-fold 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 in the supplementary material.
Comparison to the MLP The left panel of Figure 7 shows the averaged performance as a function of the depth. Although the TNTK with properly tuned parameters tend to be better than those obtained with the RBF kernel, they are often inferior to the MLP-induced NTK. The results support the good performance of the MLP-induced NTK (Arora et al., 2020). However, it should be noted that when we look at each dataset one by one, the TNTK is superior to the MLP-induced NTK for more than 30%
of the dataset, as shown in Table 1. This is a 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 repsect to the depth of the model because of the recursive computation (Jacot et al., 2018), that of the TNTK does not depend on the depth as shown in Equation (7), resulting in much faster computation than the MLP-induced NTK when the depth increases, illustrated 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) proposes 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 we increase the tree depth, we observe an improvement in performance at the beginning. After that, the performance gradually decreases. This behavior is consistent with the performance deterioration due to degeneracy (Section 4.2.3), similar to that reported for neural networks without skip-connection (Huang et al., 2020) shown with the dotted yellow line. The performance improvement by adjusting α in the decision function (Frosst & Hinton, 2017) is also observed. Performances with hard (α > 0.5) decision functions are always better than the sigmoid-like function (α = 0.5, as shown in Figure 2).

heading: 6 CONCLUSION
text: 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 of 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 our theoretical results. To date, the NTK theory has been mostly applied to neural networks, and our study is the first to apply it to the tree model. Therefore our study will be a milestone of further development of the NTK theory.

heading: 7 ETHICS STATEMENT
text: We believe that the TNTK’s theoretical analysis will not have a negative impact on society as our work does not directly lead to harmful applications.

heading: 8 REPRODUCIBILITY STATEMENT
text: Proofs of all theoretical results are given in the supplementary material. For the numerical experiments and figures, we share our reproducible source code in the supplementary material.

heading: A PROOF OF THEOREM 1
text: Proof. The model output from a certain depth tree ensemble f (d) can be written alternatively using an incremental formula as
f (d)(xi,w,π) = 1√ M M∑ m=1 ( σ ( w>m,txi ) f (d−1)m ( xi,w (l) m ,π (l) m ) + ( 1− σ ( w>m,txi )) f (d−1)m ( xi,w (r) m ,π (r) m )) , (A.1)
where indices (l) and (r) used with model parameters wm and πm mean the parameters at the (l)eft subtree and the (r)ight subtree, respectively, and t used in wm,t denotes the node at (t)op of the tree. For example, for trees of depth 3 as shown in Figure 1, w(l)m = (wm,2,wm,4,wm,5), w (r) m = (wm,3,wm,6,wm,7), and wm,t = wm,1.
We prove the theorem by induction. When d = 1,
f (1)(xi,w,π) = 1√ M M∑ m=1 ( σ(w>m,1xi)πm,1 + (1− σ(w>m,1xi))πm,2 ) . (A.2)
Derivatives are ∂f (1)(xi,w,π)
∂wm,1 = 1√ M
(πm,1 − πm,2)xiσ̇ ( w>m,1xi ) , (A.3)
∂f (1)(xi,w,π)
∂πm,1 = 1√ M σ ( w>m,1xi ) , (A.4)
∂f (1)(xi,w,π)
∂πm,2 = − 1√ M
( 1− σ ( w>m,1xi )) , (A.5)
Therefore, since there is only one internal node per a single tree, from the definition of the NTK, the TNTK is obtained as
Θ̂(1) (xi,xj) = M∑ m=1
(〈 ∂f (xi,w,π)
∂wm,1 , ∂f (xj ,w,π) ∂wm,1
〉
+
〈 ∂f (xi,w,π)
∂πm,1 , ∂f (xj ,w,π) ∂πm,1
〉 + 〈 ∂f (xi,w,π)
∂πm,2 , ∂f (xj ,w,π) ∂πm,2
〉)
= 1
M M∑ m=1 ( (πm,1 − πm,2)2 x>i xj σ̇(w>m,1xi)σ̇(w>m,1xj) + 2σ(w>m,1xi)σ(w>m,1xj) ) .
(A.6)
Since we are considering the infinite number of trees (M →∞), the average in Equation (A.6) can be replaced by the expected value by applying the law of the large numbers:
Θ(1) (xi,xj) = Em [( (πm,1 − πm,2)2 x>i xj σ̇(w>m,1xi)σ̇(w>m,1xj)
+ 2σ(w>m,1xi)σ(w > m,1xj) )] = 2(Σ(xi,xj)Ṫ (xi,xj) + T (xi,xj)), (A.7)
which is consistent with Equation (7). Here, Em [ (πm,1 − πm,2)2 ] = 2 because the variance of πm,`
is 1.0, and wm,1 corresponds to u in Theorem 1.
For d > 1, we divide the TNTK into four components: Θ(d) (xi,xj) = Θ (d),(t) (xi,xj) + Θ (d),(l) (xi,xj) + Θ (d),(r) (xi,xj) + Θ (d),(b) (xi,xj) ,
where the indices (t), (l) and (r) mean the parameters of the (t)op 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),(t) (xi,xj) = 2Σ(xi,xj)Ṫ (xi,xj), (A.8) Θ(1),(l) (xi,xj) = 0, (A.9)
Θ(1),(r) (xi,xj) = 0, (A.10)
Θ(1),(b) (xi,xj) = 2T (xi,xj). (A.11)
For each component, we show the following lemmas:
Lemma 1. Θ(d+1),(t) (xi,xj) = 2T (xi,xj)Θ(d),(t) (xi,xj) (A.12) Lemma 2. Θ(d+1),(l) (xi,xj) + Θ (d+1),(r) (xi,xj)
= 2T (xi,xj)(Θ(d),(t) (xi,xj) + Θ(d),(l) (xi,xj) + Θ(d),(r) (xi,xj)) (A.13) Lemma 3.
Θ(d+1),(b) (xi,xj) = 2T (xi,xj)Θ(d),(b) (xi,xj) (A.14)
Combining them, we can derive Equation (7).

heading: A.1 PROOF OF LEMMA 1
text: Proof. An incremental formula for the model output with a certain depth tree ensemble is
f (d)(xi,w,π) = 1√ M M∑ m=1 ( σ ( w>m,txi ) f (d−1)m ( xi,w (l) m ,π (l) m ) + ( 1− σ ( w>m,txi )) f (d−1)m ( xi,w (r) m ,π (r) m )) , (A.15)
where t used in wm,t implies the node at the top of the tree. With Equation (A.15), ∂f (d+1)(xi,w,π)
∂wm,t = xiσ̇(w
> m,txi) ( f (d)m ( xi,w (l) m ,π (l) m ) − f (d)m ( xi,w (r) m ,π (r) m )) , (A.16)
Θ̂(d+1),(t)(xi,xj) = 1
M M∑ m=1 x>i xj σ̇(w > m,txi)σ̇(w > m,txj) ( f (d)m ( xi,w (l) m ,π (l) m ) f (d)m ( xj ,w (l) m ,π (l) m ) − f (d)m ( xi,w (l) m ,π (l) m ) f (d)m ( xj ,w (r) m ,π (r) m
) − f (d)m ( xi,w (r) m ,π (r) m ) f (d)m ( xj ,w (l) m ,π (l) m
) + f (d)m ( xi,w (r) m ,π (r) m ) f (d)m ( xj ,w (r) m ,π (r) m )) , (A.17)
Since f (d)m ( xi,w (r) m ,π (r) m ) and f (d)m ( xj ,w (l) m ,π (l) m ) are independent to each other
and have zero-mean Gaussian distribution because of the initialization of πm with zero-mean i.i.d Gaussians2, E [ f (d) m ( xi,w (l) m ,π (l) m ) f (d) m ( xj ,w (r) m ,π (r) m )] and
E [ f (d) m ( xi,w (r) m ,π (r) m ) f (d) m ( xj ,w (l) m ,π (l) m )] are zero. Therefore, considering the infinite
number of trees (M →∞),
Θ(d+1),(t)(xi,xj) = x > i xj Ṫ (xi,xj)Em [ f (d)m ( xi,w (l) m ,π (l) m ) f (d)m ( xj ,w (l) m ,π (l) m ) + f (d)m ( xi,w (r) m ,π (r) m ) f (d)m ( xj ,w (r) m ,π (r) m )] (A.18)
From Equation (A.18), what we need to prove is Em [ f (d) m (xi,wm,πm)f (d) m (xj ,wm,πm) ] =
(2T (xi,xj))d. We prove it by induction. In the base case with d = 1, Em [ f (1)m (xi,wm,πm)f (1) m (xj ,wm,πm) ] =Em [( σ(w>m,1xi)πm,1 + ( 1− σ(w>m,1xi) ) πm,2 )( σ(w>m,1xj)πm,1 + ( 1− σ(w>m,1xj) ) πm,2 )]
=Em (πm,1 − πm,2)2︸ ︷︷ ︸ →2 σ(w>m,1xi)σ(w > m,1xj)
+πm,1πm,2︸ ︷︷ ︸ →0 (σ(w>m,1xi) + σ(w > m,1xj))− π2m,2(σ(w>m,1xi) + σ(w>m,1xj)− 1︸ ︷︷ ︸
→0
)  =2T (xi,xj) , (A.19) where we use the property
E [σ(v)] = 0.5 (A.20) for any v generated from a zero-mean Gaussian distribution. The subscript arrows (→) show what the expected value will be.
Next, when the depth is d+ 1, Em [ f (d+1)m (xi,wm,πm)f (d+1) m (xj ,wm,πm) ] =Em [( σ(w>m,txi)f (d) m ( xi,w (l) m ,π (l) m ) + ( 1− σ(w>m,txi) ) f (d)m ( xi,w (r) m ,π (r) m
)) ( σ(w>m,txj)f (d) m ( xj ,w (l) m ,π (l) m ) + ( 1− σ(w>m,txj) ) f (d)m ( xj ,w (r) m ,π (r) m ))]
=Em  (f (d)m (xi,w(l)m ,π(l)m )− f (d)m (xi,w(r)m ,π(r)m ))σ(w>m,txi)︸ ︷︷ ︸
(A)
+ f (d)m ( xi,w (r) m ,π (r) m ) ︸ ︷︷ ︸
(B)  (f (d)m (xj ,w(l)m ,π(l)m )− f (d)m (xj ,w(r)m ,π(r)m ))σ(w>m,txj)︸ ︷︷ ︸
(C)
+ f (d)m ( xj ,w (r) m ,π (r) m ) ︸ ︷︷ ︸
(D)
  ,
(A.21)
where the last equality sign is just a simplification to separate components (A), (B), (C), and (D). Since f (d)m (xi,w (r) m ,π (r) m ) and f (d) m (xj ,w (l) m ,π (l) m ) are independent to each other and have zero-mean
2This holds due to the fact that model output is a weighted average of πm,`.
i.i.d Gaussian distribution, we obtain Em [(A)× (C)] = T (xi,xj)Em [ f (d)m ( xi,w (l) m ,π (l) m ) f (d)m ( xj ,w (l) m ,π (l) m ) +f (d)m ( xi,w (r) m ,π (r) m ) f (d)m ( xj ,w (r) m ,π (r) m )] , (A.22)
Em [(B)× (C)] = −0.5 Em [ f (d)m ( xi,w (r) m ,π (r) m ) f (d)m ( xj ,w (r) m ,π (r) m )] , (A.23)
Em [(A)× (D)] = −0.5 Em [ f (d)m ( xi,w (r) m ,π (r) m ) f (d)m ( xj ,w (r) m ,π (r) m )] , (A.24)
Em [(B)× (D)] = Em [ f (d)m ( xi,w (r) m ,π (r) m ) f (d)m ( xj ,w (r) m ,π (r) m )] . (A.25)
Equation (A.23), Equation (A.24), and Equation (A.25) cancel each other out. Therefore, we obtain Em [ f (d+1)m (xi,wm,πm)f (d+1) m (xj ,wm,πm) ] =2T (xi,xj)Em [ f (d)m (xi,wm,πm)f (d) m (xj ,wm,πm) ] . (A.26)
By induction hypothesis and Equation (A.19), we have Em [ f (d) m (xi,wm,πm)f (d) m (xj ,wm,πm) ] = (2T (xi,xj))d. Therefore, the original lemma also
follows.

heading: A.2 PROOF OF LEMMA 2
text: Proof. When the depth is d + 1, the derivatives of the parameters in the left subtree and the right subtree are
∂f (d+1) (xi,w,π)
∂wm,l = σ(w>m,txi)
∂f (d) m ( xi,w (l) m ,π (l) m ) ∂wm,l , (A.27)
∂f (d+1) (xi,w,π) ∂wm,r = ( 1− σ(w>m,txi) ) ∂f (d)m (xi,w(r)m ,π(r)m ) ∂wm,r , (A.28)
where l and r used inwm,l andwm,r implies the node at the left subtree and right subtree, respectively. Therefore, the limiting TNTK for the left subtree is
Θ(d+1),(l) (xi,xj) = T (xi,xj)(Θ(d),(t) (xi,xj) + Θ(d),(l) (xi,xj) + Θ(d),(r) (xi,xj)). (A.29) Similarly, for the right subtree, since
E[(1− σ(u>xi)(1− σ(u>xj)] = E 1− σ(u>xi)︸ ︷︷ ︸ →0.5 −σ(u>xj)︸ ︷︷ ︸ →0.5 +σ(u>xi)σ(u >xj)  = E[σ(u>xi)σ(u>xj)], (A.30)
we can also derive Θ(d+1),(r) (xi,xj) = T (xi,xj)(Θ(d),(t) (xi,xj) + Θ(d),(l) (xi,xj) + Θ(d),(r) (xi,xj)). (A.31)
Finally, we obtain the following by combining with Equation (A.29) and Equation (A.31),
Θ(d+1),(l) (xi,xj) + Θ (d+1),(r) (xi,xj)
= 2T (xi,xj) (Θ(d),(t) (xi,xj) + Θ(d),(l) (xi,xj) + Θ(d),(r) (xi,xj)). (A.32)

heading: A.3 PROOF OF LEMMA 3
text: Proof. With Equation (1) and Equation (6), ∂f (xi,w,π)
∂πm,` = 1√ M µm,`(xi,wm)
= 1√ M N∏ n=1 σ ( w>m,nxi )1`↙n ( 1− σ ( w>m,nxi ))1n↘` . (A.33)
When we focus on a leaf `, for a tree with depth of d, 1n↘` or 1`↙n equals to 1 d times. Therefore, by Equation (A.30), we can say that there is a T (xi,xj)d contribution to the limiting kernel Θ(d),(b) (xi,xj) per leaf index ` ∈ [L]. Since there are 2d leaf indices in the complete binary tree,
Θ(d+1),(b) (xi,xj) = (2T (xi,xj))d. (A.34)
In other words, since the number of leaves doubles with each additional depth, we can say
Θ(d+1),(b) (xi,xj) = 2T (xi,xj)Θ(d),(b) (xi,xj) . (A.35)

heading: A.4 CLOSED-FORM FORMULA FOR THE SCALED ERROR FUNCTION
text: Since we are using the scaled error function as a decision function defined as gm,n(wm,n,xi) = σ ( w>m,nxi ) = 1
2 erf ( αw>m,nxi ) + 1 2 , (A.36)
T and Ṫ in Theorem 1 can be calculated analytically. Closed-form solutions for the error function (Williams, 1996; Lee et al., 2019) are known to be
Terf(xi,xj) := E[erf(u>xi) erf(u>xj)] = 2
π arcsin
( Σ(xi,xj)√
(Σ(xi,xi) + 0.5)(Σ(xj ,xj) + 0.5)
) ,
(A.37)
Ṫerf(xi,xj) := E[ ˙erf(u>xi) ˙erf(u>xj)] = 4
π 1√ (1 + 2Σ(xi,xi)) (1 + 2Σ(xj ,xj))− 4Σ(xi,xj)2 .
(A.38)
Using the above equations, we can calculate T and Ṫ with the scaled error function as T (xi,xj) = E [ 1
4 erf(αu>xi) erf(αu >xj)
] + E [ 1
4 erf(αu>xi) +
1 4 erf(αu>xj)
] + 1
4
= 1 4 E [ erf(αu>xi) erf(αu >xj) ] + 1 4
= 1
2π arcsin
( α2Σ(xi,xj)√
(α2Σ(xi,xi) + 0.5)(α2Σ(xj ,xj) + 0.5)
) + 1
4 , (A.39)
Ṫ (xi,xj) = α2 4 E [ ˙erf(αu>xi) ˙erf(αu >xj) ] = α2
π 1√ (1 + 2α2Σ(xi,xi)) (1 + 2α2Σ(xj ,xj))− 4α4Σ(xi,xj)2 . (A.40)

heading: B NEURAL TANGENT KERNEL FOR MULTI-LAYER PERCEPTRON

heading: B.1 EQUIVALENCE BETWEEN THE TWO-LAYER PERCEPTRON AND TREES OF DEPTH 1
text: By using the same symbols used in soft trees (Section 2.1) to make it easier to see the correspondences, we consider a two-layer perceptron as
fMLP (2)(xi,w,a) = 1√ M M∑ m=1 amσ ( w>mxi ) , (B.1)
where we use M as the number of the hidden layer nodes, σ as a nonlinear activation function, and w = (w1, . . . ,wm) ∈ RN0×M and a = (a1, . . . , am) ∈ R1×M as parameters at the first and second
layers initialized by zero-mean Gaussians with unit variances. Since
∂fMLP (2)(xi,w,a)
∂wm = 1√ M amxiσ̇
( w>mxi ) , (B.2)
∂fMLP (2)(xi,w,a)
∂am = 1√ M σ ( w>mxi ) , (B.3)
we have
Θ̂MLP (2)(xi,xj) = 1
M M∑ m=1 a2mx>i xj σ̇ (w>mxi) σ̇ (w>mxj)︸ ︷︷ ︸ contribution from the first layer + σ ( w>mxi ) σ ( w>mxj )︸ ︷︷ ︸ contribution from the second layer  . (B.4)
Considering the infinite width limit (M →∞), we have
ΘMLP (2)(xi,xj) = Σ(xi,xj)Ṫ (xi,xj) + T (xi,xj), (B.5)
which is the same as the limiting TNTK shown in Equation (7) with d = 1 up to constant multiple.

heading: B.2 FORMULA FOR THE MLP-INDUCED NTK
text: Based on Arora et al. (2019), we define the L-hidden-layer perceptron3 as
fMLP (L)(xi,W ) = W (L+1) · 1√
ML σ
( W (L) · 1√
ML−1 σ
( W (L−1) . . .
1√ M1
σ ( W (1)xi ))) ,
(B.6)
where W (1) ∈ RM1×N0 , W (h) ∈ RMh×Mh−1 , and W (L+1) ∈ R1×ML are trainable parameters. We initialize all the weights W = ( W (1), . . . ,W (L+1) ) to values independently drawn from the standard normal distribution. Considering the limit of the infinite width M1,M2, . . . ,ML →∞, the formula for the limiting NTK of L-hidden-layer MLP is known to be
ΘMLP(L) (xi,xj) = L+1∑ h=1
( Σ(h−1) (xi,xj) ·
L+1∏ h′=h Σ̇(h ′) (xi,xj)
) , (B.7)
where
Σ(0) (xi,xj) := x > i xj , (B.8)
Λ(h) (xi,xj) :=
( Σ(h−1)(xi,xi) Σ
(h−1) (xi,xj) Σ(h−1) (xj ,xi) Σ (h−1) (xj ,xj)
) ∈ R2×2, (B.9)
Σ(h) (xi,xj) := Eu,v∼Normal(0,Λ(h)(xi,xj)) [σ(u)σ (v))] , (B.10)
Σ̇(h) (xi,xj) := Eu,v∼Normal(0,Λ(h)(xi,xj)) [σ̇(u)σ̇ (v))] . (B.11)
We let Σ̇(L+1) (xi,xj) := 1 for convenience. See Arora et al. (2019) for derivation. There is a correspondence between Σ(1) (xi,xj) and Σ (xi,xj) in Theorem 1, Σ(1) (xi,xj) and T (xi,xj) in Theorem 1, and Σ̇(1) (xi,xj) and Ṫ (xi,xj) in Theorem 1, respectively. Since the recursive calculation is needed in Equation (B.7), the computational cost increases as the layers get deeper. It can be seen that the effect of increasing depth is different from that of the limiting TNTK, in which the depth of 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.
3Note that the two-layer perceptron is the single-hidden-layer perceptron.

heading: C PROOF OF PROPOSITION 1
text: Proof. As shown in Section 4.1.1, there is a close correspondence between the soft tree ensemble of depth 1 and the two-layer perceptron. On the one hand, from Equation (A.7), the limiting TNTK induced by infinite trees with the depth of 1 is 2(Σ(xi,xj)Ṫ (xi,xj) + T (xi,xj)). On the other hand, if the activation function used in the two-layer perceptron is same as σ defined in Equation (5), the NTK induced by the infinite width two-layer MLP is Σ(xi,xj)Ṫ (xi,xj) + T (xi,xj) (Jacot et al., 2018; Lee et al., 2019). Hence these are exactly the same kernel up to constant multiple.
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 σ, for any input dimension N0, the NTK induced by the infinite width MLP is positive definite if ‖xi‖2= 1 for all i ∈ [N ] and xi 6= xj (i 6= j).
Note that σ defined in Equation (5) has the non-polynomial Lipschitz nonlinearity. Since the positive definite kernel multiplied by a constant is a positive definite kernel, it follows that the limiting TNTK Θ(1)(xi,xj) for the depth 1 is also positive definite.
As shown in Equation (C.1), as the trees get deeper, T (xi,xj) defined in Equation (8) is multiplied multiple times in the limiting TNTK:
Θ(d)(xi,xj) = d(2 d)Σ(xi,xj)(T (xi,xj))d−1Ṫ (xi,xj)︸ ︷︷ ︸
contribution from inner nodes
+ (2T (xi,xj))d︸ ︷︷ ︸ contribution from leaves
= 2(2T (xi,xj))d−1 (dΣ(xi,xj)Ṫ (xi,xj) + T (xi,xj))︸ ︷︷ ︸ NTK induced by two-layer perceptron (if d = 1) . (C.1)
The positive definiteness of T (xi,xj) has already been proven.
Lemma 5 (Jacot et al. (2018)). For a non-polynomial Lipschitz nonlinearity σ, for any input dimension N0, the T (xi,xj) := E[σ(u>xi)σ(u>xj)] defined in Theorem 1 is positive definite if ‖xi‖2= 1 for all i ∈ [N ] and xi 6= xj (i 6= j).
Note that dΣ(xi,xj)Ṫ (xi,xj) + T (xi,xj) for d ∈ 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)(xi,xj) holds under the same conditions as in MLP.

heading: D PROOF OF THEOREM 2
text: Proof. We use the following lemmas in the proof.
Lemma 6. Let a ∈ Rn be a random vector whose entries are independent standard normal random variables. For every v ≥ 0, with probability at least 1− 2ne(−v2n/2) we have:
‖a‖1≤ vn. (D.1)
Lemma 7. Let ai ∈ R≥0. We have
n∑ i=1 √ ai ≤ √ n √√√√ n∑ i=1 ai. (D.2)
In addition, our proof is based on the strategy used in Lee et al. (2019) which relies on the the local Lipschitzness of the model Jacobian at initialization J(x,θ), whose (i, j) entry is ∂f(xi,θ)∂θj where θj is a j-th component of θ:
Theorem 4 (Lee et al. (2019)). Assume that the limiting NTK induced by any model architecture is positive definite for input sets x such that minimum eigenvalue of the NTK λmin > 0. For models with
local Lipschitz Jacobian trained under gradient flow with a learning rate η < 2(λmin + λmax), we have with high probability:
sup ∣∣∣Θ̂∗τ (xi,xj)− Θ̂∗0 (xi,xj)∣∣∣ = O( 1√
M
) . (D.3)
It is not obvious whether or not the soft tree ensemble’s Jacobian is local Lipschitz. Therefore, we prove Lemma 8 to prove Theorem 2.
Lemma 8. For soft tree ensemble models with the NTK initialization and a positive finite scaling factor α, there is K > 0 such that for every C > 0, with high probability, the following holds:{
‖J(x,θ)‖F ≤ K ‖J(x,θ)− J(x, θ̃)‖F ≤ K‖θ − θ̃‖2 ,∀θ, θ̃ ∈ B (θ0, C) , (D.4)
where
B (θ0, C) := {θ : ‖θ − θ0‖2 < C} . (D.5)
By proving that the soft tree ensemble’s Jacobian under the NTK initialization is the local Lipschitz with high probability, we extend the Theorem 2 for the TNTK.

heading: D.1 PROOF OF LEMMA 6
text: Proof. By use of the Chebyshev’s inequality, for some constant c, we obtain
P (‖a‖1> c) ≤ E[eγ‖a‖1 ]/eγc = ( eγ 2/2(1 + erf(γ/ √ 2)) )n /eγc, (D.6)
where P means a probability. Since erf(γ/ √ 2) ≤ 1, when we use γ = c/n, we get
P (‖a‖1> c) ≤ 2ne(−c 2/2n). (D.7)
Lemma 6 can be obtained by assigning vn to c.
Figure 8 shows the right hand side of the Equation (D.7) with c = 5n. when n = 1, probability is 7.45× 10−6. As n becomes larger, the probability becomes even smaller.

heading: D.2 PROOF OF LEMMA 7
text: Proof. By use of Cauchy-Schwarz inequality, for p, q, x, y ∈ R≥0, we have p √ x+ q √ y ≤ √ (p2 + q2) (x+ y). (D.8)
With Equation (D.8), we prove the lemma by induction. In the base case, √ a1 + √ a2 ≤ √ 2 √ a1 + a2, (D.9)
which is consistent to the lemma. Next, when we assume √ a1 + · · ·+ √ ak ≤ √ k √ a1 + · · · ak, (D.10)
we have √ a1 + · · ·+ √ ak + √ ak+1 = ( √ a1 + · · ·+ √ ak) + √ ak+1
≤ √ k √ a1 + · · ·+ ak + √ ak+1 ≤ √ k + 1 √ a1 + · · ·+ ak + ak+1. (D.11)

heading: D.3 PROOF OF LEMMA 8
text: Proof. Consider the contribution of the leaf parameters at first: ∂f(xi,w,π)
∂πm,` = 1√ M µm,`(xi,wm). (D.12)
Next, contribution from the leaf parameters is
∂f(xi,w,π)
∂wm,n = 1√ M L∑ `=1 πm,` ∂µm,`(xi,wm) ∂wm,n
= 1√ M L∑ `=1 πm,`Sn,`(xi,wm)xiσ̇ ( w>m,nxi ) , (D.13)
where
Sn,`(x,wm) := ( N∏ n′=1 σ ( w>m,n′xi )1(`↙n′)&(n 6=n′) (1− σ (w>m,n′xi))1(n′↘`)&(n6=n′) ) (−1)1n↘` ,
(D.14) and & is a logical conjunction. For any real scalar p and q, the scaled error function σ defined in Equation (5) is bounded as follows:
0 ≤ σ(p) ≤ 1, |σ(p)− σ(q)| ≤ |p− q|, 0 ≤ σ̇(p) ≤ α, |σ̇(p)− σ̇(q)| ≤ α|p− q|. (D.15) Therefore, the absolute value of Sn,` does not exceed 1. With Equation (D.15), we can obtain∥∥∥∥∂µm,`(xi,wm)∂wm,n ∥∥∥∥ 2 = ∥∥Sn,`(xi,wm)xiσ̇ (w>m,nxi)∥∥2 ≤ α‖xi‖2 (D.16)
with high probability. Therefore, with Lemma 6, in probability,
‖J(x,θ)‖2F = N∑ i=1 ( ‖J(xi,w)‖2F+‖J(xi,π)‖2F ) = 1
M N∑ i=1 M∑ m=1  N∑ n=1 ∥∥∥∥∥ L∑ `=1 πm,` ∂µm,`(xi,wm) ∂wm,n ∥∥∥∥∥ 2
2
+ L∑ `=1 ( µm,`(xi,wm) 2 )
≤ 1 M N∑ i=1 M∑ m=1 ( N∑ n=1 v2L2α2‖xi‖22+ L∑ `=1 1 )
= N∑ i=1 L(v2Lα2N‖xi‖22+1). (D.17)
Next, we will consider the Jacobian difference. Since µm,`(xi,wm) is a multiple multiplication of the decision function, by use of∣∣∣∣∣ n∏ i=1 pi − n∏ i=1 qi ∣∣∣∣∣ ≤ n∑ i=1 |pi − qi| for |pi| , |qi| ≤ 1, (D.18)
we obtain
|µm,`(xi,wm)− µm,`(xi, w̃m)| = ∣∣∣∣∣ N∏ n=1 σ ( w>m,nxi )1`↙n ( 1− σ ( w>m,nxi ))1n↘` − N∏ n=1 σ ( w̃>m,nxi )1`↙n ( 1− σ ( w̃>m,nxi
))1n↘` ∣∣∣∣∣ ≤ N∑ n=1
∣∣∣σ (w>m,nxi)1`↙n (1− σ (w>m,nxi))1n↘` − σ ( w̃>m,nxi )1`↙n ( 1− σ ( w̃>m,nxi
))1n↘` ∣∣∣ ≤ N∑ n=1 |w>m,nxi − w̃>m,nxi|
≤ N∑ n=1 ‖xi‖2‖wm,n − w̃m,n‖2, (D.19)
where it should be noted that (`↙ n) & (n↘ `) must be false. Sn,` (xi,wm) − Sn,` (xi, w̃m) can be bound in the same way as Equation (D.19). Therefore, we also obtain∥∥∥∥∂µm,`(xi,wm)∂wm,n − ∂µm,`(xi, w̃m)∂w̃m,n ∥∥∥∥ 2 = ‖Sn,` (xi,wm)xiσ̇ ( w>m,nxi ) − Sn,` (xi, w̃m)xiσ̇ ( w̃>m,nxi ) ‖2
= ‖xi‖2|Sn,` (xi,wm) σ̇ ( w>m,nxi ) − Sn,` (xi, w̃m) σ̇ ( w̃>m,nxi ) |
≤ ‖xi‖2 ( |(Sn,` (xi,wm)− Sn,` (xi, w̃m))σ̇ ( w>m,nxi ) |
+ |(σ̇ ( w>m,nxi ) − σ̇ ( w̃>m,nxi ) )Sn,` (xi, w̃m) | ) ≤ ‖xi‖2 ( |α(Sn,` (xi,wm)− Sn,` (xi, w̃m))|
+ |(α(w>m,nxi − w̃>m,nxi))| )
≤ 2α‖xi‖22 N∑ n=1 ‖wm,n − w̃m,n‖2. (D.20)
To link Equation (D.19) and Equation (D.20) to the ‖θ− θ̃‖2, we use Lemma 7 to obtain the following inequalities:
N∑ n=1 ‖wm,n − w̃m,n‖2 ≤ √ N‖wm − w̃m‖2≤ √ N‖θ − θ̃‖2, (D.21)
L∑ `=1 |πm,` − π̃m,`| ≤ √ L‖πm − π̃m‖2≤ √ L‖θ − θ̃‖2. (D.22)
With Equation (D.1), Equation (D.16), Equation (D.19), Equation (D.20), Equation (D.21), and Equation (D.22),
‖J(x,θ)− J(x, θ̃)‖2F
= N∑ i=1 (‖J(xi,w)− J(xi, w̃)‖2F+‖J(xi,π)− J(xi, π̃)‖2F )
= 1
M N∑ i=1 M∑ m=1 ( N∑ n=1 (∥∥∥∥∥ L∑ `=1 ( πm,` ∂µm,`(xi,wm) ∂wm,n − π̃m,` ∂µm,`(xi, w̃m) ∂w̃m,n )∥∥∥∥∥ 2
2
)
+ L∑ `=1
(µm,`(xi,wm)− µm,`(xi, w̃m))2 )
= 1
M N∑ i=1 M∑ m=1 ( N∑ n=1 (∥∥∥∥∥ L∑ `=1 ( (πm,` − π̃m,`) ∂µm,`(xi,wm) ∂wm,n + ( ∂µm,`(xi,wm) ∂wm,n − ∂µm,`(xi, w̃m) ∂w̃m,n ) π̃m,` )∥∥∥∥∥ 2
2
)
+ L∑ `=1
(µm,`(xi,wm)− µm,`(xi, w̃m))2 )
≤ 1 M N∑ i=1 M∑ m=1 ( N∑ n=1 (( L∑ `=1 (|πm,` − π̃m,`|α‖xi‖2) + ( 2α‖xi‖22 N∑ n=1 ‖wm,n − w̃m,n‖2vL ))2)
+ L∑ `=1 ( N∑ n=1 ‖xi‖2‖wm,n − w̃m,n‖2 )2)
≤ 1 M N∑ i=1 M∑ m=1 ( N∑ n=1 (((√ L‖θ − θ̃‖2α‖xi‖2 ) + ( 2α‖xi‖22 √ N‖θ − θ̃‖2vL ))2)
+ L∑ `=1
( √ N‖xi‖2‖θ − θ̃‖2 )2)
≤ N∑ i=1 ( N ( α √ L‖xi‖2+2α‖xi‖22 √ N vL )2 + LN‖xi‖22 ) ‖θ − θ̃‖22. (D.23)
By considering the square root of both sides in Equation (D.17) and Equation (D.23), we concludes the proof for Lemma 8.

heading: E PROOF OF THEOREM 3
text: Proof. We can use the same approach with the proof of Theorem 1. Using an incremental formula, the output from the oblivious tree ensembles can be written as follows:
f (d)(xi,w,π) = 1√ M M∑ m=1 ( σ ( w>m,txi ) f (d−1)m ( xi,w (s) m ,π (l) m ) + ( 1− σ ( w>m,txi )) f (d−1)m ( xi,w (s) m ,π (r) m )) , (E.1)
where (s) ofw(s)m means (s)hared parameters at subtrees. Intuitively, the fundamental of Theorem 3 is that the outputs of the left subtree and right subtree are still independent with 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 Lemma 1, 2 and 3 are also valid for oblivious tree ensembles.
Correspondence to Lemma 1 To show the correspondence to Lemma 1, it is sufficient to show that Equation (A.22), Equation (A.23), Equation (A.24), and Equation (A.25) hold when
Em [ f (d+1)m (xi,wm,πm)f (d+1) m (xj ,wm,πm) ]
=Em  (f (d)m (xi,w(s)m ,π(l)m )− f (d)m (xi,w(s)m ,π(r)m ))σ(w>m,txi)︸ ︷︷ ︸
(A)
+ f (d)m ( xi,w (s) m ,π (r) m ) ︸ ︷︷ ︸
(B)  (f (d)m (xj ,w(s)m ,π(l)m )− f (d)m (xj ,w(s)m ,π(r)m ))σ(w>m,txj)︸ ︷︷ ︸
(C)
+ f (d)m ( xj ,w (s) m ,π (r) m ) ︸ ︷︷ ︸
(D)
  .
(E.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 even with the oblivious tree structure. Therefore, we can obtain the correspondences to Equation (A.22), Equation (A.23), Equation (A.24), and Equation (A.25) with the same procedures.
Correspondence to Lemma 2 For the depth d+ 1, since
∂f (d+1) (xi,w,π)
∂wm,s = σ(w>m,txi)
∂f (d) m ( xi,w (s) m ,π (r) m ) ∂wm,s
+ ( 1− σ(w>m,txi) ) ∂f (d)m (xi,w(s)m ,π(r)m ) ∂wm,s , (E.3)
the corresponding limiting TNTK is
Θ(d+1),(s) (xi,xj)
= d∑ s=2 Em
 σ(w>m,txi)∂f (d)m ( xi,w (s) m ,π (r) m ) ∂wm,s + ( 1− σ(w>m,txi) ) ∂f (d)m (xi,w(s)m ,π(r)m ) ∂wm,s > σ(w>m,txj)∂f (d)m ( xj ,w (s) m ,π (r) m ) ∂wm,s + ( 1− σ(w>m,txj) ) ∂f (d)m (xj ,w(s)m ,π(r)m ) ∂wm,s 
= d∑ s=2 Em  σ(w>m,txi) ∂f (d)m ( xi,w (s) m ,π (l) m ) ∂wm,s − ∂f (d) m ( xi,w (s) m ,π (r) m ) ∂wm,s  ︸ ︷︷ ︸
(A)
+ ∂f
(d) m ( xi,w (s) m ,π (r) m ) ∂wm,s︸ ︷︷ ︸
(B)
 >
σ(w>m,txj) ∂f (d)m ( xj ,w (s) m ,π (l) m ) ∂wm,s − ∂f (d) m ( xj ,w (s) m ,π (r) m ) ∂wm,s  ︸ ︷︷ ︸
(C)
+ ∂f
(d) m ( xj ,w (s) m ,π (r) m ) ∂wm,s︸ ︷︷ ︸
(D)
  . (E.4)
Since ∂f(d)m (xi,w (s) m ,π (r) m )
∂wm,s and
∂f(d)m (xj ,w (s) m ,π (l) m )
∂wm,s for s = {2, 3, . . . , d} are independent to each other
and have zero-mean Gaussian distribution4, similar calculation used for Equation (A.22), Equa-
4For a single oblivious tree, the number splitting rule is d because of the parameter sharing.
tion (A.23), Equation (A.24), and Equation (A.25) gives
Em [(A)× (C)] = T (xi,xj)Em  ∂f (d)m ( xi,w (s) m ,π (l) m ) ∂wm,s >∂f (d)m ( xj ,w (s) m ,π (l) m ) ∂wm,s 
+
∂f (d)m ( xi,w (s) m ,π (r) m ) ∂wm,s >∂f (d)m ( xj ,w (s) m ,π (r) m ) ∂wm,s   , (E.5)
Em [(B)× (C)] = −0.5 Em  ∂f (d)m ( xi,w (s) m ,π (r) m ) ∂wm,s >∂f (d)m ( xj ,w (s) m ,π (r) m ) ∂wm,s   , (E.6)
Em [(A)× (D)] = −0.5 Em  ∂f (d)m ( xi,w (s) m ,π (r) m ) ∂wm,s >∂f (d)m ( xj ,w (s) m ,π (r) m ) ∂wm,s   , (E.7)
Em [(B)× (D)] = Em  ∂f (d)m ( xi,w (s) m ,π (r) m ) ∂wm,s >∂f (d)m ( xj ,w (s) m ,π (r) m ) ∂wm,s   . (E.8)
As in the previous calculations, Equation (E.6), Equation (E.7), and Equation (E.8) cancel each other out. As a result, we obtain
Θ(d+1),(s) (xi,xj) = 2T (xi,xj) ( Θ(d),(t) (xi,xj) + Θ (d),(s) (xi,xj) ) . (E.9)
Correspondence to Lemma 3 Considering Equation (A.33), once we focus on a leaf `, it is not possible for both 11↘` and 1`↙1 to be 1. This means that a leaf cannot belong to both the right subtree and the left subtree. Therefore, even with oblivious tree structure, there is no influences. Therefore, we get exactly the same result to the Lemma 3.

heading: F DETAILS OF NUMERICAL EXPERIMENTS

heading: F.1 SETUP

heading: F.1.1 DATASET ACQUISITION
text: We use the UCI datasets (Dua & Graff, 2017) preprocessed by Fernández-Delgado et al. (2014), which are publicly available at http://persoal.citius.usc.es/manuel.fernandez. delgado/papers/jmlr/data.tar.gz. Since the size of the kernel is the 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.

heading: F.1.2 KERNEL SPECIFICATIONS
text: TNTK See Theorem 1 for the detailed definitions. We change the tree depth from 1 to 29 and change α in {0.5, 1.0, 2.0, 4.0, 8.0, 16.0, 32.0, 64.0}. MLP-induced NTK We assume the MLP activation function as ReLU. Our implementation is based on the publicly available code5 used in Arora et al. (2020). For the detailed definitions, see Arora et al. (2020). The hyperparameter of this kernel is the model depth. We change the depth from 1 to 29. Here, depth = 1 means there is no hidden layer in the MLP.
5https://github.com/LeoYu/neural-tangent-kernel-UCI
RBF kernel We use scikit-learn implementation6. The hyperparameter of this kernel is γ, inverse of the standard deviation of the RBF kernel (Gaussian function). For Figure 3, we tune γ 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 experiments, γ = 2.0 performs the best on average (Figure 9).

heading: F.1.3 MODEL SPECIFICATIONS
text: We used kernel regression implemented in scikit-learn7. To consider ridge-less situation, regularization strength is set to be 1.0× 10−8, a very small constant.

heading: F.1.4 COMPUTATIONAL COSTS
text: Since the training and inference algorithms of the kernel regression are common across different kernels, we analyze the computational cost of computing a single value in a 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 to 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 to changes in hyperparameters, thus its trend is similar to the TNTK. In terms of the space complexity, when considering a multi-layered MLP, since it is not necessary to store all past calculation results in memory during the recursive computation, the MLP-induced NTK computation consumes a certain amount of memory regardless of the depth of the layers. Therefore, the memory usage is almost the same across the RBF kernel, TNTK, and MLP-induced NTK.

heading: F.1.5 COMPUTATIONAL RESOURCE
text: We used Ubuntu Linux (version: 4.15.0-117-generic) and ran all experiments on 2.20 GHz Intel Xeon E5-2698 CPU and 252 GB of memory.

heading: F.2 RESULTS

heading: F.2.1 STATISTICAL SIGNIFICANCE OF THE PARAMETER DEPENDENCY
text: Wilcoxon signed rank test is carried out to check the statistical significance of the differences between different α. Figure 10 shows the p-values for the depth of 3 and 20. As shown in Figure 7, when the tree is shallow, the accuracy started to deteriorate after around α = 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 a significant difference over those with small α. However, when the tree is shallow, the best performance is achieved with α of about 8.0, and if α is too large, the performance deteriorates predominantly.
6https://scikit-learn.org/stable/modules/generated/sklearn.metrics. pairwise.rbf_kernel.html
7https://scikit-learn.org/stable/modules/generated/sklearn.kernel_ridge. KernelRidge.html

heading: F.2.2 DATASET-WISE RESULTS
text: For each α, scatter-plots are shown in Figures 11 and 12. As shown in Figure 13, the correlation coefficients with the TNTK are likely to be higher for the MLP-induced NTK compared to the RBF kernel. Tables 2, 3 and 4 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 1 to 29 are compared with the TNTK and the MLP-induced NTK. For the RBF kernel, γ is tuned in each dataset from 30 candidate values as described in Section F.1.2. Therefore, the number of tunable parameters is the same across all methods. All parameter-wise results are visualized in Figures 14 and 15.
na m
e si
ze α
=0 .5
α =1
.0 α
=2 .0
α =4
.0 α
=8 .0
α =1
6. 0
α =3
2. 0
α =6
4. 0
M L
PN
T K
R B
F
0 tr
ai ns
10 87
.5 00
87 .5
00 87
.5 00
87 .5
00 87
.5 00
87 .5
00 87
.5 00
87 .5
00 10
0. 00
0 87
.5 00
1 ba
llo on
s 16
87 .5
00 10
0. 00
0 93
.7 50
87 .5
00 87
.5 00
87 .5
00 87
.5 00
87 .5
00 10
0. 00
0 93
.7 50
2 le
ns es
24 87
.5 00
87 .5
00 87
.5 00
87 .5
00 87
.5 00
87 .5
00 87
.5 00
87 .5
00 87
.5 00
87 .5 00 3 lu ng -c an ce r 32 56 .2 50 53 .1 25 53 .1 25 53 .1 25 53 .1 25 56 .2 50 59 .3 75 59 .3 75 65 .6 25 53 .1 25 4 po st -o pe ra tiv e 90 63 .6 36 64 .7 73 67 .0 45 69 .3 18 69 .3 18 68 .1 82 68 .1 82 69 .3 18 69 .3 18 56 .8 18 5 pi tts bu rg -b ri dg es -S PA N 92 55 .4 35 57 .6 09 58 .6 96 67 .3 91 65 .2 17 66 .3 04 66 .3 04 67 .3 91 65 .2 17 58 .6 96 6 fe rt ili ty 10 0 84 .0 00 88 .0 00 89 .0 00 89 .0 00 89 .0 00 89 .0 00 89 .0 00 89 .0 00 89 .0 00 83 .0 00 7 zo o 10 1 10 0. 00 0 99 .0 00 99 .0 00 99 .0 00 99 .0 00 99 .0 00 99 .0 00 99 .0 00 99 .0 00 99 .0 00 8 pi tts bu rg -b ri dg es -T -O R -D 10 2 81 .0 00 84 .0 00 87 .0 00 89 .0 00 89 .0 00 89 .0 00 88 .0 00 88 .0 00 87 .0 00 89 .0 00 9 pi tts bu rg -b ri dg es -R E L -L 10 3 67 .3 08 74 .0 38 75 .0 00 74 .0 38 75 .9 62 75 .9 62 75 .9 62 75 .9 62 74 .0 38 74 .0 38 10 pi tts bu rg -b ri dg es -T Y PE 10 5 57 .6 92 59 .6 15 64 .4 23 66 .3 46 66 .3 46 66 .3 46 66 .3 46 65 .3 85 68 .2 69 59 .6 15 11 m ol ec -b io lpr om ot er 10 6 90 .3 85 88 .4 62 87 .5 00 87 .5 00 87 .5 00 87 .5 00 87 .5 00 87 .5 00 90 .3 85 88 .4 62 12 pi tts bu rg -b ri dg es -M A T E R IA L 10 6 93 .2 69 94 .2 31 94 .2 31 94 .2 31 94 .2 31 94 .2 31 94 .2 31 94 .2 31 94 .2 31 93 .2 69 13 br ea st -t is su e 10 6 65 .3 85 68 .2 69 67 .3 08 70 .1 92 72 .1 15 72 .1 15 75 .0 00 74 .0 38 69 .2 31 71 .1 54 14 α cu te -n ep hr iti s 12 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 15 α cu te -i nfl am m at io n 12 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 10 0. 00 0 16 he ar tsw itz er la nd 12 3 37 .0 97 43 .5 48 48 .3 87 47 .5 81 50 .0 00 44 .3 55 44 .3 55 44 .3 55 47 .5 81 37 .9 03 17 ec ho ca rd io gr am 13 1 81 .0 61 81 .0 61 84 .8 48 84 .0 91 85 .6 06 85 .6 06 85 .6 06 85 .6 06 85 .6 06 78 .0 30 18 ly m ph og ra ph y 14 8 88 .5 14 88 .5 14 88 .5 14 88 .5 14 87 .8 38 87 .1 62 86 .4 86 86 .4 86 88 .5 14 86 .4 86 19 ir is 15 0 95 .9 46 97 .9 73 96 .6 22 88 .5 14 86 .4 86 87 .1 62 87 .8 38 87 .1 62 87 .1 62 96 .6 22 20 te ac hi ng 15 1 56 .5 79 57 .8 95 58 .5 53 60 .5 26 64 .4 74 67 .1 05 67 .1 05 67 .7 63 63 .1 58 60 .5 26 21 he pa tit is 15 5 83 .9 74 85 .2 56 85 .2 56 84 .6 15 84 .6 15 84 .6 15 84 .6 15 85 .2 56 83 .9 74 85 .2 56 22 w in e 17 8 98 .8 64 99 .4 32 98 .8 64 98 .8 64 98 .8 64 98 .2 95 98 .2 95 97 .7 27 99 .4 32 98 .2 95 23 pl an ni ng 18 2 62 .2 22 65 .5 56 70 .0 00 71 .6 67 71 .6 67 72 .2 22 72 .2 22 72 .2 22 72 .2 22 67 .2 22 24 fla gs 19 4 52 .0 83 53 .6 46 53 .6 46 53 .1 25 53 .6 46 53 .1 25 53 .1 25 53 .1 25 53 .6 46 49 .4 79 25 pa rk in so ns 19 5 93 .8 78 94 .3 88 92 .8 57 93 .3 67 92 .8 57 92 .8 57 93 .3 67 93 .3 67 93 .8 78 95 .4 08 26 br ea st -c an ce rw is cpr og 19 8 82 .1 43 83 .6 73 83 .6 73 83 .6 73 83 .6 73 83 .6 73 83 .6 73 83 .6 73 85 .2 04 78 .5 71 27 he ar tva 20 0 31 .0 00 34 .0 00 36 .0 00 36 .0 00 37 .5 00 39 .0 00 40 .5 00 43 .0 00 36 .5 00 29 .0 00 28 co nn -b en ch -s on ar -m in es -r oc ks 20 8 86 .5 38 86 .5 38 87 .0 19 86 .5 38 86 .5 38 86 .5 38 86 .5 38 86 .5 38 87 .9 81 87 .5 00 29 se ed s 21 0 90 .8 65 93 .7 50 93 .2 69 91 .8 27 92 .3 08 92 .3 08 91 .8 27 91 .8 27 96 .1 54 95 .6 73
Ta bl
e 2:
C om
pa ri
so n
be tw
ee n
T N
T K
an d
M L
Pin
du ce
d N
T K
fo ra
ha lf
of th
e da
ta se
t( 1/
3) .
na m
e si
ze α
=0 .5
α =1
.0 α
=2 .0
α =4
.0 α
=8 .0
α =1
6. 0
α =3
2. 0
α =6
4. 0
M L
PN
T K
R B
F
30 gl
as s
21 4
60 .8
49 67
.4 53
70 .7
55 70
.7 55
71 .6
98 71
.6 98
71 .2
26 71
.2 26
70 .2
83 69
.8 11
31 st
at lo
ghe
ar t
27 0
83 .2
09 87
.3 13
87 .6
87 88
.4 33
88 .4
33 88
.4 33
87 .6
87 87
.3 13
86 .5
67 82
.4 63
32 br
ea st
-c an
ce r
28 6
64 .7
89 67
.2 54
69 .7
18 70
.4 23
72 .8
87 74
.6 48
75 .0
00 75
.0 00
71 .8
31 65
.8 45
33 he
ar t-
hu ng
ar ia
n 29
4 83
.2 19
83 .9
04 84
.2 47
84 .5
89 85
.6 16
85 .2
74 85
.2 74
85 .2
74 85
.6 16
82 .8 77 34 he ar tcl ev el an d 30 3 55 .2 63 58 .2 24 58 .8 82 59 .2 11 59 .5 39 58 .5 53 59 .2 11 59 .5 39 57 .8 95 53 .6 18 35 ha be rm an -s ur vi va l 30 6 59 .5 39 61 .5 13 61 .8 42 66 .4 47 68 .4 21 71 .7 11 73 .6 84 73 .6 84 71 .0 53 70 .3 95 36 ve rt eb ra lco lu m n2c la se s 31 0 69 .8 05 77 .2 73 78 .5 71 80 .8 44 82 .7 92 84 .0 91 84 .0 91 82 .7 92 83 .1 17 81 .4 94 37 ve rt eb ra lco lu m n3c la se s 31 0 71 .7 53 78 .2 47 81 .1 69 80 .8 44 80 .8 44 81 .8 18 81 .4 94 81 .1 69 81 .8 18 81 .1 69 38 pr im ar ytu m or 33 0 47 .5 61 50 .3 05 52 .1 34 53 .0 49 52 .7 44 50 .6 10 50 .3 05 50 .0 00 52 .1 34 45 .4 27 39 ec ol i 33 6 71 .4 29 79 .1 67 83 .0 36 84 .5 24 86 .0 12 86 .6 07 86 .9 05 86 .9 05 85 .4 17 81 .2 50 40 io no sp he re 35 1 90 .0 57 91 .4 77 90 .3 41 87 .7 84 88 .3 52 88 .3 52 88 .3 52 88 .3 52 91 .7 61 92 .3 30 41 lib ra s 36 0 82 .7 78 81 .3 89 80 .5 56 80 .8 33 81 .1 11 80 .8 33 80 .8 33 80 .8 33 83 .8 89 85 .2 78 42 de rm at ol og y 36 6 97 .8 02 97 .8 02 97 .5 27 97 .5 27 97 .2 53 97 .2 53 97 .2 53 97 .2 53 97 .8 02 97 .2 53 43 co ng re ss io na lvo tin g 43 5 61 .6 97 61 .6 97 61 .9 27 61 .9 27 61 .9 27 61 .6 97 61 .6 97 61 .6 97 61 .6 97 62 .1 56 44 α rr hy th m ia 45 2 69 .4 69 65 .2 65 64 .6 02 64 .8 23 64 .8 23 64 .8 23 64 .8 23 64 .8 23 71 .2 39 69 .2 48 45 m us k1 47 6 89 .0 76 89 .0 76 89 .0 76 89 .2 86 89 .2 86 89 .0 76 89 .0 76 89 .0 76 89 .7 06 90 .7 56 46 cy lin de rba nd s 51 2 79 .8 83 78 .1 25 78 .1 25 78 .3 20 78 .5 16 78 .3 20 78 .3 20 78 .3 20 80 .2 73 79 .6 88 47 lo w -r es -s pe ct 53 1 91 .7 29 91 .3 53 90 .6 02 89 .4 74 88 .5 34 87 .7 82 87 .2 18 87 .2 18 91 .3 53 90 .2 26 48 br ea st -c an ce rw is cdi ag 56 9 96 .1 27 96 .6 55 97 .3 59 97 .3 59 97 .3 59 96 .8 31 96 .4 79 96 .4 79 97 .0 07 95 .5 99 49 ilp din di an -l iv er 58 3 64 .8 97 69 .5 21 70 .7 19 72 .2 60 71 .0 62 71 .7 47 72 .6 03 72 .6 03 71 .9 18 70 .3 77 50 sy nt he tic -c on tr ol 60 0 99 .3 33 99 .3 33 99 .1 67 98 .8 33 98 .3 33 97 .8 33 97 .0 00 96 .6 67 98 .8 33 99 .3 33 51 ba la nc esc al e 62 5 81 .2 50 84 .6 15 88 .7 82 89 .9 04 91 .3 46 90 .0 64 85 .2 56 85 .2 56 93 .2 69 90 .8 65 52 st at lo gau st ra lia ncr ed it 69 0 59 .0 12 60 .6 10 64 .0 99 66 .2 79 67 .1 51 68 .0 23 68 .0 23 68 .0 23 66 .2 79 59 .3 02 53 cr ed itap pr ov al 69 0 82 .5 58 85 .1 74 86 .6 28 87 .2 09 87 .6 45 87 .7 91 87 .7 91 87 .3 55 87 .0 64 81 .6 86 54 br ea st -c an ce rw is c 69 9 96 .2 86 97 .2 86 97 .8 57 97 .8 57 98 .0 00 98 .0 00 98 .0 00 98 .0 00 98 .0 00 96 .7 14 55 bl oo d 74 8 67 .5 13 65 .7 75 63 .3 69 69 .7 86 72 .7 27 73 .5 29 75 .8 02 77 .0 05 74 .0 64 78 .0 75 56 en er gy -y 2 76 8 89 .5 83 89 .4 53 88 .0 21 87 .8 91 88 .1 51 87 .6 30 87 .6 30 87 .6 30 88 .2 81 90 .7 55 57 pi m a 76 8 68 .2 29 70 .1 82 71 .3 54 73 .3 07 76 .0 42 76 .3 02 77 .0 83 76 .6 93 75 .0 00 69 .6 61 58 en er gy -y 1 76 8 93 .7 50 93 .6 20 93 .2 29 90 .4 95 90 .2 34 90 .1 04 90 .2 34 90 .2 34 92 .7 08 96 .4 84 59 st at lo gve hi cl e 84 6 78 .3 18 77 .0 14 76 .5 40 73 .5 78 72 .9 86 72 .1 56 72 .0 38 72 .0 38 81 .3 98 77 .4 88
Ta bl
e 3:
C om
pa ri
so n
be tw
ee n
T N
T K
an d
M L
Pin
du ce
d N
T K
fo ra
ha lf
of th
e da
ta se
t( 2/
3) .
na m
e si
ze α
=0 .5
α =1
.0 α
=2 .0
α =4
.0 α
=8 .0
α =1
6. 0
α =3
2. 0
α =6
4. 0
M L
PN
T K
R B
F
60 oo
cy te
s_ tr
is op
te ru
s_ nu
cl eu
s_ 2f
91 2
82 .4
56 82
.5 66
82 .4
56 82
.6 75
80 .8
11 78
.7 28
78 .0
70 77
.8 51
84 .9
78 79
.6 05
61 oo
cy te
s_ tr
is op
te ru
s_ st
at es
_5 b
91 2
92 .3
25 92
.9 82
93 .6
40 93
.0 92
91 .6
67 90
.0 22
89 .6
93 89
.6 93
94 .1
89 91
.2 28
62 tic
-t ac
-t oe
95 8
99 .2
68 99
.1 63
99 .2
68 99
.2 68
99 .2
68 99
.2 68
99 .2
68 99
.2 68
98 .6
40 10
0. 00 0 63 m am m og ra ph ic 96 1 72 .7 08 71 .2 50 72 .0 83 75 .6 25 77 .6 04 78 .8 54 78 .9 58 79 .2 71 80 .0 00 78 .7 50 64 st at lo gge rm an -c re di t 10 00 75 .2 00 76 .5 00 77 .8 00 77 .3 00 76 .2 00 75 .5 00 75 .5 00 75 .4 00 77 .5 00 73 .7 00 65 le ddi sp la y 10 00 72 .4 00 72 .3 00 72 .6 00 72 .5 00 72 .3 00 72 .5 00 72 .3 00 72 .5 00 72 .9 00 73 .0 00 66 oo cy te s_ m er lu cc iu s_ nu cl eu s_ 4d 10 22 81 .0 78 80 .5 88 80 .6 86 80 .6 86 79 .4 12 77 .2 55 76 .9 61 76 .7 65 83 .7 25 75 .4 90 67 oo cy te s_ m er lu cc iu s_ st at es _2 f 10 22 92 .3 53 91 .9 61 92 .1 57 92 .1 57 91 .3 73 90 .7 84 90 .7 84 90 .4 90 93 .0 39 92 .0 59 68 co nt ra c 14 73 40 .0 82 44 .2 93 47 .1 47 50 .0 68 51 .1 55 52 .0 38 52 .5 14 51 .1 55 50 .2 72 43 .2 07 69 ye as t 14 84 42 .5 88 49 .3 26 54 .3 80 58 .1 54 60 .0 40 60 .2 43 60 .4 45 60 .8 49 59 .6 36 54 .3 80 70 se m ei on 15 93 93 .7 19 93 .4 67 93 .4 05 93 .4 67 93 .4 67 93 .4 67 93 .4 67 93 .4 05 96 .1 68 95 .6 03 71 w in equ al ity -r ed 15 99 63 .0 62 65 .9 38 68 .8 12 70 .0 00 70 .6 25 70 .3 75 70 .3 12 70 .3 12 69 .6 25 64 .4 38 72 pl an tte xt ur e 15 99 83 .8 12 81 .8 12 79 .4 38 77 .9 38 77 .6 88 77 .6 25 77 .7 50 77 .6 25 86 .1 25 85 .6 25 73 pl an tm ar gi n 16 00 84 .7 50 83 .9 38 82 .9 38 81 .8 75 80 .7 50 79 .5 00 78 .9 38 78 .5 63 84 .8 75 83 .8 75 74 pl an tsh ap e 16 00 64 .8 12 63 .5 62 62 .4 38 60 .3 75 58 .3 12 57 .0 62 56 .3 75 55 .9 37 66 .2 50 68 .0 00 75 ca r 17 28 97 .4 54 97 .5 69 97 .1 64 96 .7 01 96 .3 54 96 .1 81 96 .1 23 96 .1 23 97 .7 43 98 .0 32 76 st ee lpl at es 19 41 76 .2 89 77 .3 20 77 .9 38 77 .4 23 77 .0 62 76 .7 53 76 .5 98 76 .4 95 78 .3 51 75 .1 03 77 ca rd io to co gr ap hy -3 cl as es 21 26 92 .2 32 92 .5 14 92 .0 43 91 .9 02 91 .9 49 91 .8 55 91 .9 96 91 .8 55 93 .1 73 92 .0 43 78 ca rd io to co gr ap hy -1 0c la se s 21 26 80 .8 38 82 .9 57 82 .2 50 80 .7 44 79 .8 96 79 .8 96 79 .6 61 79 .6 14 84 .1 81 79 .1 43 79 tit an ic 22 01 78 .9 55 78 .9 55 78 .9 55 78 .9 55 78 .9 55 78 .9 55 78 .9 55 78 .9 55 78 .9 55 78 .9 55 80 st at lo gim ag e 23 10 96 .3 60 96 .9 67 97 .0 97 96 .7 50 96 .2 31 95 .9 27 95 .8 84 95 .6 24 97 .6 60 96 .4 04 81 oz on e 25 36 97 .3 58 97 .2 40 97 .2 00 97 .2 00 97 .2 00 97 .2 00 97 .2 00 97 .2 00 97 .3 97 97 .2 00 82 m ol ec -b io lsp lic e 31 90 86 .7 31 85 .9 47 84 .5 36 83 .0 93 82 .4 65 82 .4 03 82 .3 71 82 .3 71 86 .9 20 86 .4 18 83 ch es skr vk p 31 96 99 .1 24 98 .9 05 98 .6 55 97 .8 72 96 .9 02 95 .5 26 95 .3 07 95 .3 07 99 .4 06 98 .9 99 84 α ba lo ne 41 77 50 .4 07 49 .8 80 55 .5 32 60 .0 10 62 .5 48 64 .2 00 64 .9 43 65 .0 86 63 .4 10 64 .1 52 85 ba nk 45 21 88 .6 28 89 .3 36 89 .3 58 89 .5 13 89 .3 58 89 .1 59 89 .1 81 89 .1 59 89 .7 35 88 .1 42 86 sp am ba se 46 01 91 .4 78 91 .1 74 92 .4 35 90 .6 52 93 .1 30 89 .6 30 91 .4 78 93 .3 48 94 .9 13 90 .6 52 87 w in equ al ity -w hi te 48 98 63 .6 23 66 .8 10 67 .5 45 68 .7 91 69 .1 58 68 .9 75 68 .9 95 68 .9 13 69 .0 97 65 .7 48 88 w av ef or m -n oi se 50 00 86 .3 60 86 .3 40 86 .5 20 86 .5 40 86 .7 20 86 .5 00 85 .9 00 85 .5 20 86 .5 40 85 .4 60 89 w av ef or m 50 00 85 .4 40 85 .7 80 86 .3 00 86 .5 00 86 .6 60 86 .7 00 86 .7 40 86 .5 20 86 .3 40 84 .6 40
Ta bl
e 4:
C om
pa ri
so n
be tw
ee n
T N
T K
an d
M L
Pin
du ce
d N
T K
fo ra
ha lf
of th
e da
ta se
t( 3/
3) .

Review summaries:
The paper presents an extension of a neural network analytic tool called Neural Tangent Kernels to its use for decision trees and forests.  The focus is a previously proposed notion of soft trees. A few analytical results are presented about the properties of the extended notion, called Tree Neural Tangent Kernel, such as the existence of some limiting deterministic form, how alternative probabilistic tree ensembles would have their kernels converging to this deterministic form, that this limiting kernel is positive definite, and that the kernel remains stable during training, equivalence of the kernels for one-level tree ensembles to those of two-layer perceptrons, etc. Some support for the analytical claims is provided by simulation experiments. 

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. 

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.