# Single MCMC Chain Parallelisation on Decision Trees

arXiv: https://arxiv.org/abs/2207.12688 · HTML: https://mlsanity.com/paper/2207.12688/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 34 references that are in the map.
- First posted on arXiv 26 Jul 2022.

## Builds on (most cited first, 3 of 3)

- [On Theory for BART](https://mlsanity.com/paper/1810.00787/) (2018)
- [Parallel Markov Chain Monte Carlo via Spectral Clustering](https://mlsanity.com/paper/1605.09454/) (2016)
- [Continuous-Time Birth-Death MCMC for Bayesian Regression Tree Models](https://mlsanity.com/paper/1904.09339/) (2019)

## Built on by (most cited first, 2 of 2)

- [Parallel Approaches to Accelerate Bayesian Decision Trees](https://mlsanity.com/paper/2301.09090/) (2023)
- [Bayesian Decision Trees Inspired from Evolutionary Algorithms](https://mlsanity.com/paper/2305.18774/) (2023)

## Abstract (arXiv)

Decision trees are highly famous in machine learning and usually acquire state-of-the-art performance. Despite that, well-known variants like CART, ID3, random forest, and boosted trees miss a probabilistic version that encodes prior assumptions about tree structures and shares statistical strength between node parameters. Existing work on Bayesian decision trees depend on Markov Chain Monte Carlo (MCMC), which can be computationally slow, especially on high dimensional data and expensive proposals. In this study, we propose a method to parallelise a single MCMC decision tree chain on an average laptop or personal computer that enables us to reduce its run-time through multi-core processing while the results are statistically identical to conventional sequential implementation. We also calculate the theoretical and practical reduction in run time, which can be obtained utilising our method on multi-processor architectures. Experiments showed that we could achieve 18 times faster running time provided that the serial and the parallel implementation are statistically identical.