从朴素贝叶斯分类器到贝叶斯网络（下）-CDA数据分析师官网

从朴素贝叶斯分类器到贝叶斯网络（下）

2017-03-18

从朴素贝叶斯分类器到贝叶斯网络（下）

三、贝叶斯网络

贝叶斯网络（Bayesian Network）是一种用于表示变量间依赖关系的数据结构，有时它又被称为信念网络（Belief Network）或概率网络（Probability Network）。在统计学习领域，概率图模型（PGM，Probabilistic Graphical Models）常用来指代包括贝叶斯网络在内的更加宽泛的一类机器学习模型，例如隐马尔可夫模型（HMM，Hidden Markov Model）也是一种PGM。

具体而言，贝叶斯网络是一个有向无环图（Directed Acyclic Graph），其中每个节点都标注了定量的概率信息，并具有如下结构特点：

（1）一个随机变量集构成了图结构中的节点集合。变量可以是离散的，也可以是连续的。

（2）一个连接节点对的有向边集合反映了变量间的依赖关系。如果存在从节点X指向节点Y的有向边，则称X是Y的一个父节点。

（3）每个节点Xi都有一个（在给定父节点情况下的）条件概率分布，这个分布量化了父节点对其之影响。

在一个正确构造的网络中，箭头显式地表示了X对Y的直接影响。而这种影响关系往往来自于现实世界的经验分析。一旦设计好贝叶斯网络的拓扑结构，只要再为每个节点指定当给定具体父节点时的条件概率，那么一个基本的概率图模型就建立完成了。尽管现实中贝叶斯网络的结构可能非常复杂，但无论多么复杂的拓扑本质上都是由一些基本的结构单元经过一定之组合演绎出来的。而且最终的拓扑和对应的条件概率完全可以给出所有变量的联合分布，这种表现方式远比列出所有的联合概率分布要精简得多。图1给出了三种基本的结构单元，下面我们将分别对它们进行介绍。

图1 三种基本的结构单元
首先，如果几个随机变量之间是完全独立的，那么它们之间将没有任何的边进行连接。而对于朴素贝叶斯中的假设，即变量之间是条件独立（Conditionally Independent）的，那么可以画出此种结构如图1中的左图所示。这表明在给定Y的情况下，X和Z是条件独立的。

其次，另外一种与之相反的情况如图1中的中图所示。此时X和Z是完全独立的。我们通常把左图的情况称为“Common Cause”，而把中图的情况称为“Common Effect”。

最后，对于图1中右图所示的链式结构，X和Z不再是相互独立的。但在给定Y时，X和Z就是独立的。因为P(Z|X,Y)=P(Z|Y)。

文献[1]中给出了一个简单的贝叶斯网络示例，如图2所示。假设你在家里安装了一个防盗报警器。这个报警器对于探测盗贼的闯入非常可靠，但是偶尔也会对轻微的地震有所反应。你还有两个邻居John和Mary，他们保证在你工作时如果听到警报声就给你打电话。John听到警报声时总是会给你打电话，但是他们有时候会把电话铃声当成警报声，然后也会打电话给你。另一方面，Mary特别喜欢大声听音乐，因此有时候根本听不见警报声。给定了他们是否给你打电话的证据，我们希望估计如果有人入室行窃的概率。

图2 贝叶斯网络示例

现在暂时忽略图中的条件概率分布，而是将注意力集中于网络的拓扑结构上。在这个防盗网络的案例中，拓扑结构表明盗贼和地震直接影响到警报的概率（这相当于一个Common Effect的结构），但是John或者Mary是否打电话仅仅取决于警报声（这相当于一个Common Cause的结构）。因此网络表示出了我们的一些假设：“John和Mary不直接感知盗贼，也不会注意到轻微的地震”（这表明当给定随机变量Alarm时，“盗贼或地震”都独立于“打电话”），并且他们不会在打电话之前交换意见（所以在给定随机变量Alarm时，John打电话和Mary打电话就是条件独立的）。

注意网络中没有对应于Mary当前正在大声听音乐或者电话铃声响起来使得John误以为是警报的节点。这些因素实际上已经被概括在与从Alarm到JohnCalls或者到MaryCalls这两条边相关联的不确定性中了。这同时体现了操作中的惰性与无知：要搞清楚为什么那些因素会以或多或少的可能性出现在任何特殊情况下，需要大量的工作，而且无论如何我们都没有合理的途径来获取相关信息。上面的概率实际上概括了各种情况的潜在无限集合，其中包括报警器可能会失效的情况（诸如环境湿度过高、电力故障、电线被切断、警铃里卡了一只死老鼠等等）或者John和Mary没有打电话报告的情况（诸如出去吃午饭了、外出度假、暂时性失聪、直升机刚巧飞过而噪声隆隆等）。如此一来，一个小小的智能体可以处理非常庞大的世界，至少是近似地处理。如果我们能够引入附加的相关信息，近似的程度还可以进一步地提高。

