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.
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.
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