On State-Space Abstraction for Anytime Evaluation of Bayesian Networks

ion for Anytime Evaluation of Bayesian Networks Chao-Lin Liu and Michael P. Wellman University of Michigan AI Laboratory Ann Arbor, MI 48109-2110 USA fchaolin, wellmang@umich.edu Abstract Despite the increasing popularity of Bayesian networks for representing and reasoning about uncertain situations, the complexity of inference in this formalismremains a significant concern. A viable approach to relieving the problem is trading off accuracy for computational efficiency. To this end, varying the granularity of state space of state variables appears to be a feasible strategy for controlling the evaluation process. We consider an anytime procedure for approximate evaluation of Bayesian networks based on this idea. On application to some simple networks, the procedure exhibits a smooth improvement in approximation quality as computation time increases. With the aim of developing principled control techniques, we also conduct a theoretical analysis of the quality of approximation. Our m..