# MCMC sampling of decision tree space vs. random forest

A random forest is a collection of decision trees formed by randomly selecting only certain features to build each tree with (and sometimes bagging the training data). Apparently they learn and generalize well. Has anybody done MCMC sampling of the decision tree space or compared them to random forests? I know it might be computationally more expensive to run the MCMC and save all the sampled trees, but I am interested in the theoretical features of this model, not the computational costs. What I mean is something like this:

1. Construct a random decision tree (It would probably perform horribly)
2. Compute likelihood of the tree with something like $P(Tree|Data) \propto P(Data|Tree)$, or perhaps add a $P_{prior}(Tree)$ term.
3. Choose a random step to change the tree and select based on the likelihood $P(Tree|Data)$.
4. Every N steps, save a copy of the current tree
5. Go back to 3 for some large N*M times
6. Use the collection of M saved trees to do prediction

Would this give a similar performance to Random Forests? Note that here we are not throwing away good data or features at any step unlike random forests.

• I'm not sure if this is exactly the sort of procedure you sketch, but there is BART. Here's a link to a PDF Aug 24, 2011 at 20:11

## 2 Answers

This was done some 13 years ago by Chapman, George and McCulloch (1998, JASA). Of course there's been huge literature on Bayesian regression trees that grew out of this idea.

Unfortunately, Chipman et al. in their Bayesian CART approach only extract the most probable tree. They never tried to average over trees and compare the performance to Random Forest and Extra-Trees.

I've just read the BART paper from Chipman. If I understand correctly, it is a Bayesian averaging of K samples over a collection of m tree. It is interesting in many ways and does seems to perform really good. When m='1', it is a simple Bayesian averaging of K samples of 1 tree, coming from the posterior. However, not much test have been done on that particular aspect. And I would still be interested in knowing how does Random Forest or Extra-Trees compare to the true Bayes model.