DOC PREVIEW
CMU CS 10708 - BN Semantics 2 – The revenge of d-separation

This preview shows page 1-2-3-22-23-24-44-45-46 out of 46 pages.

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

Unformatted text preview:

BN Semantics 2 – The revenge of d-separationLocal Markov assumption & I-mapsToday: The Representation TheoremFactorized distributionsBN Representation Theorem – I-map to factorizationBN Representation Theorem – I-map to factorization: Proof, part 1BN Representation Theorem – I-map to factorization: Proof, part 2Adding edges doesn’t hurtDefining a BNBN Representation Theorem – Factorization to I-mapBN Representation Theorem – Factorization to I-map: ProofThe BN Representation TheoremWhat you need to know thus farAnnouncementsIndependencies encoded in BNUnderstanding independencies in BNs – BNs with 3 nodesUnderstanding independencies in BNs – Some examplesUnderstanding independencies in BNs – Some more examplesAn active trail – ExampleActive trails formalizedActive trails and independence?More generally: Soundness of d-separationExistence of dependency when not d-separatedMore generally: Completeness of d-separationInterpretation of completenessAlgorithm for d-separationWhat you need to knowBuilding BNs from independence propertiesMinimal I-mapsObtaining a minimal I-mapMinimal I-map not unique (or minimal)Perfect maps (P-maps)Inexistence of P-maps 1Inexistence of P-maps 2Obtaining a P-mapI-EquivalenceSkeleton of a BNWhat about V-structures?Same V-structures not necessaryImmoralities & I-EquivalenceSlide 41Identifying the skeleton 1Identifying the skeleton 2Identifying immoralitiesFrom immoralities and skeleton to BN structuresSlide 461BN Semantics 2 – The revenge of d-separationGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversitySeptember 20th, 2006Readings:K&F: 3.3, 3.410-708 – Carlos Guestrin 20062 Local Markov assumption & I-mapsFluAllergySinusHeadacheNoseLocal Markov Assumption:A variable X is independentof its non-descendants given its parents (Xi  NonDescendantsXi | PaXi)Local independence assumptions in BN structure G:Independence assertions of P:BN structure G is an I-map (independence map) if:10-708 – Carlos Guestrin 20063 Today: The Representation TheoremBN:Encodes independenceassumptionsJoint probabilitydistribution:ObtainIf conditionalindependenciesin BN are subset of conditional independencies in PIf joint probabilitydistribution:ObtainThen conditionalindependenciesin BN are subset of conditional independencies in P10-708 – Carlos Guestrin 20064 Factorized distributionsGiven Random vars X1,…,XnP distribution over vars BN structure G over same varsP factorizes according to G ifFluAllergySinusHeadacheNose10-708 –  Carlos Guestrin 20065 BN Representation Theorem – I-map to factorizationJoint probabilitydistribution:ObtainIf conditionalindependenciesin BN are subset of conditional independencies in PG is an I-map of P P factorizes according to G10-708 – Carlos Guestrin 20066 BN Representation Theorem – I-map to factorization: Proof, part 1FluAllergySinusHeadacheNoseObtainG is an I-map of P P factorizes according to GNumber variables such that:parent has lower number than childi.e., Xi ! Xj ) i<jDAGs always have (many) topological orderingsfind by a modification of breadth first search (not exactly what is in the book)Topological Ordering:10-708 – Carlos Guestrin 20067 BN Representation Theorem – I-map to factorization: Proof, part 2Local Markov Assumption:A variable X is independentof its non-descendants given its parents (Xi  NonDescendantsXi | PaXi)ALL YOU NEED:FluAllergySinusHeadacheNoseObtainG is an I-map of P P factorizes according to G10-708 – Carlos Guestrin 20068 Adding edges doesn’t hurtTheorem: Let G be an I-map for P, any DAG G’ that includes the same directed edges as G is also an I-map for P.Proof: FluAllergySinusHeadacheNoseAirplane Season10-708 –  Carlos Guestrin 20069 Defining a BNGiven a set of variables and conditional independence assertions of PChoose an ordering on variables, e.g., X1, …, Xn For i = 1 to nAdd Xi to the networkDefine parents of Xi, PaXi, in graph as the minimal subset of {X1,…,Xi-1} such that local Markov assumption holds – Xi independent of rest of {X1,…,Xi-1}, given parents PaXiDefine/learn CPT – P(Xi| PaXi)10-708 – Carlos Guestrin 200610 BN Representation Theorem – Factorization to I-mapG is an I-map of P P factorizes according to GIf joint probabilitydistribution:ObtainThen conditionalindependenciesin BN are subset of conditional independencies in P10-708 – Carlos Guestrin 200611 BN Representation Theorem – Factorization to I-map: ProofG is an I-map of P P factorizes according to GIf joint probabilitydistribution:ObtainThen conditionalindependenciesin BN are subset of conditional independencies in PHomework 1!!!! 10-708 – Carlos Guestrin 200612 The 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 G10-708 – Carlos Guestrin 200613 What you need to know thus farIndependence & conditional independenceDefinition of a BNLocal Markov assumptionThe representation theorems Statement: G is an I-map for P if and only if P factorizes according to G Interpretation10-708 – Carlos Guestrin 200614 AnnouncementsUpcoming recitationTomorrow 5 - 6:30pm in Wean 4615A review BN representation, representation theorem, d-separation (coming next)Don’t forget to register to the mailing list at:https://mailman.srv.cs.cmu.edu/mailman/listinfo/10708-announceIf you don’t want to take the class for credit (will sit in or audit) – please talk with me after class10-708 – Carlos Guestrin 200615 Independencies 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!!!10-708 –  Carlos Guestrin 200616 Understanding 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


View Full Document

CMU CS 10708 - BN Semantics 2 – The revenge of d-separation

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 BN Semantics 2 – The revenge of d-separation
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 BN Semantics 2 – The revenge of d-separation 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 BN Semantics 2 – The revenge of d-separation 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?