# CSCI 3202 Artificial Intelligence

## Assignment 4

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.

 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 (B23 = true, B43 = true), and the pits that could be responsible for the breezes (P13, P24, P33, and P44).

(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(P13 | b23, b43) 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(P13 | b23, b43).

### 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.