DOC PREVIEW
CMU CS 10708 - Variable elimination 2 Clique trees

This preview shows page 1-2-15-16-31-32 out of 32 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 32 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 32 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 32 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 32 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 32 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 32 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 32 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Variable elimination 2Clique treesAnnouncementsComplexity of variable elimination – Graphs with loopsEliminating a node – Fill edgesInduced 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 knowWhat if I want to compute P(Xi|x0,xn+1) for each i?Reusing computationCluster graphFactors generated by VECluster graph for VERunning intersection propertyClique tree & IndependenciesVariable elimination in a clique tree 1Variable elimination in a clique tree 2Belief from messageChoice of rootShafer-Shenoy Algorithm (a.k.a. VE in clique tree for all roots)Calibrated Clique treeNew reading:Chapter 7 of Koller&FriedmanVariable elimination 2Clique treesGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversitySeptember 28th, 2005Announcements Recitation room change!!! Wean Hall 4615A (Thursdays 5-6pm) Waiting List Anyone still wants to be registered?Complexity of variable elimination –Graphs with loopsDifficultySATGradeHappyJobCoherenceLetterIntelligenceMoralize graph:Connect parents into a clique and remove edge directionsConnect nodes that appear together in an initial factorEliminating a node – Fill edgesEliminate variableadd Fill Edges:Connect neighborsDifficultySATGradeHappyJobCoherenceLetterIntelligenceThe induced graph IF≺for elimination order ≺has an edge Xi–Xjif Xiand Xjappear togetherin a factor generated by VE for elimination order ≺on factors F Induced graphElimination order:{C,D,S,I,L,H,J,G}DifficultySATGradeHappyJobCoherenceLetterIntelligence DifficultySATGradeHappyJobCoherenceLetterIntelligenceInduced graph and complexity of VEDifficultySATGradeHappyJobCoherenceLetterIntelligence 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 graphElimination order:{C,D,I,S,L,H,J,G}Example: Large induced-width with small number of parentsCompact representation ⇒ Easy inference /Finding optimal elimination orderDifficultySATGradeHappyJobCoherenceLetterIntelligence Theorem: Finding best elimination order is NP-complete: Decision problem: Given a graph, determine if there exists an elimination order that achieves induced width · K Interpretation: Hardness of elimination order “orthogonal” to hardness of inference Actually, can find elimination order in time exponential in size of largest clique – same complexity as inference (next week) Elimination order:{C,D,I,S,L,H,J,G}Induced graphs and chordal graphsDifficultySATGradeHappyJobCoherenceLetterIntelligence Chordal graph: Every cycle X1–X2–…–Xk–X1with k ≥ 3 has a chord Edge Xi–Xjfor non-consecutive i & j Theorem: Every induced graph is chordal “Optimal” elimination order easily obtained for chordalgraphChordal graphs and triangulation Triangulation: turning graph into chordal graph Max Cardinality Search: Simple heuristic Initialize unobserved nodes X as unmarked For k = |X| to 1 X ← unmarked var with most marked neighbors ≺(X) ← k Mark X Theorem: Obtains optimal order for chordal graphs Often, not so good in other graphs!BEDHGAFCMinimum fill/size/weight heuristics Many more effective heuristics page 262 of K&F Min (weighted) fill heuristic Often very effective Initialize unobserved nodes X as unmarked For k = 1 to |X| X ← unmarked var whose elimination adds fewest edges ≺(X) ← k Mark X Add fill edges introduced by eliminating X Weighted version: Consider size of factor rather than number of edgesBEDHGAFCChoosing an elimination order Choosing best order is NP-complete Reduction from MAX-Clique Many good heuristics (some with guarantees) Ultimately, can’t beat NP-hardness of inference Even optimal order can lead to exponential variable elimination computation In practice Variable elimination often very effective Many (many many) approximate inference approaches available when variable elimination too expensive Most approximate inference approaches build on ideas from variable eliminationMost likely explanation (MLE) Query: Using Bayes rule: Normalization irrelevant:FluAllergySinusHeadacheNoseMax-marginalizationFluAllergy=tSinusExample of variable elimination for MLE – Forward passFluAllergySinusHeadacheNose=tExample of variable elimination for MLE – Backward passFluAllergySinusHeadacheNose=tMLE Variable elimination algorithm – Forward pass Given a BN and a MLE query maxx1,…,xnP(x1,…,xn,e) Instantiate evidence E=e Choose an ordering on variables, e.g., X1, …, Xn For i = 1 to n, If Xi∉E Collect factors f1,…,fkthat include Xi Generate a new factor by eliminating Xifrom these factors Variable Xihas been eliminated!MLE Variable elimination algorithm – Backward pass {x1*,…, xn*} will store maximizing assignment For i = n to 1, If Xi∉ E Take factors f1,…,fkused when Xiwas eliminated Instantiate f1,…,fk, with {xi+1*,…, xn*} Now each fjdepends only on Xi Generate maximizing assignment for Xi:What you need to know Variable elimination algorithm Eliminate a variable: Combine factors that include this var into single factor Marginalize var from new factor Cliques in induced graph correspond to factors generated by algorithm  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)Elimination order is important! NP-complete problem Many good heuristics Variable elimination for MLE Only difference


View Full Document

CMU CS 10708 - Variable elimination 2 Clique trees

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 2 Clique trees
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 2 Clique trees 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 Clique trees 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?