用递归算法三角化BN

1、递归分布估计算法三角化贝叶斯网络作者：Txomin Romero a,b , Pedro Larranaga c摘要：贝叶斯网可用作一种模型在内在不确定性领域进行推理，即，给定一组变量具体实例时，确定另一组变量的概率分布。这个推理是NP难的。有几种算法可以做精确和近似推理。最流行的算法之一，也是一种精确算法，是Lauritzen和Spiegelhalter提出的证据传播算法Local computations with probabilities on gra-phical structures and their application on expert systems(1988) ,之后

2、被Jensena等人改进Bayesian updating in causal probabilistic networks by local computations(1990)。该算法需要一个变量序来三角化端正图，它与初始贝叶斯网络结构相联系。推理的有效性依赖于变量序。在这篇文章，我们使用一种新的进化计算范式，分布估计算法（EDAs），来得到最优变量序，从而获得最有效的三角化。我们还将提出一种新的进化算法，递归分布估计算法（REDAs）。并证明在这个特定问题中，REDAs提高了EDAs效果，并且它们的结果与其它三角化方法相比很有竞争力。 1. 前言 是一个n维随机变量，其中是的具体取值。一

3、个PGM或概率图模型，是一个图结构和一组局部参数。是一组节点，代表系统变量，是一个弧集，代表结构变量间的条件依赖或独立关系。一个BN是一个PGM，其中图结构是一个有向无环图（DAG），是离散随机变量（叫做节点），参数组，其中从1到，从1到，从1到，代表上的局部概率分布，即，是当的父节点变量取第个值时，取第个值的条件概率。最后，代表第个变量不同取值个数，表示第个变量父节点集的可能取值个数。BN范式可作为一种模型在内在不确定领域进行推理。一个BN所表示的联合分布因式分解，允许一个模型内的有效推理。关于BN的介绍和经典教材参见10,18和30。作为推理模型，我们将尝试获得BN的最好三角化，也将在分布

4、估计算法中用到这个三角化BN。在BN中进行推理的最直接方法是，通过未实例变量来计算边缘分布。在边缘分布中涉及的参数数量，随着变量数量呈指数增长。Lauritzen和Spigel-halter26提出，为了取代在后面的步骤加入它们而分别计算每个联合概率，我们组合它们所有的相同因式，从而使计算更有效。例如，对于Asia网（图1）。我们有： （1）我们可以改写等式（1）为 （2）这里，每个因式不是一个条件概率，而是一个势函数。首先，势函数是条件概率，它们的参数是图中相连的变量。一个有效的程序，寻找每个势函数与哪些变量是相连的，就是端正化这个图。也就是，在每个节点的父节点间增加一条弧（见图2）。然而，

5、当我们在表达式中对所有的值求和时，我们得到了一个新因式（一个新的辅助势函数）依赖于和,且在这些节点间没有弧。这是由于前面定义的势函数而产生的问题。我们可以通过三角化这个图来解决这个问题（有关更详尽的解释见26）。一个图被三角化，如果每个长度大于3的圈都有一条边。在Asia网中，增加的弧就足以三角化它（见图3），但是在很复杂网络，这就不那么容易。一个好三角化可以使一些有关图问题获得解，在多项式时间内，而不是指数时间内3。BXDAETSL图1 The Asia BNALSTEBDALSTEBXXD图2端正化Asia网图3.三角化Asia网在实验中，搜索最好三角化的算法是用熟悉的顶点移除法。主要地，

6、当一个顶点被选择从图中移除，我们增加任何需要的弧，使得它们的相邻顶点子图完整（子图中与移除顶点相邻的顶点之间都有边相连）。然后，我们移除这个顶点及与它相连的弧。这个把所有新弧加入到它原始弧集的图，叫做三角化图。给定序团的规模时，移除顶点序决定了生成三角化图的效果。有些标准来估计三角化效果34。最有名的标准之一是，在实验中作为EDAs评价函数的最小权重。这个方法给每个团联系一个权重： （3）其中，表示属于团的顶点的可能状态数。所以我们可以定义一个三角化图的权重： （4） 因此，我们的目标是最小化。对一个BN获得最好三角化是个NP难的问题2,36。在这篇文章中，我们将使用单变量边缘分布算法（UMD

