On the Expressive Efficiency of Sum Product Networks

Introduction

Sum Product Networks (SPNs) (Poon and Domingos, 2011) are a recently developed class of deep generative models which compute their associated unnormalized density functions using a special type of arithmetic circuit. Like neural networks, arithmetic circuits (e.g. Shpilka and Yehudayoff, 2010) are feed-forward circuits whose gates/nodes compute real values, and whose connections have associated real-valued weights. Each node in an arithmetic circuit computes either a weighted sum or a product over their real-valued inputs.

For an important special class of SPNs called “valid SPNs”, computing the normalizing constant, along with any marginals, can be performed by what amounts to a single evaluation of the network. This is to be contrasted with other deep generative models like Deep Boltzmann Machines (Salakhutdinov and Hinton, 2009), where quantities crucial to learning and model evaluation (such as the normalizing constant) are provably intractable, unless $P=\#P$ (Roth, 1996).

The tractability properties of valid SPNs are the primary reason they are interesting both from a theoretical and practical perspective. However, validity is typically enforced via the so-called “decomposability” and “completeness” conditions (which we will abbreviate as “D&C”). While easy to describe and verify, the D&C conditions impose stringent structural restrictions on SPNs which limit the kinds of architectures that are allowed. While some learning algorithms have been developed that can respect these conditions (e.g. Gens and Domingos, 2013; Peharz et al., 2013; Rooshenas and Lowd, 2014), the extent to which they limit the expressive efficiencyBy this we mean the extent to which they can efficiently capture various distribution. A distribution is “efficiently captured” if it is contained in the closure of the set of distributions corresponding to different settings of the models parameters, for polynomial sized (in the dimension $n$ of the data/input) instances of the model, where size is measured by the number of “units” or parameters. Often these will be realistic low-order polynomials, although this depends on how exactly the constructions are done. Note that a distribution being “efficiently captured” says nothing about how easily the marginal densities or partition function of its associated density can be computed (except in the case of D&C SPNs of course). The concept of expressive efficiency is also sometimes called “expressive power” or “representational power”, although we will use the word “efficiency” instead of “power” to emphasize our focus on the question of whether or not certain distributions which can be captured efficiently by the model, instead of the question of whether or not they can be captured at all (i.e. by super-polynomially sized instances of the model). This latter question is the topic of papers which present so-called “universality” results which show how some models can capture any distribution if they are allowed be exponentially large in $n$ (by essentially simulating a giant look-up table). Such results are fairly straightforward, and indeed it easy to show that D&C SPNs are universal in this sense. of SPNs versus various other deep generative models remains unclear.

Like most models, D&C SPNs are “universal” in the sense that they can capture any distribution if they are allowed to be of a size which is exponential in the dimension $n$ of the data/input. However, any distribution function which can be efficiently captured by D&C SPNs, which is to say by one of polynomial size, must therefore be tractable (in the sense of having computable marginals, etc). And given complexity theoretic assumptions like $P\neq\#P$ it is easy to come up with density functions whose marginals/normalizers are intractable, but which nonetheless correspond to distributions which can be efficiently captured by various other deep generative models (e.g. using the simulation results from Martens (2014)). Thus we see that the tractability properties enjoyed by D&C SPNs indeed come with a price.

However, one could argue that the intractability of these kinds of “hard” distributions would make it difficult or even impossible to learn them in practice. Moreover, any model which can efficiently capture them must therefor lack an efficient general-case inference/learning algorithm. This is a valid point, and it suggests the obvious follow-up question: is there a fully tractable distribution (in the sense that its marginal densities and partition function can be computed efficiently) which can be efficiently captured by other deep models, but not by D&C SPNs?

In this work we answer this question in the affirmative, without assuming any complexity theoretic conjectures. This result thus establishes that D&C SPNs are in some sense less expressively efficient than many other deep models (since, by the results of Martens (2014), such models can efficiently simulate D&C SPNs), even if we restrict our attention only to tractable distributions. Moreover, it suggests existence of a hypothetical model which could share the tractability properties of D&C SPNs, while being more expressively efficient.

In addition to this result, we also analyze the effect of depth, and other structural characteristics, on the expressive efficiency of D&C SPNs. Perhaps most notably, we use existing results from arithmetic circuit theory to establish that D&C SPNs gain expressive efficiency with each additional layer of depth. In particular, we show that the set of distributions which can be efficiently captured by D&C SPNs grows with each layer of depth permitted. This kind of “depth hierarchy” property has never before been shown to hold for any other well-known deep model, despite the widespread belief that it does hold for most of them (e.g. Bengio and Delalleau, 2011).

Along with these two results, we also make numerous other contributions to the theoretical understanding of SPNs which are summarized below.

In Section 2, we first propose a generalized definition of SPNs that captures all previous definitions. We then illuminate the various connections between SPNs and multilinear arithmetic circuits, allowing us to exploit the many powerful results which have already been proved for the latter.

In Section 3 we provide new insights regarding the D&C conditions and their relationship to validity, and introduce a slightly strengthened version of validity which we show to be equivalent to the D&C conditions (whereas standard validity is merely implied by them). We also show that for a slightly generalized definition of SPNs, testing for standard validity is a co-NP hard problem.

In Section 5 we give examples of various state-based models of computation which can be efficiently simulated by D&C SPNs, and show how these can be used to give constructive proofs that various simple density functions can be efficiently computed by D&C SPNs.

In Section 6 we address the prior work on the expressive efficiency of D&C SPNs due to Delalleau and Bengio (2011), and give a much shorter proof of their results using powerful techniques borrowed from circuit theory. We go on to show how these techniques allow us to significantly strengthen and extend the results of Delalleau and Bengio (2011), answering an open question which they posed.

In Section 7 we leverage prior work done on multilinear arithmetic circuits to prove several very powerful results regarding the relationship between depth and expressive efficiency of D&C SPNs. First, we show that with each extra layer of depth added, there is an expansion of the set of functions efficiently computable by D&C SPNs (thus giving a strict “hierarchy of depth”). Next we show that if depth is allowed to grow with the input dimension $n$, that its effect on expressive efficiency greatly diminishes after it reaches $\mathcal{O}(\log(n)^{2})$.

In Section 8 we show that when D&C SPNs are constrained to have a recursive “formula” structure, as they are when learned using the approach of (Gens and Domingos, 2013), they lose expressive efficiency. In particular we use prior work on multilinear arithmetic circuits to produce example functions which can be efficiently computed by general D&C SPNs, but not by ones constrained to have a formula structure.

Finally, in Section 9 we give what is perhaps our most significant and difficult result, which is the existence of a simple density function whose marginals and normalizer are computable by an $\mathcal{O}(n^{1.19})$ time algorithm, and whose corresponding distribution can be efficiently captured by various other deep models (in terms of their size), but which cannot be efficiently computed, or even efficiently approximated, by a D&C SPN of any depth.

Definitions and Notation

Arithmetic circuits (e.g. Shpilka and Yehudayoff, 2010) are a type of circuit, similar to Boolean logic circuits, or neural networks. But instead of having gates/nodes which compute basic logical operations like AND, or sigmoidal non-linearities, they have nodes which perform one of the two fundamental operations of arithmetic: addition and multiplication. Their formal definition follows.

For a node $u$ in $\Phi$, $\Phi_{u}$ denotes the subcircuit of $\Phi$ rooted at $u$. This subcircuit is formed by taking only the nodes in $\Phi$ that are on a path to $u$.

The scope of a node $u$, denoted by $y_{u}$, is defined as the subset of the elements of $y$ which appear as labels in the sub-circuit rooted at $u$. These are the variables which $u$’s output essentially “depends on”.

The size of $\Phi$, denoted by $|\Phi|$, is defined as the number of nodes in $\Phi$, and its depth is defined as the length of the longest directed path in $\Phi$. An alternative notion of depth, called product depth (Raz and Yehudayoff, 2009), is defined as the largest number of product nodes which appear in a directed path in $\Phi$.

Note that in general, nodes in an arithmetic circuit can have out-degree greater than 1, thus allowing the quantities they compute to be used in multiple subsequent computations by other nodes. When this is not the case and the nodes of $\Phi$ each have out-degree at most 1, $\Phi$ is said to be an arithmetic formula, because it can be written out compactly as a formula.

2 Sum Product Networks (SPNs)

In this section we will give our generalized definition of Sum Product Networks (SPNs).

A Sum Product Network (SPN) $\Phi$ is defined as a monotone arithmetic circuit over $f$. It inherits all of the properties of monotone arithmetic circuits, and gains some additional ones, which are discussed below.

Because an SPN is an arithmetic circuit over $f$, any one of its nodes $u$ computes a polynomial function $q_{u}(f)$ in $f$. But because the elements of $f$ are functions of the elements of $x$, a node $u$ of an SPN can be also viewed as computing a function of $x$, as given by $q_{u}(f(x))$, where $f(x)$ denotes the set/tuple obtained by replacing each element $f_{i,j}$ in $f$ with the value of $f_{i,j}(x_{i})$.

The dependency-scope of a node $u$ is defined as the set of elements of $x$ on which members of $u$’s scope $f_{u}$ depend. The dependency-scope is denoted by $x_{u}$.

A formula SPN is defined as an SPN which is also an arithmetic formula. In other words, a formula SPN is one whose nodes each have an out-degree of at most 1.

It is important to remember that the domains (the $R_{i}$’s) and the measures ($M_{i}$’s) can be defined however we want, so that SPNs can represent both continuous and discrete distributions. For example, to represent a discrete distribution, we can choose $M_{i}$ to be the counting measure with support given by a finite subset, such as $\{0,1\}$. In such a case, integration of some function $g(x_{i})$ w.r.t. such a $M_{i}$ amounts to the summation $\sum_{x_{i}\in\{0,1\}}g(x_{i})$.

3 Validity, decomposability, and completeness

