Refined Junction-Tree-Based Algorithm for Reasoning in Bayesian Network
HU Chun-Ling1,2, HU Xue-Gang1, YAO Hong-Liang1
1.School of Computer and Information, Hefei University of Technology, Hefei 230009 2.Key Laboratory of Network and Intelligent Information Processing, Hefei University, Hefei 230601
Abstract Two classical junction-tree-based algorithms for reasoning in Bayesian network, Shafer-Shenoy architecture and Hugin architecture,are analyzed and compared. For the limitation of the Hugin algorithm in the reasoning analysis, a refined Hugin algorithm, R-Hugin, is proposed, which introduces the zero-factor flag and zero-factor processing mechanism in the message propagation process of the Hugin algorithm. R-Hugin algorithm has good reasoning and analyzing performance. Meanwhile, the correctness and efficiency of the R-Hugin algorithm are validated by theory and experiments.
[1] Tian Fengzhan, Zhang Hongwei, Lu Yuchang, et al. Simplification of Inferences in Multiply Sectioned Bayesian Networks. Journal of Computer Research and Development, 2003, 40(8): 1230-1237 (in Chinese) (田凤占,张宏伟,陆玉昌,等. 多模块贝叶斯网络中推理的简化. 计算机研究与发展,2003, 40(8): 1230-1237) [2] Dechter R. Bucket Elimination: A Unifying Framework for Reasoning. Artificial Intelligence, 1999, 113(1/2): 41-85 [3] Zhang N L, Poole D. A Simple Approach to Bayesian Network Computations // Proc of the 10th Canadian Conference on Artificial Intelligence. Banff, Canada, 1994: 171-178 [4] Kask K, Dechter R. A General Scheme for Automatic Generation of Search Heuristics from Specification Dependencies. Artificial Intelligence, 2001, 129(1/2): 91-131 [5] Shafer G R, Shenoy P P. Probability Propagation. Annals of Mathematics and Artificial Intelligence, 1990, 2(1/2/3/4): 327-352 [6] Jensen F V, Olesen K G, Andersen S K. An Algebra of Bayesian Belief Universes for Knowledge-Based Systems. Networks, 1990, 20(5): 637-659 [7] Jensen F V, Lauritzen S L, Olesen K G. Bayesian Updating in Causal Probabilistic Networks by Local Computation. Computational Statistics Quarterly, 1990, 5(4): 269-282 [8] Ghosh J K, Dclampady M, Samanta T. An Introduction to Bayesian Analysis: Theory and Methods. Heidelberg, Germany: Springer-Verlag, 2006 [9] Jensen F V, Jensen F. Optimal Junction Trees // Proc of the 10th Conference on Uncertainty in Artificial Intelligence. Seattle, USA, 1994: 360-366 [10] Becker A, Geiger D. A Sufficiently Fast Algorithm for Finding Close to Optimal Junction Trees // Proc of the 12th Conference on Uncertainty in Artificial Intelligence. Portland, USA, 1996: 81-89 [11] Kask K, Dechter R, Larrosa J, et al. Unifying Tree Decompositions for Reasoning in Graphical Models. Artificial Intelligence, 2005, 166(1/2): 165-193 [12] Darwiche A. A Differential Approach to Inference in Bayesian Networks. Journal of the ACM, 2003, 50(35): 280-305 [13] Mateescu R, Kask K, Gogate V, et al. Join-Graph Propagation Algorithms. Journal of Artificial Intelligence Research, 2010, 37(1): 279-328 [14] Lepar V. Performance of Architectures for Local Computations in Bayesian Networks.Ph.D Dissertation. Fribourg, Switzerland: University of Fribourg, 1999
2011, Vol. 24 
