DOC PREVIEW
CMU CS 10708 - structure-learn-inference2

This preview shows page 1-2-14-15-29-30 out of 30 pages.

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

Unformatted text preview:

Structure Learning (The Good), The Bad, The Ugly InferenceDecomposable scoreStructure learning for general graphsUnderstanding score decompositionFixed variable order 1Fixed variable order 2Learn BN structure using local searchExploit score decomposition in local searchSome experimentsOrder search versus graph searchBayesian model averagingWhat you need to know about learning BN structuresInference in graphical models: Typical queries 1Inference in graphical models: Typical queries 2 – MaximizationAre MPE and MAP Consistent?C++ LibraryComplexity of conditional probability queries 1Complexity of conditional probability queries 2Inference is #P-complete, hopeless?Complexity for other inference questionsInference in BNs hopeless?General probabilistic inferenceMarginalizationProbabilistic inference exampleFast probabilistic inference example – Variable eliminationUnderstanding variable elimination – Exploiting distributivityUnderstanding variable elimination – Order can make a HUGE differenceUnderstanding variable elimination – Intermediate resultsUnderstanding variable elimination – Another examplePruning irrelevant variables1Structure Learning(The Good), The Bad, The UglyInference Graphical Models – 10708Carlos GuestrinCarnegie Mellon UniversityOctober 13th, 2008Readings:K&F: 17.3, 17.4, 17.5.1, 8.1, 12.110-708 – Carlos Guestrin 2006-200810-708 – Carlos Guestrin 2006-20082Decomposable scoreLog data likelihoodDecomposable score:Decomposes over families in BN (node and its parents)Will lead to significant computational efficiency!!!Score(G : D) = i FamScore(Xi|PaXi : D)10-708 – Carlos Guestrin 2006-20083Structure learning for general graphsIn a tree, a node only has one parentTheorem:The problem of learning a BN structure with at most d parents is NP-hard for any (fixed) d≥2Most structure learning approaches use heuristicsExploit score decomposition(Quickly) Describe two heuristics that exploit decomposition in different ways10-708 – Carlos Guestrin 2006-20084Understanding score decompositionDifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 2006-20085Fixed variable order 1Pick a variable ordere.g., X1,…,XnXi can only pick parents in {X1,…,Xi-1}Any subsetAcyclicity guaranteed!Total score = sum score of each node10-708 – Carlos Guestrin 2006-20086Fixed variable order 2Fix max number of parents to kFor each i in order Pick PaXi{X1,…,Xi-1}Exhaustively search through all possible subsetsPaXi is maximum U{X1,…,Xi-1} FamScore(Xi|U : D)Optimal BN for each order!!!Greedy search through space of orders:E.g., try switching pairs of variables in orderIf neighboring vars in order are switched, only need to recompute score for this pair O(n) speed up per iteration10-708 – Carlos Guestrin 2006-20087Learn BN structure using local searchStarting from Chow-Liu treeLocal search,possible moves:Only if acyclic!!!• Add edge• Delete edge• Invert edgeSelect using favorite score10-708 – Carlos Guestrin 2006-20088Exploit score decomposition in local searchAdd edge and delete edge:Only rescore one family!Reverse edgeRescore only two familiesDifficultySATGradeHappyJobCoherenceLetterIntelligence10-708 – Carlos Guestrin 2006-20089Some experimentsAlarm network10-708 – Carlos Guestrin 2006-200810Order search versus graph searchOrder search advantagesFor fixed order, optimal BN – more “global” optimizationSpace of orders much smaller than space of graphsGraph search advantagesNot restricted to k parentsEspecially if exploiting CPD structure, such as CSICheaper per iterationFiner moves within a graph10-708 – Carlos Guestrin 2006-200811Bayesian model averagingSo far, we have selected a single structureBut, if you are really Bayesian, must average over structuresSimilar to averaging over parametersInference for structure averaging is very hard!!!Clever tricks in reading10-708 – Carlos Guestrin 2006-200812What you need to know about learning BN structuresDecomposable scoresData likelihood Information theoretic interpretationBayesianBIC approximationPriorsStructure and parameter assumptionsBDe if and only if score equivalenceBest tree (Chow-Liu)Best TANNearly best k-treewidth (in O(Nk+1))Search techniquesSearch through ordersSearch through structuresBayesian model averaging10-708 – Carlos Guestrin 2006-200813Inference in graphical models: Typical queries 1FluAllergySinusHeadacheNoseConditional probabilitiesDistribution of some var(s). given evidence10-708 – Carlos Guestrin 2006-200814Inference in graphical models: Typical queries 2 – MaximizationFluAllergySinusHeadacheNoseMost probable explanation (MPE)Most likely assignment to all hidden vars given evidenceMaximum a posteriori (MAP)Most likely assignment to some var(s) given evidence10-708 – Carlos Guestrin 2006-200815Are MPE and MAP Consistent?Sinus NoseMost probable explanation (MPE)Most likely assignment to all hidden vars given evidenceMaximum a posteriori (MAP)Most likely assignment to some var(s) given evidenceP(S=t)=0.4 P(S=f)=0.6P(N|S)C++ LibraryNow available, join:http://groups.google.com/group/10708-f08-code/The library implements the following functionality:random variables, random processes, and linear algebrafactorized distributions, such Gaussians, multinomial distributions, and mixturesgraph structures and basic graph algorithmsgraphical models, including Bayesian networks, Markov networks, andjunction treesbasic static and dynamic inference algorithmsparameter learning for Gaussian distributions, Chow LiuFairly advanced C++ (not for everyone )10-708 – Carlos Guestrin 2006-20081610-708 – Carlos Guestrin 2006-200817Complexity of conditional probability queries 1How hard is it to compute P(X|E=e)?Reduction – 3-SAT...)()(432321 XXXXXX10-708 – Carlos Guestrin 2006-200818Complexity of conditional probability queries 2How hard is it to compute P(X|E=e)? At least NP-hard, but even harder!10-708 – Carlos Guestrin 2006-200819Inference is #P-complete, hopeless?Exploit structure!Inference is hard in general, but easy for many (real-world relevant) BN structures10-708 – Carlos Guestrin 2006-200820Complexity for


View Full Document

CMU CS 10708 - structure-learn-inference2

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 structure-learn-inference2
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 structure-learn-inference2 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 structure-learn-inference2 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?