Treated as density models, general SPNs suffer from many of the same intractability issues that plague other deep density models, such as Deep Boltzmann Machines (Salakhutdinov and Hinton, 2009). In particular, there is no efficient general algorithm for computing their associated partition function $Z$ or marginal densities.

However, it turns out that for a special class of SPNs, called valid SPNs, computing the the partition function and marginal densities can be accomplished by what is essentially a single evaluation of the network. Moreover, the validity of a given SPN can be established using certain easy-to-test structural conditions called decomposability and completeness, which we will discuss later.

Decoding the notation, this definition says that for a valid SPN $\Phi$ we can compute the integral of the output function $q_{\Phi}(f(x))$ with respect to a subset of the input variables (given by the index set $I$) over corresponding subsets of their respective domains (the $S_{i}$’s), simply by computing the corresponding integrals over the respective univariate functions (the $f_{i,j}$’s) and evaluating the circuit by having nodes labeled by these $f_{i,j}$’s compute said integrals.

While validity may seem like a magical property for an SPN to have, as shown by Poon and Domingos (2011) there is a pair of easy to enforce (and verify) structural properties which, when they appear together, imply validity. These are known as “decomposability” and “completeness”, and are defined as follows.

Definition 2 (Decomposable) An SPN $\Phi$ is decomposable if for every product node $u$ in $\Phi$ the dependency-scopes of its children are pairwise disjoint.

Definition 3 (Completeness) An SPN $\Phi$ is complete if for every sum node $u$ in $\Phi$ the dependency-scopes of its children are all the same.

As was the case in the work of Poon and Domingos (2011), decomposability and completeness turn out to be sufficient conditions, but not necessary ones, for ensuring validity according to our more general set of definitions. Moreover, we will show that for a natural strengthening of the concept of validity, decomposability and completeness become necessary conditions as well.

The tractability of the partition function and marginal densities is a virtually unheard of property for deep probabilistic models, is the primary reason that decomposably and complete SPNs are so appealing.

For the sake of brevity we will call an SPN which satisfies the decomposability and completeness conditions a D&C SPN.

A notion related to decomposability which was discussed in Poon and Domingos (2011) is that of “consistency”, which is defined only for SPNs whose univariate functions $f$ are either the identity function $g(z)=z$ or the negation function $g(z)=1-z$, and whose inputs variables $x$ are all 0/1-valued. Such an SPN is said to be consistent if each product node satisfies the property that if one of its children has the identity function of $x_{i}$ in its scope, then none of the other children can have the negation function of $x_{i}$ in their scopes. This is a weaker condition than decomposability, and is also known to imply validity (Poon and Domingos, 2011).

Note that for $0/1$-valued variables we have $x_{i}^{2}=x_{i}$ and $(1-x_{i})^{2}=1-x_{i}$, and so it is possible to construct an equivalent decomposable SPN from a consistent SPN by modifying the children of each product node so as to remove the “redundant” factors of $x_{i}$ (or $1-x_{i}$). Note that such a construction may require the introduction of polynomially many additional nodes, as in the proof of Proposition 10. In light of this, and the fact that consistency only applies to a narrowly defined sub-class of SPNs, we can conclude that consistency is not a particularly interesting property to study by itself, and so we will not discuss it any further.

4 Top-down view of D&C SPNs

For a D&C SPN $\Phi$ it is known (and is straightforward to show) that if the weights on the incoming edges to each sum node sum to 1, and the univariate functions have integrals of 1 (i.e. so they are normalized density functions), then the normalizing constant of $\Phi$’s associated density is 1, and each node can be interpreted as computing a normalized density over the variables in its dependency scope. We will call such a $\Phi$ “weight-normalized”.

A weight-normalized D&C SPN $\Phi$ can be interpreted as a top-down directed generative model where each sum node corresponds to a mixture distribution over the distributions associated with its children (with mixture weights given by the corresponding edge weights), and where each product node corresponds to factorized distribution, with factors given by the distributions of its children (Gens and Domingos, 2013). Given this interpretation it is not hard to see that sampling from $\Phi$ can be accomplished in a top-down fashion starting at the root, just like in a standard directed acyclic graphical model.

One interesting observation we can make is that it is always possible to transform a general D&C SPN into an equivalent weight-normalized one, as is formalized in the following proposition:

Given a D&C SPN $\Phi$ there exists a weight-normalized D&C SPN $\Phi^{\prime}$ with the same structure as $\Phi$ and with the same associated distribution.

5 Relationship to previous definitions

Our definitions of SPNs and related concepts subsume those given by Poon and Domingos (2011) and later by Gens and Domingos (2013). Thus the various results we prove in this paper will still be valid according to those older definitions.

The purpose of this subsection is justify the above claim, with a brief discussion which assumes pre-existing familiarity with the definitions given in the above cited works.

First, to see that our definition of SPNs generalizes that of Poon and Domingos (2011), observe that we can take the univariate functions to be of the form $x_{i}$ or $\overline{x_{i}}=1-x_{i}$, and that we can choose the domains of measures so that the $x_{i}$’s are discrete $\{0,1\}$-valued variables, and choose the associated measures so that integration over values of $x_{i}$ becomes equivalent to summation.

Second, to see that our definition generalizes that of Gens and Domingos (2013), observe that we can take the univariate functions to be univariate density functions. And while Gens and Domingos (2013) formally defined SPNs as always being decomposable and complete, we will keep the concepts of SPNs and D&C SPNs separate in our discussions, as in the original paper by Poon and Domingos (2011).

6 Polynomials and multilinearity

In this section we will define some additional basic concepts which will be useful in our analysis of SPNs in the coming sections.

In general, polynomials over $y$ are defined as a finite sum of monomial terms. Given a monomial $m$, its associated coefficient in a polynomial $q$ will refer to the coefficient of the monomial term whose associated monomial is $m$ (we will assume that like terms have been collected, so this is unique). As a short-hand, we will say that a monomial $m$ is “in $q$” if the associated coefficient of $m$ in $q$ is non-zero.

The zero polynomial is defined as a polynomial which has no monomials in it. While the zero polynomial clearly computes the zero function, non-zero polynomials can sometimes also compute the zero function over the domain of $y$, and thus these are related but distinct concepts For example, $y_{1}(1-y_{1})$ computes the zero function when the domain of $y_{1}$ is $\{0,1\}$ but is clearly not the zero polynomial..

A polynomial is called non-negative if the coefficients of each of its monomials are non-negative. Non-negativity is related to the monotonicity of arithmetic circuits in the following way:

If $\Phi$ is a monotone arithmetic circuit over $y$ (such as an SPN with $y=f$), then $q_{\Phi}$ is a non-negative polynomial.

We will define the scope of a polynomial $q$ in $y$, denoted by $y_{q}$, to be the set of variables which appear as factors in at least one of its monomials. Note that for an node $u$ in an arithmetic circuit, the scope $y_{u}$ of $u$ can easily be shown to be a superset of the scope of its output polynomial $q_{u}$ (i.e. $y_{q_{u}}$), but it will not be equal to $y_{q_{u}}$ in general.

A central concept in our analysis of D&C SPNs will be that of multilinearity, which is closely related to the decomposability condition.

Definition 6 (Multilinear Polynomial) A polynomial $q$ in $y$ is multilinear if the degree of each element of $y$ is at most one in each monomial in $q$. For example, $y_{1}+y_{2}y_{3}$ is a multilinear polynomial.

Some more interesting examples of multilinear polynomials include the permanent and determinant of a matrix (where we view the entries of the matrix as the variables).

Definition 7 (Multilinear Arithmetic Circuit) If every node of an arithmetic circuit $\Phi$ over $y$ computes a multilinear polynomial in $y$, $\Phi$ is said to be a (semantically) multilinear arithmetic circuit. And if for every product node in $\Phi$, the scopes of its child nodes are pair-wise disjoint, $\Phi$ is said to be a syntactically multilinear arithmetic circuit.

It is easy to show that a syntactically multilinear arithmetic circuit is also a semantically multilinear circuit. However, it is an open question as to whether one can convert a semantically multilinear arithmetic circuit into a syntactically multilinear one without increasing its size by a super-polynomial factor Raz et al. (2008). In the case of formulas however, given a semantically multilinear formula of size $s$ one can transform it into an equivalent syntactically multilinear formula of size at most $s$ Raz (2004).

It should be obvious by this point that there is an important connection between syntactic multilinearity and decomposability. In particular, if our univariate functions of the $x_{i}$’s are all identity functions, then scope and dependency-scope become equivalent, and thus so do syntactic multilinearity and decomposability.

Given this observation we have that a monotone syntactically multilinear arithmetic circuit over $x$ can be viewed as a decomposable SPN.

A somewhat less obvious fact (which will be very useful later) is that any decomposable SPN over 0/1-valued $x_{i}$’s can be viewed as a syntactically multilinear arithmetic circuit over $x$, of a similar size and depth. To see this, note that any arbitrary univariate function $g$ of a 0/1-valued variable $z$ can always be written as an affine function of $z$, i.e. of the form $az+b$ with $a=g(1)-g(0)$ and $b=g(0)$. Thus we can replace each node computing a univariate function of some $x_{i}$ with a subcircuit computing this affine function, and this yields a (non-monotone) syntactically multilinear arithmetic circuit over $x$, with a single additional layer of sum nodes (of size $\mathcal{O}(n)$).

An extension of the concept of multilinearity is that of set-multilinearity (e.g. Shpilka and Yehudayoff, 2010). To define set-multilinearity we must first define some additional notation which we will carry through the rest of the paper.

Let $G_{1},G_{2},G_{3},...,G_{k}$ be a partitioning of the elements of $y$ into disjoint sets. The set-scope $G_{q}$ of a polynomial $q$ is the sub-collection of the collection $\{G_{1},...,G_{k}\}$ defined as consisting of those sets $G_{i}$ which have some element in common with the scope $y_{q}$ of $q$. i.e. $G_{q}=\{G_{i}:y_{q}\cap G_{i}\neq\varnothing\}$. Similarly, the set-scope $G_{u}$ of a node $u$ in an arithmetic circuit $\Phi$ is the sub-collection of the collection $\{G_{1},...,G_{k}\}$ defined as consisting of those sets $G_{i}$ which have some element in common with the scope of $u$. i.e. $G_{u}=\{G_{i}:y_{u}\cap G_{i}\neq\varnothing\}$.

