Risk Assessment and Decision Analysis with Bayesian Networks

455

Appendix C: Junction Tree Algorithm

We break down the junction tree algorithm into two components: the algorithm for creating the tree and the

algorithm for evidence propagation in the tree.

C.1 Algorithm for Creating a Junction Tree

In summary there are three steps involved in producing the junction tree of a Bayesian network (BN):

1. Construct the moral graph. This involves constructing an undirected graph from the BN.

2. Triangulate the moral graph. This involves choosing a node ordering of the moral graph, and

using node elimination to identify a set of clusters (which are sets of nodes having certain proper-

ties we will explain later).

3. Construct the junction tree. This involves creating nodes corresponding to the clusters and insert-

ing the appropriate separators between them.

Steps 2 and 3 are nondeterministic; consequently, many different junction trees can be built from the same BN.

We know that a BN comprises a graph G, and associated probability tables. When we speak of the junction tree associ-

ated with the BN, we are actually only interested in the underlying graph G. The algorithm for constructing a junction

tree applies to any directed acyclic graph (DAG).

C.1.1 Step 1: Constructing the Moral Graph

The moral graph, G

M

, corresponding to G is constructed as follows:

1. For each node V in G identify its parents in G. For example, in the BN graph G in Figure C.1a,

the parents of nodes F are {D, E}, the parents of H are {G, E}. The other nodes all have just one or

zero parents.

2. For any pair of such parents add an edge linking them if an arc does not already connect them.

For example, since there is no arc linking the parents {D, E} of F we add an edge linking D and

E. Similarly we need to add an edge linking G and E.

3. Drop the direction of all the arcs. The resulting graph G

M

is the moral graph, as shown in Figure

C.1b.

The reason we call this a moral graph is because we insist on “marrying” all of the parent nodes together.