基于根节点优先搜索的信度传输DBP算法研究

李曼 杨俊清 任静 石锋 张少应

摘要：针对信度传输算法迭代次数较多的问题，提出一种基于根节点优先搜索的信度传输DBP算法。DBP算法依据根节点优先搜索的原理，选择一种特定的节点顺序进行信度传播，直接到达信息传播的不动点，降低迭代次数，节省推理时间。首先，分析了BP算法的主要思想、工作原理及推理过程，其次，提出了DBP算法，建立了贝叶斯网络模型，给出了该算法的基本原理，最后，给出了DBP算法流程，并通过典型的树形结构的贝叶斯网络实例，对DBP算法进行了分析，结果表明DBP算法在推理时间上优于BP算法，算法的时间优化率更高，从而验证了DBP算法的有效性。

关键词：信度传输算法;DBP算法;贝叶斯网络;消息传递算法;证据推理

中图分类号：TP3文献标识码：A

文章编号：1009-3044（2020）03-0249-03

1 概述

Pearl.J等在20世纪80年代提出了信度传输（Belief Propaga-tion，BP）算法[1]，最初是采用树形结构明确表述的，后来扩展到多树结构。BP算法在无环的图模型中可得到精确的边缘概率或者后验概率，但在有环的图模型中只能得到近似的结果，甚至不收敛。

在有环的图模型中使用BP算法，信息将在环中循环传播，信息很可能在重复的路径中传播，一方面使得传播过程变得冗余，另一方面，也可能使得信息来回振荡而不收敛。目前解决此类问题的代表方法[2]有基于树的再参数方法、基于树的序列再加权方法等，相比于经典的BP算法，这些算法尽管提高了收敛性，但迭代次数仍然很多。

针对信息传输算法迭代次数较多的问题，提出了一种基于根节点优先搜索的信度传输算法，用于提高算法优化率，减少算法执行时间。首先阐述了信度传输（BP）算法的推理过程，其次提出了一种基于根节点优先搜索的信度传输（DBP）算法，给出DBP的算法流程，并予以实验研究。

2 信度传输算法和DBP算法

2.1 信度传输算法

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

贝叶斯网的结构体现了变量间的条件独立性，即一个节点在其父节点的条件下与其他的祖先节点独立。N个节点的贝叶斯网的节点联合概率为：

由于贝叶斯网能如此紧凑地表达联合概率，可以有效地进行概率推理，包括计算边缘概率和后验概率，通常是使用BP算法，其主要思想是每个节点利用邻节点传来的信度和自己的条件概率更新自身的信度，再将结果再传递给邻节点;在整个更新过程中，需要对所有节点进行迭代，存在迭代次数较多甚至不收敛等问题，通常可以作为一种近似的推理算法。

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

该算法的工作原理是在节点之间的边上传递一种称为消息[6]的真值函数，包含了一个节点变量施加于另一个节点变量的影响。

BP算法成立的一个重要假设就是在某个节点的条件下，其父节点和子节点是条件独立的，这意味着该算法只有在树状结构的图中才能得到准确的结果。

在贝叶斯网络的推理过程中，常常需对所有节点进行计算。但在一个大型网络中，往往有部分节点的关注度较少，甚至不被关注，如果每次给定证据节点后，都对其进行计算，务必延长每一次推理的计算时间。

2.2 基于根节点优先搜索的信度传输（DBP）算法

相对于经典BP算法，提出了基于根节点优先搜索的信度传输算法（Belief Propagation Algorithm Based on Deepness FirstSearch of root node），简写为DBP算法。

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

DBP算法的实现步骤如下：

第一阶段：首次获得证据信息后，DBP算法第一阶段推理过程如图1所示：

