On the Relationship between Sum-Product Networks and Bayesian Networks

Han Zhao
HAN . ZHAO @ UWATERLOO . CA
Mazen Melibari
MMELIBAR @ UWATERLOO . CA
Pascal Poupart
PPOUPART @ UWATERLOO . CADavid R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada

Abstract
In this paper, we establish some theoretical connections between Sum-Product Networks (SPNs)
and Bayesian Networks (BNs). We prove that every SPN can be converted into a BN in linear timeand space in terms of the network size. The key
insight is to use Algebraic Decision Diagrams(ADDs) to compactly represent the local conditional probability distributions at each node in the
resulting BN by exploiting context-specific independence (CSI). The generated BN has a simple
directed bipartite graphical structure. We showthat by applying the Variable Elimination algorithm (VE) to the generated BN with ADD representations, we can recover the original SPN
where the SPN can be viewed as a history recordor caching of the VE inference process. To help
state the proof clearly, we introduce the notion of
normal SPN and present a theoretical analysis of
the consistency and decomposability properties.
We conclude the paper with some discussion of
the implications of the proof and establish a connection between the depth of an SPN and a lower
bound of the tree-width of its corresponding BN.

1. Introduction
Sum-Product Networks (SPNs) have recently been proposed as tractable deep models (Poon & Domingos, 2011)
for probabilistic inference. They distinguish themselvesfrom other types of probabilistic graphical models (PGMs),
including Bayesian Networks (BNs) and Markov Networks(MNs), by the fact that inference can be done exactly in linear time with respect to the size of the network. This has
generated a lot of interest since inference is often a coretask for parameter estimation and structure learning, andit typically needs to be approximated to ensure tractabil-

ity since probabilistic inference in BNs and MNs is #Pcomplete (Roth, 1996).
The relationship between SPNs and BNs, and more broadly
with PGMs, is not clear. Since the introduction of SPNs in
the seminal paper of Poon & Domingos (2011), it is wellunderstood that SPNs and BNs are equally expressive inthe sense that they can represent any joint distribution overdiscrete variables1 , but it is not clear how to convert SPNs
into BNs, nor whether a blow up may occur in the conversion process. The common belief is that there exists
a distribution such that the smallest BN that encodes this
distribution is exponentially larger than the smallest SPN
that encodes the same distribution. The key behind thisbelief lies in SPNs’ ability to exploit context-specific independence (CSI) (Boutilier et al., 1996).
While the above belief is correct for classic BNs with tabular conditional probability distributions (CPDs) that ignore
CSI, and for BNs with tree-based CPDs due to the replication problem (Pagallo, 1989), it is not clear whether it iscorrect for BNs with more compact representations of the
CPDs. The other direction is clear for classic BNs with tabular representation: given a BN with tabular representationof its CPDs, we can build an SPN that represents the same
joint probability distribution in time and space complexitythat may be exponential in the tree-width of the BN. Briefly,
this is done by constructing a junction tree and translating
it into an SPN2 . However, to the best of our knowledge,
it is still unknown how to convert an SPN into a BN andwhether the conversion will lead to a blow up when morecompact representations than tables and trees are used for
the CPDs.
In this paper, we prove that by adopting Algebraic Decision Diagrams (ADDs) (Bahar et al., 1997) to represent theCPDs at each node in a BN, every SPN can be converted
into a BN in linear time and space complexity in the size of
the SPN. The generated BN has a simple bipartite structure,
1

Proceedings of the 32 nd International Conference on Machine
Learning, Lille, France, 2015. JMLR: W&CP volume 37. Copyright 2015 by the author(s).

Joint distributions over continuous variables are also possible, but we will restrict ourselves to discrete variables in this paper.
2
http://spn.cs.washington.edu/faq.shtml

On the Relationship between Sum-Product Networks and Bayesian Networks

which facilitates the analysis of the structure of an SPN in
terms of the structure of the generated BN. Furthermore,
we show that by applying the Variable Elimination (VE)
algorithm (Zhang & Poole, 1996) to the generated BN with
ADD representation of its CPDs, we can recover the original SPN in linear time and space with respect to the size of
the SPN.
Our contributions can be summarized as follows. First, we
present a constructive algorithm and a proof for the conversion of SPNs into BNs using ADDs to represent the local CPDs. The conversion process is bounded by a linear function of the size of the SPN in both time and space.
This gives a new perspective to understand the probabilistic semantics implied by the structure of an SPN throughthe generated BN. Second, we show that by executing VE
on the generated BN, we can recover the original SPN in
linear time and space complexity in the size of the SPN.
Combined with the first point, this establishes a clear relationship between SPNs and BNs. Third, we introduce
the subclass of normal SPNs and show that every SPN
can be transformed into a normal SPN in quadratic timeand space. Compared with general SPNs, the structure of
normal SPNs exhibit more intuitive probabilistic semantics
and hence normal SPNs are used as a bridge in the conversion of general SPNs to BNs.

