The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks

From Tetherless World Wiki

Jump to: navigation, search

Citation: Gregory F. Cooper. (1990) The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks. In KSL-90-34, 1990.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Gregory F. Cooper
title The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks
number KSL-90-34
institution Knowledge Systems, AI Laboratory
year 1990
Bibtex more
Access Paper
abstract 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.

KSL Technical Report ID: KSL-90-34
Facts about The Computational Complexity of Probabilistic Inference Using Bayesian Belief NetworksRDF feed
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  +
Bibtype techreport  +
Has author Gregory F. Cooper  +
Has identifier KSL-90-34  +
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  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-90-34  +
Number KSL-90-34  +
Process note YES  +
Title The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks  +
Year 1990  +
Retrieved from "http://tw.rpi.edu/wiki/The_Computational_Complexity_of_Probabilistic_Inference_Using_Bayesian_Belief_Networks"