Probability Distribution on Full Rooted Trees

• URL: http://arxiv.org/abs/2109.12825v1
• Date: Mon, 27 Sep 2021 06:51:35 GMT
• Title: Probability Distribution on Full Rooted Trees
• Authors: Yuta Nakahara, Shota Saito, Akira Kamatsuka, Toshiyasu Matsushima
• Abstract summary: 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.
• Score: 2.1506382989223782
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The recursive and hierarchical structure of full rooted trees is used in various areas such as data compression, image processing, and machine learning. In most of these studies, the full rooted tree is not a random variable. It causes a problem of model selection to avoid overfitting. One method to solve it is to assume a prior distribution on the full rooted trees. It enables us to avoid overfitting based on the Bayes decision theory. For example, by assigning a low prior probability on a complex model, the MAP estimator prevents the overfitting. Further, we can avoid it by averaging all the models weighted by their posteriors. In this paper, we propose a probability distribution on a set of full rooted trees. Its parametric representation is well suited to calculate the properties of our distribution by recursive functions: the mode, the expectation, the posterior distribution, etc. Although some previous studies have proposed such distributions, they are for specific applications. Therefore, we extract the mathematically essential part of them and derive new generalized methods to calculate the expectation, the posterior distribution, etc.

Related papers

• Treeffuser: Probabilistic Predictions via Conditional Diffusions with Gradient-Boosted Trees [39.9546129327526]
  Treeffuser is an easy-to-use method for probabilistic prediction on tabular data. Treeffuser learns well-calibrated predictive distributions and can handle a wide range of regression tasks. We demonstrate its versatility with an application to inventory allocation under uncertainty using sales data from Walmart.
  arXiv  Detail & Related papers  (2024-06-11T18:59:24Z)
• Rejection via Learning Density Ratios [50.91522897152437]
  Classification with rejection emerges as a learning paradigm which allows models to abstain from making predictions. We propose a different distributional perspective, where we seek to find an idealized data distribution which maximizes a pretrained model's performance. Our framework is tested empirically over clean and noisy datasets.
  arXiv  Detail & Related papers  (2024-05-29T01:32:17Z)
• 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)
• An Approximation Method for Fitted Random Forests [0.0]
  We study methods that approximate each fitted tree in the Random Forests model using the multinomial allocation of the data points to the leafs. Specifically, we begin by studying whether fitting a multinomial logistic regression helps reduce the size while preserving the prediction quality.
  arXiv  Detail & Related papers  (2022-07-05T17:28:52Z)
• Distributional Gradient Boosting Machines [77.34726150561087]
  Our framework is based on XGBoost and LightGBM. We show that our framework achieves state-of-the-art forecast accuracy.
  arXiv  Detail & Related papers  (2022-04-02T06:32:19Z)
• Probability Distribution on Rooted Trees [1.3955252961896318]
  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.
  arXiv  Detail & Related papers  (2022-01-24T05:13:58Z)
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
  We design and analyze an algorithm that boosts the error exponent by at least 40% when $rho$ is at least $0.8$. Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph.
  arXiv  Detail & Related papers  (2021-10-27T10:45:21Z)
• 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)
• 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)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  We formulate a method that learns a finite set of statistics from each return distribution via neural networks. Our method can be interpreted as implicitly matching all orders of moments between a return distribution and its Bellman target. Experiments on the suite of Atari games show that our method outperforms the standard distributional RL baselines.
  arXiv  Detail & Related papers  (2020-07-24T05:18:17Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  We study BQO under distributional uncertainty in which the underlying probability distribution is unknown except for a limited set of its i.i.d. samples. A standard BQO approach maximizes the Monte Carlo estimate of the true expected objective given the fixed sample set. We propose a novel posterior sampling based algorithm, namely distributionally robust BQO (DRBQO) for this purpose.
  arXiv  Detail & Related papers  (2020-01-19T12:00:33Z)

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.