1 Consider the variable elimination algorithm in Figure 11. a. Section 4 applies variable elimination to the...

1 Consider the variable elimination algorithm in Figure 11.

Transcribed Image Text:

a. Section 4 applies variable elimination to the query P(Burglary John Calls = true, MaryCalls = true). Perform the calculations indicated and check that the answer is correct. b. Count the number of arithmetic operations performed, and compare it with the number performed by the enumeration algorithm. c. Suppose a network has the form of a chain: a sequence of Boolean variables X1,..., Xn where Parents(X) = {Xi-1} for i=2,..., n. What is the complexity of computing P(X1|X = true) using enumeration? Using variable elimination? d. Prove that the complexity of running variable elimination on a polytree network is linear in the size of the tree for any variable ordering consistent with the network structure. 6 Investigate the complexity of exact inference in general Bayesian networks: a. Prove that any 3-SAT problem can be reduced to exact inference in a Bayesian network constructed to represent the particular problem and hence that exact inference is NP-