2. Related WorkThe SPN, as an inference machine, has a close connection with the broader field of knowledge representation andknowledge compilation. In knowledge compilation, thereasoning process is divided into two phases: an offlinecompilation phase and an online query-answering phase. In
the offline phase, the knowledge base, either propositional
theory or belief network, is compiled into some tractabletarget language. In the online phase, the compiled target
model is used to answer a large number of queries efficiently. The key motivation of knowledge compilation is to
shift the computation that is common to many queries fromthe online phase into the offline phase. As an example,
Arithmetic Circuits (ACs) have been studied and used extensively in both knowledge representation and probabilistic inference (Darwiche, 2000; Huang et al., 2006; Chavira
et al., 2006). Rooshenas & Lowd (2014) recently showedthat ACs and SPNs can be converted mutually without an
exponential blow-up in both time and space. As a direct result, ACs and SPNs share the same expressiveness for probabilistic reasoning. Another representation closely related
to SPNs in propositional logic and knowledge representation is the deterministic-Decomposable Negation Normal
Form (d-DNNF) (Darwiche & Marquis, 2001). Like SPNs,
d-DNNF formulas can be queried to answer satisfiability
and model counting problems. We refer interested readers

to Darwiche & Marquis (2001) and Darwiche (2001) for
more detailed discussions.
Since their introduction by Poon & Domingos (2011),
SPNs have generated a lot of interest as a tractable classof models for probabilistic inference in machine learning. Discriminative learning techniques for SPNs havebeen proposed and applied to image classification (Gens& Domingos, 2012). Later, automatic structure learning algorithms were developed to build tree-structured
SPNs directly from data (Dennis & Ventura, 2012; Peharz
et al., 2013; Gens & Domingos, 2013; Rooshenas & Lowd,2014). SPNs have also been applied to various fields andhave generated promising results, including activity modeling (Amer & Todorovic, 2012), speech modeling (Peharz
et al., 2014) and language modeling (Cheng et al., 2014).
Theoretical work investigating the influence of the depth of
SPNs on expressiveness exists (Delalleau & Bengio, 2011),
but is quite limited. As discussed later, our results reinforce previous theoretical results about the depth of SPNs
and provide further insights about the structure of SPNs by
examining the structure of equivalent BNs.

3. Preliminaries
We start by introducing the notation used in this paper. We
use 1 : N to abbreviate the notation {1, 2, . . . , N }. We
use a capital letter X to denote a random variable and abolded capital letter X1:N to denote a set of random variables X1:N = {X1 , . . . , XN }. Similarly, a lowercase letterx is used to denote a value taken by X and a bolded lowercase letter x1:N denotes a joint value taken by the corresponding vector X1:N of random variables. We may omit
the subscript 1 : N from X1:N and x1:N if it is clear fromthe context. For a random variable Xi , we use xji , j ∈ 1 : J
to enumerate all the values taken by Xi . For simplicity,
we use Pr(x) to mean Pr(X = x) and Pr(x) to mean
Pr(X = x). We use calligraphic letters to denote graphs(e.g., G). In particular, BNs, SPNs and ADDs are denoted
respectively by B, S and A.
To ensure that the paper is self contained, we briefly review some background material about Algebraic Decision
Diagrams and Sum-Product Networks.
3.1. Algebraic Decision Diagram
We first give a formal definition of Algebraic Decision Diagrams (ADDs) for variables with Boolean domains andthen extend the definition to domains corresponding to arbitrary finite sets.
Definition 1 (Algebraic Decision Diagram (Bahar et al.,1997)). An Algebraic Decision Diagram (ADD) is a graphical representation of a real function with Boolean input
variables: f : {0, 1}N 7→ R, where the graph is a rooted

On the Relationship between Sum-Product Networks and Bayesian Networks

