Variational Mean Field For Graphical Models - Computing

Variational Mean Fieldfor Graphical ModelsCS/CNS/EE 155Baback MoghaddamMachine Learning Groupbaback @ jpl.nasa.gov

Approximate Inference Consider general UGs (i.e., not tree-structured) All basic computations are intractable (for large G)- likelihoods & partition function- marginals & conditionals- finding modes

Taxonomy of Inference bbs, M-HDeterministic(MC) MC, SACluster MPLBPEPVariational

Approximate Inference Stochastic (Sampling)- Metropolis-Hastings, Gibbs, (Markov Chain) Monte Carlo, etc- Computationally expensive, but is “exact” (in the limit) Deterministic (Optimization)- Mean Field (MF), Loopy Belief Propagation (LBP)- Variational Bayes (VB), Expectation Propagation (EP)- Computationally cheaper, but is not exact (gives bounds)

Mean Field : Overview General idea- approximate p(x) by a simpler factored distribution q(x)- minimize “distance” D(p q) - e.g., Kullback-Liebleroriginal Gp( x) (Naïve) MF H0 φ ( x )cccq ( x) structured MF Hs q (x )iiiq ( x ) q A ( x A ) q B ( xB )

Mean Field : Overview Naïve MF has roots in Statistical Mechanics (1890s)- physics of spin glasses (Ising), ferromagnetism, etc- why is it called “Mean Field” ?with full factorization : E[xi xj ] E[xi ] E[xj ] Structured MF is more “modern”Coupled HMMStructured MF approximation(with tractable chains)

KL Projection D(Q P ) Infer hidden h given visible v (clamp v nodes with δ ‘s) Variational : optimize KL globallythe right density form for Q “falls out”KL is easier since we’re taking E [.] wrt simpler QQ seeks mode with the largest mass (not height)so it will tend to underestimate the support of PP 0 forces Q 0

KL Projection D(P Q ) Infer hidden h given visible v (clamp v nodes with δ ‘s) Expectation Propagation (EP) : optimize KL locallythis KL is harder since we’re taking E [.] wrt Pno nice global solution for Q “falls out”must sequentially tweak each qc (match moments)Q covers all modes so it overestimates supportP 0 forces Q 0

α - divergences The 2 basic KL divergences are special cases of Dα (p q) is non-negative and 0 iff p q– when α– when α- 1 we get KL(P Q) 1 we get KL(Q P)– when α 0 D0 (P Q) is proportional to Hellinger’s distance (metric)So many variational approximations must exist, one for each α !

for more on α - divergencesShun-ichi Amari

for specific examples of α 1See Chapter 10Variational Single GaussianVariational Linear RegressionVariational Mixture of GaussiansVariational Logistic RegressionExpectation Propagation (α -1)

Hierarchy of Algorithms(based on α and structuring)Power EP exp family Dα(p q)Structured MF exp family KL(q p)FBP fully factorized Dα(p q)EP exp family KL(p q)MF fully factorized KL(q p)TRW fully factorized Dα(p q) α 1BP fully factorized KL(p q)by Tom Minka

Variational MF11 ψ ( x)p( x) γ c ( xc ) eZ cZlog Z log eψ ( x)ψ ( x) clog(γ c ( xc ))dxe log Q( x)dxQ( x)ψ ( x) supQ EQ log [eJensen’sψ ( x) EQ log [eψ ( x ) / Q( x)]/ Q( x)] supQ { EQ [ψ ( x)] H [Q( x)] }

Variational MFlog Z supQ { EQ [ψ ( x)] H [Q( x)] }Equality is obtained for Q(x) P(x)(all Q admissible)Using any other Q yields a lower bound on log ZThe slack in this bound is KL-divergence D(Q P)Goal: restrict Q to a tractable subclass Qoptimize with supQ to tighten this boundnote we’re (also) maximizing entropy H[Q]

Variational MFlog Z supQ { EQ [ψ ( x)] H [Q( x)] }Most common specialized family :“log-linear models”ψ ( x) cθc φc ( xc ) θ Tφ ( x)linear in parameters θ(natural parameters of EFs)φ (x)(sufficient statistics of EFs)clique potentialsFertile ground for plowing Convex Analysis

Convex AnalysisThe Old TestamentThe New Testament

Variational MF for EFlog Z supQ { EQ [ψ ( x)] H [Q( x)] }log Z supQ { EQ [θ φ ( x)] H [Q( x)] }log Z supQ {θ EQ [φ ( x)] H [Q( x)] }TTA(θ ) sup µ M {θ µ A * ( µ ) }TM set of all moment parameters realizable under subclass QEFnotation

Variational MF for EFSo it looks like we are just optimizing a concave function(linear term negative-entropy) over a convex setYet it is hard . Why?1. graph probability (being a measure) requires a very largenumber of marginalization constraints for consistency (leadsto a typically beastly marginal polytope M in the discrete case)e.g., a complete 7-node graph’s polytope has over 108 facets !In fact, optimizing just the linear term alone can be hard2. exact computation of entropy -A*(µ) is highly non-trivial(hence the famed Bethe & Kikuchi approximations)

