Clique Trees 2 Undirected Graphical Models Here the couples get to swing!What if I want to compute P(Xi|x0,xn+1) for each i?Cluster graphFactors generated by VECluster graph for VERunning intersection propertyConstructing a clique tree from VEFind clique tree from chordal graphClique tree & IndependenciesVariable elimination in a clique tree 1Variable elimination in a clique tree 2Belief from messageChoice of rootShafer-Shenoy Algorithm (a.k.a. VE in clique tree for all roots)Calibrated Clique treeAnswering queries with clique treesMessage passing with divisionLauritzen-Spiegelhalter Algorithm (a.k.a. belief propagation)VE versus BP in clique treesClique tree invariantBelief propagation and clique tree invariantSubtree correctnessClique trees versus VEClique tree summaryAnnouncementsSwinging Couples revisitedPotentials (or Factors) in Swinging CouplesComputing probabilities in Markov networks v. BNsNormalization for computing probabilitiesFactorization in Markov networksGlobal Markov assumption in Markov networksThe BN Representation TheoremMarkov networks representation Theorem 1What about the other direction for Markov networks ?Markov networks representation Theorem 2 (Hammersley-Clifford Theorem)Representation Theorem for Markov NetworksCompleteness of separation in Markov networksWhat are the “local” independence assumptions for a Markov network?Local independence assumptions for a Markov networkEquivalence of independencies in Markov networksMinimal I-maps and Markov NetworksHow about a perfect map?Unifying properties of BNs and MNsWhat you need to know so far about Markov networks1Clique 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 20062 What 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?X0X5X3X4X2X110-708 – Carlos Guestrin 20063 Cluster graphCluster graph: For set of factors FUndirected graphEach node i associated with a cluster Ci Family preserving: for each factor fj 2 F, 9 node i such that scope[fi]µ CiEach edge i – j is associated with a separator Sij = Ci Å CjDIGJSLGJSLHGJCDGSIDSGHJCLI10-708 – Carlos Guestrin 20064 Factors generated by VEElimination order:{C,D,I,S,L,H,J,G}DifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 20065 Cluster graph for VEVE generates cluster tree!One clique for each factor used/generatedEdge i – j, if fi used to generate fj“Message” from i to j generated when marginalizing a variable from fiTree because factors only used onceProposition:“Message” ij from i to jScope[ij] µ SijDIGJSLGJSLHGJCDGSI10-708 – Carlos Guestrin 20066 Running intersection propertyRunning intersection property (RIP)Cluster tree satisfies RIP if whenever X2 Ci and X2 Cj then X is in every cluster in the (unique) path from Ci to CjTheorem:Cluster tree generated by VE satisfies RIPDIGJSLGJSLHGJCDGSI10-708 – Carlos Guestrin 20067 Constructing a clique tree from VESelect 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 20068 Find clique tree from chordal graphTriangulate moralized graph to obtain chordal graphFind maximal cliquesNP-complete in generalEasy for chordal graphs Max-cardinality search Maximum spanning tree finds clique tree satisfying RIP!!!Generate weighted graph over cliquesEdge weights (i,j) is separator size – |CiÅCj|DifficultyGradeHappyJobCoherenceLetterIntelligenceSAT10-708 – Carlos Guestrin 20069 Clique tree & IndependenciesClique tree (or Junction tree)A cluster tree that satisfies the RIPTheorem:Given some BN with structure G and factors FFor a clique tree T for F consider Ci – Cj with separator Sij:X – any set of vars in Ci side of the treeY – any set of vars in Ci side of the treeThen, (X Y | Sij) in BNFurthermore, I(T) µ I(G)DIGJSLGJSLHGJCDGSI10-708 – Carlos Guestrin 200610 Variable elimination in a clique tree 1Clique tree for a BNEach CPT assigned to a cliqueInitial potential 0(Ci) is product of CPTsC2: DIG C4: GJSL C5: HGJC1: CD C3: GSIDSGHJCLI10-708 – Carlos Guestrin 200611 Variable elimination in a clique tree 2VE in clique tree to compute P(Xi)Pick a root (any node containing Xi)Send messages recursively from leaves to rootMultiply incoming messages with initial potentialMarginalize vars that are not in separatorClique ready if received messages from all neighborsC2: DIG C4: GJSL C5: HGJC1: CD C3: GSI10-708 – Carlos Guestrin 200612 Belief from messageTheorem: When clique Ci is readyReceived messages from all neighborsBelief i(Ci) is product of initial factor with messages:10-708 – Carlos Guestrin 200613 Choice of rootRoot: node 5Root: node 3Message does not depend on root!!!“Cache” computation: Obtain belief for all roots in linear time!!10-708 – Carlos Guestrin 200614 Shafer-Shenoy Algorithm (a.k.a. VE in clique tree for all roots)Clique Ci ready to transmit to neighbor Cj if received messages from all neighbors but jLeaves are always ready to transmitWhile 9 Ci ready to transmit to CjSend message i! jComplexity: Linear in # cliquesOne message sent each direction in each edgeCorollary: At convergenceEvery clique has correct beliefC2C4C5C1C3C7C610-708 – Carlos Guestrin 200615 Calibrated Clique treeInitially, neighboring nodes don’t agree on “distribution” over separatorsCalibrated clique tree:At convergence, tree is calibratedNeighboring nodes agree on distribution over separator10-708 – Carlos Guestrin 200616 Answering queries with clique treesQuery within cliqueIncremental updates – Observing evidence Z=zMultiply some clique by indicator 1(Z=z)Query outside cliqueUse variable elimination!10-708 – Carlos Guestrin 200617 Message passing with divisionComputing messages by multiplication:Computing messages by division:C2: DIG C4: GJSL C5: HGJC1: CD C3: GSI10-708 – Carlos Guestrin 200618 Lauritzen-Spiegelhalter Algorithm (a.k.a. belief propagation)Initialize all
View Full Document
Unlocking...