Sample-and-Accumulate Algorithms
for Belief Updating in Bayes Networks

Author(s):

Eugene Santos Jr.
Air Force Institute of Technology, Wright-Patterson Air Force Base
Dept. of Elec. and Comp. Eng. Air Force Inst. of Tech.
Wright-Patterson AFB, OH 45433-7765
e-mail: esantos@afit.af.mil

Solomon Eyal Shimony
Ben-Gurion University - Math. and Comp. Sci. Dept.
P. O. Box 653
84105 Be'er Sheva, Israel
e-mail: shimony@cs.bgu.ac.il
Phone: +972-7-461653
FAX : +972-7-472909

Edward Williams
Air Force Institute of Technology, Wright-Patterson Air Force Base
Dept. of Elec. and Comp. Eng. Air Force Inst. of Tech.
Wright-Patterson AFB, OH 45433-7765
e-mail: ewilliams@afit.af.mil

Abstract:

Belief updating in Bayes nets, a well known computationally hard problem, has recently been approximated by several deterministic algorithms, and by various randomized approximation algorithms. Deterministic algorithms usually provide probability bounds, but have an exponential runtime. Some randomized schemes have a polynomial runtime, but provide only probability estimates.

We present randomized algorithms that enumerate high-probability partial instantiations, resulting in probability bounds. Some of these algorithms are also sampling algorithms. Specifically, we introduce and evaluate a variant of backward sampling, both as a sampling algorithm and as a randomized enumeration algorithm. We also relax the implicit assumption used by both sampling and accumulation algorithms, that query nodes must be instantiated in all the samples.

Keywords:

Probabilistic Reasoning, Bayes Networks, Belief Updating, Approximation Algorithms, Sampling Algorithms, Genetic Algorithms.

Availability:

This paper is also available in (PostScript) format.