贝叶斯网络

包括贝叶斯网络、马尔可夫随机场及其缩写形式MRF（Markov Random Field）和因子图在内的各种概念模型，在本质上都是用来描述系统中变量之间相互依赖关系的工具；由此可见，这些概念均归属于机器学习领域内的概率图形模型（PGM, Probability Graphical Model）。

一：定义

该系统被称作贝叶斯网络体系（Belief Network System, BN），它是一种基于有向无环图框架构建的概率分布系统，在此框架下每个节点xi都有直接父节点parent(xi)，这些条件概率分布共同构成了系统的知识库部分。该系统被广泛应用于模拟人类推理过程中的因果关系不确定性处理机制模型，在此过程中其拓扑结构维持为有向无环图（DAG）特征模式。

那么给定了样本(包括特征和标签)，我们为什么要建立贝叶斯网络呢？

为了便于理解这一概念，在此提供一个简明的示例：假设我们有一个训练集（其中每个样本由若干特征组成），具体包括吸烟史、呼吸系统疾病病史、癌症病史以及胸片结果；同时每个样本都有一个对应的标签——咳嗽频率，并且这些数据均为伯努利分布）。接下来的问题是如何计算这些变量之间的联合概率分布？

那么此时我们从数据中得出了2⁵−¹=3¹个概率（即5位二进制码中的一个具体组合如01111所对应的概率就是一个），从而当别人询问某特定事件的发生概率时（例如p(s=1,b=1,c=0,x=0,d=1)），我们可以通过这3¹个可能的情况来确定其发生概率是多少。而在贝叶斯网络模型中，并不需要像传统方法那样存储大量参数数量（如图所示为该模型的拓扑结构图）。具体而言，在已知条件(C,B)的情况下发生D事件的概率时，则只需要4个参数；同样地，在已知条件B的情况下发生C事件的概率时，则需要2个参数；而当已知条件C的情况下发生X事件的概率时，则同样需要2个参数；类似地，在已知条件D的情况下发生S事件的概率时，则需要4个参数；最后，在已知条件S的情况下发生X事件的概率时，则仅需一个参数即可描述这种情况下的发生概率分布情况。综上所述这些必要的基本参数总共有：4+2+2+4+1=13个独立的条件概率值。一旦我们能够从样本数据集中获得这全部的13个独立条件概率值及其对应的分布表，则就可以直接利用这些信息来计算出整个系统的联合概率分布表。因此利用贝叶斯网络方法不仅显著简化了计算过程而且一旦给出了完整的贝叶斯网络拓扑结构以及所有相关变量对应的条件概率分布表，则可以方便地求解任意给定条件下各变量之间的关系及其联合发生的可能性大小

一个正常的贝叶斯网络的联合概率分布为：

贝叶斯网络模型的过程为：

基于给定的数据集建立贝叶斯网络的拓扑结构和各节点的概率参数；这些过程通常需要结合先验知识并运用极大似然估计法来实现。

基于贝叶斯网络建立的结点拓扑结构及其条件概率分布前提下，可用于应用该网络进行推断未知数据的条件概率或后验概率，并从而实现诊断、预测或分类的目标。

特别注意：在分析网络拓扑结构时，请关注节点所包含的信息内容。例如，在贝叶斯网络拓扑结构示例中，请注意以下几点：首先，在该拓扑结构中节点被划分为两类数据字段——第一类是用于标识对象特性的属性字段；第二类是用于区分不同对象的状态区分字段。其次，在该模型设计中我们采用了一种层次化的数据组织方式以提高模型预测效率

二：贝叶斯网络的构造

识别随机变量间的拓扑关系以构建DAG。该步骤一般由领域专家负责实施，并且要获得良好的拓扑结构往往需要反复优化。

下面给出构造DAG的算法：

算法过程：

(1) 选择变量的一个合理顺序：X1，X2，…Xn

(2) 对于i=1到n：在网络中添加结点Xi, 在X1，X2…Xi-1选择Xi的父母，使得

(3) 这种构造方法显然保证了全局的语义要求：

请特别注意：其产物取决于变量的初始化顺序，在这种情况下所得的结果可能不够优雅——即它可能不是最理想的贝叶斯网络结构。在此情形下条件概率表可能会需要额外的参数量

三：通过贝叶斯网络判定的条件独立

通过贝叶斯网络可以得到三种情况的条件独立：

（1）形式1：head-to-head

贝叶斯网络的第一种结构形式如下图所示：

所以有：P(a,b,c)= P(a)*P(b)*P(c|a,b)成立，化简后可得：

基于c未知的条件下（c unknown），当a和b之间发生阻断（blocked），它们彼此之间保持相互独立（mutually independent），我们将其定义为head-to-head条件独立性（head-to-head conditional independence）。这一概念与图中最初展示的情况相对应（corresponds to the initial illustration in the text）。

(2) 形式2：tail-to-tail

贝叶斯网络的第二种结构形式如下图所示

考虑c未知，跟c已知这两种情况：

1. 在c未知的时候，有：P(a,b,c)=P(c)*P(a|c)*P(b|c)，此时，没法得出P(a,b) = P(a)P(b)，即c未知时，a、b不独立。
2. 在c已知的时候，有：P(a,b|c)=P(a,b,c)/P(c)，然后将P(a,b,c)=P(c)*P(a|c)*P(b|c)带入式子中，得到：P(a,b|c)=P(a,b,c)/P(c) = P(c)*P(a|c)*P(b|c) / P(c) = P(a|c)*P(b|c)，即c已知时，a、b独立。

