11Clique Trees 2Undirected Graphical ModelsHere the couples get to swing!Graphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 18th, 2006Readings:K&F: 9.1, 9.2, 9.3, 9.4K&F: 5.1, 5.2, 5.3, 5.4, 5.510-708 –Carlos Guestrin 20062What if I want to compute P(Xi|x0,xn+1) for each i?Variable elimination for each i?Compute:Variable elimination for every i, what’s the complexity?X0X5X3X4X2X1210-708 –Carlos Guestrin 20063Cluster graph Cluster graph: For set of factors F Undirected graph Each node i associated with a cluster Ci Family preserving: for each factor fj∈ F, ∃ node i such that scope[fi]⊆ Ci Each edge i – j is associated with a separator Sij= Ci∩ CjDIGJSLGJSLHGJCDGSIDSGHJCLI10-708 –Carlos Guestrin 20064Factors generated by VEElimination order:{C,D,I,S,L,H,J,G}DifficultySATGradeHappyJobCoherenceLetterIntelligence310-708 –Carlos Guestrin 20065Cluster graph for VE VE generates cluster tree! One clique for each factor used/generated Edge i – j, if fiused to generate fj “Message” from i to j generated when marginalizing a variable from fi Tree because factors only used once Proposition: “Message” δijfrom i to j Scope[δij] ⊆ SijDIGJSLGJSLHGJCDGSI10-708 –Carlos Guestrin 20066Running intersection property Running intersection property (RIP) Cluster tree satisfies RIP if whenever X∈ Ciand X∈ Cjthen X is in every cluster in the (unique) path from Cito Cj Theorem: Cluster tree generated by VE satisfies RIPDIGJSLGJSLHGJCDGSI410-708 –Carlos Guestrin 20067Constructing a clique tree from VE Select elimination order ≺ Connect factors that would be generated if you run VE with order ≺ Simplify! Eliminate factor that is subset of neighbor10-708 –Carlos Guestrin 20068Find clique tree from chordal graph Triangulate moralized graph to obtain chordal graph Find maximal cliques NP-complete in general Easy for chordal graphs Max-cardinality search Maximum spanning tree finds clique tree satisfying RIP!!! Generate weighted graph over cliques Edge weights (i,j) is separator size – |Ci∩Cj|DifficultyGradeHappyJobCoherenceLetterIntelligenceSAT510-708 –Carlos Guestrin 20069Clique tree & Independencies Clique tree (or Junction tree) A cluster tree that satisfies the RIP Theorem: Given some BN with structure G and factors F For a clique tree T for F consider Ci– Cjwith separator Sij: X – any set of vars in Ciside of the tree Y – any set of vars in Ciside of the tree Then, (X ⊥ Y | Sij) in BN Furthermore, I(T) ⊆ I(G)DIGJSLGJSLHGJCDGSI10-708 –Carlos Guestrin 200610Variable elimination in a clique tree 1 Clique tree for a BN Each CPT assigned to a clique Initial potential π0(Ci) is product of CPTsC2: DIG C4: GJSL C5: HGJC1: CD C3: GSIDSGHJCLI610-708 –Carlos Guestrin 200611Variable elimination in a clique tree 2 VE in clique tree to compute P(Xi) Pick a root (any node containing Xi) Send messages recursively from leaves to root Multiply incoming messages with initial potential Marginalize vars that are not in separator Clique ready if received messages from all neighborsC2: DIG C4: GJSL C5: HGJC1: CD C3: GSI10-708 –Carlos Guestrin 200612Belief from message Theorem: When clique Ciis ready Received messages from all neighbors Belief πi(Ci) is product of initial factor with messages:710-708 –Carlos Guestrin 200613Choice of rootRoot: node 5Root: node 3 Message does not depend on root!!!“Cache” computation: Obtain belief for all roots in linear time!!10-708 –Carlos Guestrin 200614Shafer-Shenoy Algorithm (a.k.a. VE in clique tree for all roots) Clique Ciready to transmit to neighbor Cjif received messages from all neighbors but j Leaves are always ready to transmit While ∃ Ciready to transmit to Cj Send message δi→ j Complexity: Linear in # cliques One message sent each direction in each edge Corollary: At convergence Every clique has correct beliefC2C4C5C1C3C7C6810-708 –Carlos Guestrin 200615Calibrated Clique tree Initially, neighboring nodes don’t agree on “distribution” over separators Calibrated clique tree: At convergence, tree is calibrated Neighboring nodes agree on distribution over separator10-708 –Carlos Guestrin 200616Answering queries with clique trees Query within clique Incremental updates – Observing evidence Z=z Multiply some clique by indicator 1(Z=z) Query outside clique Use variable elimination!910-708 –Carlos Guestrin 200617Message passing with division Computing messages by multiplication: Computing messages by division:C2: DIG C4: GJSL C5: HGJC1: CD C3: GSI10-708 –Carlos Guestrin 200618Lauritzen-Spiegelhalter Algorithm (a.k.a. belief propagation) Initialize all separator potentials to 1 µij← 1 All messages ready to transmit While ∃ δi→ jready to transmit µij’ ← If µij’ ≠ µij δi→j← πj← πj× δi→j µij← µij’ ∀ neighbors k of j, k≠ i, δj→kready to transmit Complexity: Linear in # cliques for the “right” schedule over edges (leaves to root, then root to leaves) Corollary: At convergence, every clique has correct beliefC2C4C5C1C3C7C6Simplified descriptionsee reading for details1010-708 –Carlos Guestrin 200619VE versus BP in clique trees VE messages (the one that multiplies) BP messages (the one that divides)10-708 –Carlos Guestrin 200620Clique tree invariant Clique tree potential: Product of clique potentials divided by separators potentials Clique tree invariant: P(X) = πΤ (X)1110-708 –Carlos Guestrin 200621Belief propagation and clique tree invariant Theorem: Invariant is maintained by BP algorithm! BP reparameterizes clique potentials and separator potentials At convergence, potentials and messages are marginal distributions10-708 –Carlos Guestrin 200622Subtree correctness Informed message from i to j, if all messages into i (other than from j) are informed Recursive definition (leaves always send informed messages) Informed subtree: All incoming messages informed Theorem: Potential of connected informed subtree T’ is marginal over scope[T’] Corollary: At convergence, clique tree is calibrated πi= P(scope[πi]) µij= P(scope[µij])1210-708 –Carlos
View Full Document
Unlocking...