摘要
贝叶斯网络提供了一套强有力的图形工具来表达基于概率的领域知识,是对人工智能领域中不确定性问题进行表示和处理的一种重要工具,已被成功应用于故障诊断、数据挖掘和医疗诊断等领域。动态贝叶斯网络是贝叶斯网络在时间因素上的扩展,是对人工智能领域中动态不确定性问题进行表示和处理的一种重要工具。本文在对贝叶斯网络进行全面概述的基础上,对贝叶斯网络和动态贝叶斯网络的近似推理进行了研究。全文的主要内容如下:
(1)贝叶斯网络的概述。概述了贝叶斯网络的起源与发展,详细介绍了贝叶斯网络模型、贝叶斯网络的构建过程、贝叶斯网络的类型以及贝叶斯网络的应用,并在此基础上,对动态贝叶斯网络进行了概述;概述了贝叶斯网络的主要研究内容,并对贝叶斯网络和动态贝叶斯网络的推理算法进行了重点介绍。
(2)在贝叶斯网络近似推理方面,针对贝叶斯网络的马尔可夫链蒙特卡洛(Markov Chain Monte Carlo,MCMC)推理存在的问题,本文以MCMC推理算法中具有代表性的Gibbs抽样为基本框架,提出一种贝叶斯网络的并行MCMC(Parallel MCMC,PMCMC)推理方法,在生成马尔可夫链的组成序列时,通过增加对贝叶斯网络中每个结点的抽样频率,即加大样本数来提高其推理精度,并在消息传递接口MPI的支持下,利用主从式并行机制来实现其推理过程,以保证推理的时间性能。在3个不同贝叶斯网络即Asia、Mildew和Alarm网上的推理实验结果表明,PMCMC在提高推理精度的同时有效保证了推理的时间性能。
(3)在动态贝叶斯网络近似推理方面,针对动态贝叶斯网络的粒子滤波推理存在的问题,本文将离散粒子群优化技术引入到传统粒子滤波推理中,提出一种新的粒子滤波算法—进化粒子滤波(Evolutionary Particle Filtering,EPF)。在进化粒子滤波中,利用离散粒子群优化技术的迭代寻优能力重新分配粒子,使粒子的表示更加接近真实后验概率密度,以提高粒子滤波推理的精度性能。在2个不同动态贝叶斯网络上的概率推理实验结果表明,与传统的粒子滤波推理算法相比,EPF利用较少的粒子就可以取得较好的推理精度。
Bayesian network provides a powerful graph tool to express domain knowledge based on probability. It has becomes an important methodology for representing and computing uncertain problem of stochastic processes in the field of artificial intelligence, and it has been successfully applied to fault diagnosis, data mining, medical diagnosis, and other fields. Dynamic Bayesian network is a Bayesian network with the expansion on the factor of time, it provides a powerful tool to represent and deal with dynamic uncertain problem of stochastic processes in the field of artificial intelligence. Based on the comprehensive overview of Bayesian network, this thesis focuses on the research of approximate inference algorithm for Bayesian network and dynamic Bayesian network. The main contents of this thesis are as follows:
(1) This thesis makes a survey about the research on Bayesian network, including the origin, development, the model, the construction process, the type and the application of Bayesian network. On basis of this, dynamic Bayesian network is introduced. And, the main research contents of Bayesian network are summarized. Moreover, the inference algorithms for Bayesian network and dynamic Bayesian network are introduced in detail.
(2) In the approximate inference of Bayesian network, to deal with the existing problems of Markov Chain Monte Carlo (MCMC) inference algorithm, taking Gibbs sampling as an example, a parallel MCMC (PMCMC) inference algorithm for Bayesian network is proposed. To improve the accuracy, larger samples are used in PMCMC when generating the sequence of Markov chain. Moreover, to guarantee the inference speed, the algorithm has been implemented using the Master-Slave parallel programming model with the support of MPI. The experiment results on three different Bayesian networks show that PMCMC can achieve higher accuracy without the loss of time performance.
(3) In the approximate inference of dynamic Bayesian network, to improve the performance of particle filtering (PF) inference algorithm, discrete particle swarm optimization (DPSO) technique is introduced to form a new filter called the evolutionary particle filter (EPF), in which the iterative search and optimization procedure of DPSO is used to redistribute particles closer to the true posterior density. The experimental results on two different dynamic Bayesian networks show that EPF can achieve better accuracy with fewer particles.
引文
[1] Pearl J. Fusion, propagation, and structuring in belief networks[J]. Artificial Intelligence, 1986, 29:241-288.
[2] Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference[M], Morgan Kaufman Publishers, Inc., San Mateo, CA, 2nd Edition,1988.
[3] Jensen F V. An introduction to Bayesian networks[M]. New York: Springer Press, 1996.
[4] Miao A X, Zacharias G L, Shih-Ping Kao. A computational situation assessment model for nuclear power plant operations[J]. IEEE Transactions on SMC, 1997,27(6):728-742.
[5] Heckerman D. Bayesian networks for data mining[J]. Data Mining and Knowledge Discovery, 1997, 1:79-119.
[6] Kahn C E, Roberts L M, Haddawy P. Construction of a Bayesian networks for mammographic diagnosis of breast cancer[J]. Computation of Biology Medicine, 1997, 27(l):19-29.
[7] Casto E, Gutierrez J M, Hadi A S. Expert systems and probabilistic network models. Springer Verlag, New York, 1997.
[8] Heckerman D, Geiger D, Chickering D M. Learning Bayesian networks: The combination of knowledge and statistical data[J]. Machine Learning,1995:197-243.
[9] Murphy K P, Mian S. Modelling gene expression data using dynamic Bayesian networks. Berkeley: Computer Science Division, University of California,1999.
[10] Murphy K. Dynamic Bayesian networks: representation, inference and learning[D]. Doctor of Philosophy dissertation, University of California,Berkeley, 2002.
[11] Kuenzer A, Schlick C, Ohmann F, et al. An empirical study of dynamic Bayesian networks for user modeling[C]. Proceedings of the UM2001 Workshop on Machine Learning for User Modeling, 2001:1-10.
[12] Oliver N, Rosario B, Pentland A. Graphical models for recognizing human interactions[C]. Proceedings of Neural Information Processing Systems, 1998.
[13] Ghahramani Z. An introduction to hidden Markov models and Bayesian networks[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2001, 15(1):9-42.
[14]王辉.用于预测的贝叶斯网络[J].东北师范大学学报(自然科学版),2002,34(1):9-14.
[15]刘启元,张聪,沈一栋.信度网推理——方法及问题(上)(J).计算机科学,2001,28(1):74-77.
[16]Cooper G F,Herskovits E.A Bayesian method for the induction of probabilistic networks from data[J],Machine Learning,1992,9:309-347
[17]Heckerman D.A tutorial on learning Bayesian networks[R],New York:Technical Report MRS-TR-95-06,Mocrosoft Research.
[18]刘启元,张聪,沈一栋.信度网推理——方法及问题(下)(J).计算机科学,2001,28(2):115-118.
[19]Dechter R.Bucket elimination:A unifying framework for probabilistic inference[C],In Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence,1996:211-219.
[20]Finn Verner Jensen,Frank Jensen.Optimal junction trees[C],UAI1994,1994:360-366.
[21]Cooper G F.Computational complexity of probability inference using Bayesian belief networks[J].Artificial Intelligence,1993,15:246-255.
[22]刘启元,张聪,沈一栋.信度网近似推理算法(上)[J].计算机科学,2001,28(1):70-73.
[23]刘启元,张聪,沈一栋.信度网近似推理算法(下)[J].计算机科学,2001,28(2):111-114.
[24]Thomas Back,Jeannette M.de Graaf,Joost N.Kok,Walter A.Kosters,Theory of genetic algorithms[J],Current Trends in Theoretical Computer Science,2001:546-578
[25]Lauritzen S L,Spiegelhalter D J.Local computation with probabilities on graphical structure and their application to expert system[J].Roy.Stat.Soc.B,1998(50):157-224.
[26]Sharer G R,Shenoy P P.Probability propagation[J].Annals of Mathematics and Artificial Intelligence,1990(2):327-352.
[27]张颖,刘艳秋编著软计算方法[M].北京:科学出版社,2002.
[28](美)S Russell,P Norvig.人工智能——一种现代方法(第二版)[M].姜哲,金奕江,等.北京:人民邮电出版社,2004.
[29]周本达,王浩,姚宏亮.1 1/2片联合树算法在动态贝叶斯网精确推理中的应用[J].计算机工程与应用,2005,41(14):81-84.
[30]Boyen X,Kollen D.Tractable inference for complex stochastic processes[C]. In Proc.Of UAI-98,1998:33-42.
[31]Murphy K,Weiss Y.The factored frontier algorithm for approximate inference in DBNs[C].In Proc.Of UAI-01,2001:378-385.
[32]Paskin M A.Thin junction tree filters for simultaneous localization and mapping[C].In proc.Of IJCAI-03,2003:1157-1164.
[33]Arulampalam M S,Maskell S,Gordon N,et al.A Tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking[J].IEEE Transactions on Signal Processing,2002,50(2):174-188.
[34]Doucet A.de Freitas N,Murphy K.Rao-blackwellised particle filtering for dynamic Bayesian networks[C].In Proceedings of the UAI-16th,2000:253-259.
[35]Brenda Ng,Avi Pfeffer,Dearden R,Hutter F.Factored sampling for monitoring nonlinear hybrid systems with autonomous transitions[C].Submitted to the Conference on Uncertainty in Artificial Intellingence,2004.
[36]Andrieu C,de Freitas N,Doucet A et al.An Introduction to MCMC for machine learning[J].Machine Learning,2003,50:5-43.
[37]汪成亮,沈文武,张勤.因果图中高效并行GIBBS仿真算法的研究[J].计算机仿真,2004,21(11):77-79.
[38]Pearl,J.Evidential reasoning using stochastic simulation of causal models[J].Artificial Intelligence,1987,32:245-257.
[39]Norsys Software Corp.,http://www.norsys.com,2006.
[40]都志辉.高性能计算并行编程技术.MPI并行程序设计[M].北京:清华大学出版社,2001.
[41]Burns G,Daoud R,Vaigl J.LAM:an open cluster environment for MPI[C].Proceedings of Supercomputing Symposium,1994:379-386.
[42]Gropp W,Lusk E.User's guide for mpich,a portable implementation of MPI[R].Technical Report ANL-96/6,Argonne National Laboratory,1994.
[43]胡士强,敬忠良.粒子滤波算法综述[J].控制与决策,2005,20(4):361-371.
[44]Doucet A,Godsill S,Andrieu C.On sequential Monte Carlo sampling methods for Bayesian filtering[J].Statistics and Computing,2000,10(3):197-208.
[45]Kotecha J H,Djuric P M.Gaussian particle filtering[J].IEEE Transactions on Signal Processing,2003,51(10):2592-2601.
[46]Eberhart R C,Kennedy J A.A new optimizer using particle swarm theory[C].Nagoya,Japan:Proceedings of the Sixth International Symposium on Micro Machine and Human Science,1995:39-43.
[47]Kennedy J,Eberhart R C.Particle swarm optimization[C].Perth,Australia: Proceedings of IEEE International Conference on Neural Networks,1995:1942-1948.
[48] Kennedy J, Eberhart R. A discrete binary version of the particle swarm optimization[C]. Proceedings of the World Multiconference on Systemics,Cybernetics and Informatics. Piscataway, NJ: IEEE Service Center, 1997:4104-4109.
[49] Carlin B P, Poison N G, Stoffer D S. A Monte Carlo approach to nonnormal and nonlinear state-space modeling[J]. Journal of the American Statistical Association, 1992, 87(418):493-500.
[50] Doucet A, Godsill S. On sequential Monte Carlo sampling methods for Bayesian filtering [R], Cambridge: University of Cambridge, 1998:1-36.
[51] Liu J S, Chen R. Sequential Monte Carlo methods for dynamic systems[J],Journal of the American Statistical Association, 1998,93(5):1032-1044
[52] Gordon N, Salmond D. Novel approach to non-linear and non-Gaussian Bayesian state estimation[J], Proc of Instirute Electric Engineering, 1993,140(2):107-113.
[53] Liu J S, Chen R. Blind deconvolution via sequential imputation[J], Journal of the American Statistical Association, 1995.90(2):567-576.
[54] Bergman N. Recursive Bayesian estimation: navigation and tracking applications[D]. Linkoping, Sweden: Linko|¨ping University, 1999.
[55] Kjaerulff U. dHugin: A computational system for dynamic time-sliced Bayesian networks[J], International Journal of Forecasting, Special Issue on Probability Forcasting, 1995,11:89-111.
[56] Shi Y, Eberhart R C. Empirical study of particle swarm optimization[C].Piscataway, NJ: Proceedings of the 1999 Congress on Evolutionary Computation, 1999:1945—1950.