DAG. There are two kinds of nodes in an ADD. Terminal
nodes, whose out-degree is 0, are associated with real values. Internal nodes, whose out-degree is 2, are associatedwith Boolean variables Xn , n ∈ 1 : N . For each internal
node Xn , the left out-edge is labeled with Xn = FALSE
and the right out-edge is labeled with Xn = TRUE.
We extend the original definition of an ADD by allowing
it to represent not only functions of Boolean variables, butalso any function of discrete variables with a finite set as
domain. This can be done by allowing each internal node
Xn to have |Xn | out-edges and label each edge with xjn , j ∈1 : |Xn |, where Xn is the domain of variable Xn and |Xn |is the number of values Xn takes. Such an ADD represents
a function f : X1 × · · · × XN 7→ R, where × means the
Cartesian product between two sets. Henceforth, we will
use our extended definition of ADDs throughout the paper.
For our purpose, we will use an ADD as a compact graphical representation of local CPDs associated with each node
in a BN. This is a key insight of our constructive proof presented later. Compared with a tabular representation ora decision tree representation of local CPDs, CPDs represented by ADDs can fully exploit CSI (Boutilier et al.,1996) and effectively avoid the replication problem (Pagallo, 1989) of the decision tree representation.
We give an example in Fig. 1 where the tabular representation, decision-tree representation and ADD representationof a function of 4 Boolean variables is presented. Anotheradvantage of ADDs to represent local CPDs is that arithmetic operations such as multiplying ADDs and summingout a variable from an ADD can be implemented efficiently
in polynomial time. This will allow us to use ADDs in the
Variable Elimination (VE) algorithm to recover the originalSPN after its conversion to a BN with CPDs represented by
ADDs. Readers are referred to Bahar et al. (1997) for amore detailed and thorough discussion about ADDs.
3.2. Sum-Product Network
Before introducing SPNs, we first define the notion of network polynomial, which plays an important role in our
proof. We use I[X = x] to denote an indicator that returns
1 when X = x and 0 otherwise. To simplify the notation,
we will use Ix to represent I[X = x].
Definition 2 (Network Polynomial (Poon & Domingos,
2011)). Let f (·) ≥ 0 be an unnormalized probability
distribution over a Boolean random vector X1:N . The
network polynomial of f (·) is a multilinear functionPQN
x f (x)n=1 Ixn of indicator variables, where the summation is over all possible instantiations of the Boolean
random vector X1:N .
Intuitively, the network polynomial is a Boolean expansion (Boole, 1847) of the unnormalized probability dis-tribution f (·). For example, the network polynomial of a
BN X1 → X2 is Pr(x1 , x2 )Ix1 Ix2 + Pr(x1 , x̄2 )Ix1 Ix̄2 +Pr(x̄1 , x2 )Ix̄1 Ix2 + Pr(x̄1 , x̄2 )Ix̄1 Ix̄2 .
Definition 3 (Sum-Product Network (Poon & Domingos,
2011)). A Sum-Product Network (SPN) over Boolean variables X1:N is a rooted DAG whose leaves are the indicators
Ix1 , . . . , IxN and Ix̄1 , . . . , Ix̄N and whose internal nodes are
sums and products. Each edge (vi , vj ) emanating from asum node vi has a non-negative weight wij . The value ofa product node is the productPof the values of its children.
The value of a sum node is vj ∈Ch(vi ) wij val(vj ) whereCh(vi ) are the children of vi and val(vj ) is the value of
node vj . The value of an SPN S[Ix1 , Ix̄1 , . . . , IxN , Ix̄N ] isthe value of its root.
The scope of a node in an SPN is defined as the set of variables that have indicators among the node’s descendants:
For any node v in an SPN, if v is a terminal node, say,an indicator S
variable over X, then scope(v) = {X}, else
scope(v) = ṽ∈Ch(v) scope(ṽ). Poon & Domingos (2011)
further define the following properties of an SPN:
Definition 4 (Complete). An SPN is complete iff each sum
node has children with the same scope.
Definition 5 (Consistent). An SPN is consistent iff no variable appears negated in one child of a product node andnon-negated in another.
Definition 6 (Decomposable). An SPNTis decomposable
iff for every product node v, scope(vi )scope(vj ) = ∅where vi , vj ∈ Ch(v), i 6= j.
Clearly, decomposability implies consistency in SPNs. An
SPN is said to be valid iff it defines a (unnormalized) probability distribution. Poon & Domingos (2011) proved that
if an SPN is complete and consistent, then it is valid. Notethat this is a sufficient, but not necessary condition. In thispaper, we focus only on complete and consistent SPNs as
we are interested in their associated probabilistic semantics. For a complete and consistent SPN S, each node v in
S defines a network polynomial fv (·) which corresponds tothe sub-SPN rooted at v. The network polynomial definedby the root of the SPN can then be computed recursively bytaking a weighted sum of the network polynomials definedby the sub-SPNs rooted at the children of each sum node
and a product of the network polynomials defined by the
sub-SPNs rooted at the children of each product node. The
probability distribution induced by an SPN S is defined as, where fS (·) is the network polynoPrS (x) , PfSf(x)x S (x)mial defined by the root of the SPN S.

4. Main Results
In this section, we state the main results obtained in thispaper and then provide a discussion. Due to the space limit,On the Relationship between Sum-Product Networks and Bayesian Networks

X1
X3

X1

X2

X2
0.3

X4
X1
0
0
0
0
0
0
0
0

X2
0
0
0
0
1
1
1
1

X3
0
0
1
1
0
0
1
1

X4
0
1
0
1
0
1
0
1

f (·)
0.4
0.6
0.3
0.3
0.4
0.6
0.3
0.3

X1
1
1
1
1
1
1
1
1

X2
0
0
0
0
1
1
1
1

X3
0
0
1
1
0
0
1
1

X4
0
1
0
1
0
1
0
1

(a) Tabular representation.

f (·)
0.4
0.6
0.3
0.3
0.1
0.1
0.1
0.1

0.1

X3

X3
0.4

0.6

0.3

X4

0.4

0.6

(b) Decision-Tree representation.

0.3

X4
0.4

0.1

0.6

(c) ADD representation.

Figure 1. Different representations of the same Boolean function. The tabular representation cannot exploit CSI and the Decision-Treerepresentation cannot reuse isomorphic subgraphs. The ADD representation can fully exploit CSI by sharing isomorphic subgraphs,
which makes it the most compact representation among the three representations. In Fig. 1(b) and Fig. 1(c), the left and right branchesof each internal node correspond respectively to FALSE and TRUE.

we refer the reader to the supplementary material for all the
proof details. To keep the presentation simple, we assume
without loss of generality that all the random variables are
Boolean unless explicitly stated. It is straightforward toextend our analysis to discrete random variables with finite
support. For an SPN S, let |S| be the size of the SPN, i.e.,
the number of nodes plus the number of edges in the graph.
For a BN B, the size of B, |B|, is defined by the size of thegraph plus the size of all the CPDs in B (the size of a CPD
depends on its representation, which will be clear from thecontext). The main theorems are:S over Boolean variables X1:N , the original SPN S can berecovered by applying the Variable Elimination algorithm
to B in O(N |S|).
Remark 3. The combination of Theorems 1 and 2 showsthat distributions for which SPNs allow a compact representation and efficient inference, BNs with ADDs also allow a compact representation and efficient inference (i.e.,
no exponential blow up).

