Belief Updating with Junction Trees
Yang Xiang · Cambridge University Press eBooks · 2002
Chapter 4 discussed the conversion of the DAG structure of a BN into a junction tree. In a BN, the strength of probabilistic dependence between variables is encoded by conditional probability distributions. This quantitative knowledge is encoded in a junction tree model in terms of probability distributions over clusters. For flexibility, these distributions are often unnormalized and are termed potentials. This chapter addresses conversion of the conditional probability distributions of a BN into potentials in a junction tree model and how to perform belief updating by passing potentials as concise messages in a junction tree. Section 5.2 defines basic operations over potentials: product, quotient, and marginal. Important properties of mixed operations are discussed, including associativity, order independence, and reversibility. These basic and mixed operations form the basis of message manipulation during concise message passing. Initializing of potentials in a junction tree according to the Bayesian network from which it is derived is then considered in Section 5.3. Section 5.4 presents an algorithm for message passing over a separator in a junction tree and discusses the algorithm's consequences. Extending this algorithm, Section 5.5 addresses belief updating by message passing in a junction tree model and formally establishes the correctness of the resultant belief. Processing observations is described in Section 5.6. Guide to Chapter 5 Given a BN, its DAG structure provides the qualitative knowledge about the dependence among domain variables.