Computer Science 242Homework 4The 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
Part I: Exact InferenceFor 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:
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 trueThat is, load the network from the XMLBIF file aima-alarm.xml, the query variable is 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.xmlAn 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 InferenceFor 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:
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 trueThis specifies 1000 samples be used for the run. The distribution of the random variable
Part III: EvaluationWe are providing three XML format Bayesian networks:
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.
READMEFor 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
SubmissionDue by TURN_IN script by 5pm, Fri 4/12. |