Question 1

Consider the domain of house plumbing represented below. This is a simplified model of the same domain used in the previous assignment.

In this figure, p1, p2 and p3 denote cold water pipes. p1 is the pipe coming in from the main water supply. t1, t2 and t3 are taps and d1, d2 and d3 are drainage pipes. The constants shower denotes a shower, bath denotes a bath, sink denotes a sink, and floor denotes the floor. There can also be plugs in the sink or in the bath. You can assume that you are in a static situation (i.e., you don't have to worry about time); imagine that you have stumbled in this situation and must reason about it.

Suppose you can observe or query the tap positions, flow out of drain d1, and whether there is water in the sink and bath, and whether there is water on the floor.

1. What are the random variables? In particular, you need random variables to represent the observations you may want to make, the queries you may be interested and other (hidden) variables to keep the model simple. For each variable, give its domain and intended interpretation.
2. Give a belief network for these variables, assuming a causal ordering of the variables. Give reasonable conditional probability tables. You can use the CIspace applet or any other belief network tool. (e.g., Netica or Genie).
3. Suppose you had to demonstrate to a skeptic that Belief networks are appropriate for this domain. Argue that this is a reasonable representation, and as part of your explanation, you need to give some test cases that show what your model is capable of. Use proper English. Be brief and concise (as this skeptic doesn't have much time).
4. What would your belief network look like if you had chosen the opposite ordering of variables?

Solution

(d) there are many more arcs, in particular there are arcs between nodes X and Y in the new ordering if there were arcs in the original network or if they have common ancestors in the original (causal) belief network that are lower in the total ordering than both X and Y or where there are common descendents (in the original graph) of X and Y that are also parents in the new graph. [This is a convoluted way of using D-separation in the original causal network to determine parents in the inverse network.] You just need to give some examples.

Question 2

P(a)	=	0.9
P(b)	=	0.2
P(c|a,b)	=	0.1
P(c|a,¬b)	=	0.8
P(c|¬a,b)	=	0.7
P(c|¬a,¬b)	=	0.4 P(d| b)	=	0.1
P(d|¬b)	=	0.8
P(e|c)	=	0.7
P(e|¬c)	=	0.2
P(f|c)	=	0.2
P(f|¬c)	=	0.9

1. Compute P(e) using variable elimination. Please try to do it by hand, then check it with the CIspace applet. Do not do any pruning. Explain the significance of each factor created (either what does it represent or why does it have particular values).
2. Compute P(e|¬f) using variable elimination. How much of the previous computation can be reused? Show only what is different.
3. Compute P(a|d) using variable elimination.
4. Compute P(a | ¬f).
5. Compute P(a|¬f,d).
6. Explain when observing d affects your belief in a. (Be as specific as possible.)

Solution

1. To compute P(e), you can sum out D and F, and the factors created are just 1's (that is why they can be pruned). I'll ignore these factors.

   You start off with the factors f₀(A), f₁(B), f₂(A,B,C), f₃(C,E).

   Eliminating A, you multiply f₀ and f₂, and sum out A, creating a factor f₄(B,C).

   Eliminating B, you multiply f₁ and f₄, sum out B, and create a factor f₅(C).

   Eliminating C, you multiply f₅ and f₃, sum out C, and the resulting factor f₆(E) represents P(E).

2. To compute P(e|¬f), you create a factor (lets call it f₇ to avoid confusion with the previous part) f₇(C).

   You can prune D. Eliminating A and B acts exactly as before, creating the same factors.

   Eliminating C, you multiply f₅, f₃ and f₇, sum out C, with the resulting factor f₈(E). To get the answer, you need to divide each element of ₈ by SUM_Ef₈(E). This creates f₉(E) which represents P(E|¬f).

3. Everything can be pruned! Or there are lots of tables with just ones, and a constant factor. P(a|d)=P(a).
4. E and D can be pruned.
5. What I wanted you to notice here is that D is not irrelevant when F is also observed.
6. When C, E or F are observed and B isn't observed.

Question 3

1. Rejection sampling
2. Importance sampling
3. Particle filtering

Solution

1. Rejection sampling: Sample B, then sample D, then you can reject the sample if the sample doesn't assign D=true. Then sample the rest of the variables. Return the proportion of the samples where F=true.
2. Importance sampling: Sample B. Weight those samples where B=true by 0.8 and those samples with B=false by 0.8. [You can actually do something smarter if you don't sample B by its prior, but use a different proposal distribution.]. Then sample the other variables. Return the weighted average of the samples with F=true.
3. Particle filtering: create lots of samples (here I will use 1000 as an example). Sample B 1000 times. Weight each sample using D as in importance sampling. Now generate a new 1000 samples, choosing each sample with probability proportional to its weight. Sample the rest of the variables with these new samples, and return the proportion of the samples where F=true.