7、A）28和输入聚类互信息最大化（MIMIC）12，这两个分布估计算法（EDAs），去寻找最可能的三角化。EDAs是一种新的启发方法，属于建立在概率论中的进化算法（EA）。文章剩下部分组织如下：在第二部分，我们介绍分布估计算法，描述个体表示。第三部分，我们介绍递归分布估计算法（REDA）范例。第四部分，我们介绍EDA和REDA的实验结果。第五部分，我们回顾了关于搜索最好三角化的早期工作。第六部分是总结评价。2. 分布估计算法 EDAs 23,25,27,29是基于种群的随机启发算法，它通过从数据中学习概率分布和后期仿真，来代替遗传算法中经典的交叉和变异算子。最初地，随机产生一组个体。每个个体用一

8、个目标函数评价。新个体种群抽样于概率分布，这个概率分布用来自前一代的个体子集评价。具有较好函数值的个体，有更大机会进入被选个体子集。这个过程被迭代，直到满足一些终止标准。这样，我们可以清楚地采集所有变量间的关系。EDAs已经被应用在几个问题中，例如：图匹配6，BNs部分溯因推理13，BNs结构学习7,31,33。2.1. EDA算法的一般形式在给出EDA一般伪代码之前，我们先确定一些定义：表示有个分量的维变量（表示个体），表示维变量的一个实例（一个个体）。表示第代，有个个体的种群。表示选自的由个个体组成的种群（）。表示给定时，第代中的联合广义概率分布。记号用来表示离散和连续变量。 为了搜索最好

9、的三角化，这里提出EDA算法的一般形式，可以参见图4。为了估计（主要问题）和抽样新一代，EDAs构造和使用一个来自所选个体池的PGM。如果表示个体组成的变量是离散的，所选的PGM就是一个BN，如果是连续的，EDA构造一个高斯网络（GN）35。2.2. 个体表示 在它们进化过程中，EDAs模拟个分量的不同个体（，其中是一个整数或实数），且这些个体必须与个变量的具体排序单一联系。在连续EDAs中，个体表示没有问题，因为个体分量仅仅需要定序，每个实例分量与它各自指标相联系来获得有效排序。就是，在这种情况下，。它的缺点包括，这种表示高度冗余，由于不同的连续个体可以产生相同的序。例如，一个连续个体（0.

10、5,1.6,0.2,0.1）可以与序（3-4-2-1）联系，但是个体（0.3,2.0,0.2,0.0）也一样。在离散域情况下，直接个体表示成为一个问题。如果我们有4个变量，就有种可能的排列或排序，我们不可能用一个4个分量的个体，它的分量最多有4个实例，因为我们可以获得，例如，实例（2-3-4-4），不是一个有效排序。这里有一个解决方法，首先在33被Romero等人使用，这使得个体序是双射联系的。我们可以用的因式分解，从种可能排列中确定一个特定排序。例如，如果我们有4个变量，系统会产生种可能排序，如表1所示。的因式分解是。如果我们用三个分量,其中和来表示个体。很容易从一个个体中获得系统列表的一个

11、特定排序。但是这个表示仍然有一些缺陷：会有可能状态数很大的分量，这使得EDA的效率很差。在这篇文章中用到的一个局部解决方案，是的质因数分解（对于4个变量，质因数分解决定4个分量的个体）。但是如果我们有大量的分量，个体就会非常长，且一些分量会继续有大量的可能状态。例如，在50个变量的网络，我们发现47是一个质数：所以我们将至少有一个分量有47种可能状态。 图4.EDA方法的主要方案表1.四个节点的可能排序2.3.概率分布估计这里，我们将用两个DEAs的例子：单变量边缘分布算法（UMDA）和输入聚类互信息最大化（MIMIC）。它们都将用在离散和连续域，只考虑低阶依赖性。UMDA算法，由Muhlen

