Neural Tangent Kernels for Axis-Aligned Tree Ensembles

Thank you for your review.

In Section 3.1, if I interpret it correctly, AAA refers to axis-aligned initialization, with the assumption that the selected split feature at each node remains constant throughout training. This assumption appears rather restrictive, considering that typical axis-aligned trees do not impose such constraints. It would be valuable if the author provided further insights or comments regarding this assumption.

Our idea is to divide the learning process of decision trees into two components:

1. selecting tree topological structure and split features,
2. tuning parameters for splitting thresholds at internal nodes and leaves,

and providing theoretical analysis for AAA and AAI about the second component with Theorem 2. Since it can be combined with any method for the first component, the entire model is no longer restrictive in practice. Similar to the typical decision trees, it is possible to grow a tree by trying out several splitting patterns and adopting the ones with better performance. In our experiments in Section 4.2, we have used MKL to learn tree architectures for the first component and showed its effectiveness.

The paper lacks an exploration of the computational complexity and scalability issues related to employing Multiple Kernel Learning (MKL) for tree architecture search. It is crucial to assess the feasibility and efficiency of utilizing MKL, particularly for large-scale datasets and high-dimensional feature spaces.

The overall computational cost of MKL can be divided in two parts: computation of the kernel matrix and optimization of weights.

To obtain a single kernel matrix, a calculation defined in Equation (9) is performed $N^2$ times, where $N$ is the size of an input dataset. When we denote the number of leaves as $\mathcal{L}$ and the depth of the tree as $D$, the worst case overall computational complexity is $\mathcal{O}(N^2 \mathcal{L}D^2)$. Additionally, this calculation is needed to be repeated for all the kernel matrices, while parallelization is possible in this process. Note that if there are duplicates in the output of $h(a_\ell)$ for all $\ell \in [\mathcal{L}]$, the computational cost can be reduced by aggregating and computing these duplicates together, so the actual computational cost is often less than this. For example, when considering oblivious trees, the computational complexity reduces to $O(N^2 D^2)$.

The cost to calculate the weights of the kernels by EasyMKL depends on the number of kernels. Specifically, EasyMKL uses Kernelized Optimization of the Margin Distribution (KOMD), and its computational cost is known to be linear with respect to the number of kernels [1].

We have added the above discussion about the computational complexity in the Appendix (Section E) in our revision.

Please note that MKL is mainly chosen for a better understanding of the behavior of AAI and AAI, and we have successfully shown that suitable features can differ between AAA and AAI in Figure 7. If one would like to construct more practical methods, other approaches should be considered, while it is beyond the scope of our paper.

[1] Fabio Aiolli and Michele Donini (2015), EasyMKL: a scalable multiple kernel learning algorithm

Additionally, I have another question regarding the analysis framework: does this analysis framework allow non-zero initialized parameters (selected split features) become zero (no split at one node) during the training? If the framework allows for such adaptability, it could potentially accommodate changes in the shapes or depths of trees during training, thus enhancing its overall generality.

Thank you for your comment. It is indeed an interesting idea. For example, incorporating L1 regularization on weights in the training process using gradient descent might be possible to obtain space weights. It could also be interesting to apply a temperature-scaled sparsemax [2] to the weights. We believe these ideas are interesting future directions.

[2] Martins & Astudillo (2016), From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification

Thank you for your review.

The paper is theoretical in nature, but its impact for practical applications seems very limited to me.

We disagree with this point. For instance, Proposition 2 guarantees that the consideration of oblivious trees is sufficient for searching tree architectures, resulting in a substantial reduction in the architecture search space in practical situations. Moreover, the insight that feature selection is not important for AAI can lead to more efficient processes by reducing unnecessary searches. We believe that acquiring the NTK that enables us to comprehend training behavior, and using it to theoretically support these characteristics in a rigorous manner, is of significant importance.

Experimental validation is limited to one dataset. This raises concerns about the practical use of this work. The comparison with Random Forest in unfair because RF is limited to depth 3.

There is no comparison with existing modern ensembling techniques such as Gradient Boost.

While we show the results of only one dataset in the main text, we have already conducted numerical experiments on 14 datasets about MKL weight distributions, as written in the last sentence of the second paragraph in Section 4.2. These experiments have been already described in our initial submission before revision. In addition, while it is not directly related to the main claim of the paper, empirical analyses of the generalization performance across numerous datasets have also been added to the Appendix (Section D.5). The tic-tac-toe dataset was chosen for the main content because we think it made understanding the properties of models easier. We would like to note that, in our paper, we do not focus on the practical utility of these forest models; rather, we aim to understand their theoretical properties. It is not fundamental to make a general claim that AAA and AAI are better or worse than other models in terms of generalization performance as it depends on datasets. This is a natural consequence and orthogonal to our claim in this paper. The tic-tac-toe dataset intuitively demonstrates that methods like AAA and AAI perform better than greedy methods such as Random Forest. This discussion has been added to the Appendix (Section D.5).

