11Variable 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 20062Complexity of variable elimination –Graphs with loopsConnect nodes that appear together in an initial factorDifficultySATGradeHappyJobCoherenceLetterIntelligenceMoralize graph:Connect parents into a clique and remove edge directions210-708 –©Carlos Guestrin 20063Induced 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 F 10-708 –©Carlos Guestrin 20064Induced 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}310-708 –©Carlos Guestrin 20065Example: Large induced-width with small number of parentsCompact representation ⇒ Easy inference /10-708 –©Carlos Guestrin 20066Finding 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}410-708 –©Carlos Guestrin 20067Induced 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 20068Chordal graphs and triangulation Triangulation: turning graph into chordalgraph Max Cardinality Search: Simple heuristic Initialize unobserved nodes X as unmarked For k = |X| to 1 X ← unmarked var with most markedneighbors ≺(X) ← k Mark X Theorem: Obtains optimal order for chordal graphs Often, not so good in other graphs!BEDHGAFC510-708 –©Carlos Guestrin 20069Minimum fill/size/weight heuristics Many more effective heuristics see reading 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 edgesBEDHGAFC10-708 –©Carlos Guestrin 200610Choosing 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 elimination610-708 –©Carlos Guestrin 200611Announcements 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 200612Most likely explanation (MLE) Query: Using defn of conditional probs: Normalization irrelevant:FluAllergySinusHeadacheNose710-708 –©Carlos Guestrin 200613Max-marginalizationFlu Sinus Nose=t10-708 –©Carlos Guestrin 200614Example of variable elimination for MLE – Forward passFluAllergySinusHeadacheNose=t810-708 –©Carlos Guestrin 200615Example of variable elimination for MLE – Backward passFluAllergySinusHeadacheNose=t10-708 –©Carlos Guestrin 200616MLE 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!910-708 –©Carlos Guestrin 200617MLE 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:10-708 –©Carlos Guestrin 200618What you need to know about VE 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” (special recitation) Elimination order is important! NP-complete problem Many good heuristics Variable elimination for MLE Only difference between probabilistic inference and MLE is “sum” versus “max”1010-708 –©Carlos Guestrin 200619What 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 200620Reusing computationCompute:X0X5X3X4X2X11110-708 –©Carlos Guestrin 200621Cluster graph Cluster graph: For set of factors F Undirected graph Each node i associated with a cluster Ci Family preserving: for each factor fj∈ F, ∃ node i such that scope[fi]⊆ Ci Each edge i – j is associated with a separator Sij=
View Full Document
Unlocking...