Definition 8 (Set-multilinear polynomial) A polynomial is set-multilinear if each of its monomials has exactly one factor from each of the $G_{i}$’s in its set-scope.

For example, $3y_{1}y_{3}-y_{2}y_{4}$ is a set-multilinear polynomial when $G_{1}=\{y_{1},y_{2}\},G_{2}=\{y_{3},y_{4}\}$, while $y_{1}y_{2}+2y_{2}y_{4}$ is not. The permanent and determinant of a matrix also turn out to be non-trivial examples of set-multilinear polynomials, if we define the collection of sets so that $G_{i}$ consists of the entries in the $i^{th}$ row of the matrix.

Definition 9 (Set-multilinear arithmetic circuits) An arithmetic circuit is called (semantically) set-multilinear if each of its nodes computes a set-multilinear polynomial. An arithmetic circuit $\Phi$ is called syntactically set-multilinear if it satisfies the following two properties:

for each product node $u$ in $\Phi$, the set-scopes of the children of $u$ are pairwise disjoint

for each sum node $u$, the set-scopes of the children of $u$ are all the same.

A crucial observation is that the concepts of set-multilineary in arithmetic circuits and decomposability and completeness in SPNs are even more closely related than syntactic multilinearity is to decomposability. In particular, it is not hard to see that if we take $k=n$, $y=f$ and $G_{i}=f_{i}$, then set-scope (of nodes) and dependency-scope become analogous concepts, and D&C SPNs correspond precisely to monotone syntactically set-multilinear arithmetic circuits in $f$. Because of the usefulness of this connection, we will use the above identifcations for the remainder of this paper whenever we discuss set-multilinearity in the specific context of SPNs.

This connection also motivates a natural definition for the dependency-scope for polynomials over $f$. In particular, the dependency-scope of the polynomial $q$ over $f$ will be defined as the set of variables on which the members of $q$’s scope $f_{u}$ depend. We will denote the dependency-scope by $x_{q}$.

Analysis of Validity, Decomposability and Completeness

In this section we give a novel analysis of the relationship between validity, decomposability and completeness, making use of many of the concepts from circuit theory reviewed in the previous section.

First, we will give a quick result which shows that an incomplete SPN can always be efficiently transformed into a complete one which computes the same function of $x$. Note that this is not a paradoxical result, as the new SPN will behave differently than the original one when used to evaluate integrals (in the sense of definition of valid SPNs in Section 2).

Given an SPN $\Phi$ of size $s$ there exists a complete SPN $\Phi^{\prime}$ of size $s+n+k\in\mathcal{O}(s^{2})$, and an expanded set/tuple of univariate functions $f^{\prime}$ s.t. $q_{\Phi^{\prime}}(f^{\prime}(x))=q_{\Phi}(f(x))$ for all values of $x$, where $k$ is the sum over the fan-in’s of the sum nodes of $\Phi$. Moreover, $\Phi^{\prime}$ is decomposable if $\Phi$ is.

So in some sense we can always get completeness “for free”, and of the two properties, decomposability will be the one which actually constrains SPNs in a way that affects their expressive efficiency.

Unlike with decomposability and completeness, validity depends on the particular definitions of univariate functions making up $f$, and thus cannot be described in purely structural terms like set-multilinearity. This leads us to propose a slightly stronger condition which we call strong validity, which is independent of the particular choice of univariate functions making up $f$.

Definition 11 An SPN $\Phi$ is said to be strongly valid if it is valid for every possible choice of the univiariate functions making up $f$. Note: only the values computed by each $f_{i,j}$ are allowed to vary here, not the identities of the dependent variables.

The following theorem establishes the fundamental connection between set-multilinearity and strong validity.

Suppose the elements of $x$ are all non-trivial variables (as defined below). Then an SPN $\Phi$ is strongly valid if and only if its output polynomial is set-multilinear.

A variable $x_{i}$ is non-trivial if there are at least two disjoint subsets of $x_{i}$’s range $R_{i}$ which have finite and non-zero measure under $M_{i}$.

Non-triviality is a very mild condition. In the discrete case, it is equivalent to requiring that there is more than one element of the range set $R_{i}$ which has mass under the associated measure. Trivial variables can essentially be thought of as “constants in disguise”, and we can easily just replace them with constant nodes without affecting the input-output behavior of the circuit.

It is worth noting that the non-triviality hypothesis is a necessary one for the forward direction of Theorem 12 (although not the reverse direction). To see this, consider for example the SPN $\Phi$ which computes $f_{1,1}(x_{1})^{2}f_{2,1}(x_{2})$ in the obvious way, where $R_{1}=\{1\}$ and $R_{2}=\{0,1\}$, and the $M_{i}$ are the standard counting measures. While $\Phi$’s output polynomial $q_{\Phi}$ is not set-multilinear by inspection, it is relatively easy to show that $\Phi$ is indeed strongly valid, as it is basically equivalent to $cf_{2,1}(x_{2})$ for a constant $c$.

While Theorem 12 is interesting by itself as it provides a complete characterization of strong validity in terms of purely algebraic properties of an SPN’s output polynomial, its main application in this paper will be to help prove the equivalence of strong validity with the decomposability and completeness conditions.

Note that such an equivalence does not hold for standard validity, as was first demonstrated by Poon and Domingos (2011). To see this, consider the SPN which computes the expression $(f_{1,1}(x_{1})f_{1,2}(x_{1})+1)f_{2,1}(x_{2})$ in the obvious way, where the $x_{i}$ are 0/1-valued, the $M_{i}$ are the standard counting measures, and $f_{1,1}(x_{1})=x_{1}$, $f_{1,2}(x_{1})=\overline{x_{1}}=1-x_{1}$, and $f_{2,1}(x_{2})=x_{2}$. Clearly this SPN is neither decomposable nor complete, and yet an exhaustive case analysis shows that it is valid for these particular choices of the $f_{i,j}$’s.

Before we can prove the equivalence of strong validity with the decomposability and completeness conditions, we need to introduce another mild hypothesis which we call “non-degeneracy”.

Definition 13 A monotone arithmetic circuit (such as an SPN) is called non-degenerate if all of its weights and constants are non-zero (i.e. strictly positive).

Like non-triviality, non-degeneracy is a very mild condition to impose, since weights which are zero don’t actually “affect” the output. Moreover, there is a simple and size-preserving procedure which can transform a degenerate monotone arithmetic circuit to a non-degenerate one which computes precisely the same output polynomial, and also preserves structural properties like decomposability and completeness in SPNs. The procedure is as follows. First we remove all edges with weight . Then we repeatedly remove any nodes with fan-out 0 (except for the original output node) or fan-in 0 (except input node and constant nodes), making sure to remove any product node which is a parent of a node we remove. It is not hard to see that deletion of a node by this procedure is a proof that it computes the zero-polynomial and thus doesn’t affect the final output.

Without non-degeneracy, the equivalence between strong validity and the decomposability and completeness conditions does not hold for SPNs, as can be seen by considering the SPN $\Phi$ which computes the expression $0f_{1,1}(x_{1})^{2}+f_{1,1}(x_{1})f_{2,1}(x_{2})$ in the obvious way, where the $x_{i}$ are 0/1-valued and the $M_{i}$ are the standard counting measures, and the $f_{i,j}$’s are the identity function (i.e. $f_{i,j}(x_{i})=x_{i}$). Because the output polynomial $q_{\Phi}$ of $\Phi$ is equivalent to $f_{1,1}(x_{1})f_{2,1}(x_{2})$, it is indeed valid. However, the product node within $\Phi$ which computes $f_{1,1}(x_{1})^{2}$ violates the decomposability condition, even though this computation is never actually “used” in the final output (due to how it is weighted by 0).

Non-degeneracy allows us to prove many convenient properties, which are given in the lemma below.

Suppose $\Phi$ is a non-degenerate monotone arithmetic circuit. Denote by $r$ the root of $\Phi$, and $\{u_{i}\}_{i}$ its child nodes.

Each of the $\Phi_{u_{i}}$’s are non-degenerate monotone arithmetic circuits.

If $r$ is a product node, the set of monomials in $q_{r}$ is equal to the set consisting of every possible product formed by taking one monomial from each of the $q_{u_{i}}$’s. NOTE: This is true even for degenerate circuits.

If $r$ is a sum node, the set of monomials in $q_{r}$ is equal to the union over the sets of monomials in the $q_{u_{i}}$’s.

The set-scope of $r$ is equal to the set-scope of $q_{r}$.

We are now in a position to prove the following theorem.

A non-degenerate monotone arithmetic circuit $\Phi$ has a set-multilinear output polynomial if and only if it is syntactically set-multilinear.

Given this theorem, and utilizing the previously discussed connection between syntactic set-multilinearity and the decomposability and completeness conditions, the following corollary is immediate:

A non-degenerate SPN $\Phi$ has a set-multilinear output polynomial if and only if it is decomposable and complete.

And from this and Theorem 12, we have a 3-way equivalence between strong validity, the decomposability and completeness conditions, and the set-multilinearity of the output polynomial. This is stated as the following theorem.

Suppose $\Phi$ is a non-degenerate SPN whose input variables (the elements of $x$) are all non-trivial. Then the following 3 conditions are equivalent:

$\Phi$’s output polynomial is set-multilinear

Because SPNs can always be efficiently transformed so that the non-degeneracy and non-triviality hypotheses are both satisfied (as discussed above), this equivalence between strong validity and the D&C conditions makes the former easy to verify (since the D&C conditions themselves are).

However, as we will see in later sections, decomposability and completeness are restrictive conditions that limit the expressive power of SPNs in a fundamental way. And so a worthwhile question to ask is whether a set of efficiently testable criteria exist for verifying standard/weak validity.

