Collapsed Variational Inference for Sum-ProductNetworks
Han Zhao1 , Tameem Adel2 , Geoff Gordon1 , Brandon Amos1
Presented by: Han Zhao
Carnegie Mellon University1 , University of Amsterdam2

June. 20th, 2016

1 / 26

Outline
Background
Sum-Product Networks
Variational Inference
Collapsed Variational Inference
Motivations and Challenges
Efficient Marginalization
Logarithmic Transformation
Experiments
Summary

2 / 26

Sum-Product Networks
Definition

A Sum-Product Network (SPN) is a
I Rooted directed acyclic graph of univariate distributions, sum
nodes and product nodes.
I Value of a product node is the product of its children.
I Value of a sum node is the weighted sum of its children,
where the weights are nonnegative.
I Value of the network is the value at the root.
+w1×

Ix1

w3w2×

Ix̄1×

Ix2

Ix̄23 / 26

Sum-Product Networks
Mixture of Trees

Each SPN can be decomposed as a mixture of trees:+w1

I x1+w3w2××

Ix̄1×

Ix2

Ix̄2= w1++w2×

Ix1

Ix2++w3×

Ix1

Ix̄2×

Ix̄1Ix̄2

I Each tree is a product of univariate distributions.
I Number of mixture components is Ω(2Depth ).
I Each network computes a positive polynomial (posynomial)function of model parameters:Vroot (x | w) =τSXY

t=1 (k,j)∈TtEwkjnYpt (Xi = xi )i=14 / 26

Sum-Product Networks
Bayesian Network

Alternatively, each SPN S is equivalent to a Bayesian network B
with bipartite structure.
H+×××

H1

H2

H3

H4++++××××

X1

X3

X2

X4

⇔

H1

H3

X1

X2

H

H2

H4

X3

X4

I Number of sum nodes in S = Number of hidden variables inB = Θ(|S|). |B| = O(n|S|)

I Number of observable variables in B = Number of variables

modeled by S.

I Typically number of hidden variables  number of observablevariables.

5 / 26

Variational Inference
Brief Introduction

Bayesian Inference:p(w | x) ∝ p(w) p(x | w)
| {z } | {z } | {z }posterior

prior

likelihood

Often intractable because of:
I No analytical solution.
I Expensive numerical integration.

General idea: find the best approximation in a tractable family of
distributions Q:
minimizeq∈QKL[q(w) || p(w | x)]

Typical choice of approximation families: Mean-field, structured
mean-field, etc.
6 / 26

Variational Inference
Brief Introduction

Variational method: Optimization-based, deterministic approach
for approximate Bayesian inference.
inf KL[q(w) || p(w | x)] ⇔ sup Eq [log p(w, x)] + H[q]q∈Qq∈QbEvidence Lower Bound L:
log p(x) ≥ sup Eq [log p(w, x)] + H[q] =: Lbq∈Q

7 / 26

Collapsed Variational Inference
Motivations and Challenges

Bayesian inference algorithms for SPNs:
I Flexible at incorporating prior knowledge about the structureof SPNs.
I More robust to overfitting.

8 / 26

Collapsed Variational Inference
Motivations and Challenges

W1

W2

H1X1

W3

H2X2

H3X3······

I W – Model parameters,Wm

global hidden variables.
I H – Assignments of sum
Hm···nodes, local hidden
variables.
Xn

I X – Observable variables.

DI D – Number of instances.

Challenges for standard VB:
I Large number of local hidden variables: number of local

hidden variables = Number of sum nodes = Θ(|S|).

9 / 26

Collapsed Variational Inference
Motivations and Challenges

W1

W2

H1

X1

W3H2X2

H3

X3······

I W – Model parameters,

Wmglobal hidden variables.
I H – Assignments of sum
Hm···nodes, local hiddenvariables.
XnI X – Observable variables.

DI D – Number of instances.

Challenges for standard VB:
I Large number of local hidden variables: number of local

hidden variables = Number of sum nodes = Θ(|S|).
I Memory overhead: space complexity O(D|S|).

10 / 26

Collapsed Variational Inference
Motivations and Challenges

W1

W2

H1

X1

W3

H2X2

H3X3······

I W – Model parameters,Wm

global hidden variables.
I H – Assignments of sum
Hm···nodes, local hiddenvariables.
Xn

I X – Observable variables.

DI D – Number of instances.

Challenges for standard VB:
I Large number of local hidden variables: number of local

hidden variables = Number of sum nodes = Θ(|S|).
I Memory overhead: space complexity O(D|S|).
I Time complexity: O(nD|S|).
11 / 26

Collapsed Variational Inference
Contributions

Our contributions:b the one
I We obtain better ELBO L to optimize than L,
obtained by mean-field.

I Reduced space complexity: O(D|S|) ⇒ O(|S|), spacecomplexity is independent of training size.

I Reduced time complexity: O(nD|S|) ⇒ O(D|S|), removing

the explicit dependency on the dimension.

12 / 26

Collapsed Variational Inference
Efficient Marginalization

Recall ELBO in standard VI:
Lb := Eq(w,h) [log p(w, h, x)] + H[q(w, h)]Consider the new ELBO in Collapsed VI:
L :=Eq(w) [log p(w, x)] + H[q(w)]X=Eq(w) [logp(w, h, x)] + H[q(w)]hWe can establish the following inequality:log p(x) ≥ L ≥ Lb
The new ELBO in Collapsed VI leads to a better lower bound thanthe one used in standard VI!
13 / 26

