Bayesian Networks Independencies and Inference Scott Davies and Andrew Moore Note to other teachers and users of these slides Andrew and Scott would be delighted if you found this source material useful in giving your own lectures Feel free to use these slides verbatim or to modify them to fit your own needs PowerPoint originals are available If you make use of a significant portion of these slides in your own lecture please include this message or the following link to the source repository of Andrew s tutorials http www cs cmu edu awm tutorials Comments and corrections gratefully received 1 What Independencies does a Bayes Net Model In order for a Bayesian network to model a probability distribution the following must be true by definition Each variable is conditionally independent of all its nondescendants in the graph given the value of all its parents This implies n P X 1 K X n P X i parents X i i 1 But what else does it imply 2 What Independencies does a Bayes Net Model Example Given Y does learning the value of Z tell us nothing new about X Z I e is P X Y Z equal to P X Y Y Yes Since we know the value of all of X s parents namely Y and Z is not a descendant of X X is conditionally independent of Z X Also since independence is symmetric P Z Y X P Z Y Quick proof that independence is symmetric Assume P X Y Z P X Y Then P X Y Z P Z P X Y Bayes s Rule P Y Z P X Y Z P Z P X Y P Y Chain Rule P Y Z P X Y P Z P X Y P Y By Assumption P Z X Y P Y Z P Z P Z Y P Y Bayes s Rule 3 What Independencies does a Bayes Net Model Let I X Y Z represent X and Z being conditionally independent given Y Y X Z I X Y Z Yes just as in previous example All X s parents given and Z is not a descendant What Independencies does a Bayes Net Model Z U V X I X U Z No I X U V Z Yes Maybe I X S Z iff S acts a cutset between X and Z in an undirected version of the graph 4 Things get a little more confusing X Z Y X has no parents so we re know all its parents values trivially Z is not a descendant of X So I X Z even though there s a undirected path from X to Z through an unknown variable Y What if we do know the value of Y though Or one of its descendants The Burglar Alarm example Burglar Earthquake Alarm Phone Call Your house has a twitchy burglar alarm that is also sometimes triggered by earthquakes Earth arguably doesn t care whether your house is currently being burgled While you are on vacation one of your neighbors calls and tells you your home s burglar alarm is ringing Uh oh 5 Things get a lot more confusing Burglar Earthquake Alarm Phone Call But now suppose you learn that there was a medium sized earthquake in your neighborhood Oh whew Probably not a burglar after all Earthquake explains away the hypothetical burglar But then it must not be the case that I Burglar Phone Call Earthquake even though I Burglar Earthquake d separation to the rescue Fortunately there is a relatively simple algorithm for determining whether two variables in a Bayesian network are conditionally independent d separation Definition X and Z are d separated by a set of evidence variables E iff every undirected path from X to Z is blocked where a path is blocked iff one or more of the following conditions is true 6 A path is blocked when There exists a variable V on the path such that it is in the evidence set E the arcs putting V in the path are tail to tail V Or there exists a variable V on the path such that it is in the evidence set E the arcs putting V in the path are tail to head V Or A path is blocked when the funky case Or there exists a variable V on the path such that it is NOT in the evidence set E neither are any of its descendants the arcs putting V on the path are head to head V 7 d separation to the rescue cont d Theorem Verma Pearl 1998 If a set of evidence variables E d separates X and Z in a Bayesian network s graph then I X E Z d separation can be computed in linear time using a depth first search like algorithm Great We now have a fast algorithm for automatically inferring whether learning the value of one variable might give us any additional hints about some other variable given what we already know Might Variables may actually be independent when they re not dseparated depending on the actual probabilities involved d separation example A B C D E F G H I J I C D I C A D I C A B D I C A B J D I C A B E J D 8 Bayesian Network Inference Inference calculating P X Y for some variables or sets of variables X and Y Inference in Bayesian networks is P hard Inputs prior probabilities of 5 I1 I2 I3 I4 I5 Reduces to How many satisfying assignments O P O must be sat assign 5 inputs Bayesian Network Inference But inference is still tractable in some cases Let s look a special class of networks trees forests in which each node has at most one parent 9 Decomposing the probabilities Suppose we want P Xi E where E is some set of evidence variables Let s split E into two parts Ei is the part consisting of assignments to variables in the subtree rooted at Xi Ei is the rest of it Xi Decomposing the probabilities cont d P X i E P X i Ei Ei Xi 10 Decomposing the probabilities cont d P X i E P X i Ei Ei P Ei X Ei P X Ei P Ei Ei Xi Decomposing the probabilities cont d P X i E P X i Ei Ei P Ei X Ei P X Ei P Ei Ei Xi P Ei X P X Ei P Ei Ei 11 Decomposing the probabilities cont d P X i E P X i Ei Ei P Ei X Ei P X Ei P Ei Ei Xi P Ei X P X Ei P Ei Ei X i X i Where is a constant independent of Xi Xi P Xi Ei Xi P Ei Xi Using the decomposition for inference We can use this decomposition to do inference as follows First compute Xi P Ei Xi for all Xi recursively using the leaves of the tree as the base case If Xi is …
View Full Document
Unlocking...