PaperlayerView exact revision on arXiv

Source-linked AI summary

Sum-Product Networks: A New Deep Architecture

Hoifung Poon, Pedro Domingos

arXiv:1202.3732v1cs.LGcs.AIstat.ML

TL;DR

Graphical-model inference and learning are limited by the complexity of the partition function and by difficult inference in deep networks. The paper introduces sum-product networks, whose structured sums and products enable tractable computation and learning with backpropagation or EM. SPNs outperform other methods on image completion, while experiments also expose comparability limits in a deep-network baseline.

  • Problem

    Graphical models face exponential worst-case inference and learning costs, while deep networks combine non-convex likelihood with intractable inference.

  • Method

    The paper introduces sum-product networks, directed acyclic graphs of indicator leaves, weighted sums, and products, and proposes learning them with backpropagation and EM.

  • Results

    SPNs outperform all evaluated methods on image completion by a wide margin, with differences statistically significant at p < 0.01.

  • Takeaways & Limitations

    SPNs provide a probabilistic deep architecture that computes partition functions and marginals efficiently and supports faster, more accurate inference and learning than previous deep architectures.

  • Takeaways & Limitations

    The reported DBN comparison is not directly comparable because its improved results use reduced-scale images and a training set exceeding 120,000 transformed images.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper asks which models permit tractable partition-function computation and introduces SPNs as an efficiently computable representation using sums and products. This addresses limitations of graphical models and supports learning through backpropagation or EM.

  • Motivation: Graphical models can have compact distributions that are not representable as normalized products of factors.The even-parity distribution is given as an example.
  • Motivation: Inference, accurate learning, and learning time can all face worst-case exponential complexity in graphical models.The stated difficulties include exponential inference, sample requirements, and learning time.
  • Motivation: Deep networks with hidden layers can compactly represent more distributions, but non-convex likelihood and intractable inference make learning challenging.Existing tractable graphical-model classes are described as limited in the distributions they represent compactly.
  • Key idea: The partition function is difficult because it sums exponentially many terms, while all marginals are sums of subsets of those terms.Efficient computation of the partition function therefore provides efficient computation of marginals.
  • Key idea: Reorganizing factor products with the distributive law yields a polynomial-size computation involving only sums and products.The paper proposes learning a model already in this efficiently computable form, with sums viewed as implicit hidden variables.
  • Contribution: SPNs provide tractability conditions more general than previous classes and support efficient learning by backpropagation or EM.The paper notes that whether polynomial-size SPNs suffice for real-world problems remains an empirical question.

2 SUM-PRODUCT NETWORKS

Sum-product networks (SPNs) are directed acyclic graphs that represent distributions through weighted sums and products over indicator leaves. Completeness and consistency make their computations valid, enabling efficient evidence probabilities, marginals, and partition functions.

  • SPN definition: SPNs are rooted directed acyclic graphs with indicator leaves, sum and product internal nodes, and non-negative weights on sum edges.Product nodes multiply child values, while sum nodes compute weighted sums of their children.
  • SPN semantics: An SPN evaluates complete states, partial evidence, or the partition function by setting indicator variables according to the queried assignment.All indicators set to 1 produce S(∗), while evidence sets compatible indicators to 1 and incompatible indicators to 0.
  • Validity conditions: Completeness requires all children of each sum node to have the same scope, while consistency forbids opposite indicators for one variable across product-node children.These structural conditions ensure that expansions preserve the correspondence between monomials and variable states.
  • Validity conditions: A complete and consistent SPN is valid, meaning it correctly computes the probability of every evidence assignment.Validity also implies S(∗) equals the SPN partition function, and evidence probabilities can be computed in time linear in network size.
  • Inference: A valid SPN computes all marginals, including the partition function, and represents any Markov-network distribution whose SPN has polynomially many edges.For such a representation, the partition function is computable in time polynomial in the number of variables.
  • Semantics and examples: SPNs provide mixture-model semantics: sum nodes correspond to hidden variables, while product nodes represent features or mixture components.A sum node can be interpreted as summing out a hidden variable whose values correspond to its children.

3 SUM-PRODUCT NETWORKS AND OTHER MODELS

SPNs provide compact representations that can be exponentially smaller than several existing model classes while retaining probabilistic semantics and efficient inference. They also extend naturally to grammatical and vision models, although some junction-tree distributions remain outside their compact representational scope.

  • Representational generality: SPNs can be exponentially more compact than hierarchical mixture models and thin junction trees by reusing mixtures and exploiting context-specific independence and determinism.Both model classes can be represented as SPNs without loss of compactness, while some distributions admit exponentially smaller SPN representations.
  • Representational generality: A five-variable even-parity distribution has a linear-size SPN representation, whereas a mixture model requires exponentially many complete-state components.Intermediate components are reused in the SPN; mixture components cannot cover multiple states without assigning probability to odd-parity states.
  • Representational generality: SPNs can represent some distributions without conditional independences, and can be exponentially more compact than their expanded multilinear representations.This extends compact representation beyond models whose structure is explained by conditional independence.
  • Scope boundary: Graphical models with junction-tree clique potentials that cannot be simplified to polynomial size cannot be represented compactly as SPNs.This is a scope boundary on SPN compactness, not a claim that such distributions cannot be represented at all.
  • Applications and connections: Unlike arithmetic circuits and AND/OR graphs, SPNs are presented as models with semantics and learning procedures rather than only as compilation targets.Prior learning approaches lacked SPN-level flexibility or did not reuse subcircuits.
  • Applications and connections: Convolutional networks alternate feature and pooling layers, whereas SPNs combine probabilistic modeling with feature hierarchies and general-purpose architecture.The supplied passage introduces this contrast but does not complete the comparison.
  • Applications and connections: Probabilistic context-free grammars can be implemented as decomposable SPNs, while SPNs additionally represent unrestricted probabilistic grammars with bounded recursion.Nonterminal nodes correspond to sums and productions to products, making SPN learning equivalent to directly learning a bounded-size chart parser for PCFGs.