现在回到图中的条件概率分布上。每一个分布都被显示为一个条件概率表（CPT, Conditional Probability Table）。这种形式的表格适用于离散型随机变量。本文也仅讨论这种类型的表示方法。CPT中的每一行包含了每个节点值在给定条件下的条件概率。这个所谓的“给定条件”就是所有父节点取值的某个可能组合。每一行概率加起来和必需是1，因为行中条目表示了该对应变量的一个无遗漏的情况集合。对于布尔变量，一旦知道它为真的概率是p，那么它为假的概率就应该是1-p。所以可以省略第二个数值。通常，一个具有k个布尔父节点的布尔变量的CPT中有2^k个独立的可指定概率。而对于没有父节点的节点而言，它的CPT只有一行，表示了该变量可能取值的先验概率（例如图中的Burglary和Earthquake对应的CPT）。

四、模型推理

当我们已经确定了一个贝叶斯网络的结构时，如何利用它进行推理将成为焦点。例如现在我们想知道当John和Mary都打电话时发生地震的概率。即 P(E = T | J = T, M = T) = ?

总的来说，通常可采用的方法有三种：1）首先是利用与朴素贝叶斯类似方法来进行推理（其中同样用到贝叶斯公式），我们称其为枚举法；2）其次是一种更为常用的算法，我们称之为消去法；3）最后还有一种基于蒙特卡洛法的近似推理方法，本文将仅讨论前两种算法。

4.1 枚举法

为了详细地说明原委，我们还是从一个简单的概率论知识点开始。众所周知，由n个随机变量X1, X2, ..., Xn构成的向量

X = (X1, X2, ..., Xn) 称为n维随机向量（或称n维随机变量）。首先我们以二维随机向量(X,Y)为例来说明边缘分布的概念。随机向量(X,Y)的分布函数F(x,y)完全决定了其分量的概率特征。所以由F(x,y)便能得出分量X的分布函数FX(x)，以及分量Y的分布函数FY(y)。而相对于联合分布F(x,y)，分量的分布FX(x)和FY(y)称为边缘分布。由

FX(x) = P{X ≤ x} = P{X ≤ x, Y ≤ +∞} = F(x, +∞)

FY(y) = P{Y ≤ y} = P{X ≤ +∞,Y ≤ y} = F(+∞, y)

可得

FX(x) = F(x, +∞)， FY(y) = F(+∞, y)

若(X,Y)为二维离散随机变量，则

若(X,Y)为二维连续随机变量，设密度函数为p(x,y)，则

回想在朴素贝叶斯中所使用的策略。我们根据已经观察到的证据计算查询命题的后验概率。并将使用全联合概率分布作为“知识库”，从中可以得到所有问题的答案。这其中贝叶斯公式发挥了重要作用，而下面的示例同样演示了边缘分布的作用。从一个非常简单的例子开始：一个由3个布尔变量Toothache、Cavity以及Catch （由于牙医的钢探针不洁而导致的牙龈感染）组成的定义域。其全联合分布是一个2 × 2 × 2 的表格，如下表所示。

根据概率公理的要求，联合分布中的所有概率之和为1 。无论是简单命题还是复合命题，我们只需要确定在其中命题为真的那些原子事件，然后把它们的概率加起来就可获得任何命题的概率。例如，命题Cavity ∨ Toothache在 6 个原子事件中成立，所以可得

P(Cavity ∨ Toothache) = 0.108 + 0.012 + 0.072 + 0.008 + 0.165 + 0.064 = 0.28

一个特别常见的任务是将随机变量的某个子集或者某单个变量的分布抽取出来，也就是我们前面提到的边缘分布。例如，将所有Cavity取值为真的条目抽取出来在求和就得到了Cavity的无条件概率（也就是边缘概率）

P(Cavity) = 0.108 + 0.012 + 0.072 + 0.008 = 0.2

该过程称为边缘化（Marginalisation），或者称为“和出”（Summing Out）——因为除了Cavity以外的变量都被求和过程排除在外了。对于任何两个变量集合Y和Z，可以写出如下的通用边缘化规则（这其实就是前面给出的公式，我们只是做了简单的变量替换）

也就是说，Y的分布可以通过根据任何包含Y的联合概率分布对所有其它变量进行求和消元得到。根据乘法规则，这条规则的一个变形涉及条件概率而不是联合概率：

这条规则称为条件化。以后会发现，对于涉及概率表达式的所有种类的推导过程，边缘化和条件化具有非常强大的威力。

