Variable elimination 2Clique treesAnnouncementsComplexity of variable elimination – Graphs with loopsEliminating a node – Fill edgesInduced 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 knowWhat if I want to compute P(Xi|x0,xn+1) for each i?Reusing computationCluster graphFactors generated by VECluster graph for VERunning intersection propertyClique 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 treeNew reading:Chapter 7 of Koller&FriedmanVariable elimination 2Clique treesGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversitySeptember 28th, 2005Announcements Recitation room change!!! Wean Hall 4615A (Thursdays 5-6pm) Waiting List Anyone still wants to be registered?Complexity of variable elimination –Graphs with loopsDifficultySATGradeHappyJobCoherenceLetterIntelligenceMoralize graph:Connect parents into a clique and remove edge directionsConnect nodes that appear together in an initial factorEliminating a node – Fill edgesEliminate variableadd Fill Edges:Connect neighborsDifficultySATGradeHappyJobCoherenceLetterIntelligenceThe induced graph IF≺for elimination order ≺has an edge Xi–Xjif Xiand Xjappear togetherin a factor generated by VE for elimination order ≺on factors F Induced graphElimination order:{C,D,S,I,L,H,J,G}DifficultySATGradeHappyJobCoherenceLetterIntelligence DifficultySATGradeHappyJobCoherenceLetterIntelligenceInduced graph and complexity of VEDifficultySATGradeHappyJobCoherenceLetterIntelligence Structure 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 1 Minimal induced width –induced width of best order ≺Read complexity from cliques in induced graphElimination order:{C,D,I,S,L,H,J,G}Example: Large induced-width with small number of parentsCompact representation ⇒ Easy inference /Finding optimal elimination orderDifficultySATGradeHappyJobCoherenceLetterIntelligence Theorem: Finding best elimination order is NP-complete: Decision problem: Given a graph, determine if there exists an elimination order that achieves induced width · K Interpretation: Hardness of elimination order “orthogonal” to hardness of inference Actually, can find elimination order in time exponential in size of largest clique – same complexity as inference (next week) Elimination order:{C,D,I,S,L,H,J,G}Induced graphs and chordal graphsDifficultySATGradeHappyJobCoherenceLetterIntelligence Chordal graph: Every cycle X1–X2–…–Xk–X1with k ≥ 3 has a chord Edge Xi–Xjfor non-consecutive i & j Theorem: Every induced graph is chordal “Optimal” elimination order easily obtained for chordalgraphChordal graphs and triangulation Triangulation: turning graph into chordal graph Max Cardinality Search: Simple heuristic Initialize unobserved nodes X as unmarked For k = |X| to 1 X ← unmarked var with most marked neighbors ≺(X) ← k Mark X Theorem: Obtains optimal order for chordal graphs Often, not so good in other graphs!BEDHGAFCMinimum fill/size/weight heuristics Many more effective heuristics page 262 of K&F Min (weighted) fill heuristic Often very effective Initialize unobserved nodes X as unmarked For k = 1 to |X| X ← unmarked var whose elimination adds fewest edges ≺(X) ← k Mark X Add fill edges introduced by eliminating X Weighted version: Consider size of factor rather than number of edgesBEDHGAFCChoosing an elimination order Choosing best order is NP-complete Reduction from MAX-Clique Many good heuristics (some with guarantees) Ultimately, can’t beat NP-hardness of inference Even optimal order can lead to exponential variable elimination computation In practice Variable elimination often very effective Many (many many) approximate inference approaches available when variable elimination too expensive Most approximate inference approaches build on ideas from variable eliminationMost likely explanation (MLE) Query: Using Bayes rule: Normalization irrelevant:FluAllergySinusHeadacheNoseMax-marginalizationFluAllergy=tSinusExample of variable elimination for MLE – Forward passFluAllergySinusHeadacheNose=tExample of variable elimination for MLE – Backward passFluAllergySinusHeadacheNose=tMLE Variable elimination algorithm – Forward pass Given a BN and a MLE query maxx1,…,xnP(x1,…,xn,e) Instantiate evidence E=e Choose an ordering on variables, e.g., X1, …, Xn For i = 1 to n, If Xi∉E Collect factors f1,…,fkthat include Xi Generate a new factor by eliminating Xifrom these factors Variable Xihas been eliminated!MLE Variable elimination algorithm – Backward pass {x1*,…, xn*} will store maximizing assignment For i = n to 1, If Xi∉ E Take factors f1,…,fkused when Xiwas eliminated Instantiate f1,…,fk, with {xi+1*,…, xn*} Now each fjdepends only on Xi Generate maximizing assignment for Xi:What you need to know Variable elimination algorithm Eliminate a variable: Combine factors that include this var into single factor Marginalize var from new factor Cliques in induced graph correspond to factors generated by algorithm Efficient algorithm (“only” exponential in induced-width, not number of variables) If you hear: “Exact inference only efficient in tree graphical models” You say: “No!!! Any graph with low induced width” And then you say: “And even some with very large induced-width” (next week)Elimination order is important! NP-complete problem Many good heuristics Variable elimination for MLE Only difference
View Full Document