3 - Belief Updating and Cluster Graphs

Summary

Chapter 2 introduced several methods using message passing as a mechanism for effective belief updating in BNs. The λ – π message passing method along the arcs of a BN produces exact posteriors only in tree-structured BNs. Loop cutset conditioning requires converting a nontree BN into multiple tree-structured BNs and carrying out λ – π message passing in each of them. The stochastic simulation can be applied directly to a nontree BN to compute approximate posteriors but requires massive message passing in the BN. In this chapter, we focus on concise message passing and will drop the word concise when there is no confusion. We explore the opportunities presented by reorganizing the DAG structure of a BN into a cluster graph structure. The objective is to develop an alternative exact method that uses concise message passing in a single cluster graph structure for belief updating with nontree BNs. A cluster graph consists of an interconnected set of clusters. Each cluster is a subset of nodes (variables) in the original BN. Message passing is performed between adjacent clusters in the cluster graph. We investigate under what conditions such message passing leads to correct belief updating.

Section 3.2 introduces cluster graphs. A set of conventions on how a cluster graph constrains message passing is outlined in Section 3.3.