Sum-Product Networks: A New Deep Architecture
arXiv:1202.3732
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 (2)
Cited by in corpus (109)
- Deep Learning in Neural Networks: An Overview
- Deep Learning for Anomaly Detection: A Survey
- Structure Discovery in Nonparametric Regression through Compositional Kernel Search
- MADE: Masked Autoencoder for Distribution Estimation
- Deep Generative Stochastic Networks Trainable by Backprop
- DeepID-Net: multi-stage and deformable deep convolutional neural networks for object detection
- On the Expressive Power of Deep Learning: A Tensor Analysis
- Hinge-Loss Markov Random Fields and Probabilistic Soft Logic
- On the number of response regions of deep feed forward networks with piece-wise linear activations
- Benefits of depth in neural networks
- Hinge-loss Markov Random Fields: Convex Inference for Structured Prediction
- On the Relationship between Sum-Product Networks and Bayesian Networks
- SPPL: Probabilistic Programming with Fast Exact Symbolic Inference
- Conditional Generative Moment-Matching Networks
- An Algorithm for Training Polynomial Networks
- SPFlow: An Easy and Extensible Library for Deep Probabilistic Learning using Sum-Product Networks
- Online Semi-Supervised Learning with Deep Hybrid Boltzmann Machines and Denoising Autoencoders
- Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits
- On Relaxing Determinism in Arithmetic Circuits
- Gradient Estimation with Stochastic Softmax Tricks
- A Dynamic Programming Algorithm for Inference in Recursive Probabilistic Programs
- Convolutional Rectifier Networks as Generalized Tensor Decompositions
- Analysis and Design of Convolutional Networks via Hierarchical Tensor Decompositions
- Bayesian Learning of Sum-Product Networks
- DeepDB: Learn from Data, not from Queries!
- Accurate and Conservative Estimates of MRF Log-likelihood using Reverse Annealing
- SimNets: A Generalization of Convolutional Networks
- Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions
- Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation
- FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
- Tensorial Mixture Models
- Conditional Sum-Product Networks: Imposing Structure on Deep Probabilistic Architectures
- Efficient Generation of Structured Objects with Constrained Adversarial Networks
- Learning with Memory Embeddings
- Truncated Variational Expectation Maximization
- Deep Structured Mixtures of Gaussian Processes
- Tractable Querying and Learning in Hybrid Domains via Sum-Product Networks
- Approximation Complexity of Maximum A Posteriori Inference in Sum-Product Networks
- Model-based Approximate Query Processing
- Flow Models for Arbitrary Conditional Likelihoods
- The Sum-Product Theorem: A Foundation for Learning Tractable Models
- Sum-Product-Quotient Networks
- The Tensor Memory Hypothesis
- Integrity Constraints Revisited: From Exact to Approximate Implication
- CryptoSPN: Privacy-preserving Sum-Product Network Inference
- Sum-product networks: A survey
- Strudel: Learning Structured-Decomposable Probabilistic Circuits
- FSPN: A New Class of Probabilistic Graphical Model
- Sum-Product Networks for Sequence Labeling
- A Unified Transferable Model for ML-Enhanced DBMS
- Towards Predicting the Likeability of Fashion Images
- Deep Residual Mixture Models
- Deep Generalized Convolutional Sum-Product Networks
- Learning Arbitrary Sum-Product Network Leaves with Expectation-Maximization
- Simplified Stochastic Feedforward Neural Networks
- Interventions and Counterfactuals in Tractable Probabilistic Models: Limitations of Contemporary Transformations
- Probabilistic Generating Circuits
- Stochastic And-Or Grammars: A Unified Framework and Logic Perspective
- Efficient Learning of Generative Models via Finite-Difference Score Matching
- Complexity of Representation and Inference in Compositional Models with Part Sharing
- Optimisation of Overparametrized Sum-Product Networks
- Sum-Product-Transform Networks: Exploiting Symmetries using Invertible Transformations
- A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries
- SLASH: Embracing Probabilistic Circuits into Neural Answer Set Programming
- Probabilistic Circuits for Variational Inference in Discrete Graphical Models
- Symmetry-Aware Marginal Density Estimation
- A Minimalistic Approach to Sum-Product Network Learning for Real Applications
- GSNs : Generative Stochastic Networks
- On the Long-Term Memory of Deep Recurrent Networks
- Tractable Inference in Credal Sentential Decision Diagrams
- Probabilistic Approximate Logic and its Implementation in the Logical Imagination Engine
- Leveraging Probabilistic Circuits for Nonparametric Multi-Output Regression
- Reified Context Models
- Quantifying the probable approximation error of probabilistic inference programs
- Latent Dependency Forest Models
- Mixtures of Sparse Autoregressive Networks
- End-to-end learning potentials for structured attribute prediction
- Recurrent Sum-Product-Max Networks for Decision Making in Perfectly-Observed Environments
- On the Relationship Between Probabilistic Circuits and Determinantal Point Processes
- Random Sum-Product Forests with Residual Links
- Sum-Product Network Decompilation
- Query the model: precomputations for efficient inference with Bayesian Networks
- Joints in Random Forests
- From Pixels to Buildings: End-to-end Probabilistic Deep Networks for Large-scale Semantic Mapping
- Arbitrary Conditional Distributions with Energy
- Deep Compression of Sum-Product Networks on Tensor Networks
- Propositional Knowledge Representation and Reasoning in Restricted Boltzmann Machines
- Sum-Product-Attention Networks: Leveraging Self-Attention in Probabilistic Circuits
- A Chain Graph Interpretation of Real-World Neural Networks
- On Constraint Definability in Tractable Probabilistic Models
- Hierarchical Spatial Sum-Product Networks for Action Recognition in Still Images
- Learning Tuple Probabilities
- The Complexity of Bayesian Networks Specified by Propositional and Relational Languages
- Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption
- Learning Large-Scale Topological Maps Using Sum-Product Networks
- Learning Tractable Probabilistic Models for Fault Localization
- Stability of the Stochastic Gradient Method for an Approximated Large Scale Kernel Machine
- Provable Guarantees on the Robustness of Decision Rules to Causal Interventions
- Coresets for Dependency Networks
- Sum-Product Networks for Hybrid Domains
- Explaining Deep Tractable Probabilistic Models: The sum-product network case
- Rediscovering Deep Neural Networks Through Finite-State Distributions
- Regularization for Multiple Kernel Learning via Sum-Product Networks
- Weighted Positive Binary Decision Diagrams for Exact Probabilistic Inference
- Continuous Learning: Engineering Super Features With Feature Algebras
- Workload-Aware Materialization of Junction Trees
- RECOWNs: Probabilistic Circuits for Trustworthy Time Series Forecasting
- On the Sample Complexity of Learning Sum-Product Networks
- Factor Graph Grammars