好哒,这一节聊一下什么是马尔科夫随机场/概率无向图模型,顾名思义,就是用无向图表达的随机变量的联合概率分布,比如如下的一个图,就是包含了4个随机变量的概率无向图,它描述了随机变量与随机变量之间的关系:
avatar

一.概率计算

一看这图首先会想到如何计算它的联合概率分布?先说求解方式:它的联合概率分布表示为其最大团上的随机变量的函数的乘积。这里有两点不好理解,什么是最大团?随机变量的函数又是什么? 下面对其做介绍,

团与最大团

无向图中任何两个节点均有边连接的节点子集构成一个团,若这个团不能再加入任何一个其他的图中节点,则称为最大团。

所以上面的无向图中:

(1)团有7个:{X1,X2},{X1,X3},{X2,X3},{X2,X4},{X3,X4},{X1,X2,X3},{X2,X3,X4}

(2)最大团有两个:{X1,X2,X3},{X2,X3,X4}

注意:{X1,X2,X3,X4}不构成最大团,因为X1与X4之间没有连接

随机变量的函数:势函数

关于随机变量的函数,称为势函数,通常写作:

$$ \psi_C(X_C) $$


这里,$X_C$即表示一个最大团,而且要求$\psi_C(X_C)>0$,通常会定义为一个指数函数

联合概率计算:Hammersley-Clifford定理

所以,其联合概率分布$P(X)$的可以表示为如下形式:

$$ P(X)=\frac{1}{Z}\prod_C\psi_C(X_C)\\ Z=\sum_X\prod_C\psi_C(X_C) $$

这里,$C$是无向图的最大团,$X_C$是其对应的随机变量,$\psi_C(X_C)$是$C$上定义的严格正函数,乘积是在无向图所有的最大团上进行的,这便是Hammersley-Clifford定理

二.马尔科夫随机场的定义

这里再倒回来说一下马尔科夫随机场的定义,其实我们在实际问题中很难遇到需要考究其定义的情况,因为既然无向图都画出来了,说明肯定是满足其定义的~~~ ,好的,要构建一个马尔科夫随机场需要满足如下三个定义

成对马尔科夫性

设$u$和$v$是无向图$G$中任意两个没有边直接连接的节点,其对应的随机变量分别为$X_u$,$X_v$,剩余的所有节点为$O$,对应的随机变量组为$X_O$,那么在给定$X_O$的条件下,随机变量$X_u$与$X_v$是条件独立的,即

$$ P(X_u,X_v\mid X_O)=P(X_u\mid X_O)P(X_v\mid X_O) $$

PS:可以想象所有$O$构成了一堵墙将$u$与$v$隔断

局部马尔科夫性

设$u\in V$是无向图$G$中任意一个节点,$W$是与$v$有边直接相连的所有节点,$O$是$v$和$W$以外的其他所有节点,$v$对应的随机变量是$X_v$,$W$对应的随机变量组是$X_W$,$O$对应的随机变量组是$X_O$,那么在给定$X_W$的条件下,$X_u$与$X_O$是条件独立的,即

$$ P(X_u,X_O\mid X_W)=P(X_u\mid X_w)P(X_O\mid X_W) $$

PS:可以想象所有$W$构成了一堵$v$的围墙,将它与外界隔离

全局马尔科夫性

设节点集合$A,B$是无向图$G$中被节点集合$C$分开的任意节点集合,它们对应的随机变量组分别为$X_A,X_B,X_C$,那么在$X_C$给定的条件下,$X_A$与$X_B$条件独立:

$$ P(X_A,X_B\mid X_C)=P(X_A\mid X_C)P(X_B\mid X_C) $$

其实,这三个定义是互相等价的,所以只需其一即可

In [ ]: