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.

本文分析了 Sum Product Networks 中的 D&C 条件，并揭示了它们与多线性算术电路之间的联系，探讨了它们能够捕捉各种分布的效果，并考虑了深度对其性能的影响。