Posterior concentration for Bayesian regression trees and forests

From MaRDI portal
Publication:2215727



Abstract: Since their inception in the 1980's, regression trees have been one of the more widely used non-parametric prediction methods. Tree-structured methods yield a histogram reconstruction of the regression surface, where the bins correspond to terminal nodes of recursive partitioning. Trees are powerful, yet susceptible to over-fitting. Strategies against overfitting have traditionally relied on pruning greedily grown trees. The Bayesian framework offers an alternative remedy against overfitting through priors. Roughly speaking, a good prior charges smaller trees where overfitting does not occur. While the consistency of random histograms, trees and their ensembles has been studied quite extensively, the theoretical understanding of the Bayesian counterparts has been missing. In this paper, we take a step towards understanding why/when do Bayesian trees and their ensembles not overfit. To address this question, we study the speed at which the posterior concentrates around the true smooth regression function. We propose a spike-and-tree variant of the popular Bayesian CART prior and establish new theoretical results showing that regression trees (and their ensembles) (a) are capable of recovering smooth regression surfaces, achieving optimal rates up to a log factor, (b) can adapt to the unknown level of smoothness and (c) can perform effective dimension reduction when p>n. These results provide a piece of missing theoretical evidence explaining why Bayesian trees (and additive variants thereof) have worked so well in practice.


The authors consider the already classical nonparametric regression model \(Y_i=f_0(\mathbf{x} _i)+\epsilon_i\), where \(\mathbf{x}_i=(x_{i1},\dots, x_{ip})'\), \(1\leq i\leq n\), are \(p\) potential covariates, \(Y_i\) are the responses and \(\epsilon _i\) are the noise variables. The statistical problem is to recover \(f_0\) from the samples (\(\mathbf{x}_i\), \(Y_i\)). In the present paper, from the class of nonparametric prediction methods, Bayesian regression trees and forests are considered and studied. As stated by the authors, the goal of this paper is to provide optimality results for Bayesian regression trees. They introduce a new variant of the Bayesian CART prior for dimension reduction and model-free variable selection, the spike-and-tree prior. A set of theoretical results is provided. Some basics are presented in the second section and the definitions of recursive partitions in the third one. Notions as valid partitions, balanced partitions, tree partitions, \(k\)-d tree partitions, tree-structured step functions are explained. In the fourth section one introduces the concept of spike-and-tree priors and one shows that the posterior distribution under the Bayesian CART prior has optimal properties. A detailed analysis of the collective behavior of partitioning cells generated by individual trees is done in the fifth section. A result regarding the posterior concentration for Bayesian additive regression trees in case \(f_0\) has an additive structure is presented in the sixth section. There follow some implementation considerations as well as a short discussion on the results. The eighth section and a supplementary material entitled: Supplement to ``Posterior concentration for Bayesian regression trees and forests, \url{doi:10.1214/19-AOS1879SUPP} contain detailed proofs of the results.



Cites work


Cited in
(43)


Describes a project that uses

Uses Software






This page was built for publication: Posterior concentration for Bayesian regression trees and forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2215727)