Collapsed Variational Inference
ComparisonsStandard Variational Inference QQ
Mean-field assumption: q(w, h) = i q(wi ) j q(hj )ELBO: Lb := Eq(w,h) [log p(w, h, x)] + H[q(w, h)]Collapsed Variational Inference for LDA, HDP
Collapsed out global hidden variables: q(h) =ELBO: Lh := Eq(h) [log p(h, x)] + H[q(h)]Better lower bound: Lh ≥ Lb

Rw q(w, h) dw

Collapsed Variational Inference for SPN
Collapsed out local hidden variables: q(w) =ELBO: Lw := Eq(w) [log p(w, x)] + H[q(w)]Better lower bound: Lw ≥ LbP

h q(w, h)

14 / 26

Collapsed Variational Inference
Efficient Marginalization

Time complexity
P of the exact marginalization incurred incomputing h p(w, h, x):
I Time complexity of marginalization in graphical model G:O(D · 2tw(G) ).

Space complexity reduction:

15 / 26

Collapsed Variational Inference
Efficient Marginalization

Time complexity
P of the exact marginalization incurred incomputing h p(w, h, x):
I Time complexity of marginalization in graphical model G:O(D · 2tw(G) ).
I Exact marginalization in BN B with algebraic decision

diagram as local factors: O(D|B|) = O(nD|S|).

Space complexity reduction:

16 / 26

Collapsed Variational Inference
Efficient Marginalization

Time complexity
P of the exact marginalization incurred incomputing h p(w, h, x):
I Time complexity of marginalization in graphical model G:O(D · 2tw(G) ).
I Exact marginalization in BN B with algebraic decision

diagram as local factors: O(D|B|) = O(nD|S|).

I Exact marginalization in SPN S: O(D|S|).

Space complexity reduction:

17 / 26

Collapsed Variational Inference
Efficient Marginalization

Time complexity
P of the exact marginalization incurred incomputing h p(w, h, x):
I Time complexity of marginalization in graphical model G:O(D · 2tw(G) ).
I Exact marginalization in BN B with algebraic decision

diagram as local factors: O(D|B|) = O(nD|S|).

I Exact marginalization in SPN S: O(D|S|).

Space complexity reduction:
I No posterior over h to approximate anymore.

18 / 26

Collapsed Variational Inference
Efficient Marginalization

Time complexity
P of the exact marginalization incurred incomputing h p(w, h, x):
I Time complexity of marginalization in graphical model G:O(D · 2tw(G) ).
I Exact marginalization in BN B with algebraic decision

diagram as local factors: O(D|B|) = O(nD|S|).

I Exact marginalization in SPN S: O(D|S|).

Space complexity reduction:
I No posterior over h to approximate anymore.
I No variational variables over h needed: O(D|S|) ⇒ O(|S|).

19 / 26

Collapsed Variational Inference
Logarithmic Transformation

New optimization objective:
Eq(w) [logmaximizeq∈QXp(w, h, x)] + H[q(w)]hwhich is equivalent tominimizeq∈QKL[q(w) || p(w)] − Eq(w) [log p(x | w)]

I p(w) – prior distribution over w, product of Dirichlets.
I q(w) – variational posterior over w, product of Dirichlets.
I p(x | w) – likelihood, not multinomial anymore aftermarginalization.

Non-conjugate q(w) and p(x | w), no analytical solution forEq(w) [log p(x | w)].
20 / 26

Collapsed Variational Inference
Logarithmic Transformation

Key observation:p(x | w) = Vroot (x | w) =τSXY

t=1 (k,j)∈TtE

wkjnYpt (Xi = xi )i=1

is a posynomial function of w.
Make a bijective mapping (change of variable): w0 = log(w).
I Dates back to the literature of geometric programming.
I The new objective after transformation is convex in w0 .

log p(x | w) = log τSX
t=1

exp ct +X

wkj0 (k,j)∈TtE

Jensen’s inequality to obtain further lower bound.
21 / 26

Collapsed Variational Inference
Logarithmic Transformation

Further lower bound:
Eq(w) [log p(x | w)] = Eq(w0 ) [log p(x | w0 )] ≥ log p(x | Eq0 (w0 ) [w0 ])Relaxed objective:minimizeq∈QKL[q(w) || p(w)] − log p(x | Eq0 (w0 ) [w0 ]){z}||{z}Regularity

Data fitting

Roughly, log p(x | Eq0 (w0 ) [w0 ]) corresponds the log-likelihood bysetting the weights of SPN as the posterior mean of q(w).
Optimized by projected GD.

22 / 26

Collapsed Variational Inference
Algorithm

I Line 4 – 8 easily parallelizable, distributed version.
I Sample minibatch in Line 4 – 8, stochastic version.

23 / 26

Experiments
I Experiments on 20 data sets, report average log-likelihoods,

Wilcoxon ranked test.
I Compared with (O)MLE-SPN and OBMM-SPN.
MLE-SPN vs CVB-SPN, Avg. log-likelihoods

050100100200
OCVB-Projected GD

CVB-Projected GD

0150
200
250300
400
500

300

600

350700400400350300

250200150
MLE-Projected GD

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

800800

700

600

500
400300OMLE-Projected GD

200100024 / 26

Experiments
OBMM vs OCVB, Avg. log-likelihoods050

OCVB-Projected

100150200250300
300250200150100
OBMM-Moment Matching

50

025 / 26

SummaryThanks
Q&A

26 / 26