Logarithmic Time Parallel Bayesian Inference

2013/01/30 by David M. Pennock, Pennock, David M.
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #cs.AI

paper · pdf · doi:10.48550/arxiv.1301.7406

Appears in Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI1998)

arxiv created 2013/01/30 · arxiv updated 2013/02/01

Abstract

I present a parallel algorithm for exact probabilistic inference in Bayesian networks. For polytree networks with n variables, the worst-case time complexity is O(log n) on a CREW PRAM (concurrent-read, exclusive-write parallel random-access machine) with n processors, for any constant number of evidence variables. For arbitrary networks, the time complexity is O(r^3w*log n) for n processors, or O(w*log n) for r^3w*n processors, where r is the maximum range of any variable, and w is the induced width (the maximum clique size), after moralizing and triangulating the network.

Related

• Logarithmic-Time Updates and Queries in Probabilistic Networks
• A Parallel Algorithm for Exact Bayesian Structure Discovery in Bayesian Networks
• Parallelizing Probabilistic Inference: Some Early Explorations
• Pruning Bayesian Networks for Efficient Computation
• Discrete Bayesian Networks: The Exact Posterior Marginal Distributions