概率图模型4：贝叶斯网络

作者：孙相国

转载请注明出处

概率图模型主要研究四方面问题：

1. 表示
2. 推理
3. 学习

在本系列博文中，我们将按照下面的路线进行陈述：

1. 首先我们研究贝叶斯网络和无向图网络的最基本的概念。

2. 在此基础上，我们分出两个分支，一个是以贝叶斯网络为基础，一个是以无向图为基础，讨论学习问题：

3. 最后我们将会研究一些关于推理方面的知识.

• • 参考文献
  • 1 为什么要研究贝叶斯网络
  • 2 朴素贝叶斯模型
    • 21 基本方法
    • 22 参数估计
    • 23 python实现
  • 3 图与分布
    • 31基本任务
    • 32基本定义
      • 定义 1贝叶斯网的语义
      • 定义 2I-Map
      • 定义3 因子分解
      • 定义4贝叶斯网
    • 33 AB
    • 34 BA
  • 4 图中的独立性
    • 41 d-分离
      • 定义5有效迹
      • 定义6d-分离
      • 结论1可靠性
      • 结论2完备性
      • 结论3弱等价

0. 参考文献

[1] 概率图模型原理与技术（中文版）

[2] probabilistic graphical models（概率图模型原理与技术 英文版）

[3] 机器学习 周志华

[4] 统计学习方法 李航

[5] csdn博客：http://blog.csdn.net/github_36326955

[6] 模式识别

1.1 为什么要研究贝叶斯网络？

对于一个联合概率分布，我们需要跟多个独立变量来表示，甚至独立变量的个数会呈现指数级的增长。例如，考虑 P(X1,X2,X3,⋯,Xn) ，假如，每一个 Xi 都是二项分布的话。这样联合概率里面就有至少 2n−1 个参数（对应的是 X1,⋯,Xn 的全排列数目减一，减掉1是因为最后一种情况可以用1减掉之前的所有概率）。因此我们希望通过建立联合概率与图的关联，从图中找到条件独立性论断（并且我们可以证明，图中的条件独立性论断在联合概率中都是成立的。），这样就可以将原始的联合概率写成多个独立因子的乘积，从而减少独立变量的个数，使得模型更加“紧凑”。例如，如果我们可以建立一个概率图，并且从中发现了如下的独立性论断：
(Xi⊥X−i|C)
其中 X−i 表示 {X1,⋯,Xn}−{Xi} ,那么 P(C,X1,X2,X3,⋯,Xn) 可以写成:
P(C)Πni=1P(Xi|C)
注意到每一个 P(Xi|Cj) 都有两种情况（对应1个参数），因此公式 (2) 的参数个数只有 2n+1 个。

事实上，这种假设太强，但是仍然在很多应用的价值。接下来您将会看到，基于这种独立性假设建立的概率图表示模型，就是朴素贝叶斯模型。

“紧凑”，在这里的具体含义是：经过独立性约间的式子(2)，其独立参数个数小于原始的联合概率分布形势下独立参数个数。

1.2 朴素贝叶斯模型

单纯的介绍朴素贝叶斯模型和对应的概率图，并没有什么价值。事实上，关于朴素贝叶斯的定义，1.1节几乎已经介绍得很充分了。具体来说，在公式 (1) 中，我们把 C=c1,⋯,ck 看做样本的类别。把 Xi 看做样本的第 i 个维度的特征。那么，朴素贝叶斯假设的实际意义就很明显了：朴素贝叶斯模型假设在给定样本实例的类别的条件下，不同的性质可以独立的确定。

在本节，我们将要介绍的，是与朴素贝叶斯模型相关的一个机器学习算法：朴素贝叶斯法。它在文本分类中经常被使用（参见作者博文《python 中文文本分类》）。

1.2.1 基本方法

