KSL-91-46
## Approximating Probabilistic Inference in Bayesian Belief Networks

**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.

*Jump to*...
[KSL]
[SMI]
[Reports by Author]
[Reports by KSL Number]
[Reports by Year]

Send mail to:
ksl-info@ksl.stanford.edu to send a message to the maintainer of the
KSL Reports.