静态贝叶斯网络及其推理

离散动态贝叶斯网络推理与应用

---

0 引

$\qquad$本章内容主要围绕静态贝叶斯网络的基本概念及二种经典推理算法进行讲解。
本章的主要知识点：

• 贝叶斯网络三要素：节点及其取值、节点间的结构、条件概率表
• 贝叶斯网络的特性：条件独立性和其判定条件（有向分隔）
• $\bbox[5px,border:2px solid red]{\color{red}{贝叶斯网络的两种经典推理算法：消息传播算法和联接树算法}}$

其中红色框选部分为本人认为本章的重点、难点部分。

1贝叶斯网络基础

1.1概念

贝叶斯网络：信念网络（Belief Networks，BN）或因果网络（Causal Networks）
贝叶斯网络的定义：描述数据变量之间依赖关系的一种图形模型，也是一种用来进行推理的模型。
贝叶斯网络的作用：用于不确定环境建模和推理，提供了一种方便的框架结构来表示因果关系，使不确定性推理在逻辑上变得更为清晰、可理解性更强。

贝叶斯网络[1]的数学定义：
(1)存在一个变量集$V=\{X_i\}$,其中$i=1,2,\dots,n$，以及变量对应节点之间有向边的集合$E$。
(2)每个变量的取值既可以是离散的，也可以是连续的。
(3)由变量对应的节点和节点之间的有向边构成一个有向无环图$G=<V,E>$，其中$V$为节点集，与领域的随机变量一一对应，$E$为有向边集，反应节点变量之间的因果依赖关系。
(4)对每个节点$X_i$和它的父节点集合$Pa(X_i)$都对应一个条件概率分布表$P(X_i|Pa(X_i))$，且满足：

$$\bbox[5px,border:2px solid red]{P(X_1,X_2,\dots,X_n)=\prod_{i=1}^nP(X_i|Pa(X_i))\qquad (1)}$$
图论概念：
有向图(Directed Graphs)：图的所有边都有方向，其中父节点(Parent)指向子节点(Child)
根节点(Root Nodes)：没有父节点
叶节点(Child Nodes)：没有子节点
祖先节点(Ancestors)：包含其父节点及父节点祖先节点，根节点没有祖先节点
后代节点(Descendants)：包含其子节点及子节点后代节点，叶节点没有后代节点
非后代节点(Non-Descendants)：包含所有不是其后代节点的节点
有向环(Directed Cycle)：某节点是自己的祖先节点
有向无环图(Directed Acyclic Graph)：不含有向环的有向图

1.2三要素

1.2.1节点及其取值

$\qquad\bbox[5px,border:2px solid red]{\color{red}{贝叶斯网络的节点和随机变量是一一对应的}}$，根据随机变量的取值类型，可将贝叶斯网络分为：$\bbox[5px,border:2px solid red]{\color{red}{离散型}}$、连续型和混合型贝叶斯网络。

离散变量：
(a) 布尔变量(Boolean Variables)：真(1)、假(0)
(b) 顺序变量(Ordered Variables)：等级划分、取值分顺序(高、中、低)
(c) 整数变量(Integral Variables)：取值对应一定的范围(0 ~ 20)

1.2.2节点间结构

$\qquad$贝叶斯网络的图形结构定性表示了各变量之间的关系。

在贝叶斯网络中：
1、如果一个节点影响或导致另外一个节点发生时，它们可以直接连接
2、节点与父节点被称为一个家族(Family)，一个节点可以有多个父节点
3、所有节点的联合概率分布被分解为各个家族的条件概率之间的乘积

1.2.3条件概率表

$\qquad$贝叶斯网络的参数(条件概率表)定量描述了变量节点与父节点之间的依赖关系。

在贝叶斯网络中：
1、每个节点的条件概率表与其父节点集的实例相关联。
2、概率归一性，对于节点取值个数为$p$时，只要指定$p-1$个参数
3、根节点的参数为其先验概率

$\qquad$$\bbox[5px,border:2px solid red]{\color{red}{——贝叶斯网络分解了联合概率，压缩了概率表的规模}}$

2贝叶斯特性

$\qquad$$\bbox[5px,border:2px solid red]{\color{red}{贝叶斯网络能实现多变量联合概率分布的压缩性建模关键在于条件独立性假设}}$，而条件独立性假设蕴涵在有向无环图中。

