概率图模型详解

B站讲解

概率图模型

考虑三个随机变量$a,b,c$，其联合概率分布为：

$$ P(a,b,c)=P(a)P(b\mid a)P(c\mid a,b) $$

将上述三个随机变量抽象成有向图中的3个结点
对于每个条件概率，在图中添加相应的链接（箭头），具体规则是：箭头的起点是条件概率中条件对应的结点，箭头的终点是条件概率中结论对应的结点，例如$P(b\mid a)$表示从$a$结点引出一条箭头指向$b$结点。特别地，对于概率$P(a)$，因为它不是条件概率，所以没有指向它的结点
如果存在一个结点$a$到结点$b$的箭头，则称结点$a$是结点$b$的父结点，结点$b$是结点$a$的子结点

实际上，$P(a,b,c)$的联合概率公式通过上述三条规则即可做出一个确定的有向图

概率图模型（Probabilistic Graphical Model）就是一类用图来表达随机变量之间关系的概率模型：

用一个结点表示一个或一组随机变量
结点之间的边表示变量间的概率关系

根据边的性质不同，概率图模型大致可以分为两类：

使用有向无环图表示随机变量间的依赖关系，称为贝叶斯网络，适用于随机变量间存在显示的因果关系
使用无向图表示随机变量间的相关关系，称为马尔可夫网络，适用于随机变量间有关系，但是难以显示表达

条件独立

考虑三个随机变量$a,b,c$，并且假设给定$b,c$的条件下$a$的条件概率分布不依赖于$b$的值，即

$$ P(a\mid b,c)=P(a\mid c) $$

用记号

$$ a \perp b\mid c $$

表示给定$c$的条件下（或者说$c$被观测到的情况下）$a,b$条件独立，实际上条件独立可以扩充到集合范围，即给定集合$X$的条件下，$Y,Z$条件独立。在使用概率模型时，条件独立起着重要的作用，它简化了模型的结构，降低了模型训练和推断的计算量

贝叶斯网络

贝叶斯网络结构$\mathcal{G}$是一个有向无环图，其中每个结点对应于一个随机变量。若两个随机变量之间有直接依赖关系，则将它们用一条带箭头的边相连。贝叶斯网络结构有效地表达了特征间的条件独立性，它假设每个结点仅与它的直接父结点有关，而与其它结点独立。但是通常情况下，每个结点的父结点不止一个，所以我们将结点$X_i$的父结点集合记作$P_{X_i}$

实际上，上面加粗部分规范化的说法是：贝叶斯网络假设每个特征与它的非后裔结点表达的特征是相互独立的。但是由于这种说法实在不好理解，故我对其进行了一些修改

贝叶斯网络中三个结点之间的典型依赖关系如下图：

同父结构

实际上，按照正常的联合概率公式，则有

$$ P(X_1,X_2,X_3)=P(X_1)P(X_2\mid X_1)P(X_3\mid X_1, X_2) $$

按照贝叶斯假设，则有

$$ P(X_1,X_2,X_3)=P(X_1)P(X_2\mid X_1)P(X_3\mid X_1) $$

综合上述两式，消掉相同的部分得${\color{red} {P(X_3\mid X_1,X_2)=P(X_3\mid X_1)}}$

结论：$X_1$被观测的情况下，$X_2$和$X_3$独立；$X_1$未被观测的情况下，$X_2$和$X_3$不独立。即$X_2\perp X_3\mid X_1$

顺序结构

实际上，按照正常的联合概率公式，则有

$$ P(X_1,X_2,X_3)=P(X_3)P(X_1\mid X_3)P(X_2\mid X_1, X_3) $$

按照贝叶斯假设，则有

$$ P(X_1,X_2,X_3)=P(X_3)P(X_1\mid X_3)P(X_2\mid X_1) $$

综合上述两式，消掉相同的部分得${\color{red} {P(X_2\mid X_1,X_3)=P(X_2\mid X_1)}}$

结论：$X_1$被观测的情况下，$X_2$和$X_3$独立；$X_1$未被观测的情况下，$X_2$和$X_3$不独立。即$X_2\perp X_3\mid X_1$

