CMU CS 10708 - lecture (21 pages)

Previewing pages 1, 2, 20, 21 of 21 page document View the full content.
View Full Document

lecture



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

View the full content.
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

Loading Unlocking...
Login

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

or
We will never post anything without your permission.
Don't have an account?
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?