Theorem 1. There exists an algorithm that converts any
complete and decomposable SPN S over Boolean variables
X1:N into a BN B with CPDs represented by ADDs in timeO(N |S|). Furthermore, S and B represent the same distribution and |B| = O(N |S|).

To make the upcoming proofs concise, we first define anormal form for SPNs and show that every complete andconsistent SPN can be transformed into a normal SPN in
quadratic time and space without changing the network
polynomial. We then derive the proofs with normal SPNs.
Note that we only focus on SPNs that are complete and consistent. Hence, when we refer to an SPN, we assume that it
is complete and consistent without explicitly stating this.

As it will be clear later, Thm. 1 immediately leads to thefollowing corollary:

4.1. Normal Form

Corollary 1. There exists an algorithm that converts any
complete and consistent SPN S over Boolean variables
X1:N into a BN B with CPDs represented by ADDs in timeO(N |S|2 ). Furthermore, S and B represent the same distribution and |B| = O(N |S|2 ).
Remark 1. The BN B generated from S in Theorem 1 andCorollary 1 has a simple bipartite DAG structure, where
all the source nodes are hidden variables and the terminal
nodes are the Boolean variables X1:N .

Remark 2. Assuming sum nodes alternate with productnodes in SPN S, the depth of S is proportional to the maximum in-degree of the nodes in B, which, as a result, is
proportional to a lower bound of the tree-width of B.
Theorem 2. Given the BN B with ADD representation of
CPDs generated from a complete and decomposable SPN

For an SPN S, let fS (·) be the network polynomial definedat the root of S. Define the height of an SPN to be thelength of the longest path from the root to a terminal node.
Definition 7. An SPN is said to be normal if
1. It is complete and decomposable.
2. For each sum node in the SPN, the weights of theedges emanating from the sum node are nonnegativeand sum to 1.
3. Every terminal node in the SPN is a univariate distribution over a Boolean variable and the size of thescope of a sum node is at least 2 (sum nodes whose
scope is of size 1 are reduced into terminal nodes).
Theorem 3. For any complete and consistent SPN S, there
exists a normal SPN S 0 such that PrS (·) = PrS 0 (·) and|S 0 | = O(|S|2 ).

On the Relationship between Sum-Product Networks and Bayesian Networks

An example of a normal SPN constructed from a general
SPN is depicted in Fig. 2.
+
10
×

+

9

6

4
7

×

+

×

+
4

+

×

×

×

+
14

9

Normal Form

9
35

6
35

2

6

1

6

8

Ix1

Ix̄1

Ix2

Ix̄2

X1

X1

X2

X2

(0.6, 0.4)

(0.9, 0.1)

(0.3, 0.7)

(0.2, 0.8)

Figure 2. Transform an SPN into a normal form. Terminal nodes
which are probability distributions over a single variable are represented by a double-circle.

In order to construct a BN from an SPN, we require the
SPN to be in a normal form, otherwise we can first transform it into a normal form by Thm. 3 using the algorithms
provided in the supplementary material.
Let S be a normal SPN over X1:N . Before showing how
to construct a corresponding BN, we first give some intuitions. One useful view is to associate each sum node inan SPN with a hidden variable. For example, consider asum node v ∈ S with out-degree l. Since S is normal, wePlhave i=1 wi = 1 and wi ≥ 0, ∀i ∈ 1 : l. This naturally suggests that we can associate a hidden discrete random variable Hv with multinomial distribution Prv (Hv =i) = wi , i ∈ 1 : l for each sum node v ∈ S. Therefore,
S can be thought as defining a joint probability distribution over X1:N and H = {Hv | v ∈ S, v is a sum node}
where X1:N are the observable variables and H are thehidden variables. When doing inference with an SPN, we
implicitly sum
P out all the hidden variables H and compute
PrS (x) = h PrS (x, h). Associating each sum node inan SPN with a hidden variable not only gives us a conceptual understanding of the probability distribution definedby an SPN, but also helps to elucidate one of the key properties implied by the structure of an SPN as summarized
below:
Proposition 1. Given a normal SPN S, let p be a productnode in S with l children. Let v1 , . . . , vk be sum nodes
which lie on a path from the root of S to p. Then
Pr(x|scope(p) Hv1 = v1∗ , . . . , Hvk = vk∗ ) =S

i=1

Pr(x|scope(pi ) Hv1 = v1∗ , . . . , Hvk = vk∗ )S

Based on the observations above and with the help of thenormal form for SPNs, we now proceed to prove the firstmain result in this paper: Thm. 1. First, we present thealgorithm to construct the structure of a BN B from S in
Alg. 1. In a nutshell, Alg. 1 creates an observable variable
Algorithm 1 Build BN Structure

4.2. SPN to BNlY

Note that there may exist multiple paths from the root to
p in S. Each such path admits the factorization stated in
Eq. 1. Eq. 1 explains two key insights implied by the structure of an SPN that will allow us to construct an equivalent
BN with ADDs. First, CSI is efficiently encoded by the
structure of an SPN using Proposition 1. Second, the DAG
structure of an SPN allows multiple assignments of hidden
variables to share the same factorization, which effectively
avoids the replication problem present in decision trees.