V型结构

实际上，按照正常的联合概率公式，则有

$$ P(X_1,X_2,X_3) = P(X_2)P(X_3\mid X_2)P(X_1\mid X_2,X_3) $$

按照贝叶斯假设，则有

$$ P(X_1,X_2,X_3)=P(X_2)P(X_3)P(X_1\mid X_2,X_3) $$

综合上述两式，消掉相同的部分得${\color{red} {P(X_3\mid X_2)=P(X_3)}}\Rightarrow {\color{red} {P(X_2,X_3)=P(X_2)P(X_3)}}$

结论：$X_1$被观测的情况下，$X_2$和$X_3$不独立；$X_1$未被观测的情况下，$X_2$和$X_3$独立。即$X_2 \not \perp X_3\mid X_1$。可以用一个比较通俗的例子来解释，$X_2$和$X_3$理解为一男一女，当这两个人没有孩子$X_1$时，$X_2$和$X_3$是独立的；当它们有了孩子$X_1$之后，$X_2$和$X_3$就不独立了
特别地，如果$X_1$有子结点$X_4$，且$X_4$被观测的情况下，无论$X_1$是什么状态，$X_2$和$X_3$也是不独立的

D-划分

为了判断贝叶斯网络中任意两个结点是否独立，我们需要用到D-划分。D-划分其实是贝叶斯网络三种基本拓扑结构的推广，将结点关系推广到集合关系

我们先总结简单的结点关系，之后再推广到集合

设有结点$a,b$，若在$a$和$b$之间存在路径结点集合$V=\{v_1,v_2,...,v_n\}$，若该结点集合中的所有结点$v_i$满足：

$v_i$被观测，且$v_i$拓扑结构为同父结构或顺序结构
$v_i$未被观测，且$v_i$拓扑结构为V型结构

则称$a,b$独立

注：$a$到$b$某一条路径上的结点$v_i$实际上不止一个，但只要有一个满足上面的任意一个条件，就认为该路径被阻断。并且$a$到$b$的路径也可能不止一条（忽略箭头方向），只有当所有的路径都被阻断，才认为$a$和$b$被阻断

推广到集合：若有结点集合$A,B$，若在集合$A$中的任意结点到$B$中的任意结点，都满足上述条件，则称集合$A,B$独立

如下图所示，在给定$X_2$和$X_3$的情况下，$X_1$和$X_6$是独立的，即$X_1\perp X_6\mid (X_2, X_3)$。具体来说，从$X_1$到$X_6$有两条路径：

$X_1\to X_2\to X_6$，其中$X_2$被观测到，且$X_2$是顺序结构，因此该条路径被阻断
$X_1\to X_3\to X_6$，其中$X_3$被观测到，且$X_3$是顺序结构，因此该条路径被阻断

如下图所示，在给定$X_1$和$X_6$的情况下，$X_2$和$X_3$不是独立的，即$X_2\not \perp X_3\mid (X_1,X_6)$。具体来说，从$X_2$到$X_3$有两条路径：

$X_2\to X_6\to X_5\to X_3$，其中$X_6$被观测到，且$X_6$是V型结构，因此该条路径未被阻断
$X_2\to X_1\to X_3$，其中$X_1$被观测到，且$X_1$是同父结构，因此该条路径被阻断

只有当所有的路径都被阻断，$X_2$和$X_3$才是独立的，因此$X_2$和$X_3$不是独立的

在理解了D-划分之后，我们可以对原本复杂的概率公式进行化简，如下：

$$ P(B,C,T,A,L)=P(C)P(A\mid C)P(B\mid A,C)P(T\mid A,B,C)P(L\mid C,A,B,T) $$

用D-划分化简：

