DBN条件下信度传输优化算法仿真研究

李曼, 杨俊清, 任静, 石锋, 张少应, 马文胜

(西安航空学院 计算机学院， 陕西 西安 710077)

0 引言

Pearl.J等在20世纪80年代提出了信度传输(Belief Propagation, BP)算法[1]，最初是采用树形结构明确表述的，后来扩展到多树结构[2]。在有环的图模型中使用BP算法，信息将在环中循环传播，信息很可能在重复的路径中传播，一方面使得传播过程变得冗余，另一方面，也可能使得信息来回振荡而不收敛。

针对信息传输算法迭代次数较多的问题，提出了一种基于根节点优先搜索的信度传输DBP算法，用于提高算法优化率。首先，分析了BP算法的推理过程，其次，提出了优化的信度传输算法，分析了树的定义及树的遍历，给出了优化的信度传输算法的基本原理和实现步骤，最后，在动态贝叶斯网络DBN条件下，通过单一证据和组合证据推理，对优化的DBP算法与BP算法进行实验研究和仿真分析。

1 信度传输算法与优化的信度传输算法

1.1 信度传输算法

信度传输BP算法是一种对贝叶斯网络[3]等图模型进行推理的消息传递算法，其本质上是一个贝叶斯过程，采用有向图的形式表达多个变量的联合概率。有向图中的节点表示变量,而边表示变量间的概率依赖关系，即在给定任意观察节点的条件下，计算每一个未观察节点的边缘分布[4]。

由于贝叶斯网络[5]能如此紧凑地表达联合概率，可以有效地进行概率推理，包括计算边缘概率和后验概率[6]，通常是使用BP算法。在贝叶斯网络的推理过程中，常常需要对所有节点进行计算。但在一个大型网络中，往往有部分节点的关注度较少，甚至不被关注，如果每次给定证据节点后，都对其进行计算，务必延长每一次推理的计算时间。

相对于经典BP算法，提出一种信度传输优化算法(Belief Propagation Optimization Algorithm)，即基于根节点优先搜索的信度传输算法 (Belief Propagation Algorithm based on Deepness First Search of root node)，简写为DBP算法。下面先介绍树的定义及遍历。

1.2 树的定义及遍历

树是一类重要的非线性数据结构[7]，是以分支关系定义的层次结构。

(1) 定义

如果x是一个离散随机变量序列，p为联合集合函数，单个xi的边缘分布为p在其它变量上的叠加和。

定义：树(tree)是n(n0)个结点的有限集T，其中，n=0 为空树；

有且仅有一个特定的结点，称为树的根 (root)；

当n>1时，其余结点可分为m(m>0)个互不相交的有限集。T1,T2,…,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。

(2) 特点

树中至少有一个结点——根；

树中各子树是互不相交的集合。

(3) 树的遍历

树的遍历[7]是指从树中的某个结点出发，按照某种顺序访问树中的每个顶点，使每个顶点被访问一次且仅一次；遍历可分为先根遍历和后根遍历两种方式。

① 先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树；

② 后根遍历树，即先依次后根遍历每棵子树，然后访问根结点。

1.3 信度传输优化DBP算法

信度传输优化DBP算法的基本原理是对于一个树形结构的贝叶斯网络，当证据节点依次给出时，每获得一个证据信息，按照基于根节点优先搜索的方式，搜寻证据节点和关注节点之间的路径，只对该路径上的若干节点采用BP推理方法进行推理，而对其他节点的推理在本次计算中省略，只有在这些节点处于搜寻的路径上时，对其概率信息进行更新。当同时给出若干证据时，搜寻出这些给出的证据到关注节点的相关路径，这些相关路径构成了一个路径网，只对该路径网上的节点进行BP推理，省略掉其他不相关的节点，从而节省推理时间。

2 DBN条件下，DBP算法与BP算法实验研究

实验环境

处理器：Intel(R) Pentium(R) Dual

内存：1.79 GHz，0.99 GB

操作系统：Microsoft Windows XP

DBP算法软件实现如下。

