CS440-Assignment 4 Solved

Problem 1 [Marie is getting married tomorrow at an outdoor ceremony in NYC. In recent years, it rained about once every three days. The weatherman has predicted there will be no rain for tomorrow. When it actually rains, the weatherman correctly forecasts rain 80% of the time. When it doesn't rain, he incorrectly forecasts rain 20% of the time. What is the probability that it will rain on the day of Marie's wedding according to Bayes' rule?

Problem 2 Consider the Monty Hall problem that we discussed in class. Instead of having three doors with one door having a price, now suppose there are four doors with two doors hiding goats behind them and one door having a price behind it. The other door has nothing behind it. To play the game, the guest will pick a door and the host will then reveal another door with a goat behind. The guest can then choose whether to stick to the original choice or switching. Should the guest switch? What is the probability of winning if the guest switches?

Problem 3 Using the sampling procedure covered in class and python (or any other way you see fit), generate N samples for the cumulative distribution function

1     sign(x) . 1             2.2

4)(x) = — +______ V1 —e 7, .

2

2

sign(x) is the sign of x, e.g., sign(-1.6) = 1, sign(5.3) = 1, and sign(0) = 0. Discard any sample if Ix' 5. Plot a histogram of your data from —5 to 5 with 0.2 increments (i.e., you should have 50 bins). Do this for N = 100, 200, 500, and 1000. You should submit four figures. Note that you can easily do histograms in python using matplotlib. (Hint: it can be slightly tricky to compute x from the CDF; but you don't need to).

Problem 4 . Consider the following Bayesian network, where variables A through E are all Boolean valued:

P(A=true)= 0.2 P(B=true)=0 .5 P(C=true)=0 .8





 
 


A
B
P(D=true I A,B)
F
F
0.9
F
T
0.6
T
F
0.5
T
T
0.1
 
 


B
C
P(E=true I B ,C)
F
F
0.2
F
T
0.4
T
F
0.8
T
T
0.3
 
 

a) What is the probability that all five of these Boolean variables are true?

b)  Compute P(A, E I B).

c)   Compute P(A = true I B = false, C = false, D = false, E = false).

d)  Compute P(C = true, D = false I B = false).

e)  Compute P(B = true, C = false, D = true I A = false).

Problem 5. For this problem, check the Variable Elimination algorithm in your book. Also consider the Bayesian network from the "burglary" example.

a)   Apply variable elimination to the query: P(BurglarylJohnsCalls = true, MaryCalls = true)

and show in detail the calculations that take place. Use your book to confirm that your answer is correct.

b)   Count the number of arithmetic operations performed (additions, multiplications, divisions), and compare it against the number of operations performed by the tree enumera­tion algorithm.

c)  Suppose a Bayesian network has the from of a chain: a sequence of Boolean variables Xi, ... Xn, where Parents(Xi) = {Xj_1} for i = 2, ... , n. What is the complexity of computing P(Xi IXn = true) using enumeration (in Big 0 notation)? What is the complexity with variable elimination?