1Bayes NetsRepresenting and Reasoning about Uncertainty(Continued)Combining the Two Examples• I am at work, my neighbor John calls to say that my alarm went off, my neighbor Mary doesn’t call. Sometimes the alarm is set off by a minor earthquake. Is there a burglar?BurglaryEarthquakeJohnCallsMaryCallsAlarm2Earthquake Example• I am at work, my neighbor John calls to say that my alarm went off, neighbor Mary doesn’t call. Sometimes the alarm is set off by a minor earthquake. Is there a burglar?BurglaryEarthquakeJohnCallsMaryCallsAlarm1: Define the variables that completely describe the problem. Earthquake Example• I am at work, my neighbor John calls to say that my alarm went off, neighbor Mary doesn’t call. Sometimes the alarm is set off by a minor earthquake. Is there a burglar?BurglaryEarthquakeJohnCallsMaryCallsAlarm3Earthquake Example• I am at work, my neighbor John calls to say that my alarm went off, neighbor Mary doesn’t call. Sometimes the alarm is set off by a minor earthquake. Is there a burglar?BurglaryEarthquakeJohnCallsMaryCallsAlarm2: Define the links between variables.• The resulting directed graph must be acyclic• If node X has parents Y1,..,Yn, any variable that is not a descendent of X is conditionally independent of X given (Y1,..,Yn)Earthquake Example• I am at work, my neighbor John calls to say that my alarm went off, neighbor Mary doesn’t call. Sometimes the alarm is set off by a minor earthquake. Is there a burglar?BurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=true) = 0.001P(E=true) = 0.0024Earthquake Example• I am at work, my neighbor John calls to say that my alarm went off, neighbor Mary doesn’t call. Sometimes the alarm is set off by a minor earthquake. Is there a burglar?BurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=True) = 0.001P(E=true) = 0.0020.001F F0.29F T0.94T F0.95T TP(A = True|B=b,E=e)B E0.05F0.90TP(J = True|A=a)A0.01F0.70TP(M = True|A=a)AEarthquake Example• I am at work, my neighbor John calls to say that my alarm went off, neighbor Mary doesn’t call. Sometimes the alarm is set off by a minor earthquake. Is there a burglar?BurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=True) = 0.001P(E=true) = 0.0020.001F F0.29F T0.94T F0.95T TP(A = True|B=b,E=e)B E0.05F0.90TP(J = True|A=a)A0.01F0.70TP(M = True|A=a)A3: Add a probability table for each node. The table for node X contains P(X|Parent Values) for each possible combination of parent values5Computing a Joint Entry• Any entry in the joint probability table can be computed: Probability that both John and Mary calls, the alarm goes off, but there is no earthquake or burglar.BurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=True) = 0.001P(E=true) = 0.0020.001F F0.29F T0.94T F0.95T TP(A = True|B=b,E=e)B E0.05F0.90TP(J = True|A=a)A0.01F0.70TP(M = True|A=a)AComputing a Joint EntryP(J ^ M ^ A ^ ¬B ^ ¬ E) = P(J | M ^ A ^ ¬ B ^ ¬ E) P(M ^ A ^ ¬ B ^ ¬ E) = P(J | A) P(M ^ A ^ ¬ B ^ ¬ E) = P(J | A) P(M | A ^ ¬ B ^ ¬ E) = P(J | A) P(M | A) P(A| ¬ B ^ ¬ E) P(¬ B ^ ¬ E)= P(J | A) P(M | A) P(A| ¬ B ^ ¬ E) P(¬ B) P(¬ E)= 0.90 x 0.70 x 0.001 x 0.999 x 0.998 = 0.0006BurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=True) = 0.001P(E=true) = 0.0020.001F F0.29F T0.94T F0.95T TP(A = True|B=b,E=e)B E0.05F0.90TP(J = True|A=a)A0.01F0.70TP(M = True|A=a)A6Computing a Joint EntryP(J ^ M ^ A ^ ~B ^ ~E) = P(J | M ^ A ^ ~B ^ ~E) P(M ^ A ^ ~B ^ ~E) = P(J | A) P(M ^ A ^ ~B ^ ~E) = P(J | A) P(M | A ^ ~B ^ ~E) = P(J | A) P(M | A) P(A| ~B ^ ~E) P(~B ^ ~E)= P(J | A) P(M | A) P(A| ~B ^ ~E) P(~B) P(~E)= 0.90 x 0.70 x 0.001 x 0.999 x 0.998 = 0.0006BurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=True) = 0.001P(E=true) = 0.0020.001F F0.29F T0.94T F0.95T TP(A = True|B=b,E=e)B E0.05F0.90TP(J = True|A=a)A0.01F0.70TP(M = True|A=a)AWe would need 25entries to store the entire joint distribution table.But we need to store only 10 values by representing the dependencies between variablesInference• Any inference operation of the form P(values of some variables | values of the other variables) can be computed: Probability that both John and Mary call given that there was a burglar.BurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=True) = 0.001P(E=true) = 0.0020.001F F0.29F T0.94T F0.95T TP(A = True|B=b,E=e)B E0.05F0.90TP(J = True|A=a)A0.01F0.70TP(M = True|A=a)A7InferenceBurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=True) = 0.001P(E=True) = 0.0020.001F F0.29F T0.94T F0.95T TP(A = True|B=b,E=e)B E0.05F0.90TP(J = True|A=a)A0.01F0.70TP(M = True|A=a)A∑∑==BYBMJXYPXPBPBMJPBMJPcontain that entries All^^contain that entries All)()()(),,()|,(InferenceBurglaryEarthquakeJohnCallsMaryCallsAlarmP(B=True) = 0.001P(E=true) = 0.0020.001F F0.29F T0.94T F0.95T TP(A = True|B=b,E=e)B E0.05F0.90TP(J = True|A=a)A0.01F0.70TP(M = True|A=a)A∑∑==BYBMJXYPXPBPBMJPBMJPcontain that entries All^^contain that entries All)()()(),,()|,(We know how to compute these sums because we know how to compute the joint as written, we still need to compute most of the entire joint table8Bayes Net: Formal Definition• Bayes Net = directed acyclic graph represented by:– Set of vertices V– Set of directed edges E joining vertices. No cycles are allowed.• With each vertex is associated:– The name of a random variable– A probability distribution table indicating how the probability of the variable’s values depends on all the possible combinations of values of its parentsBayes Net: Formal Definition• Bayes Net = directed acyclic graph represented by:– Set of vertices V– Set of directed edges E joining vertices. No cycles are allowed.• With each vertex is associated:– The name of a random variable– A probability distribution table indicating how the probability of the variable’s values depends on all the possible combinations of values of its parentsBayes Nets are also called Belief NetworksThe tables associated with the vertices are called Conditional Probability Tables (CPT)All the definitions can be extended to using continuous random variables instead of discrete variables9Bayes Net Construction• Choose a set of variables and an ordering {X1,..,Xm}• For each variable Xifor i = 1 to m:1. Add the variable Xito the network2. Set Parents(Xi) to be the minimal subset of {X1,..,Xi-1} such that Xiis conditionally independent of all the other members of {X1,..,Xi-1} given Parents(Xi)3. Define the probability table describing P(Xi| Parents(Xi))Bayes Net Construction• Choose a set of
View Full Document
Unlocking...