CMSC 671 - Fall 2010
Homework #4

Out Monday 11/1/10
Due Monday 11/22/10


1. Bayesian networks (60 pts.)

(Adapted from R&N 2/e, exercise 14.2) In the local nuclear power station, there is an alarm that senses when a temperature gauge exceeds a given threshold. The gauge measures the core temperature. Consider the Boolean variables A (alarm sounds), FA (alarm is faulty), and FG (gauge is faulty), and the discrete-valued nodes G (gauge reading) and T (actual core temperature).

In parts (c) through (f), you should simplify the probability equations by using the following shorthand:
     T = temperature is high         ~T = temperature is not high (normal)
     G = gauge G reads high       ~G = gauge G reads normal
     A = alarm sounds                ~A = alarm doesn't sound
     FG = gauge G is faulty         ~FG = gauge G is working
     FA = alarm is faulty              ~FA = alarm is working
 
(a) (5 pts.) Draw a belief net for this domain, given that the gauge is more likely to fail when the core temperature gets too high.

(b) (5 pts.) Suppose that there are just two possible actual and measured temperatures, Normal and High, and that the gauge gives the incorrect temperature (x*100)% of the time when it is working, but (y*100)% of the time when it is faulty. (For example, if the gauge gives the incorrect temperature 25% of the time when it is working correctly, then x=.25.)  Give the conditional probability table associated with G. Please specify your CPT in the following form:
 
P (G | T, FG) T = Normal T = Normal T = High T = High

FG ~FG FG ~FG
~G



G



(c) (5 pts.) Suppose the alarm works unless it is faulty, in which case it never sounds. Give the conditional probability table associated with A. Use the same CPT table format, this time for P (A | G, FA).

(d) (14 pts.) For this and the next problem, you will also need to know that P(T) = p, P (FG | T) = g, and P (FG | ~T) = h.  Suppose the alarm and gauge are working, and the alarm sounds. Show how to compute the probability that the core temperature is too high, using inference by enumeration. (Your answer may include summation terms, and may include the probabilities given above -- i.e., x, y, p, g, and h.)

(e) (14 pts.)  Suppose that the alarm is known to be faulty, and the gauge is known to be working.  Show how to compute the probability that the alarm will sound, using the method of variable elimination.  Again, your answers may include summation terms and the probabilities given above.

(f) (12 pts.) Describe, in words, how you would apply rejection sampling to determine the same probability given in question 1(g).  You may use pseudocode if you wish.

(g) (5 pts.) Suppose we add a second temperature gauge H, connected so that the alarm goes off (if it's working) when either gauge reads high. Where do H and FH (the event of H failing) go in the network? What is the new CPT associated with A?

2. Probabilistic Reasoning Over Time (20 pts)

(a) (10 pts.) (R&N Exercise 15.1) Show that any second-order Markov process can be rewritten as a first-order Markov process with an augmented set of state variables.  Can this always be done parsimoniously; that is, without increasing the number of parameters needed to specify the transition model?

(b) (10 pts.) In the summary to Chapter 15, Russell and Norvig summarize the three families of temporal models as "hidden Markov models, Kalman filters, and dynamic Bayesian networks (which include the other two as special cases)."  Explain in your own words why the first two can be seen as special cases of the third.

3. Decision Theory (20 pts.)

R&N Exercise 16.3.