正如你在1.1节看到的公式 (2) 所表达的一样，公式 (2) 是对联合概率的一个计算。运用贝叶斯定理，我们可以很轻易的求得：
P(C=ck|X1:n)=P(C=ck)Πni=1P(Xi|C=ck)∑CP(C=cj)Πni=1P(Xi|C=cj)
公式 (3) 表达了对于给定观测样本，其属于类别 ck 的概率。因此朴素贝叶斯分类器可以表示为：
y=f(X1:n)=argmaxckP(C=ck)Πni=1P(Xi|C=ck)∑CP(C=cj)Πni=1P(Xi|C=cj)
考虑到分母对所有样本是相同的，因此，可以进一步规约为：
y=f(X1:n)=argmaxckP(C=ck)Πni=1P(Xi|C=ck)
从常理上看，朴素贝叶斯分类器把样本实例分到后验概率最大的类别，是很自然的，也是符合我们的认知的（你可以在作者这篇博文中找到更详细的解释《深入浅出EM算法与实践（持续更新）》）。那么，除了从感性的角度认为这种分类策略有道理外，我们能不能从更严谨的角度去考察这种分类策略的合理性呢？答案是可以的，事实上，朴素贝叶斯的分类策略，等价于期望风险最小化（更多的论述，读者可以参考其他文献，例如李航博士的《统计学习方法》4.1.2，这里不再赘述）。

1.2.2 参数估计

从公式 (5) 可以看到，我们需要估计的参数有 P(C=ck) 和 P(Xi=xi|C=ck)

由于这些概率事实上都是可以从样本集合中估计出来的，所以整个估计策略并不复杂。只是对样本做了一些基本的统计(极大似然估计)。例如：
P(C=ck)=∑ni=1I(yi=ck)n,k=1,2,⋯,K

P(Xi=xi|C=ck)=∑ni=1I(Xi=xi|C=ck)∑ni=1I(C=ck)

其中 I(.) 为指示函数。

需要注意的是：公式 (6,7) 都是基于现有的样本做统计的。那么，如果碰巧某类情况在样本中没有出现（事实上这种情况是很常见的，因为机器学习处理的数据是小规模的），那么就有可能遭遇某类概率为0的情况。因此，我们需要对公式做一个平滑处理：
P(C=ck)=∑ni=1I(yi=ck)+λn+Kλ,k=1,2,⋯,K;λ⩾0
特别的，当 λ=1 时，成为拉普拉斯平滑。

通过对分子分母加一个系数，我们实现了概率的平滑处理。事实上，在很多其他研究中，我们还有其他的办法让我们的概率“平滑”，一个最经典的例子就是将特征加权后，送入到logistic函数中。我们就可以很自然地得到一个人工构造的概率。更详细的内容，请参阅作者的博客《logistic回归》

1.2.3 python实现

从前几个小节的介绍来看，朴素贝叶斯分类器的实现，并不复杂。在scikit-learn库中，有直接的函数可以调用。只是这个库中的函数，为我们指定了公式 (5) 中的类条件概率分布的形式（比如可能是高斯分布，或者伯努利分布等）。关于scikit-learn库中相应函数的使用，你可以参考作者的博文《python 中文文本分类》。这里给出的代码，是没有指定任何分布，仅仅根据公式 (7,8) 得到的。

实例代码托管在GitHub上：

实例代码

1.3 图与分布

1.3.1基本任务

贝叶斯网图的形式化语义是一系列的独立性断言( I(G) ，见定义1)。另一方面它又是由条件概率分布做注释的图，并通过链式法则为贝叶斯网定义了一个联合分布( P )。本小节接下来的工作就是证明这两者的等价，即如下命题成立： A⇔B ，其中：

A: 分布 P 满足与图 G 相关的局部独立性。

B: P 可以由与图 G 相关的一系列条件概率分布表示。

换言之，若 P 可以由图 G 蕴含的的一系列条件概率表示时，那么 G 中的所有条件独立性都在 P 的所有条件独立性集合中，反之亦然。在接下来的内容里，你将会看到，A所表达的意涵就是I-Map,B所表达的意涵叫做因子分解。我们接下来首先给出几个基本概念。然后在此基础上进行命题的证明。

