本篇博文主要总结贝叶斯网络相关知识。

复习之前的知识点

相对熵

相对熵，又称互熵，交叉熵，鉴别信息，$Kullback$ 熵，$Kullback-Leible$ 散度等 。

设$p(x)、q(x)$ 是$X$ 中取值的两个概率分布，则$p$ 对$q$ 的相对熵是 :
$$D(p||q)=\sum _{x}p(x)log\frac{p(x)}{q(x)}=E_{p(x)}log\frac{p(x)}{q(x)}$$

• 相对熵可以度量两个随机变量的“距离”。
• 一般的，$D(p||q)\ne D(q||p)$。
• $D(p||q)\ge 0，D(q||p)\ge 0$。

互信息

两个随机变量$X，Y$ 的***互信息***，定义为$X，Y$ 的***联合分布和独立分布乘积的相对熵***。
$$I(X,Y)=D(P(X,Y)||P(x)P(Y)$$
$$I(X,Y)=\sum _{x,y}P(x,y)log\frac{P(x,y)}{p(x)p(y)}$$

• 显然当$X,Y$ 互相独立时，$P(X,Y)=P(X)P(Y)$ 这个时候，$X,Y$距离最短，互信息为零。

信息增益

信息增益表示得知特征$A$ 的信息而使得类$X$ 的信息的不确定性减少的程度。

定义：特征$A$ 对训练数据集$D$ 的信息增益 $g(D,A)$，定义为集合$D$ 的经验熵$H(D)$ 与特征 $A$ 给定条件下$D$ 的经验条件熵$H(D|A)$ 之差， 即：
$$g(D,A)=H(D)-H(D|A)$$

对于两个随机变量$X,Y$，关于熵和互信息的一些总结公式：

• $H(Y|X)=H(X,Y)-H(X)$
• $H(Y|X)=H(Y)-I(X,Y)$
• $H(Y|X)<H(Y)$
• $H(X|Y)<H(X)$
• $I(X,Y)=H(X)+H(Y)-H(X,Y)$

显然，这即为训练数据集$D$ 和特征$A$ 的互信息。

贝叶斯公式和最大后验估计

贝叶斯估计是一种生成式模型。所谓生成式和判别式模型的区别在于：

• 通过$P(y|x)$ 直接得出的模型称为判别式模型。
• $P(y|x)$ 是由$P(x|y)$ 得出的模型叫做生成式模型，也就是在类别已知的情况下，样本是怎么生成出来的。

$$P(A|D)=\frac{P(D|A)}{p(D)}$$

给定某些样本$D$ ，在这些样本中计算某结论$A1、A2\dots \dots An$ 出现的概率，即$P(Ai|D)$。

• 第一个等式：贝叶斯公式；
• 第二个等式：样本给定，则对于任何$Ai,P(D)$ 是常数，即分母仅为归一化因子
• 第三个箭头：若这些结论$A1、A2\dots \dots An$ 的先验概率相等 (或近似)，***即$P(A_1)=P(A_2)=...P(A_n)$***， 则得到最后一个等式：即第二行的公式，这时候其实是转成了求最大似然估计。

朴素贝叶斯

朴素贝叶斯的假设

一个特征出现的概率，与其他特征(条件)独立 (特征独立性)

• 其实是：对于给定分类的条件下，特征独立

每个特征***同等重要***(特征均衡性)

朴素贝叶斯的推导

朴素贝叶斯(Naive Bayes，NB)是基于“特征之间是独立的”这一朴素假设，应用贝叶斯定理的***监督学习*** 算法。

对于给定的特征向量$X_1,X_2,...,X_n$

类别$y$ 的概率可以根据贝叶斯公式得到：

使用朴素的***独立性*** 假设：
$$P(x_i|y,x_1,...,x_{i-1},x_{i+1},...,x_n)=P(x_i|y)$$

类别$y$ 的概率可简化为：
$$P(y|x_1,x_2,..,x_n)=\frac{P(y)P(x_1,x_2,...,x_n|y)}{p(x_1,x_2,...,x_n)}=\frac{P(y){\prod }_{i=1}^{n}P(x_i|y)}{p(x_1,x_2,...,x_n)}$$

在给定样本的前提下， $p(x_1,x_2,...,x_n)$ 是常数：
$$P(y|x_1,x_2,...,x_n)\propto P(y)\prod _{i=1}^{n}P(x_i|y)$$

从而：
$$\hat{y}=argmaxP(y)\prod _{i=1}^{n}P(x_i|y)$$

以上就是朴素贝叶斯通用化的推导，所有的朴素贝叶斯都可以这样推导出来。

根据样本使用$MAP(MaximumAPosteriori)$ 估计$P(y)$，建立合理的模型估计$P(x_i|y)$，从而得到样本的类别。$$\hat{y}=argmaxP(y)\prod _{i=1}^{n}P(x_i|y)$$

高斯朴素贝叶斯

根据样本使用$MAP(MaximumAPosteriori)$ 估计$P(y)$，建立合理的模型估计 $P(x_i|y)$，从而得到样本的类别。$$\hat{y}=argmaxP(y)\prod _{i=1}^{n}P(x_i|y)$$

假设特征服从高斯分布，即：

参数使用$MLE$ （最大似然估计）估计即可。

多项分布朴素贝叶斯

假设特征服从多项分布，从而，对于每个类别y， 参数为 ${\theta }_y=({\theta }_{y1},{\theta }_{y2},{\theta }_{y2},...,{\theta }_{yn})$，其中$n$ 为特征的数目，$P(x_i|y)$ 的概率为 $,{\theta }_{yi}$。

参数${\theta }_{yi}$ 使用$MLE$ 估计的结果为：

假定训练集为$T$，有:

其中：

• $\alpha =1$ 称为$Laplace$ 平滑。
• $\alpha <1$ 称为$Lidstone$ 平滑。
• 平滑操作除了避免出现零，还有增加模型的泛化能力的作用。

以文本分类为例

问题描述

• 样本：$1000$ 封邮件，每个邮件被标记为垃圾邮件或者非垃圾邮件 。
• 分类目标：给定第$1001$ 封邮件，确定它是垃圾邮件还是非垃圾邮件。
• 方法：朴素贝叶斯

问题分析

类别$c$ ：垃圾邮件$c1$，非垃圾邮件$c2$。
词汇表，两种建立方法：

• 使用现成的单词词典；
• 将所有邮件中出现的单词都统计出来，得到词典。

记单词数目为$N$ 。

将每个邮件$m$ 映射成维度为$N$ 的向量$x$。

若单词$wi$ 在邮件$m$ 中出现过，则$xi=1$，否则，$xi=0$。即邮件的向量化：$m=(x1,x2\dots \dots xN)$

贝叶斯公式：$P(c|x)=P(x|c)\ast P(c)/P(x)$ ，注意这里$x$ 是向量。

特征条件独立假设 ：$P(x|c)=P(x1,x2\dots xN|c)=P(x1|c)\ast P(x2|c)\dots P(xN|c)$

特征独立假设：$P(x)=P(x1,x2\dots xN)=P(x1)\ast P(x2)\dots P(xN)$

带入公式： $$P(c|x)=P(x|c)\ast P(c)/P(x)$$
实际情况下，不需要考虑$P(x)$，故只剩下***特征条件独立假设***。

等式右侧各项的含义：

• $P(xi|cj)$：在$cj$ (此题目，$cj$ 要么为垃圾邮件1，要么为非垃圾邮件2)的前提下，第$i$ 个单词$xi$出现的概率 。
• $P(xi)$ ：在所有样本中，单词$xi$ 出现的概率。
• $P(cj)$ ：在所有样本中，邮件类别$cj$ 出现的概率。

由上面例子可以看出，朴素贝叶斯基于以下两条假设：

• 一个特征出现的概率，与其他特征(条件)独立(特征独立性)，即是：对于给定分类的条件下，特征独立 。
• 每个特征同等重要(特征均衡性) 。

以上两条假设不一定正确，但是基于这两条假设的朴素贝叶斯在一些应用中效果却是不错的。

贝叶斯网络

把某个研究系统中涉及的随机变量，根据是否***条件独立*** 绘制在一个***有向图*** 中，就形成了贝叶斯网络。

贝叶斯网络($BayesianNetwork$)，又称有向无环图模型$(directedacyclicgraphicalmodel,DAG)$，是一种概率图模型，根据概率图的拓扑结构，考察一组随机变量$X1,X2...Xn$ 及其$n$ 组条件概率分布
$(ConditionalProbabilityDistributions,CPD)$ 的性质。

一般而言，贝叶斯网络的有向无环图中的节点表示随机变量，它们可以是可观察到的变量，或隐变量、未知参数等。连接两个节点的箭头代表此两个随机变量是具有***因果关系(或非条件独立***)。若两个节点间以一 个单箭头连接在一起，表示其中一个节点是“因$(parents)$”，另一个是“果$(children)$”，两节点就会产生一个条件概率值。

每个结点在给定其直接前驱时，条件独立 于其非后继。

一个简单的贝叶斯网络

$P(a,b,c)=P(c|a,b)P(b|a)P(a)$，其对应的无向图如下：


$P(x_1,x_2,x_3,x_4|y)=P(x_1|y)\ast P(x_2|y)\ast P(x_3|y)\ast P(x_4|y)$，其对应的无向图如下：

朴素贝叶斯就是把特征$(x1,x2,x3,x4)$之间的有向边都删掉了。

全连接贝叶斯网络

每一对结点之间都有边连接：

一个“正常”的贝叶斯网络：

• 有些边缺失

• 直观上：
  $x1$ 和$x2$ 独立
  $x6$ 和$x7$ 在$x4$ 给定的条件下独立

• $x1,x2,\dots x7$ 的联合分布：

对一个实际贝叶斯网络的分析：

贝叶斯网络的形式化定义

$BN(G,\Theta )$

• G:有向无环图
• G的结点：随机变量
• G的边：结点间的***有向依赖***
• Θ：所有条件概率分布的参数集合
• 结点$X$ 的条件概率：$P(X|parent(X))$
  

通过贝叶斯网络判定条件独立—1

根据图模型，得：$P(a,b,c)=P(c)\ast P(a|c)\ast P(b|c)$
从而： $P(a,b,c)/P(c)=P(a|c)\ast P(b|c)$
因为 $P(a,b|c)=P(a,b,c)/P(c)$
得：$P(a,b|c)=P(a|c)\ast P(b|c)$

即：在$c$ 给定的条件下， $a，b$ 被阻断$(blocked)$ 是独立的。

通过贝叶斯网络判定条件独立—2

$P(a,b,c)=P(a)\ast P(c|a)\ast P(b|c)$

即：在$c$ 给定的条件下，$a，b$ 被阻断(blocked)，是独立的。

通过贝叶斯网络判定条件独立—3

在$c$ 未知的条件下，$a，b$ 被阻断(blocked)，是独立的： head-to-head

以上三种情况的举例说明：