Yet Another Representation of Binary Decision Trees: A Mathematical Demonstration

• URL: http://arxiv.org/abs/2101.07077v7
• Date: Fri, 10 May 2024 05:45:21 GMT
• Title: Yet Another Representation of Binary Decision Trees: A Mathematical Demonstration
• Authors: Jinxiong Zhang,
• Abstract summary: A decision tree looks like a simple computational graph without cycles. From the numerical perspective, we express decision trees in the language of computational graph.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: A decision tree looks like a simple computational graph without cycles, where only the leaf nodes specify the output values and the non-terminals specify their tests or split conditions. From the numerical perspective, we express decision trees in the language of computational graph. We explicitly parameterize the test phase, traversal phase and prediction phase of decision trees based on the bitvectors of non-terminal nodes. As shown later, the decision tree is a shallow binary network in some sense. Especially, we introduce the bitvector matrix to implement the tree traversal in numerical approach, where the core is to convert the logical `AND' operation to arithmetic operations. And we apply this numerical representation to extend and unify diverse decision trees in concept.

Related papers

• Terminating Differentiable Tree Experts [77.2443883991608]
  We propose a neuro-symbolic Differentiable Tree Machine that learns tree operations using a combination of transformers and Representation Products. We first remove a series of different transformer layers that are used in every step by introducing a mixture of experts. We additionally propose a new termination algorithm to provide the model the power to choose how many steps to make automatically.
  arXiv  Detail & Related papers  (2024-07-02T08:45:38Z)
• 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)
• Characterizing Intrinsic Compositionality in Transformers with Tree Projections [72.45375959893218]
  neural models like transformers can route information arbitrarily between different parts of their input. We show that transformers for three different tasks become more treelike over the course of training. These trees are predictive of model behavior, with more tree-like models generalizing better on tests of compositional generalization.
  arXiv  Detail & Related papers  (2022-11-02T17:10:07Z)
• 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)
• Arithmetical Binary Decision Tree Traversals [0.0]
  We present a suite of binary tree traversal algorithms that leverage novel representation matrices to flatten the full binary tree structure. Our approach, grounded in maximum inner product search, offers new insights into decision tree.
  arXiv  Detail & Related papers  (2022-09-11T09:53:14Z)
• 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)
• Decision Machines: Congruent Decision Trees [0.0]
  We propose Decision Machines, which embed Boolean tests into a binary vector space and represent the tree structure as a matrices. We explore the congruence of decision trees and attention mechanisms, opening new avenues for optimizing decision trees and potentially enhancing their predictive power.
  arXiv  Detail & Related papers  (2021-01-27T12:23:24Z)
• Strongly Incremental Constituency Parsing with Graph Neural Networks [70.16880251349093]
  Parsing sentences into syntax trees can benefit downstream applications in NLP. Transition-baseds build trees by executing actions in a state transition system. Existing transition-baseds are predominantly based on the shift-reduce transition system.
  arXiv  Detail & Related papers  (2020-10-27T19:19:38Z)
• 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)
• Decision trees as partitioning machines to characterize their generalization properties [2.370481325034443]
  We revisit binary decision trees on real-valued features from the perspective of partitions of the data. We show that the VC dimension of a binary tree structure with $N$ internal nodes is of order $N log(Nell)$. We elaborate a pruning algorithm based on these results that performs better than the CART algorithm on a number of datasets.
  arXiv  Detail & Related papers  (2020-10-14T19:25:58Z)
• Learning Binary Decision Trees by Argmin Differentiation [34.9154848754842]
  We learn binary decision trees that partition data for some downstream task. We do so by relaxing a mixed-integer program for the discrete parameters. We derive customized algorithms to efficiently compute the forward and backward passes.
  arXiv  Detail & Related papers  (2020-10-09T15:11:28Z)

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.