We will shed some light on this question by proving a result which shows that a criterion cannot be both efficiently testable and capture all valid SPNs, provided that $P\neq NP$. A caveat to this result is that we can only prove it for a slightly extended definition of SPNs where negative weights and constants are permitted.

Define an extended SPN as one which is allowed to have negative weights and constants. The problem of deciding whether a given extended SPN is valid is co-NP-hard.

We leave it as an open question as to whether a similar co-NP-hardness property holds for validity checking of standard SPNs.

Focusing on D&C SPNs

One of the main goals of this paper is to advance the understanding of the expressive efficiency of SPNs. In this section we explore possible directions we can take towards this goal, and ultimately propose to focus exclusively on D&C SPNs.

It is well known that standard arithmetic circuits can efficiently simulate Boolean logic circuits with only a constant factor overhead. Thus they are as efficient at computing a given function as any standard model of computation, up to a polynomial factor. However, we cannot easily exploit this fact to study SPNs, as this simulation requires negative weights, and the weights of an SPN are constrained to be non-negative (i.e. they are monotone arithmetic circuits). And while SPNs have access to non-negative valued univariate functions of the input which standard monotone arithmetic circuits do not, this fact cannot obviously be used to construct a simulation of Boolean logic circuits.

Another possible way to gain insight into general SPNs would be to apply existing results for monotone arithmetic circuits. However, a direct application of such results is impossible, as SPNs are monotone arithmetic circuits over $f$ and not $x$, and indeed their univariate functions can compute various non-negative functions of $x$ (such as $1-x_{i}$ for values of $x_{i}$ in $\{0,1\}$) which a monotone circuit could not.

But while it seems that the existing circuit theory literature doesn’t offer much insight into general SPNs, there are many interesting results available for multilinear and set-multilinear arithmetic circuits. And as we saw in Section 3, these are closely related to D&C SPNs.

Moreover, it makes sense to study D&C SPNs, as they are arguably the most interesting class of SPNs, both from a theoretical and practical perspective. Indeed, the main reason why SPNs are interesting and useful in the first place is that valid SPNs avoid the intractability problems that plague conventional deep models like Deep Boltzmann Machines. Meanwhile the D&C conditions are the only efficiently testable conditions for ensuring validity that we are aware of, and as we showed in Section 3, they are also necessary conditions for a slightly strengthened notion of validity.

Thus, D&C SPNs will be our focus for the rest of the paper.

Capabilities of D&C SPNs

Intuitively, D&C SPNs seem very limited compared to general arithmetic circuits. In addition to being restricted to use non-negative weights and constants like general SPNs, decomposability heavily restricts the kinds of structure the networks can have, and hence the kinds of computations they can perform. For example, something as simple as squaring the number computed by some node $u$ becomes impossible.

In order to address the theoretical question of what kinds of functions D&C SPNs can compute efficiently, despite their apparent limitations, we will construct explicit D&C SPNs that efficiently compute various example functions.

This is difficult to do directly because the decomposability condition prevents us from using the basic computational operations we are accustomed to working with when designing algorithms or writing down formulae. To overcome this difficulty we will provide a couple of related examples of computational systems which we will show can be efficiently simulated by SPNs. These systems will be closer to more traditional models of computation like state-space machines, so that our existing intuitions about algorithm design will be more directly applicable to them.

The first such system we will call a Fixed-Permutation Linear Model (FPLM), which works as follows. We start by initializing a “working vector” $v$ with a value $a$, and then we process the input (the $x_{i}$’s) in sequence, according to a fixed order given by a permutation $\pi$ of $[n]$. At each stage we multiply $v$ by a matrix which is determined by the value of the current $x_{i}$. After seeing the whole input, we then take the inner product of $v$ with another vector $b$, which gives us our real-valued output.

More formally, we can define FPLMs as follows.

An FPLM can be viewed as a computational system which must process its input in a fixed order and maintains its memory/state as a $k$-dimensional vector. Crucially, an FPLM cannot revisit inputs that it has already processed, which is a similar limitation to the one faced by read-once Turing Machines. The state vector can be transformed at each stage by a linear transformation which is a function of the current input. While its $k$-dimensional state vector allows an FPLM to use powerful distributed representations which clearly possess enough information capacity to memorize the input seen so far, the fundamental limitation of FPLMs lies in their limited tools for manipulating this representation. In particular, they can only use linear transformations (given by matrices with positive entries). If they had access to arbitrary transformations of their state then it is not hard to see that any function could be efficiently computed by them.

The following result establishes that D&C SPNs can efficiently simulate FPLMs.

Given a FPLM of dimension $k$ there exists a D&C SPN of size $\mathcal{O}(nk^{2})$ which computes the same function.

Thus D&C SPNs are at least as expressively efficient as FPLMs. This suggests the following question: are they strictly more expressively efficient than FPLMs, or are they equivalent? It turns out that they are more expressively efficient. We sketch a proof of this fact below.

Suppose that $x$ takes values in $\{0,1\}^{n}$. As observed in Section 2.6, this allows us to assume without loss of generality that any univariate function of one of the $x_{i}$’s is affine in $x_{i}$. In particular, we can assume that the matrix-valued functions $T_{i}$ used in FPLMs are affine functions of the respective $x_{i}$’s. In this setting it turns out that FPLMs can be viewed as a special case of a computational system called “ordered syntactically multilinear branching programs”, as they are defined by Jansen (2008). Jansen (2008) showed that there exists a polynomial function in $x$ whose computation by such a system requires exponential size (corresponding to an FPLM with an exponentially large dimension $k$). Moreover, this function is computable by a polynomially sized monotone syntactically multilinear arithmetic. As observed in Section 2.6, such a circuit can be viewed as a decomposable SPN whose univariate functions are just identity functions. Then using Proposition 10 we can convert such a decomposable SPN to a D&C SPN while only squaring its size. So the polynomial provided by Jansen (2008) is indeed computed by a D&C SPN of polynomial size, while requiring exponential size to be computed by a FPLM, thus proving that D&C SPNs are indeed more expressively efficient.

Given this result, we see that FPLMs do not fully characterize the capabilities of D&C SPNs. Nevertheless, if we can construct an FPLM which computes some function efficiently, this constitutes proof of existence of a similarly efficient D&C SPN for computing said function.

To make the construction of such FPLMs simpler, we will define a third computational system which we call a Fixed-Permutation State-Space Model (FPSSM) which is even easier to understand than FPLMs, and then show that FPLMs (and hence also D&C SPNs) can efficiently simulate FPSSMs.

An FPSSM works as follows. We initialize our “working state” $u$ as $c$, and then we process the input (the $x_{i}$’s) in sequence, according to a fixed order given by the permutation $\pi$ of $[n]$. At each stage we transform $u$ by computing $g_{\pi(i)}(x_{\pi(i)},u)$, where the transition function $g_{\pi(i)}$ can be defined arbitrarily. After seeing the whole input, we then decode the state $u$ as the non-negative real number $h(u)$.

More formally we have the following definition.

FPSSMs can be seen as general state-space machines (of state size $k$), which like FPLMs, are subject to the restriction that they must process their inputs in a fixed order which is determined ahead of time, and are not allowed to revisit past inputs. If the state-space is large enough to be able to memorize every input seen so far, it is clear that FPSSMs can compute any function, given that their state-transition function can be arbitrary. But this would require their state-size constant $k$ to grow exponentially in $n$, as one needs a state size of $2^{b}$ in order to memorize $b$ input bits. FPSSMs of realistic sizes can only memorize a number of bits which is logarithmic in $n$. And this, combined with their inability to revisit past inputs, clearly limits their ability to compute certain functions efficiently. This is to be contrasted with FPLMs, whose combinatorial/distributed state have a high information capacity even for small FPLMs, but are limited instead in how they can manipulate this state.

The following result establishes that FPLMs can efficiently simulate FPSSMs.

Given a FPSSM of state-size $k$ there exists a FPLM of dimension $k$ which computes the same function.

Note that this result also implies that FPSSMs are no more expressively efficient than FPLMs, and are thus strictly less expressively efficient than D&C SPNs.

The following Corollary follows directly from Propositions 20 and 22:

Given a FPSSM of state-size $k$ there exists a D&C SPN of size $\mathcal{O}(nk^{2})$ which computes the same function.

Unlike with D&C SPNs, our intuitions about algorithm design readily apply to FPSSMs, making it easy to directly construct FPSSMs which implement algorithmic solutions to particular problems. For example, suppose we wish to compute the number of inputs whose value is equal to 1. We can solve this with an FPSSM with a state size of $k=n$ by taking $\pi$ to be the identity permutation, and the state $u$ to be the number of 1’s seen so far, which we increment whenever the current $x_{i}$ has value 1. We can similarly compute the parity of the number of ones (which is a well known and theoretically important function often referred to simply as “PARITY”) by storing the current number of them modulo 2, which only requires the state size $k$ to be $1$. We can also decide if the majority of the $x_{i}$’s are 1 (which is a well known function and theoretically important often referred to as “MAJORITY” or “MAJ”) by storing a count of the number of ones (which requires a state size of $k=n$), and then outputting $1$ if $s\geq n/2$ and otherwise.

It is noteworthy that the simulations of various models given in this section each require an D&C SPN of depth $n$. However, as we will see in Section 7.2, the depth of any D&C SPN can be reduced to $\mathcal{O}(log(n)^{2})$, while only increasing its size polynomially.

Separating Depth 3 From Higher Depths

The only prior work on the expressive efficiency of SPNs which we are aware of is that of Delalleau and Bengio (2011). In that work, the authors give a pair of results which demonstrate a difference in expressive efficiency between D&C SPNs of depth 3, and those of higher depths.

Their first result establishes the existence of an $n$-dimensional function $g$ (for each $n$) which can be computed by a D&C SPN of size $\mathcal{O}(n)$ and depth $\mathcal{O}(\log(n))$, but which requires size $\Omega(2^{\sqrt{n}})$ to be computed by a D&C SPN of depthNote that in our presentation the input layer counts as the first layer and contributes to the total depth. 3.

