1Machine Learning 10-701Tom M. MitchellMachine Learning DepartmentCarnegie Mellon UniversityFebruary 15, 2011Today:• Graphical models• Inference• Conditional independence and D-separation• Learning from fully labeled dataReadings:Required:• Bishop chapter 8, through 8.2Bayesian Networks DefinitionA Bayes network represents the joint probability distribution over a collection of random variablesA Bayes network is a directed acyclic graph and a set of CPD’s• Each node denotes a random variable• Edges denote dependencies• CPD for each node Xidefines P(Xi| Pa(Xi))• The joint distribution over all variables is defined asPa(X) = immediate parents of X in the graph2Inference 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 solutionsExample• Bird flu and Allegies both cause Sinus problems• Sinus problems cause Headaches and runny Nose3Prob. of joint assignment: easy • Suppose we are interested in jointassignment <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)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)4Generating a sample from joint distribution: easy How can we generate random samplesdrawn according to P(F,A,S,H,N)?let’s use p(a,b) as shorthand for p(A=a, B=b)Generating a sample from joint distribution: easy Note we can estimate marginalslike P(N=n) by generating many samplesfrom joint distribution, by summing the probability mass for which N=nSimilarly, for anything else we care about P(F=1|H=1, N=0) weak but general method for estimating anyprobability term…let’s use p(a,b) as shorthand for p(A=a, B=b)5Prob. of marginals: not so easy But sometimes the structure of the network allows us to be clever avoid exponential workeg., chain A DB C EProb. of marginals: not so easy But sometimes the structure of the network allows us to be clever avoid exponential workeg., chain A DB C E6Inference 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 solutionsConditional 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 …X1X4 X2X37Inference 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 solutionsConditional 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-separationX1X4 X2X38prove A cond indep of B given C?ie., p(a,b|c) = p(a|c) p(b|c)Easy Network 1: Head to Tail ACBlet’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 ACBlet’s use p(a,b) as shorthand for p(A=a, B=b)9prove A cond indep of B given C? ie., p(a,b|c) = p(a|c) p(b|c)Easy Network 3: Head to HeadACBlet’s use p(a,b) as shorthand for p(A=a, B=b)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=motionAlarmEasy Network 3: Head to HeadACB10X 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 ZX 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 blockedA path from variable A to variable B is blocked if it includes a node such that either1.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]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 blockedA path from variable A to variable B is blocked if it includes a node such that either1.arrows on the path meet either head-to-tail or tail-to-tail at the node and this node is in Z2.the arrows meet head-to-head at the node, and neither the node, nor any of its descendants, is in ZX1 indep of X3 given X2?X3 indep of X1 given X2?X4 indep of X1 given X2?X1X4 X2X311X and Y are D-separated by Z (and therefore conditionally indep, given Z) iffevery path from any variable in X to any variable in Y is blocked by ZA path from variable A to variable B is blocked by Z if it includes a node such that either1.arrows on the path meet either head-to-tail or tail-to-tail at the node and this node is in Z2.the arrows meet head-to-head at the node, and neither the node, nor any of its descendants, is in ZX4 indep of X1
View Full Document
Unlocking...