A Neural Tangent Kernel Perspective of Infinite Tree Ensembles

• URL: http://arxiv.org/abs/2109.04983v1
• Date: Fri, 10 Sep 2021 16:48:24 GMT
• Title: A Neural Tangent Kernel Perspective of Infinite Tree Ensembles
• Authors: Ryuichi Kanoh, Mahito Sugiyama
• Abstract summary: 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.
• Score: 8.020742121274417
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In practical situations, the ensemble tree model is one of the most popular models along with neural networks. A soft tree is one of the variants 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 the effect of the oblivious tree structure and the degeneracy of the TNTK induced by the deepening of the trees. Moreover, we empirically examine the performance of an ensemble of infinite soft trees using the TNTK.

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)
• ViTree: Single-path Neural Tree for Step-wise Interpretable Fine-grained Visual Categorization [56.37520969273242]
  We introduce ViTree, a novel approach for fine-grained visual categorization. By traversing the tree paths, ViTree effectively selects patches from transformer-processed features to highlight informative local regions. This patch and path selectivity enhances model interpretability of ViTree, enabling better insights into the model's inner workings.
  arXiv  Detail & Related papers  (2024-01-30T14:32:25Z)
• 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)
• A Neural Tangent Kernel Formula for Ensembles of Soft Trees with Arbitrary Architectures [5.634825161148483]
  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.
  arXiv  Detail & Related papers  (2022-05-25T16:49:29Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  We consider learning Ising tree models when the observations from the nodes are corrupted by independent but non-identically distributed noise. Katiyar et al. (2020) showed that although the exact tree structure cannot be recovered, one can recover a partial tree structure. We propose Symmetrized Geometric Averaging (SGA), a more statistically robust algorithm for partial tree recovery.
  arXiv  Detail & Related papers  (2021-01-22T01:57:35Z)
• 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)
• 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)
• Born-Again Tree Ensembles [9.307453801175177]
  Tree ensembles offer a good prediction quality in various domains, but the concurrent use of multiple trees reduces the interpretability of the ensemble. We study the process of constructing a single decision tree of minimum size that reproduces the exact same behavior as a given tree ensemble in its entire feature space. This algorithm generates optimal born-again trees for many datasets of practical interest.
  arXiv  Detail & Related papers  (2020-03-24T22:17:21Z)
• The Tree Ensemble Layer: Differentiability meets Conditional Computation [8.40843862024745]
  We introduce a new layer for neural networks composed of an ensemble of differentiable decision trees (a.k.a. soft trees) Differentiable trees demonstrate promising results in the literature, but are typically slow in training and inference as they do not support conditional computation. We develop specialized forward and backward propagation algorithms that exploit sparsity.
  arXiv  Detail & Related papers  (2020-02-18T18:05:31Z)

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.