Average-Case Analysis of a Search Algorithm for Estimating Prior and Posterior Probabilities in Bayesian Networks with Extreme Probabilities

Poole, David

Average-Case Analysis of a Search Algorithm for Estimating Prior and Posterior Probabilities in Bayesian Networks with Extreme Probabilities

Download BibTeX Cite

Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 606-611.

Abstract

This paper provides a search-based algorithm for computing prior and posterior probabilities in discrete Bayesian Networks. This is an "anytime" algorithm, that at any stage can estimate the probabilities and give an error bound. Whereas the most popular Bayesian net algorithms exploit the structure of the network for efficiency, we exploit probability distributions for efficiency. The algorithm is most suited to the case where we have extreme (close to zero or one) probabilities, as is the case in many diagnostic situations where we are diagnosing systems that work most of the time, and for commonsense reasoning tasks where normality assumptions (allegedly) dominate. We give a characterisation of those cases where it works well, and discuss how well it can be expected to work on average.

David Poole. 1993. Average-Case Analysis of a Search Algorithm for Estimating Prior and Posterior Probabilities in Bayesian Networks with Extreme Probabilities. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93. IJCAI, 606–611. https://ijcai.org/proceedings/1993/85

@inproceedings{ijcai1993p85,
  title     = {Average-Case Analysis of a Search Algorithm for Estimating Prior and Posterior Probabilities in Bayesian Networks with Extreme Probabilities},
  author    = {Poole, David},
  booktitle = {Proceedings of the Thirteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-93}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ruzena Bajcsy},
  pages     = {606--611},
  year      = {1993},
  note      = {Knowledge Representation},
  url       = {https://ijcai.org/proceedings/1993/85},
}

TY  - CPAPER
TI  - Average-Case Analysis of a Search Algorithm for Estimating Prior and Posterior Probabilities in Bayesian Networks with Extreme Probabilities
AU  - Poole, David
T2  - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1993
SP  - 606
EP  - 611
UR  - https://ijcai.org/proceedings/1993/85
ER  -