20世纪90年代以来,贝叶斯网络(Bayesian networks,BNs)成为人工智能、决策科学、机器学习、模式识别等众多分支学科中的理论研究热点.目前,随着应用领域的数据存储量增大,在大数据环境下对 复杂的贝叶斯网络进行推理并提高时间效率对传统的贝叶斯网络提出了较大挑战.已证明传统的贝叶斯网络的推理是一个NP-hard问题[1].
Koller等科学家将模块化和面向对象的思想引入到贝叶斯网络中[2],提出多模块贝叶斯网络(multiply sectioned Bayesian networks,MSBNs).MSBNs是贝叶斯网络的一种拓展,将大型的复杂网络分解为几个子网分别进行建模,并且将子网抽象成类,使得子网具有良好的复用性与封装性,解决了复杂网络模型的构造问题.目前,MSBNs的研究将传统贝叶斯网络忽视的结构化信息(层次结构、数据类型结构)重新变成研究的重点,并利用结构化知识改进BNs,从而增强贝叶斯网络的解释性,降低贝叶斯网络推理的复杂度.MSBNs的推理可分为每个贝叶斯子网中的局部推理以及子网与子网之间的全局推理两个层次,整个推理可以通过有限次 局部推理完成[3,4].局部推理中应用了许多经典贝叶斯网络的推理算法,精确推理算法与近似推理算法都可以应用到局部推理中.
许多学者对实际应用领域中的MSBNs建模研究,将一些相同或类似的子系统抽象成类.郭文强等应用MSBN对农业车辆处于复杂农田环境的识别信度定量分析问题进行研究[5].此类研究需要对类进行具有实际意义的子网划分,这对问题本身有一定的要求.2003年清华大学的田凤占等 [6]通过实验证明多模块贝叶斯网络推理算法的时空复杂度主要取决于各个子网的推理复杂度,并指出在模型建立初期就应该尽量简化子系统的内部结构,将整个系统划分为若干个松散耦合的稀疏网络的子系统.
联合树算法是通过步骤的共享来加快推理的一种算法[7].许多科学家为了使消息传播的速度更快,在联合树算法的基础上提出了基于传统推理算法的拓展算法,例如,Shafer-Shenoy and lazy propagation算法[8],这些算法能够加快信息的收集和传播速度.但是这些算法普遍存在对树形结构进行三角化的过程中三角化方案不唯一的问题[9].三角化的不唯一直接导致联合树树形结构的不同,最终导致消息传递的路径不同,会对推理的时间和空间复杂度造成较大影响.
针对这一问题,本文提出一种基于联合树算法改进的多模块贝叶斯网络局部推理算法,该算法结合图论中“顶点度”的概念,提出一种一般性的三角化方案.“顶点度”表示的是节点与其邻居节点之间关联边的个数,节点顶点度数越大表示其与周围节点关联越多,消息传递的范围越广.因此,在三角化的时候将“顶点度”考虑在内,从而保证消息最大范围的传播,加快推理的进行.
1 面向对象的MSBN模型及改进的局部推理算法 1.1 面向对象的MSBN模型MSBNs提出了引入面向对象思想的贝叶斯网络,为搭建面向对象思想的贝叶斯网络模型提供了研究方向与框架,但是并没有通过面向对象编程语言对模型进行具体的定义.本文提出一个面向对象的MSBN模型,用面向对象的编程语言对多模块贝叶斯网络的元素进行定义,并且确定了模型中的存储结构.面向对象的MSBN模型,将贝叶斯网络划分成子网并将相同或类似的子网结构抽象成类,使其具有继承、封装、多态的特性,为以后的推理计算以及参数、结构学习提供了前提与基本框架.
定义1 节点类(Node).节点类是对贝叶斯网络节点的一个抽象,一个节点类对应一个节点,即随机变量将其属性进行封装.节点类中包含属性:名字(Name),编号(Number),状态(State),顶点度(Degree)和条件概率参数(CPD).节点类是一个MSBN子网中最小的结构单元,其数据结构如下:
Class Node{
attributes:
-Name;
-Number;//从0开始计数
-State;
-CPD;
-Degree;//先默认为0,在联合树算法中构建Moral图后再赋值
}
定义2 边(Directededge[i][j]).定义矩阵
来表示节点之间的关系,即贝叶斯网络中连接节点的边,其中,x为节点名字,i,j为节点编号.矩阵中每行代表节点的出度,每列代表节点的入度,出度为零的节点为叶子节点,没有子节点,入度为零的节点为根节点,其没有父节点.但是,根节点不代表是信息输入节点,可能有许多根节点但是只有部分节点集合是信息输入节点;叶子节点也同理,并不是所有叶子节点都是信息输出节点.除此之外,因为贝叶斯网络是一个有向无环图,所以对角线上的数值全部为零.定义3 子网类(SubNetwork).子网类是模型中拥有相同或相似网络结构的贝叶斯网络的抽象.子网中包含贝叶斯网络的基本元素:节点Nodes与边Directededge[][],同时它还应该包含多模块贝叶斯网络特有的属性:消息传入节点InputNodes、消息传出节点OutputNodes以及一般节点NormalNodes.根据不同的推理方法可以在子网类中定义不同的推理函数inference()进行不同的概率推理算法,其数据结构如下:
Class SubNetwork{
attributes:
-Nodes;
-Directededge[][];
-Name;
-InputNodes;
-OutputNodes;
-NormalNodes;
-JointTree
methods:
+addNodes();
+addEdges();
+IsEmpty();
+getFirstNeighbor(int v);
+getNextNeighbor(int v1,int v2);
+findNode();//找到节点
+findCircle();//找到回路
+createMoralGraph();//构建Moral图
+createTriangulatedGraph();//图形的三角化算法
+createJointTree();//通过对三角化后的图形进行操作形成联合树结构
+inference();//推理函数
}
定义4 团结点类(Clique).团结点类是联合树结构上团节点进行封装的类,包含多个节点Nodes以及条件概率在联合树上的映射函数EnergyFunction,操作方法中最重要的有消息更新方法update(),该方法用于消息传递,使联合树达到一致状态,其数据结构如下:
Class Clique{
attributes:
-Nodes;
-Name;
-Number;
-EnergyFunction;
methods:
+update();
}
定义5 分割集类(Separator.)分割集类是联合树算法中生成的一种数据类型,分割集类是对分割集的抽象.分割集类包含多个节点Nodes,其条件概率是联合树上的映射函数Energy Function,操作方法中最重要的有消息更新方法update(),该方法用于消息传递,使联合树达到一致状态,其数据结构如下:
Class Separator{
attributes:
-Nodes;
-Name;
-Number;
-EnergyFunction;
methods:
+update();
}
定义6 联合树类(JointTree).对分割集和团结点进行封装的类称为联合树类.联合树类是联合树推理算法进行当中构建的一个新的数据类型,用以存储团结点Cliques与分割节点Separators,联合树类可以对整个联合树进行消息更新等操作,其数据结构如下:
Class JointTree{
attributes:
-SubNetwork;
-Cliques;
-Separators;
-Name;
-Number;
-List
[1] | Haenni R,Romeijn J W,Wheeler G,et al.Probabilistic logics and probabilistic networks[M].Berlin:Springer,2010. (1) |
[2] | Koller D,Pfeffer A.Object-oriented Bayesian networks[M].London:Morgan Kaufmann Publishers Inc.,1997. (1) |
[3] | Xiang Y,Jensen F V.Inference in multiply sectioned Bayesian networks with extended Shafer-Shenoy and lazy propagation[M].London:Morgan Kaufmann Publishers Inc.,1999. (1) |
[4] | Xiang Y.Belief updating in multiply sectioned Bayesian networks without repeated local propagations[J].International Journal of Approximate Reasoning,2000,23(1):1-21. (1) |
[5] | 郭文强,高晓光,侯勇严,等.采用MSBN多智能体协同推理的智能农业车辆环境识别[J].智能系统学报,2013(5):453-458.(Guo Wen-qiang,Gao Xiao-guang,Hou Yong-yan,et al.Environment recognition of intelligent agricultural vehicles based on MSBN and multi-agent coordinative inference[J]. Journal of Intelligent Systems,2013(5):453-458.) (1) |
[6] | 田凤占,张宏伟,陆玉昌,等.多模块贝叶斯网络中推理的简化[J].计算机研究与发展,2003,40(8):1230-1237.(Tian Feng-zhan,Zhang Hong-wei,Lu Yu-chang,et al.Multiple modules in Bayesian network inference of simplified[J]. Journal of Computer Research and Development,2003,40(8):1230-1237.) (1) |
[7] | Jensen F V,Lauritzen S L,Olesen K G.Bayesian updating in causal probabilistic networks by local computations[J].Computational Statistics Quarterly,1990,4(1):269-282. (1) |
[8] | Madsen A L,Nilsson D.Solving influence diagrams using HUGIN,Shafer-Shenoy and lazy propagation[M].London:Morgan Kaufmann Publishers Inc.,2001. (1) |
[9] | Jensen F V,Jensen F.Optimal junction trees[M].London:Morgan Kaufmann Publishers Inc.,1994. (1) |