Prev Up Next
Go backward to Solution to part (e)
Go up to 4 Variable Elimination Algorithm (Multiply Connected)
Go forward to Solution to part (g)

Solution to part (f)

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) (i.e., B, D, A, C, E, G, F, I, H) to compute the posterior distribution on J given an observation on K, what are the sizes of the factors created? Is there an ordering that has a smaller factors?

The largest factor has three variables. The factors created have sizes: 2, 3, 3, 3, 3, 3, 2, 2, 1.

Step Eliminating Variables in factor Number of Variables
1. B A, D 2
2. D A, F, G 3
3. A C, F, G 3
4. C E, F, G 3
5. E H, F, G 3
6. G F, H, I 3
7. F H, I 2
8. I H, J 2
9. H J 1

There is no ordering with a smaller largest factor. But the variable ordering B, A, C, G, F, E, D, I, H results in only one factor of size 3.

Step Eliminating Variables in factor Number of Variables
1. B A, D 2
2. A C, D 2
3. C E, D 2
4. G D, I 2
5. F E, H, D 3
6. E H, D 2
7. D H, I 2
8. I H, J 2
9. H J 1

Computational Intelligence online material, ©David Poole, Alan Mackworth and Randy Goebel, 1999

Prev Up Next