An optimal approximation algorithm for Bayesian inference

Approximating the inference probability Pr[X = xjE = e] in any sense, even for a single evidence node E, is NP-hard. This result holds for belief networks that are allowed to contain extreme conditional probabilities|that is, conditional probabilities arbitrarily close to 0. Nevertheless, all previous approximation algorithms have failed to approximate e ciently many inferences, even for belief networks without extreme conditional probabilities. We prove that we can approximate e ciently probabilistic inference in belief net-works without extreme conditional probabilities. We construct a randomized approx-imation algorithm|the bounded-variance algorithm|that is a variant of the known likelihood-weighting algorithm. The bounded-variance algorithm is the rst algorithm with provably fast inference approximation on all belief networks without extreme con-ditional probabilities. From the bounded-variance algorithm, we construct a deterministic approximation algorithm using currentadvances in the theory of pseudorandom generators. In contrast to the exponential worst-case behavior of all previous deterministic approximations, the deterministic bounded-variance algorithm approximates inference probabilities in worst-(log n)d case time that is subexponential 2, for some integer d that is a linear function of the depth of the belief network