CSE 4308/5360 - Assignments - Written Assignment 5

Questions 1-6 refer to the Bayesian network in Figure 1. Questions 7 and 8 refer to the Bayesian network in Figure 2.



Figure 1: A Bayesian network graph establishing relations between various car problems and their causes.

Problem 1

On the network shown in Figure 1, consider the event E = "battery age is less than three years". Let A = P(E | "battery dead"=true AND "no oil"=true) and B = P(E | "battery dead"=true AND "no oil"=false). Which of the following three cases can possibly be true: A > B, A = B, or A < B? Why?

Answer: A = B, because the "battery age" variable and the "no oil" variable are conditionally independent given the value for the "battery age" variable.

Problem 2

On the network shown in Figure 1, consider again the event E = "battery age is less than three years". Let A = P(E | "battery dead"=true AND "no oil"=true) and B = P(E | "battery dead"=true AND "starter broken"=true). Which of the following three cases can possibly be true: A > B, A = B, or A < B? Why?

Answer: A = B, because the "battery age" variable and the "no oil" variable are conditionally independent given the value for the "battery age" variable, and the "battery age" variable and the "fanbelt broken" variable are also conditionally independent given the value for the "battery age" variable. Both A and B are equal to P(E | "battery dead" = true).

Problem 3

The "alternator broken" event and the "fanbelt broken" event are both causes of the "no charging event." Let A = P("alternator broken"=true | "no charging"=true) and B = P("alternator broken"=true | "no charging"=true AND "fanbelt broken"=true). Which of the following three cases do you expect to be true: A > B, A = B, or A < B? Why?

Answer: A > B. Since "alternator broken" and "fanbelt broken" are both causes of "no charging", given "no charging"=true, knowing that one cause is true makes the other cause less likely.

Problem 4

On the network shown in Figure 1, the "no gas" event is a cause of the "car won't start" event. Let A = P("no gas"=true) and B = P("no gas"=true | "car won't start"=true). Which of the following three cases do you expect to be true: A > B, A = B, or A < B? Why?

Answer: A < B. Since "no gas" is a cause of "car won't start", given "car won't start"=true, the cause for that becomes more likely.

Problem 5

On the network shown in Figure 1, suppose that: What is P("no charging"=false)? How is it derived?

Answer: We use the following abbreviations: 

ncf stands for "no charging = false"
abt stands for "alternator broken = true"
abf stands for "alternator broken = false"
Using the above abbreviations, we have: 
P(ncf) = P(ncf | abt) * P(abt) + P(ncf | abf) * P(abf) 
= 0.05 * 0.02 + 0.99 * 0.98 = 0.9712

Problem 6

Suppose that: What is P("battery age" <= 3 years | "battery dead"=true)? How is it derived?

Answer: We use the following abbreviations: 

ba3 stands for "battery age <= 3 years"
ba4 stands for "battery age > 3 years"
bdt stands for "battery dead = true"
Using the above abbreviations, we have: 
P(ba3 | bdt) = P(bdt | ba3) * P(ba3) / P(bdt) = 0.02 * 0.7 / P(bdt)

P(bdt) = P(bdt | ba3) * P(ba3) + P(bdt | ba4) * P(ba4) 
= 0.02 * 0.7 + 0.1 * 0.3 = 0.044
Consequently, P(ba3 | bdt) = P(bdt | ba3) * P(ba3) / P(bdt) = 0.02 * 0.7 / 0.044 = 0.318.



Figure 2: A Bayesian network establishing relations between events on the burglary-earthquake-alarm domain, together with complete specifications of all probability distributions.

Problem 7

On the network shown in Figure 2, what is the probability of the following event: burglary=false AND earthquake=true AND alarm=false AND JohnCalls=true AND MaryCalls=false.

Answer: We use the following abbreviations: 

bf stands for "burglary = false"
et stands for "earthquake = true"
af stands for "alarm = false"
jt stands for "JohnCalls = true"
mf stands for "MaryCalls = false"
Using the above abbreviations, we have: 
P(bf, et, af, jt, mf) = P(bf) *  P(et) * P(af | bf, et) * P(jt | af) * P(mf | af)
= (1 - 0.001) * 0.002 * (1 - 0.29) * 0.05 * (1-0.01) = 7.022 * 10-5

Problem 8

On the network shown in Figure 2, what is the probability of the following event: earthquake=true AND alarm=false AND JohnCalls=true AND MaryCalls=false.