4 LEARNING SUM-PRODUCT NETWORKS

SPNs can be learned by initializing a valid architecture, updating weights through inference-based procedures, and pruning zero-weight edges. Backpropagation and EM provide standard updates, while hard EM is proposed to overcome gradient diffusion in deep SPNs.

  • Learning procedure: Learning starts from a densely connected valid SPN, initializes its weights, repeatedly performs inference and weight updates, and prunes zero-weight edges after convergence.Removing zero-weight edges and parentless non-root nodes produces the final learned SPN.
  • Learning procedure: The initial architecture is built from selected variable subsets, multiple sum nodes per subset, and product nodes encoding selected decompositions.The construction connects combinations of sum nodes associated with decomposed subsets.
  • Learning procedure: Restricting the number of subsets and decompositions to polynomially many keeps the initial SPN polynomial in size and inference efficient during and after learning.For domains with local structure, subsets and decompositions can be chosen using domain-specific patterns.
  • Weight learning: Backpropagation computes likelihood gradients efficiently through SPN derivatives, while EM treats each sum node as a hidden variable and updates normalized child weights.In EM, inference supplies hidden-variable marginals for the E step, and their accumulated counts determine the M-step weights.
  • Weight learning: A sparse prior can yield smaller SPNs after pruning, enabling faster inference and helping combat overfitting.The prior is applied during MAP learning.
  • Deep learning: Hard EM replaces marginal inference with MPE inference so every update from root to inputs has unit size, avoiding gradient diffusion in deep SPNs.The authors report accurate learning of SPNs with tens of layers in experiments using this approach.

5 EXPERIMENTS

The experiments evaluate SPNs for large-image completion and compare them with deep and conventional baselines. SPNs achieve strong completion results while supporting very deep architectures and efficient learning and inference.

  • Evaluation: SPNs were evaluated by masking half of images from Caltech-101 and additionally testing on the Olivetti face dataset.For Caltech-101, the last third of each category was held out for testing, with up to 50 images per category.
  • Architecture: The image-completion experiments used architectures built from rectangular image regions, with coarse decompositions for large regions and finer decompositions inside 4-by-4 blocks.The architecture selected all rectangular regions initially, then used multiple resolution levels to accelerate learning with little accuracy degradation.
  • Architecture: The learned SPNs were very deep, containing 36 layers in the reported experiments.For d×d images, the architecture generally has 2(d−1) layers between the root and input.
  • Comparisons: SPNs were compared with DBNs, DBMs, PCA, and nearest neighbor using mean squared errors on completed pixels.Nearest neighbor used the training image with the most similar visible half, while PCA used 100 principal components.
  • Results: SPNs outperformed the other methods by a wide margin on image completion, with differences statistically significant at p < 0.01.PCA sometimes achieved relatively low mean squared errors but often produced blurred completions; nearest-neighbor quality depended on finding a similar training image.
  • Results: SPNs provide exact inference and were at least an order of magnitude faster in learning and inference than DBNs and DBMs.Caltech learning took about 6 minutes with 20 CPUs, whereas DBN/DBM learning ranged from 30 hours to over a week; SPN MPE inference took less than a second.

6 SUM-PRODUCT NETWORKS AND THE CORTEX

The paper draws an analogy between SPN nodes used for MAP inference and the cortex’s pyramidal and stellate neurons, while noting that the connection may broaden computational neuroscience tools.

  • 6 SUM-PRODUCT NETWORKS AND THE CORTEX: For MAP inference, SPNs use max and sum nodes, analogous respectively to inhibitory and excitatory neurons.Max nodes select the highest input, whereas sum nodes compute sums of their inputs.
  • 6 SUM-PRODUCT NETWORKS AND THE CORTEX: The cortical analogy differs in weight placement: SPNs place weights at max-node inputs, whereas the analogy suggests placing them at sum-node inputs.The two arrangements can be mapped by having max nodes ignore their children’s weights and use only their values.
  • 6 SUM-PRODUCT NETWORKS AND THE CORTEX: The proposed analogy may reduce computation, improve discriminative performance, or reflect priors approximately encoded by neural activity.These are offered as possible justifications for allowing max nodes to ignore priors.
  • 6 SUM-PRODUCT NETWORKS AND THE CORTEX: The authors present the connection as an addition to the computational neuroscience toolkit rather than as an established cortical model.The passage describes the connection as potentially interesting in several ways.

7 CONCLUSION

The conclusion presents SPNs as deep architectures that efficiently support inference and learning while combining mixture models with feature hierarchies. Experiments indicate faster and more accurate performance than previous deep architectures, with robustness reducing data requirements.

  • 7 CONCLUSION: SPNs are directed acyclic graphs of sums and products that compute partition functions and marginals efficiently and support learning by backpropagation and EM.They combine mixture-model and feature-hierarchy perspectives.
  • 7 CONCLUSION: Inference and learning with SPNs are faster and more accurate than in previous deep architectures.The conclusion attributes the learning improvement to faster and more accurate inference.
  • 7 CONCLUSION: SPNs’ robustness means they require much less data for learning.
Loading 1202.3732v1…