In their second result they show that for each $d\geq 4$ there is an $n$-dimensional function $h_{d}$ which can be computed by a D&C SPN of size $\mathcal{O}(dn)$ and depth $d$, but which requires size $\Omega(n^{d})$ to be computed by a D&C SPN of depth 3.

It is important to note that these results do not establish a separation in expressive efficiency between D&C SPNs of any two depths both larger than 3 (e.g. between depths 4 and 5). So in particular, despite how the size lower bound increases with $d$ in their second resultAs shown by our Theorem 29, there is a much stronger separation between depths 3 and 4 than is proved by Delalleau and Bengio (2011) to exist between depths $3$ and $d$ for any $d\geq 4$, and thus this apparent increase in the size of their lower bound isn’t due to the increasing power of D&C SPNs with depth so much as it an artifact of their particular proof techniques. this does not imply that the set of efficiently computable functions is larger for D&C SPNs of depth $d+k$ than for those of depth $d$, for any $k>0$, except when $d\leq 3$. This is to be contrasted with our much stronger “depth hierarchy” result (Theorem 29 of Section 7.1) which shows that D&C SPNs do in fact have this property (even with $k=1$) for all choices of $d$, where depth is measured in terms of product-depth.

In the next subsection we will show how basic circuit theoretic techniques can be used to give a short proof of a result which is stronger than both of the separation results of Delalleau and Bengio (2011), using example functions which are natural and simple to understand. Beyond providing a simplified proof of existing results, this will also serve as a demonstration of some of the techniques underlying the more advanced results from circuit theory which we will later make use of in Sections 7.1 and 8.

Moreover, by employing these more general and powerful proof techniques, we are able to prove a stronger result which seperates functions that can be efficiently approximated by D&C SPNs of depth 3 from those which can be computed by D&C SPNs of depth 4 and higher. This addresses the open question posed by Delalleau and Bengio (2011).

We begin by defining some basic concepts and notation which are standard in circuit theory.

For an arbitrary function $g$ of $x$, and a partition $(A,B)$ of the set $[n]$ of indices of the elements of $x$, define $M^{A,B}_{g}$ to be the $2^{|A|}$ by $2^{|B|}$ matrix of values that $g$ takes for different values of $x$, where the rows of $M^{A,B}_{g}$ are indexed by possible values of $x_{A}$, and the columns of $M^{A,B}_{g}$ are indexed by possible values of $x_{B}$.

$M^{A,B}_{g}$ is called a “communication matrix” in the context of communication complexity, and appears frequently as a tool to prove lower bounds. Its usefulness in lower bounding the size of D&C SPNs of depth $3$ is established by the following theorem.

Suppose $\Phi$ is a D&C SPN of depth 3 with $k$ nodes in its second layer. For any partition $(A,B)$ of $[n]$ we have $k\geq\operatorname{rank}\left(M^{A,B}_{q_{\Phi}(f(x))}\right)$.

Note that the proof of this theorem doesn’t use the non-negativity of the weights of the SPN, and thus applies to the “extended” version of SPNs discussed in Section 3.

We will now define the separating function which we will use to separate the expressive efficiency of depth 3 and 4 D&C SPNs.

Define $H_{1}=\{1,2,...,n/2\}$ and $H_{2}=\{n/2+1,n/2+2,...,n\}$. We will define the function $\operatorname{EQUAL}$ for $\{0,1\}^{n}$-valued $x$ to be $1$ when $x_{H_{1}}=x_{H_{2}}$ (i.e. the first half of the input is equal to the second half) and otherwise.

Observe that $M^{H_{1},H_{2}}_{\operatorname{EQUAL}}=I$ and so this matrix has rank $2^{n/2}$. This gives the following simple corollary of the above theorem:

Any D&C SPN of depth 3 with computes $\operatorname{EQUAL}(x)$ must have at least $2^{n/2}$ nodes in its second layer.

Meanwhile, $\operatorname{EQUAL}(x)$ is easily shown to be efficiently computed by a D&C SPN of depth 4. This is stated as the following proposition.

$\operatorname{EQUAL}$ can be computed by an D&C SPN of size $O(n)$ and depth 4.

Note that the combination of Corollary 25 and Proposition 26 gives a stronger separation result than both of the aforementioned results of Delalleau and Bengio (2011). Our result also has the advantage of using an example function which is easy to interpret, and can be easily extended to prove separation results for other functions which have a high rank communication matrix.

2 Separations for approximate computation

An open question posed by Delalleau and Bengio (2011) asked whether a separation in expressive efficiency exists between D&C SPNs of depth 3 and 4 if the former are only required to compute an approximation to the desired function. In this section we answer this question in the affirmative by making use of Theorem 24 and an additional technical result which lower bounds the rank of the perturbed versions of the identity matrix.

Suppose $\Phi$ is a D&C SPN of depth 3 whose associated distribution is such that each value of $x$ with $\operatorname{EQUAL}(x)=1$ has an associated probability between $a/2$ and $a$ for some $a>0$ (so that all such values of $x$ have roughly equal probability), and that the total probability $\delta$ of all of the values of $x$ satisfying $\operatorname{EQUAL}(x)=0$ obeys $\delta\leq 1/4$ (so that the probability of drawing a sample with $\operatorname{EQUAL}(x)=0$ is $\leq 1/4$). Then $\Phi$ must have at least $2^{n/2-2}/3$ nodes in its second layer.

To prove this result using Theorem 24 we will make use of the following lemma which lower bounds the rank of matrices of the form $I+D=M^{H_{1},H_{2}}_{\operatorname{EQUAL}}+D$ for some “perturbation matrix” $D$, in terms of a measure of the total size of the entries of $D$.

Depth Analysis

In this section we show that D&C SPNs become more expressively efficient as their product-depthProduct-depth is defined in Section 2.1. Note that it can be shown to be equivalent to standard depth up to a factor of 2 (e.g. by ‘merging’ sum nodes that are connected as parent/child). $d$ increases, in the sense that the set of efficiently computable density functions expands as $d$ grows. This is stated formally as follows:

For every integer $d\geq 1$ and input size $n$ there exists a real-valued function $g_{d+1}$ of $x$ such that:

There is a D&C SPN of product-depth $d+1$ and size $\mathcal{O}(n^{2})$ which computes $g_{d+1}$ for all values of $x$ in $\{0,1\}^{n}$, where the SPN’s univariate functions $f$ consist only of identity functions.

For any choice of the univariate functions $f$, a D&C SPN of product-depth $d$ that computes $g_{d+1}$ for all values of $x$ in $\{0,1\}^{n}$ must be of size $n^{\Omega(\log(n)^{1/2d})}$ (which is super-polynomial in $n$).

Previously, the only available result on the relationship of depth and expressive efficiency of D&C SPNs has been that of Delalleau and Bengio (2011), who showed that D&C SPNs of depth 3 are less expressively efficient than D&C SPNs of depth 4.

An anologous result seperating very shallow networks from deeper ones also exists for neural networks. In particular, it is known that under various realistic constraints on their weights, threshold-based neural networks with one hidden layer (not counting the output layer) are less expressively efficient those with 2 or more hidden layers (Hajnal et al., 1993; Forster, 2002).

More recently, Martens et al. (2013) showed that Restricted Boltzmann Machines are incapable of efficiently capturing certain simple distributions, which by the results of Martens (2014), can be efficiently captured by Deep Boltzmann Machines.

A “depth-hierarchy” property analogous to Theorem 29 is believed to hold for various other deep models like neural networks, Deep Boltzmann Machines (Salakhutdinov and Hinton, 2009), and Sigmoid Belief Networks (Neal, 1992), but has never been proven to hold for any of them. Thus, to the best of our knowledge, Theorem 29 represents the first time that a practical and non-trivial deep model has been rigorously shown to gain expressive efficiency with each additional layer of depth added.

To prove Theorem 29, we will make use of the following analogous result which is a slight modification of one proved by Raz and Yehudayoff (2009) in the context of multilinear circuits.

(Adapted from Theorem 1.2 of Raz and Yehudayoff (2009)) For every integer $d\geq 1$ and input size $n$ there exists a real-valued function $g_{d+1}$ of $x$ such that:

Note that the original Theorem 1.2 from Raz and Yehudayoff (2009) uses a slightly different definition of arithmetic circuits from ours (they do not permit weighted connections), and the constructed circuits are not stated to be monotone. However we have confirmed with the authors that their result still holds even with our definition, and the circuits constructed in their proof are indeed monotone (Raz, 2014).

There are several issues which must be overcome before we can use Theorem 30 to prove Theorem 29. The most serious one is that syntactically multilinear arithmetic circuits are not equivalent to D&C SPNs as either type of circuit has capabilities that the other does not. Thus the ability or inability of syntactically multilinear arithmetic circuits to compute certain functions does not immediately imply the same thing for D&C SPNs.

To address this issue, we will consider the case where $x$ is binary-valued (i.e. takes values in $\{0,1\}^{n}$) so that we may exploit the close relationship which exists between syntactically multilinear arithmetic circuits and decomposable SPNs over binary-valued inputs $x$ (as discussed in Section 2.6).

With these observations in place the proof of Theorem 29 from Theorem 30 becomes straightforward (and is given in the appendix).

2 The limits of depth

Next, we give a result which shows that the depth of any polynomially sized D&C SPN can be essentially compressed down to $\mathcal{O}(\log(n)^{2})$, at the cost of only a polynomial increase in its total size. Thus, beyond this sublinear threshold, adding depth to a D&C SPN does not increase the set of functions which can be computed efficiently (where we use this term liberally to mean “with polynomial size”). Note that this does not contradict Theorem 29 from the previous subsection as that dealt with the case where the depth $d$ is a fixed constant and not allowed to grow with $n$.

