In generative modeling, researchers often face a "pick two" dilemma between expressive power, exact inference, and fast sampling. As Dinh et al. observe, most architectures sacrifice at least one: autoregressive models are expressive but slow to sample; Variational Autoencoders (VAEs) offer fast sampling but rely on approximate inference; and Generative Adversarial Networks (GANs) are powerful but difficult to evaluate.
This tension defines the expressivity-tractability trade-off. On one end, deep neural networks can approximate nearly any distribution but act as "black boxes" where calculating a simple marginal probability is NP-hard. On the other end, tractable probabilistic models (TPMs) provide rigorous guarantees for exact reasoning but often struggle to capture the nuances of high-dimensional data like images or audio.
The Problem of the Partition Function
The core of this trade-off lies in the normalization constant, or partition function. For a model to represent a valid probability distribution, the sum of all possible outcomes must equal one. Sohl-Dickstein et al. note that while simple distributions are easy to normalize, they cannot capture the complex manifolds of real-world data. Conversely, highly flexible models—like Energy-Based Models (EBMs)—often suffer from intractable normalization constants, making them notoriously difficult to train and sample from, as discussed by Yu et al..
To bypass this, researchers have developed two primary strategies: imposing structural constraints to ensure tractability by design, or using iterative and invertible transformations to maintain mathematical control.
Tractability by Design: Probabilistic Circuits
One way to ensure tractability is to build models out of components that are "tractable by construction." Sum-Product Networks (SPNs) and Probabilistic Circuits (PCs) achieve this by using specific structural properties like decomposability and determinism.
As Shao et al. explain, these models allow for exact, efficient computation of marginals and conditionals—tasks that are mathematically impossible in standard deep models. However, these constraints can limit raw representational power. To bridge this gap, Butz et al. introduced Deep Convolutional Sum-Product Networks (DCSPNs), which adopt the architecture of CNNs while maintaining the rigorous framework of probabilistic graphical models. Similarly, Shih et al. proposed HyperSPNs, which use a small neural network to generate the weights of a large PC, allowing the model to benefit from deep expressivity while retaining a tiny memory footprint and exact inference.
Tractability through Transformation: Flows and CDFs
Another approach involves Normalizing Flows, which transform a simple distribution into a complex one through a series of invertible mappings. By ensuring the Jacobian of these transformations is easy to compute, models like Real NVP achieve exact likelihood calculation. Chan et al. further refined this with LU-Net, using matrix factorization to make these calculations even more efficient.
A more direct route to tractability involves modeling the Cumulative Distribution Function (CDF) rather than the density itself. Li et al. argue that by designing a neural network to represent a CDF, one can use the Fundamental Theorem of Calculus to enable exact likelihood evaluation and fast sampling via the inverse transform method. This bypasses the partition function problem entirely.
The Hybrid Middle Ground
Recent work suggests that the trade-off is not a binary choice but a spectrum. Dong et al. proposed partitioning variables into a "complex" set handled by neural networks and a "tractable" set handled by TPMs. This hybrid approach allows for non-linear dependencies while still permitting efficient "cutset" sampling.
Similarly, Xie et al. developed CoopFlow, which uses a Normalizing Flow to "jump-start" the sampling process for an Energy-Based Model. This marriage of techniques aims to provide the synthesis speed of flows with the expressive density modeling of EBMs.
Why Tractability Matters for Generalization
The push for tractability isn't just about computational speed; it's about the reliability of the model. Novikov et al. point out that "black box" models often lack functional completeness, meaning they cannot perform basic tasks like calculating marginals or cumulative densities, which are essential for comprehensive probabilistic analysis.
Furthermore, Zhu et al. argue that there is a fundamental trade-off between perfect mathematical approximation and sample complexity. To ensure a model can generalize from finite data without succumbing to the "curse of dimensionality," researchers must often accept a looser approximation of the target distribution. As Bengio noted in the context of the Neural Autoregressive Distribution Estimator (NADE), the goal is to achieve exact likelihoods without sacrificing the representational power needed to generalize to complex, real-world data.
Key Foundational Work
Discussion of "The Neural Autoregressive Distribution Estimator" (2011) — contributed 2 concept elements to this direction.
Feature Selection and Dualities in Maximum Entropy Discrimination (2000) — contributed 1 concept elements to this direction.