Exercise 20.1 - Variable elimination

Answers

The figure index is mistaken. The graphical model takes the following structure:

Figure 1: Exercise 20.1.

For question (a), we use the following order for variable elimination:

x 1 , x 2 , x 3 , x 4 , x 5 , x 6 .

We detail the entire process as follows:

Z = ∑ x 6 ∑ x 5 ∑ x 4 ∑ x 3 ∑ x 2 ∑ x 1 ψ 12 ( x 1 , x 2 ) ψ 13 ( x 1 , x 3 ) ψ 24 ( x 2 , x 4 ) ψ 34 ( x 3 , x 4 ) ψ 45 ( x 4 , x 5 ) ψ 56 ( x 5 , x 6 ) = ∑ x 6 ∑ x 5 ψ 56 ∑ x 4 ψ 45 ∑ x 3 ψ 34 ∑ x 2 ψ 24 ∑ x 1 ψ 12 ψ 13 = ∑ x 6 ∑ x 5 ψ 56 ∑ x 4 ψ 45 ∑ x 3 ψ 34 ∑ x 2 ψ 24 τ 23 = ∑ x 6 ∑ x 5 ψ 56 ∑ x 4 ψ 45 ∑ x 3 ψ 34 τ 34 = ∑ x 6 ∑ x 5 ψ 56 ∑ x 4 ψ 45 τ 4 = ∑ x 6 ∑ x 5 ψ 56 τ 5 = ∑ x 6 τ 6 .

The largest intermediate factor is:

τ 23 ∑ x 1 ψ 12 ψ 13 ,

hence for (b) the largest clique consists of three nodes.

For question (c), we have:

Z = ∑ x 6 ∑ x 5 ∑ x 3 ∑ x 2 ∑ x 1 ∑ x 4 ψ 12 ψ 13 ψ 24 ψ 34 ψ 45 ψ 56 = ∑ x 6 ∑ x 5 ψ 56 ∑ x 3 ∑ x 2 ∑ x 1 ψ 12 ψ 13 ∑ x 4 ψ 24 ψ 34 ψ 45 = ∑ x 6 ∑ x 5 ψ 56 ∑ x 3 ∑ x 2 ∑ x 1 ψ 12 ψ 13 τ 235 = ∑ x 6 ∑ x 5 ψ 56 ∑ x 3 ∑ x 2 τ 235 ′ = ∑ x 6 ∑ x 5 ψ 56 ∑ x 3 τ 35 = ∑ x 6 ∑ x 5 ψ 56 τ 5 = ∑ x 6 τ 6 ,

where we observe a big clique { x 2 , x 3 , x 4 , x 5 } .

User profile picture
2021-03-24 13:42
Comments