CECS 451 Assignment 9

CECS 451
Assignment 9
Total: 44 Points
General Instruction
• Submit uncompressed file(s) in the Dropbox folder via BeachBoard (Not email).
• Use Python 3, any other programming language is not acceptable.
• You can import modules in the Python Standard Library (please check the full list
here). If you want to use any other library, please consult with the instructor or TA.
• Your submission may be evaluated automatically using a script file, so if you would
not follow the output format, you may receive zero point even though your program
outputs correct answers.
1. Consider Figure 1 (notice that some of the probabilities are different with the figure
in the textbook), and implement a program to answer the query P~ (C|¬s, w) by using
MCMC sampling. The program should generate 1, 000, 000 samples to estimate the
probability. To answer (a) and (b), you can prepare the answers with scratch paper and
print-out them (hard coding is fine). However, you are asked to implement a simulation
program to answer (c). Please use the filename mcmc.py. You may want to verify your
estimated probability with the one computed by using bayes.jar.
(a) (8 points) Show P~ (C|¬s, r), P~ (C|¬s, ¬r), P~ (R|c, ¬s, w), P~ (R|¬c, ¬s, w).
(b) (16 points) Show the transition probability matrix Q ∈ R
4×4 where
qij = transition probability from Si to Sj
in Figure 2.
(c) (20 points) Show the probability of the query P~ (C|¬s, w)
(d) Please follow the output format. (Fix precisions using "{:.4f}".format)
Part A. The sampling probabilities
P(C|-s,r) = <..., ...>
P(C|-s,-r) = <..., ...>
P(R|c,-s,w) = <..., ...>
P(R|-c,-s,w) = <..., ...>
Part B. The transition probability matrix
S1 S2 S3 S4
S1 . . . .
S2 . . . .
S3 . . . .
S4 . . . .
Part C. The probability for the query
P(C|-s,w) = <..., ...>
CECS 451 Assignment 9 - Page 2 of 2
Figure 1: A multiply connected network with conditional probability tables. Note that the
probabilities are slightly different than the lecture notes and the text book example.
Figure 2: Possible states diagram