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.
翻译:树形图模型因易于计算而被广泛使用。然而,它们缺乏表达能力,因为需要对特定的稀疏依赖结构进行承诺。我们提出了一种新的生成模型类,称为混合所有树:即,对于$n$个变量,混合所有可能的($n^{n-2}$个)树形图模型。我们证明了可以以紧凑的方式(使用多项式大小的表示)对这种模型进行参数化,从而通过随机梯度下降进行可计算性和优化。此外,通过利用树形模型的可计算性,我们设计了快速收敛的条件采样算法,用于近似推断,尽管我们的理论分析表明在MoAT模型中精确计算边际分布是NP难问题。在实证方面,与强大的概率模型(包括隐Chow-Liu树)相比,MoAT在密度估计基准测试中实现了最先进的性能。