On the Expressive Efficiency of Sum Product Networks

Abstract

Sum Product Networks (SPNs) are a recently developed class of deep generative models which compute their associated unnormalized density functions using a special type of arithmetic circuit. When certain sufficient conditions, called the decomposability and completeness conditions (or "D&C" conditions), are imposed on the structure of these circuits, marginal densities and other useful quantities, which are typically intractable for other deep generative models, can be computed by what amounts to a single evaluation of the network (which is a property known as "validity"). However, the effect that the D&C conditions have on the capabilities of D&C SPNs is not well understood. In this work we analyze the D&C conditions, expose the various connections that D&C SPNs have with multilinear arithmetic circuits, and consider the question of how well they can capture various distributions as a function of their size and depth. Among our various contributions is a result which establishes the existence of a relatively simple distribution with fully tractable marginal densities which cannot be efficiently captured by D&C SPNs of any depth, but which can be efficiently captured by various other deep generative models. We also show that with each additional layer of depth permitted, the set of distributions which can be efficiently captured by D&C SPNs grows in size. This kind of "depth hierarchy" property has been widely conjectured to hold for various deep models, but has never been proven for any of them. Some of our other contributions include a new characterization of the D&C conditions as sufficient and necessary ones for a slightly strengthened notion of validity, and various state-machine characterizations of the types of computations that can be performed efficiently by D&C SPNs.

arXiv commentVarious minor revisions and corrections throughout

Cited by in corpus (16)

• Training Very Deep Networks
• Two-hidden-layer Feedforward Neural Networks are Universal Approximators: A Constructive Approach
• On the Expressive Power of Deep Polynomial Neural Networks
• NeuroCard: One Cardinality Estimator for All Tables
• FLAT: Fast, Lightweight and Accurate Method for Cardinality Estimation
• Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
• BayesCard: Revitilizing Bayesian Frameworks for Cardinality Estimation
• FSPN: A New Class of Probabilistic Graphical Model
• Depth-Width Trade-offs for Neural Networks via Topological Entropy
• A Deep Conditioning Treatment of Neural Networks
• Probabilistic Generating Circuits
• Subtractive Mixture Models via Squaring: Representation and Learning
• Efficient Deep Learning of GMMs
• On the Relationship Between Probabilistic Circuits and Determinantal Point Processes
• How ConvNets model Non-linear Transformations
• Tucker Decomposition Network: Expressive Power and Comparison