2.1条件独立性假设

定理：随机变量A、B、C，若存在

$$P(A|B,C)=P(A|C)\qquad(2)\\ P(A,B|C)=P(A|B,C)P(B| C)=P(A|C)P(B|C)\qquad(3)\\$$
则，称A和B在给定C时条件独立，A和B的联合概率分布可以分解为A的边缘概率分布于B的边缘概率分布的乘积。
补充：
(a)贝叶斯公式：
$$P(B_i|A)=\frac{P(B_i)P(A|B_i)}{\sum_{j=1}^nP(B_j)P(A|B_j)}\qquad(4)$$
(b)条件概率公式及推广
$$P(AB)=P(A)P(B|A)\qquad (5)\\ P(A_1A_2\dots A_n)=P(A_1)P(A_2|A_1)P(A_3|A_1A_2)\dots P(A_n|A_1A_2\dots A_n)\qquad (6)$$

2.2有向分隔

$\qquad$原则上，利用概率论的基本公式可以验证多变量之间的条件独立性假设，但是过于耗时。
$\qquad\bbox[5px,border:2px solid red]{\color{red}{贝叶斯网络（有向无环图）的有向分隔特性，有效避免了复杂的概率运算而能得到多变量之间的条件独立性。}}$

$\qquad$考虑三变量A、B、C相连典型分类蕴涵的条件独立性：

证：顺连情况相似，证第一种
根据式(1)得

$$P(A,B,C)=P(A)P(C|A)P(B|C)$$
根据式(2)得 $$P(A,B|C)=\frac{P(A,B,C)}{P(C)}=\frac{P(A)P(C|A)P(B|C)}{P(C)}=P(A|C)P(B|C)$$
得证，$\color{red}{A和B在给定C时条件独立，信息通道阻塞}$。

证：
根据式(1)得

$$P(A,B,C)=P(C)P(A|C)P(B|C)$$
根据式(2)得 $$P(A,B|C)=\frac{P(A,B,C)}{P(C)}=P(A|C)P(B|C)$$
得证，$\color{red}{A和B在给定C时条件独立，信息通道阻塞}$。

证：
根据式(1)得

$$\sum_CP(A,B,C)=\sum_CP(A)P(B)P(C|A,B)$$
当$C$未知时 $$P(A,B)=P(A)P(B)$$
当$C$已知时 $$P(A,B|C)=\frac{P(A,B,C)}{P(C)}=\frac{P(A)P(B)P(C|A,B)}{P(C)}$$
得证，$\color{red}{A和B在未给定C时独立，信息通道阻塞}$。

结论：
给定一个节点集合$E$,设$\alpha$是节点$X$与$Y$之间的一条通路，$Z$是该通路上的一个节点，则通路$\alpha$被$E$阻塞($\color{red}{有向分隔}$)的充分条件是，满足其一：
(a)$Z$在$E$中，且$Z$与通路中的相邻节点构成顺连结构。(构造给定$C$)
(b)$Z$在$E$中，且$Z$与通路中的相邻节点构成分连结构。(构造给定$C$)
(c)$Z$为汇连节点，且$Z$和$Z$的后代均不在$E$中。(构造未给定$C$)
引[2]贝叶斯网络的马尔可夫性，若$E$有向分隔$X$和$Y$，那么$X$和$Y$在给定$E$时条件独立。
补充：
通路：在贝叶斯网络中，两个节点$X$和$Y$之间的一条通路是开始于$X$结束于$Y$的一个节点序列，其中节点各异且相邻两节点之间有边相连。

3贝叶斯网络推理基本类型

$\qquad$贝叶斯网络的推理是通过计算回答查询的过程，其主要推理问题包括以下三类：

• $\bbox[5px,border:2px solid red]{\color{red}{后验概率问题}}$：已知证据变量，计算其它变量的后验分布问题$P(Q|E=e)$
• 最大后验假设问题(Maximum a Posterior Hypothesis, MAP)：计算变量后验概率最大的状态组合
• 最大可能假设问题[3](Most Probable Explanation, MPE)：寻找概率最大的网络中全部变量和证据变量相一致的状态组合。

$\qquad$书上主要讨论的是后验概率问题，根据贝叶斯网络中蕴涵因果语义，其概率推理又可分为：

