Variable Elimination Dhruv Batra, 10-708 Recitation 10/16/2008Overview • Variable Elimination – Example on chain networks – Intuition – Tools for VE, factor product, marginalization – Implementation hintsChain Networks • BN: • Goal: Need all marginals P(X)Chain Networks • Naïve solutionChain Networks • A little smarter solution: Phased Computation • General Chains: • Why is this better? vs • What’s the intuition?Chain Networks • A lot of structureChain Networks • Let’s cacheChain Networks • Let’s cache againChain Networks • Intuitions from this process – Group common things/terms/factors based on scope – Dynamic programming ideas: cache computations • VE extends/formalizes these intuitions to general graphs – but separates the elimination ordering from the processAnother Idea • A commonly used idea • Goal • Can forget about denominator; just renormalize when doneExample • Let’s do an example for general graphs W O C MFGBSH0.70.3FalseTrueFalse False 0.5 0.50.8True 0.2FalseFalseTrue 0.40.6TrueO0.9True0.1TrueFalseW0.40.6FalseTrue0.60.4FalseTrue0.90.1FalseTrueFalse False 0.1 0.90.7True 0.3FalseFalseTrue 0.40.6TrueB0.95True0.05TrueFalseFFalse False 0.2 0.80.75True 0.25FalseFalseTrue 0.30.7TrueG0.9True0.1TrueFalseFFalse False 0.7 0.30.01True 0.99FalseFalseTrue 0.10.9TrueM0.1True0.9TrueFalseCFalse False 0.01 0.990.4True 0.6FalseFalseTrue 0.50.5TrueG0.99True0.01TrueFalseSW O C MFGBSH0.70.3FalseTrueFalse False 0.5 0.50.8True 0.2FalseFalseTrue 0.40.6TrueO0.9True0.1TrueFalseW0.40.6FalseTrue0.60.4FalseTrue0.90.1FalseTrueFalse False 0.1 0.90.7True 0.3FalseFalseTrue 0.40.6TrueB0.95True0.05TrueFalseFFalse False 0.2 0.80.75True 0.25FalseFalseTrue 0.30.7TrueG0.9True0.1TrueFalseFFalse False 0.7 0.30.01True 0.99FalseFalseTrue 0.10.9TrueM0.1True0.9TrueFalseCFalse False 0.01 0.990.4True 0.6FalseFalseTrue 0.50.5TrueG0.99True0.01TrueFalseSImplementing VE • What do you need to implement VE? – Reuse some code from HW2Tools for VE • Factors • Special kind of factors: CPTs CW X Y ZOperations on Factors • Factor Product – Consider two factors – Define factor product – such thatOperations on Factors • Factor ProductOperations on Factors • Factor Marginalization – Consider a factor – Define factor marginal – such thatOperations on Factors • Factor MarginalizationFactors • Are factors always distributions? – Obviously not • Are factors produced in VE always distributions? – Yes, always conditional distributions – In SOME graph, not necessarily the original graph – HW3, prob 2. Hint: read 8.3.1.3Implementing VE • What do you need to implement VE? – Reuse some code from HW2 • Representation – BN as an array of factors – table_factor.m – assignment.m • VE – multipy_factors.m – marginalize_factor.m – min_fill.m21 Variable 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,…,fk that include Xi Generate a new factor by eliminating Xi from these factors Variable Xi has been eliminated! Normalize P(X,e) to obtain
View Full Document