# Bayesian Decision Trees via Tractable Priors and Probabilistic Context-Free Grammars

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 42 references that are in the map.
- First posted on arXiv 15 Feb 2023.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Why do tree-based models still outperform deep learning on tabular data?](https://mlsanity.com/paper/2207.08815/) (2022)
- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [Generative Augmented Flow Networks](https://mlsanity.com/paper/2210.03308/) (2022)
- [A Variational Perspective on Generative Flow Networks](https://mlsanity.com/paper/2210.07992/) (2022)
- [GP-BART: a novel Bayesian additive regression trees approach using Gaussian processes](https://mlsanity.com/paper/2204.02112/) (2022)
- [A Mixing Time Lower Bound for a Simplified Version of BART](https://mlsanity.com/paper/2210.09352/) (2022)
- [Top-down particle filtering for Bayesian decision trees](https://mlsanity.com/paper/1303.0561/) (2013)
- [MABSplit: Faster Forest Training Using Multi-Armed Bandits](https://mlsanity.com/paper/2212.07473/) (2022)
- [Model Mixing Using Bayesian Additive Regression Trees](https://mlsanity.com/paper/2301.02296/) (2023)
- [Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks](https://mlsanity.com/paper/2111.01853/) (2021)
- [Improving Generative Flow Networks with Path Regularization](https://mlsanity.com/paper/2209.15092/) (2022)
- [The Taxicab Sampler: MCMC for Discrete Spaces with Application to Tree Models](https://mlsanity.com/paper/2107.07313/) (2021)
- [Adaptive Bayesian Reticulum](https://mlsanity.com/paper/1912.05901/) (2019)

## Abstract (arXiv)

Decision Trees are some of the most popular machine learning models today due to their out-of-the-box performance and interpretability. Often, Decision Trees models are constructed greedily in a top-down fashion via heuristic search criteria, such as Gini impurity or entropy. However, trees constructed in this manner are sensitive to minor fluctuations in training data and are prone to overfitting. In contrast, Bayesian approaches to tree construction formulate the selection process as a posterior inference problem; such approaches are more stable and provide greater theoretical guarantees. However, generating Bayesian Decision Trees usually requires sampling from complex, multimodal posterior distributions. Current Markov Chain Monte Carlo-based approaches for sampling Bayesian Decision Trees are prone to mode collapse and long mixing times, which makes them impractical. In this paper, we propose a new criterion for training Bayesian Decision Trees. Our criterion gives rise to BCART-PCFG, which can efficiently sample decision trees from a posterior distribution across trees given the data and find the maximum a posteriori (MAP) tree. Learning the posterior and training the sampler can be done in time that is polynomial in the dataset size. Once the posterior has been learned, trees can be sampled efficiently (linearly in the number of nodes). At the core of our method is a reduction of sampling the posterior to sampling a derivation from a probabilistic context-free grammar. We find that trees sampled via BCART-PCFG perform comparable to or better than greedily-constructed Decision Trees in classification accuracy on several datasets. Additionally, the trees sampled via BCART-PCFG are significantly smaller -- sometimes by as much as 20x.