Because this depth-reducing transformation doesn’t explicitly preserve monotonicity, and deals with multilinear circuits instead of set-multilinear circuits, while using a slightly different definition of arithmetic circuits, it cannot be directly applied to prove an analogous statement for D&C SPNs. However, it turns out that the proof contained in Raz and Yehudayoff (2008) does in fact support a result which doesn’t have these issues (Raz, 2014). We state this as the following theorem.

Note that the size of the constructed circuit is smaller here than in Theorem 3.1 of Raz and Yehudayoff (2008) because we can avoid the “homogenization” step required in the original proof, as syntactically set-multilinear arithmetic circuits automatically have this property.

Given this theorem and the equivalence between monotone syntactically set-multilinear arithmetic circuits and D&C SPNs which was discussed near the end of Section 2.6, the following corollary is immediate.

Given a D&C SPN of size $s$ and arbitrary depth there exists a D&C SPN of size $\mathcal{O}(s^{3})$ and depth $\mathcal{O}(\log(n)\log(s))$ which computes the same function.

Note that when the size $s$ is a polynomial function of $n$, this depth bound is stated more simply as $\mathcal{O}(\log(n)^{2})$.

Circuits vs Formulas

In Gens and Domingos (2013) the authors gave a learning algorithm for SPNs which produced D&C SPN formulas. Recall that formulas are distinguished from more general circuits in that each node has fan-out at most 1. They are called “formulas” because they can be written down directly as formula expressions without the need to define temporary variables.

It is worthwhile asking whether this kind of structural restriction limits the expressive efficiency of D&C SPNs.

As we show in this section, the answer turns out to be yes, and indeed D&C SPN formulas are strictly less expressively efficient than more general D&C SPNs. This is stated formally as the following theorem:

For every input size $n$ there exists a real-valued function $g$ of $x$ such that:

There is a D&C SPN of size $\mathcal{O}(n^{4/3})$ which computes $g$, where the SPN’s univariate functions $f$ consist only of identity functions.

For any choice of the univariate functions $f$, a D&C SPN formula that computes $g$ must be of size $n^{\Omega(\log(n))}$ (which is super-polynomial in $n$).

As in Section 7.1, to prove Theorem 34, we will make use of an analogous result which is a slight modification of one proved by Raz and Yehudayoff (2008) in the context of multilinear circuits. This is stated below.

(Adapted from Theorem 4.4 of Raz and Yehudayoff (2008)) For every input size $n$ there exists a real-valued function $g$ of $x$ such that:

As in Section 7.1, the original Theorem 4.4 from Raz and Yehudayoff (2008) uses a slightly different definition of arithmetic circuits from ours (they do not permit weighted connections), and the constructed circuits are not stated to be monotone. However we have confirmed with the authors that their result still holds even with our definition, and the circuits constructed in their proof are indeed monotone (Raz, 2014).

When trying to use Theorem 35 to prove Theorem 34, we encounter similar obstacles to those encountered in Section 7.1. Fortunately, the transformation between decomposable SPNs and multilinear arithmetic circuits (for the case of binary-valued inputs) happens to preserve formula structure. Thus the ideas discussed in Section 7.1 for overcoming these obstacles also apply here.

A Tractable Distribution Separating D&C SPNs and Other Deep Models

The existence of a D&C SPN of size $s$ for computing some density function (possibly unnormalized) implies that the corresponding marginal densities can be computed by an $\mathcal{O}(s)$ time algorithm. Thus, it follows that D&C SPNs cannot efficiently compute densities whose marginals are known to be intractable. And if we assume the widely believed complexity theoretic conjecture that $P\neq\#P$, such examples are plentiful.

However, it is debatable whether this should be considered a major drawback of D&C SPNs, since distributions with intractable marginals are unlikely to be learnable using any model. Thus we are left with an important question: can D&C SPNs efficiently compute any density with tractable marginals?

In Poon and Domingos (2011) it was observed that essentially every known model with tractable marginal densities can be viewed as a D&C SPN, and it was speculated that the answer to this question is yes.

In this section we refute this speculation by giving a counter example. In particular, we construct a simple distribution $\mathcal{D}$ whose density function and corresponding marginals can be evaluated by efficient algorithms, but which provably cannot be computed by a sub-exponentially sized D&C SPN of any depth. Notably, this density function can be computed by a Boolean circuit of modest depth and size, and so by the simulation results of (Martens, 2014) the distribution can in fact be captured efficiently by various other deep probabilistic models like Deep Boltzmann Machines (DBMs).

Notably, our proof of the lower bound on the size of D&C SPNs computing this density function will not use any unproven complexity theoretic conjectures, such as $P\neq\#P$.

It is worthwhile considering whether there might be distributions which can be efficiently modeled by D&C SPNs but not by other deep generative models like DBMs or Contrastive Backprop Networks (Hinton et al., 2004). The answer to this question turns out to be no.

To see this, note that arithmetic circuits can be efficiently approximated by Boolean circuits, and even more efficiently approximated by linear threshold networks (which are a simple type of neural network). Thus, by the simulations results of Martens (2014) the aforementioned deep models can efficiently simulate D&C SPNs of similar depths (up to a reasonable approximation factor). Here “efficiently” means “with a polynomial increase in size”, although in practice this polynomial can be of low order, depending on how exactly one decides to simulate the required arithmetic. For linear threshold networks (and hence also Contrastive Back-prop Nets), very efficient simulations of arithmetic circuits can be performed using the results of Reif and Tate (1992), for example.

To construct the promised distribution over values of $x$ we will view each $x_{i}$ as an indicator variable for the presence or absence of a particular labeled edge in a subgraph $G_{x}$ of $K_{m}$, where $K_{m}$ denotes the complete graph on $m$ vertices. In particular, $x_{i}$ will take the value $1$ if the edge labeled by $i$ is present in $G_{x}$ and otherwise. Note that there are $\binom{m}{2}$ total edges in $K_{m}$ and so the total input size is $n=\binom{m}{2}$.

The distribution $\mathcal{D}$ will then be defined simply as the uniform distribution over values of $x$ satisfying the property that $G_{x}$ is a spanning tree of $K_{m}$. We will denote its density function by $d(x)$.

Computing $d(x)$ up to a normalizing constantThe normalizing constant in this case is given by $Z=m^{m-2}$ by Cayley’s Formula. amounts to deciding if the graph $G_{x}$ represented by $x$ is indeed a spanning tree of $K_{m}$, and outputting $1$ if it is, and otherwise. And to decide if the graph $G_{x}$ is a spanning tree amounts to checking that it is connected, and that it has exactly $m-1$ edges.

The first problem can be efficiently solved by a Boolean circuit with $\mathcal{O}(n)$ gates and depth $\mathcal{O}(\log(n))$ using the well-known trick of repeatedly squaring the adjacency matrix. The second can be solved by adding all of the entries of $x$ together, which can also be done with a Boolean circuit with $\mathcal{O}(n)$ gates and depth $\mathcal{O}(\log(n))$ (Paterson et al., 1990). Due to how neural networks with simple linear threshold nonlinearities can simulate Boolean circuits in a 1-1 manner (e.g Parberry, 1994), it follows that such networks of a similar size and depth can compute $d(x)$. And since linear threshold gates are easily simulated by a few sigmoid or rectified linear units, it follows that neural networks of the same dimensions equipped with such nonlinearities can also compute $d(x)$, or at least approximate it arbitrarily well (see Martens (2014) for a review of these basic simulation results).

Moreover, by the results of Martens (2014) we know that any distribution whose density is computable up to a normalization constant by Boolean circuits can be captured, to an arbitrarily small KL divergence, by various deep probabilistic models of similar dimensions. In particular, these results imply that Deep Boltzmann Machines of size $\mathcal{O}(n)$ and Constrastive Backprop Networks of size $\mathcal{O}(n)$ and depth $\mathcal{O}(\log(n))$ can model the distribution $\mathcal{D}$ to an arbitrary degree of accuracy. And since we can sample $(n-2)$-length Prüfer sequences (Prüfer, 1918) and implement the algorithm for converting these sequences to trees using a threshold network of size $\mathcal{O}(n^{2})$ and depth $\mathcal{O}(n)$ it follows from Martens (2014) that we can also approximate $\mathcal{D}$ using Sigmoid Belief Networks (Neal, 1992) of this size and depth.

While the existence of small circuits for computing $d(x)$ isn’t too surprising, it is a somewhat remarkable fact that it is possible to evaluate any marginal of $d(x)$ using an $\mathcal{O}(n^{1.19})$-time algorithm. That is, given a subset $I$ of $\{1,...,n\}$, and associated fixed values of the corresponding variables (i.e. $x_{I}$), we can compute the sum of $d(x)$ over all possible values of the remaining variables (i.e. $x_{\{1,...n\}\setminus I}$) using an algorithm which runs in time $\mathcal{O}(n^{1.19})$.

To construct this algorithm we first observe that the problem of computing these marginal densities reduces to the problem of counting the number of spanning trees consistent with a given setting of $x_{I}$ (for a given $I$). And it turns out that this is a problem we can attack directly by first reducing it to the problem of counting the total number of spanning trees of a certain auxiliary graph derived from $x_{I}$, and then reducing it to the problem of computing determinants of the Laplacian matrix of this auxiliary graph via an application of generalized version of Kirchoff’s famous Matrix Tree Theorem (Tutte, 2001). This argument is formalized in the proof of the following theorem.

There exists a $\mathcal{O}(n^{1.19})$-time algorithm, which given as input a set $I\subset\{1,...,n\}$ and corresponding fixed values of $x_{I}$, outputs the number of edge-labeled spanning trees $T$ of $K_{m}$ which are consistent with those values.

2 Main lower bound result

The main result of this section is stated as follows:

Suppose that $d(x)$ can be approximated arbitrarily well by D&C SPNs of size $\leq s$ and $m\geq 20$. Then $s\geq 2^{m/30240}$.