1.3.2基本定义

定义 1（贝叶斯网的语义）

贝叶斯网结构 G 是其节点代表随机变量 X1,⋯,Xn 的一个有向无圈图(DAG)。令 PaGXi 表示 Xi 在 G 中的父节点， NonDescendantsXi 在图中的非后代节点变量。

因此 G 表示了如下称为局部独立性的条件独立性假设，并且记为 Il(G) :

对每一个变量 Xi : (Xi⊥NonDescendantsXi|PaGXi)

话句话是说，局部独立性表明，在给定父节点的条件下，每个节点 Xi 与其非后代节点条件独立。

定义 2（I-Map）

设 G 为一个网络图，记 I(G) 为这个网络图 G 中蕴含的所有形如 (X⊥Y|Z) 的独立性断言集合。

设 P 为一个分布，记 I(P) 为在 P 中成立的所有形如 (X⊥Y|Z) 的独立性断言集合。

若 I(G)⊆I(P) ，则称 G 是一个I-Map(独立图)。

定义2 事实上描述了我们证明任务的前半部分，即：分布 P 满足与图 G 相关的局部独立性。正如我们从包含关系中所看到的：任何由 G 断言的独立性，在 P 中必然成立； P 中成立的独立性，未必能够体现在图 G 中。接下来，我们需要对证明任务的后半部分形式化定义： P 可以由与图 G 相关的一系列条件概率分布表示。

定义3 （因子分解）

令 G 为定义在变量 X1,⋯,Xn 上的一个贝叶斯网络。假如 P 可以表示为如下乘积：
P(X1,⋯,Xn)=Πni=1P(Xi|PaGXi)
则称分布 P 是关于图 G 的在同一空间上的因子分解。这个式子叫做贝叶斯网的链式法则，单个因子 P(Xi|PaGXi) 称为条件概率分布（CPD）或局部概率模型。

定义3 事实上描述了我们证明任务的后半部分，即： P 可以由与图 G 相关的一系列条件概率分布表示。正如我们从定义1中所看到的， G 中蕴含了如下的独立性论断： Il(G)={(Xi⊥NonDescendantsXi|PaGXi):Xi∈X1:n} 。我们假定 X1,X2,⋯,Xn 的顺序就是图 G 的一个拓扑序。那么：
P(X1,⋯,Xn)=P(X1)P(X2|X1)P(X3|X1,X2)⋯P(Xn|X1,⋯,Xn−1)
其中公式 (10) 对任何联合分布都是适用的。由于 X1,X2,⋯,Xn 是图 G 的一个拓扑序，因此对于式子 (10) 中的任意一项 P(Xi|X1,⋯,Xi−1) ，有 {X1,⋯,Xi−1}=PaGXi∪Z,Z⊆NonDescendantsXi ，根据独立性论断 Il(G) ,有 P(Xi|X1,⋯,Xi−1)=P(Xi|PaGXi) ，进而有公式 (9) .

由定义3，我们可以给出贝叶斯网络的定义：

定义4（贝叶斯网）

一个贝叶斯网是一个偶对 B=(G,P) ,其中 P 是 G 上的因子分解，并且 P 指定为关联在 G 上节点的一系列条件概率分布，通常记为 PB 。

接下来,本文将对1.3.1节中的两个命题做等价性证明，这两个命题是：

A: 分布 P 满足与图 G 相关的局部独立性。

B: P 可以由与图 G 相关的一系列条件概率分布表示。

我们首先证明 A⇒B ，再证明 A⇐B .

1.3.3 A=>B

A⇒B 的语义表述为：

令 G 是定义在变量集 X 上的一个贝叶斯网络，并且 P 是同一个空间上的联合分布。如果 G 是 P 的一个I-map，那么 P 根据 G 因子分解。

证明：

假定 X1,X2,⋯,Xn 的顺序就是图 G 的一个拓扑序。