DBP算法可分为4个主要模块予以实现，分别是创建矩阵、构建网络、设置参数和过程推理，部分主要代码如下所示。

(1) 创建矩阵

Void CreatMatrix

{ N=m;

dag=zeros(m，m);

dag(1，2)=x;

dag(2，3)=x;

}

(2) 构建网络

Void BulidNetwork

{ discrete_nodes=1:N;

node_sizes=2*ones(1，N);

bnet=mk_bnet(dag，node_sizes，'discrete'，discrete_nodes);

}

(3) 设置参数

Void Settings

{ bnet.CPD{1}=tabular_CPD(bnet，1，[x1 x2]);

bnet.CPD{2}=tabular_CPD(bnet，2，[x1 x2 x3]);

}

(4) 过程推理

Void ProcessReasoning

{ engine=pearl_inf_engine(bnet);

evidence=cell(1，N);

evidence{4}=1;

[engine，ll]=enter_evidence(engine，evidence);

}

贝叶斯模型如下。

采用的贝叶斯模型，如图1所示。

图1 贝叶斯网络模型实例

图1是一个具有38个节点的树形结构，并建立动态贝叶斯网络，时间片长度为3。

(1) 单一证据推理

证据节点ENode = 30；关注节点CNode = 8。

推理进行一百次的执行时间对比结果，如图2所示(单位s)。

图2 单一证据时，BP和DBP算法执行时间对比图

(2) 组合证据推理

证据节点Enode1 = 31，Enode2=35；关注节点CNode = 14。

推理进行一百次的执行时间对比结果，如图3所示(单位s)。

图3 组合证据时，BP和DBP算法执行时间对比图

(3) 结果分析

输入单一证据，时间t= 1，节点30为“真”。经典BP算法的网络推理拓扑图，如图4所示。

而采用DBP算法，推理得到并使用的推理拓扑图，如图5所示。

图5 单一证据输入，DBP算法推理网络图

组合证据与单一证据类似，输入组合证据时间为1，证据节点ENode 30、ENode34为“真”，经典BP算法推理拓扑不发生改变。DBP算法更新后的推理网络拓扑图，如图6所示。

可见无论是输入单一证据还是组合证据，DBP算法都能生成一个规模小于原树的新的树状网络图，在38个节点树形结构图的情况下，单一、组合证据下节点数为27、45个。

对经典的BP算法、BP改进算法和DBP算法的优缺点分析如下。

(1) 在有环的图模型[8]中使用BP算法，信息将在环中循环传播，信息很可能在重复的路径中传播，一方面使得传播过程变得冗余，另一方面，也可能使得信息来回振荡而不收敛；

(2) 基于树的再参数方法、基于树的序列再加权方法[9]等，相比于经典的BP算法，这些算法尽管提高了收敛性，但迭代次数仍然很多；

(3) 还有降低推理复杂度的按良序的信度传输方法[10]

图6 组合证据输入，DBP算法推理网络图

以及关于Bethe自由能最小化的方法，不同的Bethe自由能最小化方法对应于不同的信息传播策略；

(4) 针对信息传输算法迭代次数较多的问题，提出了优化的信度传输算法，即基于根节点优先搜索的信度传输DBP算法，用于提高算法优化率，减少算法执行时间。主要是因为随着网络趋于复杂，DBP算法推理得到新网络相对于原来的网络消除了更多的无关节点，而得到新网络的算法本身并不随着网络节点数的增多而时间明显增加，从而减少迭代次数、提高算法优化率。

3 总结

首先阐述了信度传输(BP)算法的基本内容，分析了BP算法的主要思想和推理过程；其次，提出了优化的信度传输算法，分析了树的定义及树的先根遍历，给出了优化的信度传输算法的基本原理和实现步骤；最后，通过典型的树形结构的贝叶斯网络实例，在DBN条件下，对DBP算法和BP算法进行了分析。DBP算法在推理时间上优于BP算法，且优化率随关键节点的变化而浮动。实验表明：DBP算法更适用于大型的网络，原因在于大型网络中节点更复杂，DBP算法可减少迭代次数，节省更多的推理时间，提高算法有效性。