# Mixtures of All Trees

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 32 references that are in the map.
- First posted on arXiv 27 Feb 2023.

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

- [BIVA: A Very Deep Hierarchy of Latent Variables for Generative Modeling](https://mlsanity.com/paper/1902.02102/) (2019)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [Probabilistic Generating Circuits](https://mlsanity.com/paper/2102.09768/) (2021)
- [Bucket Elimination: A Unifying Framework for Several Probabilistic Inference](https://mlsanity.com/paper/1302.3572/) (2013)
- [Fast Mixing Markov Chains for Strongly Rayleigh Measures, DPPs, and Constrained Sampling](https://mlsanity.com/paper/1608.01008/) (2016)
- [Sampling Random Spanning Trees Faster than Matrix Multiplication](https://mlsanity.com/paper/1611.07451/) (2016)
- [Solving #SAT and Bayesian Inference with Backtracking Search](https://mlsanity.com/paper/1401.3458/) (2014)
- [Flexible Modeling of Diversity with Strongly Log-Concave Distributions](https://mlsanity.com/paper/1906.05413/) (2019)
- [CrossCat: A Fully Bayesian Nonparametric Method for Analyzing Heterogeneous, High Dimensional Data](https://mlsanity.com/paper/1512.01272/) (2015)
- [Latent Tree Analysis](https://mlsanity.com/paper/1610.00085/) (2016)

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

- [Polynomial Semantics of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2402.09085/) (2024)
- [Distribution Learning Meets Graph Structure Sampling](https://mlsanity.com/paper/2405.07914/) (2024)
- [Probably Approximately Correct Maximum A Posteriori Inference](https://mlsanity.com/paper/2601.16083/) (2026)

## Abstract (arXiv)

Tree-shaped graphical models are widely used for their tractability. However, they unfortunately lack expressive power as they require committing to a particular sparse dependency structure. We propose a novel class of generative models called mixtures of all trees: that is, a mixture over all possible (nn-2) tree-shaped graphical models over n variables. We show that it is possible to parameterize this Mixture of All Trees (MoAT) model compactly (using a polynomial-size representation) in a way that allows for tractable likelihood computation and optimization via stochastic gradient descent. Furthermore, by leveraging the tractability of tree-shaped models, we devise fast-converging conditional sampling algorithms for approximate inference, even though our theoretical analysis suggests that exact computation of marginals in the MoAT model is NP-hard. Empirically, MoAT achieves state-of-the-art performance on density estimation benchmarks when compared against powerful probabilistic models including hidden Chow-Liu Trees.