11School of Computer ScienceApproximate Inference:Loopy Belief Propagation and VariantsProbabilistic Graphical Models (10Probabilistic Graphical Models (10--708)708)Lecture 16, Nov 7, 2007Eric XingEric XingReceptor AKinase CTF FGene GGene HKinaseEKinase DReceptor BX1X2X3X4X5X6X7X8Receptor AKinase CTF FGene GGene HKinaseEKinase DReceptor BX1X2X3X4X5X6X7X8X1X2X3X4X5X6X7X8Reading: KF-Chap. 12Eric Xing 2An Ising model on 2-D imagez Nodes encode hidden information (patch-identity).z They receive local information from the image (brightness, color).z Information is propagated though the graph over its edges.z Edges encode ‘compatibility’ between nodes.?air or water ?2Eric Xing 3Why Approximate Inference?z Tree-width of NxN graph is O(N)z N can be a huge number(~1000s of pixels)z Exact inference will be too expensive⎭⎬⎫⎩⎨⎧+=∑∑< iiijijiijXXXZXp0exp1)(θθEric Xing 4z For a distribution p(X|θ) associated with a complex graph, computing the marginal (or conditional) probability of arbitraryrandom variable(s) is intractablez Variational methodsz formulating probabilistic inference as an optimization problem:{})( minor maxarg*fFff S∈=queries ticprobabiliscertain tosolutions or,ondistributiy probabilit )(tractable a:fe.g.Variational Methods3Eric Xing 5BetheBetheEnergy MinimizationEnergy MinimizationEric Xing 6The Objectivez Let us call the actual distribution Pz We wish to find a distribution Q such that Q is a “good”approximation to Pz Recall the definition of KL-divergencez KL(Q1||Q2)>=0z KL(Q1||Q2)=0 iff Q1=Q2zBut, KL(Q1||Q2) ≠ KL(Q2||Q1)∏∈=FfaaaXfZXP )(/1)())()(log()()||(21121XQXQXQQQKLX∑=4Eric Xing 7Which KL?z Computing KL(P||Q) requires inference!z But KL(P||Q) can be computed without performing inference on Pz Using ))()(log()()||(XPXQXQPQKLX∑=)(log)()(log)( XPXQXQXQXX∑∑−=))(/1log()()||(∏∈−−=FfaaQQaXfZEXHPQKL∏∈=FfaaaXfZXP )(/1)(∑∈−−−=FfaaQQaXfEZXH )(log/1log)()(log)( XPEXHQQ−−=Eric Xing 8The ObjectivezzWe will call the “Energy Functional” *z =?z F(P,Q) >= F(P,P)ZXfEXHPQKLFfaaQQalog)(log)()||( +−−=∑∈),( QPF),( QPF*also called Gibbs Free Energy),( PPF5Eric Xing 9The Energy Functionalz Let us look at the functionalz can be computed if we have marginals over each faz is harder! Requires summation over all possible valuesz Computing F, is therefore hard in general.z Approach 1: Approximate with easy to compute∑∈−−=FfaaQQaXfEXHQPF )(log)(),(∑∈FfaaQaXfE )(log∑−=XQXQXQH )(log)(),( QPF∧),( QPFEric Xing 10Tree Energy Functionalsz Consider a tree-structured distributionz The probability can be written as:zzz involves summation over edges and vertices and is therefore easy to compute()()1−∈∏∏=iiiEjijiijxbxxbb,,)(x()()()()∑∑∑∑×+−=∈ijixiiiiiEjixxjiijjiijtreexbxbxxbxxbH ln,ln, ,,1()()() ()() ()() ()()()()()()()() ()∑∑∑∑∑∑∑∑∑∑∑∑∑∑×−+=−−⎟⎟⎠⎞⎜⎜⎝⎛×+−−=∈∈∈iijiijiijixiiiiiixiiiiiiEjijijijiijxxjiijixiiiiEjijijixxjiijxiiiiiEjijiijxxjiijTreexbxbxfxbxbxxfxxbxxbxfxbxxfxxbxbxbxxbxxbFlnln,,ln,ln,ln, ln,ln, ,,,,,,,,211X2X3X4X5X6X7X8X73625178672312.. FFFFFFFFFF−−−−−−++++=6Eric Xing 11Tree Energy Functionalsz Consider a tree-structured distributionz The probability can be written as:zzz involves summation over edges and vertices and is therefore easy to compute()()idiiiaaaxbbb−∏∏=1xx)(()()()()()∑∑∑∑−+−=iaiiiiiiaaaaatreebbdbbHxxxxxx lnln 1()()()( ) () ()∑∑∑∑−+=iaiiiiiiaaaaaaaTreebbdfbbFxxxxxxx lnln 11X2X3X4X5X6X7X8X73625178672312.. FFFFFFFFFF−−−−−−++++=Eric Xing 12Bethe Approximation to Gibbs Free Energyz For a general graph, choosez Called “Bethe approximation” after the physicist Hans Bethez Equal to the exact Gibbs free energy when the factor graph is a treez In general, HBetheis not the same as the H of a treeBethaFQPF =∧),(1X2X3X4X5X6X7X8X862517867231222 FFFFFFFFFFbethe−−−−−++++= ....()()()( ) () () ()bethaaaiiiiiiaaaaaaaBetheHfbbdfbbFia−−=−+=∑∑∑∑xxxxxxxxlnln 1()()()()()∑∑∑∑−+−=iaiiiiiiaaaaaBethebbdbbHxxxxxx lnln 17Eric Xing 13Bethe Approximationz Pros:z Easy to compute, since entropy term involves sum over pairwise and single variablesz Cons:z may or may not be well connected toz It could, in general, be greater, equal or less than z Optimize each b(xa)'s. z For discrete belief, constrained opt. with Lagrangian multiplier z For continuous belief, not yet a general formulaz Not always convergebetheFQPF =∧),(),( QPF),( QPFEric Xing 14Undirected graph (Markov random field)Directed graph(Bayesian network)∏∏=iijjiijiixxxZxP)()(),()(1)(ψψij)(iixψ),()( jiijxxψ)|()()(parents∏=iiixxPxPiParents(i)factor graphsinteractionsvariablesFrom GM to factored graphs8Eric Xing 15Recall Beliefs and messages in FGi∏∈→∝)()()()(iNaiiaiiiixmxfxb“beliefs” “messages”a∏∏∈∈→∝)(\)()()()(aNiaiNciicaaaaxmXfXbThe “belief” is the BP approximation of the marginal probability.Eric Xing 16Bethe Free Energy for FG()()()( ) () ()∑∑∑∑−+=iaiiiiiiaaaaaaaBethabbdfbbFxxxxxxx lnln 1()()()()()∑∑∑∑−+−=iaiiiiiiaaaaaBethebbdbbHxxxxxx lnln 1()bethaaaBetheHfF −−= x9Eric Xing 17() ( ) ()∑∑∑∑∑∑⎭⎬⎫⎩⎨⎧−+−+=∈axXiiaaaNixiaixiiiiBetheiaiixbXbxxbFL\)( }1)({λγ0)(=∂∂iixbL⎟⎟⎠⎞⎜⎜⎝⎛−∝∑∈ )()(11exp)(iNaiaiiiixdxbλ0)(=∂∂aaXbL⎟⎟⎠⎞⎜⎜⎝⎛+−∝∑∈ )()()(exp)(aNiiaiaaaaxXEXbλConstrained Minimization of the Bethe Free EnergyEric Xing 18Bethe = BP on FGz Identifyz to obtain BP equations:i∏∈→∝)()()()(iNaiiaiiiixmxfxb“beliefs” “messages”a∏∏∈∈→∝)(\)()()()(aNiaiNciicaaaaxmXfXbThe “belief” is the BP approximation of the marginal probability.∏≠∈→=aiNbiibiaixmx)()(ln)(λ10Eric Xing 19Using,)()(\∑=→iaxXaaiiaXbxbwe getai∑∑∏∏∈∈→→=iaxXiaNjajNbjjbaaiiaxmXfxm\\)(\)()()()(ia=BP Message-update Rules( A sum product algorithm )Eric Xing 20ikkkkijkkkMki∏∑→→∝kiikxiijiijjjixMxxxxMi)()(),()(ψψCompatibilities (interactions)external evidence∏∝kkkiiiixMxxb )()()(ψBelief Propagation on treesz BP Message-update Rulesz BP on trees always converges to exact marginals (cf. Junction tree algorithm)11Eric Xing 21ikkkkijkkkMkiBelief Propagation on loopy graphsz BP Message-update Rulesz May not converge or converge to a wrong solution∏∑→→∝kiikxiijiijjjixMxxxxMi)()(),()(ψψCompatibilities
View Full Document
Unlocking...