Written Assignment 4: Bayes' Nets

Question 1 (4 points). Consider the following basic Bayes' net, in which X, Y, and Z are Boolean variables:

1. Prove that X and Z are (marginally) independent, for any choice of the local conditional probabilities.

2. Exhibit a set of local conditional probabilities with the property that X and Z are also conditionally independent given Y.  (You may wish to use the applet referred to in problem 3 to test out your distributions painlessly.)

3. Exhibit a set of local conditional probabilities with the property that, given Y = true, X and Z exhibit a negative correlation (explaining-away).  That is, P(X = true | Y = true) > P(X = true), but P(X = true | Y = true, Z = true) < P(X = true | Y = true).  Give an intuitive scenario where this trend would hold.

4. Exhibit a set of local conditional probabilities with the property that, given Y = true, X and Z exhibit a positive correlation.  That is, P(X = true | Y = true) > P(X = true), and P(X = true | Y = true, Z = true) > P(X = true | Y = true).  Give an intuitive scenario where this trend would hold.

Question 2 (4 points). Given the Bayes' net below, consider each of the listed pairs of variables.  For each pair:

1. Specify a minimal set of variables (possibly none) whose observation makes the pair conditionally independent
2. Specify a minimal set of variables (possibly none) for which the variables may be dependent
3. Show a path which connects the variables using the Bayes' ball (d-separation) reachability algorithm given the evidence variables you chose above

1. A and F
2. B and I
3. G and E
4. Which nodes are reachable from A (i.e. not separated, or possibly dependent) given observations of D and H?  What about given C and I?

Question 3 (5 points). Consider the following domain:

• There are three soccer teams, A, B, and C.  Each has a fixed, unknown quality of 0, 1, 2, or 3 (larger is better). 
• Each team plays every other team once, resulting in a win, loss, or draw.
• When two teams play, the result is a noisy, probabilistic function of the difference between their qualities: 
  • If the difference is 0, a team wins 30%, loses 30%, or draws 40% of the time.
  • If the difference is 1, the better team wins 50%, loses 20%, or draws 30%.
  • If the difference is 2, the better team wins 70%, loses 10%, or draws 20%.
  • If the difference is 3, the better team wins 90% or draws 10%.

For the parts which ask for specific calculations, use the Bayes' net applets at the UBC CI site or JavaBayes to execute the queries (use the belief network app, not the decision network one).  Parts (c) through (h) should take very little time with the help of the applet.

1. Draw a reasonable Bayes' net for this domain, briefly justifying what arcs you do and do not include.
2. For each node, specify a reasonable local conditional probability table.  If multiple nodes in your network have the same local distributions, you only need to write those distributions once.
3. What is the posterior distribution over the game between B and C, given no evidence?  Does this answer make sense?
4. If A beats B, what is the updated posterior distribution over the outcome of the game between B and C?  Does this make sense?
5. If A beats B but draws against C, what is the updated posterior distribution over the outcome of the game between B and C?  Does this change make sense?
6. If A beats B but draws against C, what are the posterior distributions over the unobserved qualities of each team?  Do these distributions make sense?
7. If A beats B (and the result of the game against C is unknown), what is the posterior distribution over C's quality?  Why can you answer this question without any numerical calculations?
8. If A is known to have quality 1, what is the posterior distribution over the outcome of the game between A and B?  Does this distribution make sense?

Question 4 (4 points). Consider the following local conditional probability tables over the domain from lecture, where low pressure (L) causes rain (R), which causes both a dripping ceiling (D) and traffic (T).  Traffic in turn causes traffic reports (T') but such reports are often out-of-date and not all traffic is reported:

1. Draw the Bayes' net corresponding to these tables (i.e. state the the graph structure given the local tables).
2. Assume you are given an initial observation that there is no traffic report, but there is a low pressure system (note: contradictory evidence).  You wish to calculate the posterior distribution over whether or not it is raining (R) under these circumstances.  What are the initial factors for this model and observations for the purposes of the variable elimination algorithm?
3. Define and calculate the new factor introduced after eliminating T (show the result after T is both joined and summed out).
4. Continuing from the factors after the elimination of T, define and calculate the new factor introduced after eliminating D.  Why does this factor take this special form?  In general, for any run of the variable elimination algorithm, we can completely ignore any variable which does not have either a query node or an evidence node as a descendent.
5. What is the final posterior distribution over R?

Question 5 (3 points). Consider the following Bayes' net in which a single cause has several indirect effects:

Assume that you wish to predict the posterior distribution over Q given observations of E₁ = e₁ through E₄ = e₄.

1. State the original factors for the variable elimination algorithms in terms of the local conditional probabilities of the given net.
2. Assuming that each variable is Boolean, what is the size of the largest factor created if all the variables H_i are eliminated first, then C?
3. What if C is eliminated first, then all of the H_i are eliminated?
4. Argue (very briefly) which order is more efficient and why.