DOC PREVIEW
CMU CS 10708 - Variable Elimination 2

This preview shows page 1-2-3-20-21-40-41-42 out of 42 pages.

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

Unformatted text preview:

Variable Elimination 2 Clique TreesComplexity of variable elimination – Graphs with loopsInduced 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 orderAnnouncementsMost 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 know about VEWhat if I want to compute P(Xi|x0,xn+1) for each i?Reusing computationCluster graphFactors generated by VECluster graph for VERunning intersection propertyConstructing a clique tree from VEFind clique tree from chordal graphClique 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 treeAnswering queries with clique treesMessage passing with divisionLauritzen-Spiegelhalter Algorithm (a.k.a. belief propagation)VE versus BP in clique treesClique tree invariantBelief propagation and clique tree invariantSubtree correctnessClique trees versus VEClique tree summary1Variable Elimination 2Clique TreesGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 13th, 2006Readings:K&F: 8.1, 8.2, 8.3, 8.7.1K&F: 9.1, 9.2, 9.3, 9.410-708 – Carlos Guestrin 20062 Complexity 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 20063 Induced 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 20064 Induced 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}10-708 –  Carlos Guestrin 20065 Example: Large induced-width with small number of parentsCompact representation  Easy inference 10-708 – Carlos Guestrin 20066 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 finding elimination order in addition to hardness of inferenceActually, can find elimination order in time exponential in size of largest clique – same complexity as inferenceElimination order:{C,D,I,S,L,H,J,G}10-708 – Carlos Guestrin 20067 Induced graphs and chordal graphsDifficultySATGradeHappyJobCoherenceLetterIntelligenceChordal graph:Every cycle X1 – X2 – … – Xk – X1 with k ¸ 3 has a chordEdge Xi – Xj for non-consecutive i & jTheorem:Every induced graph is chordal“Optimal” elimination order easily obtained for chordal graph10-708 – Carlos Guestrin 20068 Chordal 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!BEDHGAFC10-708 –  Carlos Guestrin 20069 Minimum fill/size/weight heuristicsMany more effective heuristicssee reading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 edgesBEDHGAFC10-708 – Carlos Guestrin 200610 Choosing 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 elimination10-708 – Carlos Guestrin 200611 AnnouncementsRecitation on advanced topic:Carlos on Context-Specific Independence On Monday Oct 16, 5:30-7:00pm in Wean Hall 4615A10-708 – Carlos Guestrin 200612 Most likely explanation (MLE)Query:Using defn of conditional probs:Normalization irrelevant:FluAllergySinusHeadacheNose10-708 – Carlos Guestrin 200613 Max-marginalizationFlu Sinus Nose=t10-708 – Carlos Guestrin 200614 Example of variable elimination for MLE – Forward passFluAllergySinusHeadacheNose=t10-708 – Carlos Guestrin 200615 Example of variable elimination for MLE – Backward passFluAllergySinusHeadacheNose=t10-708 – Carlos Guestrin 200616 MLE 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,…,fk that include XiGenerate a new factor by eliminating Xi from these factorsVariable Xi has been eliminated!10-708 – Carlos Guestrin 200617 MLE Variable elimination algorithm – Backward pass{x1*,…, xn*} will store maximizing assignmentFor i = n to 1, If Xi  ETake factors f1,…,fk used when Xi was eliminatedInstantiate f1,…,fk, with {xi+1*,…, xn*}Now each fj depends only on XiGenerate maximizing assignment


View Full Document

CMU CS 10708 - Variable Elimination 2

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