(1)

where Hv = v ∗ means the sum node v selects its v ∗ thbranch and x|A denotes restricting x by set A, pi is the ith
child of product node p.

Input: normal SPN S
Output: BN B = (BV , BE )1: R ← root of S
2: if R is a terminal node over variable X then3:
Create an observable variable X
4:
BV ← BV ∪ {X}
5: else6:
for each child Ri of R do
7:
if BN has not been built for SRi then8:
Recursively build BN Structure for SRi
9:
end if
10:
end for11:
if R is a sum node then12:
Create a hidden variable HR associated with R
13:
BV ← BV ∪ {HR }14:for each observable variable X ∈ SR do
15:
BE ← BE ∪ {(HR , X)}
16:
end for17:
end if
18: end if

X in B for each terminal node over X in S (Lines 2-4). For
each internal sum node v in S, Alg. 1 creates a hidden variable Hv associated with v and builds directed edges from
Hv to all observable variables X appearing in the sub-SPN
rooted at v (Lines 11-17). The BN B created by Alg. 1 has
a directed bipartite structure with a layer of hidden variables pointing to a layer of observable variables. A hidden
variable H points to an observable variable X in B iff X
appears in the sub-SPN rooted at H in S.
We now present Alg. 2 and 3 to build ADDs for each observable variable X and hidden variable H in B. For eachhidden variable H, Alg. 3 builds AH as a decision stump3
obtained by finding H and its associated weights in S.
Consider ADDs built by Alg. 2 for observable variables
Xs. Let X be the current observable variable we are considering. Basically, Alg. 2 is a recursive algorithm applied
to each node in S whose scope intersects with {X}. There3

A decision stump is a decision tree with one variable.

On the Relationship between Sum-Product Networks and Bayesian Networks

Algorithm 2 Build CPD using ADD, observable variable
Input: normal SPN S, variable X
Output: ADD AX
1: if ADD has already been created for S and X then2:
AX ← retrieve ADD from cache
3: else4:
R ← root of S
5:
if R is a terminal node then6:
AX ← decision stump rooted at R
7:else if R is a sum node then8:
Create a node HR into AX
9:for each Ri ∈ Ch(R) do
10:
Link BuildADD(SRi , X) as ith child of HR
11:
end for12:
else if R is a product node then13:
Find child SRi such that X ∈ scope(Ri )14:
AX ← BuildADD(SRi , X)
15:
end if16:
store AX in cache
17: end if

Algorithm 3 Build CPD using ADD, hidden variable
Input: normal SPN S, variable H
Output: ADD AH
1: Find the sum node H in S
2: AH ← decision stump rooted at H in S

are three cases. If the current node is a terminal node, thenit must be a probability distribution over X. In this case we
simply return the decision stump at the current node. If thecurrent node is a sum node, then due to the completeness ofS, we know that all the children of R share the same scopewith R. We first create a node HR corresponding to thehidden variable associated with R into AX (Line 8) andrecursively apply Alg. 2 to all the children of R and linkthem to HR respectively. If the current node is a productnode, then due to the decomposability of S, we know that
there will be a unique child of R whose scope intersects
with {X}. We recursively apply Alg. 2 to this child andreturn the resulting ADD (Lines 12-15).
Equivalently, Alg. 2 can be understood in the following
way: we extract the sub-SPN induced by {X} and contract4 all the product nodes in it to obtain AX . Note thatthe contraction of product nodes will not add more edges
into AX since the out-degree of each product node in the
induced sub-SPN must be 1 due to the decomposability ofthe product node. We illustrate the application of Alg. 1, 2
and 3 on the normal SPN in Fig. 2, which results in the BN
B with CPDs represented by ADDs shown in Fig. 3.
Theorem 4. For any normal SPN S over X1:N , the BN B
constructed by Alg. 1, 2 and 3 encodes the same probability
distribution, i.e., PrS (x) = PrB (x), ∀x.
4

In graph theory, the contraction of a node v in a DAG is theoperation that connects each parent of v to each child of v andthen delete v from the graph.

The proof is by induction on the height of S (see the supplementary material for more details).
Theorem 5. |B| = O(N |S|), where BN B is constructedby Alg. 1, 2 and 3 from normal SPN S over X1:N .
Theorem 6. For any normal SPN S over X1:N , Alg. 1, 2
and 3 construct an equivalent BN in time O(N |S|).
4.3. BN to SPN
Algorithm 4 Multiplication of two symbolic ADDs, ⊗Input: Symbolic ADD AX1 , AX2
Output: Symbolic ADD AX1 ,X2 = AX1 ⊗ AX2
1: R1 ← root of AX1 , R2 ← root of AX2
2: if R1 and R2 are both variable nodes then3:
if R1 = R2 then4:
Create a node R = R1 into AX1 ,X2
5:
for each r ∈ dom(R) do
6:
ArX1 ← Ch(R1 )|r7:
ArX2 ← Ch(R2 )|r
8:
ArX1 ,X2 ← ArX1 ⊗ ArX2
9:Link ArX1 ,X2 to the rth child of R in AX1 ,X2
10:
end for
11:
else
12:
AX1 ,X2 ← create a symbolic node ⊗13:
Link AX1 and AX2 as two children of ⊗14:
end if
15: else if R1 is a variable node and R2 is ⊗ then16:
if R1 appears as a child of R2 then17:
AX1 ,X2 ← AX2
R1
1
18:
AR
X1 ,X2 ← AX1 ⊗ AX2
19:
else
20:
Link AX1 as a new child of R2
21:
AX1 ,X2 ← AX2
22:
end if
23: else if R1 is ⊗ and R2 is a variable node then24:
if R2 appears as a child of R1 then25:
AX1 ,X2 ← AX1
R2
2
26:
AR
X1 ,X2 ← AX2 ⊗ AX1
27:
else
28:
Link AX2 as a new child of R1
29:
AX1 ,X2 ← AX1
30:
end if
31: else
32:
AX1 ,X2 ← create a symbolic node ⊗33:
Link AX1 and AX2 as two children of ⊗34: end if
35: Merge connected product nodes in AX1 ,X2

