Analyzing Tree Architectures in Ensembles via Neural Tangent Kernel
This provides theoretical insights for machine learning researchers working on ensemble methods and tree-based models, though it is incremental as it builds on existing NTK analysis.
The paper tackles the problem of understanding the impact of different tree architectures in soft tree ensembles by analyzing their Neural Tangent Kernel (NTK), finding that only the number of leaves at each depth matters for training and generalization in infinite ensembles, and showing that asymmetric trees avoid NTK degeneration unlike perfect binary trees.
A soft tree is an actively studied variant of a decision tree that updates splitting rules using the gradient method. Although soft trees can take various architectures, their impact is not theoretically well known. In this paper, we formulate and analyze the Neural Tangent Kernel (NTK) induced by soft tree ensembles for arbitrary tree architectures. This kernel leads to the remarkable finding that only the number of leaves at each depth is relevant for the tree architecture in ensemble learning with an infinite number of trees. In other words, if the number of leaves at each depth is fixed, the training behavior in function space and the generalization performance are exactly the same across different tree architectures, even if they are not isomorphic. We also show that the NTK of asymmetric trees like decision lists does not degenerate when they get infinitely deep. This is in contrast to the perfect binary trees, whose NTK is known to degenerate and leads to worse generalization performance for deeper trees.