Learning Bayesian Networks Using a Parallel EM Approach

YU Kui, WANG Hao, WU Xin-Dong, YAO Hong-Liang

PDF(538 KB)
Pattern Recognition and Artificial Intelligence ›› 2008, Vol. 21 ›› Issue (5) : 670-676.
Researches and Applications

Learning Bayesian Networks Using a Parallel EM Approach

Author information +
History +

Abstract

Computing the expected statistics is the main bottleneck in learning Bayesian networks. Firstly, a parallel expectation-maximization (PL-EM) algorithm for leaning Bayesian network parameters is presented. The PL-EM algorithm parallelizes the E-step and M-step and the greatly reduces the time complexity of the parameter learning. Then PL-EM algorithm is applied to learning Bayesian networks structure, and a parallel learning algorithm is proposed for learning Bayesian networks based on an existing structural EM algorithm (SEM), called PL-SEM. PL-SEM exploits PL-EM algorithm to compute the expected statistics at the structural E_Step. Thus, it can implement the parallel computation of the expected statistics and greatly reduce the time complexity of learning Bayesian networks.

Key words

Bayesian Networks / Parameter Learning / Structural Learning / Expectation-Maximization (EM) Algorithm / Message Passing Interface (MPI) Library

Cite this article

Download Citations
YU Kui , WANG Hao , WU Xin-Dong , YAO Hong-Liang. Learning Bayesian Networks Using a Parallel EM Approach. Pattern Recognition and Artificial Intelligence. 2008, 21(5): 670-676

References

[1] Ghahramani Z. An Introduction to Hidden Markov Models and Bayesian Networks. Journal of Pattern Recognition and Artificial Intelligence, 2001, 15(1): 9-42
[2] Chickering D M, Heckerman D. Efficient Approximations for the Marginal Likelihood of Bayesian Networks with Hidden Variables. Machine Learning, 1997, 29(2/3): 181-221
[3] Wang Shuangcheng, Yuan Senmiao. Research on Learning Bayesian Networks Structure with Missing Data. Journal of Software, 2004, 15(7): 1042-1048 (in Chinese)
(王双成,苑森淼.具有丢失数据的贝叶斯网络结构学习研究. 软件学报, 2004, 15(7): 1042-1048)
[4] Friedman N. The Bayesian Structural EM Algorithm // Proc of the 14th Conference on Uncertainty in Artificial Intelligence. Madison, USA, 1998: 129-168
[5] Neal R M, Hinton G E. A View of the EM Algorithm That Justifies Incremental, Sparse, and Other Variants // Proc of the NATO Advanced Study Institute on Learning in Graphical Models. Norwell, USA, 1998: 355-368
[6] Thiesson B, Meek C, Heckerman D. Accelerating EM for Large Databases. Machine Learning, 2001, 45(3): 279-299
[7] Myers J W, Laskey K B, de Tong K A. Learning Bayesian Networks from Incomplete Data Using Evolutionary Algorithms // Proc of the Conference on Genetic and Evolutionary Computation. Orlando, USA, 1999: 458-465
[8] Tian Fengzhen, Lu Yuchang, Shi Chunyi. Learning Bayesian Networks with Hidden Variables Using the Combination of EM and Evolutionary Algorithms // Proc of the Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Hongkong, China, 2001: 568-574
[9] Luna J E O, Zanusso M B, Revisited E M. Algorithms for Learning Structure and Parameters in Bayesian Networks // Proc of the International Conference on Artificial Intelligence. Las Vegas, USA, 2005: 572-578
[10] Jeng W M, Huang S H S. Inter-Iteration Optimization of Parallel EM Algorithm on Message-Passing Multicomputers // Proc of the IEEE International Conference on Parallel Processing. Minneapolis, USA, 1998: 245-252
[11] Chen C M, Lee S Y. Optimal Data Replication: A New Approach to Optimizing Parallel EM Algorithms on a Mesh-Connected Multiprocessor for 3D PET Image Reconstruction. IEEE Trans on Nuclear Science, 1995, 42(4): 1235-1245
[12] Kruengkrai C, Jaruskulchai C. A Parallel Learning Algorithm for Text Classification // Proc of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada, 2002: 201-206
[13] Leonid G, Gagan A. Parallelizing EM Clustering Algorithm on a Cluster of SMPs // Proc of the International Euro-Par Conference. Pisa, Italy, 2004: 372-380
[14] Chu Tongsheng, Xiang Yang. Exploring Parallelism in Learning Belief Networks // Proc of the 13th Conference on Uncertainty in Artificial Intelligence. Providence, USA, 1997: 90-98
[15] Lam W, Segre A M. A Distributed Learning Algorithm for Bayesian Inference Networks. IEEE Trans on Knowledge and Data Engineering, 2002, 14(1): 93-105
[16]Munetomo M, Murao N, Akama K. Empirical Studies on Parallel Network Construction of Bayesian Optimization Algorithms // Proc of the IEEE Congress on Evolutionary Computation. Edinburgh, UK, 2005: 1524-1531
[17] Gropp W, Lusk E, Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. Cambridge, USA: MIT Press, 1999
[18] Norsys Software Corp. Netica [DB/OL]. [2007-03-27]. http://www.norsys.com
PDF(538 KB)

774

Accesses

0

Citation

Detail

Sections
Recommended

/