Project 3.2: Battleship: Bayes' Nets
Due 11/9 at 11:59pm
Update: 11/6: This checkpoint will only be the written problems below; the code will be its own checkpoint 3.3. However, this checkpoint will still be due on 11/9 at 11:59pm.
What to submit: Submit your assignment in a .pdf or a .txt file. You may submit one assignment per group, as always,
though we recommend everyone work through this assignment on their own before meeting with a partner.
Bayes' Nets
Question 1 (4 points) Consider the following
network, in which a mouse agent is reasoning about the behavior of a cat.
The mouse really wants to know whether the cat will attack (A), which depends on
whether the cat is hungry (H) and whether the cat is sleepy (S). The mouse
can observe two things, whether the cat is sleepy (S) and whether the cat has a
collar (C). The cat is more often sleepy (S) when it's either full (f) or
starved (v) than when it is peckish (p) and the collar (C) tends to indicate
that the cat is not starved. Note that entries are omitted, such as P(C=~c),
when their complements are given.
P(C) 
P(HC) 
P(SH) 
P(AH,S) 

H 
C 
P 
f 
c 
0.60 
v 
c 
0.10 
p 
c 
0.30 
f 
~c 
0.20 
v 
~c 
0.40 
p 
~c 
0.30 

S 
H 
P 
s 
f 
0.90 
s 
v 
0.70 
s 
p 
0.30 

A 
H 
S 
P 
a 
f 
s 
0.01 
a 
f 
~s 
0.10 
a 
v 
s 
0.50 
a 
v 
~s 
0.90 
a 
p 
s 
0.20 
a 
p 
~s 
0.70 

Assume you have the following samples relative to the evidence C=c, S=s:
C=c, H=f, S=s, A=~a
C=c, H=f, S=s, A=~a
C=c, H=f, S=s, A=~a
C=c, H=p, S=s, A=a
C=c, H=v, S=s, A=~a
 Draw the graphical model associated with this problem.
 Calculate P(A  C=c, S=s) using joint inference by enumeration
 Assume the samples were generated by rejection sampling. What would
the estimate of P(A  C=c, S=s) be?
 Assume the samples were generated by likelihood weighting. What
would the estimate of P(A  C=c, S=s) be?
 Which sampling scheme is more likely to have generated these samples,
rejection sampling or likelihood weighting?
 It might seem strange that collars "cause" hunger: their
relationship is one of correlation, not causation. Propose a new node
which allows a more sensible causal interpretation and state how the network
connections should change to accommodate it.
Question 2 (2 points). In the network below,
consider which nodes are possibly dependent on the listed node with the listed
evidence:
 B with no observations
 B given G
 G given F and C
 C given E, F, and B
Question 3 (4 points). Sometimes we can prune down
a network before inference to simplify our computations. In this problem,
you will develop a condition under which "dangling" variables can be
pruned.
 Consider two networks, G and G'. In G, we have nodes X, Y, and Z
where X is the parent of Y and Y is the parent of Z, so that P(x, y, z) =
P(x) P(y  x) P(z  y). G' is identical to G except, Z and its CPTs
have been deleted. Show that P(x  y) is the same whether we compute
it from G or G'.
 More generally, assume we have a network G in which there are nodes X1 ...
Xn. Assume that we wish to calculate P(Q_{1}=q_{1},
... Q_{k}=q_{k } E_{1}=e_{1}, ... E_{m}=e_{m}),
where each query variable Q and evidence variable E is one of the variables
X_{i}. Let H_{1}, ... H_{p} be all the
remaining (hidden) nodes which are neither observed nor queried. Write
an expression for P(q_{1}, ... q_{k } e_{1}, ... e_{m})
in terms of the full joint distribution entries P(q_{1}, ... q_{k},
e_{1}, ... e_{m}, h_{1}, ... h_{p}).
 Assume that one of the hidden variables H, say H_{1}, is a
leaf node, that is, it has no children in G. Let G' be identical to G
but with H removed. Show that P(q_{1}, ... q_{k } e_{1},
... e_{m}) is the same whether calculated in G or G'.
 Prove that any node which does not dominate either an evidence or query
node ("dangling nodes") may be pruned without effecting the result
of a query.