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 (n^n-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.

@inproceedings{SelvamAISTATS23,
  author  = {Selvam, Nikil Roashan and Zhang, Honghua and Van den Broeck, Guy},
  title     = {Mixtures of All Trees},
  booktitle = {Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS)},
  month     = 4,
  year      = {2023},
  url       = "http://starai.cs.ucla.edu/papers/SelvamAISTATS23.pdf",
  code    = "https://github.com/UCLA-StarAI/MoAT",
  keywords  = {conference,selective}
}