|
|
|
| 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.
|
|
Received: 17 May 2010
|
|
|
|
|
|
[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 
