Continuous-Time Birth-Death MCMC for Bayesian Regression Tree Models
arXiv:1904.09339
Abstract
Decision trees are flexible models that are well suited for many statistical regression problems. In a Bayesian framework for regression trees, Markov Chain Monte Carlo (MCMC) search algorithms are required to generate samples of tree models according to their posterior probabilities. The critical component of such an MCMC algorithm is to construct good Metropolis-Hastings steps for updating the tree topology. However, such algorithms frequently suffering from local mode stickiness and poor mixing. As a result, the algorithms are slow to converge. Hitherto, authors have primarily used discrete-time birth/death mechanisms for Bayesian (sums of) regression tree models to explore the model space. These algorithms are efficient only if the acceptance rate is high which is not always the case. Here we overcome this issue by developing a new search algorithm which is based on a continuous-time birth-death Markov process. This search algorithm explores the model space by jumping between parameter spaces corresponding to different tree structures. In the proposed algorithm, the moves between models are always accepted which can dramatically improve the convergence and mixing properties of the MCMC algorithm. We provide theoretical support of the algorithm for Bayesian regression tree models and demonstrate its performance.
arXiv commentPublished at http://jmlr.org/papers/v21/19-307 in the Journal of Machine Learning Research (https://www.jmlr.org)
References in corpus (9)
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Analysis of a Random Forests Model
- BDgraph: An R Package for Bayesian Structure Learning in Graphical Models
- To tune or not to tune the number of trees in random forest?
- Random Forests, Decision Trees, and Categorical Predictors: The "Absent Levels" Problem
- Thompson sampling with the online bootstrap
- Top-down particle filtering for Bayesian decision trees
- Efficient sampling of Gaussian graphical models using conditional Bayes factors
- The scalable Birth-Death MCMC Algorithm for Mixed Graphical Model Learning with Application to Genomic Data Integration