Bayesian trees and forests for unsupervised learning and their spatial adaptation properties

Tree-based methods are popular nonparametric tools for capturing spatial heterogeneity and making predictions in multivariate problems. In unsupervised learning, trees and their ensembles have also been applied to a wide range of statistical inference tasks, such as multi-resolution sketching of distributional variations, localization of high-density regions, and design of efficient data compression schemes. In this talk, we will focus on the density estimation problem---a fundamental one in unsupervised learning. We consider the optional P{\'o}lya tree (Wong and Ma, 2010) prior and the Dirichlet prior or their variations on individual trees. First we show that Bayesian density trees can achieve minimax (up to a logarithmic term) convergence over the anisotropic Besov class, which implies that tree based methods can adapt to spatially inhomogeneous features of the underlying density function, and can achieve fast convergence as the dimension increases. We will also introduce a novel Bayesian model for forests, and show that for a class of anisotropic H{\"o}lder continuous functions, such type of density forests can achieve faster convergence than trees. The convergence rate is adaptive in the sense that to achieve such a rate we do not need any prior knowledge of the smoothness level of the density. The Bayesian framework naturally provides a stochastic search algorithm over either the tree space or the forest one. For both Bayesian density trees and forests, we will provide several numerical results to illustrate their performance in the moderately high-dimensional case.