Consider the variable elimination algorithm in Figure elimination-ask-algorithm (page elimination-ask-algorithm).
-
Section exact-inference-section applies variable elimination to the query Perform the calculations indicated and check that the answer is correct.
-
Count the number of arithmetic operations performed, and compare it with the number performed by the enumeration algorithm.
-
Suppose a network has the form of a chain: a sequence of Boolean variables $X_1,\ldots, X_n$ where ${Parents}(X_i){X_{i-1}}$ for $i2,\ldots,n$. What is the complexity of computing ${\textbf{P}}(X_1X_n{true})$ using enumeration? Using variable elimination?
-
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.