KSL-90-34 + redirect page
The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks + Has identifier
The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks + Ksl tr id
The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks + Number
| The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks |
Bibtype
techreport
Has publishing details
1990
Has title
The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks
Has where published
KSL-90-34
Has year
1990
Title
The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks
Year
1990
Abstract
Bayesian belief networks provide a natural … Bayesian belief networks provide a natural, efficient method for representing probabilistic dependencies among a set of variables. For these reasons, numerous researchers are exploring the use of belief networks as a knowledge representation in artificial intelligence. Algorithms have been developed previously for efficient probabilistic inference using special classes of belief networks. More general classes of belief networks, however, have eluded efforts to develop efficient inference algorithms. We show that probabilistic inference using belief networks is NP-hard. Therefore, it seems unlikely that an exact algorithm can be developed to perform probabilistic inference efficiently over all classes of belief networks. This result suggests that research should be directed away from the search for a general, efficient probabilistic inference algorithm, and toward the design of efficient special-case, average-case, and approximation algorithms. verage-case, and approximation algorithms.
Author
Gregory F. Cooper +
Has author
Gregory F. Cooper +
Has identifier
The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks +
Institution
Knowledge Systems, AI Laboratory +
Ksl tr id
The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks +
Number
The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks +
Process note
YES +
Categories KSL Technical Report +, Publication +, Technical Report +
|
