Slide 1Slide 2Getting a Full Joint Table Entry from a Bayes NetInference ExampleChain RuleChain Rule and BN SemanticsMarkov Blanket and Conditional Independenced-Separationd-Separation (continued)d-Separation (continued)d-SeparationAn I-Map is a Set of Conditional Independence StatementsSlide 13Procedure for BN ConstructionPrinciples to Guide ChoicesIdentifying Conditional Independencies in Bayes NetsLecture 4Getting a Full Joint Table Entry from a Bayes Net•Recall:•A table entry for X1 = x1,…,Xn = xn is simply P(x1,…,xn) which can be calculated based on the Bayes Net semantics above.•Recall example:P ( ) = P ( )x , . . . , x x | P a r e n t s ( X )n i ii =n11P ( ) = P ( ) P ( ) P ( ) P ( ) P ( )a , j , m , b , e j | a m | aa | b , e b e    Inference Example•What is probability alarm sounds, but neither a burglary nor an earthquake has occurred, and both John and Mary call?•Using j for John Calls, a for Alarm, etc.:P ( ) =P ( ) P ( ) P ( ) P ( ) P ( ) =( 0 . 9 ) ( 0 . 7 ) ( 0 . 0 0 1 ) ( 0 . 9 9 9 ) ( 0 . 9 9 8 ) = 0 . 0 0 0 6 2j m a b ej a m a a b e b e         | | |Chain Rule•Generalization of the product rule, easily proven by repeated application of the product rule•Chain Rule: P ( ) =P ( ) P ( ) . . . P ( ) P ( )= P ( )x , . . . xx | x , . . . , x x | x , . . . , x x | x xx | x , . . . , xnn n - n - n -i i - ii =n11 1 1 2 1 2 1 111Chain Rule and BN SemanticsB N s e m a n t i c s : P ( ) = P ( )K e y P r o p e r t y : ( ) = ( )p r o v i d e d . S a y s a n o d e i sc o n d i t i o n a l l y i n d e p e n d e n t o f i t s p r e d e c e s s o r s i n t h en o d e o r d e r i n g g i v e n i t s p a r e n t s , a n d s u g g e s t si n c r e m e n t a l p r o c e d u r e f o r n e t w o r k c o n s t r u c t i o n .x , . . . , x x | P a r e n t s ( X )X | X , . . . , X X | P a r e n t s ( X )P a r e n t s ( X ) X , . . . , Xn i ii =ni i - i ii i -111 11 1P PMarkov Blanket andConditional Independence•Recall that X is conditionally independent of its predecessors given Parents(X).•Markov Blanket of X: set consisting of the parents of X, the children of X, and the other parents of the children of X.•X is conditionally independent of all nodes in the network given its Markov Blanket.d-SeparationA B CLinear connection: Information can flow between A and Cif and only if we do not have evidence at Bd-Separation (continued)A B CDiverging connection: Information can flow between Aand C if and only if we do not have evidence at Bd-Separation (continued)A B CConverging connection: Information can flow between Aand C if and only if we do have evidence at B or anydescendent of B (such as D or E)D Ed-Separation•An undirected path between two nodes is “cut off” if information cannot flow across one of the nodes in the path•Two nodes are d-separated if every undirected path between them is cut off•Two sets of nodes are d-separated if every pair of nodes, one from each set, is d-separatedAn I-Map is a Set of Conditional Independence Statements•P(X Y | Z): sets of variables X and Y are conditionally independent given Z (given a complete setting for the variables in Z) •A set of conditional independence statements K is an I-map for a probability distribution P just if the independence statements in K are a subset of the conditional independencies in P. K and P can also be graphical models instead of either sets of independence statements or distributions.Note: For Some CPT Choices, More Conditional Independences May Hold•Suppose we have:•Then only conditional independence we have is: P(A C | B)•Now choose CPTs such that A must be True, B must take same value as A, and C must take same value as B•In the resulting distribution P, all pairs of variables are conditionally independent given the third•The Bayes net is an I-map of P A B CProcedure for BN Construction•Choose relevant random variables.•While there are variables left:1 . a n e x t v a r i a b l e a n d a d d a n o d e f o r i t .2 . S e t t o m i n i m a l s e t o f n o d e s s u c h t h a t t h e K e y P r o p e r t y ( p r e v i o u s s l i d e ) i s s a t i s f i e d .3 . D e f i n e t h e c o n d i t i o n a l d i s t r i b u t i o n ( ) .C h o o s es o m ePXP a r e n t s ( X )X | P a r e n t s ( X )iii iPrinciples to Guide Choices•Goal: build a locally structured (sparse) network -- each component interacts with a bounded number of other components.•Add root causes first, then the variables that they