It is known that a BN with CPDs represented by tables canbe converted into an SPN by first converting the BN intoa junction tree and then translating the junction tree into
an SPN. The size of the generated SPN, however, will be
exponential in the tree-width of the original BN since thetabular representation of CPDs is ignorant of CSI. Hence,
the generated SPN loses its power to compactly represent
some BNs with high tree-width, yet, with CSI in its CPDs.
In this section, we focus on BNs with ADDs that are constructed using Alg. 2 and 3 from normal SPNs. We showOn the Relationship between Sum-Product Networks and Bayesian Networks

AH =

H

h1
+
4
7

9
35

6
35

×

×

H

×

X1

X2

X2

(0.6, 0.4)

(0.9, 0.1)

(0.3, 0.7)

(0.2, 0.8)

h2

h3

h3
6
35

X1
H

X1

4
7

h2

9
35

X2

= AX1

AX2 =

h1

h1
x1
0.6

X1

0.4

h2
h3

x1

x̄1

H

0.9

X1

x2

x̄1
0.1

0.3

X2

x2

x̄2
0.7

0.2

X2
x̄2
0.8

Figure 3. Construct a BN with CPDs represented by ADDs from an SPN. On the left, the induced sub-SPNs used to create AX1 andAX2 by Alg. 2 are indicated in blue and green respectively. The decision stump used to create AH by Alg. 3 is indicated in red.

that when applying VE to those BNs with ADDs we canrecover the original normal SPNs. The key insight is thatthe structure of the original normal SPN naturally defines
a global variable ordering that is consistent with the topological ordering of every ADD constructed.
In order to apply VE to a BN with ADDs, we need toshow how to apply two common operations used in VE,i.e., multiplication of two factors and summing-out a hidden variable, on ADDs. For our purpose, we use a symbolic ADD as an intermediate representation during the inference process of VE by allowing symbolic operations,such as +, −, ×, / to appear as internal nodes in ADDs.
In this sense, an ADD can be viewed as a special typeof symbolic ADD where all the internal nodes are variables. The same trick was applied by (Chavira & Darwiche, 2007) in their compilation approach. For example,
given symbolic ADDs AX1 over X1 and AX2 over X2 ,the multiplication of those ADDs returns a new symbolic
ADD AX1 ,X2 over X1 , X2 such that AX1 ,X2 (x1 , x2 ) ,(AX1 ⊗ AX2 ) (x1 , x2 ) = AX1 (x1 ) × AX2 (x2 ). To simplify the presentation, we choose the inverse topologicalordering of the hidden variables in the original SPN S as
the elimination order used in VE. This helps to avoid thesituations where a multiplication is applied to a sum nodein symbolic ADDs. Other elimination orders could be used,
but a more detailed discussion of sum nodes is needed. The
algorithm for multiplying two symbolic ADDs is listed in
Alg. 4. It is important to point out here that the time complexity of multiplication between two symbolic ADDs isO(|S|), i.e., bounded by the size of the original SPN S
since all the ADDs constructed by Alg. 2 are induced subSPNs with contraction of product nodes from the originalSPN S. Please refer to the supplementary material for amore detailed analysis of the linear complexity of Alg. 4.

To sum-out one hidden variable H, we simply replace H
in A by a symbolic sum node ⊕ and label each edge of⊕ with weights obtained from AH . The algorithm to implement the summing-out operation in a symbolic ADD ispresented in Alg. 5. Note that Alg. 4 and 5 apply only
to ADDs constructed from normal SPNs by Alg. 2 and 3
because such ADDs naturally inherit the topological ordering of sum nodes (hidden variables) in the original SPN
S. Otherwise we need to pre-define a global variable ordering of all the sum nodes and then arrange each ADD
such that its topological ordering is consistent with the predefined ordering. Note also that Alg. 4 and 5 should be
implemented with caching of repeated operations in orderto ensure that directed acyclic graphs are preserved.
We now present the Variable Elimination (VE) algorithm
in Alg. 6 used to recover the original SPN S, taking multiplication and summing-out as two operations ⊗ and ⊕ respectively. In each iteration of Alg. 6, we select one hidden
variable H in ordering π, multiply all the symbolic ADDs
AX in which H appears and then sum-out H from the new
ADD. The algorithm keeps going until all the hidden variables have been summed out and there is only one symbolic
ADD left in Φ. The final symbolic ADD gives us the SPN
S which can be used to build BN B. Note that the SPN
returned by Alg. 6 may not be literally equal to the originalSPN since during the multiplication of two symbolic ADDs
we effectively remove redundant nodes by merging connected product nodes. Hence, the SPN returned by Alg. 6
could have a smaller size while representing the same probability distribution. An example is given in Fig. 4 to illustrate the recovery process. The BN in Fig. 4 is the one
constructed in Fig. 3.
Theorem 7. Alg. 6 builds SPN S from BN B with ADDsin O(N |S|).