By “approximated arbitrarily well by D&C SPNs of size $\leq s$” we mean that there is a sequence of D&C SPNs of size $\leq s$ whose output approaches $d(x)$, where the univariate functions $f$ are allowed to be different for each SPN in the sequence. Observe that $d(x)$ being computed exactly by a D&C SPN of size $s$ trivially implies that it can approximated arbitrarily well by D&C SPNs of size $\leq s$.

Note that the large constant in the denominator of the exponent can likely be lowered substantially with a tighter analysis than the one we will present. However, for our purposes, we will be content simply to show that the lower bound on $s$ is exponential in $m$ (and hence also in $\sqrt{n}$).

Our strategy for proving Theorem 37 involves two major steps. In the first we will show that the output polynomial of any D&C SPN of size $s$ can be “decomposed” into the sum of $s^{2}$ “weak” functions. We will then extend this result to show that the same is true of any function which can computed as the limit of the outputs of an infinite sequence of D&C SPNs of size $\leq s$. This will be Theorem 39.

In the second step of the proof we will show that in order to express $d(x)$ as the sum of such “weak” functions, the size $k$ of the sum must be exponentially large in $m$, and thus so must $s$. This will follow from the fact (which we will show) that each “weak” function can only be non-zero on a very small fraction of the all the spanning trees of $K_{m}$ (to avoid being non-zero for a non-spanning tree graph), and so if a sum of them has the property of being non-zero for all of the spanning trees, then that sum must be very large. This will be Theorem 40.

Theorem 37 will then follow directly from Theorems 39 and 40.

3 Decomposing D&C SPNs

The following theorem shows how the output polynomial of a D&C SPN of size $s$ can be “decomposed” into a sum of $s^{2}$ non-negatives functions which are “weak” in the sense that they factorize over two relatively equal-sized partitions of the set of input variables.

Suppose $\Phi$ is a D&C SPN over $f$ of size $s$. Then we have:

where $k\leq s^{2}$, and where the $g_{i}$’s and $h_{i}$’s are non-negative polynomials in $f$ satisfying the conditions:

It should be noted that this result is similar to an existing one proved by Raz and Yehudayoff (2011) for monotone multilinear circuits, although we arrived at it independently.

While Theorem 38 provides a useful characterization of the form of functions which can be computed exactly by a D&C SPN of size $s$, it doesn’t say anything about functions which can only be computed approximately. To address this, we will strengthen this result by showing that any function which can be approximated arbitrarily well by D&C SPNs of size $s$ also has a decomposition which is analogous to the one in Theorem 38. This is stated as follows.

Suppose $\{\Phi_{j}\}_{j=1}^{\infty}$ is a sequence of D&C SPNs of size at most $s$ (where the definitions of the univariate functions $f$ is allowed to be different for each), such that the sequence $\{q_{\Phi_{k}}\}_{1}^{\infty}$ of corresponding output polynomials converges pointwise (considered as functions of $x$) to some function $\gamma$ of $x$. And further suppose that the size of the range of possible values of $x$ is given by some finite $d$. Then we have that $\gamma$ can be written as

where $k\leq s^{2}$ and $\forall i$, $g_{i}$ and $h_{i}$ are real-valued non-negative functions of $y_{i}$ and $z_{i}$ (resp.) where $y_{i}$ and $z_{i}$ are sub-sets/tuples of the variables in $x$ satisfying $\frac{n}{3}\leq|y_{i}|,|z_{i}|\leq\frac{2n}{3}$, $y_{i}\cap z_{i}=\varnothing$, $y_{i}\cup z_{i}=x$.

4 A lower bound on k

In this section we will show that if $d(x)$ is of the same form of $\gamma(x)$ from eqn. 2, then the size of the size $k$ of the sum must grow exponentially with $m$ (and hence $\sqrt{n}$). In particular, we will prove the following theorem.

Suppose $d(x)$ is of the form from eqn. 2, and $m\geq 20$. Then we must have that $k\geq 2^{m/15120}$.

Our strategy to prove this result will be to show that each term in the sum can only be non-zero on an exponentially small fraction of all the spanning trees of $K_{m}$ (and is thus “weak”). And since the sum must be non-zero on all the spanning trees in order to give $d(x)$, it will follow that $k$ will have to be exponentially large.

We will start with the simple observation that, due to the non-negativity of the $g_{i}$’s and $h_{i}$’s, each factored term $g_{i}h_{i}$ in the sum $d=\sum_{i=1}^{k}g_{i}h_{i}$ must agree with $d$ wherever $d$ is 0 (i.e. because we have $d(x)\geq g_{i}(y_{i})h_{i}(z_{i})$ for each $i$). And in particular, for each value of $x$ with $d(x)=0$, either $g_{i}(y_{i})$ or $h_{i}(z_{i})$ must be 0.

Intuitively, this is a very stringent requirement. As an analogy, we can think of each factor ($g_{i}$ or $h_{i}$) as “seeing” roughly half the input edges, and voting “yes, I think this is a spanning tree”, or “no, I don’t think this is a spanning tree” by outputting either a value $>0$ for “yes” or for “no”, with tie votes always going “no”. The requirement can thus be stated as: “each pair of factors is never allowed to reach an incorrect ‘yes’ decision”.

Despite both factors in each pair being arbitrary functions of their respective inputs (at least in principle), each only “sees” the status of roughly half the edges in the input graph, and so cannot say much about whether the entire graph actually is a spanning tree. While some potential cycles might be entirely visible from the part of the graph visible to one of the factors, this will not be true of most potential cycles. Thus, to avoid ever producing an incorrect “yes” decision, the factors are forced to vote using a very conservative strategy which will favor “no”.

The remainder of this section is devoted to formalizing this argument by essentially characterizing this conservative voting strategy and showing that it leads to a situation where only a very small fraction of all of the possible spanning trees of $K_{m}$ can receive two “yes” votes.

Suppose $g(y)$ and $h(z)$ are real-valued non-negative functions of the same form as those described in eqn. 2, and that for any value of $x$, $d(x)=0$ implies $g(y)=0$ or $h(z)=0$. Define $P=|\{x\in\{0,1\}^{m}:d(x)=1\mbox{ and }g(y)h(z)>0\}|$ and $Z=|\{x\in\{0,1\}^{m}:d(x)=1\}|=m^{m-2}$. Then for $m\geq 20$ we have

It is not hard to see that this lemma will immediately imply Theorem 40. In particular, provided that $d(x)=0$ implies that each term in the sum is , we have each term can be non-zero on at most a proportion $\frac{1}{2^{m/15120}}$ of the values of $x$ for which $d(x)=1$, and thus the entire sum can be non-zero on at most a proportion at most $\frac{k}{2^{m/15120}}$. Thus we must have that $k\frac{1}{2^{m/15120}}\geq 1$, i.e. $k\geq 2^{m/15120}$.

The rest of this section will be devoted to the proof of Lemma 41, which begins as follows.

Suppose we are given such a $g$ and $h$. We will color all of the edges of the complete graph $K_{m}$ as red or blue according to whether they correspond to input variables from $y$ or $z$ (resp.).

We define a “triangle” of a graph to be any complete subgraph on 3 vertices. $K_{m}$ has $\binom{m}{3}$ triangles total since it is fully connected. After coloring $K_{m}$, each triangle is either monochromatic (having edges with only one color), or dichromatic, having 2 edges of one color and 1 edge of the other color. We will refer to these dichromatic triangles as “constraint triangles”, for reasons which will soon become clear.

Clearly any graph $G_{x}$ which is a spanning tree of $K_{m}$ can’t contain any triangles, as these are simple examples of cycles. And determining whether $G_{x}$ contains all 3 edges of a given constraint triangle is impossible for $g$ or $h$ by themselves, since neither of them gets to see the status of all 3 edges. Because of this, $g$ and $h$ must jointly employ one of several very conservative strategies with regards to each constraint triangle in order to avoid deciding “yes” for some graph containing said triangle. In particular, we can show that either $g$ must always vote ‘no’ whenever all of the red edges of the triangle are present in the input graph $G_{x}$, or $h$ must vote “no” whenever all of the blues edges of the triangle are present in $G_{x}$.

This is formalized in the following proposition.

Let $a,b$ and $c$ be edges that form a constraint triangle in $K_{n}$. Suppose that $a$ and $b$ are both of a different color from $c$.

Then one of the following two properties holds:

$g(y)h(z)=0$ for all values of $x$ such that $G_{x}$ contains both $a$ and $b$

$g(y)h(z)=0$ for all values of $x$ such that $G_{x}$ contains $c$

Thus we can see that each constraint triangle over edges $a$, $b$, and $c$ in $K_{m}$ gives rise to distinct constraint which must be obeyed by any graph $G_{x}$ for which $g(y)h(z)>0$. These are each one of two basic forms:

We now give a lower bound on the number of constraint triangles (i.e. the number of dichromatic triangles) in $K_{m}$ as a function of the number edges of each color.

Given any coloring of the complete graph $K_{m}$ with $m\geq 20$ which has $r$ red edges and $n-r$ blue edges (recall $n=\binom{m}{2}$ is the total number of edges), for $n/3\leq r\leq 2n/3$, the total number of dichromatic triangles is lower bounded by $m^{3}/60$.

Our proof of the above lemma makes use of a known upper bound of the number of triangles in an arbitrary graph due to Fisher (1989).

As the choice of $y$ and $z$ implies the hypothesis $n/3\leq r\leq 2n/3$ we can apply this lemma to conclude that there are at least $m^{3}/60$ constraint triangles, and thus any graph $G_{x}$ for which $g(y)h(z)>0$ must obey $m^{3}/60$ distinct constraints of the forms given above.

It remains to show that the requirement of obeying $m^{3}/60$ such constraints limits the number of graphs $G_{x}$ for which $g(y)h(z)>0$ to be an exponentially small proportion of the total. Our strategy for doing this will be as follows. We will consider a randomized procedure (due to Aldous, 1990) that samples uniformly from the set of all spanning trees of $K_{m}$ by performing a type of random walk on $K_{m}$, adding an edge from the previous vertex whenever it visits a previously unvisited vertex. We will then show that the sequence of vertices produced by this random walk will, with very high probability, contain a length-3 subsequence which implies that the sampled tree violates at least one of the constraints.

