Sum-Product Networks: A New Deep Architecture

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.

References in corpus (1)

• Learning Arithmetic Circuits

Cited by in corpus (45)

• Deep Learning in Neural Networks: An Overview
• Deep Learning for Anomaly Detection: A Survey
• MADE: Masked Autoencoder for Distribution Estimation
• DeepID-Net: multi-stage and deformable deep convolutional neural networks for object detection
• On the Relationship between Sum-Product Networks and Bayesian Networks
• SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networks
• On Relaxing Determinism in Arithmetic Circuits
• A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs
• Accurate and Conservative Estimates of MRF Log-likelihood using Reverse Annealing
• SimNets: A Generalization of Convolutional Networks
• Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation
• The Sum-Product Theorem: A Foundation for Learning Tractable Models
• The Tensor Memory Hypothesis
• CryptoSPN: Privacy-preserving Sum-Product Network Inference
• FSPN: A New Class of Probabilistic Graphical Model
• Strudel: Learning Structured-Decomposable Probabilistic Circuits
• Interventions and Counterfactuals in Tractable Probabilistic Models: Limitations of Contemporary Transformations
• Optimisation of Overparametrized Sum-Product Networks
• A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries
• Symmetry-Aware Marginal Density Estimation
• Complexity of Representation and Inference in Compositional Models with Part Sharing
• Sum-Product-Transform Networks: Exploiting Symmetries using Invertible Transformations
• Latent Dependency Forest Models
• Leveraging Probabilistic Circuits for Nonparametric Multi-Output Regression
• GSNs : Generative Stochastic Networks
• Reified Context Models
• End-to-end learning potentials for structured attribute prediction
• Tractable Inference in Credal Sentential Decision Diagrams
• A Chain Graph Interpretation of Real-World Neural Networks
• The Complexity of Bayesian Networks Specified by Propositional and Relational Languages
• Learning Tuple Probabilities
• On Constraint Definability in Tractable Probabilistic Models
• On the Relationship Between Probabilistic Circuits and Determinantal Point Processes
• Recurrent Sum-Product-Max Networks for Decision Making in Perfectly-Observed Environments
• Sum-Product-Attention Networks: Leveraging Self-Attention in Probabilistic Circuits
• Learning Large-Scale Topological Maps Using Sum-Product Networks
• Coresets for Dependency Networks
• Sum-Product Networks for Hybrid Domains
• Workload-Aware Materialization of Junction Trees
• Weighted Positive Binary Decision Diagrams for Exact Probabilistic Inference
• Provable Guarantees on the Robustness of Decision Rules to Causal Interventions
• Learning Tractable Probabilistic Models for Fault Localization
• RECOWNs: Probabilistic Circuits for Trustworthy Time Series Forecasting
• Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption
• On the Sample Complexity of Learning Sum-Product Networks