Building Expressive and Tractable Probabilistic Generative Models: A Review

Sahil Sidheekh, Sriraam Natarajan

Introduction

In the field of generative modeling, a fundamental tension exists between expressivity and tractability. Deep Generative Models (DGMs), such as GANs, VAEs, and Diffusion models, excel at capturing high-dimensional data distributions but often function as "black boxes" where exact probabilistic inference is computationally prohibitive. Conversely, Tractable Probabilistic Models (TPMs) guarantee exact, polynomial-time answers to complex queries—like marginals or conditionals—but historically struggled with the complexity of real-world data like images.

This review explores the emerging synergy between these two paradigms, focusing on Probabilistic Circuits (PCs) as a unified framework to achieve the "best of both worlds": the raw power of deep learning combined with the rigorous reasoning of classical logic.

The Probabilistic Circuit Framework

A Probabilistic Circuit (PC) is a computational graph that represents a joint probability distribution. It is composed of three primary node types:

  • Sum nodes: Representing mixtures or weighted averages of distributions.
  • Product nodes: Representing factorizations or independence assumptions.
  • Leaf nodes: Simple univariate distributions (e.g., Gaussians or Categoricals).

To ensure tractability, PCs must adhere to specific structural constraints. Smoothness requires sum nodes to share the same scope of variables, while decomposability ensures product nodes have disjoint scopes. For more complex tasks like Maximum-a-Posteriori (MAP) inference, determinism—where at most one child of a sum node is non-zero for any input—is often required.

Taxonomy of Probabilistic Circuits (PCs) including learning algorithms and design extensions.

The evolution of PCs has moved from manually engineered structures to automated learning algorithms, ranging from heuristic-based structure learning to modern overparameterized random structures that leverage GPU acceleration.

Bridging the Gap: Hybrid Architectures

The most significant recent advancements involve "building bridges" between PCs and deep learning. These hybrid approaches allow models to scale to high-dimensional data without sacrificing tractability.

A taxonomy of methods for building bridges between Deep Generative Models (DGMs) and Probabilistic Circuits (PCs).

Key hybridization strategies include:

  • Neural Gating: Using neural networks to dynamically predict the weights of sum nodes based on input features, increasing the model's flexibility.
  • Latent Variable Distillation: Employing a DGM (like a VAE) as a "teacher" to help a PC learn complex latent representations, effectively transferring the DGM's expressive power into a tractable format.
  • Probabilistic Flow Circuits: Integrating Normalizing Flows into the leaf nodes or as transformation layers within the circuit, allowing for more complex base distributions.

Key Insights and Scaling

Recent research has shifted the focus from finding the "optimal" sparse structure to utilizing large, Random Structures. By using "Einsum" layers and tensorized parameterizations, PCs can now match the training efficiency of neural networks, achieving significant improvements in scaling.

Furthermore, PCs offer unique functional utilities. They have been successfully applied to certify fairness in machine learning models and perform causal inference (such as backdoor adjustments) in polynomial time—tasks that are typically intractable for standard deep learning models. Unlike standard VAEs, which rely on an Evidence Lower Bound (ELBO), certain PC architectures can compute the exact likelihood, leading to more stable and theoretically grounded training.

Future Directions

Despite these breakthroughs, several challenges remain:

  • Theory of Overparameterization: Understanding why large random PCs generalize effectively remains an open question.
  • Disentanglement: While VAEs produce interpretable latent spaces, the latent variables in PCs are still difficult to disentangle for downstream tasks.
  • Inductive Biases: Incorporating domain-specific symmetries, such as rotation or translation invariance, into the rigid graph structure of a PC is a significant architectural hurdle.

By continuing to fuse the strengths of DGMs and PCs, researchers are moving toward a new generation of models that are both incredibly powerful and mathematically transparent.

Summary updated

Abstract

We present a comprehensive survey of the advancements and techniques in the field of tractable probabilistic generative modeling, primarily focusing on Probabilistic Circuits (PCs). We provide a unified perspective on the inherent trade-offs between expressivity and tractability, highlighting the design principles and algorithmic extensions that have enabled building expressive and efficient PCs, and provide a taxonomy of the field. We also discuss recent efforts to build deep and hybrid PCs by fusing notions from deep neural models, and outline the challenges and open questions that can guide future research in this evolving field.
BibTeX
@inproceedings{sidheekh2024building,
  author = {Sahil Sidheekh and Sriraam Natarajan},
  title = {{Building Expressive and Tractable Probabilistic Generative Models: A Review}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure