Logarithmic time parallel Bayesian inference
作者： David M. Pennock
DOI:
关键词:
摘要: I present a parallel algorithm for exact probabilistic inference in Bayesian networks. For polytree networks with n variables, the worstcase time complexity is O(logn) on CREW PRAM (concurrent-read, exclusive-write random-access machine) processors, any constant number of evidence variables. arbitrary networks, O(r3w log n) or O(w r3w where r maximum range variable, and w induced width (the clique size), after moralizing triangulating network.
arxiv.org参考文章(23)
Kristian G. Olesen, Finn V. Jensen, Steffen L. Lauritzen, Bayesian updating in causal probabilistic networks by local computations Computational Statistics Quarterly. ,vol. 4, pp. 269- 282 ,(1990)
Ton Kloks, Treewidth: Computations and Approximations ,(1994)
Bruce D'Ambrosio, Tony Fountain, Zhaoyu Li, Parallelizing probabilistic inference: some early explorations uncertainty in artificial intelligence. pp. 59- 66 ,(1992) , 10.1016/B978-1-4832-8287-9.50013-X
Ross D. Shachter, Evidence Absorption and Propagation through Evidence Reversals uncertainty in artificial intelligence. ,vol. 10, pp. 173- 190 ,(1990) , 10.1016/B978-0-444-88738-2.50021-X
Paul Spirakis, Alan Gibbons, Lectures on parallel computation Cambridge University Press. ,(1993)
S. L. Lauritzen, D. J. Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems Journal of the royal statistical society series b-methodological. ,vol. 50, pp. 415- 448 ,(1990) , 10.1111/J.2517-6161.1988.TB01721.X
Ross D. Shachter, Kim-Leng Poh, Stig K. Andersen, Directed reduction algorithms and decomposable graphs uncertainty in artificial intelligence. pp. 197- 208 ,(1990)
K Abrahamson, N Dadoun, D.G Kirkpatrick, T Przytycka, A simple parallel tree contraction algorithm Journal of Algorithms. ,vol. 10, pp. 287- 302 ,(1989) , 10.1016/0196-6774(89)90017-5
Gregory F. Cooper, The computational complexity of probabilistic inference using bayesian belief networks Artificial Intelligence. ,vol. 42, pp. 393- 405 ,(1990) , 10.1016/0004-3702(90)90060-D
Richard E. Neapolitan, Probabilistic Reasoning In Expert Systems: Theory and Algorithms ,(2012)