Probability Distribution on Rooted Trees

Yuta Nakahara, Shota Saito, Akira Kamatsuka, Toshiyasu Matsushima

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publication2022 IEEE International Symposium on Information Theory, ISIT 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781665421591
Publication statusPublished - 2022
Event2022 IEEE International Symposium on Information Theory, ISIT 2022 - Espoo, Finland
Duration: 2022 Jun 262022 Jul 1

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Conference2022 IEEE International Symposium on Information Theory, ISIT 2022


  • Bayes decision theory
  • Bayes statistics
  • recursive algorithm
  • rooted trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modelling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Probability Distribution on Rooted Trees'. Together they form a unique fingerprint.

Cite this