用递归算法三角化BN

递归分布估计算法三角化贝叶斯网络作者：TxominRomeroa,b,PedroLarranagac摘要：贝叶斯网可用作一种模型在内在不确定性领域进行推理，即，给定一组变量具体实例时，确定另一组变量的概率分布。这个推理是NP难的。有几种算法可以做精确和近似推理。最流行的算法之一，也是一种精确算法，是Lauritzen和Spiegelhalter提出的证据传播算法[Localcomputationswithprobabilitiesongra-phicalstructuresandtheirapplicationonexpertsystems(1988)],之后被Jensena等人改进[Bayesianupdatingincausalprobabilisticnetworksbylocalcomputations(1990)]。该算法需要一个变量序来三角化端正图，它与初始贝叶斯网络结构相联系。推理的有效性依赖于变量序。在这篇文章，我们使用一种新的进化计算范式，分布估计算法（EDAs），来得到最优变量序，从而获得最有效的三角化。我们还将提出一种新的进化算法，递归分布估计算法（REDAs）。并证明在这个特定问题中，REDAs提高了EDAs效果，并且它们的结果与其它三角化方法相比很有竞争力。1.前言n21,,,XXXX是一个n维随机变量，其中ix是iX的具体取值。一个PGM或概率图模型sS,，是一个图结构,XS和一组局部参数s。X是一组节点，代表系统变量，是一个弧集，代表结构变量间的条件依赖或独立关系。一个BN是一个PGM，其中图结构是一个有向无环图（DAG），iX是离散随机变量（叫做节点），参数组ijks，其中k从1到ir，j从1到iq，i从1到n，代表X上的局部概率分布，即，ijk是当iX的父节点变量取第j个值时，iX取第k个值的条件概率。最后，ir代表第i个变量不同取值个数，iq表示第i个变量父节点集的可能取值个数。BN范式可作为一种模型在内在不确定领域进行推理。一个BN所表示的联合分布因式分解，允许一个模型内的有效推理。关于BN的介绍和经典教材参见[10,18]和[30]。作为推理模型，我们将尝试获得BN的最好三角化，也将在分布估计算法中用到这个三角化BN。在BN中进行推理的最直接方法是，通过未实例变量来计算边缘分布。在边缘分布中涉及的参数数量，随着变量数量呈指数增长。Lauritzen和Spigel-halter[26]提出，为了取代在后面的步骤加入它们而分别计算每个联合概率，我们组合它们所有的相同因式，从而使计算更有效。例如，对于Asia网（图1）。我们有：TELBSSBLETSPSBPSLPBEDPLTEPEXPATPAPSBLDEXTAPDXAP||,|,|||,,,,,,,,,,,,,（1）我们可以改写等式（1）为SSBSLBEDLTEEXATADXAPSBLET,,,,,,,,,,,,,,（2）这里，每个因式不是一个条件概率，而是一个势函数。首先，势函数是条件概率，它们的参数是图中相连的变量。一个有效的程序，寻找每个势函数与哪些变量是相连的，就是端正化这个图。也就是，在每个节点的父节点间增加一条弧（见图2）。然而，当我们在表达式SSBSL,,中对所有的S值求和时，我们得到了一个新因式（一个新的辅助势函数）依赖于L和B,且在这些节点间没有弧。这是由于前面定义的势函数而产生的问题。我们可以通过三角化这个图来解决这个问题（有关更详尽的解释见[26]）。一个图被三角化，如果每个长度大于3的圈都有一条边。在Asia网中，增加BL的弧就足以三角化它（见图3），但是在很复杂网络，这就不那么容易。一个好三角化可以使一些有关图问题获得解，在多项式时间内，而不是指数时间内[3]。在实验中，搜索最好三角化的算法是用熟悉的顶点移除法。主要地，当一个顶点被选择从图中移除，我们增加任何需要的弧，使得它们的相邻顶点子图完整（子图中与移除顶点相邻的顶点之间都有边相连）。然后，我们移除这个顶点及与它相连的弧。这个把所有新弧加入到它原始弧集的图，叫做三角化图。给定序团的规模时，移除顶点序决定了生成三角化图的效果。有些标准来估计三角化效果[34]。最有名的标准之一是，在实验中作为EDAs评价函数的最小权重。这个方法给每个团联系一个权重iCw：BXDAETSL图1TheAsiaBNALSTEBDALSTEBXXD图2端正化Asia网图3.三角化Asia网ijCXjrC2ilogw（3）其中，jr表示属于团iC的顶点jX的可能状态数。所以我们可以定义一个三角化图的权重：CCCXjtiijrGw2log（4）因此，我们的目标是最小化tGw。对一个BN获得最好三角化是个NP难的问题[2,36]。在这篇文章中，我们将使用单变量边缘分布算法（UMDA）[28]和输入聚类互信息最大化（MIMIC）[12]，这两个分布估计算法（EDAs），去寻找最可能的三角化。EDAs是一种新的启发方法，属于建立在概率论中的进化算法（EA）。文章剩下部分组织如下：在第二部分，我们介绍分布估计算法，描述个体表示。第三部分，我们介绍递归分布估计算法（REDA）范例。第四部分，我们介绍EDA和REDA的实验结果。第五部分，我们回顾了关于搜索最好三角化的早期工作。第六部分是总结评价。2.分布估计算法EDAs[23,25,27,29]是基于种群的随机启发算法，它通过从数据中学习概率分布和后期仿真，来代替遗传算法中经典的交叉和变异算子。最初地，随机产生一组个体。每个个体用一个目标函数评价。新个体种群抽样于概率分布，这个概率分布用来自前一代的个体子集评价。具有较好函数值的个体，有更大机会进入被选个体子集。这个过程被迭代，直到满足一些终止标准。这样，我们可以清楚地采集所有变量间的关系。EDAs已经被应用在几个问题中，例如：图匹配[6]，BNs部分溯因推理[13]，BNs结构学习[7,31,33]。2.1.EDA算法的一般形式在给出EDA一般伪代码之前，我们先确定一些定义：●mZZZ,,1表示有m个分量的m维变量（表示个体），mzzz,,1表示m维变量的一个实例（一个个体）。●MlzzD,,1表示第l代，有M个个体的种群。●slD表示选自lD的由N个个体组成的种群（MN）。●slllDZZ1|表示给定slD1时，第l代中Z的联合广义概率分布。记号用来表示离散和连续变量。为了搜索最好的三角化，这里提出EDA算法的一般形式，可以参见图4。为了估计Zl（主要问题）和抽样新一代，EDAs构造和使用一个来自所选个体slD1池的PGM。如果表示个体组成的变量是离散的，所选的PGM就是一个BN，如果是连续的，EDA构造一个高斯网络（GN）[35]。2.2.个体表示在它们进化过程中，EDAs模拟m个分量的不同个体（mzz,,1，其中iz是一个整数或实数），且这些个体必须与n个变量的具体排序单一联系。在连续EDAs中，个体表示没有问题，因为个体分量仅仅需要定序，每个实例分量与它各自指标相联系来获得有效排序。就是，在这种情况下，nm。它的缺点包括，这种表示高度冗余，由于不同的连续个体可以产生相同的序。例如，一个连续个体（0.5,1.6,0.2,0.1）可以与序（3-4-2-1）联系，但是个体（0.3,2.0,0.2,0.0）也一样。在离散域情况下，直接个体表示成为一个问题。如果我们有4个变量，就有！4种可能的排列或排序，我们不可能用一个4个分量的个体，它的分量最多有4个实例，因为我们可以获得，例如，实例（2-3-4-4），不是一个有效排序。这里有一个解决方法，首先在[33]被Romero等人使用，这使得个体序是双射联系的。我们可以用!n的因式分解，从!n种可能排列中确定一个特定排序。例如，如果我们有4个变量，系统会产生！4种可能排序，如表1所示。！4的因式分解是1234。如果我们用三个分量321,,ZZZ,其中,3,421rr和23r来表示个体。很容易从一个个体中获得系统列表的一个特定排序。但是这个表示仍然有一些缺陷：会有可能状态数很大的分量，这使得EDA的效率很差。在这篇文章中用到的一个局部．．．．．．．．．．．．．解决方案，是．．．．．．!n的质因数分解（对于．．．．．．．．．4．个变量，质因数分解．．．．．．．．．12322决定．．4．个．分量的个体）。但是如果我们有大量的分量，个体就会非常长，且一些分量会继．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．续有大量的可能状态。例如，在．．．．．．．．．．．．．．50．．个变量的网络，我们发现．．．．．．．．．．．47．．是一个质数：所．．．．．．．以我们将至少有一个分量有．．．．．．．．．．．．47．．种可能状态。．．．．．．图4.EDA方法的主要方案表1.四个节点的可能排序2.3.概率分布估计这里，我们将用两个DEAs的例子：单变量边缘分布算法（UMDA）和输入聚类互信息最大化（MIMIC）。它们都将用在离散和连续域，只考虑低阶依赖性。UMDA算法，由Muhlenbein介绍在[28]，假设变量间的边缘独立（个体分量间），即，在离散域下，用来估计zpl的模型是最简单的，用边缘频率得到概率分布：NDzZzpNjsliijil11|（5）其中.0,1|11相反的情况种情况下，的第如果在iislsliijzZjDDzZ（6）在连续域情况下，联合密度函数的因式分解由通常的单变量分布组成：22111221,;,;iiixniiniiiiexfXf（7）以及参数估计使用它们的最大似然估计：NrNrNrlirlirlirlililixNxNxN112111,1,MIMIC或输入聚类互信息最大化，被DeBonet等人提出[12]，解释依赖性，但是只在对变量之间。在连续域，使用GNs（高斯网络）。主要的思想是，在每一代中，搜索变量间的最好排列，为了获得关于经验分布slD的最接近概率分布zpl，使用相对熵也叫KL散度、KLD（Kullback–Leiblerdivergence）：111|njiililljjnXXHXHXH（8）其中XH是变量X的香农熵（信息熵），YXH|是给定Y时X的条件熵。我们尝试搜索排列来最小化xHl。测试所有的!n种排列是不可能的。所以，MIMIC搜索最好排列作为变量niX序，使它有较小估计熵（这个估计用slD计算），在每一步，选择与上一步被选变量的条件熵最小的变量。对连续情况的说明参见[25]。2.4.新一代抽样在离散和连续领域，我们将使用Henrion[17]的概率逻辑抽样（PLS）方法对新一代取样。在这种方法中，当节点的所有父节点被用iizp|分布抽样后，就产生了这个变量实例。在执行模拟前，变量必须用祖先序进行排序。在高斯网络下，执行通常的密度模拟[25]。3.递归分布估计算法（REDAs）REDAs主要的思想是，在EDA算法执行的某些部分，划分网络顶点集为两个子集（我们想要获得网络节点集的最优排序）。那么新算法对每个子集递归地调用REDA，在每次调用中尝试为它获得一个最优排序。所以在第一次调用中，我们将固定一个节点子集，在其它子集上进化递归，第二次调用中我们将相反地执行。正如我们在[5]中看到的，EDA最繁琐的一步是结构学习，有时如果我们的估计函数很复杂的话，新种群模拟和个体估计都很复杂。所有这些问题随着个体分量数增长而增长。如果我们限制