11BN Semantics 2 –The revenge of d-separationGraphical Models – 10708Carlos GuestrinCarnegie Mellon UniversitySeptember 20th, 2006Readings:K&F: 3.3, 3.410-708 –©Carlos Guestrin 20062Local 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:210-708 –©Carlos Guestrin 20063Today: 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 20064Factorized distributions Given Random vars X1,…,Xn P distribution over vars BN structure G over same vars P factorizes according to G ifFluAllergySinusHeadacheNose310-708 –©Carlos Guestrin 20065BN 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 20066BN 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:410-708 –©Carlos Guestrin 20067BN 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 20068Adding 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 Season510-708 –©Carlos Guestrin 20069Defining 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 Xito the network Define parents of Xi, PaXi, in graph as the minimal subset of {X1,…,Xi-1} such that local Markov assumption holds – Xiindependent of rest of {X1,…,Xi-1}, given parents PaXi Define/learn CPT – P(Xi| PaXi)10-708 –©Carlos Guestrin 200610BN 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 P610-708 –©Carlos Guestrin 200611BN 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 200612The 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 G710-708 –©Carlos Guestrin 200613What 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 Pfactorizes according to G Interpretation10-708 –©Carlos Guestrin 200614Announcements 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 class810-708 –©Carlos Guestrin 200615Independencies 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 200616Understanding 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:910-708 –©Carlos Guestrin 200617Understanding independencies in BNs– Some examplesAHCEGDBFKJI10-708 –©Carlos Guestrin 200618Understanding independencies in BNs– Some more examplesAHCEGDBFKJI1010-708 –©Carlos Guestrin 200619An active trail – ExampleA HCEGDBFF’’F’When are A and H independent?10-708 –©Carlos Guestrin 200620Active trails formalized A trail 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 descendents1110-708 –©Carlos Guestrin 200621Active 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 observedAHCEGDBFKJI10-708 –©Carlos Guestrin 200622More generally: Soundness of d-separation Given BN structure G Set of independence assertions obtained by d-separation: I(G) = {(X⊥Y|Z) : d-sepG(X;Y|Z)} Theorem: Soundness of d-separation If P factorizes over G then I(G)⊆I(P) Interpretation: d-separation only captures true independencies Proof discussed when we talk about undirected models1210-708 –©Carlos Guestrin 200623Existence of dependency when not d-separated Theorem:
View Full Document
Unlocking...