Readings K F 3 1 3 2 3 3 1 3 3 2 BN Semantics 2 Representation Theorem The revenge of d separation Graphical Models 10708 Carlos Guestrin Carnegie Mellon University September 17th 2008 10 708 Carlos Guestrin 2006 2008 1 Factored joint distribution Preview Flu Allergy Sinus Headache Nose 10 708 Carlos Guestrin 2006 2008 2 Number of parameters Flu Allergy Sinus Headache Nose 10 708 Carlos Guestrin 2006 2008 3 The independence assumption Flu Allergy Sinus Headache Nose Local Markov Assumption A variable X is independent of its non descendants given its parents and only its parents Xi NonDescendantsXi PaXi 10 708 Carlos Guestrin 2006 2008 4 Joint distribution Flu Allergy Sinus Headache Nose Why can we decompose Local Markov Assumption 10 708 Carlos Guestrin 2006 2008 5 A general Bayes net 10 708 Carlos Guestrin 2006 2008 6 Questions What distributions can be represented by a BN What BNs can represent a distribution What are the independence assumptions encoded in a BN in addition to the local Markov assumption 10 708 Carlos Guestrin 2006 2008 7 Independencies in Problem World Data reality BN Graph G encodes local independence assumptions True distribution P contains independence assertions Key Representational Assumption 10 708 Carlos Guestrin 2006 2008 8 Today The Representation Theorem True Independencies to BN Factorization BN Encodes independence assumptions If conditional independencies Obtain in BN are subset of conditional independencies in P 10 708 Carlos Guestrin 2006 2008 Joint probability distribution 9 Today The Representation Theorem BN Factorization to True Independencies BN If joint probability distribution Encodes independence assumptions Obtain 10 708 Carlos Guestrin 2006 2008 Then conditional independencies in BN are subset of conditional independencies in P 10 Let s start proving it for na ve Bayes From True Independencies to BN Factorization Independence assumptions Xi independent given C Let s assume that P satisfies independencies must prove that P factorizes according to BN P C X1 Xn P C i P Xi C Use chain rule 10 708 Carlos Guestrin 2006 2008 11 Let s start proving it for na ve Bayes From BN Factorization to True Independencies Let s assume that P factorizes according to the BN P C X1 Xn P C i P Xi C Prove the independence assumptions Xi independent given C Actually X Y C 8 X Y subsets of X1 Xn 10 708 Carlos Guestrin 2006 2008 12 Today The Representation Theorem BN If conditional independencies in BN are subset of conditional independencies in P If joint probability distribution Encodes independence assumptions Obtain Obtain 10 708 Carlos Guestrin 2006 2008 Joint probability distribution Then conditional independencies in BN are subset of conditional independencies in P 13 Local Markov assumption I maps Local independence assumptions in BN structure G Flu Allergy Sinus Independence assertions of P Headache BN structure G is an I map independence map if Nose Local Markov Assumption A variable X is independent of its non descendants given its parents and only its parents Xi NonDescendantsXi PaXi 10 708 Carlos Guestrin 2006 2008 14 Factorized distributions Given Random Flu vars X1 Xn P distribution over vars BN structure G over same vars Allergy P factorizes according to G if 10 708 Carlos Guestrin 2006 2008 Sinus Headache Nose 15 BN Representation Theorem I map to factorization If conditional independencies in BN are subset of conditional independencies in P Obtain Joint probability distribution P factorizes according to G G is an I map of P 10 708 Carlos Guestrin 2006 2008 16 BN Representation Theorem I map to factorization Proof part 1 G is an I map of P Obtain P factorizes according to G Topological Ordering Number variables such that parent has lower number than child i e Xi Xj i j Key variable has lower number than all of its DAGs always have many topological orderings Flu Allergy Sinus Headache Nose find by a modification of breadth first search 10 708 Carlos Guestrin 2006 2008 17 BN Representation Theorem I map to factorization Proof part 2 G is an I map of P P factorizes according to G Obtain ALL YOU NEED Local Markov Assumption A variable X is independent of its non descendants given its parents and only its parents Xi NonDescendantsXi PaXi Flu Allergy Sinus Headache 10 708 Carlos Guestrin 2006 2008 Nose 18 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 2006 2008 19 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 Corollary 1 is strictly more expressive than Corollary 2 If G is an I map for P then adding edges still an I map Proof Airplane Season Flu Allergy Sinus Headache 10 708 Carlos Guestrin 2006 2008 Nose 20 Announcements Homework 1 Collaboration policy OK to discuss in groups Tell us on your paper who you talked with Each person must write their own unique paper No searching the web papers etc for answers we trust you want to learn Audit policy Out today Due in 2 weeks beginning of class It s hard start early ask questions No sitting in official auditors only see course website Recitation tomorrow Wean 5409 5pm 10 708 Carlos Guestrin 2006 2008 21 BN Representation Theorem Factorization to I map If joint probability distribution P factorizes according to G Then conditional independencies in BN are subset of conditional independencies in P Obtain G is an I map of P 10 708 Carlos Guestrin 2006 2008 22 BN Representation Theorem Factorization to I map Proof If joint probability distribution P factorizes according to G Then conditional independencies in BN are subset of conditional independencies in P Obtain G is an I map of P Homework 1 10 708 Carlos Guestrin 2006 2008 23 The BN Representation Theorem If conditional independencies in BN are subset of conditional independencies in P Obtain Joint probability distribution Important because Every P has at least one BN structure G If joint probability distribution Obtain Then conditional independencies in BN are subset of conditional independencies in P Important because Read independencies of P from BN structure G 10 708 Carlos Guestrin 2006 2008 24 What you need to know thus far Independence
View Full Document
Unlocking...