• 诊断推理(Diagnosis Inference):结果到原因的推理(已知子节点求父节点)
• 预测推理(Predictive Inference):原因到结果的推理(已知父节点求子节点)
• 原因关联推理(Intercausal Inference):更进一步，求造成同一结果的诸多原因(已知子节点求其多个父节点)
• 混合推理(Mixed Inference):包含上述类型

$\qquad\bbox[5px,border:2px solid red]{\color{red}{——概率推理复杂度低是贝叶斯网络的另一个特点。}}$

3.1确定性证据推理

3.1.1消息传播算法(Message Passing)

$\qquad$该算法因为避免复杂的图形变换，在处理较为简单的网络时有优势。该算法最早由Kim和Pearl针对单连通网络推理开发[4]。

补充：
信度(Belief)：节点的后验概率
信度更新(Belief Updating)：在给定一些节点证据时，更新其它节点的后验概率。
单连通网络(Singly-Connected Networks)：贝叶斯网络中，任意两个节点之间最多只有一条通路。
多连通网络(Multiply-Connected Networks)：……任意两节点间不只一条通路。

---

核心公式：
(a)信度更新

$$Bel(X)=\alpha \lambda(X)\pi(X)\qquad(6)$$
$$\lambda(X=x_i)= \begin{cases} 1,&e=x_i\\ 0,&e=x_j,j\neq x_i\\ \prod_j\lambda_{Y_j}(X),&e未知 \end{cases}\qquad (7)\\ \pi(X)=\sum_UP(X|U)\prod_i\pi_X(U_i)\qquad(8)$$
$\alpha$为归一化因子，保证$\sum_XBel(X)=1$。
(b)自底而上传播
利用节点$X$计算新的$\lambda$并输入到它的父节点，即
$$\lambda_X(U_i)=\alpha\sum_X\lambda(X)\sum_{U\backslash\{U_i\}}P(X|U)\prod_k\pi_X(U_k)\qquad(9)$$
(c)自顶而下传播
利用节点$X$计算新的$\pi$并传输到它的子节点，即
$$\pi_{Y_j}(X=x_i)= \begin{cases} 1,&e=x_i\\ 0,&e\neq x_i\\ \alpha\prod_{k\neq j}\lambda_{Y_k}(X)\sum_UP(X|U)\prod_i\pi_X(U_i)=\frac{\alpha Bel(X)}{\lambda_{Y_j}(X)},&e未知 \end{cases}\qquad(10)$$
补充：
1.消息传播算法推理目的在于通过计算$P(X|E)${$X$是查询节点，$E$是若干证据节点}来更新$X$的信度$Bel(X)$。
2.对$X$来说，网路中的证据分别来自父节点$U$的预测信息，以及来自子节点$Y$的诊断信息。
$\qquad$(a)认为$\pi$信息沿弧方向传递，记为$\pi_{接收者}(发出者)$，即$\pi_X(U_i)$。
$\qquad$(b)认为$\lambda$信息沿弧反方向传递，记为$\lambda_{发出者}(接收者)$，即$\lambda_{Y_j}(X)$。

消息传播过程及步骤：
1.初始化。
$\qquad$(a)在没有证据输入和消息传播之前，网络中所有节点$X$的自身消息参数$\lambda$、传递给父节点的$\lambda$消息、以及传递给子节点的$\pi$消息均初始化为1。
$\qquad$(b)对于根节点，初始化其自身参数$\pi$为其先验概率。
2.无证据输入下的消息传播（$\color{red}{考虑自顶而下传播}$）
$\qquad$(a)默认所有$\lambda$消息均为单位向量，无需考虑$\lambda$消息传播。
$\qquad$(b)求根节点信度。因已知根节点的$\pi$消息和$\lambda$消息，故可先求出其信度。
$\qquad$(c)求第一代子节点信度。根据公式(8)求第一代子节点的$\pi$消息，（$\color{red}{需要罗列父节点实例}$）由于$\lambda$信号为单位向量，则得第一代子节点信度。
$\qquad$(d)求第二代及后代子节点信度。根据公式(10)求子节点收到的$\pi_{Y_j}(X)$，再根据公式(8)求子节点$\pi$信息。
3.有证据输入下的消息传播（$\color{red}{考虑自底而上传播，仅考虑证据节点为最后一代子节点}$）
$\qquad$(a)对证据节点的$\lambda$参数进行设置，设$X$的证据为$x_i$，可设定$\lambda(X)=\{0，\dots，1,\dots，0\}$，即第$i$位为1。
$\qquad$(b)求第$n$代父节点的$\lambda$信息和信度。根据公式(9)求第一代父节点的$\lambda_{X}(U_i)$信息，结合公式(7)求其$\lambda$信息。此时，该父节点的$\pi$信息为步骤2无证据输入时的信度。（$\color{red}{需要罗列父节点实例}$）
$\qquad$(c)求第$n-1$代及其祖先父节点的$\lambda$信息和信度。（$\color{red}{需要罗列父节点实例}$）,需要利用公式(9)和公式(7)，如果遇到$\pi$信息传递还要用到公式(10)和公式(8)。

