Artificial Intelligence

Assigned:
Tue Sep 21

Due: Thu Oct 7

In this assignment, you will build
several Bayesian networks and explore inference algorithms described in
the text.

### Part 1

Let's revisit the Wumpus world we considered in Assignment 3.

(a) Draw a Bayesian net that represents the dependencies between the two cells at which breezes have been observed (B_{23} = true, B_{43}
= true), and the pits that could be responsible for the breezes (P_{13},
P_{24}, P_{33}, and P_{44}).

(b) Write out the conditional probability tables necessary to characterize this domain. If you've done it right, there should be one table for every variable, including the variables that have no ancestors.

(c) Using this network, write out the formula for P(P_{13} | b_{23},
b_{43}) in terms of the conditional-probability tables you have
created. If you have nested summations, be sure to move terms as
far to the left as possible.

(d) Using either variable elimination or enumeration, compute P(P_{13}
| b_{23}, b_{43}).

### Part 2

Consider the following network of binary random variables:

This network represents dependencies between:

* a student being exhausted (Exhausted)

* a student partying the night before (Party)

* a student being overworked (Overworked)

* it is the day following a football game (Football)

* it is the day following a holiday (Holiday)

* the student is working on senior project (Sr.Project)

* it is around the time of midterm exams (Midterm)

(a) Assume that Party, Overworked, and Exhausted are noisy-OR functions of their parents. Specify the conditional probability tables for noisy-OR given the effect probabilities specified on the graph. For example, Football=true alone has a .6 probability of resulting in Party=true, i.e., P(p | f, ¬h) = 0.6.

(b) Compute P(m | ¬f, ¬h, e), i.e., the probability that it is midterm time given that the student is exhausted, and there has not been a football game or holiday. To perform this computation, you require the conditional-probability tables you made in (a), along with prior probabilities of the four top nodes, given in the diagram.

### Part 3

For this part of the homework, use the Cloudy-Rain-Sprinkler-WetGrass
network in Figure 14.11.

(a) using the enumeration technique, compute P(cloudy | sprinkler, wetgrass).

(b) Write a program that estimates the same conditional probability using likelihood weighting. Your program does not have to be general: It can be specific to this network and to this query. Your program should take one input N, the number of samples used to construct the estimate (same N as the text uses). You should run the program M times, allowing you to compute a mean and variance of the conditional probability estimate for a given value of N.

Run the program M=1000 times for N=10, 100, 1000, 5000. Report the mean and variance for each value of N. If your code is working right, the variance in the estimate should decrease as N increases.

### Part 4

Design a Bayes net for a problem of your own choosing. The
network should have at least 5 nodes. Preferably, the network
should not be a polytree (i.e., it should have some undirected loops),
and/or some continuous random variables. To give you some
inspiration, think about problems involving diagnosis, where you are presented
with some symptoms and want to infer the underlying causes (e.g.,
automobile breakdowns, medical diagnosis).

(a) List your random variables, explain the meaning of each, and specify the conditional probability distributions of the network (including the priors for the variables without parents).

(b) use MCMC to simulate the network and perform some interesting sort of inference. As in Part 3, you do not have to write general code: The code can be specific to your network and your query.

4 |
||||

3 |
OK breeze |
OK breeze |
||

2 |
OK |
OK |
||

1 |
OK |
OK |
OK |
OK |

1 |
2 |
3 |
4 |

(a) Draw a Bayesian net that represents the dependencies between the two cells at which breezes have been observed (B

(b) Write out the conditional probability tables necessary to characterize this domain. If you've done it right, there should be one table for every variable, including the variables that have no ancestors.

(c) Using this network, write out the formula for P(P

(d) Using either variable elimination or enumeration, compute P(P

This network represents dependencies between:

* a student being exhausted (Exhausted)

* a student partying the night before (Party)

* a student being overworked (Overworked)

* it is the day following a football game (Football)

* it is the day following a holiday (Holiday)

* the student is working on senior project (Sr.Project)

* it is around the time of midterm exams (Midterm)

(a) Assume that Party, Overworked, and Exhausted are noisy-OR functions of their parents. Specify the conditional probability tables for noisy-OR given the effect probabilities specified on the graph. For example, Football=true alone has a .6 probability of resulting in Party=true, i.e., P(p | f, ¬h) = 0.6.

(b) Compute P(m | ¬f, ¬h, e), i.e., the probability that it is midterm time given that the student is exhausted, and there has not been a football game or holiday. To perform this computation, you require the conditional-probability tables you made in (a), along with prior probabilities of the four top nodes, given in the diagram.

(a) using the enumeration technique, compute P(cloudy | sprinkler, wetgrass).

(b) Write a program that estimates the same conditional probability using likelihood weighting. Your program does not have to be general: It can be specific to this network and to this query. Your program should take one input N, the number of samples used to construct the estimate (same N as the text uses). You should run the program M times, allowing you to compute a mean and variance of the conditional probability estimate for a given value of N.

Run the program M=1000 times for N=10, 100, 1000, 5000. Report the mean and variance for each value of N. If your code is working right, the variance in the estimate should decrease as N increases.

(a) List your random variables, explain the meaning of each, and specify the conditional probability distributions of the network (including the priors for the variables without parents).

(b) use MCMC to simulate the network and perform some interesting sort of inference. As in Part 3, you do not have to write general code: The code can be specific to your network and your query.