DOC PREVIEW
CMU CS 10701 - Bayesian Networks – Inference

This preview shows page 1-2-3-19-20-39-40-41 out of 41 pages.

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

Unformatted text preview:

2005-2007 Carlos GuestrinBayesian Networks –Inference Machine Learning – 10701/15781Carlos GuestrinCarnegie Mellon UniversityMarch 21st, 20072005-2007 Carlos GuestrinHandwriting recognitionCharacter recognition, e.g., kernel SVMszcbcacrrrrrr2005-2007 Carlos GuestrinHandwriting recognition 22005-2007 Carlos GuestrinFactored joint distribution -PreviewFluAllergySinusHeadacheNose2005-2007 Carlos GuestrinKey: Independence assumptionsFluAllergySinusHeadacheNoseKnowing sinus separates the variables from each other2005-2007 Carlos GuestrinThe independence assumption FluAllergySinusHeadacheNoseLocal Markov Assumption:A variable X is independentof its non-descendants given its parents2005-2007 Carlos GuestrinExplaining awayFluAllergySinusHeadacheNoseLocal Markov Assumption:A variable X is independentof its non-descendants given its parents2005-2007 Carlos GuestrinThe Representation Theorem –Joint Distribution to BNJoint probabilitydistribution:ObtainBN:Encodes independenceassumptionsIf conditionalindependenciesin BN are subset of conditional independencies in P2005-2007 Carlos GuestrinA general Bayes net Set of random variables Directed acyclic graph  Encodes independence assumptions CPTs Joint distribution:2005-2007 Carlos GuestrinHow many parameters in a BN? Discrete variables X1, …, Xn Graph Defines parents of Xi, PaXi CPTs – P(Xi| PaXi)2005-2007 Carlos GuestrinAnother example Variables: B – Burglar E – Earthquake  A – Burglar alarm N – Neighbor calls R – Radio report Both burglars and earthquakes can set off the alarm If the alarm sounds, a neighbor may call An earthquake may be announced on the radio2005-2007 Carlos GuestrinIndependencies encoded in BN We said: All you need is the local Markov assumption (Xi⊥ NonDescendantsXi| PaXi) But then we talked about other (in)dependencies e.g., explaining away What are the independencies encoded by a BN? Only assumption is local Markov But many others can be derived using the algebra of conditional independencies!!!2005-2007 Carlos GuestrinUnderstanding independencies in BNs– BNs with 3 nodesZYXLocal Markov Assumption:A variable X is independentof its non-descendants given its parents Z YXZ YXZYXIndirect causal effect:Indirect evidential effect:Common cause:Common effect:2005-2007 Carlos GuestrinUnderstanding independencies in BNs– Some examplesAHCEGDBFKJI2005-2007 Carlos GuestrinAn active trail – ExampleA HCEGDBFF’’F’When are A and H independent?2005-2007 Carlos GuestrinActive trails formalized A path X1 – X2 – · · · –Xkis an active trail when variables O⊆{X1,…,Xn} are observed if for each consecutive triplet in the trail: Xi-1→Xi→Xi+1, and Xiis not observed (Xi∉O) Xi-1←Xi←Xi+1, and Xiis not observed (Xi∉O) Xi-1←Xi→Xi+1, and Xiis not observed (Xi∉O) Xi-1→Xi←Xi+1, and Xiis observed (Xi∈O), or one of its descendents2005-2007 Carlos GuestrinActive trails and independence? Theorem: Variables Xiand Xjare independent given Z⊆{X1,…,Xn} if the is no active trail between Xiand Xjwhen variables Z⊆{X1,…,Xn} are observedAHCEGDBFKJI2005-2007 Carlos GuestrinThe BN Representation TheoremIf joint probabilitydistribution:ObtainThen conditionalindependenciesin BN are subset of conditional independencies in PJoint probabilitydistribution:ObtainIf conditionalindependenciesin BN are subset of conditional independencies in PImportant because: Every P has at least one BN structure GImportant because: Read independencies of P from BN structure G2005-2007 Carlos GuestrinLearning Bayes netsMissing dataFully observable dataUnknown structureKnown structurex(1)…x(m)Datastructure parametersCPTs –P(Xi| PaXi)2005-2007 Carlos GuestrinLearning the CPTsx(1)…x(m)DataFor each discrete variable Xi2005-2007 Carlos GuestrinWhat you need to know Bayesian networks A compact representation for large probability distributions  Not an algorithm Semantics of a BN Conditional independence assumptions Representation Variables Graph CPTs Why BNs are useful Learning CPTs from fully observable data Play with applet!!! ☺2005-2007 Carlos GuestrinGeneral probabilistic inference Query: Using Bayes rule: Normalization:FluAllergySinusHeadacheNose2005-2007 Carlos GuestrinMarginalizationFlu Sinus Nose=t2005-2007 Carlos GuestrinProbabilistic inference exampleFluAllergySinusHeadacheNose=tInference seems exponential in number of variables!Actually, inference in graphical models is NP-hard 2005-2007 Carlos GuestrinFast probabilistic inference example – Variable eliminationFluAllergySinusHeadacheNose=t(Potential for) Exponential reduction in computation!2005-2007 Carlos GuestrinUnderstanding variable elimination –Exploiting distributivityFlu Sinus Nose=t2005-2007 Carlos GuestrinUnderstanding variable elimination –Order can make a HUGE differenceFluAllergySinusHeadacheNose=t2005-2007 Carlos GuestrinUnderstanding variable elimination –Another examplePharmacySinusHeadacheNose=t2005-2007 Carlos GuestrinVariable elimination algorithm Given a BN and a query P(X|e) ∝ P(X,e) Instantiate evidence e Choose an ordering on variables, e.g., X1, …, Xn For i = 1 to n, If Xi∉{X,e} Collect factors f1,…,fkthat include Xi Generate a new factor by eliminating Xifrom these factors Variable Xihas been eliminated! Normalize P(X,e) to obtain P(X|e)IMPORTANT!!!2005-2007 Carlos GuestrinComplexity of variable elimination –(Poly)-tree graphsVariable elimination order:Start from “leaves” up –find topological order, eliminate variables in reverse orderLinear in number of variables!!! (versus exponential)2005-2007 Carlos GuestrinComplexity of variable elimination –Graphs with loopsExponential in number of variables in largest factor generated2005-2007 Carlos GuestrinComplexity of variable elimination –Tree-widthMoralize graph:Connect parents into a clique and remove edge directionsComplexity of VE elimination:(“Only”) exponential in tree-widthTree-width is maximum node cut +12005-2007 Carlos GuestrinExample: Large tree-width with small number of parentsCompact representation ⇒⇒⇒⇒ Easy inference 2005-2007 Carlos GuestrinChoosing an elimination order Choosing best order is NP-complete Reduction from MAX-Clique Many