由概率的链式法则有：
P(X1,⋯,Xn)=P(X1)P(X2|X1)P(X3|X1,X2)⋯P(Xn|X1,⋯,Xn−1)
由于 G 为I-map,因此 G 中蕴含了如下的独立性论断： Il(G)={(Xi⊥NonDescendantsXi|PaGXi):Xi∈X1:n} .且 Il(G)⊆I(P) 。

由于 X1,X2,⋯,Xn 是图 G 的一个拓扑序，因此对于式子 (11) 中的任意一项 P(Xi|X1,⋯,Xi−1) ， Xi 的所有父节点都在集合 {X1,⋯,Xi−1} 中，并且这个集合不存在任何 Xi 的后代节点,即： {X1,⋯,Xi−1}=PaGXi∪Z,Z⊆NonDescendantsXi ，根据独立性论断 Il(G) 和条件独立性分解性质，有： P(Xi|X1,⋯,Xi−1)=P(Xi|PaGXi) ，进而有公式 (9) .

得证

1.3.4 B=>A

B⇒A 的语义表述为：

令 G 是定义在变量集 X 上的一个贝叶斯网络，并且 P 是同一个空间上的联合分布。如果 P 根据 G 因子分解，那么 G 是 P 的一个I-map。

证明：

为了证明命题成立，只需证明:

P(Xi|NonDescendantsXi,PaGXi)=P(Xi|PaGXi)

同样假定 X1,X2,⋯,Xn 是图 G 的一个拓扑序.令 NonDescendantsXi={Xn1,Xn2,⋯,Xnk} 其中， {Xn1,Xn2,⋯,Xnk} 是 {X1,X2,⋯,Xi−1} 中的子集.令 PaGXi={N1,⋯,Nm},Ni∈{X1,X2,⋯,Xn}

则：
P(Xi|NonDescendantsXi,PaGXi)=P(Xi,Xn1,Xn2,⋯,Xnk,N1,⋯,Nm)P(Xn1,Xn2,⋯,Xnk,N1,⋯,Nm)
上式的分子可以由因子分解的定义写成：
P(Xi|PaXi)P(Xn1|PaXn1)⋯P(Xnk|PaXnk)P(N1|PaN1)P(N2|PaN2)⋯P(Nm|PaNm)
其中，上式所有的 PaM 都不含 Xi 。

式子 (12) 分母可以写成：
∑xiP(Xi,Xn1,Xn2,⋯,Xnk,N1,⋯,Nm)
进一步地，对式子 (14) 写成式子 (13) 的形式则为：
P(Xn1|PaXn1)⋯P(Xnk|PaXnk)P(N1|PaN1)P(N2|PaN2)⋯P(Nm|PaNm)∑xiP(Xi|PaXi)
其中 ∑xiP(Xi|PaXi)=1 ,因此式子 (15) 变为：
P(Xn1|PaXn1)⋯P(Xnk|PaXnk)P(N1|PaN1)P(N2|PaN2)⋯P(Nm|PaNm)
公式 (16) 是公式 (12) 中的分母，公式 (13) 是公式 (12) 中的分子。故有：
(12)=P(Xi|PaXi)P(Xn1|PaXn1)⋯P(Xnk|PaXnk)P(N1|PaN1)P(N2|PaN2)⋯P(Nm|PaNm)P(Xn1|PaXn1)⋯P(Xnk|PaXnk)P(N1|PaN1)P(N2|PaN2)⋯P(Nm|PaNm)=P(Xi|PaXi)
得证。

1.4 图中的独立性

在1.3节中，我们解决了命题 A 与命题 B 的等价，但是前提是在贝叶斯网络这个大框架中。换言之，由贝叶斯网的语义定义，我们讨论的独立性假设集合是： Il(G) ，即对每一个变量 Xi : (Xi⊥NonDescendantsXi|PaGXi) 。也就是说，1.3节为我们解决了这样的一个问题：虽然只是知道分布 P 根据 G 因子分解，但是仍然可以得出 P 满足 Il(G) 的结论。