12、bein介绍在28，假设变量间的边缘独立（个体分量间），即，在离散域下，用来估计的模型是最简单的，用边缘频率得到概率分布： （5）其中 （6）在连续域情况下，联合密度函数的因式分解由通常的单变量分布组成： （7） 以及参数估计使用它们的最大似然估计： MIMIC或输入聚类互信息最大化，被De Bonet等人提出12，解释依赖性，但是只在对变量之间。在连续域，使用GNs（高斯网络）。主要的思想是，在每一代中，搜索变量间的最好排列，为了获得关于经验分布的最接近概率分布，使用相对熵也叫KL散度、KLD（KullbackLeibler divergence）： （8）其中是变量的香农熵（信息熵），是给

13、定时的条件熵。我们尝试搜索排列来最小化。测试所有的种排列是不可能的。所以，MIMIC搜索最好排列作为变量序，使它有较小估计熵（这个估计用计算），在每一步，选择与上一步被选变量的条件熵最小的变量。对连续情况的说明参见25。2.4.新一代抽样在离散和连续领域，我们将使用Henrion17的概率逻辑抽样（PLS）方法对新一代取样。在这种方法中，当节点的所有父节点被用分布抽样后，就产生了这个变量实例。在执行模拟前，变量必须用祖先序进行排序。在高斯网络下，执行通常的密度模拟25。3. 递归分布估计算法（REDAs）REDAs主要的思想是，在EDA算法执行的某些部分，划分网络顶点集为两个子集（我们想要获得

14、网络节点集的最优排序）。那么新算法对每个子集递归地调用REDA，在每次调用中尝试为它获得一个最优排序。所以在第一次调用中，我们将固定一个节点子集，在其它子集上进化递归，第二次调用中我们将相反地执行。正如我们在5中看到的，EDA最繁琐的一步是结构学习，有时如果我们的估计函数很复杂的话，新种群模拟和个体估计都很复杂。所有这些问题随着个体分量数增长而增长。如果我们限制EDA在节点子集上执行，而不是整个集合，由于联系的个体将变得很少，我们在短时间内可以获得良好的总体效果。所以我们可以在增加代数的同时不增加执行时间。为了介绍递归算法，我们先定义一些概念： 是一个节点序的存储器。这个存储器由执行REDA时

15、发现的个个体的最好序组成(其中是种群的规模)。存储器使用序估计进行排序。正如后面看到的，我们将在个体估计和种群初始化中使用这个存储器。 图5. 在的递归等级1中，当时，用构造 图6. REDA伪代码.考虑到REDAs比EDAs更有效，由于在BaseEda中的评价个体数和大多数递归调用中的个体规模都较小是一个BN的节点集合，我们将用来三角化。是由的节点组成的规模是的子集，在递归等级下，没有固定。 递归等级是连续递归调用的次数。也就是，首先，主代码的等级是0，第一次递归调用，等级是1，等等。（m）是个体分量的数量，表示一个（n）节点序（m=n）。注意，尽管在连续域，但是在离散域不成立。是一个在第代

16、中规模为的个体种群，其中，是递归等级。我们可以用记号来合并递归等级，不仅对种群而且对这里描述的其它变量。然而在描述伪代码时不需要显示这个信息，由于变量是局部的，我们更倾向于简化记号。是属于的个节点的第个序。序通常是每一时刻发现的最好序。是从中抽取的节点序，它由的节点组成，这些节点在递归等级中不固定，维持它们在中的相对序。是一个节点序，是一个属于存储器的。是个分量的个体，与序关联。是一个节点序。是一个抽取于的。是个分量的个体，与序关联。是一个序。是第个序中的第个节点。是一个节点序，由一个序产生。我们构造它，通过放置递归等级的固定节点在它们各自的位置上，然后放置出现在序中的节点在所得的间隙，并维持

17、它们在中的相对序。，如果这个函数返回一个序的测度。是一个程序，使用序来构造序，并返回，和序。 图7.初始化种群的伪代码（调用BaseEda） 图8.一个估计的伪代码表格2 每次REDA中的值 我们可以只计算一个序的权重，如果它有个节点：所以，我们在计算它的 测度之前必须转换为一个。但是，我们可以用它们出现在存储器中最好个体的相对序，而不是总放置递归等级中的固定分量在同样的序位置。我们看一个关于这种构造的例子，在图5中。 图6-8给出了所用的伪代码。正如我们看到的，非固定的节点子集规模，决定了递归算法的总体情况和基本情况。在递归调用的前后，必须考虑它，我们用标准EDA（BaseEda）在整个节点

