Variable EliminationGeneral probabilistic inferenceMarginalizationProbabilistic inference exampleFast probabilistic inference example – Variable eliminationUnderstanding variable elimination – Exploiting distributivityUnderstanding variable elimination – Order can make a HUGE differenceUnderstanding variable elimination – Intermediate resultsUnderstanding variable elimination – Another examplePruning irrelevant variablesVariable elimination algorithmOperations on factorsSlide 13Complexity of VE – First analysisComplexity of variable elimination – (Poly)-tree graphsWhat you need to know about inference thus farAnnouncementsComplexity 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 know1Variable EliminationGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 11th, 2006Readings:K&F: 8.1, 8.2, 8.3, 8.7.110-708 – Carlos Guestrin 20062 General probabilistic inferenceQuery:Using def. of cond. prob.:Normalization:FluAllergySinusHeadacheNose10-708 – Carlos Guestrin 20063 MarginalizationFlu Nose=tSinus10-708 – Carlos Guestrin 20064 Probabilistic inference exampleFluAllergySinusHeadacheNose=tInference seems exponential in number of variables!10-708 – Carlos Guestrin 20065 Fast probabilistic inference example – Variable eliminationFluAllergySinusHeadacheNose=t(Potential for) Exponential reduction in computation!10-708 – Carlos Guestrin 20066 Understanding variable elimination – Exploiting distributivityFlu Sinus Nose=t10-708 – Carlos Guestrin 20067 Understanding variable elimination – Order can make a HUGE differenceFluAllergySinusHeadacheNose=t10-708 – Carlos Guestrin 20068 Understanding variable elimination – Intermediate resultsFluAllergySinusHeadacheNose=tIntermediate results are probability distributions10-708 – Carlos Guestrin 20069 Understanding variable elimination – Another examplePharmacySinusHeadacheNose=t10-708 – Carlos Guestrin 200610 Pruning irrelevant variablesFluAllergySinusHeadacheNose=tPrune all non-ancestors of query variablesMore generally: Prune all nodes not on active trail between evidence and query vars10-708 – Carlos Guestrin 200611 Variable elimination algorithmGiven a BN and a query P(X|e) / P(X,e)Instantiate evidence ePrune 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,…,fk that include XiGenerate a new factor by eliminating Xi from these factorsVariable Xi has been eliminated!Normalize P(X,e) to obtain P(X|e)IMPORTANT!!!10-708 – Carlos Guestrin 200612 Operations on factorsFluAllergySinusHeadacheNose=tMultiplication:10-708 – Carlos Guestrin 200613 Operations on factorsFluAllergySinusHeadacheNose=tMarginalization:10-708 – Carlos Guestrin 200614 Complexity of VE – First analysisNumber of multiplications:Number of additions:10-708 – Carlos Guestrin 200615 Complexity 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 200616 What you need to know about inference thus farTypes of queriesprobabilistic inferencemost probable explanation (MPE)maximum a posteriori (MAP)MPE and MAP are truly different (don’t give the same answer)Hardness of inferenceExact and approximate inference are NP-hardMPE is NP-completeMAP is much harder (NPPP-complete)Variable elimination algorithmEliminate a variable:Combine factors that include this var into single factorMarginalize var from new factorEfficient 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 problemMany good heuristics10-708 – Carlos Guestrin 200617 AnnouncementsRecitation tomorrow:Khalid on Variable EliminationRecitation on advanced topic:Carlos on Context-Specific Independence On Monday Oct 16, 5:30-7:00pm in Wean Hall 4615A10-708 – Carlos Guestrin 200618 Complexity 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 200619 Eliminating a node – Fill edgesEliminate variableadd Fill Edges:Connect neighborsDifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 200620 Induced 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 200621 Different elimination order can lead to different induced graphElimination order:{G,C,D,S,I,L,H,J}DifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 200622 Induced 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
View Full Document
Unlocking...