View Full Document

CMU CS 10701 - Bayesian Networks – Inference

Documents in this Course
lecture

lecture

12 pages

lecture

lecture

17 pages

HMMs

HMMs

40 pages

lecture

lecture

15 pages

lecture

lecture

20 pages

Notes

Notes

10 pages

Notes

Notes

15 pages

Lecture

Lecture

22 pages

Lecture

Lecture

13 pages

Lecture

Lecture

24 pages

Lecture9

Lecture9

38 pages

lecture

lecture

26 pages

lecture

lecture

13 pages

Lecture

Lecture

5 pages

lecture

lecture

18 pages

lecture

lecture

22 pages

Boosting

Boosting

11 pages

lecture

lecture

16 pages

lecture

lecture

20 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Lecture

Lecture

14 pages

Lecture

Lecture

18 pages

Lecture

Lecture

13 pages

Exam

Exam

10 pages

Lecture

Lecture

27 pages

Lecture

Lecture

15 pages

Lecture

Lecture

24 pages

Lecture

Lecture

16 pages

Lecture

Lecture

23 pages

Lecture6

Lecture6

28 pages

Notes

Notes

34 pages

lecture

lecture

15 pages

Midterm

Midterm

11 pages

lecture

lecture

11 pages

lecture

lecture

23 pages

Boosting

Boosting

35 pages

Lecture

Lecture

49 pages

Lecture

Lecture

22 pages

Lecture

Lecture

16 pages

Lecture

Lecture

18 pages

Lecture

Lecture

35 pages

lecture

lecture

22 pages

lecture

lecture

24 pages

Midterm

Midterm

17 pages

exam

exam

15 pages

Lecture12

Lecture12

32 pages

lecture

lecture

19 pages

Lecture

Lecture

32 pages

boosting

boosting

11 pages

pca-mdps

pca-mdps

56 pages

bns

bns

45 pages

mdps

mdps

42 pages

svms

svms

10 pages

Notes

Notes

12 pages

lecture

lecture

42 pages

lecture

lecture

29 pages

lecture

lecture

15 pages

Lecture

Lecture

12 pages

Lecture

Lecture

24 pages

Lecture

Lecture

22 pages

Midterm

Midterm

5 pages

mdps-rl

mdps-rl

26 pages

Load more
Download Bayesian Networks – Inference
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 Bayesian Networks – Inference 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 Bayesian Networks – Inference 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?