# Probability Distribution on Full Rooted Trees

arXiv: https://arxiv.org/abs/2109.12825 · HTML: https://mlsanity.com/paper/2109.12825/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 18 references that are in the map.
- First posted on arXiv 27 Sep 2021.

## Builds on (most cited first, 2 of 2)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Bayesian Context Trees: Modelling and exact inference for discrete time series](https://mlsanity.com/paper/2007.14900/) (2020)

## Built on by (most cited first, 9 of 9)

- [Batch Updating of a Posterior Tree Distribution over a Meta-Tree](https://mlsanity.com/paper/2303.09705/) (2023)
- [Soft Bayesian Context Tree Models for Real-Valued Time Series](https://mlsanity.com/paper/2601.11079/) (2026)
- [Probability Distribution on Rooted Trees](https://mlsanity.com/paper/2201.09460/) (2022)
- [Stochastic 2D Signal Generative Model with Wavelet Packets Basis Regarded as a Random Variable and Bayes Optimal Processing](https://mlsanity.com/paper/2202.00568/) (2022)
- [Prediction Algorithms Achieving Bayesian Decision Theoretical Optimality Based on Decision Trees as Data Observation Processes](https://mlsanity.com/paper/2306.07060/) (2023)
- [Boosting-Based Sequential Meta-Tree Ensemble Construction for Improved Decision Trees](https://mlsanity.com/paper/2402.06386/) (2024)
- [Variational Bayesian Methods for a Tree-Structured Stick-Breaking Process Mixture of Gaussians by Application of the Bayes Codes for Context Tree Models](https://mlsanity.com/paper/2405.00385/) (2024)
- [Variable Splitting Binary Tree Models Based on Bayesian Context Tree Models for Time Series Segmentation](https://mlsanity.com/paper/2601.16112/) (2026)
- [A Mixture Autoregressive Image Generative Model on Quadtree Regions for Gaussian Noise Removal via Variational Bayes and Gradient Methods](https://mlsanity.com/paper/2605.11585/) (2026)

## Abstract (arXiv)

The recursive and hierarchical structure of full rooted trees is applicable to represent statistical models in various areas, such as data compression, image processing, and machine learning. In most of these cases, the full rooted tree is not a random variable; as such, model selection to avoid overfitting becomes problematic. A method to solve this problem is to assume a prior distribution on the full rooted trees. This enables the optimal model selection based on the Bayes decision theory. For example, by assigning a low prior probability to a complex model, the maximum a posteriori estimator prevents the selection of the complex one. Furthermore, we can average 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 suitable for calculating the properties of our distribution using recursive functions, such as the mode, expectation, and posterior distribution. Although such distributions have been proposed in previous studies, they are only applicable to specific applications. Therefore, we extract their mathematically essential components and derive new generalized methods to calculate the expectation, posterior distribution, etc.