a. Consider the Bayes net in Figure S13.19. 

(i) Given B, what variable(s) is E guaranteed to be independent of? 

(ii) Given B and F, what variable(s) is G guaranteed to be independent of?

b. Now we’d like to formulate d-separation as a search problem. Specifically, you’re given a variable X and a variable Y, a Bayes net G, and a set of observed variables E. You’re also given E⁺, which is the set of variables that are the parents or ancestors of evidence variables. Given this information, define a search problem that finds Y if X and Y are not d-separated, and does not find a goal otherwise. You may find the notation W → U ∈ G meaning “an arc from W to U is in the Bayes net” helpful. A full credit solution will have a minimal state space.

c. Give a non-trivial consistent heuristic for this problem.

Figure S13.19

Transcribed Image Text:

E C A B F D G