18、子集上进化它。如果在每次递归调用中，我们用一个随机初始种群，那么将不会用到之前的优良个体（其它递归等级的）。但是我们可以通过在实际调用等级中，从现有的旧存储器的所有序中，提取非固定节点的相对序（不是精确的相对序，而是与相联系的个体）来初始化种群。为了减小第一个随机种群对REDA进化的决定性，我们可以在新存储器中保留旧存储器的5个最好个体，在实际递归等级用REDA选出的最好个体来填充剩下的个个体。4. 实验部分 就像在第一部分看到的，我们将在实验中使用大家都知道的顶点移除方法。4.1.实验中使用的网络用来比较EDAs和REDAs的网络叫做稀疏和稠密网络21。稀疏网络是计算机产生的，有50个变量和

19、100条弧。稠密网络，也是计算机产生的，有50个变量和大量的弧：359.表格3 在 稀疏网络中执行EDAs50次的平均效果表格4 在稠密网络中执行EDAs50次的平均效果严格地讲，稀疏和稠密网并不是BNs，因为它们两的结构都是无向非循环图。这简化了三角化的过程，因为这里不需要端正化网络。另外，我们使用了两个更复杂的网络，叫做MedianusI和MedianusII21来比较REDAs与其它三角化方法在现实世界网络中的效果。MedianusI是一个BN，这个网络描述疾病间的关系、病理生理学特征及对人类中枢神经采取的措施，它源于MUNIN系统的发展1。它有43个节点，66条弧。MedianusII

20、是对MedianusI的修改，有56个节点，161条弧。在两个网络中，节点值在3到21之间。4.2.EDAs和REDAs的参数选择我们通常用规模为和的种群，对于稀疏和稠密网络。我们对每个EDA执行50次实验（连续的UMDA或UMDAC,离散的UMDA或UMDAd，连续的MIMIC或MIMICC,和离散的MIMIC或MIMICd）。在EDAs中，我们复制了所有个不同评价个体的一个样本（最好个体的）。在REDAs中，执行了所有个不同估计，由于我们可以在个体子集规模小时，充分利用该算法的较快速度。当我们复制了100个样本时，EDA停止。这里没有一个收敛判定准则，由于它不能保证算法终止。REDA利用它

21、的执行速度，在相邻的存储器间连续执行5次。在每次执行中，我们复制50个样本。所以当我们总共复制250个样本时，停止算法。考虑到复制的50个样本在所有递归调用间是分离的，由于迭代次数很少，另外在多数递归调用中，个体的规模也较小，使得BaseEda的执行更快。在EDAs中，我们从实际种群中选择排在前面的个最好个体，用EDA生成BN，然后模拟下一代。在前面实验组之后，我们选择出现在表格2中的值进行REDAs。在EDAs中，从上一代到下一代，我们只保留5个最好个体，在每一步或一代抽样个个体。在REDAs中，我们抽样个个体。4.3.EDAs在稀疏和稠密网络的效果在表3中，我们可以看到对稀疏网络执行50次

22、EDAs的平均效果，在连续（UMDAC,MIMICC）和离散（UMDAd,MIMICd）域。在表4中，对稠密网络，我们有同样的信息。总的来说，使用标准EDAs进行三角化的结果，不好。除了在UMDAd的情况下，对于稀疏网络，最好的平均效果是26.55，然而对模拟退火最坏的结果是23.89，见文献22。在24中，使用一般算法，作者获得的平均效果小于23.05，在实验中用1296个参数组合，实验334次。在稠密网络，最好的平均结果是55.16（没有考虑UMDAd的情形），这个远超模拟退火的最坏结果54.25在22，或者对于平均算法，428个可能参数组合在平均权重低于52.88下，见24。我们可以看一

