Complexity of Var. Elim MPE Inference Junction TreesWhat’s nextComplexity of variable elimination – Graphs with loopsEliminating a node – Fill edgesInduced graphDifferent elimination order can lead to different induced 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 orderMost 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 summary1Complexity of Var. ElimMPE InferenceJunction TreesGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 20th, 2008Readings:K&F: 8.4, 12.1, 12.2, 9 10-708 – Carlos Guestrin 2006-2008What’s nextThus far: Variable elimination(Often) Efficient algorithm for inference in graphical modelsNext: Understanding complexity of variable eliminationWill lead to cool junction tree algorithm later10-708 – Carlos Guestrin 2006-2008210-708 – Carlos Guestrin 2006-20083Complexity 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 2006-20084Eliminating a node – Fill edgesEliminate variableadd Fill Edges:Connect neighborsDifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 2006-20085Induced 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 2006-20086Different elimination order can lead to different induced graphElimination order:{G,C,D,S,I,L,H,J}DifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 2006-20087Induced 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 2006-20088Example: Large induced-width with small number of parentsCompact representation Easy inference 10-708 – Carlos Guestrin 2006-20089Finding 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 2006-200810Induced 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 2006-200811Chordal 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 2006-200812Minimum 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 2006-200813Choosing 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 2006-200814Most likely explanation (MLE)Query:Using defn of conditional probs:Normalization irrelevant:FluAllergySinusHeadacheNose10-708 – Carlos Guestrin 2006-200815Max-marginalizationFlu Sinus Nose=t10-708 – Carlos Guestrin 2006-200816Example of variable elimination for MLE – Forward passFluAllergySinusHeadacheNose=t10-708 – Carlos Guestrin 2006-200817Example of variable elimination for MLE – Backward passFluAllergySinusHeadacheNose=t10-708 – Carlos Guestrin 2006-200818MLE Variable elimination
View Full Document