CSE151 Assignment 1

Inference in Medical Diagnosis networks
Due: 11:59PM April 25, 2006

In this programming assignment, you will be using the Bayes Net Toolbox to find marginal distributions and most-probable exaplanations in a medical diagnosis network.

Background: The QMR-DT network is used by doctors to find the most likely causes of a patient's symptoms. The network has two layers of binary random variables: the diseases and the findings. Each finding can be caused by some (hopefully small) subset of the diseases, and has a "noisy-OR" activation function as described in lecture.

All edges in the graph go from the disease nodes to the finding nodes. Disease nodes have some prior probability of being true, and each finding node has an associated "leak" parameter representing the possibility that none of the modeled diseases caused the finding to be true. Each edge in the graph has an inhibition parameter, which models the fact that a disease may be present even if the finding is not.

Given these parameters and a set of observed findings (evidence), your job will be to construct the Bayes net, and then find either the marginal distribution over the hidden nodes or the most probable explanation.

You may work in groups of up to 3, and all files must be submitted with the turnin utility no later than 11:59PM (PDT) April 25, 2006.

Guildelines: Format your report using the NIPS template provided below. Include the following sections:

  1. Introduction - describe the problem you're solving
  2. Methods - Brief description of the methods you used (for example, describe the different inference algorithms).
  3. Results - put all graphs, plots, and answers to the questions here. Include a subsection for each part of the assignment.
  4. Discussion - summarize your results, talk about any interesting and/or surprising outcomes.
  5. Conclusion - summarize what you learned from the project. Each partner in your group should write a paragraph describing his or her specific contributions.

  1. Getting Started

    Familiarize yourself with Matlab and the Bayes Net Toolbox. Read through the documentation and try out some of the examples.

    To use the BNT installation on lab machines running Linux, follow these instructions:

    1. At the shell prompt, run the command "prep cs151s"
    2. Once in Matlab, type "add_BNT_to_path" (you will need to do this each time you start Matlab)
    3. To make sure that everything is set up properly, run the command "test_BNT".

    This will not work under Windows in the lab.

  2. Building a Bayes Net

    Write a Matlab function of the form 
        [bnet ndiseases nsymptoms] = load_qmr_data(diseases, findings, arcs)
    Here, the parameters diseases, findings, and arcs specify the names of files containing the parameters for a QMR-DT-style Bayes net.

    The file formats are as follows:

    Here, all _Number parameters are integer indices of the nodes, and all _Value parameters are floating-point.

    The load_qmr_data function will read in these data files and return a bnet object, on which you can perform inference with the standard BNT tools. It should also return the number of diseases and the number of symptoms in the network.

    Load in the first data set and display the resulting Bayes net with the "draw_graph" function.

    What to turn in:

  3. Most-Probable Explanations

    Write a matlab function to load evidence into your Bayes net. It should be of the form: 
        obs = load_qmr_evidence(evidence, ndiseases, nfindings)
    where evidence contains the name of a text file containing observed values for finding nodes, and the ndiseases and nfindings parameters should be those returned by load_qmr_data. The format of the evidence file is:

    evidence.txt 

        Finding_Number      Observation

    Here, Observation can be either 0 (false) or 1 (true). Remember that BNT represents false as 1 and 2 as true. Your function should return an evidence cell matrix obs suitable for entry into an inference algorithm.

    Using the junction tree inference algorithm (jtree_inf_engine), find the most probable explanation (MPE) variable assignment for the test2 data set on all three sets of evidence.

    Display the resulting disease variable assignments as a bar plot. Do not include the finding nodes in this plot.

    What to turn in:

  4. Inference Algorithms

    Do a comparison of the following inference algorithms for finding marginal distributions on the test3 set:

    For each evidence set, answer the following:

    1. For each inference algorithm, make a bar plot of the marginal probabilities the disease nodes being true.
    2. Which algorithm is fastest? Which approximate algorithm gives the best results, compared to quickscore?
    3. What is the smallest number of samples for likelihood weighting that still gives accurate results (when compared with quickscore)? How few iterations of belief propagation can you use and still get reasonably good results?
    4. How are accuracy and performance of each inference algorithm affected by the alternate evidence sets? Why might this be?

    Note: some of these inference algorithms may take a long time to run, so start early!

    What to turn in:

Resources