Linear Time Computation of Moments in
Sum-Product Networks
Han Zhao and Geoff Gordon
Machine Learning Department, Carnegie Mellon UniversityMp(f (wk,j )) =Recursive computation of the network:j∈Ch(k) wk,j Vj (x; w)

Scope: The set of variables that have univariate distributions among
the node’s descendants.
Complete: An SPN is complete iff each sum node has children withthe same scope.
Decomposable: An SPN is decomposable iff for every product nodeTv, scope(vi) scope(vj ) = ∅ where vi, vj ∈ Ch(v), i 6= j.

Summary• So far the best algorithm for moment computation scales

quadratically in the size of Sum-product Networks (SPNs).
• We propose an optimal linear-time algorithm that works evenwhen the SPN is a general directed acyclic graph (DAG).
I A linear time reduction from the moment computation problem
to a joint inference problem.
I An efficient procedure for polynomial evaluation bydifferentiation without expanding the network.
I A dynamic programming method to reduce the computation ofthe moments of all the edges from quadratic to linear.
• Applications:
I Online moment matching
I Assumed density filteringNIPS-2017• Naive computation: Ω(|S| · 2H(S))
2• Recursive algorithm for trees: O(|S|), but O(|S| ) for DAGs
(Rashwan et al., 2016)

Sufficient statistics for each edge contains three terms:• Forward value Vj at the child.
• Backward value Dk at the parent.
• Edge weight wk,j .

Quadratic to Linear: For all edges (k, j), moments can be computedin O(|S|) time, using only two more copies of the network.

Linear Time Reduction to Joint Inference:
For each edge (k, j), partition all the trees into two sets:• TT = {Tt : t ∈ [τ ], (k, j) ∈ Tt}, trees containing the edge.
• TF = {Tt : t ∈ [τ ], (k, j) 6∈ Tt}, trees not containing the edge.

Mp(f (wk,j )) = 1XZx Tt∈TF 1ctut Mp0,k (f (wk,j )) + 

Applications
Used as subroutines to develop linear time algorithms for Bayesian
moment matching (BMM) and assumed density filters (ADF).
Runtime (log-seconds) over 20 real-world data sets.

X

Zx Tt∈TTctut Mp0(f(w))
k,j0,kEfficient Polynomial Evaluation by Differentiation:PτPτKey observation 1: t∈TT ctut + t∈TF ctut can be computed in O(|S|)
time and space in a bottom-up evaluation of S, by re-defining the edge
weights of the network.
PτP
Key observation 2: Tt∈TT ctut = wk,j (∂ t=1 ctut/∂wk,j ), and it canbe computed in O(|S|) time and space in a top-down differentiationof S, by the multilinear nature of the network polynomial.
Example:Running Time of Online Algorithms

13PGD
EGSMA
CCCP
CVB
BMMADF121110987
65g(x1, x2, x3) = 4x1x2 + 3x2x3 + 5x1x3⇒∂
x1g(x1, x2, x3) = 4x1x2 + 3x2x3 + 5x1x3∂x1XXX


X

X

XXXX


December 6, 2017

4Netflix




P


Z
τ
Y
1 X
=
ct p0(w)f (wk,j )wk0,j 0 dw
Zx t=1 w(k 0,j 0)∈TtE

Audio

Vk (x; w) =  j∈Ch(k) Vj (x; w)

if k is a leaf node over Xi
if k is a product node
if k is a sum node

wf (wk,j )p(w | x) dw

Reuters-52

p(X=x)
ii

QZ

JesterIx̄2

MSNBC

Ix̄1

WebKB

Ix̄2

BBCIx1

×

KosarekIx2

f -moment on each edge in the network:

×KDD

Ix1+w3×

PlantsIx̄2+w2×

EachMovie

Ix2

= w1

×

Vj (x; w) ×

DNAIx̄1×+

Pumsb-star×+∂Vroot(x; w)
Dk (x; w) =∂Vk (x; w)

wk,jAccidentsw2

×

I x1+w3

Dk (x; w)+MSWeb+w1

For each edge (k, j), moment can be computed in O(|S|) time andspace. Naive computation leads to O(|S|2) for all edges.

Retailnodes and product nodes.
• We focus on discrete SPNs, but the proposed algorithms work forcontinuous ones as well.

Exact Posterior Has Exponentially Many Modes:
Every complete and decomposable SPN S can be factorized into asum of Ω(2H(S)) induced trees (sub-graphs), where each tree corresponds to a product of univariate distributions. H(S) = height of S:τ YmnYY1 Xp(w | x) =Dir(wk ; αk )wk,j pt(xi)Zx t=1 k=1
i=1(k,j)∈TtEBook• Rooted directed acyclic graph of univariate distributions, sum

Dynamic Programming

Ad

Sum-Product Networks (SPNs):

Linear Time Exact Moment Computation

NLTCS

Backgroundhan.zhao@cs.cmu.edu