Divide, Conquer, Combine Bayesian Decision Tree Sampling
Jodie A. Cochrane Adrian Wills Sarah J. Johnson
Decision trees are commonly used predictive models due to their flexibility
and interpretability. This paper is directed at quantifying the uncertainty of
decision tree predictions by employing a Bayesian inference approach. This is
challenging because these approaches need to explore both the tree structure
space and the space of decision parameters associated with each tree structure.
This has been handled by using Markov Chain Monte Carlo (MCMC) methods, where a
Markov Chain is constructed to provide samples from the desired Bayesian
estimate. Importantly, the structure and the decision parameters are tightly
coupled; small changes in the tree structure can demand vastly different
decision parameters to provide accurate predictions. A challenge for existing
MCMC approaches is proposing joint changes in both the tree structure and the
decision parameters that result in efficient sampling. This paper takes a
different approach, where each distinct tree structure is associated with a
unique set of decision parameters. The proposed approach, entitled DCC-Tree, is
inspired by the work in Zhou et al. [23] for probabilistic programs and
Cochrane et al. [4] for Hamiltonian Monte Carlo (HMC) based sampling for
decision trees. Results show that DCC-Tree performs comparably to other
HMC-based methods and better than existing Bayesian tree methods while
improving on consistency and reducing the per-proposal complexity.