DOC PREVIEW
CMU CS 10708 - Variable Elimination

This preview shows page 1-2-3-4-5 out of 15 pages.

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

Unformatted text preview:

1 1 Variable Elimination Graphical Models – 10708 Carlos Guestrin Carnegie Mellon University October 15th, 2008 Readings: K&F: 8.1, 8.2, 8.3, 8.4 10-708 – ©Carlos Guestrin 2006-2008 10-708 – ©Carlos Guestrin 2006-2008 2 Inference in BNs hopeless?  In general, yes!  Even approximate!  In practice  Exploit structure  Many effective approximation algorithms (some with guarantees)  For now, we’ll talk about exact inference  Approximate inference later this semester2 10-708 – ©Carlos Guestrin 2006-2008 3 General probabilistic inference  Query:  Using def. of cond. prob.:  Normalization: Flu Allergy Sinus Headache Nose 10-708 – ©Carlos Guestrin 2006-2008 4 Probabilistic inference example Flu Allergy Sinus Headache Nose=t Inference seems exponential in number of variables!3 10-708 – ©Carlos Guestrin 2006-2008 5 Flu Allergy Sinus Headache Nose=t Fast probabilistic inference example – Variable elimination (Potential for) Exponential reduction in computation! 10-708 – ©Carlos Guestrin 2006-2008 6 Understanding variable elimination – Exploiting distributivity Flu Sinus Nose=t4 10-708 – ©Carlos Guestrin 2006-2008 7 Understanding variable elimination – Order can make a HUGE difference Flu Allergy Sinus Headache Nose=t 10-708 – ©Carlos Guestrin 2006-2008 8 Understanding variable elimination – Intermediate results Flu Allergy Sinus Headache Nose=t Intermediate results are probability distributions5 10-708 – ©Carlos Guestrin 2006-2008 9 Understanding variable elimination – Another example Pharmacy Sinus Headache Nose=t 10-708 – ©Carlos Guestrin 2006-2008 10 Pruning irrelevant variables Flu Allergy Sinus Headache Nose=t Prune all non-ancestors of query variables More generally: Prune all nodes not on active trail between evidence and query vars6 10-708 – ©Carlos Guestrin 2006-2008 11 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 P(X|e) IMPORTANT!!! 10-708 – ©Carlos Guestrin 2006-2008 12 Operations on factors Flu Allergy Sinus Headache Nose=t Multiplication:7 10-708 – ©Carlos Guestrin 2006-2008 13 Operations on factors Flu Allergy Sinus Headache Nose=t Marginalization: 10-708 – ©Carlos Guestrin 2006-2008 14 Complexity of VE – First analysis  Number of multiplications:  Number of additions:8 10-708 – ©Carlos Guestrin 2006-2008 15 Complexity of variable elimination – (Poly)-tree graphs Variable elimination order: Start from “leaves” inwards: • Start from skeleton! • Choose a “root”, any node • Find topological order for root • Eliminate variables in reverse order Linear in CPT sizes!!! (versus exponential) 10-708 – ©Carlos Guestrin 2006-2008 16 What you need to know about inference thus far  Types of queries  probabilistic inference  most probable explanation (MPE)  maximum a posteriori (MAP)  MPE and MAP are truly different (don’t give the same answer)  Hardness of inference  Exact and approximate inference are NP-hard  MPE is NP-complete  MAP is much harder (NPPP-complete)  Variable elimination algorithm  Eliminate a variable:  Combine factors that include this var into single factor  Marginalize var from new factor  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” (next week with context-specific independence)  Elimination order is important!  NP-complete problem  Many good heuristics9 10-708 – ©Carlos Guestrin 2006-2008 17 Announcements  Recitation tomorrow  Be there!!  Homework 3 out later today What’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 later 10-708 – ©Carlos Guestrin 2006-2008 1810 10-708 – ©Carlos Guestrin 2006-2008 19 Complexity of variable elimination – Graphs with loops Connect nodes that appear together in an initial factor Difficulty SAT Grade Happy Job Coherence Letter Intelligence Moralize graph: Connect parents into a clique and remove edge directions 10-708 – ©Carlos Guestrin 2006-2008 20 Eliminating a node – Fill edges Eliminate variable add Fill Edges: Connect neighbors Difficulty SAT Grade Happy Job Coherence Letter Intelligence11 10-708 – ©Carlos Guestrin 2006-2008 21 Induced graph Elimination order: {C,D,S,I,L,H,J,G} Difficulty SAT Grade Happy Job Coherence Letter Intelligence The induced graph IF for elimination order  has an edge Xi – Xj if Xi and Xj appear together in a factor generated by VE for elimination order  on factors F 10-708 – ©Carlos Guestrin 2006-2008 22 Different elimination order can lead to different induced graph Elimination order: {G,C,D,S,I,L,H,J} Difficulty SAT Grade Happy Job Coherence Letter Intelligence12 10-708 – ©Carlos Guestrin 2006-2008 23 Induced graph and complexity of VE Difficulty SAT Grade Happy Job Coherence Letter Intelligence  Structure 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 1  Minimal induced width – induced width of best order Á Read complexity from cliques in induced graph Elimination order: {C,D,I,S,L,H,J,G} 10-708 – ©Carlos Guestrin 2006-2008 24 Example: Large induced-width with small number of parents Compact representation ⇒ Easy inference 13 10-708 – ©Carlos Guestrin 2006-2008 25 Finding optimal elimination order Difficulty SAT Grade Happy


View Full Document

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
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?