Computational Advantages of Relevance Reasoning in Bayesian Belief Networks
Yan Lin, Marek Druzdzel
This paper introduces a computational framework for reasoning in Bayesian belief networks that derives significant advantages from focused inference and relevance reasoning. This framework is based on d -separation and other simple and computationally efficient techniques for pruning irrelevant parts of a network. Our main contribution is a technique that we call relevance-based decomposition. Relevance-based decomposition approaches belief updating in large networks by focusing on their parts and decomposing them into partially overlapping subnetworks. This makes reasoning in some intractable networks possible and, in addition, often results in significant speedup, as the total time taken to update all subnetworks is in practice often considerably less than the time taken to update the network as a whole. We report results of empirical tests that demonstrate practical significance of our approach.
Keywords: Relevance, Bayesian belief networks, algorithms.
PS Link: http://www.pitt.edu/~druzdzel/psfiles/uai97.ps
PDF Link: /papers/97/p342-lin.pdf
AUTHOR = "Yan Lin
and Marek Druzdzel",
TITLE = "Computational Advantages of Relevance Reasoning in Bayesian Belief Networks",
BOOKTITLE = "Proceedings of the Thirteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1997",
PAGES = "342--350"