Logarithmic Time Parallel Bayesian Inference
This work addresses the computational bottleneck of Bayesian inference for researchers and practitioners in AI and machine learning, offering a significant speedup through parallelization, though it is incremental in building on existing inference methods.
The paper tackles the problem of exact probabilistic inference in Bayesian networks by presenting a parallel algorithm that achieves O(log n) worst-case time complexity for polytree networks and O(r^{3w}*log n) for arbitrary networks on a CREW PRAM with n processors.
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.