11Variable EliminationGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 11th, 2006Readings:K&F: 8.1, 8.2, 8.3, 8.7.110-708 –©Carlos Guestrin 20062General probabilistic inference Query: Using def. of cond. prob.: Normalization:FluAllergySinusHeadacheNose210-708 –©Carlos Guestrin 20063MarginalizationFlu Nose=tSinus10-708 –©Carlos Guestrin 20064Probabilistic inference exampleFluAllergySinusHeadacheNose=tInference seems exponential in number of variables!310-708 –©Carlos Guestrin 20065Fast probabilistic inference example – Variable eliminationFluAllergySinusHeadacheNose=t(Potential for) Exponential reduction in computation!10-708 –©Carlos Guestrin 20066Understanding variable elimination –Exploiting distributivityFlu Sinus Nose=t410-708 –©Carlos Guestrin 20067Understanding variable elimination –Order can make a HUGE differenceFluAllergySinusHeadacheNose=t10-708 –©Carlos Guestrin 20068Understanding variable elimination –Intermediate resultsFluAllergySinusHeadacheNose=tIntermediate results are probability distributions510-708 –©Carlos Guestrin 20069Understanding variable elimination –Another examplePharmacySinusHeadacheNose=t10-708 –©Carlos Guestrin 200610Pruning irrelevant variablesFluAllergySinusHeadacheNose=tPrune all non-ancestors of query variablesMore generally: Prune all nodes not on active trail between evidence and query vars610-708 –©Carlos Guestrin 200611Variable elimination algorithm Given a BN and a query P(X|e) ∝ P(X,e) Instantiate evidence e Prune non-active vars for {X,e} Choose an ordering on variables, e.g., X1, …, Xn Initial factors {f1,…,fn}: fi= P(Xi|PaXi) (CPT for Xi) For i = 1 to n, If Xi∉{X,E} Collect factors f1,…,fkthat include Xi Generate a new factor by eliminating Xifrom these factors Variable Xihas been eliminated! Normalize P(X,e) to obtain P(X|e)IMPORTANT!!!10-708 –©Carlos Guestrin 200612Operations on factorsFluAllergySinusHeadacheNose=tMultiplication:710-708 –©Carlos Guestrin 200613Operations on factorsFluAllergySinusHeadacheNose=tMarginalization:10-708 –©Carlos Guestrin 200614Complexity of VE – First analysis Number of multiplications: Number of additions:810-708 –©Carlos Guestrin 200615Complexity of variable elimination –(Poly)-tree graphsVariable elimination order:Start from “leaves” inwards: • Start from skeleton!• Choose a “root”, any node• Find topological order for root• Eliminate variables in reverse orderLinear in CPT sizes!!! (versus exponential)10-708 –©Carlos Guestrin 200616What you need to know about inference thus far Types of queries probabilistic inference most probable explanation (MPE) maximum a posteriori (MAP) MPE and MAP are truly different (don’t give the same answer) Hardness of inference Exact and approximate inference are NP-hard MPE is NP-complete MAP is much harder (NPPP-complete) Variable elimination algorithm Eliminate a variable: Combine factors that include this var into single factor Marginalize var from new factor 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 with context-specific independence)Elimination order is important! NP-complete problem Many good heuristics910-708 –©Carlos Guestrin 200617Announcements Recitation tomorrow: Khalid on Variable Elimination Recitation on advanced topic: Carlos on Context-Specific Independence On Monday Oct 16, 5:30-7:00pm in Wean Hall 4615A 10-708 –©Carlos Guestrin 200618Complexity of variable elimination –Graphs with loopsConnect nodes that appear together in an initial factorDifficultySATGradeHappyJobCoherenceLetterIntelligenceMoralize graph:Connect parents into a clique and remove edge directions1010-708 –©Carlos Guestrin 200619Eliminating a node – Fill edgesEliminate variableadd Fill Edges:Connect neighborsDifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 –©Carlos Guestrin 200620Induced graphElimination order:{C,D,S,I,L,H,J,G}DifficultySATGradeHappyJobCoherenceLetterIntelligenceThe induced graph IF≺for elimination order ≺has an edge Xi–Xjif Xiand Xjappear togetherin a factor generated by VE for elimination order ≺on factors F1110-708 –©Carlos Guestrin 200621Different elimination order can lead to different induced graphElimination order:{G,C,D,S,I,L,H,J}DifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 –©Carlos Guestrin 200622Induced 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}1210-708 –©Carlos Guestrin 200623Example: Large induced-width with small number of parentsCompact representation ⇒ Easy inference /10-708 –©Carlos Guestrin 200624Finding 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 finding elimination order in addition to hardness of inference Actually, 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}1310-708 –©Carlos Guestrin 200625Induced 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 chordal graph10-708 –©Carlos Guestrin 200626Chordal graphs and triangulation Triangulation: turning graph into chordalgraph Max Cardinality Search: Simple heuristic Initialize unobserved nodes X as
View Full Document