Project 3.2: Battleship: Bayes' Nets

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.

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

1. Draw the graphical model associated with this problem.
2. Calculate P(A | C=c, S=s) using joint inference by enumeration
3. Assume the samples were generated by rejection sampling.  What would the estimate of P(A | C=c, S=s) be?
4. Assume the samples were generated by likelihood weighting.  What would the estimate of P(A | C=c, S=s) be?
5. Which sampling scheme is more likely to have generated these samples, rejection sampling or likelihood weighting?
6. 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:

1. B with no observations
2. B given G
3. G given F and C
4. 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.

1. 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'.
2. More generally, assume we have a network G in which there are nodes X1 ... Xn.  Assume that we wish to calculate P(Q₁=q₁, ... Q_k=q_k | E₁=e₁, ... E_m=e_m), where each query variable Q and evidence variable E is one of the variables X_i.  Let H₁, ... H_p be all the remaining (hidden) nodes which are neither observed nor queried.  Write an expression for P(q₁, ... q_k | e₁, ... e_m) in terms of the full joint distribution entries  P(q₁, ... q_k, e₁, ... e_m, h₁, ... h_p).
3. Assume that one of the hidden variables H, say H₁,  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₁, ... q_k | e₁, ... e_m) is the same whether calculated in G or G'.
4. 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.