On the Relationship between Sum-ProductNetworks and Bayesian Networks
Han Zhao, Mazen Melibari and Pascal Poupart{han.zhao, mmelibar, ppoupart}@uwaterloo.caDavid R. Cheriton School of Computer Science, University of Waterloo

Introduction

Our Results• We prove that every Sum-Product Network (SPN) can be converted

into a Bayesian Network (BN) in linear time and space.
• The generated BN has a simple directed bipartite graphical structurewith Algebraic Decision Diagrams (ADDs) as representations of thelocal probability distributions.
• Applying the Variable Elimination algorithm (VE) to the generated
BN will recover the original SPN.
• We introduce normal SPN and present a theoretical analysis of theconsistency and decomposability properties.

Normal SPN:
• Complete and decomposable.
• Locally normalized weights.

Theorem 1:
For any complete and consistent SPN S, there exists a normal SPN S 0020such that PrS (·) = PrS (·) and |S | = O(|S| ).
+10Background

Scope: The set of variables that have indicators among the node’s descendants.
Complete: An SPN is complete iff each sum node has children withthe same scope.
Consistent: An SPN is consistent iff no variable appears negated inone child of a product node and non-negated in another.
Decomposable: An SPN is decomposable iff for every product nodeTv, scope(vi) scope(vj ) = ∅ where vi, vj ∈ Ch(v), i 6= j.
Algebraic Decision Diagram: A graphical representation a real function with boolean input variables, where the graph is a rooted DAG.
X1X3X100000000

X200001111X3001
10011X401010101f (·)
0.4
0.6
0.3
0.3
0.4
0.6
0.3
0.3

X1
11111111

X200001111X3
001
1001
1

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

X1

X2

X2
0.3

X4

0.4

0.6

0.1

X3

X3

0.3

X4

0.4
0.4

0.3

X4

0.1

0.6

0.6

Figure 1: Tabular representaFigure 2: Decision tree Figure 3: ADD repretion
sentation
representation

×+4

product nodes as internal nodes.
• Edges from sum nodes are associated with nonnegative weights.
• The value of a product node is the product of the values of its
children. The value of a sum node is the weighted sum of the valuesof its children. The value of an SPN is the value of its root.

47×+• A rooted DAG with indicator variables as leaves and sum nodes,+

96×

Definition (Poon and Domingos):

Remark 5:
Assuming sum nodes alternate with product nodes in SPN S,
the depth of S is proportional to the maximum in-degree of thenodes in B, which, as a result, is proportional to a lower boundof the tree-width of B.
Theorem 6 (BN to SPN):
Given the BN B with ADD representation of CPDs generated
from a complete and decomposable SPN S over Boolean
variables X1:N , the original SPN S can be recovered byapplying the Variable Elimination algorithm to B in O(N |S|).

+Normal Form

635×××

x1

9X1

261

68

Ix1

Ix̄1

Ix2

Ix̄2

X1

(0.6, 0.4)

X2

(0.9, 0.1)+
935×H×X1X2X2(0.6, 0.4)

(0.9, 0.1)

(0.3, 0.7)

(0.2, 0.8)

47

h2

h3

h2

h3635

X1
H

X1

x̄1

0.9

0.1

x2

h3

X2

X2x2

x̄2

0.3

h20.7

x̄2

0.20.8noit
icalpitlu935

X2= AX1

AX2 =

h1

h1
x1
0.6

X1

0.4

X2
x2
0.3

x̄2
0.7

⌦

x1
0.6

h3

h2

X1
x̄1
0.4

⌦47

Summing Out

X2
x2
0.2

x̄20.8

⌦

x1
0.9

635

⇥

X1

935

⇥

⇥

x̄1
0.1

X2

X1

X2

X1

(0.3, 0.7)

(0.6, 0.4)

(0.2, 0.8)

(0.9, 0.1)Hh2
h3x1x̄1h1+HRemark 7:
The combination of the above two theorems shows thatdistributions for which SPNs allow a compact representationand efficient inference, BNs with ADDs also allow a compact
representation and efficient inference.

Hh1×⌦

X1

h1HM

AH =

6350.4(0.2, 0.8)

Theorem 2 (SPN to BN):
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 time O(N |S|). Furthermore, S and B represent
the same distribution and |B| = O(N |S|).

47x1x̄10.6

X2(0.3, 0.7)h1

X1

AX2 =h3h2+14= AX 1

H9350.9

X1x2x̄10.10.3

X2x2x̄20.7

0.2

X2x̄20.8

Corollary 3:
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 time O(N |S|2). Furthermore, S and B represent2
the same distribution and |B| = O(N |S| ).
Remark 4:
The BN B generated from S has a simple bipartite DAG structure,
where all the source nodes are hidden variables and the terminal nodes
are the Boolean variables X1:N .

Conclusion• The CSI among variables helps to reduce the inference complexity

to enable efficient exact inference even for graphical models withlarge tree-width.
• There may exist other techniques to convert an SPN into a BN with amore compact representation and also a smaller tree-width.
• Structure and parameter learning for SPNs can benefit from theBayesian network perspective.
• The analysis showed in this paper can be straightforwardly appliedto analyze the relationship between SPNs and Markov networks.