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 distributionsGiven Random vars X1,…,XnP distribution over vars BN structure G over same varsP 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 GNumber variables such that:parent has lower number than childi.e., Xi ! Xj ) i<jDAGs always have (many) topological orderingsfind 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 hurtTheorem: 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 BNGiven a set of variables and conditional independence assertions of PChoose an ordering on variables, e.g., X1, …, Xn For i = 1 to nAdd Xi to the networkDefine 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 PaXiDefine/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 farIndependence & conditional independenceDefinition of a BNLocal Markov assumptionThe representation theorems Statement: G is an I-map for P if and only if P factorizes according to G Interpretation10-708 – Carlos Guestrin 200614 AnnouncementsUpcoming recitationTomorrow 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-announceIf 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 BNWe said: All you need is the local Markov assumption(Xi NonDescendantsXi | PaXi)But then we talked about other (in)dependenciese.g., explaining awayWhat are the independencies encoded by a BN?Only assumption is local MarkovBut 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