Variable Elimination 2 Clique TreesComplexity of variable elimination – Graphs with loopsInduced graphInduced graph and complexity of VEExample: Large induced-width with small number of parentsFinding optimal elimination orderInduced graphs and chordal graphsChordal graphs and triangulationMinimum fill/size/weight heuristicsChoosing an elimination orderAnnouncementsMost likely explanation (MLE)Max-marginalizationExample of variable elimination for MLE – Forward passExample of variable elimination for MLE – Backward passMLE Variable elimination algorithm – Forward passMLE Variable elimination algorithm – Backward passWhat you need to know about VEWhat if I want to compute P(Xi|x0,xn+1) for each i?Reusing computationCluster 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 summary1Variable Elimination 2Clique TreesGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 13th, 2006Readings:K&F: 8.1, 8.2, 8.3, 8.7.1K&F: 9.1, 9.2, 9.3, 9.410-708 – Carlos Guestrin 20062 Complexity of variable elimination – Graphs with loopsConnect nodes that appear together in an initial factorDifficultySATGradeHappyJobCoherenceLetterIntelligenceMoralize graph:Connect parents into a clique and remove edge directions10-708 – Carlos Guestrin 20063 Induced graphElimination order:{C,D,S,I,L,H,J,G}DifficultySATGradeHappyJobCoherenceLetterIntelligenceThe induced graph IFÁ for elimination order Á has an edge Xi – Xj if Xi and Xj appear togetherin a factor generated by VE for elimination order Á on factors F10-708 – Carlos Guestrin 20064 Induced graph and complexity of VEDifficultySATGradeHappyJobCoherenceLetterIntelligenceStructure of induced graph encodes complexity of VE!!!Theorem:Every factor generated by VE subset of a maximal clique in IFÁFor every maximal clique in IFÁ corresponds to a factor generated by VE Induced width (or treewidth)Size of largest clique in IFÁ minus 1Minimal induced width – induced width of best order ÁRead complexity from cliques in induced graphElimination order:{C,D,I,S,L,H,J,G}10-708 – Carlos Guestrin 20065 Example: Large induced-width with small number of parentsCompact representation Easy inference 10-708 – Carlos Guestrin 20066 Finding optimal elimination orderDifficultySATGradeHappyJobCoherenceLetterIntelligenceTheorem: Finding best elimination order is NP-complete:Decision problem: Given a graph, determine if there exists an elimination order that achieves induced width · KInterpretation:Hardness of finding elimination order in addition to hardness of inferenceActually, can find elimination order in time exponential in size of largest clique – same complexity as inferenceElimination order:{C,D,I,S,L,H,J,G}10-708 – Carlos Guestrin 20067 Induced graphs and chordal graphsDifficultySATGradeHappyJobCoherenceLetterIntelligenceChordal graph:Every cycle X1 – X2 – … – Xk – X1 with k ¸ 3 has a chordEdge Xi – Xj for non-consecutive i & jTheorem:Every induced graph is chordal“Optimal” elimination order easily obtained for chordal graph10-708 – Carlos Guestrin 20068 Chordal graphs and triangulationTriangulation: turning graph into chordal graphMax Cardinality Search:Simple heuristicInitialize unobserved nodes X as unmarkedFor k = |X| to 1X Ã unmarked var with most marked neighborsÁ(X) Ã kMark XTheorem: Obtains optimal order for chordal graphsOften, not so good in other graphs!BEDHGAFC10-708 – Carlos Guestrin 20069 Minimum fill/size/weight heuristicsMany more effective heuristicssee readingMin (weighted) fill heuristicOften very effectiveInitialize unobserved nodes X as unmarkedFor k = 1 to |X|X Ã unmarked var whose elimination adds fewest edgesÁ(X) Ã kMark XAdd fill edges introduced by eliminating XWeighted version:Consider size of factor rather than number of edgesBEDHGAFC10-708 – Carlos Guestrin 200610 Choosing an elimination orderChoosing best order is NP-completeReduction from MAX-CliqueMany good heuristics (some with guarantees)Ultimately, can’t beat NP-hardness of inferenceEven optimal order can lead to exponential variable elimination computationIn practiceVariable elimination often very effectiveMany (many many) approximate inference approaches available when variable elimination too expensiveMost approximate inference approaches build on ideas from variable elimination10-708 – Carlos Guestrin 200611 AnnouncementsRecitation on advanced topic:Carlos on Context-Specific Independence On Monday Oct 16, 5:30-7:00pm in Wean Hall 4615A10-708 – Carlos Guestrin 200612 Most likely explanation (MLE)Query:Using defn of conditional probs:Normalization irrelevant:FluAllergySinusHeadacheNose10-708 – Carlos Guestrin 200613 Max-marginalizationFlu Sinus Nose=t10-708 – Carlos Guestrin 200614 Example of variable elimination for MLE – Forward passFluAllergySinusHeadacheNose=t10-708 – Carlos Guestrin 200615 Example of variable elimination for MLE – Backward passFluAllergySinusHeadacheNose=t10-708 – Carlos Guestrin 200616 MLE Variable elimination algorithm – Forward passGiven a BN and a MLE query maxx1,…,xnP(x1,…,xn,e)Instantiate evidence E=eChoose an ordering on variables, e.g., X1, …, Xn For i = 1 to n, If XiECollect factors f1,…,fk that include XiGenerate a new factor by eliminating Xi from these factorsVariable Xi has been eliminated!10-708 – Carlos Guestrin 200617 MLE Variable elimination algorithm – Backward pass{x1*,…, xn*} will store maximizing assignmentFor i = n to 1, If Xi ETake factors f1,…,fk used when Xi was eliminatedInstantiate f1,…,fk, with {xi+1*,…, xn*}Now each fj depends only on XiGenerate maximizing assignment
View Full Document