Description
CS 440: INTRO TO ARTIFICIAL INTELLIGENCE
PART A.
Question 1: [10 points] Consider the following Bayesian network, where variables A through E
are all Boolean valued:
a) What is the probability that all five of these Boolean variables are simultaneously true?
[Hint: You have to compute the joint probability distribution (JPD). The structure of the
Bayesian network suggests how the JPD is decomposed to the conditional probabilities available.]
b) What is the probability that all five of these Boolean variables are simultaneously false?
[Hint: Answer similarly to above.]
c) What is the probability that A is false given that the four other variables are all known to be
true?
[Hint: Try to use the definition of the conditional probability and the structure of the network.
For probabilities that can not be computed directly from the network, remember the following normalization trick: if P() = α · ƒ () and P(¬) = α · ƒ (¬), then you can compute the
normalization factor as α =
1.0
ƒ ()+ƒ (¬)
, since P() + P(¬) = 1.0.]
Question 2: [10 points] 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(Brgry|JohnsCs = tre, MryCs = tre)
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 enumeration algorithm.
c) Suppose a Bayesian network has the from of a chain: a sequence of Boolean variables
X1, . . . Xn where Prents(X) = {X−1} for = 2, . . . , n. What is the complexity of computing P(X1|Xn = tre) using enumeration? What is the complexity with variable elimination?
Question 3: [15 points]
In this problem, you will implement two kinds of sampling techniques (rejection sampling and
likelihood weighting) to perform approximate inference on the given Bayesian network.
a) Compute the probabilities of P(d|c), P(b|c), and P(d|¬, b) by enumeration. Then, employ
rejection sampling and likelihood weighting to approximate them. Use 1000 samples, and
document your results. How do the approximations and the actual values compare?
b) Next, we focus on P(d|c). We know that the accuracy of the approximation depends on the
number of samples used. For each of the sampling methods, plot the probability as a function
of the number of samples used. Do you notice large divergences in the convergence rates
among the methods?
c) Construct a query on this Bayes Net such that the convergence and effectiveness of rejection
sampling is noticeably worse than that of likelihood weighting List the query you are using,
and provide the probability plot as a function of samples used. Why is it the case that rejection
sampling is noticeably worse for this query?
Question 4: [15 points]
You are an interplanetary search and rescue expert who has just received an urgent message:
a rover on Mercury has fallen and become trapped in Death Ravine, a deep, narrow gorge on the
borders of enemy territory. You zoom over to Mercury to investigate the situation. Death Ravine
is a narrow gorge 6 miles long, as shown below. There are volcanic vents at locations A and D,
indicated by the triangular symbols at those locations.
[3pts] (b) Estimate the expectation E[f(X, Y, Z)|Y = 0, Z = 1] using two samples obtained using likelihood-weighting. Show
your work. Reuse the sequence {ai}1≤i≤15 (starting with a1) as a source of randomness.
3 [6 pts] HMM: Search and Rescue
You are an interplanetary search and rescue expert who has just received an urgent message: a rover on Mercury
has fallen and become trapped in Death Ravine, a deep, narrow gorge on the borders of enemy territory. You zoom
over to Mercury to investigate the situation. Death Ravine is a narrow gorge 6 miles long, as shown below. There
are volcanic vents at locations A and D, indicated by the triangular symbols at those locations. A B C F D E
! !
The rover was heavily damaged in the fall, and as a result, most of its sensors are broken. The only ones still functioning are its thermometers, which register only two levels: hot and cold. The rover sends back evidence E = hot
when it is at a volcanic vent (A and D), and E = cold otherwise. There is no chance of a mistaken reading. The rover
fell into the gorge at position A on day 1, so X1 = A. Let the rover’s position on day t be Xt ∈ {A, B, C, D, E, F}.
The rover is still executing its original programming, trying to move 1 mile east (i.e. right, towards F) every day.
However, because of the damage, it only moves east with probability 0.5, and it stays in place with probability 0.5.
Your job is to figure out where the rover is, so that you can dispatch your rescue-bot.
(a) (2 pt) Three days have passed since the rover fell into the ravine. The observations were (E1 = hot, E2 = cold,
E3 = cold). What is P(X3|hot1, cold2, cold3), the probability distribution over the rover’s position on day 3, given
the observations?
You decide to attempt to rescue the rover on day 4. However, the transmission of E4 seems to have been corrupted,
and so it is not observed.
(b) (2 pt) What is the rover’s position distribution for day 4 given the same evidence, P(X4|hot1, cold2, cold3)?
(c) (2 pt) All this computation is taxing your computers, so the next time this happens you decide to try approximate inference using particle filtering to track the rover. If your particles are initially in the top configuration shown
below, what is the probability that they will be in the bottom configuration shown below after one day (after time
elapses, but before evidence is observed)?
!
A B C F D E
! !
A B C F D E
!
4
The rover was heavily damaged in the fall, and as a result, most of its sensors are broken.
The only ones still functioning are its thermometers, which register only two levels: hot and cold.
The rover sends back evidence E = hot when it is at a volcanic vent (A and D), and E = cold
otherwise. There is no chance of a mistaken reading. The rover fell into the gorge at position A
on day 1, so X1 = A. Let the rover’s position on day t be Xt ∈ {A, B, C, D, E, F}. The rover is still
executing its original programming, trying to move 1 mile east (i.e. right, towards F) every day.
However, because of the damage, it only moves east with probability 0.80, and it stays in place
with probability 0.20. Your job is to figure out where the rover is, so that you can dispatch your
rescue-bot.
a) Filtering: Three days have passed since the rover fell into the ravine. The observations were
(E1 = hot, E2 = cold, E3 = cold). What is P(X3 | hot1, cold2, cold3), the probability distribution
over the rover’s position on day 3, given the observations? (This is a probability distribution
over the six possible positions).
b) Smoothing: What is P(X2 | hot1, cold2, cold3), the probability distribution over the rover’s
position on day 2, given the observations? (This is a probability distribution over the six
possible positions).
c) Most Likely Explanation: What is the most likely sequence of the rover’s positions in the three
days given the observations (E1 = hot, E2 = cold, E3 = cold)?
d) Prediction: What is P(hot4, hot5, cold6 | hot1, cold2, cold3), the probability of observing hot4
and hot5 and cold6 in days 4,5,6 respectively, given the previous observations in days 1,2,
and 3? (This is a single value, not a distribution).
e) Prediction: You decide to attempt to rescue the rover on day 4. However, the transmission
of E4 seems to have been corrupted, and so it is not observed. What is the rover’s position
distribution for day 4 given the same evidence, P(X4 | hot1, cold2, cold3)?
The same thing happens again on day 5. What is the rover’s position distribution