Gibbs Sampling for Ising Binary MRF G (V,E ) with pairwise clique potentials1. pick a node s at random2. sample u Uniform(0,1)3. update node s :4. goto step 1a slower stochastic version of ICM

Naive MF for Ising use a variational mean parameter at each site1. pick a node s at random2. update its parameter :3. goto step 1 deterministic “loopy” message-passing how well does it work? depends on θ

Graphical Models as EF G(V,E) with nodes sufficient stats : clique potentials probability log-partition mean parameterslikewise for θ st

Variational Theorem for EF For any mean parameter µ where θ (µ ) is the corresponding natural parameterin relative interior of Mnot in the closure of M the log-partition function has this variational representation this supremum is achieved at the moment-matching value of µ

Legendre-Fenchel Duality Main Idea: (convex) functions can be “supported” (lower-bounded) by acontinuum of lines (hyperplanes) whose intercepts create a conjugate dualof the original function (and vice versa)conjugate dual of Aconjugate dual of A*Note that A** A (iff A is convex)

Dual Map for EFTwo equivalent parameterizations of the EFBijective mapping between Ω and the interior of MMapping is defined by the gradients of A and its dual A*Shape & complexity of M depends on X and size and structure of G

Marginal Polytope G(V,E) graph with discrete nodes Then M convex hull of all φ (x) equivalent to intersecting half-spaces aT µ b difficult to characterize for large G hence difficult to optimize over interior of M is 1-to-1 with Ω

The Simplest Graph G(V,E) a single Bernoulli nodexφ (x) x density log-partition(of course we knew this) we know A* too, but let’s solve for it variationally differentiate rearrange tostationary point, substitute into A*Note: we found both the meanparameter and the lower boundusing the variational method

The 2nd Simplest Graphx1x2 G(V,E) 2 connected Bernoulli nodes moments variational problem solve (it’s still easy!)moment constraints

The 3rd Simplest Graphx1x2x33 nodes16 constraints# of constraints blows up real fast:7 nodes200,000,000 constraintshard to keep track of valid µ’s(i.e., the full shape and extent of M )no more checking our results againstclosed-forms expressions that wealready knew in advance!unless G remains a tree, entropy A*will not decompose nicely, etc

Variational MF for Ising tractable subgraph H (V,0 ) fully-factored distribution moment space entropy is additive :- variational problem for A(θ ) using coordinate ascent :

Variational MF for Ising Mtr is a non-convex inner approximationM tr Mwhat causes this funky curvature? optimizing over Mtr must then yield a lower bound

Factorization with Trees suppose we have a tree G (V,T ) useful factorization for trees entropy becomes- singleton terms- pairwise termsMutual Information

Variational MF for Loopy Graphs pretend entropy factorizes like a tree (Bethe approximation) define pseudo marginalsmust impose thesenormalizationand marginalizationconstraints define local polytope L(G ) obeying these constraints note thatM (G ) L(G ) for any Gwith equality only for trees : M(G ) L(G )

Variational MF for Loopy GraphsL(G) is an outer polyhedral approximationsolving this Bethe Variational Problem we get the LBP eqs !so fixed points of LBP are thestationary points of the BVPthis not only illuminates what was originally an educated “hack” (LBP)but suggests new convergence conditions and improved algorithms (TRW)

see ICML’2008 Tutorial

Summary SMF can also be cast in terms of “Free Energy” etc Tightening the var bound min KL divergence Other schemes (e.g, “Variational Bayes”) SMF- with additional conditioning (hidden, visible, parameter) Solving variational problem gives both µ and A(θ ) Helps to see problems through lens of Var Analysis

Matrix of Inference MethodsExactDiscreteDeterministic approximationChain (online)Low treewidthHigh treewidthBP forwardsVarElim, Jtree,recursiveconditioningLoopy BP, mean field,structured variational,EP, graph-cutsJtree sparse linearalgebraLoopy BPEP, EM, VB,EP, variational EM, VB,NBP, GibbsBoyen-Koller (ADF),beam searchGaussianOtherStochastic approximationBP Kalman filterEKF, UKF, momentmatching (ADF)Particle filterNBP, GibbsGibbsGibbsBP Belief Propagation, EP Expectation Propagation, ADF Assumed Density Filtering, EKF Extended Kalman Filter,UKF unscented Kalman filter, VarElim Variable Elimination, Jtree Junction Tree, EM Expectation Maximization,VB Variational Bayes, NBP Non-parametric BPby Kevin Murphy

THEEND

entropy is additive :- variational problem for A(q) . Matrix of Inference Methods EP, variational EM, VB, NBP, Gibbs EP, EM, VB, NBP, Gibbs EKF, UKF, moment matching (ADF) Particle filter Other Loopy BP Gibbs Jtree sparse linear algebra Gaussian BP Kalman filter Loopy BP, mean field, structured variational, EP, graph-cuts Gibbs