东北大学学报:自然科学版 ›› 2015, Vol. 36 ›› Issue (9): 1251-1255.DOI: 10.3969/j.issn.1005-3026.2015.09.008

• 信息与控制 • 上一篇    下一篇

一种改进的多模块贝叶斯网络局部推理算法

赵建喆, 李凯   

  1. (东北大学 工商管理学院, 辽宁 沈阳110819)
  • 收稿日期:2014-08-25 修回日期:2014-08-25 出版日期:2015-09-15 发布日期:2015-09-14
  • 通讯作者: 赵建喆
  • 作者简介:赵建喆(1982-),女,吉林白山人,东北大学博士研究生; 李凯(1957-),男,辽宁昌图人,东北大学教授,博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(61202085);教育部高等学校博士学科点专项科研基金资助项目(2012004,2120010).

An Improved Local Inference Algorithm for Multiply Sectioned Bayesian Networks

ZHAO Jian-zhe, LI Kai   

  1. School of Business Administration, Northeastern University, Shenyang 110819, China.
  • Received:2014-08-25 Revised:2014-08-25 Online:2015-09-15 Published:2015-09-14
  • Contact: ZHAO Jian-zhe
  • About author:-
  • Supported by:
    -

摘要: 针对多模块贝叶斯网络的局部推理的时间和空间复杂度高的问题,提出了一种改进的多模块贝叶斯网络局部推理算法.该算法用面向对象语言重新定义了多模块贝叶斯网络模型,在联合树推理算法的基础上结合图论中“顶点度”的概念对局部推理算法进行了优化,针对三角化结果不唯一的问题,给出了一种一般性的解决方案,使三角化后的结果能够将消息传递得更快,有效地缩短推理时间.给出了算法的仿真实例并进行实验分析,结果表明改进后的推理算法有效减小时间、空间复杂度.

关键词: 多模块贝叶斯网络(MSBN), 局部推理, 联合树算法, 顶点度, 三角化

Abstract: Due to the temporal and spatial complexity in the local inference of multiply sectioned Bayesian networks (MSBN), an improved algorithm for the local inference of MSBN was proposed. The algorithm redefined the model of MSBN with an object-oriented language. Combined with the concept of vertex degree in graph theory, the algorithm was optimized based on the joint tree algorithm. Considering that the outcome of triangulation was not single, the improved algorithm offered a general solution, which helped to convey message faster and greatly shorten inference time. Finally, an instance of the algorithm was given for experimental analysis, whose results showed that the improved inference algorithm significantly reduces both temporal and spatial complexity.

Key words: multiply sectioned Bayesian network, local inference, joint tree algorithm, vertex degree, triangulation

中图分类号: