Junction Trees 2What if I want to compute P(Xi|x0,xn+1) for each i?Reusing computationCluster graphCluster 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 treesIntroducing message passing with divisionFactor divisionLauritzen-Spiegelhalter Algorithm (a.k.a. belief propagation)Convergence of Lauritzen-Spiegelhalter AlgorithmVE versus BP in clique treesClique tree invariantBelief propagation and clique tree invariantSubtree correctnessClique trees versus VEClique tree summary1Junction Trees 2Graphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 22nd, 2008Readings:K&F: 9.1, 9.2, 9.3, 9.4 10-708 – Carlos Guestrin 2006-200810-708 – Carlos Guestrin 2006-20082What 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 2006-20083Reusing computationCompute:X0X5X3X4X2X110-708 – Carlos Guestrin 2006-20084Cluster 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 2006-20085Cluster 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 2006-20086Running intersection propertyRunning intersection property (RIP)Cluster tree satisfies RIP if whenever X2Ci and X2Cj then X is in every cluster in the (unique) path from Ci to CjTheorem:Cluster tree generated by VE satisfies RIPDIGJSLGJSLHGJCDGSI10-708 – Carlos Guestrin 2006-20087Constructing 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 2006-20088Find 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 – |CiCj|DifficultyGradeHappyJobCoherenceLetterIntelligenceSAT10-708 – Carlos Guestrin 2006-20089Clique 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 2006-200810Variable 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 2006-200811Variable 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 2006-200812Belief from messageTheorem: When clique Ci is readyReceived messages from all neighborsBelief i(Ci) is product of initial factor with messages:10-708 – Carlos Guestrin 2006-200813Choice 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 2006-200814Shafer-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 2006-200815Calibrated 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 2006-200816Answering 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 200617Introducing message passing with divisionVariable elimination (message passing with multiplication)message:belief:Message passing with division:message:belief update:C2: SEC4: GJSC1: CDC3: GDS10-708 – Carlos Guestrin 200618Factor divisionLet X and Y be disjoint set of variablesConsider two factors: 1(X,Y) and 2(Y)Factor =1/20/0=010-708 – Carlos Guestrin 200619Separator potentials ijone per edge (same both directions)holds “last message”initialized to 1Message i!jwhat does i think the separator potential should be? i!jupdate belief for j:pushing j to what i thinks about separatorreplace separator potential:C2: SEC4: GJSC1: CDC3: GDSLauritzen-Spiegelhalter Algorithm (a.k.a. belief propagation)Simplified descriptionsee reading for details10-708 – Carlos Guestrin 2006-200820Convergence of Lauritzen-Spiegelhalter Algorithm Complexity: Linear in # cliquesfor the “right” schedule over edges (leaves to root, then root to leaves)Corollary: At convergence, every clique has correct beliefC2C4C5C1C3C7C610-708 –
View Full Document
Unlocking...