Given i.i.d. data from an unknown distribution, we consider the problem of predicting future items. An adaptive way to estimate the probability density is to recursively subdivide the domain to an appropriate data-dependent granularity. In Bayesian inference one assigns a data-independent prior probability to \subdivide", which leads to a prior over inflnite(ly many) trees. We derive an exact, fast, and simple inference algorithm for such a prior, for the data evidence, the predictive distribution, the efiective model dimension, moments, and other quantities. We prove asymptotic convergence and consistency results, and illustrate the behavior of our model on some prototypical functions.
['Marcus Hutter']
Exact Non-Parametric Bayesian Inference on Infinite Trees