Probability Distribution on Rooted Trees

• URL: http://arxiv.org/abs/2201.09460v1
• Date: Mon, 24 Jan 2022 05:13:58 GMT
• Title: Probability Distribution on Rooted Trees
• Authors: Yuta Nakahara, Shota Saito, Akira Kamatsuka, Toshiyasu Matsushima
• Abstract summary: hierarchical expressive capability of rooted trees is applicable to represent statistical models in various areas, such as data compression, image processing, and machine learning. One unified approach to solve this is a Bayesian approach, on which the rooted tree is regarded as a random variable and a direct loss function can be assumed on the selected model or the predicted value for a new data point. In this paper, we propose a generalized probability distribution for any rooted trees in which only the maximum number of child nodes and the maximum depth are fixed.
• Score: 1.3955252961896318
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The hierarchical and recursive expressive capability of rooted trees is applicable to represent statistical models in various areas, such as data compression, image processing, and machine learning. On the other hand, such hierarchical expressive capability causes a problem in tree selection to avoid overfitting. One unified approach to solve this is a Bayesian approach, on which the rooted tree is regarded as a random variable and a direct loss function can be assumed on the selected model or the predicted value for a new data point. However, all the previous studies on this approach are based on the probability distribution on full trees, to the best of our knowledge. In this paper, we propose a generalized probability distribution for any rooted trees in which only the maximum number of child nodes and the maximum depth are fixed. Furthermore, we derive recursive methods to evaluate the characteristics of the probability distribution without any approximations.

Related papers

• Decision Trees for Interpretable Clusters in Mixture Models and Deep Representations [5.65604054654671]
  We introduce the notion of an explainability-to-noise ratio for mixture models. We propose an algorithm that takes as input a mixture model and constructs a suitable tree in data-independent time. We prove upper and lower bounds on the error rate of the resulting decision tree.
  arXiv  Detail & Related papers  (2024-11-03T14:00:20Z)
• Ensembles of Probabilistic Regression Trees [46.53457774230618]
  Tree-based ensemble methods have been successfully used for regression problems in many applications and research studies. We study ensemble versions of probabilisticregression trees that provide smooth approximations of the objective function by assigningeach observation to each region with respect to a probability distribution.
  arXiv  Detail & Related papers  (2024-06-20T06:51:51Z)
• 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)
• Prediction Algorithms Achieving Bayesian Decision Theoretical Optimality Based on Decision Trees as Data Observation Processes [1.2774526936067927]
  This paper uses trees to represent data observation processes behind given data. We derive the statistically optimal prediction, which is robust against overfitting. We solve this by a Markov chain Monte Carlo method, whose step size is adaptively tuned according to a posterior distribution for the trees.
  arXiv  Detail & Related papers  (2023-06-12T12:14:57Z)
• Bayesian Decision Trees via Tractable Priors and Probabilistic Context-Free Grammars [7.259767735431625]
  We propose a new criterion for training Bayesian Decision Trees. BCART-PCFG can efficiently sample decision trees from a posterior distribution across trees given the data. We find that trees sampled via BCART-PCFG perform comparable to or better than greedily-constructed Decision Trees.
  arXiv  Detail & Related papers  (2023-02-15T00:17:41Z)
• Social Interpretable Tree for Pedestrian Trajectory Prediction [75.81745697967608]
  We propose a tree-based method, termed as Social Interpretable Tree (SIT), to address this multi-modal prediction task. A path in the tree from the root to leaf represents an individual possible future trajectory. Despite the hand-crafted tree, the experimental results on ETH-UCY and Stanford Drone datasets demonstrate that our method is capable of matching or exceeding the performance of state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-26T12:18:44Z)
• A cautionary tale on fitting decision trees to data from additive models: generalization lower bounds [9.546094657606178]
  We study the generalization performance of decision trees with respect to different generative regression models. This allows us to elicit their inductive bias, that is, the assumptions the algorithms make (or do not make) to generalize to new data. We prove a sharp squared error generalization lower bound for a large class of decision tree algorithms fitted to sparse additive models.
  arXiv  Detail & Related papers  (2021-10-18T21:22:40Z)
• Probability Distribution on Full Rooted Trees [2.1506382989223782]
  In data compression, image processing, and machine learning, the full rooted tree is not a random variable. One method to solve it is to assume a prior distribution on the full rooted trees. In this paper, we propose a probability distribution on a set of full rooted trees.
  arXiv  Detail & Related papers  (2021-09-27T06:51:35Z)
• Probabilistic Gradient Boosting Machines for Large-Scale Probabilistic Regression [51.770998056563094]
  Probabilistic Gradient Boosting Machines (PGBM) is a method to create probabilistic predictions with a single ensemble of decision trees. We empirically demonstrate the advantages of PGBM compared to existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-03T08:32:13Z)
• 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)

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.