# CMU CS 10708 - lecture (21 pages)

Previewing pages 1, 2, 20, 21 of 21 page document
View Full Document

## lecture

Previewing pages 1, 2, 20, 21 of actual document.

View Full Document
View Full Document

## lecture

128 views

Pages:
21
School:
Carnegie Mellon University
Course:
Cs 10708 - Probabilistic Graphical Models
##### Probabilistic Graphical Models Documents
Unformatted text preview:

Probabilistic Graphical Models 10 708 Variational Inference Eric Xing Lecture 18 Nov 14 2005 Reading KF Chap 9 Variational Methods z z For a distribution p X associated with a complex graph computing the marginal or conditional probability of arbitrary random variable s is intractable Variational methods z formulating probabilistic inference as an optimization problem e g f f arg max f S F f a tractable probability distribution or solutions to certain probabilistic queries 1 Lower bounds of exponential functions 8 4 2 1 0 1 2 exp x exp x 1 exp x 1 exp x 3 3 x 2 6 x 1 6 Exponential Family z Exponential representation of graphical models p X exp XD A z Includes discrete models Gaussian Poisson exponential and many others E X XD is referred to as the energy of state x p X exp E X A exp E XH xE A xE 2 Example the Boltzmann distribution on atomic lattice p X exp ij Xi X j i 0Xi Z i j i 1 Lower bounding likelihood Representing q XH by exp E XH Lemma Every marginal distribution q XH defines a lower bound of likelihood p xE d xH exp E xH 1 A xE E xH xE E xH where xE denotes observed variables evidence Upgradeable to higher order bound Leisink and Kappen 2000 3 Lower bounding likelihood Representing q XH by exp E XH Lemma Every marginal distribution q XH defines a lower bound of likelihood p xE C E X H x E C E q q XH d xH q xH log q xH Hq where xE denotes observed variables evidence E q E expected energy Hq entropy q Hq Gibbs free energy KL and variational Gibbs free energy z Kullback Leibler Distance KL q p q z ln z z q z p z Boltzmann s Law definition of energy p z 1 C exp E z KL q p q z E z q z ln q z ln C z z Gibbs Free Energy G q minimized when q Z p Z 4 KL and Log Likelihood z Jensen s inequality l x log p x log p x z z p x z q z x p x z q z x log q z x z log q z x z z l x lc x z q Hq L q KL and Lower bound of likelihood KL q p p x z p x z l x log p x log q z log p z x p z x z p x z q z q z log q z p z x z p x z q z q z log q z log q z p z x z z z ln p D L q l x L q KL q p Setting q q z x closes the gap c f EM A variational representation of probability distributions q arg max E arg min E q Q q Q q q Hq Hq where Q is the equivalent sets of realizable distributions e g all valid parameterizations of exponential family distributions marginal polytopes winright et al 2003 Difficulty Hq is intractable for general q solution approximate Hq and or relax or tighten Q 5 Mean field methods z Optimize q XH in the space of tractable families z z i e subgraph of Gp over which exact computation of Hq is feasible Tightening the optimization space z exact objective z tightened feasible set Hq Q T q arg min E q T q T Q Hq Belief Propagation z Do not optimize q XH explicitly but focus on the set of beliefs z z e g b bi j xi x j bi xi Relax the optimization problem z approximate objective z relaxed feasible set HBetha H H Fbi b i j b q Mo M 0M x M 1 M xi x j x j i o o b arg min b M o z xi E b F b xi The loopy BP algorithm z a fixed point iteration procedure that tries to solve b 6 Loopy Belief Propagation Region based Approximations to the Gibbs Free Energy Kikuchi 1951 Exact G q X intractable Regions G br Xr 7 Bethe Approximation to Gibbs Free Energy z Bethe free energy GBethe ba xa ln fa xa 1 di bi xi ln bi xi a z i xa xi Equal to the exact Gibbs free energy when the factor graph is a tree because in that case b x ba xa bi xi 1 di a z z i But otherwise it may or may not give a lower bound of the likelihood Optimize each b xa s z For discrete belief constrained opt with Lagrangean multiplier z For continuous belief not yet a general formula z Not always converge Minimizing the Bethe Free Energy L GBethe i bi x i 1 i L 0 ba X a X a x i ai xi ba X a bi xi a i N a x i L 0 bi xi xi 1 bi xi exp ai xi d i 1 a N i ba X a exp Ea X a ai xi i N a 8 Bethe BP z Identify ai xi ln m b i xi b N i a z to obtain BP equations i bi xi m a i xi a N i ba X a f a X a m b i xi i N a b N i a Generalized Belief Propagation z Belief in a region is the product of z Local information factors in region z Messages from parent regions z Messages into descendant regions from parents who are not descendants z Message update rules obtained by enforcing marginalization constraints z Kikuchi free energy 9 Generalized Belief Propagation 1 2 3 4 5 6 7 8 9 1245 2356 4578 5689 25 45 56 58 5 Generalized Belief Propagation 1 2 3 4 5 6 7 8 9 1245 2356 4578 5689 25 45 56 58 5 b5 m2 5 m4 5 m6 5 m8 5 10 Generalized Belief Propagation 1 2 3 4 5 6 7 8 9 1245 2356 4578 5689 25 45 56 58 5 b45 f 45 m12 45m78 45m2 5 m6 5 m8 5 Generalized Belief Propagation 1 2 3 4 5 6 7 8 9 1245 2356 4578 5689 25 45 56 58 5 b1245 f12 f14 f 25 f 45 m36 25m78 45m6 5 m8 5 11 Mean Field Approximation Cluster based approx to the Wiegerinck 2001 Gibbs free energy Xing et al 03 04 Exact G q X intractable Clusters G qc Xc 12 Mean field approx to Gibbs free energy z Given a disjoint clustering C1 CI of all variables z Let z Mean field free energy q X qi XC i i GMF qi xCi E x qi xCi ln qi xCi i e g xCi z xCi GMF q xi q x j xi x j q xi xi q xi ln q xi i j xi x j z i i i xi i na …

View Full Document

## Access the best Study Guides, Lecture Notes and Practice Exams Unlocking...
Sign Up

Join to view lecture and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?