CIS 830
Friday, 26 March 2004
Due: Friday,
09 April 2004
(before
midnight Saturday 10 April 2004)
This
problem set is designed to apply your theoretical understanding of inference in
graphical models using the junction tree
algorithm.
Refer
to the course intro handout for guidelines on working with other students.
Note: Remember to submit your solutions in
electronic form by uploading them to ksu-cis830-spring2004
and produce them only from your personal source code, scripts, and
documents from the machine learning applications used in this problem set
(not common work or sources other than the textbook or properly cited
references).
First,
log into your course accounts on the KDD Core (Fingolfin, Ringil, Anaire,
Telchar, Narvi) and make sure your home directory is in order. Notify admin@www.kddresearch.org (and cc: cis830ta@www.kddresearch.org) if
you have any problems at this stage.
Problems
1.
(10
points) Running Hugin and building
Bayesian networks. Download the Hugin Lite package from www.hugin.com
(as of 26 Mar 2004, the download URL is http://www.hugin.com/Products_Services/Products/Demo/Lite/)
and install it on your Windows, Solaris, or Linux system. Walk through the “apple tree” Bayesian belief
network (BBN) example and decision network example. Now use Hugin to build a Bayesian network for the decision-theoretic Apple-Tree example
using your own conditional probability and utility values. Turn in a screen shot of your BBN (pasted
into Word, PostScript, or PDF) and a Hugin network file titled Apple-Tree.hkb.
2.
(40
points) Tracing the junction tree
algorithm.
Your
solution to this problem must be in MS Word, PostScript, or PDF format. Use a spreadsheet (I recommend OpenOffice or
Excel XP/2003) to record your solution if you wish.
a) (15
points) Burglary Example. Draw a BBN illustrating the buglary network
shown in Russell and Norvig (Fig. 15.2, p. 439 1st edition). Modify the conditional probability table
(CPT) values given so that the prior for Burglary
is 0.002 and the prior for Earthquake
is 0.08. Now use the BBN to infer the
most probable explanation (MPE) given that John calls but Mary does
not. Save your .hkb file and take a
screen shot of the result. Paste and type this into a Word, PostScript,
or PDF document. Explain in a few
sentences and equations how the MPE can be computed in this case.
b) (30
points) Asia Example. Download the Asia network from http://www.norsys.com/networklibrary.html
or use the copy in Bayesian Network tools
in Java (BNJ) at http://bndev.sourceforge.net,
and trace through the steps of the junction tree algorithm by hand on this
example. Show your work and cite your
references, especially if you refer to the Lauritzen-Spiegelhalter paper or the
Neapolitan book (1990).
Extra credit
(5 points) Car Example. Download Bayesian Network tools in Java (BNJ) from
http://bndev.sourceforge.net and
use it to convert “Car Diagnosis 2” into XML format. The network can be found at http://www.norsys.com/networklibrary.html.
(15 points) Join
tree aka junction tree aka the Lauritzen-Spiegelhalter (L-S)
algorithm for exact inference in Decision Networks. Repeat the exercise for the Asia-DEC network from Cowel, Dawid,
Lauritzen and Spiegelhalter (1999).
Next Assignment:
-
Modifying
L-S
-
ECJ