LAZY propagation: A junction tree inference algorithm based on lazy evaluation

In this paper we present a junction tree based inference architecture exploiting the structure of the original Bayesian network and independence relations induced by evidence to improve the efficiency of inference, The efficiency improvements are obtained by maintaining a multiplicative decomposition of clique and separator potentials. Maintaining a multiplicative decomposition of clique and separator potentials offers a tradeoff between off-line constructed junction trees and online exploitation of baron variables and independence relations induced by evidence. We consider the impact of the proposed architecture on a number of commonly performed Bayesisn network tasks. The tasks we consider include cautious propagation of evidence, determining a most probable configuration, and fast retraction of evidence a long with a number of other tasks. The general impression is that the proposed architecture increases the computational efficiency of performing these tasks. The efficiency improvement offered by the proposed architecture is emphasized through empirical evaluations involving large real-world Bayesian networks. We compare the time and space performance of the proposed architecture with non-optimized implementations of the HUGIN and Shafer-Shenoy inference architectures. (C) 1999 Elsevier Science B.V. All rights reserved.