KSL-91-46 + redirect page
Approximating Probabilistic Inference in Bayesian Belief Networks + Has identifier
Approximating Probabilistic Inference in Bayesian Belief Networks + Ksl tr id
Approximating Probabilistic Inference in Bayesian Belief Networks + Number
| Approximating Probabilistic Inference in Bayesian Belief Networks |
Bibtype
techreport
Has publishing details
1991
Has title
Approximating Probabilistic Inference in Bayesian Belief Networks
Has where published
KSL-91-46
Has year
1991
Title
Approximating Probabilistic Inference in Bayesian Belief Networks
Year
1991
Abstract
We design an approximation algorithm for p … 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. rithms for approximating these inferences.
Author
Paul Dagum and R. Martin Chavez +
Has author
Paul Dagum and R. Martin Chavez +
Has identifier
Approximating Probabilistic Inference in Bayesian Belief Networks +
Institution
Knowledge Systems, AI Laboratory +
Ksl tr id
Approximating Probabilistic Inference in Bayesian Belief Networks +
Number
Approximating Probabilistic Inference in Bayesian Belief Networks +
Process note
YES +
Categories KSL Technical Report +, Publication +, Technical Report +
|
