1Bayesian Networks:Independencies and InferenceScott Davies and Andrew MooreNote 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.2What 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 non-descendants in the graph given the value of all its parents.• This implies• But what else does it imply?∏==niiinXparentsXPXXP11))(|()( K3What Independencies does a Bayes Net Model?• Example:ZYXGiven Y, does learning the value of Z tell usnothing new about X? I.e., is P(X|Y, Z) equal to P(X | 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.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:),()()|,(),|(YXPZPZYXPYXZP =)()|()(),|()|(YPYXPZPZYXPZYP=(Bayes’s Rule)(Chain Rule)(By Assumption)(Bayes’s Rule))()|()()|()|(YPYXPZPYXPZYP=)|()()()|(YZPYPZPZYP==4What Independencies does a Bayes Net Model?• Let I<X,Y,Z> represent X and Z being conditionally independent given Y.• I<X,Y,Z>? Yes, just as in previous example: All X’s parents given, and Z is not a descendant.YX ZWhat Independencies does a Bayes Net Model?• 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…?ZVUX5Things get a little more confusing• 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?ZXYThe “Burglar Alarm” example• 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!Burglar EarthquakeAlarmPhone Call6Things get a lot more confusing• 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 thoughI<Burglar,{}, Earthquake>!Burglar EarthquakeAlarmPhone Calld-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 Xto Z is “blocked”, where a path is “blocked” iff one or more of the following conditions is true: ...7A 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”• 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”• Or, ...VVA 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”V8d-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 d-separated, depending on the actual probabilities involvedd-separation exampleA BC DE FGIHJ•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>?9Bayesian Network Inference• Inference: calculating P(X|Y) for some variables or sets of variables X and Y.• Inference in Bayesian networks is #P-hard!Reduces toHow many satisfying assignments? I1 I2 I3 I4 I5OInputs: prior probabilities of .5P(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 / forestsin which each node has at most one parent.10Decomposing 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 itXiDecomposing the probabilities, cont’d),|()|(+−=iiiiEEXPEXPXi11Decomposing the probabilities, cont’d)|()|(),|(),|()|(+−++−+−==iiiiiiiiiEEPEXPEXEPEEXPEXPXiDecomposing the probabilities, cont’d)|()|()|()|()|(),|(),|()|(+−+−+−++−+−===iiiiiiiiiiiiiEEPEXPXEPEEPEXPEXEPEEXPEXPXi12Decomposing the probabilities, cont’d)(λ)(απ)|()|()|()|()|(),|(),|()|(iiiiiiiiiiiiiiiXXEEPEXPXEPEEPEXPEXEPEEXPEXP====+−+−+−++−+−XiWhere:• α 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 Xirecursively, using the leaves of the tree as the base case.• If Xiis a leaf:• If Xiis in E: λ(Xi) = 1 if Ximatches E, 0 otherwise• If Xiis not in E: Ei-is the null set, so P(Ei-| Xi) = 1 (constant)13Quick aside: “Virtual evidence”• For theoretical simplicity, but without loss of generality, let’s assume that all variables in E (the evidence set) are leaves in the
View Full Document
Unlocking...