DOC PREVIEW
CMU CS 10708 - Lecture

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

11School of Computer ScienceApproximate Inference:Loopy Belief Propagation and variantsProbabilistic Graphical Models (10Probabilistic Graphical Models (10--708)708)Lecture 14, Nov 7, 2007HetunandanHetunandanKamisettyKamisettyReceptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8Receptor AKinase CTF FGene GGene HKinase EKinase DReceptor BX1X2X3X4X5X6X7X8X1X2X3X4X5X6X7X8Reading: KF-Chap. 12, Yedidia et alEric Xing 2An Ising model on 2-D imageNodes encode hidden information (patch-identity).They receive local information from the image (brightness, color).Information is propagated though the graph over its edges.Edges encode ‘compatibility’ between nodes.?air or water ?2Eric Xing 3Why Approximate Inference?Why can’t we just run junction tree on this graph?If NxN grid, tree width atleast NIf N~O(1000), we have a clique with 2100entriesEric Xing 4Undirected graph (Markov random field)Directed graph(Bayesian network)ij)(iixψ),()( jiijxxψiParents(i)factor graphsinteractionsvariablesA recap: Factor Graphs∏ ∏=i ijjiijiixxxZxP)()(),()(1)(ψψ)|()()(parents∏=iiixxPxP∏∈=FfaaaXfZXP )(/1)()(aaXf3Eric Xing 5ikkkkijkkkMki∏∑→→∝kiikxiijiijjjixMxxxxMi)()(),()(ψψCompatibilities (interactions)external evidence?)(iixbBelief PropagationBP Message-update RulesBP on trees always converges to exact marginals (cf. Junction tree algorithm)Eric Xing 6Beliefs and messages in FGi∏∈→∝)()()()(iNaiiaiiiixmxfxb“beliefs” “messages”a∏∏∈→∈→→∝=)(\)()()()()()(aNiiaiaaaaaiNciiciaixmXfXbxmxm?)( =→ iiaxm4Eric Xing 7Approximate Inference: What to approximate?Let us call the actual distribution PWe wish to find a distribution Q such that Q is a “good”approximationRecall the definition of KL-divergenceKL(Q1||Q2)>=0KL(Q1||Q2)=0 iff Q1=Q2We can therefore use KL as a scoring function to decide a good QBut, KL(Q1||Q2) ≠ KL(Q2||Q1)∏∈=FfaaaXfZXP )(/1)(Eric Xing 8Which KL?Computing KL(P||Q) requires inference!But KL(Q||P) can be computed without performing inference on PUsing ))()(log()()||(XPXQXQPQKLX∑=))(/1log()()||(∏∈−−=FfaaQQaXfZEXHPQKL∏∈=FfaaaXfZXP )(/1)(5Eric Xing 9Optimization functionWe will call the “Free energy” *=?F(P,Q) >= F(P,P)ZXfEXHPQKLFfaaQQalog)(log)()||( +−−=∑∈),( QPF),( QPF*Gibbs Free Energy),( PPFEric Xing 10The Free EnergyLet us look at the free energycan be computed if we have marginals over each fais harder! Requires summation over all possible valuesComputing F, is therefore hard in general.Approach 1: Approximate with easy to compute∑∈−−=FfaaQQaXfEXHQPF )(log)(),(∑∈FfaaQaXfE )(log∑=XQXQXQH )(log)(),( QPF∧),( QPF6Eric Xing 11Easy free energiesConsider a tree-structured distributionThe probability can be written as: involves summation over edges and vertices and is therefore easy to compute( ) ( )idiiiaaaxbbb−∏∏=1xx)(()()()()()∑∑∑∑−+−=iaiiiiiiaaaaatreebbdbbHxxxxxx log1log( )()( )( ) ( ) ( )∑∑∑∑−+=iaiiiiiiaaaaaaaTreebbdfbbFxxxxxxx log1log=1X2X3X4X5X6X7X8XEric Xing 12Bethe Approximation to Gibbs Free EnergyFor a general graph, chooseCalled “Bethe approximation” after the physicist Hans BetheEqual to the exact Gibbs free energy when the factor graph is a tree Note: This is not the same as the entropy of a tree( )()( )( ) ( ) ( )∑∑∑∑−+=∧iaiiiiiiaaaaaaabbdfbbQPFxxxxxxx log1log),(1X2X3X4X5X6X7X8X=betheF7Eric Xing 13Bethe ApproximationPros:Easy to compute, since entropy term involves sum over pairwise and single variablesCons:may or may not be well connected toIt could, in general, be greater, equal or less than Optimize each b(xa)'s. For discrete belief, constrained opt. with Lagrangian multiplier For continuous belief, not yet a general formulaNot always convergebetheFQPF =∧),(),( QPF),( QPFEric Xing 14Minimizing the Bethe Free EnergySet derivative to zero( ) ( ) ( )∑ ∑∑ ∑∑∑−+−+=∈a xXaaiiaNi xiaixiiiiBetheiaiiXbxbxxbFL\)( })(1{λγ8Eric Xing 15ProofEric Xing 169Eric Xing 17∏≠∈→→==aiNbiibiaiiaixmxmx)()(log))(log()(λ∏∈→∝)()()(iNaiiaiixmxb∏∈→∝)()()()(aNiiaiaaaaxmXfXbiBethe = BPWe hadIdentifyto obtain BP equations:−∝∑∈ )()(11exp)(iNaiaiiiixdxbλ+−∝∑∈ )()()(logexp)(aNiiaiaaaaxXfXbλEric Xing 18A fixed point iteration procedure that tries to minimize FbetheStart with random initialization of messages and beliefsWhile not converged doAt convergence, stationarity properties are guaranteed. Why?However, not guaranteed to converge!Loopy Belief Propagation∏∈→∝)()()(iNaiiaiixmxb∏∈→∝)()()()(aNiiaiaaaaxmXfXb∏∈→→=aiNciicinewaixmxm\)()()(∑∏∈→→=iaxXiaNjjajaainewiaxmXfxm\\)()()()(10Eric Xing 19Region graphsIt will be useful to look explicitly at the messages being passed Messages from variable to factorsMessages from factors to variablesLet us represent this graphically1X2X3X4X5X6X7X8X26155651221 6Eric Xing 20Summary so far∏∈=FfaaaXfZXP )(/1)(∑∈−−=FfaaQQaXfEXHQPF )(log)(),(( )()( )( ) ( ) ( )∑∑∑∑−+=∧iaiiiiiiaaaaaaabbdbfbQPFxxxxxxx log1log),(−∝∑∈ )()(11exp)(iNaiaiiiixdxbλ+−∝∑∈ )()()(logexp)(aNiiaiaaaaxXfXbλa11Eric Xing 21Better approximations?Recall that Bethe approximation wasWe could construct bigger regionsRules:If a region includes a factor, it must include the vertices as wellEach factor and vertex must appear in atleast one regionAssociate a weight with each region so that each vertex and factor is counted exactly once1X2X3X4X5X6X7X8X8625178672312..22..FFFFFFFFFFbethe−−−−−++++=Eric Xing 22Other regions? 1X2X3X4X5X6X7X8X73623626347823671256^FFFFFFFFFF++++−−++=12Eric Xing 23)]([ XqG)}]([{rrXbGExact:Regions:(intractable)(Kikuchi, 1951)Region-based Approximations to the Gibbs Free EnergyEric Xing 24Belief in a region is the product of:Local information (factors in region)Messages from parent regionsMessages into descendant regions from parents who are not descendants.Message-update rules obtained by enforcing marginalization constraints.Generalized Belief Propagation13Eric Xing 25582356 4578 568925 455612455123456789Generalized Belief Propagation=^FEric


View Full Document

CMU CS 10708 - Lecture

Documents in this Course
Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

causality

causality

53 pages

lecture11

lecture11

16 pages

Exam

Exam

15 pages

Notes

Notes

12 pages

lecture

lecture

18 pages

lecture

lecture

16 pages

Lecture

Lecture

17 pages

Lecture

Lecture

15 pages

Lecture

Lecture

17 pages

Lecture

Lecture

19 pages

Lecture

Lecture

42 pages

Lecture

Lecture

16 pages

r6

r6

22 pages

lecture

lecture

20 pages

lecture

lecture

35 pages

Lecture

Lecture

19 pages

Lecture

Lecture

21 pages

lecture

lecture

21 pages

lecture

lecture

13 pages

review

review

50 pages

Semantics

Semantics

30 pages

lecture21

lecture21

26 pages

MN-crf

MN-crf

20 pages

hw4

hw4

5 pages

lecture

lecture

12 pages

Lecture

Lecture

25 pages

Lecture

Lecture

25 pages

Lecture

Lecture

14 pages

Lecture

Lecture

15 pages

Load more
Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
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 2 2 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?