在大部分情况下，在给定关于某些其它变量的条件下，我们会对计算某些变量的条件概率产生感兴趣。条件概率可以如此找到：首先根据条件概率的定义式得到一个无条件概率的表达式，然后再根据全联合分布对表达式求值。例如，在给定牙疼的条件下，可以计算蛀牙的概率为

P(Cavity | Toothache) = P(Cavity ∧ Toothache) / P(Toothache)

=( 0.108 +0.012) / (0.108 + 0.012 + 0.016 + 0.064) = 0.6

为了验算，还可以计算已知牙疼的条件下，没有蛀牙的概率为

P(┐Cavity | Toothache) = P(┐Cavity ∧ Toothache) / P(Toothache)

=( 0.016 +0.064) / (0.108 + 0.012 + 0.016 + 0.064) = 0.4

注意这两次计算中的项 1/P(Toothache) 是保持不变的，与我们计算的Cavity的值无关。事实上，可以把它看成是P(Cavity I Toothache) 的一个归一化常数，保证其所包含的概率相加等于1，也就是忽略P(Toothache) 的值，这一点我们在朴素贝叶斯部分已经讲过。

此外，我们将用α来表示这样的常数。用这个符号我们可以把前面的两个公式合并写成一个：

P(Cavity | Toothache) =α P(Cavity, Toothache)

=α [P(Cavity, Toothache, Catch) + P(Cavity, Toothache, ┐Catch)]

=α [〈0.108, 0.016〉+〈0.012, 0.064〉] = α〈0.12, 0.08〉=〈0.6, 0.4〉

在很多概率的计算中，归一化都是一个非常有用的捷径。

从这个例于里可以抽取出一个通用推理过程。我们将只考虑查询仅涉及一个变量的情况。我们将需要使用一些符号表示：令X 为查询变量（前面例子中的Cavity）；令E 为证据变量集合（也就是给定的条件，即前面例子中的Toothache ）， e 表示其观察值；并令 Y 为其余的未观测变量（就是前面例于中的Catch）。查询为P(X I e)，可以对它求值：

其中的求和针对所有可能的y （也就是对未观测变量Y的值的所有可能组合）。注意变量 X, E 以及Y一起构成了域中所有布变量的完整集合，所以P(X, e, y)只不过是来自全联合分布概率的一个子集。算法对所有X和Y的值进行循环以枚举当 e 固定时所有的原子事件，然后根据全联合分布的概率表将它们的概率加起来，最后对结果进行归一化。

下面我们就用枚举法来解决本节开始时抛出的问题： P(E = T | J = T, M = T) = ?

P(E|j,m) = α P(E, j, m)

其中，我们用小写字母 j 和 m 来表示 J = T，以及M = T（也就是给定J和M）。但表达式的形式是P(E|j,m)而非P(e|j,m)，这是因为我们要将E = T 和 E = F这两个公式合并起来写成一个。同样，α 是标准化常数。然后就要针对其他未观测变量（也就是本题中的Burglary和Alarm）的值的所有可能组合进行求和，则有

根据图2中所示之贝叶斯网络，应该很容易可以写出下列关系式。

下面我们来循环枚举并加和消元。

在计算上还可以稍微做一点改进。因为P(E)对于ΣaΣb来说是一个常数，所以可以把它提出来。这样就避免了多次乘以P(E)所造成的低效。

上式中所有的值都可以基于CPT求得，算术当然是很繁杂的，我们这里不具体给出最终的结果。但一个显而易见的事实是当变量的数目变多时，全联合分布的表长增长是相当惊人的！所以我们非常希望能够有一种更轻巧的办法来替代这种枚举法，于是便有了下面将要介绍的消去法。

4.2 消去法

变量消去算法（Variable Elimination Algorithm）是一种基于动态规划思想设计的算法。而且在算法执行的过程中需要使用因子表来储存中间结果，当再次需要使用时无需重新计算而只需调用已知结果，这样就降低了算法执行的时间消耗。

Each factor is a matrix indexed by the values of its argument variable. 例如，与P(j|a)和P(m|a)相对应的因子fJ(A)和fM(A)只依赖于A，因为J和M在我们的问题里是已知的，因此fJ(A)和fM(A)都是两个元素的矩阵（也是向量）

在这种记法中括号里的参数表示的是变量，而下标仅仅是一种记号，所以你也可以使用f4(A)和f5(A)来代替fJ(A)和fM(A)。但我们这里使用J和M来作为下标的意图是考虑用P( _ | A)的 _ 来作为标记。所以P(a|b,E)可以写成fA(A, B, E)，注意因为A，B, E都是未知的，所以fA(A, B, E) 就是一个2×2×2的矩阵，即数据分析师培训