Variable EliminationInference in BNs hopeless?General probabilistic inferenceProbabilistic 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 farAnnouncementsWhat’s nextComplexity 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 order1Variable EliminationGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 15th, 2008Readings:K&F: 8.1, 8.2, 8.3, 8.4 10-708 – Carlos Guestrin 2006-200810-708 – Carlos Guestrin 2006-20082Inference in BNs hopeless?In general, yes! Even approximate!In practiceExploit structureMany effective approximation algorithms (some with guarantees)For now, we’ll talk about exact inferenceApproximate inference later this semester10-708 – Carlos Guestrin 2006-20083General probabilistic inferenceQuery:Using def. of cond. prob.:Normalization:FluAllergySinusHeadacheNose10-708 – Carlos Guestrin 2006-20084Probabilistic inference exampleFluAllergySinusHeadacheNose=tInference seems exponential in number of variables!10-708 – Carlos Guestrin 2006-20085FluAllergySinusHeadacheNose=tFast probabilistic inference example – Variable elimination(Potential for) Exponential reduction in computation!10-708 – Carlos Guestrin 2006-20086Understanding variable elimination – Exploiting distributivityFlu Sinus Nose=t10-708 – Carlos Guestrin 2006-20087Understanding variable elimination – Order can make a HUGE differenceFluAllergySinusHeadacheNose=t10-708 – Carlos Guestrin 2006-20088Understanding variable elimination – Intermediate resultsFluAllergySinusHeadacheNose=tIntermediate results are probability distributions10-708 – Carlos Guestrin 2006-20089Understanding variable elimination – Another examplePharmacySinusHeadacheNose=t10-708 – Carlos Guestrin 2006-200810Pruning 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 2006-200811Variable 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 2006-200812Operations on factorsFluAllergySinusHeadacheNose=tMultiplication:10-708 – Carlos Guestrin 2006-200813Operations on factorsFluAllergySinusHeadacheNose=tMarginalization:10-708 – Carlos Guestrin 2006-200814Complexity of VE – First analysisNumber of multiplications:Number of additions:10-708 – Carlos Guestrin 2006-200815Complexity 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 2006-200816What 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 2006-200817AnnouncementsRecitation tomorrowBe there!!Homework 3 out later todayWhat’s nextThus far: Variable elimination(Often) Efficient algorithm for inference in graphical modelsNext: Understanding complexity of variable eliminationWill lead to cool junction tree algorithm later10-708 – Carlos Guestrin 2006-20081810-708 – Carlos Guestrin 2006-200819Complexity 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-200820Eliminating a node – Fill edgesEliminate variableadd Fill Edges:Connect neighborsDifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 2006-200821Induced 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 2006-200822Different elimination order can lead to different induced graphElimination order:{G,C,D,S,I,L,H,J}DifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 2006-200823Induced graph and complexity of VEDifficultySATGradeHappyJobCoherenceLetterIntelligenceStructure of induced graph encodes complexity of VE!!!Theorem:Every
View Full Document