因此，在c被固定时（即给定c），a和b之间的影响因素阻止了它们之间的直接影响**（blocked）而它们之间的关系仅通过其他变量间接影响（tail-to-tail condition of independence）**. 我们将其称为尾到尾条件下的独立性（tail-to-tail condition of independence），这与本节开头所展示的第一张图中所描述的情况一致：“当给定x4时,x6和x7相互独立”.

(3) 形式3：head-to-tail

贝叶斯网络的第三种结构形式如下图所示：

还是分c未知跟c已知这两种情况：

1. 当c未知时：有P(a,b,c) = P(a) \cdot P(c|a) \cdot P(b|c)；但无法得出P(a,b) = P(a) \cdot P(b)；即当c未知时a与b不独立。
2. 当c已知时：有P(a,b|c) = \frac{P(a,b,c)}{P(c)}；并且根据P(a,c) = P(a) \cdot P(c|a) = P(c) \cdot P(a|c)可以化简得到：

鉴于此，在给定变量c的情况下，当a和b被阻止时，并不相互影响（它们彼此之间存在依赖关系），因此我们称这种情况为head-to-tail条件独立。

插一句 ：这个head-to-tail其实就是一个链式网络，如下图所示：

在之前的介绍中可知，在给定 xi 的情况下, xi+1 的概率分布与 x₁, x₂, …, xi-₁ 相互独立。那这到底是什么意思呢？具体来说是说: 在给定 x_i 的情况下, x_{i+1} 的状态仅受其前一状态的影响,并不与其他更早的状态相关联。简单来说就是: 现在的状态仅由前一个状况决定,不受更早状况的影响。这种顺次演变的过程就叫做马尔可夫链 (Markov chain) 是一种描述系统状态转移的概率模型

四：贝叶斯网络推断概率的通用方法

利用贝叶斯网络即可对未知样本集推导出其条件分布或后验分布，并实现对未知样本集的诊断、预测或者分类分析。在实际应用中，通常会采用边缘化的方式进行处理以获得所需的统计量信息。本文则系统阐述了基于贝叶斯网络实现边缘分布推导的具体步骤。

o 由贝叶斯网络得到因子图(Factor Graph)

o 通过在因子图中消息传递的思想，计算概率(sum_product算法)

所以下面要讲解因子图和sum_product算法

因子图：

维基百科上给出的因子图的定义如下：

这里举个栗子来说明：

然而，在实际应用中我们可以使用一种称为Forney-stylefactorgraph的变型。其构建方法论基础是什么呢？

• 在贝叶斯网络中，每个因子与因子图上的相应节点之间建立了一一对应关系。
• 贝叶斯网络中的每个变量会在其对应的边上或半边上进行表示。
• 节点g与边x相连的条件是该边所代表的变量x存在于对应的因子g之中。

给个栗子，如下：

Sum_product 算法

获得因子图后, 我们即可采用Belief Propagation Algorithm（亦称为Message Passing Algorithm）的信息传递机制来计算边缘概率分布函数.

基于某随机变量fk的边缘概率值，可通过其相关变量x1,x2,x3,...,xn的联合概率分布来计算。具体数学表达式为：

而一般情况下我们能够利用贝叶斯网络的拓扑结构及其条件概率表来进行计算。不过这确实会让人感到困惑那有没有更简便的办法呢？这里通过例子从而引出消息传递的思想。

举个栗子，假定现在我们需要计算计算如下式子的结果：

同时，因子图为：

借鉴分配率，我们可以提取公因子：

由于变量的边缘概率等于所有与其直接相关的函数依次传递回来的信息的积，因此计算得到：

认真分析了前文所述的计算流程后会发现值得注意的是其中涉及到了类似于消息传递的观点主要包含两部分

第一步操作是在对f进行分析时完成的任务；该任务涉及基于蓝色和红色虚线框所界定区域外部的信息流动情况

计算可得：

第二步、根据蓝色虚线框、红色虚线框围住的两个box内部的消息传递：

最后： 以下给出sum_product算法的总体框架：

五：贝叶斯网络解决有环问题

可知，在贝叶斯网络中包含有向循环时（即网络结构为双向连接），所构造的因子图也会形成循环结构。基于消息传递的方法而言，在这种情况下，该消息将无限地传播下去而无法完成有效的概率计算。

解决方法有三个：

移除贝叶斯网络中的某些连接，并通过这一操作避免了形成无向循环。所采用的核心思想基于最大权重生成树算法（MSWT）。此处略做解释，请参考文末参考文献以获取更多信息。

2：重构无环贝叶斯网络—基于调整初始排序可以获得更好的贝叶斯网络结构。

采用loopy belief propagation算法（即基于sum-product算法的递归版本），该方法通常会采用以下步骤：首先，在一个环路中随机初始化某条消息的权重；随后利用sum-product算法进行迭代计算；由于存在环路结构，在迭代过程中最终会更新到最初设置的那个变量的消息；这一过程会持续直至系统中的所有消息不再发生变化为止。然而该方法的一个显著缺点是无法保证收敛性；尽管如此，在大多数实际应用中该算法仍能有效收敛。

参考文献：

<>探讨起源于贝叶斯推理模型的系统化演绎过程

2. 点击此处访问我们的文章：http://blog.jobbole.com/86441/?from=timeline&isappinstalled=0 算法杂货铺 - 贝叶斯网络作为分类器相关技术的基础