On the Relationship between Sum-Product Networks and Bayesian Networks
= AX1
h3

H
h2
x1
0.6

h1

X1
x̄1

0.4

x1
0.9

AX2 =

X1
x̄1
0.1

⊗

h1

H

h2

h3

h1
Multiplication

x2

X2

0.3

x̄2
0.7

x2
0.2

X2

X2
x̄2
0.8

x2

x̄2

0.3

0.7

⊗

H

+

X1
x1

x̄1

0.6

0.4

⊗

4
7

h3

h2

Summing Out

X2
x2

x̄2

0.2

0.8

⊗

×

X1
x1

x̄1

0.9

0.1

9
35

6
35

×

×

X2

X1

X2

X1

(0.3, 0.7)

(0.6, 0.4)

(0.2, 0.8)

(0.9, 0.1)

Figure 4. Multiply AX1 and AX2 that contain H and then sum out H. The final SPN is isomorphic with the SPN in Fig. 3.

Algorithm 5 Summing-out a hidden variable H from A
using AH , ⊕Input: Symbolic ADDs A and AH
Output: Symbolic ADD with H summed out
1: if H appears in A then2:
Label each edge emanating from H with weights from AH
3:
Replace H by a symbolic ⊕ node
4: end if

Algorithm 6 Variable Elimination for a BN with ADDs
Input: BN B with ADDs for all observable and hidden variables
Output: Original SPN S
1: π ← inverse topological order of hidden variables in ADDs
2: Φ ← {AX | X is an observable variable}
3: for each hidden variable H in π do
4:
P ← {AX | H appears in AX }5:
Φ ← Φ\P ∪ {⊕H ⊗A∈P A}
6: end for7: return Φ

5. Discussion and Conclusion
Thm. 1 together with Thm. 2 establish a relationship between BNs and SPNs: SPNs are no more powerful thanBNs with ADD representation. Informally, a model is considered to be more powerful than another one if there exists a distribution that can be encoded in polynomial size
in some input parameter N , while the other model requires
exponential size in N to represent the same distribution.
The key is to recognize that the CSI encoded by the structure of an SPN as stated in Proposition 1 can also be encoded explicitly with ADDs in a BN. We can also view
an SPN as an inference machine that efficiently records
the history of the inference process when applied to a BN.
Based on this perspective, an SPN is actually storing the
calculations to be performed (sums and products), whichallows online inference queries to be answered quicky. The
same idea also exists in other fields, including propositional
logic (d-DNNF) and knowledge compilation (AC).
The constructed BN has a simple bipartite structure, nomatter how deep the original SPN is. However, we canrelate the depth of an SPN to a lower bound on the treewidth of the corresponding BN obtained by our algorithm.
Without loss of generality, let’s assume that product layers
alternate with sum layers in the SPN we are considering.
Let the height of the SPN, i.e., the longest path from theroot to a terminal node, be K. By our assumption, there

will be at least bK/2c sum nodes in the longest path. Accordingly, in the BN constructed by Alg. 1, the observablevariable corresponding to the terminal node in the longest
path will have in-degree at least bK/2c. Hence, after moralizing the BN into an undirected graph, the clique-size ofthe moral graph is bounded below by bK/2c + 1. Notethat for any undirected graph the clique-size minus 1 is always a lower bound of the tree-width. We then reach theconclusion that the tree-width of the constructed BN has
a lower bound of bK/2c. In other words, the deeper the
SPN, the larger the tree-width of the BN constructed by ouralgorithm and the more complex are the probability distributions that can be encoded. This observation is consistent
with the conclusion drawn in (Delalleau & Bengio, 2011)
where the authors prove that there exist families of distributions that can be represented much more efficiently witha deep SPN than with a shallow one, i.e. with substantiallyfewer hidden internal sum nodes. Note that we only give a
proof that there exists an algorithm that can convert an SPN
into a BN without any exponential blow-up. There may exist other techniques to convert an SPN into a BN with amore compact representation and also a smaller tree-width.
High tree-width is usually used to indicate a high inferencecomplexity, but this is not always true as there may exist
lots of CSI between variables, which can reduce inferencecomplexity. CSI is precisely what enables SPNs and BNs
with ADDs to compactly represent and tractably perform
inference in distributions with high tree-width. In contrast, in a Restricted Boltzmann Machine, which is an undirected bipartite Markov network, CSI may not be present
or not exploited, which is why practitioners have to resort to approximate algorithms, such as contrastive divergence (Carreira-Perpinan & Hinton, 2005). Similarly, approximate inference is required in bipartite diagnostic BNs
such as the Quick Medical Reference network (Shwe et al.,1991) since causal independence is insufficient to reducethe complexity, while CSI is not present or not exploited.
Although we mainly focus on the relationship between
SPNs and BNs, our analysis can be straightforwardly applied to the relationship between SPNs and MNs. The insight lies in the fact that we can always moralize a BN into
an MN and an ADD can also be used to encode potential functions defined by cliques in MNs. Our work also
provides a new direction for future research about SPNs
and BNs. Structure and parameter learning algorithms for
SPNs can now be used to indirectly learn BNs with ADDs.