缺陷：

• 需要多次对某一节点的父节点所有实例进行求和计算，计算量呈指数关系。
• 距离证据节点越远，消息传播步骤越多，复杂度越高。

优点：

• 所有计算是局部的，适合并行分布式实现，在某种意义上是高效的。
• 避免了复杂的图形变换，针对简单网络有优势。

3.1.2联接树(Junction Tree)

$\qquad$由于工程实践中贝叶斯网络多数为多连通网络，消息传播算法将在该种网络的无向环中陷入无限循环，甚至失效。目前联接树算法(团树算法)为多连通网络广泛采用的精确推理算法。联接树算法[5]最早是Lauritzen和Spiegelhalter于1988年提出，不但可以解决单连通网络下的推理，也可以完成多连通网络下的推理计算。
$\qquad$联接树算法的基本思路：通过合并多连通网络节点，为网络构建一个等价的单连通网络，在所得到的单连通网络上进行消息传播，以实现多连通网络中的精确推理。

联接树算法基本流程：
1.构建贝叶斯网络结构对应端正图(Moral Graph)。将网络中拥有共同子节点但二者之间并未直接相连的节点进行连接，并除去所有边的方向。
2.将所得端正图三角化(Triangulate)。这里涉及寻找最优三角图的NP问题，多采用启发式方法构造三角图。启发式方法构造一个节点顺序，然后按节点顺序逐个进行处理进行三角化。
$\qquad$其中构造节点顺序可采用最大势搜索算法(Maximum Cardinality Search)。我们认为在一个无向图中每个包含3个以上节点的环中至少有一根弦，则该无向图可称为三角图。
3.创建联接树。
$\qquad$(a)创建簇(Cluster)。在三角图中识别所有极大团，对每个极大团所包含节点进行合并，作为一个新的节点。其中极大团中不包含无向图中的其他团(两两之间互相连接的一组节点)。
$\qquad$(b)候选分离集(Separator)。每对簇$X$和$Y$，候选分离集为$S_{XY}=\{X,Y\}$。在实际操作中，认为各个团之间的交集作为分离集。分离集选择的原则是： 1.优先选择最大质量的候选分离集(所含变量多)2.当质量相同时，优先选择最小代价候选分离集(两簇所有节点组合状态数之和)。
4.给联接树中的簇分配参数。
$\qquad$(a)初始设定簇和分离集(即节点集)节点所有状态组合对应的实数概率表每个元素均为1。
$\qquad$(b)确定委托变量。$\color{green}{为贝叶斯网络中每个变量指定一个包含该变量及其所有父节点的簇，将其条件概率表P(X|\pi(X))与为其指定簇的概率表相乘。}$
5.信度更新。在加入证据后，使用消息传播算法对联接树中的信度进行更新。
$\qquad$加入证据之后，生成证据向量。将该证据向量与为$X$指定的簇概率表相乘(结果为与证据$x_i$相一致的状态组合所对应的条目保持不变，其余为0)。再进行消息传播。

---

涉及核心公式：
(a)相邻簇通过分离集进行消息传播更新公式
设联接树簇$V$和簇$W$通过分离集$S$相连，对应概率表$\phi(V),\phi(W),\phi(S)$。消息自$V$传至$W$，对应$\phi(S),\phi(W)$更新公式：

