Collapsed Variational Inference for
Sum-Product Networks
1211Han Zhao , Tameem Adel , Geoff Gordon and Brandon Amos
12
{han.zhao, ggordon, bamos}@cs.cmu.edu, T.M.A.A.Hesham@uva.nl
12Carnegie Mellon University, University of Amsterdam;Radboud University
Introduction

Collapsed Variational Inference• Sum-Product Networks (SPNs) are probabilistic inference machines thatadmit exact inference in linear time in the size of the network.
• We develop a deterministic collapsed variational inference algorithm for
SPNs that is both computationally and statistically efficient.
• The proposed algorithm can be easily adapted to stochastic anddistributed settings.
• The proposed algorithm has a linear reduction in both time and spacecomplexity compared with standard variational inference algorithm.

Qm
k=1 p(wk |αk )α) =Prior distribution over model parameters: p(w|αQm
k=1 Dir(wk |αk ). Exact posterior in computationally intractable:mYDp(w|{xd}d=1, α ) ∝Dir(wk |αk )

τSD X
YYwkj

d=1 t=1 (k,j)∈TtE

k=1nY=pt(xdi)i=1Standard Variational Bayes Inference:
Mean Field assumption:q(w, h) =Yq(wi)iYq(hj )jEvidence Lower BOund (ELBO):
L := Eq(w,h)[log p(w, h, x)] + H[q(w, h)]cBackground

Collapsed Variational Bayes Inference:
Using exact conditional distribution q(h|w), leading to the new ELBO:

Sum-Product Networks (SPNs):

L := Eq(w)[log p(w, x)] + H[q(w)]• Rooted directed acyclic graph of univariate distributions, sum nodes andproduct nodes.
• Value of a product node is the product of its children.
• Value of a sum node is the weighted sum of its children, where theweights are nonnegative.
• Value of the network is the value at the root.

PEquivalent to marginalizing out local hidden variables: q(w) = h q(w, h)

Recursive computation of the network:

Variational optimization formulation:p(X=x)ii
QVk (x | w) =  j∈Ch(k) Vj (x | w)

P


j∈Ch(k) wkj Vj (x | w)

before approximating the true marginal posterior distribution.
α) ≥ L ≥ L.
• A better lower bound: log p(x|αc• Reduced space complexity: O(D|S|) ⇒ O(|S|).
• Reduced time complexity: O(nD|S|) ⇒ O(D|S|).

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

No closed form solution for Eq(w)[log p(x|w)] due to the non-conjugacy
between q(w) and p(x|w).
Logarithmic Transformation:0
Bijective mapping (change of variable) w = log(w), leading to:

SPNs as Mixture of Trees:
+w1
×

I x1+

w3

w2
×

Ix̄1×

Ix2

= w1

Ix̄2++w2

×

Ix1

Ix2++w3×

Ix1

Ix̄2

Ix̄1f (w) , Vroot(x|w) =τSXYt=1 (k,j)∈TtE

wkjnY

Ix̄2Eq(w)[log p(x | w)] = Ept(Xi = xi)

i=1

q(w0)

Equivalent Bayesian Networks:
Each SPN S is equivalent to a Bayesian network B with bipartite structure.
···0[log p(x | w )] ≥ log p(x | Eq 0(w0)0[w ])Relaxed objective:0KL[q(w) || p(w)] − log p(x | Eq0(w0)[w ])minimizeq∈QW3

a convex function of w0. Apply Jensen’s inequality to obtain further lower
bound:

is a posynomial function of w.

W2

τSXX0 log p(x | w) = log  exp ct +wkj t=1(k,j)∈TtE

×Let τS = Vroot(1|1).

W1KL[q(w) || p(w)] − Eq(w)[log p(x | w)]

minimizeq∈Q{zRegularity|}|{zData fitting}

Optimized by Projected gradient descent. Easily extended to stochastic anddistributed settings.

Wm

Experiments
Compared with (O)MLE-SPN, OBMM on 20 benchmark data sets. Measuring average log-likelihoods on test data.

···

HmX1X2X3···

MLE-SPN vs CVB-SPN, Avg. log-likelihoods0Xn50

100

100200150200250700D• Number of observable variables in B = Number of variables in S.
• Number of sum nodes in S = Number of hidden variables in B = Θ(|S|).

|B| = O(n|S|).
• Typically number of hidden variables  number of observablevariables, i.e., m  n.
• Hj are local hidden variables. Wj are global hidden variables.

300

250
200150
MLE-Projected GD

100

50

0100500

350
350

50400

600

OBMM vs OCVB, Avg. log-likelihoods

0300

300400400

OMLE-SPN vs OCVB-SPN, Avg. log-likelihoods

0

OCVB-ProjectedH3

OCVB-Projected GD

H2CVB-Projected GD

H1150200250800
800700600500400300
OMLE-Projected GD

2001000300300

250200150
100
OBMM-Moment Matching

50Conclusion• CVB-SPN maintains a variational posterior distribution over global

hidden variables by marginalizing out all the local hidden variables.
• CVB-SPN is both computationally and statistically efficient.

0