2013论文翻译(一篇基于贝叶斯网路学习和推理工作的关于进化算法的回顾)

一篇贝叶斯网络学习和推理进化算法的综述摘要：由于概率图模型固有的性能，使得它成为机器学习和决策任务的主要候选者之一，尤其在不确定领域。如果有效地使用它们的功能，比如表示、推理和学习，能极大地有助于建立可以在不同问题领域相应地起作用的智能系统。贝叶斯网络是这些模型中被最广泛使用的一种。贝叶斯网络方面的一些推理和学习任务涉及到复杂的优化问题，这些问题需要使用元启发式算法。作为成功的问题求解者，进化算法是优化的有希望的候选者。这篇文章回顾了进化算法在解决一些有关贝叶斯网络推理和学习上NP难的最优化问题的应用。1.引论概率论已经为许多科学和工程工作提供了一种可靠的基础。人工智能和更多具体的机器学习是利用概率开发新的原理和算法的领域之一。贝叶斯网络作为一种流行的概率图模型，第一次被珀尔提出【105】，它结合图形和概率论来获得联合概率分布的一种更易于理解的表示。这个工具可以指出根本问题中的有用的模块性，帮助完成推理和决策任务，尤其在不确定领域。这些有用工具的应用已经被进一步改善，利用不同的方法提出了一组样本的概率图模型推理和自动感应。与此同时，现实世界的应用中存在的困难和复杂问题，增加了对有效的元启发式算法的要求，这些算法通过实施对可能解空间的智能搜索来获得良好的（不一定是最优的）解决方案。进化计算是这些算法中最成功的一个，它在广泛的问题领域获得了非常好的效果。应用这些算法的自然启发机制，可以实施一种更有效的多样的关于难问题的巨大解空间的搜索。例如，适者生存或基因互换和突变，人口候选解决方案，进化算法（比如遗传算法）。一些最相关的贝叶斯网络推理和学习问题被用公式表示成一个函数的优化。这些问题常常有一种棘手的复杂性，因此是应用元启发式方法的潜在领域。这篇文章的目的是回顾进化算法是怎样用来解决一些贝叶斯网络推理和学习上存在的组合问题的。这篇文章的组织如下。第二部分介绍贝叶斯网络和回顾关于其提出的一些推理的学习方法。第三部分展现了进化算法的框架和讨论它们是怎样运行的。主要的回顾关于进化算法是怎样在贝叶斯网络学习和推理中应用在第四部分给出。最后，第五部分总结文章。2.贝叶斯网络这一部分给出了贝叶斯网络的介绍和贝叶斯网络怎样被用到表示离散的、连续的、混合的环境下的概率分布。然后简洁的回顾贝叶斯网络推理和学习的方法。这部分采纳和引进的术语和概念在之后的展现用进化算法来学习贝叶斯网络推理和学习中会用到。更多的关于贝叶斯网络和概率图模型的信息，参见Koller和Friedman【74】，和Larranaga和Moral【83】。2.1、有关概率的概念),,,(21nXXXX是一个随机变量向量，),,,(21nxxxx是这些变量的一个可能的组合值，ix表示iX的一个可能值，iX是X的第i个分量，y表示子向量,nJJJXXYkJJK,,1),,(),,,(11的一个可能组合值。如果X中的所有变量是离散的，)(xXP（或简单的)(xP）用来表示变量的一个特定组合x的联合概率质量.当给定jjxX时,变量iX的具体取值ix的条件概率质量表示为)(jjiixXxXP（或简单的)(jixxp）。相似地，对于连续变量，联合密度函数表示为)(xP及条件密度函数表示为)(jixxp。当向量),,,(21nXXXX中所有变量不相关时,1x,,nxx用来代表广义的联合概率。Y、Z和W表示变量的三个不相交的子向量。那么，Y就叫做给定W时与Z条件独立（表示为),(WZYI），当且仅当对于所有的y，z，w，)(),(wywzy成立。2.2、贝叶斯网络的定义对于变量向量的一个贝叶斯网（BN）,S由两部分组成：·S表示一个有向无环图（DAG）结构，用来表达变量间的条件独立【30】关系。·一系列的局部参数表示给定它们父节点的不同组合值时，每个变量值的条件概率分布，是根据结构S确定的。图1a给出了一个含有六个变量的问题的贝叶斯网络结构。对于每个变量iX，i=1,…,n,结构S表示当给定iX的父节点iPa时，iX条件独立于它的除去父节点的非子孙节点。也就是，,\iiiiIXNDXPaPa。这个性质被叫作贝叶斯网的马尔科夫条件。因此，一个贝叶斯网编译了变量们的联合概率分布的因式分解。11,,nnBiiipxpxxpxpa，（1）图1.一个贝叶斯网络结构和参数的例子，它的一个变量4X假设1iri这里iPa表示父节点集iPa的一个可能组合值，等式（1）陈述了一个贝叶斯网中的变量的联合概率分布可以计算为给定单变量父节点时，单变量的条件概率分布的乘积。这些条件概率分布在贝叶斯网中被编译为局部参数i。在贝叶斯网络中一个相关的概念是变量的马尔科夫毯（MB）【107】。贝叶斯网络中变量的马尔科夫毯包括它的父节点、子节点、子节点的父节点（配偶节点）。马尔科夫毯子集的重要特性是贝叶斯网络中的每个变量只被它的马尔科夫毯影响。换句话说，给出变量的马尔科夫毯后，它条件独立于所有其它的变量（不包括它的马尔科夫毯），即)())(\,(iiiXMBXMBXXI。在离散的领域，当一个变量iX有ir个可能的取值，1,,iriixx，并且根据结构S它的父节点iPa有iq个可能的组合值，1,,iqiipapa，那么kjBiiijkPxpa表示在它的父节点取第j个组合值时，iX取第k个值的概率。由于所有的变量是离散的，父节点可能组合值的个数是可以容易计算出来miimXpaqr。贝叶斯网局部参数的第i个变量可表示为11iiqriijkkj。图1（b）给出了一个贝叶斯网中的一个离散变量的条件概率表的例子。2.3.机器学习中的贝叶斯网络2.3.1监督式学习近几年，在已经发表的研究中，出现了大量的用贝叶斯网进行监督分类的方法【82】。贝叶斯分类器计算具有最高后验概率的组值*c，并赋值给每一组的估计值1,,nxx：)(),,(maxarg),,(maxarg1111*cCPcCxXxXxXxXcCPcnncnnc（2）不同的贝叶斯分类器可以依据11,,nnpXxXxCc的因式分解获得。图2给出了一些贝叶斯分类器的例子。朴素贝叶斯（NB）【94】（图1a）是最简单的贝叶斯分类器。它建立在假设，当已知类值时预测变量是条件独立的。11,,nniipxxcpxc（3）图2贝叶斯分类器结构的不同类型半朴素贝叶斯分类器（SNB）【104】（图2b）考虑了一种新的变量类型来避免传统朴素贝叶斯的条件独立假设。这些变量通过结合最初的预测变量形成，它们的值来源于组成变量值的笛卡尔积。Pazzani【104】提出了一种贪婪封装方法(greedywrapper)来建立一个半朴素贝叶斯分类器（SNB），这个模型里无关变量C123654（a）朴素贝叶斯网2,3C1，5，64（b）半朴素贝叶斯C321456（c）TAN2C43561（d）kDB,k=2被移除，相关变量通过它们的笛卡尔积结合。树增强朴素贝叶斯（TAN）分类器【43】（图1c）延伸了NB分类器结构，通过在预测变量间构建一种树形结构来考虑它们的关系。K-依赖贝叶斯（kDB）分类器【122】（图1d）也延伸了BN分类器，通过一种更一般的结构，这种结构允许每个预测变量有k个父节点。贝叶斯分类器也可以用变量的马尔科夫毯来定义。特别地，类变量的马尔科夫毯指定一组预测变量来影响它的后验概率计算：))((),,(1CMBCPXXCPn（4）2.3.2无监督学习机器学习中另外一个使用BN的领域是无监督学习和聚类。一个n维随机变量nXXX,,1的数据聚类应该考虑数据产生机制所应用的结构限制假设。就BNs而言，约束状态应该是一个边缘，这个边缘从随机变量代表的聚类C到每个预测变量iX。因此，对(n+1)维随机变量XC,的联合概率分布的因式分解可表示为：),()(),(1iiniBBBpacxcPxc（5）注意，上式相似与监督分类贝叶斯网的因式分解。然而，主要的不同是，在聚类问题中变量C的值是未知的。并且要使用像EM算法【33】这样的技术来估计。2.4贝叶斯网络推理BN范式主要应用于内在不确定性领域的推理。模型内的推理，也就是在模型中，依赖反映变量间条件独立的结构来传播证据。Cooper提出在一般情况下有多重连通结构的BNs问题是NP难的。总的来说，证据的传播涉及分配概率给非实例变量的子集值，当一些其它变量值已知时。对于这个问题提出的方法可以分为两类：（a）准确算法【86,107】,和(b)近似算法，其中包括定性方法【13,38,65】和基于BN中的仿真样本方法【14,18,58,124】。关于这些算法的更详细情况，读者可以参考【16,29,66】。Lauritzen和Spiegelhalter【86】关于精确推理提出了一种最为流行的算法。第一步是端正化网络结构。在这一步里有共同子节点的变量(每个节点的不同父节点)被连接在一起(即在它们之间加一条边)，并移除所有边的方向。得到的图叫做端正图。第二步，就是所谓的三角化端正图。一个图被三角化就是任何长度大于三的圈加一条弦。这步被认为是Lauritzen和Spiegelhalter的算法中最难的一步（就计算的复杂性来说）。然后,所得的结构用来证据传播和概率计算.关于这种算法的进一步解释和叙述,参见Lauritzen和Spiegelhalter【86】。三角化端正图的基本方法是(参见图3)通过一系列移除图的节点。在移除一个节点和它所附带的边之前,我们检查如下:所有和它连接的节点都互相直接相连，通过向图中添加一些需要的边。根据变量给出的顺序来选择移除的节点。三角化的效果通过三角化后图tS的权重来测量)(log)(2CCXitirSw(6)其中C表示由变量iX组成的三角化图tS的最大团，每个iX有ir个可能不同的状态。三角化的效果最终被节点所移除的顺序完全决定。因此，搜索一个最优的三角化等价于搜索一个最优节点移除序列，即搜索一个最优的节点排列。Wen【136】表明，搜索最优三角化是NP难的。Kjarulff【72】将三角化方法与模拟退火算法进行了一个实证比较，获得了最好的结果。与在BN中寻找一个变量子集概率相反，我们有时需要找到最高概率的变量组合值。以下两个推理任务是与这个需要直接相关的。图3是一个三角化算法的例子。节点的移除顺序是：624351,,,,,XXXXXX，并假设.6,,1,1iiri（a）初始DAG。（b）相关的端正图。（c）移除1X：43211,,,XXXXC，添加边：32,XX，43,XX。（d）移除5X：542,XXC。（e）移除3X：3C;（f）移除64244,,:XXXCX，增加边：62,XX。（g）移除52:CX：（h）移除66:CX.（i）三角化图的总权重：.255log)753655432(log222.4.1.总溯因推理也叫做最可能解释问题（MPE）【106】，这种推理类型寻找BN中每个未知变量的最可能取值，当给定一组观测值00xX时。更正式地说，如果0\XXXU是一组未观察到的变量，那么目标就是获得组态UX相应的*Ux，如0*|maxargxxxUU（7）搜索MPE就像概率传播一样复杂（是NP难的）【125】。事实上，MPE可以通过概率传播算法得到，其中总和是在最后的边缘最大化操作这步中被替代【101】。2.4.2.部分溯因推理也叫做最大后验问题（MAP）,这种推理找出BN中变量子集的最可能组态，被叫做解释组。如果UEXX表示解释组，那么目标就是获得组态EX相应的*Ex,如)(maxarg0*xxxExEE（8）这个问题可以使用MPE问题再进行公式化，在EURXXX\中边缘化所有的变量。因此，找出MAP是比MPE问题更复杂，由于它有一个棘手的复杂性（NP难的），即使MPE可以在多项式时间（即polytrees）【103】内计