CS 151: Programming Assignment 4

Reasoning with Uncertainty [90 points]
due Wednesday, April 2 11:55pm


The purpose of this assignment is to program some of the bayes net inference algorithms that we have learned in class and to exercise your skills at building Bayes nets.  You will:
  1. Build a simple Bayes net
  2. Implement the variable elimination algorithm
  3. Implement rejection sampling for approximate inference
  4. Work with (and modify) a more complex Bayes net
  5. (Optional) Implement MCMC for approximate inference

This assignment is based in part on assignments from AI courses at Berkeley and Duke.

Part 0: Setup

You will need to install some software and download some files to get started on this assignment.

First, install Bayesian Networks for Java (BNJ), a bayes net simulation tool.  You can find BNJ here: http://bnj.sourceforge.net/.  This software should run on both PCs and Macs, but let me know if you have trouble.

Now, download the python starter code for this assignment, read it over, and make sure you have an idea of what's going on (more or less--it'll become more clear below).

a4code.zip

Part 1: [25 points] Creating a Simple Bayes Net

For this problem, you will use BNJ it to build your own network.  You will also find BNJ  helpful in the next part of the assignment to verify that you have implemented your algorithms correctly.

Create a Bayes net to represent the following (taken from an assignment from Berkeley's 2004 AI course):

Let Pass be a variable which has value true if a given student passes a given class, and false otherwise. Let us consider some of the factors useful for predicting if a student will pass, as seen from the point of view of the professor. The observable variables are the GPA in all previous classes (high, medium, or low), whether or not the student has taken the PreReqs (true or false), and whether or not the student is Asleep in class (true or false). There are also some relevant unobserved variables: whether the student is Smart, Studious, and pulls an AllNiter, and the student's WorkLoad. (It is up to you to choose the possible values of these unobserved variables.)

Question 1 (15 pts).Begin by using the procedure in Chapter 14 to design the topology of the network. Choose an ordering for the variables that reflects the causal processes in the domain, and try to avoid having nodes with too many parents. Design your network and briefly exaplain why you choose this topology.  You should also specify CPTs for each of the nodes in the network.

Question 2 (10 pts). Now enter your network into BNJ.  There are twelve possible cases for the three evidence variables. Use BNJ to compute the exact probability of Pass in each case, using your network. Check to see that these values look reasonable. If not, you may want to alter some of your conditional probabilities. You can do this using edit-cpt-row for each row you want to change. Include the final results and Bayes net with your writeup.

What to submit for part 1:

For part 1 of the assignment you should submit the following files:

Part 2: [65 points] Inference Algorithms and More Complex Networks

In this assignment we will be working with code that is built on the code from the book, however, you should use this code, NOT the code that came with the book.  Take a look at the probability.py file you downloaded above.  You will see a number of utility functions for working with probabilities, and some incomplete code that implements Bayesian networks.  Your task is to extend this code so that it allows the user to create and reason with Bayesian networks.  

The other files you downloaded include some sample Bayesian networks on which you will test your code (networks.py, insurance.bif and insurance.xml).  Place all of these files in the same directory with the code.   IMPORTANT: you will use the burglary network in the networks.py file, NOT the one that came with the original distribution of the code.  networks.py defines two networks in using the internal format that you will work with when writing your inference algorithms.  In a nutshell, a BayesNet object is just a list of BayesNetNodes and a list of evidence.  A BayesNetNode is a variable, a list of its parents, and a CPT that is represented as described in networks.py.  Make sure you are comfortable with the BayesNet reprensentation before you start coding.  You may modify this representation if  you think you need to or want to.

Do not trust any of the inference algoritms that came with the book's distribution of the code (specifically: enumerate_ask will not work in general, especially given the above network representation).  If you need to check your values, use BNJ.

Question 3 (35 points): Implement the variable elimination inference algorithm from Figure 14.10 in the book and test your results using the burglary network. You should name this function elimination_ask.  The function should take three arguments: a variable (a string--the variable's name), evidence (a dictionary that maps variable names to values), and a BayesNet object. It should return a probability distribution over the values for the query variable (represented as a dictionary).  Note that you have to extract the possible values for the query variable from the Bayes net.

Here's an example to illustrate the behavior of this function.  To answer the query P(Burglary|johncalled, marycalled) I would call:

>>> elimination_ask('Burgalry', {'JohnCalls': True, 'MaryCalls': True}, burglary)

And the function would return:

{True: 0.284, False: 0.716}

This step will take some thought.  You have to figure out how to create and manipulate the factors, etc.  Don't worry about finding an efficient variable ordering.

You will notice that there is already some code for this function in probability.py.  You should modify and extend what's there (or just delete it and start over if you want).

You should make sure that your function works correctly for a large number of network queries (you could feasibly test your function on all possible queries to the network if you wanted to by writing a function to enumerate them all.)  You can verify that your results are correct by comparing them to the values produced by BNJ.

WARNING: START EARLY AND PLAN OUT YOUR DATA STRUCTURES CAREFULLY.  THIS PART IS NOT EASY.

Question 4 (15 points): Implement the rejection sampling algorithm for appoximate inference from figure 14.13.   This function takes 4 arguments: the query variable, the evidence (a dictionary), a Bayes net object, and the total number of samples to be generated.  I.e.,

>>> rejection_sampling_ask('Burglary',  {'JohnCalls': True, 'MaryCalls': True}, burglary, 1000)

Again, there is skeleton code for part of this function, but you will need to expand it and fill it in.

This function will be harder to test because it is not guarneteed to give the correct values for the posterior distributions. However,  you should be careful to ensure that your algorithm is functioning correctly before moving on to the next part.

Question 5 (15 points): This question asks you to examine how well rejection sampling works for various networks.  To get a more quantitative idea of how well various sampling algorithms work, we will need to instrument them to enable measurement of the error with respect to the true probability distribution as a function of the number of samples. Write a modified version of rejection_sampling_ask called
(recording_RS_ask Xname E bn iterations interval runs true-distribution file). The idea is that after every interval iterations (but not after 0 iterations) the current distribution for X is compared to the true distribution. Accumulate a dictionary that associates the number of iterations with the squared error (you will need to write a squared error function--it's not hard). Repeat the process several times, as specified by the runs argument, and average the results. At the end, you should have a dictionary with the mean squared error at each interval point, sorted by number of iterations. Write these results to a file. Do as many runs and iterations as you can reasonably manage. [Hint: beware of dividing by zero in rejection-sampling! Consider how to define the error when no samples survive the rejection process.]

Now use your functions to analize the burglary network and the insurance network (attached to this assignment).  Plot the squared error for Burglary given JohnCalls and MaryCalls.  (After you have generated the results file, use any graphing software you would like--Excel, Gnuplot, etc).  Then repeat this process for two distinct queries (i.e., a configuration of evidence and a query varaible) of your choosing on the insurance network.  You can use the insurance.xml file attached to this email to load the network into BNJ to get the true value for your query variable. Include your graphs in your writeup.  You should also comment on your results.  Which configurations converge to the true distribution faster?  Why do you think this is?  

What to submit for part 2:

For part 2 of the assignment you should submit the following files:
Extra Credit (10 points): Implement the MCMC or the likelihood weighting sampling algorithm and analize the performace of these algorithms as you did in Q5.  Compare these results to your results from rejection sampling.