On the Tree Structure Used by Lazy Propagation for Inference in Bayesian Networks

摘要

Lazy Propagation (LP) is a propagation scheme for belief update in Bayesian networks based upon Shenoy-Shafer propagation. So far the secondary computational structure has been a junction tree (or strong junction tree). This paper describes and shows how different tree structures can be used for LP. This includes the use of different junction trees and the maximal prime subgraph decomposition organised as a tree. The paper reports on the results of an empirical evaluation on a set of real-world Bayesian networks of the performance impact of using different tree structures in LP. The results indicate that the tree structure can have a significant impact on both time and space performance of belief update.