贝叶斯网络

在该部分对贝叶斯网络进行介绍，按照递进关系总结以下知识点：

• 条件独立性
• 条件参数化
• 朴素贝叶斯模型
• 贝叶斯网络

---

问题来源

首先探讨下为什么我们需要利用变量之间的条件独立性性质，假设我们要描述的对象为$n$个二值变量：$X_1,\dots,X_n$,这些变量的联合分布为$P$,那么我们需要$\bf{2^n - 1}$个参数来描述联合分布$P$，所需参数量是$O(2^n)$级别，我们便考虑能否利用变量之间的某种性质使得$P$可以用更少的参数来描述，由此便引出了变量之间的独立性性质。

独立性

下面给出一些独立性等价的定义:

• 若$P(X = x|Y = y) = P(X=x)$对于任意的$x,y$均成立 $\Rightarrow$ 变量$X$与$Y$相互独立
• 若$P(X,Y) = P(X|Y)P(Y) = P(X)P(Y)$ $\Rightarrow$ 变量$X$与$Y$相互独立

若问题来源中的$n$个变量相互独立，则联合分布:

$$P(X_1,X_2,\dots,X_n) = P(X_1) P(X_2) \dots P(X_n)$$

此时仅需$O(n)$个变量来对联合分布进行描述，参数花销大大减少，但在实际中，独立性是一个非常强的假设，往往不能够得到满足，由此便引出了条件独立性性质。

条件独立性

定义： 两个变量$X$和$Y$关于变量$Z$是条件独立的 $\Leftrightarrow$ 对于$\forall x,y,z$,$P(X = x|Y = y, Z = z) = P(X = x|Z = z)$ $\Leftrightarrow$ $P(X = x,Y = y|Z = z) = P(X = x|Z = z) \cdot P(Y=y|Z= z)$

这里需要特别说明的是条件独立性并不能推出独立性，独立性也并不能推出条件独立性，下面给出两个反例：

• 独立性 $\nRightarrow$ 条件独立性: 有两枚正反概率均为$50\%$的硬币,设事件A为第一枚硬币为正面，事件B为第二枚硬币为正面，事件C为两枚硬币同面，若不考虑事件C，事件A与事件B显然独立;但若事件C已经发生，则此时A与B便不再独立，即A与B关于C不条件独立。
• 条件独立性 $\nRightarrow$ 独立性: 有两枚硬币，一枚正面概率为$90\%$,另一枚反面概率为$90\%$,随机拿出一枚抛掷硬币两次, 事件A表示第一次为正面，事件B表示第二次为正面，事件C表示选择的是第一枚硬币，则抛开事件C，事件A与事件B并不独立($0.5 = P(B) \neq P(B|A) = 0.9802$),但若事件C发生，则相当于进行了两次独立重复实验，此时事件A与事件B独立。

条件独立性符号表示：

• $Ind(X;Y|Z)$ or $(X \perp Y|Z)$

条件参数化

在了解了变量条件独立性后，下面以一个例子分析如何利用变量之间的条件独立性性质来减少描述联合分布所需的参数。


图中大写字母均代表随机变量，含义如下：

• $D:$课程难度，$Val(D) = {d^0, d^1}$
• $I:$智力，$Val(I) = {i^0,i^1}$
• $S:$SAT分数，$Val(S) = {s^0,s^1}$
• $G:$课程成绩，$Val(G) = {g^0,g^1, g^2}$
• $L:$推荐信，$Val(L) = {l^0,l^1}$

假设$G$和$S$关于$I$条件独立，下面我们分析两种情况的条件参数化

首先以$I$和$S$两个变量为例，我们既可以通过联合分布$P(I,S)$来进行描述，也可以通过$P(I)$和$P(S|I)$进行描述，两种描述均是三个独立参数，如下图所示。

接下来分析$I、D、G$三个变量的条件参数化，其中$I$与$D$相互独立，下面分析两种表示方法所需的参数个数：

• 联合分布: $P(I,D,G)$,所需参数个数为$2 \times 2 \times 3 - 1=11$
• 利用独立性条件: $P(I,D,G) = P(I)P(D)P(G|I,D)$,所需独立参数为$1+1+2\times 2 \times (3-1) =10 $
  $\Rightarrow$ 利用独立性可以减少表示联合分布所需的参数个数

