Parallel Exact Inference on Multicore Using MapReduce

• Nam Ma University of Southern California
• Yinglong Xia IBM Thomas J. Watson Research Center
• Viktor K. Prasanna University of Southern California

Resumo

Inference is a key problem in exploring probabilistic graphical models for machine learning algorithms. Recently, many parallel techniques have been developed to accelerate inference. However, these techniques are not widely used due to their implementation complexity. MapReduce provides an appealing programming model that has been increasingly used to develop parallel solutions. MapReduce though has been mainly used for data parallel applications. In this paper, we investigate the use of MapReduce for exact inference in Bayesian networks. MapReduce based algorithms are proposed for evidence propagation in junction trees. We evaluate our methods on general-purpose multi-core machines using Phoenix as the underlying MapReduce runtime. The experimental results show that our methods achieve 20x speedup on an Intel West mere-EX based system.

Palavras-chave: Junctions, Bayesian methods, Particle separators, Parallel processing, Inference algorithms, Runtime, Complexity theory, exact inference, data dependency, MapReduce, multi-core