CSE443 Reasoning Under Uncertainty

Assignment 2, 2001

www.csse.monash.edu.au/~annn/443/Ass2.html

Due date (Parts A-C): Friday 10 August, 11am (to me in class)

Due date (Part D): Friday 17 August, 4pm (in my mailbox)

This assignment is worth 20% of your final mark for this subject. I expect each student to spend no more than 15 hrs completing this assignment, though be warned that it is easy to spend more time playing around with your networks. The work you submit should be done on your own.

Belief Network Software

This assignment involves using the Netica (http://www.norsys.com) belief network package to develop models for uncertain reasoning.

This package can be downloaded and installed from the Internet. Note that we have a Monash Educational Site License for Netica. When you first download and run a copy of Netica, you will be asked for a license password to run it in more than Demo mode. (Demo mode does not allow you to save files of more than 15 nodes). The password is available from the lecturer. A Postscript version of the Netica manual is available here. I will also make 2 copies of the manual available in the Honours lab.

The latest version of Netica 2.06 is already installed on the Honours lab machines. If you wish to install on your machine at home, please note that the web site download only gives version 1.12. Once you have done the full Netica installed, you should download separately version 2.06 executable. It is a pre-release version, but is reasonable stable and bug-free. It is available from the Norsys ftp site as file ver206.zip. Point your browser to ftp://norsys.com/pub/users/norsys/dl: or ftp to norsys.com, login as anonymous and cd pub/users/norsys/dl. This only has the .exe file, and no help files or examples, so you should place it in the same folder as Netica.exe of the regular full download (moving the old Netica.exe out, or renaming it).

Note: All questions in the assignment sections below that require an answer, should be answered in a single separate README file.


PART A: The Case of the Missing Car (20 marks)

John and Mary Nguyen arrive home after a night out to find that their second car is not in garage. Two explanations occur to them: either the car has been stolen or their daughter Sam has borrowed the car without permission. The Nguyens know that the rate of car theft in their area is about 1 in 2000 each day, and that if the car was stolen, there is a 95% chance that the garage will show signs of forced entry. (There is nothing else worth stealing in the garage, so assume that if the car isn't stolen, the garage won't show signs of forced entry.) The Nguyens also know that Sam borrows the car without asking about once a week, and that Sam has a busy social life, so even if she didn't borrow the car, there is a 50% chance that she is out.
  1. Construct a Belief Network using BN software to represent and draw inferences about the case of the missing car.
  2. Show the belief of the each variable before adding any evidence (Save in A1). Which nodes in your network are d-separated when there is no evidence added?
  3. Add the evidence about the car being missing. After doing belief updating on the network, what are the Nguyen's beliefs that the car has been stolen? (Save in A2)
  4. After noticing the car is missing, suppose that Mary Nguyen checks the garage and doesn't find any sign of forced entry. What effect does this have on her belief that the car was stolen, that Sam borrowed the car, and that Sam will be home ? (Save in A3) Explain your answer in terms of diagnostic, causal and intercausal reasoning.
  5. With these two pieces of evidence in your network, which pairs of nodes are d-separated?
  6. Netica performs inference using a version of the Jensen join-tree algorithm. Does the software package allow you to look at the constructed join-tree? If so, what is the complexity of the join-tree? Can you reconstruct the steps taken to construct it?

PART B: Model your own problem (20 marks)

Think of your own problem involving reasoning with evidence and uncertainty.
  1. Write down an English description of the problem (in README file), then model it using a Belief Network. Your network should have between 8 and 15 nodes, and it should be multiply connected (i.e. not a tree or a polytree).
  2. Show the beliefs for each node in the network before any evidence is added. (Save in B1)
  3. Which nodes are d-separated with no evidence added?
  4. Which nodes in your network would be considered evidence (or observation) nodes? Which might be considered the query nodes? (Obviously this depends on the domain and how you might use the network).
  5. For one of the possible query nodes, use Netica's sensitivity analysis function to determine which would be the most informative observation to make next. Cut and paste the Netica output information into your README file, before explaining your answer.
  6. Show how the beliefs change in a form of diagnostic reasoning when evidence about at least one of the domain variables is added (Save in B2). Which nodes are d-separated with this evidence added?
  7. Show how the beliefs change in a form of causal reasoning when evidence about at least one of the domain variables is added (Save in B3).
  8. Show how the beliefs change through "explaining away" when evidence particular combinations of evidence are added. (Save in B4).
  9. Show how the beliefs change when you change the priors of a node without parents (rather than adding evidence). (Save in B5)
  10. What is the complexity of the join-tree for this network?

PART C: Modelling decision making (10 marks)

For one of the problems represented in either Part A or Part B, extend the problem to be a decision problem. This means that you must decide on the possible actions to be presented in the decision node, and decide what the utility node should be a function of.
  1. Describe the extended problem and the new nodes, particularly the utility values, in the README file
  2. .
  3. Show the decision outcome (including the expected utilities) for at least 2 different evidence cases. Save networks (showing probabilities and expected utility for the decision node) in files C1 and C2.
  4. Show the decision outcome (including the expected utilities) for the same two evidence cases with a different utility function. cases. Save networks (showing probabilities and expected utility for the decision node) in files C3 and C4.

PART D: Peer Assessment (Hurdle)

The final part of this assignment involves the assessment of the completed assignment (Parts A-C) of another student in the class. You will be provided with a detailed marking template for this task and I will also talk about the assessment process in class on Friday August 3rd. I expect PART D to take no more than 1 hr in total.

Submission (PARTS A-C)

Please put your network files and your README file in a directory called CSE443-Ass2-LoginId, and put this on a floppy disk. The README file should also include your name and login Id. Also print out your README file, and each of the saved BN output files (i.e. the .dne files), with belief bars showing. Make sure you label each printed BN.

If you are able to attend the CSE443 class on Friday August 10th, 11.00am, you should submit both the floppy disk and the hard copy at that time.

If you are unable to attend that class, submit them through the standard assignment submission box outside the CSSE Enquiries Office, ground floor, Blg 63.

Submission (PART D)

I will hand out assignments for peer assessment during the class on August 10th. If you are unable to attend this class, please let me know the best way to pass you the assignment you have to mark. Peer assessments are due on Friday August 17th, 4pm, on the marking sheet provided, in my mailbox (ground floor, Blg 63).

Late Submission

Obviously if you are late submitting this assignment it will impact on the peer assessment process, so late submissions received on Monday 13th will be accepted but subject to a late penalty. After that time the only excuses accepted will be illness or something for which you would normally ask for special consideration. Poor time management is not a good excuse!

Marking

The mark you will receive will be the mark from the peer assessment, after I have done a quick check to make sure the marking seems to be reasonable and that there is fairness and uniformity in marking. You will receive a marking sheet detailing the breakdown of your mark. If you wish to query any aspect of the marking, I will re-mark the assignment myself.

Note that this will be the first time I have used peer assessment for a student assignment. I am doing it partly to speed up the marking and feedback process, and partly because I think it will be very beneficial for students to have the opportunity to critically assess other BN models. I will be flexible, however, about making adjustments to the process if unforeseen problems arise.