概率无向图模型

概率无向图模型又称为马尔科夫随机场, 是一个由无向图表示的联合概率分布.

概率图模型的定义

图是由结点和连接结点的边组成的集合, 结点和边分别记作$v$和$e$, 结点和边的集合分别记作$V$和$E$, 图就记作$G=(V,E)$.

概率图模型是由图表示的概率分布, 假设$Y$是一组随机变量, 联合分布$P(Y)$. 由无向图$G=(V,E)$按照下面的方式表示概率分布$P(Y)$:

• 在图$G$中, 结点$v\in{V}$表示一个随机变量$Y_v$, 因此随机变量组$Y$就为$Y=(Y_v)_{v\in{V}}$

• 边$e\in{E}$表示随机变量之间的概率依赖关系

无向图的马尔科夫性

对于给定的联合分布概率$P(Y)$和对应的无向图$G$, 定义无向图表示的随机变量之间的三种马尔科夫性:

• 成对马尔科夫性

  $u$和$v$是无向图$G$中任意两个没有边连接的结点, 对应的随机变量分别为$Y_u$和$Y_v$, 其他所有结点为$O$, 对应的随机变量组为$Y_O$.

  成对马尔科夫性是指: 给定随机变量组$Y_O$的前提下, 随机变量$Y_u$和$Y_v$是条件独立的, 即有:

  $P(Y_u,Y_v|Y_O)=P(Y_u|Y_O)P(Y_v|Y_O)$

• 局部马尔科夫性

  $u$是无向图中任意一个结点, $W$是与$v$有边连接的所有结点, $O$是除$u$和$W$以外的其他所有结点, 局部马尔科夫性指的是: 在给定随机变量组$Y_W$的条件下随机变量$Y_v$和随机变量组$Y_O$是条件独立的, 即有:

  $P(Y_u,Y_O|Y_W)=P(Y_u|Y_W)P(Y_O|Y_W)$

  又因为:

  $P(Y_u,Y_O|Y_W)=P(Y_u|Y_O,Y_W)P(Y_O|Y_W)$

  当$P(Y_O|Y_W)>0$时, 有:

  $P(Y_u|Y_W)=P(Y_u|Y_O,Y_W)$

• 全局马尔科夫性

  结点集合$A$和$B$在无向图中被结点集合$C$分开, 全局马尔科夫性是指: 给定随机变量组$Y_C$, 随机变量组$Y_A$和$Y_B$是条件独立的, 即有:

  $P(Y_A,Y_B|Y_C)=P(Y_A|Y_C)P(Y_B|Y_C)$

以上就是定义的关于概率无向图的三种马尔科夫性, 而且这三种马尔科夫性的定义是等价的.

概率无向图模型的定义

联合概率分布$P(Y)$, 由无向图表示, 结点表示随机变量, 边表示随机变量之间的关系. 如果联合概率分布$P(Y)$满足成对, 局部或全局马尔科夫性, 就称此联合概率分布为概率无向图模型, 也称为马尔科夫随机场.

概率无向图模型的因子分解

我们希望将整体的联合概率分布写成若干个子联合概率的乘积形式, 也就是将联合概率进行因子分解, 以便于模型的学习与计算. 而概率无向图的最大特点就是易于进行因子分解.

首先定义团的概念:

• 团

  无向图中任何两个结点均有边连接的结点子集称为团

• 最大团

  对于无向图中的一个团, 如果不能再加进任何一个结点使其称为一个更大的团, 称此时的团为最大团

因子分解就是将概率无向图模型的联合概率分布表示成: 使用一个函数, 对于若干个最大团, 关于每个最大团的随机变量的函数的乘积的形式.

给定概率无向图模型, 假设$C$是无向图上的其中的一个最大团, $Y_C$表示$C$对应的随机变量, 那么概率无向图模型的联合概率分布$P(Y)$可写作图中所有最大团$C$上的函数$\Phi_C(Y_C)$成绩的形式, 即有:

$P(Y)=\frac{1}{Z}\prod\limits_{C}\Phi_C(Y_C)$

其中$Z$是规范化因子: $Z=\sum\limits_{Y}\prod\limits_{C}\Phi_C(Y_C)$

函数$\Phi_C(Y_C)$称为势函数, 要求是严格正的, 通常定义为指数函数:

$\Phi_C(Y_C)=\exp(-E(Y_C))$