23、个不同EDAs间的比较，在图9和10中，对于的盒须图。在的稀疏网络中，UMDAd超过所有其它的离散算法，这些算法在Wilcoxon秩和检验中值接近0。在其余算法间没有统计意义的不同，除了在MIMICd和UMDAc的情形（值是0.04）。在稠密网络，比较结果是一样的：UMDAd超过了其它的算法，在值小于时，MIMICd超过了MIMICc和UMDAc在值接近0时。 图9.的稀疏网络，与EDAs的比较 图10.的稠密网络，与EDAs的比较 4.4.REDAs在稀疏和稠密网络的效果REDAs的效果是很有竞争力的，比起其它的EDAs。在表5和表6中，我们可以看到执行REDAs50次的效果，分别在连续和离

24、散域，对稀疏和稠密网络。表5.REDAs在稀疏网络执行50次的平均效果表6.REDAs在稠密网络执行50次的平均效果在图11和12中，我们可以看到不同REDAs的比较，对于的胡须图。REDAs无疑超过了EDAs。在UMDAd情形下，REDA超过了一个为0.0003的EDA，在稀疏网络下，在稠密网络中没有统计意义的不同。另外，个体规模的独立，算法种类（UMDA或MIMIC）或领域的特征（连续或离散），在它们这些结果中REDAs看上去更稳定。对于的稀疏网络，只有统计意义的不同，在MIMICc和MIMICd（值为0.00077），MIMICc和UMDAd（值为0.033）。但是在稠密网络下，任何算法

25、间并没有很大的不同。如果我们比较种群规模的不同（），表现是相似的：只有在MIMICc（值为0.01）下，才有显著的统计差异。在其它实验中，没有在这篇文章中呈现，我们可以这样说，标准的EDAs是非常敏感的，对于用来产生BN的被选个体集的规模，但是在REDAs中，我们并没有检测到这样的趋势。在图13中，我们可以看到一个有100个个体种群的比较，在稀疏网络和UMDAc算法下，在几个不同规模的集合中执行10次REDAs和EDAs的平均效果。在REDAs的情况下，显示结果更稳定。 图11.稀疏网络中，REDAs比较 图12.稠密网络中，REDAs比较 图13.稀疏网络中，执行10次UMDAc的平均结果，

26、与REDAs和EDAs在不同规模的 被选个体集的比较，REDA意思是在连续存储器上连续执行次REDA.这里我们取.表格7：在MedianusI,MedianusII执行50次REDAs的平均效果表格8:对MedianusI的几个三角化方法结果表格9:对MedianusII的几个三角化方法结果4.5.现实世界网络中REDAs与其它三角化方法间的比较我们已经用离散和连续的UMDA算法（在BaseEda调用中）来比较相关的REDA和其它三角化方法的结果。我们利用REDAs到MedianusI和II网络。像表7-9中所述，REDAs与其它三角化方法相比很有竞争力，不仅在平均估计中，而且在最好的情况下。

27、5. 回顾三角化工作在早先最好三角化一个BN中，与最小化相关的方法，不是提出的唯一方法。Robertson和Seymour32及Becker和Geiger4没有尝试最小化三角图的权重，而是想要获得一个小于的团数，当给定时，图中所有节点是二进制的（在树宽标准下）。团数是图中较大团的规模。他们算法中对最好的那个团假设一个近似解，通过一个常数。Won等人37发现了一个双射关系，在超图和关系型数据库模式间。也有一个一对一的关系，在三角化图集和无环超图间。所以，作者可以用著名的与数据库模式相关的特性和方法，来获得相应的三角化图。Bodlaender等人8尝试预处理初始图，使它减小但是不丢失推算可能结果，对预处理图相对于初始图来说。减少通过规则来管理 如：如果是一个单顶点，其度，那么我们就移除，并更新找到的最大的度，这里一个顶点是单顶点，如果它与一个团相邻（它的度是这个团的规模）。算法使用这些规则直到不能再进行了。但是这个算法没有考虑每个顶点的不同值。在与直接移除顶点相关的其它策略中，Kjaerulff提出三个启发法，在21中：-移除变量，在每一步，它产生较少的最大团。-移除变量，它最小化所增加弧的数量。-移除变量，它最小化整个三角化图的权重。三个算法都未