Machine Learning 10 701 Tom M Mitchell Machine Learning Department Carnegie Mellon University February 15 2011 Today Readings Required Bishop chapter 8 through 8 2 Graphical models Inference Conditional independence and D separation Learning from fully labeled data Bayesian Networks Definition A Bayes network represents the joint probability distribution over a collection of random variables A 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 Xi defines P Xi Pa Xi The joint distribution over all variables is defined as Pa X immediate parents of X in the graph 1 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 solutions Example Bird flu and Allegies both cause Sinus problems Sinus problems cause Headaches and runny Nose 2 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 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 3 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 Generating a sample from joint distribution easy Note we can estimate marginals like P N n by generating many samples from joint distribution by summing the probability mass 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 4 Prob of marginals not so easy But sometimes the structure of the network allows us to be clever avoid exponential work eg chain A B C D E Prob of marginals not so easy But sometimes the structure of the network allows us to be clever avoid exponential work eg chain A B C D E 5 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 solutions 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 X3 6 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 solutions 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 X3 7 Easy Network 1 Head to Tail A prove A cond indep of B given C ie p a b c p a c p b c C B let s use p a b as shorthand for p A a B b Easy Network 2 Tail to Tail prove A cond indep of B given C A ie p a b c p a c p b c C B let s use p a b as shorthand for p A a B b 8 Easy Network 3 Head to Head prove A cond indep of B given C A ie p a b c p a c p b c C B let s use p a b as shorthand for p A a B b Easy Network 3 Head to Head prove A cond indep of B given C A NO Summary p a b p a p b p a b c NotEqual p a c p b c C B Explaining away e g A earthquake B breakIn C motionAlarm 9 X and Y are conditionally independent given Z if and only if X and Y are D separated by Z Bishop 8 2 2 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 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 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 X1 indep of X3 given X2 X1 X3 indep of X1 given X2 X4 indep of X1 given X2 X4 X2 X3 10 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 …
View Full Document
Unlocking...