To further address your concern, we have added comparative results of typical forest models on the tic-tac-toe dataset in the Appendix (Section D.6), including experiments where tree depth was varied or Gradient Boosting was used. Typical forest models did not surpass AAA across all the tested settings of the tree depth or learning algorithms.

It is not clear how many attributes were used for splitting at each node for RF. If the number of attributes is small, RF needs deep trees to find the relevant features.

In Random Forest, each splitting node uses a single feature to make a split, which is a typical approach, and this is the same as AAA.

What are the practical implications of knowing the NTK induced by axis-aligned tree ensembles? Does this imply that we can obtain better/faster training algorithms?

Yes, it does. That is an important argument of our paper. As described in Proposition 2, it is sufficient to consider only oblivious trees as tree topological structures, which significantly reduces the search space and can lead to faster training. Furthermore, our empirical results show that feature selection holds minimal importance for AAI, which also contributes to efficient training.

What is the difference between this paper and Kanoh and Sugiyama. "Investigating Axis-Aligned Differentiable Trees through Neural Tangent Kernels". In ICML 2023 Workshop on Differentiable Almost Everything: Differentiable Relaxations, Algorithms, Operators, and Simulators?

There is no concern regarding this matter. We have already communicated individually with the program chairs and senior area chairs. Due to the author's instructions, we are unable to provide further details in this forum.

Thank you for your review.

The paper argues that one of its contributions is including finite tree ensemble scenarios. However, in Section 4, the proposition is only on infinite trees. Why is this?

Proposition 2 focuses on the property of a deterministic closed-form formula (=limiting NTK). A deterministic closed-form kernel is derived when assuming an infinitely large number of trees, and a deterministic NTK is not induced due to initialization randomness when the number of trees is finite. As the number of trees increases, the NTK asymptotically approaches a deterministic closed-form formula.

Thank you for your review.

I do not really understand why we would want NTK for tree ensembles, or more specifically axis-aligned trees. Typically, I look to theory because it can provide insight or intuition about why some method is working well. I did not get any of that here. What does this theory explain about axis-aligned trees that we did not already know?

As stated in Section 2.2, the NTK precisely describes training behavior when an axis-aligned tree ensemble is trained through gradient methods. This ability of the NTK leads to our findings such as the sufficiency of considering oblivious trees (Proposition 2) and the realization that feature selection is not important in the case of AAI (Figure 7).

Those kernels are exact, whereas this kernel is an approximation. Given that trees/forests directly induce a kernel, I do not understand why we would want to derive an approximate kernel?

The typical kernel obtained from a trained forest simply measures the similarity between data points. However, the kernel we have derived is the NTK, which allows us to analytically describe the training behavior of a model without actually conducting the training. An example of this is shown in Figure 4, and the theoretical background is presented in Section 2.2. While both fall under the category of kernels, their roles are fundamentally different and our NTK is not an approximation of the kernels you have listed.

NTKs have successfully provided theoretical insights for not only the tree ensemble models but also various other models such as typical MLPs, CNNs, RNNs, and Transformers, and NTKs help validate the models. Examples include the equivalence between global average pooling in CNNs and certain data augmentations [1] and the explanation of why performance does not significantly deteriorate in ResNets with Skip Connections even for deeper models [2].

We would also like to clarify the issue of 'exact/approximation.' The closed-form formula for the NTK is available when considering an infinite number of trees. Moreover, even in the finite case, the kernel can be precisely derived without any approximation. Therefore our NTK is also exact in that sense. There is a randomness due to initialization and the kernel value could vary slightly with each initialization. Nevertheless, as shown in Figure A.2, this variation converges to zero as the number of trees increases, matching the deterministic kernel given in Theorem 2. We believe that such randomness also exists in the existing kernels for trained typical forest models, for example due to bagging, and this is unrelated to the question of whether it is an approximation.

[1] Li et al., (2019), Enhanced Convolutional Neural Tangent Kernels

[2] Huang et al., (2020), Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? — A Neural Tangent Kernel Perspective

The primary results seem to depend on all the trees having the same architecture, and also all the features being somehow already selected? I do not understand where the architecture or selected features come from?

We believe you are referring to Theorem 2. Then you are right that our primary result (Theorem 2) assumes that all the trees are equivalent in terms of the tree topological structure and selected features. However, it does not specify how to choose the features or tree topological structure, which can be independently implemented. One can select any method for choosing the features or tree structure, and our theorem applies to any selection. Even in AAA, it is possible to develop a tree by empirically examining various splitting patterns and adopting those with better performance on training data. As demonstrated in Section 4.2, it is also feasible to learn tree architectures using MKL. There are various approaches.