CS522 -- Spring 2006

Assignment 2

Due: 11:00am, Tuesday 7 February 2006

The aim of the assignments in this course is to help you learn the material, rather than assessing what you learned in class. Feel free to post any questions to the WebCT bulletin board.

Question 1

Consider the belief network:

cs522as2q1-2006

with Boolean variables (A=true is written as a and A=false as ¬a) and the following conditional probabilities:
P(a) = 0.9
P(b) = 0.2
P(c| a) = 0.1
P(c|¬a) = 0.7
P(d|a,b) = 0.1
P(d|a,¬b) = 0.8
P(d|¬a,b) = 0.7
P(d|¬a,¬b) = 0.4
P(e| b) = 0.4
P(e|¬b) = 0.9
P(f| d) = 0.1
P(f|¬d) = 0.8
P(g| d) = 0.8
P(g|¬d) = 0.4
P(h|e) = 0.7
P(h|¬e) = 0.2
P(i|g,h) = 0.3
P(i|g,¬h) = 0.8
P(i|¬g,h) = 0.7
P(i|¬g,¬h) = 0.4
P(j|a,i) = 0.1
P(j|a,¬i) = 0.5
P(j|¬a,i) = 0.7
P(j|¬a,¬i) = 0.2
When answering these questions, please do them by hand, then check with the applet. Please think about how much computation can be reused.
  1. Compute P(g) numerically using variable elimination. Show all of the factors created. Please try to do it by hand, then check it with the CIspace applet.
  2. Consider computing P(g|¬h) using variable elimination. Show what factors are created (by multiplying or summing out). How much of the previous computation can be reused?
  3. Show what factors are created when computing P(h) using variable elimination. How much of the previous computation can be reused?
  4. Show what factors are created when computing P(h | ¬c) using variable elimination. How much of the previous computation can be reused?
  5. Show what factors are created when computing P(h|j) using variable elimination. How much of the previous computation can be reused?
  6. Show what factors are created when computing P(h|j&¬c) using variable elimination. How much of the previous computation can be reused?
  7. Draw a clique tree (join tree) for this network.
  8. Show how recursive conditioning can be used to compute P(g|¬h). Condition using the reverse of the elimination ordering you used for part (b). Draw the tree, showing what structure is shared and when you can solve subproblems independently.

Question 2

The min-factor elimination ordering heuristic says that you should select a node that results in the smallest factor at every stage.

The minimal deficiency (also called min-fill) elimination ordering heuristic says that you should select a node at each stage that adds the fewest arcs (in the network where nodes in the same factor are joined by arcs). [The deficiency of a node is the number of pairs of neighbours of that node that are not connected.]

  1. Given an example (assume binary variables) where the largest factor created using the min-factor elimination ordering is bigger than the largest factor created using the minimal deficiency elimination ordering.
  2. Given an example (assume binary variables) where the largest factor created using the minimal deficiency elimination ordering is bigger than the largest factor created using the min-factor elimination ordering.
  3. Which heuristic do you think will work better? Explain why.

Question 3

For each question in this assignment, say how long you spent on it. Was this reasonable? What did you learn?
David Poole