An accelerated algorithm
for MCMC Bayesian decision tree sampling
In: Workshop Ensemble Methods, 4-5 march 2005.
We present a novel type of MCMC sampler intended to deal with a Bayesian framework for classification and regression trees. Typically, it is hard in practice to sample from the Bayesian posterior on trees (in order to approximate posterior-averaged or MAP estimators) by naive MCMC methods, because the space of trees is huge and the posterior presents a lot of local minima. The algorithm we introduce allows, for a large class of prior distributions, to develop an accelerated MCMC algorithm. The key point is the exact computation of some conditional posterior averages over tree structures at each step. This results in a dramatic increase of the number of models actually taken into account. It can be used in a variety of situations for Bayesian inference and we show its practical relevance on a demonstration example.