4 - Junction Tree Representation

Summary

Chapter 3 has shown that, in order to use concise message passing in a single cluster graph for exact belief updating with a nontree BN, one must reorganize the DAG into a junction tree. Graphical representations of probabilistic knowledge result in efficiency through the exploration of conditional independence in terms of graphical separation, as seen in Chapter 2. Therefore, the reorganization needs to preserve the independence–separation relations of the BN as much as possible. This chapter formally describes how independence is mapped into separation in different graphical structures and presents algorithms for converting a DAG dependence structure into a junction tree while preserving graphical separation to the extent possible.

Section 4.2 defines the graphical separation in three types of graphs commonly used for modeling probabilistic knowledge: u-separation in undirected graphs, d-separation in directed acyclic graphs, and h-separation in junction trees. The relation between conditional independence and the sufficient content of a message in concise message passing is established in Section 4.3. In Section 4.4, the concept of the independence map or I-map, which ties a graphical model to a problem domain based on the extent to which the model captures the conditional independence of the domain, is introduced. The concept of a moral graph is also introduced as an intermediate undirected graphical model to facilitate the conversion of a DAG model to a junction tree model. Section 4.5 introduces a class of undirected graphs known as chordal graphs and establishes the relation between chordal graphs and junction trees.