Efficient Enumeration of Instantiations in Bayesian Networks
Sampath Srinivas, Pandurang Nayak
Over the past several years Bayesian networks have been applied to a wide variety of problems. A central problem in applying Bayesian networks is that of finding one or more of the most probable instantiations of a network. In this paper we develop an efficient algorithm that incrementally enumerates the instantiations of a Bayesian network in decreasing order of probability. Such enumeration algorithms are applicable in a variety of applications ranging from medical expert systems to model-based diagnosis. Fundamentally, our algorithm is simply performing a lazy enumeration of the sorted list of all instantiations of the network. This insight leads to a very concise algorithm statement which is both easily understood and implemented. We show that for singly connected networks, our algorithm generates the next instantiation in time polynomial in the size of the network. The algorithm extends to arbitrary Bayesian networks using standard conditioning techniques. We empirically evaluate the enumeration algorithm and demonstrate its practicality.
Keywords: Explanation, instantiations, algorithms, Bayesian network,
enumeration, lazy evaluat
PS Link: http://www-ksl.stanford.edu/people/srinivas/psfiles/sampandu_uai96.ps
PDF Link: /papers/96/p500-srinivas.pdf
AUTHOR = "Sampath Srinivas
and Pandurang Nayak",
TITLE = "Efficient Enumeration of Instantiations in Bayesian Networks",
BOOKTITLE = "Proceedings of the Twelfth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-96)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1996",
PAGES = "500--508"