对于$P(A\mid C)$，由于$T$是V型结构，且未被观测，所以$A$和$C$独立，故$P(A\mid C)=P(A)$
对于$P(B\mid A,C)$，与1同理，所以$B$和$A$独立，故$P(B\mid A,C)=P(B\mid C)$
对于$P(T\mid A,B,C)$，由于$C$是同父结构，且已被观测（因为式子中有$P(C)$），所以$B$和$T$独立，故$P(T\mid A,B,C)=P(T\mid A,C)$
对于$P(L\mid C,A,B,T)$，由于$A$是同父结构，且已被观测（因为式子中有$P(A)$），所以$L$与除了$A$以外的所有结点都独立，故$P(L\mid A)$

因此计算公式简化为

$$ P(B,C,T,A,L)=P(C)P(A)P(B\mid C)P(T\mid A,C)P(L\mid A) $$

*道德图

阅读这一部分可以帮助你更好的理解D-划分。为了分析有向图中结点之间的条件独立性，我们会使用D-划分，这个技术本身没有什么问题，但实在是不太适合人力去做，因此我们考虑将一个有向图转为无向图，图中各边相连就代表了它们之间的关系，具体步骤如下：

找出有向图中的所有V型结构，在其两个父结点之间加上一条无向边
将所有的有向边改为无向边

这样产生的无向图称为道德图（Moral Graph），父结点相连的过程称为道德化。基于道德图能直观，迅速的找到结点之间的条件独立性。如下图所示：

道德图判断独立性的方法：设道德图中有变量$x,y$和被观测变量集合$\mathbb{Z}=\{z_i\}$，若变量$x$和$y$能在图上被$\mathbb{Z}$分开，即从道德图中将变量集合$\mathbb{Z}$去除后，$x$和$y$属于两个连通分量，则$x\perp y\mid \mathbb{Z}$成立

需要注意的是，用道德图判断出来的条件独立性在原有向图中一定是成立的，但反之则不然，有向图中的一些条件独立性不一定能从道德图中判断出来

推断

在图模型中，推断（Inference）是指在观测到部分变量$\mathbb{E}=\{e_1,e_2,...,e_m\}$时，计算其它某些变量$\mathbb{Q}=\{q_1,q_2,...,q_n\}$的后验概率$P(\mathbb{E}\mid \mathbb{Q})$。概率图模型的推断方法可以分为两大类：

精确推断，具体可以分为变量消去和信念传播两种方法，但由于复杂度太高，因此适用范围有限
近似推断，本文不作介绍，有兴趣可以看这篇文章

变量消去（Variable elimination）

变量消除算法是在求解某个随机变量的边缘分布时，通过消去其他变量的方式来获取（对联合概率进行其他变量的求和，再基于条件独立性转化为相关变量的条件概率的连乘）

实际上如果学过概率论的同学应该有印象，对于离散型随机变量，边缘概率就是求和；对于连续型随机变量，边缘概率通过积分求解。下图是一个例子，随机变量$a=\{1,1,2,3\},b=\{1,2\},c=\{1,2\}$，先通过求和消掉随机变量变量$b$，再消掉随机变量$c$，最终得到$a$的边缘概率（因为小数点精度不够，所以求和不是1，不要在意这些细节）

以下图为例，详细讲解变量消去的工作流程。假设推断目标是计算边缘概率$P(X_5)$

为了计算$P(X_5)$，只需要通过加法消去变量$X_1,X_2,X_3,X_4$即可

$$ P(X_5)=\sum_{X_1}\sum_{X_2}\sum_{X_3}\sum_{X_4}P(X_1,X_2,X_3,X_4,X_5) $$

根据贝叶斯网络的结构，结合D-划分算法可将联合概率$P(X_1,X_2,X_3,X_4,X_5)$化简为

$$ P(X_1,X_2,X_3,X_4,X_5)=P(X_1)P(X_2\mid X_1)P(X_3\mid X_2)P(X_4\mid X_3)P(X_5\mid X_3) $$

带入上式，重新排列$\sum$的位置，则有

$$ P(X_5)=\sum_{X_1}P(X_1)P(X_2\mid X_1)\sum_{X_2}P(X_3\mid X_2)\sum_{X_4}P(X_4\mid X_3)\sum_{X_3}P(X_5\mid X_3) $$

定义