$$\phi^*(S)=\sum_{V\backslash S}\phi(V)\qquad(11)\\ \phi^*(W)=\phi(W)\frac{\phi^*(S)}{\phi(S)}\qquad(12)$$
前者通过边缘化发送信息的簇概率表实现；后者将其旧表乘以分离集的新表除以分离集的旧表实现更新。
(b)联接树中的消息传播
$\qquad$确定查询节点$Q$,在联接树中任选包含$Q$的簇$C$,对$C$分别调用收集证据(Collect Evidence)子程序和分发证据(Distribute Evidence)子程序。另外防止重复传播，需把所有簇设置为未标记状态。
$$P(Q,e)=\sum_{C\backslash Q}\phi(C)\qquad(13)\\ P(Q|e)=\frac{P(Q,e)}{P(e)}\qquad(14)$$
完成消息传播之后，联接树中任意包含查询节点$Q$的簇$C$所存储的概率表需进行边缘化和归一化，便可得到查询节点的后验概率。
(c)联接树代价函数
$$\sum_{C_i\in\{C_1,C_2,\dots,C_n\}}(K_i\prod_{X\in C_i}|\Omega_X|)\qquad(15)$$
使用联接树算法进行概率推理对的代价主要由联接树中簇的状态空间大小决定。其中$K_i$为$C_i$涉及的分离集，亦$C_i$中包含父节点和子节点的数目；$\Omega_X$为$X$的状态数。
$\qquad$因此联接树的代价等于每个簇求出其所有委托节点及委托节点的父节点状态数进行求积，然后对所有簇的代价进行求和。

#CollectEvidence(C)
标记C；
if(C存在未标记的邻簇Ci)
    CollectEvidence(Ci)
    从C到调用该程序的簇传播消息
#DistributeEvidence(C)
标记C；
if(C存在未标记的邻簇Ci)
    从C到Ci传播消息
    DistributeEvidence(Ci)

3.2不确定证据推理

$\qquad$消息传播算法和联接树算法都是研究确定性证据(Specific Evidence)的推理，是对变量取特定值的明确描述。但是在现实中我们还会遇到其他类型的证据：

• 消极证据：获得的证据是对变量某些值的否定
• 不确定性证据(Uncertain Evidence)\软证据(Soft Evidence)：获得的证据信息是关于某一变量的概率分布

$\qquad$确定性证据推理与不确定性证据推理的区别在于：一旦确定性证据输入，无论将来其他节点收集到任何证据，该节点的信度都将保持不变；不确定证据希望结合其他证据来更新其自身信度。

3.2.1虚拟节点

$\qquad$通过添加虚拟节点，可以用似然比描述观测值中的不确定性。
注意：在仅考虑一个没有父节点且均匀先验的节点时可以简单地把不确定性映射为似然比。但是，在非均匀先验的条件下，似然比对于节点信度改变微乎其微。

涉及核心公式：
(a)赔率(Fair Odds)
在证据理论中，$h$的赔率指事件$h$为真的概率与$h$为假的概率之间的比值：

$$O(h)=\frac{P(h)}{P(1-h)}\qquad(16)$$
$\qquad\color{red}{赔率与概率是可以完全交换的概念}$。对赔率仍有贝叶斯公式：
$$O(h|e)=\frac{P(e|h)}{P(e|\neg h)}O(h)\qquad(17)$$

$\qquad$当情况特殊，同一个变量证据为一个集合、一个序列，或者多重不确定观测值。
解决思路为：对每个观测值建立一个虚拟节点。推理算法采用相同方法，向上传播每个虚拟节点的似然比组成的向量
注意：如果观测不独立，必须通过实际的节点显式描述它们之间的依赖关系。

消息传播算法中不确定证据的推理：
$\qquad$考虑把虚拟节点作为一个子节点与观测节点通过虚拟边相连接，这些边单向传播信息(虚拟->观测)。虚拟节点没有参数$\lambda$信息，但是可以向观测节点发送$\lambda$信息(即似然比向量)。
联接树算法中不确定证据的推理：
(a)对于确定性证据，即证据向量第$i$元素为1
(b)对于消极证据，即证据向量除第$j$元素都为1
(c)对于不确定性证据，即似然比向量为证据向量。
所有情况，证据向量都将被乘到为$X$所指定的簇的概率表上。

---

补：公式推导
(15)证，

$$O(h|e)=\frac{P(h|e)}{P(\neg h|e)}=\frac{P(e,h)}{P(e,\neg h)}=\frac{P(e|h)}{P(e|\neg h)}O(h)\qquad(17)$$

---