朴素贝叶斯模型

在这一部分对朴素贝叶斯模型做简要介绍，首先我们有两组变量：

• $C$:类别变量，$C = {c_1,\dots, c_k}$
• 观测变量：$X_1,X_2,\dots, X_d$

在朴素贝叶斯模型中，我们的目标便是利用观测变量来对类别进行预测/推理。所有这些变量其实可以看做一个联合概率分布$P(C,X_1,\dots,X_d)$,然而该概率分布很难计算，所需的参数量是指数级别，因此在朴素贝叶斯模型中有一个很强的假设：

观测变量彼此之间关于类别变量$C$是相互独立的，据此联合概率分布便很容易计算：

$$P(C,X_1,\dots,X_d) = P(X_1,\dots,X_d|C) P(C) = P(X_1|C)\dots P(X_d|C) P(C)$$

这是一个很强的假设，在真实世界中往往不能满足，同时因为没有充分利用变量之间的相关性性质，也造成了计算上的浪费。

贝叶斯网络

贝叶斯网路定义：贝叶斯网络，又称信念网络，是一种概率图模型，记做$(G,P)$,借由有向无环图表示一组随机变量及它们之间的条件概率分布。

贝叶斯网络是一种以有向无环图方式对独立性假设进行编码的手段，在贝叶斯网络中，任意变量与它的非后代变量对于其父节点变量是条件独立的：

$$(X_i \perp Nondesc(X_i)|Pa(X_i))$$

独立性映射(I-Maps): 记$P$为一组变量$\mathbf{X}$的联合概率分布，$I(P)$为表征$P$中独立性的集合

定义：$G$为贝叶斯网路，若$I(G) \subset I(P)$,则称$G$为$P$的一个独立映射

分解定理：若$G$是$P$的独立映射 $\Leftrightarrow$ $P(X1,\dots,X_d) = \prod \limits{i=1}^d P(X_i|Pa(X_i))$,通过该分解定理可以将全局的概率分布用局部的条件概率来表示

下面分析下与联合概率分布相比，贝叶斯网络所需参数,以$n$个二值变量为例：

• 联合概率分布：$2^n$
• 贝叶斯网络(限制各个节点入度为$k$):$n2^k$

d-Separation(有向分离)

在前面我们已经讨论了贝叶斯网络$G$编码了局部独立性假设，现在我们希望能够了解$G$是否还编码了其他独立性假设，因此我们需要一个方法来挖掘出$G$中所有的独立性假设
$\Rightarrow$ d-Separation
下面分别讨论不分离两种情况：

• 不分离
  • 两个节点直接相连：此时不存在一个节点使得这两个节点关于该节点条件独立
    $e.g. X \rightarrow Y$
  • 两个节点间接相连：head2tail,head2head,tail2tail
  • 一般情况：对于图$G$中的路径$X_1 \leftrightarrow \dots \leftrightarrow X_n$关于节点集合$E$是激活的如果
    • 对于每个V状结构$X{i-1} \rightarrow X_i \leftarrow X{i+1},X_i$或者其后代
      在集合$E$中
    • 路径上的点不在集合$E$中
• 分离：在贝叶斯网络$G$中，$X$和$Y$在给定$Z$条件下是d分离的$d-sep_G(X;Y|Z)$,如果不存在从集合$X$到$Y$的激活路径

由此可以通过d分离来找到贝叶斯网络中所有独立性关系：

$$I(G) = \{ (\mathbf{X \perp Y |Z}): d-sep_G(\mathbf{X;Y|Z})\}$$

简单总结而言，如果两个节点之间的路径被阻隔，则需要满足以下两个条件其一：

• 若存在V形结构，则冲撞点及其后代不能出现在条件集中
• 有路径中的点(非碰撞点)出现在条件集合中

Forward VS Backward

直观上感觉，贝叶斯网络的反向过程(给出结果，推理原因)要比前向过程困难不少，这是因为子节点会激活其父母之间的路径，而这种相关性会进一步向上传播。
最小独立映射：对于一个图$G$和一个分布$P$，我们在图中哪怕仅仅去掉一个边都会导致$G$不再是$P$的一个独立映射，则称$G$是最小独立映射。
最佳映射：对于一个图$G$和一个分布$P$，若有$I(P) = I(G)$，则称图$G$是$P$的一个最佳映射