A Neural Tangent Kernel Formula for Ensembles of Soft Trees with Arbitrary Architectures

• URL: http://arxiv.org/abs/2205.12904v1
• Date: Wed, 25 May 2022 16:49:29 GMT
• Title: A Neural Tangent Kernel Formula for Ensembles of Soft Trees with Arbitrary Architectures
• Authors: Ryuichi Kanoh, Mahito Sugiyama
• Abstract summary: A soft tree is an actively studied variant of a decision tree that updates splitting rules using the gradient method. We formulate and analyze the Neural Kernel Tangent (NTK) induced by soft tree ensembles for arbitrary tree architectures.
• Score: 5.634825161148483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A soft tree is an actively studied variant of a decision tree that updates splitting rules using the gradient method. Although it can have various tree architectures, the theoretical properties of their impact are not 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 infinitely many 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.

Related papers

• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  We introduce MetaTree, a transformer-based model trained via meta-learning to directly produce strong decision trees. We fit both greedy decision trees and globally optimized decision trees on a large number of datasets, and train MetaTree to produce only the trees that achieve strong generalization performance.
  arXiv  Detail & Related papers  (2024-02-06T07:40:53Z)
• DeepTree: Modeling Trees with Situated Latents [8.372189962601073]
  We propose a novel method for modeling trees based on learning developmental rules for branching structures instead of manually defining them. We call our deep neural model situated latent because its behavior is determined by the intrinsic state. Our method enables generating a wide variety of tree shapes without the need to define intricate parameters.
  arXiv  Detail & Related papers  (2023-05-09T03:33:14Z)
• Structure-Unified M-Tree Coding Solver for MathWord Problem [57.825176412485504]
  In previous work, models designed by taking into account the properties of the binary tree structure of mathematical expressions at the output side have achieved better performance. In this paper, we propose the Structure-Unified M-Tree Coding Coding (S-UMCr), which applies a tree with any M branches (M-tree) to unify the output structures. Experimental results on the widely used MAWPS and Math23K datasets have demonstrated that SUMC-r not only outperforms several state-of-the-art models but also performs much better under low-resource conditions.
  arXiv  Detail & Related papers  (2022-10-22T12:20:36Z)
• Linear TreeShap [16.246232737115218]
  Decision trees are well-known due to their ease of interpretability. To improve accuracy, we need to grow deep trees or ensembles of trees. This paper presents a more efficient and straightforward algorithm: Linear TreeShap.
  arXiv  Detail & Related papers  (2022-09-16T23:17:15Z)
• Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods [10.289846887751079]
  We introduce Hierarchical Shrinkage (HS), a post-hoc algorithm that does not modify the tree structure. HS substantially increases the predictive performance of decision trees, even when used in conjunction with other regularization techniques. All code and models are released in a full-fledged package available on Github.
  arXiv  Detail & Related papers  (2022-02-02T02:43:23Z)
• Tree in Tree: from Decision Trees to Decision Graphs [2.2336243882030025]
  Tree in Tree decision graph (TnT) is a framework that extends the conventional decision tree to a more generic and powerful directed acyclic graph. Our proposed model is a novel, more efficient, and accurate alternative to the widely-used decision trees.
  arXiv  Detail & Related papers  (2021-10-01T13:20:05Z)
• A Neural Tangent Kernel Perspective of Infinite Tree Ensembles [8.020742121274417]
  We introduce and study the Tree Neural Tangent Kernel (TNTK), which provides new insights into the behavior of the infinite ensemble of soft trees. We find several non-trivial properties, such as the effect of the oblivious tree structure and the degeneracy of the TNTK induced by the deepening of the trees.
  arXiv  Detail & Related papers  (2021-09-10T16:48:24Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• Convex Polytope Trees [57.56078843831244]
  convex polytope trees (CPT) are proposed to expand the family of decision trees by an interpretable generalization of their decision boundary. We develop a greedy method to efficiently construct CPT and scalable end-to-end training algorithms for the tree parameters when the tree structure is given.
  arXiv  Detail & Related papers  (2020-10-21T19:38:57Z)
• Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
  We analyze the output of state-of-the-arts on many languages from the Universal Dependency Treebank. The worst constraint-violation rate we observe is 24%.
  arXiv  Detail & Related papers  (2020-10-06T08:31:14Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.