Answer: We use the following abbreviations: 

bf stands for "burglary = false"
bt stands for "burglary = true"
et stands for "earthquake = true"
af stands for "alarm = false"
jt stands for "JohnCalls = true"
mf stands for "MaryCalls = false"
Using the above abbreviations, we have: 
P(et, af, jt, mf) = P(bf, et, af, jt, mf) + P(bt, et, af, jt, mf) 
= P(bf) *  P(et) * P(af | bf, et) * P(jt | af) * P(mf | af) + P(bt) *  P(et) * P(af | bf, et) * P(jt | af) * P(mf | af)
= (1 - 0.001) * 0.002 * (1 - 0.29) * 0.05 * (1-0.01) + 0.001 * 0.002 * (1 - 0.95) * 0.05 * (1-0.01)
= 7.022 * 10-5 + 4.95 * 10-9

Problem 9

Figure 3: A decision tree for estimating whether the patron will be willing to wait for a table at a restaurant.

Suppose that, on the entire set of training samples available for constructing the decision tree of Figure 3, 80 people decide to wait, and 20 people decide not to wait. What is the initial entropy at node A (before the test is applied)? Write an expression that fully specifies the answer numerically.

Answer: We denote by log2(x) the logarithm base 2 of x. Then: 

Entropy(A) = -80/100 * log2(80/100) - 20/100 * log2(20/100) = 0.7219

Problem 10

In the decision tree of Figure 3, node D uses the exact same test (whether it is weekend or not) as node A. What is the information gain, at node D, of using the weekend test? Justify your answer.

Answer: The information gain is 0, because all training examples at node D give the same answer (answer=yes) to the question of whether it is weekend.

Problem 11

Your boss at a software company gives you a binary classifier H that predicts, for any basketball game, whether the home team will win or not. Classifier H has a 28% accuracy, and your boss assigns you the task of improving that classifier, so that you get an accuracy that is better than 60%. How do you achieve that task?

Answer: Create a classifier H' that, for any basketball game, outputs the opposite of what H outputs. This is easy to do, since we are given classifier H, so we always know what H outputs. Then, the accuracy of H' will be 72%, more than the 60% we were asked to achieve.

Problem 12

You are a meteorologist that places temperature sensors all of the world, and you set them up so that they automatically e-mail you, each day, the high temperature for that day. Unfortunately, you have forgotten whether you placed a certain sensor S in Maine or in the Sahara desert (but you are sure you placed it in one of those two places) . The probability that you placed sensor S in Maine is 5%. The probability of getting a daily high temperature of 80 degrees or more is 20% in Maine and 90% in Sahara. Assume that probability of a daily high for any day is independent of the daily high for the previous day.

In the following questions, you do not have to perform all numerical calculations, but you have to fully specify the numerical value of each answer.

a. Given that the first e-mail you got from sensor S indicates a daily high under 80 degrees, what is the maximum likelihood estimate that sensor S is placed in Maine? Show how you derive your answer.

Answer: The ML estimate is that indeed the sensor S was placed in Maine, since that hypothesis (that the sensor was placed in Maine) maximizes the probability of the data: 

P(observation | Maine) = 0.8 > P(observation | Sahara) = 0.1

b. Given that the first e-mail you got from sensor S indicates a daily high under 80 degrees, what is the probability that the sensor is placed in Maine?

Answer: Let o1u80 stand for "first observation = daily high under 80 degrees". We first need to compute P(o1u80): 

p(o1u80) = p(o1u80 | Maine) * P(Maine) + p(o1u80 | Sahara) * P(Sahara) 
= 0.8 * 0.05 + 0.1 * 0.95 = 0.135
Then, we compute P(Maine | o1u80): 
p(Maine | o1u80) = p(o1u80 | Maine) * P(Maine) / P(o1u80) 
= 0.8 * 0.05 / 0.135 = 0.2963

c. Given that the first e-mail you got from sensor S indicates a daily high under 80 degrees, what is the probability that the second e-mail also indicates a daily high under 80 degrees?

Answer: We use these abbreviations:

Then, using the answer from Problem 4b, we compute P(o2u80 | o1u80): 
p(o2u80 | o1u80) = p(o2u80 | Maine, o1u80) * P(Maine | o1u80) + p(o2u80 | Sahara, o1u80) * P(Sahara | o1u80) 
= 0.8 * 0.2963 + 0.1 * (1 - 0.2963) = 0.3074