概率图模型详解
概率图模型
考虑三个随机变量a,b,c，其联合概率分布为：
- 将上述三个随机变量抽象成有向图中的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的值，即
用记号
表示给定c的条件下（或者说c被观测到的情况下）a,b条件独立，实际上条件独立可以扩充到集合范围，即给定集合X的条件下，Y,Z条件独立。在使用概率模型时，条件独立起着重要的作用，它简化了模型的结构，降低了模型训练和推断的计算量
贝叶斯网络
贝叶斯网络结构\mathcal{G}是一个有向无环图，其中每个结点对应于一个随机变量。若两个随机变量之间有直接依赖关系，则将它们用一条带箭头的边相连。贝叶斯网络结构有效地表达了特征间的条件独立性，它假设每个结点仅与它的直接父结点有关，而与其它结点独立。但是通常情况下，每个结点的父结点不止一个，所以我们将结点X_i的父结点集合记作P_{X_i}
实际上，上面加粗部分规范化的说法是：贝叶斯网络假设每个特征与它的非后裔结点表达的特征是相互独立的。但是由于这种说法实在不好理解，故我对其进行了一些修改
贝叶斯网络中三个结点之间的典型依赖关系如下图：
同父结构
实际上，按照正常的联合概率公式，则有
按照贝叶斯假设，则有
综合上述两式，消掉相同的部分得{\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
顺序结构
实际上，按照正常的联合概率公式，则有
按照贝叶斯假设，则有
综合上述两式，消掉相同的部分得{\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型结构
实际上，按照正常的联合概率公式，则有
按照贝叶斯假设，则有
综合上述两式，消掉相同的部分得{\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-划分之后，我们可以对原本复杂的概率公式进行化简，如下：
用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)
因此计算公式简化为
*道德图
阅读这一部分可以帮助你更好的理解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即可
根据贝叶斯网络的结构，结合D-划分算法可将联合概率P(X_1,X_2,X_3,X_4,X_5)化简为
带入上式，重新排列\sum的位置，则有
定义
$$ \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)。那么信念传播算法的求和操作可以通过下述公式表示：
在上述式子中，\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)
如果图结构中没有环，则信念传播算法经过两个步骤即可完成所有消息传递，进而计算所有变量上的边际分布：
- 指定一个根节点，从所有叶结点开始向根节点传递消息，直到根节点收到所有邻接结点的消息。
- 从根节点开始向叶结点传递消息，直到所有叶结点均收到消息
*通俗的讲解Belief Propagation算法的思想
情景一：若干士兵排成一个队列，每个士兵只能与他相邻的士兵交流，问如何才能使每个士兵都知道总的士兵数？
显然，对里面的任意一位士兵，他们只能与相邻的人交流传递信息。比如最左边的第一位向第二位传递："第二位左边只有1个人"。第二位向第三位传递："第三位左边有2个"。一直依次传递到最右边最后一位，最后一位获得的信息是他的左边有5个人
但是这个时候只有最右边那个人知道总人数（5+1=6），还不能使其他人知道总人数。其他人只知道他的左边有多少人，右边有多少并不知道
接下来再依次从右往左传递消息。比如最右边第一位告诉最右边的第二位："第二位的右边只有他1个"......正向和反向各传递一遍之后，每个人都拥有两个消息，一个是该士兵的左边有L个人，一个是右边有R个人，最终每个人都可以知道总人数（L+R+1）
但是这样效率并不高，怎么快一点呢？我们可以同时两边各向相反的方向传递消息，因为这并不影响工作流程
情景二：若干士兵站好相应位置，有些士兵不止有2个相邻的士兵，可能有3个或更多。每个士兵只能与他相邻的士兵交流，问如何才能使每个士兵都知道总的士兵数？
上图就已经和BP算法联系起来了。传播的结果是使得每个节点都可以获得其他节点传来的消息，从而计算出边缘函数
情景三：若干士兵排成环路，每个士兵只能与他相邻的士兵交流，问如何才能使每个士兵都知道总的士兵数？
由于有环路的存在，如果用上述信息更新方法来确定总人数，将会导致无法确定何时中止信息的传递，因此也就无法确定士兵人数