New version page

CMU CS 10708 - Variable Elimination

Documents in this Course
Lecture

Lecture

15 pages

Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

causality

causality

53 pages

lecture11

lecture11

16 pages

Exam

Exam

15 pages

Notes

Notes

12 pages

lecture

lecture

18 pages

lecture

lecture

16 pages

Lecture

Lecture

17 pages

Lecture

Lecture

15 pages

Lecture

Lecture

17 pages

Lecture

Lecture

19 pages

Lecture

Lecture

42 pages

Lecture

Lecture

16 pages

r6

r6

22 pages

lecture

lecture

20 pages

lecture

lecture

35 pages

Lecture

Lecture

19 pages

Lecture

Lecture

21 pages

lecture

lecture

21 pages

lecture

lecture

13 pages

review

review

50 pages

Semantics

Semantics

30 pages

lecture21

lecture21

26 pages

MN-crf

MN-crf

20 pages

hw4

hw4

5 pages

lecture

lecture

12 pages

Lecture

Lecture

25 pages

Lecture

Lecture

25 pages

Lecture

Lecture

14 pages

Lecture

Lecture

15 pages

Load more
Upgrade to remove ads

This preview shows page 1-2-21-22 out of 22 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

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
Download Variable Elimination
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Variable Elimination and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Variable Elimination 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?