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算法。在贝叶斯网络的推理过程中，常常需要对所有节点进行计算。……