On the Expressive Efficiency of Sum Product Networks

By James Martens, Venkatesh Medabalimi. 2014

75 citations recorded by the source corpus.

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.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Probabilistic & Bayesian Methods

Citations in the corpus

Training Very Deep Networks (2015, background): “Related observations hold for Boolean circuits [8, 9] and modern neural networks [10, 11, 12].”
The Power of Depth for Feedforward Neural Networks (2015, background): “2, will be shown to be easy to approximate arbitrarily well with a 3-layer network, but hard to approximate with a 2-layer network.”
On the Expressive Power of Deep Learning: A Tensor Analysis (2015, unknown): “Recently, Martens and Medabalimi (2014) proved that there exist functions which can be efﬁciently computed by decomposable and complete (D&C) SPNs of depth d + 1 , yet require a D&C SPN of depth d or less to have super-polynomial size for exact realization.”
Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks (2016, background): “These include networks which are not plain-vanilla ones (e.g. (Cohen et al., 2016; De-lalleau & Bengio, 2011; Martens & Medabalimi, 2014)), measuring quantities other than approximation error (e.g. (Bianchini & Scarselli, 2014; Poole et al., 2016)), focusing only on approximation upper bounds (e.g.…”