This argument is formalized in the proof of the following lemma.

Suppose we are given $C$ distinct constraints which are each one of the two forms discussed above. Then, of all the spanning trees of $K_{m}$, a proportion of at most

As we have $C\geq m^{3}/60$ constraints, this lemma tells us that the proportion of spanning trees $G_{x}$ for which $g(y)h(z)>0$ is upper bounded by

This finally proves Lemma 41, and thus Theorem 40.

Discussion and future directions

We have shown that there are tractable distributions which D&C SPNs cannot efficient capture, but other deep models can. However, our separating distribution $\mathcal{D}$, which is the uniform distribution over adjacency matrices of spanning trees of the complete graph, is a somewhat “complicated” one, and seems to require $\log(n)$ depth to be efficiently captured by other deep models. Some questions worth considering are:

Is a distribution like $\mathcal{D}$ learnable by other deep models in practice?

Is there a simpler example than $\mathcal{D}$ of a tractable separating distribution?

Can we extend D&C SPNs in some natural way that would allow them to capture distributions like $\mathcal{D}$?

Should we care that D&C SPNs have this limitation, or are most “natural” distributions that we might want to model with D&C SPNs of a fundamentally different character than $\mathcal{D}$?

Far from showing that D&C SPNs are uninteresting, we feel that this paper has established that they are a very attractive objects for theoretical analysis. While the D&C conditions limit SPNs, they also make it possible for us to prove much stronger statements about them than we otherwise could.

Indeed, it is worth underlining the point that the results we have proved about the expressive efficiency of D&C SPNs are much stronger and more thorough than results available for other deep models. This is likely owed to the intrinsically tractable nature of D&C SPNs, which makes them amenable to analysis using known mathematical methods, avoiding the various proof barriers that exist for more general circuits.

One aspect of SPNs which we have not touched on in this work is their learnability. It is strongly believed that for conditional models like neural networks, which are capable of efficiently simulating Boolean circuits, learning is hard in general (Daniely et al., 2014). However, D&C SPNs don’t seem to fall into this category, and to the best of our knowledge, it is still an open question as to whether there is a provably effective and efficient learning algorithm for them. It seems likely that the “tractable” nature of D&C SPNs, which has allowed us to prove so many strong statements about their expressive efficiency, might also make it possible to prove strong statements about their learnability.

The authors would like to thank Ran Raz for his helpful discussions regarding multilinear circuits. James Martens was supported by a Google Fellowship.

References

Appendix A Proofs for Section 2

We will sketch a proof of this result by describing a simple procedure to transform $\Phi$ into $\Phi^{\prime}$.

This procedure starts with the leaf nodes and then proceeds up the network, processing a node only once all of its children have been processed. After being processed, a node will have the property that it computes a normalized density, as will all of its descendant nodes.

To process a node $u$, we first compute the normalizing constant $Z_{u}$ of its associated density. If it’s a sum node, we divide its incoming weights by $Z_{u}$, and if it’s a leaf node computing some univariate funciton of an $x_{i}$, we transform this function by dividing it by $Z_{u}$. Clearly this results in $u$ computing a normalized density. Note that processing a product node is trivial since it will be automatically normalized as soon its children are (which follows from decomposability).

After performing this normalization, the effect on subsequent computations performed by ancestor nodes of $u$ is described as follows. For every sum node $v$ which is a parent of $u$, the effect is equivalent to dividing the weight on edge $(u,v)$ by $Z_{u}$. And for every product node $v$ which is a parent of $u$, the effect is to divide its output by $Z_{u}$, which affects subsequent ancestor nodes of $v$ by applying this analysis recursively. The recursive analysis fails only once we reach the root node $r$, in which case the effect is to divide the output of the SPN by the constant $Z_{u}$, which won’t change the SPN’s normalized density function (or distribution).

Thus we can compensate for the normalization and leave the distribution associated with the SPN unchanged by multiplying certain incoming edge weights of certain ancestor sum nodes of $u$ by $Z_{u}$ (as specified by the above analysis). This is the second step of processing a node $u$.

Note that because we only process a sum node $u$ after its children have been processed and thus each compute normalized densities themselves, $Z_{u}$ is given simply by the sum of the weights of the incoming edges to $u$.

Denote by $r$ the root/output node of $\Phi$, and $\{u_{i}\}_{i}$ its child nodes.

This proof is a simple induction on the depth $d$ of $\Phi$.

Suppose the claim is true for $\Phi$’s of depth $d$, and consider a $\Phi$ of depth $d+1$.

Each $\Phi_{u}$ is clearly a monotone arithmetic circuit since $\Phi$ is, and so by induction we have that the coefficients of each of the $q_{u}$’s are non-negative.

If the root node $r$ is a product node then the coefficients of monomials in $q_{\Phi}$ are given by sums of products over coefficients of monomials from the $q_{u}$’s, and are thus non-negative. And if the root node $r$ is a sum node, then since the weights are non-negative, the coefficients of the monomials in $q_{\Phi}$ are non-negatively weighted linear combinations of the coefficients of monomials in the $q_{u}$’s, and are thus also non-negative.

Thus $q_{\Phi}$ is indeed a non-negative polynomial.

The base case is trivial since a depth 1 circuit consists of a single node which computes either a non-negative constant or the value of a single variable, and both of these correspond to a non-negative polynomial in the input variables.

Appendix B Proofs for Section 3

We will form $\Phi^{\prime}$ from $\Phi$ via a modification procedure which is described as follows.

Given a sum node $u$ in $\Phi$, with dependency-scope $x_{u}$, for each child $v$ of $u$, if $v$’s dependency-scope $x_{v}$ doesn’t coincide with $x_{u}$ (i.e. $x_{v}\neq x_{u}$, where $\neq$ means inequality of sets), we add a new product node to $\Phi$ and make this node a child of $u$ in place of $v$. This product node’s children consist of the original $v$ and a set of nodes computing univariate functions of each $x_{i}\in x_{u}\setminus x_{v}$ which are each constant and equal to $1$ for all values of $x_{i}$. Note that the dependency scope of this new node is thus $x_{v}\cup x_{u}\setminus x_{v}=x_{u}$.

Note that these modifications enlarge the set/tuple $f$ of univariate functions to one which we will denote by $f^{\prime}$.

Also note that these modifications add $k\in\mathcal{O}(s^{2})$ product nodes, and an additional $n$ nodes for computing the constant univariate functions of each $x_{i}$. Thus the size of $\Phi^{\prime}$ is given by $s+n+k\in\mathcal{O}(s^{2})$.

To see that $q_{\Phi^{\prime}}(f^{\prime}(x))=q_{\Phi}(f(x))$ for all values of $x$, observe that each node we add computes the same function as the node it replaces, as long as the network is evaluated in the standard way for a particular value of $x$ (i.e. where the input to the underlying arithmetic circuit is $f(x)$). This is because the node computes the product between the aforementioned replaced node and a set of nodes which will always output $1$ when evaluated for a particular value of $x$.

To see that $\Phi^{\prime}$ is complete, consider any sum node $u$ in $\Phi^{\prime}$. By construction, a given child node $z$ of $u$ is either the original child node $v$ from $\Phi$ in the case where $x_{v}=x_{u}$ (as sets), or is one of the above constructed product nodes, and thus has dependency-scope $x_{u}$. Thus $u$ satisfies the condition required for completeness. And since $u$ was general we can conclude that $\Phi^{\prime}$ is complete.

Finally, it remains to show that $\Phi^{\prime}$ is decomposable if $\Phi$ is. But this is easy, since we didn’t modify any of the dependency-scopes of any existing nodes, and the new product nodes we added had children whose dependency-scopes were disjoint by construction.

We will first show the reverse direction, that set-multilinearity of the output polynomial of $\Phi$ implies that $\Phi$ is strongly valid.

Suppose $q_{\Phi}$ is set-multilinear. Then we have that by definition $q_{\Phi}$ is a polynomial of the form

for some coefficients $c_{k}$ and indices $j_{i,k}$.

Then for any choice of the $f_{i,j}$’s and $x_{[n]\setminus I}$ we have

and so $\Phi$ is valid for these choices.

Now suppose that $\Phi$ is strongly valid and suppose by contradiction that $q_{\Phi}$ is not set-multilinear.

One way that this can happen (“case 1”) is if there is some monomial $m$ in $q_{\Phi}$ such that for some $i_{0}\in[n]$, $m$ has a factor of the form $f_{i_{0},j_{1}}f_{i_{0},j_{2}}$ depending on the same $x_{i_{0}}$ (it might be the case that $j_{1}=j_{2}$). The other way this can happen (“case 2”) is $m$ has no factors which are functions depending on some $x_{i_{0}}$ in $q_{\Phi}$’s dependency-scope.

As remarked before, we select values of $x_{[n]\setminus\{i_{0}\}}$ so that each $f_{i,j}(x_{i})$ is positive. Fix such values. Then it is not hard to see that $q_{\Phi}A_{\{i_{0}\}}(S,x_{[n]\setminus\{i_{0}\}})$ and $q_{\Phi}A_{\{i_{0}\}}(T,x_{[n]\setminus\{i_{0}\}})$ can be viewed as a polynomial functions of $b$. Moreover, they are both equal to the same polynomial, which we will denote $g(b)$. Combining the positivity of each $f_{i,j}(x_{i})$ with Fact 5 (which says that all coefficients on monomial terms in $q_{\Phi}$ are positive) we have that each monomial term in $q_{\Phi}$, when viewed as a monomial term in $g(b)$, has a positive coefficient. Collecting like terms in $g$ we have that since all coefficients are positive, there can be no cancellation of terms, and thus there is some monomial in $g$ of the form $b^{k}$ for $k\geq 2$ (case 1) or $k=0$ (case 2).