Computer Science 242

Homework 4

The assignment is to implement both exact and approximate inference for Bayesian networks.

This project is more open-ended than the previous assignments. We expect you to experiment with different algorithms and configurations on your own, and to write up the results. You may work in groups of up to three for this project. There is no specified output format or auto checker script.

Background

Recall that a Bayesian network is directed acyclic graph whose vertices are the random variables $\{X\}\cup \mathbf{E} \cup \mathbf{Y}$, where

  • $X$ is the query variable
  • $\mathbf{E}$ are the evidence variables
  • $\mathbf{e}$ are the observed values for the evidence variables
  • $\mathbf{Y}$ are the unobserved (or hidden) variables
The inference problem for Bayesian Networks is to calculate $\mathbf{P}(X \,\vert\,\mathbf{e})$, that is, the conditional distribution of the query variable given the evidence (observed values of the evidence variables). In other words, compute the probability of each possible value of the query variable, given the evidence.

Part I: Exact Inference

For the first part of the project, you must implement the “inference by enumeration” algorithm described in AIMA Section 13.3. Pseudo-code for the algorithm is given in Figure 13.11. Section 13.3.2 suggests some speedups for you to consider.

Your implementation must be able to handle different problems and queries. For exact inference, your program must accept the following arguments on the command-line:

  • The filename of the XMLBIF encoding of the Bayesian network. You may assume that these filenames will end in “.xml”.
  • The name of the query variable, matching one of the variables defined in the file.
  • The names and values of evidence variables, again using names and domain values as defined in the file.

So for example, if this was a Python program, you might have the following to invoke it on the alarm example: 

    python mybninferencer.py aima-alarm.xml B J true M true
That is, load the network from the XMLBIF file aima-alarm.xml, the query variable is $B$, and the evidence variables are $J$ with value $\mathit{true}$ and $M$ also with value $\mathit{true}$.

You may use standard libraries to parse xml. An example python program that reads in the XMLBIF format is in the class directory: 

    /u/cs242/hw4/read.py /u/cs242/hw4/nets/aima-alarm.xml
An example java program to read the XML file:q /u/cs242/hw4/read.py /u/cs242/hw4/nets/aima-alarm.xml 
    java -cp /u/cs242/hw4 XMLBIFParser /u/cs242/hw4/nets/aima-alarm.xml

The output of your program should be the posterior distribution of the query variable given the evidence. That is, print out the probability of each possible value of the query variable given the evidence.

Your writeup and/or README must make it very clear how to run your program and specify these parameters. If you cannot make them work as described above, you should check with the TAs before the deadline and explain the situation if for some reason it can't be resolved.

Part II: Approximate Inference

For the second part of the project, you need to implement at least one of the approximate inference techniques for Bayesian networks as discussed in class (and in the textbook) The algorithms you may choose are:

  1. Rejection sampling
  2. Likelihood weighting
  3. Gibbs sampling

For running these approximate inferencers, you need to specify the number of samples to be used for the approximation. This should be the first parameter to your program. For example: 

    % java MyBNApproxInferencer 1000 aima-alarm.xml B J true M true
This specifies 1000 samples be used for the run. The distribution of the random variable $B$ will be printed at the end of the run. If you need additional parameters, document their use carefully.

Part III: Evaluation

We are providing three XML format Bayesian networks:
  1. aima-alarm.xml
  2. aima-wet-grass.xml
  3. dog-problem.xml
in /u/cs242/hw4/nets.

You should use these sample networks to test your code. The Alarm and WetGrass networks may be particularly helpful, as there are worked examples in the textbook and in the slides. In your writeup, you must quantify how many samples are necessary for your sampling algorithm to be within 1% of the exact value. Note that the number of samples will depend on the specific topology of the network; choose your own queries, evidence, and network and record your choices in your writeup.

README

For the algorithms that you implement, explain your design and implementation briefly, and evaluate the results as previously mentioned.

Additional general requirements for writeups are the same as for previous projects, as described below.

Rubric

  • 25% – XMLBIF parsing and network representation.
  • 25% – Exact Inference
  • 25% – Sampling
  • 25% – Writeup and Experimental Work

Submission

Due by TURN_IN script by 5pm, Fri 4/12.