$$ \begin{aligned} m_{1,2}(X_2)&=\sum_{X_1}P(X_1)P(X_2\mid X_1)\\ m_{2,3}(X_3)&=\sum_{X_2}P(X_3\mid X_2)m_{1,2}(X_2)\\ m_{4,3}(X_3)&=\sum_{X_4}P(X_4\mid X_3)\\ m_{3,5}(X_5)&=\sum_{X_3}P(X_5\mid X_3)m_{2,3}(X_3)m_{4,3}(X_3) \end{aligned} $$

其中，$m_{1,2}(X_2)$仅是$X_2$的函数；$m_{2,3}(X_3),m_{4,3}(X_3)$仅是$X_3$的函数；$m_{3,5}(X_5)$仅是$X_5$的函数

于是有

$$ \begin{aligned} P(X_{5})&=\sum_{X_{3}} P(X_{5} \mid X_{3}) \sum_{X_{4}} P(X_{4} \mid X_{3}) \sum_{X_{2}} P(X_{3} \mid X_{2}) \sum_{X_{1}} P(X_{1}) P(X_{2} \mid X_{1}) \\ &=\sum_{X_{3}} P(X_{5} \mid X_{3}) \sum_{X_{4}} P(X_{4} \mid X_{3}) \sum_{X_{2}} P(X_{3} \mid X_{2}) m_{1,2}(X_{2}) \\ &=\sum_{X_{3}} P(X_{5} \mid X_{3}) \sum_{X_{4}} P(X_{4} \mid X_{3}) m_{2,3}(X_{3}) \\ &=\sum_{X_{3}} P(X_{5} \mid X_{3}) m_{2,3}(X_{3}) \sum_{X_{4}} P(X_{4} \mid X_{3}) \\ &=\sum_{X_{3}} P(X_{5} \mid X_{3}) m_{2,3}(X_{3}) m_{4,3}(X_{3}) \\ &=m_{3,5}(X_{5}) \end{aligned} $$

实际上，$m_{4,3}(X_3)=\sum_{X_{4}}P(X_4\mid X_3)=1$，因此$P(X_5)=\sum_{X_3}P(X_5\mid X_3)m_{2,3}(X_3)$

总结：变量消去法通过利用乘法对加法的分配律，将多个变量的积的求和转化为对部分变量交替进行求和与积的问题

信念传播（Belief propagation）

信念传播算法将变量消去法中的求和操作看作一个消息传递过程，解决了求解多个边际分布时的重复计算问题

形式化地，假设函数$m_{i,j}(X_i)$表示随机变量概率求和的一部分中间结果，例如$\sum_{X_1}P(X_1)P(X_2 \mid X_1)$可以表示为$m_{1,2}(x_2)$。那么信念传播算法的求和操作可以通过下述公式表示：

$$ m_{i,j}(X_j) = \sum_{X_i}\psi(X_i, X_j)\prod_{k \in {n(i) ,k\neq j}}m_{k,i}(X_i) $$

在上述式子中，$\psi(X_i, X_j)$表示一个变量$X_i$和$X_j$的关联性的函数，可以是条件概率或者联合概率分布等；$n(i)$表示概率图中与$X_i$相邻的结点变量集合。在信念传播算法中，每次消息传递操作仅与$X_i$及其邻接结点直接相关，消息传递的计算被限制在图的局部进行

注意，在信念传播中，此时函数$m_{ij}(X_j)$可以表示为结点$X_i$向$X_j$传递的一个消息

在信念传播算法中：

一个结点只有在接收来自其他所有结点的消息后才能向另一个结点发送消息
其结点的边缘概率正比于其接收的消息的乘积：$P(X_i)\propto \prod_{k\in n(i)}m_{k,i}(X_i)$

如果图结构中没有环，则信念传播算法经过两个步骤即可完成所有消息传递，进而计算所有变量上的边际分布：

指定一个根节点，从所有叶结点开始向根节点传递消息，直到根节点收到所有邻接结点的消息。
从根节点开始向叶结点传递消息，直到所有叶结点均收到消息

概率图模型详解

December 13, 2020 • Read: 8062 • 数据挖掘与机器学习 • 阅读设置