4 Variable Elimination Algorithm (Multiply Connected)

Consider the following belief network:

1. Give all of the initial factors that represent the conditional probability tables.
2. Suppose we observe a value for K, what factors are removed and what factor(s) are created (call these f₁...).
3. Suppose (after observing a value for K) we were to eliminate the variables in order: B, D, A, C, E, G, F, I, H. For each step show which factors are removed and what factor(s) are created (call these f₂,f₃,..., continuing to count from the previous part). What is the size of the maximum factor created (give both the number of variables and the table size).
4. Suppose, instead that we were to observe a value for A and a value for I. What are the factors created by the observations? Given the variable ordering: K, B, D, C, E, G, F, H. For each step show which factors are removed and what factor is created.
5. Suppose, without any observations, we eliminate F. What factors are removed and what factor is created. Give a general rule as to what variables are joined when a variable is eliminated from a Bayesian network.
6. Suppose we change the graph, so that D is a parent of G, but F isn't a parent of I. Given the variable ordering in part (c) to compute the posterior distribution on J given an observation on K, what are the sizes of the factors created? Can you think of a better ordering?
7. Draw an undirected graph, with the same nodes as the original belief network, and with an arc between two nodes X and Y if there is a factor that contains both X and Y. [This is called the moral graph of the Bayesian network; can you guess why?]

   Draw another undirected graph, with the same nodes where there is an arc between two nodes if there is an original factor or a created factor (given the elimination ordering for part (c) that contains the two nodes. Notice how the second graph triangulates the moral graph.

   Draw a third undirected graph where the nodes correspond to the maximal cliques of the second (triangulated) graph. [Note that a clique of a graph G is a set of nodes of G so that there is an arc in G between each pair of nodes in the the clique. We refer to the nodes of the Bayesian network/moral graph as variables.] Draw arcs between the nodes to maintain the properties (i) there is exactly one path between any two nodes and (ii) if a variable is in two nodes, every node on the path between these two nodes contains that variable. The graph you just drew is called a junction tree or a clique tree. On the arc between two cliques, write the variables that are in the intersection of the cliques. What is the relationship between the clique tree and the VE derivation?