1Complexity 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 next Thus far: Variable elimination (Often) Efficient algorithm for inference in graphical models Next: Understanding complexity of variable elimination Will 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 IFYfor elimination order Yhas an edge Xi–Xjif Xiand Xjappear togetherin a factor generated by VE for elimination order Yon factors F 10-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 VEDifficultySATGradeHappyJobCoherenceLetterIntelligence Structure of induced graph encodes complexity of VE!!! Theorem: Every factor generated by VE subset of a maximal clique in IFY For every maximal clique in IFYcorresponds to a factor generated by VE Induced width (or treewidth) Size of largest clique in IFYminus 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}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 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}10-708 –Carlos Guestrin 2006-200810Induced 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 2006-200811Chordal 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 Y(X) Í k Mark X Theorem: Obtains optimal order for chordal graphs Often, not so good in other graphs!BEDHGAFC10-708 –Carlos Guestrin 2006-200812Minimum 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 Y(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 2006-200813Choosing 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 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 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!10-708 –Carlos Guestrin 2006-200819MLE 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 2006-200820What 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”10-708
View Full Document