给出一个贝叶斯网络，其节点构成集合Ⅳ={nl，n2，n3，n4....n13），其推理步骤为：

Stepl：输入证据节点ENode和关注节点CNode，其中ENode、CNode∈N。

Step2：搜寻ENode到CNode的一条推理路径，记录路径上各节点的顺序。

Step3：根据路径上各节点顺序，采用信度传输算法对各节点进行BP推理。

Step4：输出推理计算得到的关注节点的概率信息。

第二阶段：当再次获得证据信息后，第一阶段的推理过程不再适用，DBP算法第二阶段推理过程如图2所示： 相比第一阶段证据推理过程，第二阶段推理增加了一个更新路径上概率信息的模块，如图3所示。在首次给出证据节点和关注节点后，搜索到证据节点到关注节点的一条路径，并且进行了推理运算，当再次给出证据节点和关注节点后，搜索到新的路径和原路径相比有以下几种情况：

（1）新路径和原路径一致，路径上的概率信息已经得到更新，只需直接进行推理计算即可;

（2）新路径上节点有部分在原路径上，则只需更新不在原路径上的节点即可;

（3）新路径完全不和原路径重合，则需要对新路径上的所有节点进行更新后再完成本次BP推理。

3 基于DBP算法流程和实例分析

对于贝叶斯网络路径的搜索，DBP算法流程如图3所示：

在路径搜索之前，首先给贝叶斯网络编号。要搜寻一条从证据节点到关注节点的路径.为了简化搜索过程，分别搜索证据节点和关注节点到根节点的路径，将这两条路径合并得到所要寻找的路径，具体算法步骤为：

Stepl：输入证据节点ENode，证据节点可能有多个;

Step2：依次搜寻从节点1到证据节点的若干节点是否与证据节点有连接，由于树形结构的特殊性，一定能从这些节点中寻找出证据节点的下一个路径，记为R1，得到路径[ENode，R1];

Step3：判断搜索到的新路径节点是否为根节点l，如果是节点1，则停止搜索，如果不是，则继续搜索;

Step4：继续搜寻从节点1到R1的若干节点是否与R1相连，从而搜索到R1的下一个路径，记为R2，得到路径[ENode，R1，R2];

Step5：跳转到step3。

通过给出的流程，可分别获得证据节点到根节点的路径[ENode，R1，R2，…，1]以及关注节点到根节点的路径[CNode，Q1，Q2，…，1]，将两个路径进行合并即可得到所要搜寻的路径[ENode， R1， R2.…，1，…，Q2， Q1， CNode].

举例：具有9个节点的树形结构，如图4所示：

方法：首先，输人证据节点ENode或关注节点CNode。其中ENode=n5，CNode=n4，如图5（b）所示。其次，从证据节点遍历搜寻到根节点的路径，路径顺序为：n5→n2→n1，以相同的方法从关注节点遍历搜寻到根节点的路径，路径顺序为：n4→n1，从而我们得到了从证据节点到关注节点的路径顺序为：n5→n2→n1→n2。如图5（c）所示，根据得到的路径顺序，便可以对其进行贝叶斯推理了。

4 结束语

首先阐述了信度传输（BP）算法的基本内容，分析了BP算法的主要思想、工作原理及推理过程;其次，提出了一种基于根节点优先搜索的信度传输（DBP）算法，分析了该算法的基本原理，最后，给出了DBP算法流程，并进行实例分析。DBP算法在推理时间上优于BP算法，节省更多的推理时间，提高算法优化率和有效性。

参考文献：

[1] Jin Boru， Liu Huayan. Comparative efficacy and safety of ther-apy for the behavioral and psychological symptoms of demen-tia：a systemic review and Bayesian network meta-analysis[J].Joumal of neurology， 2019， 2363-2375.

[2] Gu Yiming. Bayesian-based traffic state estimation in large-scale networks using big data[D].Pittsburgh： Carnegie Mel-lon University.2017.

[3]項璟.广义近似消息传递算法的研究与应用[D].燕山大学，2018：2-4.

[4]王亚萍，成卫，李黎山.基于分层贝叶斯网络的交通密度估测模型[J]交通科学与工程. 2019。35（3）：104-110.

[5]陈龙，马亚平，基于分层贝叶斯网络的航母编队对潜威胁评估[J].系统仿真学报，2017，29（9）：2206-2212.

[6]李梵若，李忠.基于模糊证据推理的医疗诊断专家系统的设计与实现[J].智能计算机与应用，2019，9（4）：13-15.