Lazy Propagation in Junction Trees

Abstract

The efficiency of algorithms using secondary structures for probabilistic inference in Bayesian networks can be improved by exploiting independence relations induced by evidence and the direction of the links in the original network. In this paper we present an algorithm that on-line exploits independence relations induced by evidence and the direction of the links in the original network to reduce both time and space costs. Instead of multiplying the conditional probability distributions for the various cliques, we determine on-line which potentials to multiply when a message is to be produced. The performance improvement of the algorithm is emphasized through empirical evaluations involving large real world Bayesian networks, and we compare the method with the HUGIN and Shafer-Shenoy inference algorithms.

Appears in Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI1998)

References in corpus (2)

• Computational Advantages of Relevance Reasoning in Bayesian Belief Networks
• Cautious Propagation in Bayesian Networks

Cited by in corpus (5)

• Lazy Evaluation of Symmetric Bayesian Decision Problems
• Inference in Multiply Sectioned Bayesian Networks with Extended Shafer-Shenoy and Lazy Propagation
• Probability and Asset Updating using Bayesian Networks for Combinatorial Prediction Markets
• Exploiting Functional Dependence in Bayesian Network Inference
• Identifying the Relevant Nodes Without Learning the Model