Reference: Dagum, P. & Chavez, R. M. Approximating Probabilistic Inference in Bayesian Belief Networks. 1991.
Abstract: We design an approximation algorithm for probabilistic inference in belief networks. For any pair of positive reals e<1 and d<1 our algorithm outputs an estimate of the computed inference that is guaranteed to lie within a relative error e with probability at least 1-d. Such an algorithm is known as a randomized approximation scheme (ras). A ras provides a priori bounds on the running time required in terms of the parameters of the approximation, e and d. An a priori bound allows the level of accuracy of the approximation to be determined by resource constraints. This is valuable, for example, in decision analysis in time-dependent environments. We characterize belief networks by their independence value, I. Intuitively, the independence value gives a measure of the cumulative strength of the dependencies among nodes in a belief network that are encoded by the conditional probabilities associated with each node. When I is bounded by a polynomial in the size of the belief network, n, our algorithm has polynomial running time in n. We prove that computing probabilistic inference for this class of belief networks is #P-hard, (harder than the class of NP-complete problems) and therefore, computing inferences by exact algorithms is intractable for this class. Furthermore our algorithm is faster than any exact algorithm for belief networks with I that is O(2^c) for some constant c<1/4. Thus, the results of this paper are the first to show that an approximation algorithm is a provably faster algorithm than any exact algorithm for certain large and well characterized classes of belief networks. Other approximation algorithms such as forward simulation, straight simulation, and likelihood weighting have exponential running time when the computed inferences approach 0. Since the running time of our algorithm is independent of how close the computed inferences are to zero, our algorithm is faster than other approximation algorithms for approximating these inferences.