贝叶斯网络推理算法：优化与应用

推理是从给定的证据中得到一个新判断的思维形式。贝叶斯网络推理是利用其表达的条件独立性，快速计算待求概率值的过程。

条件独立性假设是贝叶斯网络进行定量推理的理论基础。有了这个假设，就可以减少先验概率的数目，简化计算和推理过程。贝叶斯网络的条件独立性假设的一个很重要的判据就是著名的D分隔（D-separation）定理。先来看看这个定理，设A、B、C为网络节点中三个不同的子集，当且仅当A与C间不存在以下情况的路径时，称B隔离了A和C，记为＜A|B|C＞D：所有含有聚合弧段的节点或其子节点是B的元素；其他节点不是B的元素。

同时满足以上两个条件的路径称作激活（Active）路径，否则叫作截断（Blocked）路径。这个判据指出，如果B隔离了A和C时，那么可以认为A与C是关于B条件独立的，即

P（A|C，B）=P（A|B） （7-74）

有了条件独立性假设就可以大大简化网络推理计算。但是，与其他形式的不确定性推理方法一样，贝叶斯网络推理仍然需要给出许多先验概率，它们是根节点的概率值和所有子节点在其母节点给定下的条件概率值。这些先验概率，可以是由大量历史的样本数据统计分析得到的，也可以是由领域专家长期的知识或经验总结主观给出的，或者是根据具体情况由事先假设给定的。

与其他算法一样，贝叶斯网络推理算法大致也可分为精确算法和近似算法两大类。理论上，所有类型的贝叶斯网络都可以用精确算法来进行概率推理。但Cooper指出，贝叶斯网络中的精确概率推理是一个NP难题。对于一个特定拓扑结构的网络，其复杂性取决于节点数。所以，精确算法一般用于结构较为简单的单联（Single Connected）网络。对于解决一般性的问题，人们不希望它是复杂的多项式。因而，许多情况下都采用近似算法。它可以大大简化计算和推理过程，虽然它不能够提供每个节点的精确概率值。

目前主要的推理算法主要有如下四类：多树传播（Polytree Propagation）算法、团树传播（Clique Tree Propagation）算法、图约简（Graph Reduction）算法、组合优化（Combina-torial Optimization）算法。

1.多树传播算法

多树传播算法的主要思想是给贝叶斯网络中的每一个节点分配一个处理机，每一个处理机利用相邻节点传递来的消息和存储于该处理机内部的条件概率表进行计算，以求得自身的后验概率（信度），并将结果向其余相邻节点传播。在实际计算中，贝叶斯网络接收到证据以后，证据节点的后验概率值发生改变，该节点的处理机将这一改变向它的相邻节点传播；相邻节点的处理机接收到传递来的消息后，重新计算自身的后验概率，然后将结果向自己其余的相邻节点传播，如此继续下去，直到证据的影响传遍所有的节点为止。在多连通图（即至少在两个节点间存在不止一条通路）的情况下，由于消息传递的双向性，使得消息会在无向环路中循环传播而无法进入稳态，得不到最终结果。为此，许多学者提出了各种弥补的办法，如条件（Conditioning）方法、节点集成（Node Aggregation）方法、星形分离（Star Decomposition）方法。这些方法的主要思想都是对原贝叶斯网络进行变换，将其由多连通的拓扑结构变换为单连通的拓扑结构，然后再利用多树传播算法进行计算，最后对计算的结果进行处理，以还原为待求概率值。

2.团树传播算法(www.xing528.com)

团树传播算法采用了另一种图形表达方式来表达联合概率分布。该方法所对应的图形结构是一棵无向树——团树。基于团树的推理计算也采用了消息传递的思想。在实际推理时，当接收到证据以后，所有包含证据节点的团节点内各个变量的联合概率函数值（以下简称q函数值）将发生变化。该变化将向团树中的所有团节点传播，以改变这些节点中的函数值。该算法由于所对应的图形结构是一棵树，因此不会出现多树传播算法在多连通情况下消息往复传播的问题。当系统达到稳态后，对函数值进行边缘化计算就可以求解得到待求概率值。采用该方法进行推理的第一步，就是首先构造一棵团树，目前有几种方法，通常采用连接树（Junction Tree）构造方法（称由这种方法构造的团树传播算法为连接树传播算法）。同多树传播算法一样，团树传播算法采用在图形结构上的消息传播机制进行运算。消息从每一个接收到证据的团节点开始，向图上的其他节点传播，在传播过程中，每次计算只使用相邻节点的q函数值。

3.图约简算法

图约简算法是Shachter于1988年提出的一种贝叶斯网络推理算法，它直接利用图形结构，采用了节点消元的方式来模拟边缘概率的计算。其基本思想是，逐步删除非证据节点中无子节点的节点（可以直接删除的节点所必须满足的条件），直到网络中只剩下感兴趣的节点为止。对于不满足删除条件的节点，可以对网络结构进行变换。

4.组合优化算法

前面的三类方法都是利用了图形结构以寻求局部化的计算过程，而组合优化算法则是直接针对联合概率分布的组合爆炸问题，提出解决方案。其主要思想是，首先利用链规则和条件独立性，将联合概率分布分解为一系列条件概率表的乘积；然后在符号层面上，对公式进行交换，改变求和时节点的消元顺序以及求和运算与乘积运算的先后秩序，以达到减少求和与乘积运算量的目的；最后按照变换后的公式进行逐步的乘积和求和运算，以得到待求结果。目前这类方法主要有符号概率推理（Symbolic Probabilistic Inference，SPI）方法和桶消去（Bucket Elimination）方法。

以上所介绍的贝叶斯网络推理算法都没有摆脱显式求和的计算方式，其计算量都是随着节点数的增多而呈指数增长，但有各自的特点。其中，团树传播算法基于了一个更简单的图形结构——树，其灵活性和适应面都比较好。一些其他图形结构的推理，如影响图（Influ-ence Diagram）推理也转换到团树上进行。目前针对该方法更进一步提出了一些加速推理的措施，比如惰性传播（Lazy Propagation）方法。在实际应用中，连接树传播算法应用较为广泛。

5.贝叶斯网络近似推理算法

尽管贝叶斯网络以其坚实的概率理论基础以及有效性而被认为是目前最好的不确定推理方法之一，但由于结构复杂的贝叶斯网络推理计算是一难题，对贝叶斯网络推理的研究重心转向了近似推理算法的研究。目前已经提出了多种近似推理算法，主要分为两大类：基于仿真的方法和基于搜索的方法。这些算法都采取一定的方式，在运行时间和推理精度上寻求一个折中，力求在较短的时间内得到一个满足精度要求的结果。基于仿真的方法是基于Monte-Carlo方法的基本思想，使用了一个包含随机数发生器的采样装置，根据需要产生一组样本。然后通过对样本的处理，而不是直接利用联合概率分布进行计算，以得到待求概率的近似值。另一类近似算法是基于搜索的方法，由于概率问题是一类组合问题，所以可以将所需要计算的各个变量的不同组合看作一个状态空间，状态空间中的某些状态对最后的计算结果会产生较大的影响，而另外一些状态则影响甚微。由此，可以通过启发式搜索的方法在整个状态空间中进行搜索，以寻找到那些对计算结果影响较大的状态。然后以这些影响较大的状态代替整个状态空间参与运算，以达到提高计算效率的目的，并且在计算结束时能够给出一个较精确的解答。

虽然永远不可能找到一个多项式时间复杂度的贝叶斯网络推理算法，但是对于实际的贝叶斯网络，总可以通过简化或通过各种方法的结合找到适合的推理算法。