CSE151
Programming Assignment 1

Inference in Bayesian Networks

Due: April 15th, 2004

RULES:
- The programs must be written in Matlab
- Programs must be submitted using the turnin procedure by 11:59pm on the due date
- You may work in groups of two or three
- Turn in a writeup and all the source files (see what to turn in below)
- You may NOT use the Bayes net package for matlab for this assignment
- Follow the specifications exactly!  If the assignment says write a function called "enumeration" in a file called "enumeration.m" make sure that you do exactly this.  This will make the grading go more quickly and make the TA happy :)
- Similarly, make sure your function is the same as the prototypes provided in the specification.
- Make sure to comment your code!  This means have comments describing each function as well as comments throughout the code.

Introduction:
In this assignment, you and your partner will  implement two inference methods for boolean  Bayesian  networks:  one exact inference method, inference by enumeration, and one sampling method, likelihood weighting.  Both of these algorithms are described in Chapter 14.  We will only be doing boolean, single variable inference.

Inference by enumeration:
Write a function called "enumeration" in a file called "enumeration.m".  This function should implement the exact inference by enumeration algorithm.  The following is the function prototype you should use:

function result = enumeration(x, x_val, e, e_vals, bn_filename)
% x: a string containing a single query variable.  For example, 'a'.
% x_val: the value of x to be queried, 0 or 1.
% e: a cell array of strings containing evidence variables.  For example, {'b' 'e'}
% e_vals: a cell array of integers containing the values (0 or 1) assigned to the evidence variabls.
%   for example, {1 0}
% bn_filename: the bayesian network specified in the appropriate format
% returns the p(x = x_val | e = e_vals) based on the bayesian network
%
% For example, to query the p( burglary | johnCalls, maryCalls ), the call is as follows:
%  enumeration('b', 1, {'j' 'm'}, {1 1}, 'alarm.txt')

Example run:
% p(burglar = true|JohnCalls = true, MaryCalls = true)

>> enumeration('b', 1, {'j', 'm'}, {1, 1}, 'alarm.txt')

ans =

    0.2842


Sampling using likelihood weighting:
Write a function called "likelihood_weighting" in a file called "likelihood_weighting.m".  This function should implement the likelihood weighting algorithm given in the text.  The following is the function prototype you should use:

function result = likelihood_weighting(x, x_val, e, e_vals, n, bn_filename)
% x: a string containing a single query variable.  For example, 'a'
% x_val: the value of x to be queried, 0 or 1.
% e: a cell array of strings containing evidence variables.  For example, {'b' 'e'}
% e_vals: a cell array of integers containing the values (0 or 1) assigned to the evidence variables.
%   for example, {1 0}
% n: the number of samples to generate
% bn_filename: the bayesian network specified in the appropriate format
% returns the p(x = xval | e = e_vals) based on the bayesian network using likelihood weighting
%
% For example, to query the p( burglary | johnCalls, maryCalls ), the call is as follows:
%  enumeration('b', 1, {'j' 'm'}, {1 1}, 100, 'alarm.txt')

Example runs:
% p(rain = true | sprinkler = true )

>> likelihood_weighting('r', 1, {'s'}, {1}, 1000, 'weather.txt')

ans =

    0.2959

>> likelihood_weighting('r', 1, {'s'}, {1}, 1000, 'weather.txt')

ans =

    0.2978


Input file format:
The input file consists of a line for each node in the network.  Each node has three different values: the label, the parents and the conditional probability table (cpt).  The label is just an arbitrary string.  The parents are listed separately, with each parent separated by a space.  The whole set of parents should be double quoted.  The cpt is specified with each entry separated by a space and the whole list double quoted.  If we let false be '0' and true be '1', you can view the assigned parent values in a cpt table as a binary number.  For example, "T F T" is "1 0 1" or 5.  In the file, the values for a table should be listed in ascending order, i.e. from all false (or 0) to all true.  The alarm cpt is shown below as it would for the input file:

a "b e" ".001 .29 .94 .95"

We have included input files for both the alarm problem as well as the weather problem, but try creating your own files as well.

What to turn in:
- A zip file with...
- All of your commented matlab code.
- A text writeup less than 2 pages long (be as concise as possible) which should include:
  - A brief analysis of the problem being solved and the solutions programmed
  - A very brief overview of the code
  - Any special features added
  - Any known bugs
  - Example runs of your programs on various data sets (***including one new one that you came up with)
  - A separate paragraph by each team member stating:
	what that team member contributed to the project.
	what that team member learned from the project.


HINTS!
- We have included a file "read_bn_file.m" that read in a bayes net files and returns a good representation.  This should save you a lot of time.  Feel free to write your own if you don't like this one.  The function returns a n x 3 cell array where n is the number of nodes.  Read in one of files and print out the result to get a better feeling for what this function returns.
- Make sure to write extra helper functions where necessary.  For example, a useful function might calculate the probability of a variable given it's parents... or similarly, a variable given the evidence variables.
- Be careful about the order in which you process nodes.  Depending on how you implement it, you may need to do a topological sort of the graph to make sure that the parents are always defined before the child.
- Read the bulletin board regularly for answers to common questions.
- When you're done, run your program on a variety of different problems and make sure that the answers make sense.  Check simple inputs like empty evidence, etc.