1 Machine Learning 10-601 Tom M. Mitchell Machine Learning Department Carnegie Mellon University October 13, 2011 Today: • Graphical models • Bayes Nets: • Conditional independencies • Inference • Learning Readings: Required: • Bishop chapter 8, through 8.2 Conditional Independence, Revisited • We said: – Each node is conditionally independent of its non-descendents, given its immediate parents. • Does this rule give us all of the conditional independence relations implied by the Bayes network? – No! – E.g., X1 and X4 are conditionally indep given {X2, X3} – But X1 and X4 not conditionally indep given X3 – For this, we need to understand D-separation X1 X4 X2 X32 prove A cond indep of B given C? ie., p(a,b|c) = p(a|c) p(b|c) Easy Network 1: Head to Tail A C B let’s use p(a,b) as shorthand for p(A=a, B=b) prove A cond indep of B given C? ie., p(a,b|c) = p(a|c) p(b|c) Easy Network 2: Tail to Tail A C B let’s use p(a,b) as shorthand for p(A=a, B=b)3 prove A cond indep of B given C? NO! Summary: • p(a,b)=p(a)p(b) • p(a,b|c) NotEqual p(a|c)p(b|c) Explaining away. e.g., • A=earthquake • B=breakIn • C=motionAlarm Easy Network 3: Head to Head A C B X and Y are conditionally independent given Z, if and only if X and Y are D-separated by Z. Suppose we have three sets of random variables: X, Y and Z X and Y are D-separated by Z (and therefore conditionally indep, given Z) iff every path from every variable in X to every variable in Y is blocked A path from variable A to variable B is blocked if it includes a node such that either 1. arrows on the path meet either head-to-tail or tail-to-tail at the node and this node is in Z 2. the arrows meet head-to-head at the node, and neither the node, nor any of its descendants, is in Z [Bishop, 8.2.2]4 X and Y are D-separated by Z (and therefore conditionally indep, given Z) iff every path from every variable in X to every variable in Y is blocked A path from variable A to variable B is blocked if it includes a node such that either 1. arrows on the path meet either head-to-tail or tail-to-tail at the node and this node is in Z 2. the arrows meet head-to-head at the node, and neither the node, nor any of its descendants, is in Z X1 indep of X3 given X2? X3 indep of X1 given X2? X4 indep of X1 given X2? X1 X4 X2 X3 X and Y are D-separated by Z (and therefore conditionally indep, given Z) iff every path from any variable in X to any variable in Y is blocked by Z A path from variable A to variable B is blocked by Z if it includes a node such that either 1. arrows on the path meet either head-to-tail or tail-to-tail at the node and this node is in Z 2. the arrows meet head-to-head at the node, and neither the node, nor any of its descendants, is in Z X4 indep of X1 given X3? X4 indep of X1 given {X3, X2}? X4 indep of X1 given {}? X1 X4 X2 X35 X and Y are D-separated by Z (and therefore conditionally indep, given Z) iff every path from any variable in X to any variable in Y is blocked A path from variable A to variable B is blocked if it includes a node such that either 1. arrows on the path meet either head-to-tail or tail-to-tail at the node and this node is in Z 2. the arrows meet head-to-head at the node, and neither the node, nor any of its descendants, is in Z a indep of b given c? a indep of b given f ? Markov Blanket from [Bishop, 8.2]6 What You Should Know • Bayes nets are convenient representation for encoding dependencies / conditional independence • BN = Graph plus parameters of CPD’s – Defines joint distribution over variables – Can calculate everything else from that – Though inference may be intractable • Reading conditional independence relations from the graph – Each node is cond indep of non-descendents, given only its parents – D-separation – ‘Explaining away’ See Bayes Net applet: http://www.cs.cmu.edu/~javabayes/Home/applet.html Inference in Bayes Nets • In general, intractable (NP-complete) • For certain cases, tractable – Assigning probability to fully observed set of variables – Or if just one variable unobserved – Or for singly connected graphs (ie., no undirected loops) • Belief propagation • For multiply connected graphs • Junction tree • Sometimes use Monte Carlo methods – Generate many samples according to the Bayes Net distribution, then count up the results • Variational methods for tractable approximate solutions7 Example • Bird flu and Allegies both cause Sinus problems • Sinus problems cause Headaches and runny Nose Prob. of joint assignment: easy • Suppose we are interested in joint assignment <F=f,A=a,S=s,H=h,N=n> What is P(f,a,s,h,n)? let’s use p(a,b) as shorthand for p(A=a, B=b)8 Prob. of marginals: not so easy • How do we calculate P(N=n) ? let’s use p(a,b) as shorthand for p(A=a, B=b) Generating a sample from joint distribution: easy How can we generate random samples drawn according to P(F,A,S,H,N)? let’s use p(a,b) as shorthand for p(A=a, B=b)9 Generating a sample from joint distribution: easy Note we can estimate marginals like P(N=n) by generating many samples from joint distribution, then count the fraction of samples for which N=n Similarly, for anything else we care about P(F=1|H=1, N=0) à weak but general method for estimating any probability term… let’s use p(a,b) as shorthand for p(A=a, B=b) Prob. of marginals: not so easy But sometimes the structure of the network allows us to be clever à avoid exponential work eg., chain A D B C E10 Inference in Bayes Nets • In general, intractable (NP-complete) • For certain cases, tractable – Assigning probability to fully observed set of variables – Or if just one variable unobserved – Or for singly connected graphs (ie., no undirected loops) • Variable elimination • Belief propagation • For multiply connected graphs • Junction tree • Sometimes use Monte Carlo methods – Generate many samples according to the Bayes Net distribution, then count up the results • Variational methods for tractable approximate
View Full Document
Unlocking...