On the Relationship between Sum-Product Networks and Bayesian Networks

References
Amer, Mohamed R and Todorovic, Sinisa. Sum-productnetworks for modeling activities with stochastic structure. In Computer Vision and Pattern Recognition(CVPR), 2012 IEEE Conference on, pp. 1314–1321.
IEEE, 2012.
Bahar, R Iris, Frohm, Erica A, Gaona, Charles M, Hachtel,
Gary D, Macii, Enrico, Pardo, Abelardo, and Somenzi,
Fabio. Algebraic decision diagrams and their applications. Formal methods in system design, 10(2-3):171–
206, 1997.
Boole, George. The mathematical analysis of logic. Philosophical Library, 1847.
Boutilier, Craig, Friedman, Nir, Goldszmidt, Moises,
and Koller, Daphne. Context-specific independence inbayesian networks. In Proceedings of the Twelfth international conference on Uncertainty in artificial intelligence, pp. 115–123. Morgan Kaufmann Publishers Inc.,
1996.
Carreira-Perpinan, Miguel A and Hinton, Geoffrey E. On
contrastive divergence learning. In Proceedings of thetenth international workshop on artificial intelligenceand statistics, pp. 33–40. Citeseer, 2005.
Chavira, Mark and Darwiche, Adnan. Compiling bayesian
networks using variable elimination. In IJCAI, pp. 2443–
2449, 2007.
Chavira, Mark, Darwiche, Adnan, and Jaeger, Manfred.
Compiling relational bayesian networks for exact inference. International Journal of Approximate Reasoning,
42(1):4–20, 2006.
Cheng, Wei-Chen, Kok, Stanley, Pham, Hoai Vu, Chieu,
Hai Leong, and Chai, Kian Ming A. Language modeling with sum-product networks. In Fifteenth Annual
Conference of the International Speech Communication
Association, 2014.
Darwiche, Adnan. A differential approach to inference inbayesian networks. In UAI, pp. 123–132, 2000.
Darwiche, Adnan. Decomposable negation normal form.
Journal of the ACM (JACM), 48(4):608–647, 2001.
Darwiche, Adnan and Marquis, Pierre. A perspective on
knowledge compilation. In IJCAI, volume 1, pp. 175–
182. Citeseer, 2001.
Delalleau, Olivier and Bengio, Yoshua. Shallow vs. deep
sum-product networks. In Advances in Neural Information Processing Systems, pp. 666–674, 2011.

Dennis, Aaron and Ventura, Dan. Learning the architectureof sum-product networks using clustering on variables.
In Advances in Neural Information Processing Systems,
pp. 2042–2050, 2012.
Gens, Robert and Domingos, Pedro. Discriminative learning of sum-product networks. In Advances in Neural
Information Processing Systems, pp. 3248–3256, 2012.
Gens, Robert and Domingos, Pedro. Learning the structureof sum-product networks. In Proceedings of The 30th International Conference on Machine Learning, pp. 873–
880, 2013.
Huang, Jinbo, Chavira, Mark, and Darwiche, Adnan. Solving map exactly by searching on compiled arithmetic circuits. In AAAI, volume 6, pp. 3–7, 2006.
Pagallo, Giulia. Learning DNF by decision trees. In IJCAI,
volume 89, pp. 639–644, 1989.
Peharz, Robert, Geiger, Bernhard C, and Pernkopf, Franz.
Greedy part-wise learning of sum-product networks.
In Machine Learning and Knowledge Discovery in
Databases, pp. 612–627. Springer, 2013.
Peharz, Robert, Kapeller, Georg, Mowlaee, Pejman, andPernkopf, Franz. Modeling speech with sum-productnetworks: Application to bandwidth extension. In
Acoustics, Speech and Signal Processing (ICASSP),
2014 IEEE International Conference on, pp. 3699–3703.
IEEE, 2014.
Poon, Hoifung and Domingos, Pedro. Sum-product networks: A new deep architecture. In Proc. 12th Conf.
on Uncertainty in Artificial Intelligence, pp. 2551–2558,
2011.
Rooshenas, Amirmohammad and Lowd, Daniel. Learning
sum-product networks with direct and indirect variableinteractions. In Proceedings of The 31st International
Conference on Machine Learning, pp. 710–718, 2014.
Roth, Dan. On the hardness of approximate reasoning. Artificial Intelligence, 82(1):273–302, 1996.
Shwe, Michael A, Middleton, B, Heckerman, DE, Henrion, M, Horvitz, EJ, Lehmann, HP, and Cooper, GF.
Probabilistic diagnosis using a reformulation of the
INTERNIST-1/QMR knowledge base. Methods of information in Medicine, 30(4):241–255, 1991.
Zhang, Nevin Lianwen and Poole, David. Exploiting causal
independence in bayesian network inference. Journal of
Artificial Intelligence Research, 5:301–328, 1996.