Abstract
In this paper, we revisit the consensus of computational complexity on exact inference in Bayesian networks. We point out that even in singly connected Bayesian networks, which conventionally are believed to have efficient inference algorithms, the computational complexity is still NP-hard.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Cooper, G.F.: The computational complexity of probabilistic inference using bayesian belief networks. Artificial Intelligence 42(2-3), 393–405 (1990)
Garey, M.R., Johnson, D.D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Jensen, F.V., Lauritzen, S.L., Olesen, K.G.: Bayesian updating in causal probabilistic networks by local computation. Computational Statistics Quarterly 4, 269–282 (1990)
Lauritzen, S.L., Spiegelhalter, D.J.: Local computation with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society 50, 157–244 (1988)
Lepar, V., Shenoy, P.P.: A comparison of Lauritzen-Spiegelhalter, Hugin, and Shenoy-Shafer architectures for computing marginals of probability distributions. In: Cooper, G.F., Moral, S. (eds.) Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI 1998), July 24-26 1998, pp. 328–337. Morgan Kaufmann, San Francisco (1998)
Pearl, J.: Fusion, propagation, and structuring in belief networks. Artificial Intelligence 29, 241–288 (1986)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, San Francisco (1988)
Russell, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 2nd edn. Prentice-Hall, Englewood Cliffs (2003)
Shafer, G.: Probabilistic Expert Systems. Society for Industrial and Applied Mathematics (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wu, D., Butz, C. (2005). On the Complexity of Probabilistic Inference in Singly Connected Bayesian Networks. In: Ślęzak, D., Wang, G., Szczuka, M., Düntsch, I., Yao, Y. (eds) Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. RSFDGrC 2005. Lecture Notes in Computer Science(), vol 3641. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11548669_60
Download citation
DOI: https://doi.org/10.1007/11548669_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28653-0
Online ISBN: 978-3-540-31825-5
eBook Packages: Computer ScienceComputer Science (R0)