Sum-Product Networks: A New Deep Architecture

Hoifung Poon, Pedro Domingos

TL;DR

Sum-Product Networks (SPNs) are a new class of deep probabilistic models that guarantee efficient, exact inference. By representing probability distributions as directed acyclic graphs of sums and products, SPNs bypass the intractable partition functions that plague traditional graphical models, enabling faster learning and superior performance on tasks like image completion.

What Problem Does This Paper Address?

In the world of probabilistic modeling, there is a classic tug-of-war between expressivity and tractability. Graphical models like Markov Networks are great at representing complex dependencies, but calculating their "partition function"—the normalization constant needed to turn raw scores into probabilities—is often computationally impossible (specifically, #P-complete).

Deep architectures like Deep Belief Networks (DBNs) attempt to solve this by adding layers of hidden variables, but they introduce a new headache: inference becomes so hard that researchers have to rely on slow, approximate methods like Gibbs sampling. Furthermore, training these deep models is notoriously difficult due to "gradient diffusion," where the learning signal vanishes as it propagates through many layers. Poon and Domingos ask a fundamental question: Can we design a deep architecture where the partition function is tractable by construction?

Methods

The authors introduce Sum-Product Networks (SPNs). An SPN is a rooted directed acyclic graph (DAG) where the leaves are variable indicators (e.g., $x_i$ and its negation $\bar{x}_i$) and internal nodes are either sums or products.

  • Sum nodes represent mixtures over subsets of variables.
  • Product nodes represent features or mixture components.
  • Edges from sum nodes have weights, representing the probability of choosing a particular mixture component.
Examples of SPNs: A naive Bayes mixture (top) and a junction tree implementation (bottom).

The magic of SPNs lies in two properties: completeness and consistency. If an SPN meets these criteria, it is "valid," meaning it correctly computes the probability of any evidence in time linear to the size of the network.

For learning, the authors propose a "Hard EM" algorithm. Instead of using standard marginal inference (which can lead to vanishing gradients in deep nets), they use Most Probable Explanation (MPE) inference. This ensures that updates remain "unit size" regardless of depth, allowing them to successfully train networks with over 30 layers.

Datasets

The authors evaluated SPNs primarily on image completion—a grueling test for deep architectures that requires capturing high-level structural regularities.

  • Caltech-101: A diverse dataset of 101 object categories (faces, dolphins, helicopters, etc.).
  • Olivetti Face Dataset: A standard benchmark containing 400 grayscale faces.

They compared SPNs against state-of-the-art deep models (DBNs and Deep Boltzmann Machines), as well as classical baselines like Principal Component Analysis (PCA) and Nearest Neighbor (NN).

Key Insights and Ideas

  • Sums as Hidden Variables: A key "aha" moment is that sum nodes can be viewed as marginalizing out implicit hidden variables. This allows SPNs to be seen as a massive, hierarchical mixture model where components are reused across different branches.
  • Tractability by Design: Rather than building a model and then struggling to perform inference, SPNs flip the script. They define a model class where the distributive law is baked into the graph structure, ensuring that the partition function can always be computed efficiently.
  • Overcoming Gradient Diffusion: By using "Hard EM" (MPE-based updates), the authors show that deep learning doesn't have to suffer from vanishing signals. This allowed them to train a 36-layer network that outperformed shallower competitors.
  • Biological Parallel: The authors note a striking analogy to the human cortex. Sum nodes act like excitatory pyramidal neurons, while max nodes (used in MPE inference) act like inhibitory stellate neurons that select the strongest signal for propagation.

Key Results

SPNs dominated the competition in both accuracy and speed:

  • Accuracy: On Caltech-101 image completion, SPNs achieved significantly lower Mean Squared Error (MSE) than DBMs, DBNs, and PCA. Qualitatively, SPN completions were much more coherent, correctly hypothesizing the location of eyes, hair, and mouths.
  • Speed: SPNs are at least an order of magnitude faster. Training on Caltech faces took just 6 minutes on 20 CPUs, whereas DBNs/DBMs can take anywhere from 30 hours to a full week.
  • Inference: Finding the MPE completion of an image took less than a second and provided an exact result, whereas DBNs require minutes of approximate sampling.
Qualitative comparison of face completions. SPNs (second row) produce much more realistic results than DBMs or DBNs.

Limitations and Future Work

While powerful, SPNs are not without flaws. The authors noted that completed images can sometimes look "blocky," likely a byproduct of the rectangular region decomposition used to initialize the network structure.

Future work includes developing better structure learning algorithms (rather than starting with a dense, predefined architecture), extending SPNs to handle sequential data (like text or video), and exploring "invalid" SPNs that might serve as efficient approximations for even more complex distributions.

Summary updated

Abstract

The key limiting factor in graphical model inference and learning is the complexity of the partition function. We thus ask the question: what are general conditions under which the partition function is tractable? The answer leads to a new kind of deep architecture, which we call sum-product networks (SPNs). SPNs are directed acyclic graphs with variables as leaves, sums and products as internal nodes, and weighted edges. We show that if an SPN is complete and consistent it represents the partition function and all marginals of some graphical model, and give semantics to its nodes. Essentially all tractable graphical models can be cast as SPNs, but SPNs are also strictly more general. We then propose learning algorithms for SPNs, based on backpropagation and EM. Experiments show that inference and learning with SPNs can be both faster and more accurate than with standard deep networks. For example, SPNs perform image completion better than state-of-the-art deep networks for this task. SPNs also have intriguing potential connections to the architecture of the cortex.
BibTeX
@inproceedings{poon2011sum,
  author = {Hoifung Poon and Pedro Domingos},
  title = {{Sum-Product Networks: A New Deep Architecture}},
  booktitle = {Workshops @ ICCV},
  year = {2011},
  doi = {10.1109/iccvw.2011.6130310},
}
Figure