《Exact Inference on Graphical Models：基于图形模型的精确推理》由会员分享，可在线阅读，更多相关《Exact Inference on Graphical Models：基于图形模型的精确推理（68页珍藏版）》请在金锄头文库上搜索。
1、<p><p>&lt;p&gt;&amp;lt;p&amp;gt;&amp;amp;lt;p&amp;amp;gt;Exact Inference on Graphical Models Samson Cheung Outline nWhat is inference? nOverview nPreliminaries nThree general algorithms for inference nElimination Algorithm nBelief P
2、ropagation nJunction Tree What is inference? Given a fully specified joint distribution (database), inference is to query information about some random variables, given knowledge about other random variables. Evidence: xE Query about XF? Information about XF Conditional/Marginal Prob. Ex. Visual Tra
3、cking you want to compute the conditional to quantify the uncertainty in your tracking Evidence: xE Conditional of XF? Maximum A Posterior Estimate Evidence: xE Most likely value of XF? Error Control Care about the decoded symbol. Difficult to compute the error probability in practice due to high ba
4、ndwidth. Inferencing is not easy nComputing marginals or MAP requires global communication! Marginal: P(p,q)=?Gp,q p(G) Potential: ?(p,q) = exp(-|p-q|) Evidence Outline nWhat is inference? nOverview nPreliminaries nThree general algorithms for inference nElimination Algorithm nBelief Propagation nJu
5、nction Tree Inference Algorithms General Inference Algorithms EXACTAPPROXIMATE General Graph JUNCTION TREE ELIMINATION ALGORITHM Polytrees BELIEF PROPAGATION 1.Iterative Conditional Modes 2.EM 3.Mean field 4.Variational techniques 5.Structural Variational techniques 6.Monte-Carlo 7.Expectation Propa
6、gation 8.Loopy belief propagation NP -hard 1000 nodes: Image Processing Vision Physics 10-100 nodes: Expert systems Diagnostics Simulation Outline nWhat is inferencing? nOverview nPreliminaries nThree general algorithms for inferencing nElimination Algorithm nJunction Tree nProbability Propagation I
7、ntroducing evidence nInferencing : summing or maxing “part” of the joint distribution nIn order not to be sidetrack by the evidence node, we roll them into the joint by considering nHence we will be summing or maxing the entire joint distribution Calculating Marginal Moralization nEvery directed gra
8、ph can be represented as an undirected by linking up parents who have the same child. nDeal only with undirected graph X2X3 X1 X4 X5X6 P(X1) P(X2|X1) P(X3|X1) P(X4|X1) P(X5|X2,X3) P(X 6 6 |X3,X4) X2X3 X1 X4 X5X6 ?(X1,X2,X3) ?(X1,X3,X4) ?(X2,X3,X5) ?(X3,X4,X6) Adding edges is “okay” nThe pdf of an un
9、directed graph can ALWAYS be expressed by the same graph with extra edges added. nA graph with more edge nLose important conditional independence information (okay for inferencing, not good for parameter est.) nUse more storage (why?) X2X3 X1 X4 X5X6 ?(X1,X2,X3) ?(X1,X3,X4) ?(X2,X3,X5) ?(X3,X4,X6) X
10、2X3 X1 X4 X5X6 ?(X1,X2,X3,X4) ?(X2,X3,X5) ?(X3,X4,X6) Undirected graph and Clique graph nClique graph nEach node is a clique from the parametrization nAn edge between two nodes (cliques) if the two nodes (cliques) share common variables X2X3 X1 X4 X5X6 ?C1(X1,X2,X3) ?C2(X1,X3,X4) ?C3(X2,X3,X5) ?C4(X
11、3,X4,X6) ?C5(X7,X8,X9) ?C6(X1,X7) X7X8 X9 ?C1 ?C3 ?C2 ?C6 ?C4 ?C5 Separator: ?C1? ?C3=X2,X3 Outline nWhat is inference? nOverview nPreliminaries nThree general algorithms for inference nElimination Algorithm nBelief Propagation nJunction Tree Computing Marginal nNeed to marginalize x2,x3,x4,x5 nWe n
12、eed to sum N5 terms (N is the number of symbols for each r.v.) nCan we do better? X1 X2 X3 X4 X5 Elimination (Marginalization) Order nTry to marginalize in this order: x5, x4, x3, x2 nComplexity: O(KN3), Storage: O(N2) K=# r.v.s C: O(N3) S: O(N2)C: O(N2) S: O(N)C: O(N3) S: O(N2)C: O(N2) S: O(N) MAP
13、is the same nJust replace summation with max nNote nAll the ms are different from marginal nNeed to remember the best configuration as you go Graphical Interpretation X1 X2 X3 X4 X5 List of active potential functions: ?C1(X1,X2) ?C2(X1,X3) ?C3(X2,X5) ?C4(X3,X5) ?C5(X2,X4) ?C1(X1,X2) ?C2(X1,X3) ?C3(X
14、2,X5) ?C4(X3,X5) ?C5(X2,X4) ?C1(X1,X2) ?C2(X1,X3) ?C5(X2,X4) m5(X2,X3) Kill X5 ?C1(X1,X2) ?C2(X1,X3) ?C5(X2,X4) m5(X2,X3) ?C1(X1,X2) ?C2(X1,X3) m4(X2) m5(X2,X3) Kill X4 ?C1(X1,X2) ?C2(X1,X3) m4(X2) m5(X2,X3) ?C1(X1,X2) m4(X2) m3(X1,X2) Kill X3 ?C1(X1,X2) m4(X2) m3(X1,X2) m2(X1) Kill X2 First real li
15、nk to graph theory nReconstituted Graph = the graph that contain all the extra edges after the elimination nDepends on the elimination order! X3 X1 X2 X4 X5 The complexity of graph elimination is O(NW), where W is the size of the largest clique in the reconstituted graph Proof : Exercise Finding the
16、 optimal order nTo minimize the clique size turns out to be NP-hard1 nGreedy algorithm2: nFind the node v in G that connects to the least number of neighbors nEliminate v and connect all its neighbors nGo back to 1 until G becomes a clique nCurrent best techniques use other simulated annealing3 or a
17、pproximated algorithm4 1 S. Arnborg, D.G. Corneil, A. Proskurowski, Complexity of finding embeddings in a k-tree, SIAM J.Algebraic and Discrete Methods 8 (1987) 277284. 2 D. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl. 32 (1974) 597609. 3U. Kj&amp;amp;amp;#230;rulff, Triangulation of graph-al&amp;amp;lt;/p&amp;amp;gt;&amp;lt;/p&amp;gt;&lt;/p&gt;</p></p>