接下来的问题是：在 G​ 中是否存在其他形式的独立性，使得这些独立性对于根据 G​ 分子因解的分布 P​ 仍然成立？

这就是本节要解决的问题。

1.4.1 d-分离

本节要讨论的是在什么情况下， X 在给定 Z 时可能影响 Y .如果我们能够穷举所有情况，那么我们就可以进一步得出什么时候可以保证独立性条件 (X⊥Y|Z) 在于贝叶斯网络 G 相关的分布中成立。

当影响经过 Z 可以从 X 流向 Y 时，迹 X⇌Z⇌Y 成为有效的。对有效迹分析结果总结：

因果迹 X→Z→Y :有效当且仅当没有观测到 Z 。

证据迹 X←Z←Y :有效当且仅当没有观测到 Z

共同的原因 X←Z→Y :有效当且仅当没有观测到 Z

共同的作用（V-结构） X→Z←Y :有效当且仅当观测到 Z 或 Z 的后代。

定义5（有效迹）

令 G 是一个贝叶斯网络，且 X1⇌⋯⇌Xn 是 G 中的一条迹。令 Z 是观测变量的一个子集。在给定 Z 的情况下，加入：

若有一个V结构 Xi−1→Xi←Xi+1 ,则 Xi 或其一个后代在 Z 中

迹上的其他节点都不在 Z 中

那么迹 X1⇌⋯⇌Xn 是有效迹

定义6（d-分离）

令 X,Y,Z 是图 G 的三个节点集。在给定 Z 的情况下，假如任意节点 Xi∈X 与 YI∈Y 之间不存在有效迹，那么 X 与 Y 在给定 Z 时是d-分离的，记作 d−sepG(X;Y|Z)

与d-分离相对应的独立性集合用 I(G) 表示： I(G)={(X⊥Y|Z):d−sepG(X;Y|Z)}

接下来我们直接给出一些有用的结论，对这些结论的直观理解，可以参考后面的示意图：

在示意图中，矩形代表图 G 的独立性集合。椭圆代表的是根据 G 因子分解的分布。黑色圆形代表蕴含在各个组份中的独立性。

结论1(可靠性)

如果分布 P 根据 G 因子分解，那么 I(G)⊆I(P) .

从图上来理解，可以看到 P1,P2,P3 都是图 G 的因子分解，它们都包含了图 G 的d分离独立性集合。

注意到 I(G)={(X⊥Y|Z):d−sepG(X;Y|Z)} ，而 I(P)={(X⊥Y|Z)}

因此，结论1表明：如果给定某个 Z 时，找到的两个节点 X 与 Y 是d-分离的，那么可以保证，在给定 Z 时，它们实际上是条件独立的。(如示意图中所表达的含义：)

结论2(完备性)

令 G 是一个贝叶斯网络。如果给定 Z 时， X 与 Y 在 G 中不是d-分离的（例如示意图中的“其他独立性1”），那么给定 Z 时， X 与 Y 在某些可以在 G 上因子分解的分布中（例如示意图中“其他独立性1”相对于 P2 ）相互依赖。

这个命题的逆否命题为：在所有可以在 G 上因子分解的分布 P 中，如果 (X⊥Y|Z) ，那么有 d−sepG(X;Y|Z) .对应于示意图上的解释为：对 P1,P2,P3 均成立的独立性（事实上就是三个椭圆相交的黑色圆），必然是图 G 中的d分离的子集。

事实上，结论1描述的是可靠性，结论2描述的是完备性。综合结论1和结论2，我们可以得到结论3：

结论3(弱等价)

对于几乎所有在 G 上因子分解的分布 P ，我们有 I(P)=I(G) .

结论3在示意图上的解释为：忽略掉了其他独立性1,2,3,4.

（在示意图中，矩形代表图的独立性集合。椭圆代表的是根据因子分解的分布。黑色圆形代表蕴含在各个组份中的独立性。）