11.3 无向图模型（马尔科夫随机场）

11.3.1 马尔科夫随机场

一、概率分布

团：无向图中任何两个节点均有边相连的节点子集称为团

极大团：若C是无向图G的一个团，并且不能再加入G中的任何一个节点使其称为更大的团，则称C为G的一个极大团

将无向图模型的联合概率分布表示为其极大团上的随机变量的函数的乘积的形式，称为概率无向图模型的因子分解

给定无向图G，C为G上的极大团，$X_C$表示C对应到随机变量。则无向图模型的联合概率分布$P(X)$可以表示为图中所有极大团上的函数$\Psi_C(X_C)$的乘积形式：

$$P(X) = \frac1Z\prod_C\Psi_c(X_c)$$

其中，Z是归一化因子：

$$Z=\sum_X\prod_C\Psi_c(X_c)$$

在上式中，$\Psi_C(X_C)$称为势函数。一般来说，势函数既不是条件概率也不是边际概率，这里一般要求势函数是严格正的，因此一般定义为指数函数：

$$\Psi_c(X_c) = \exp\{-H_c(X_c)\}$$

二、表示

同样的，通过利用局部参数去表示联合概率，大大的缩小了参数的量

三、条件独立

相较于有向图，无向图的条件独立较为简单：

对于一个无向图，一个节点所有的邻居节点，构成该节点的马尔科夫包裹。

只要给定任一节点的邻居，则该节点和其余节点独立。

11.3.2 小结

定义一族概率分布的两种方式

• 通过枚举所有图上极大团的势函数的可能选择

$$P(X)=\frac1Z\prod_{C\in G}\varPhi_c(X_c)$$

• 通过声明图上的所有条件独立断言

$$P(X_i\mid X_{G\text{\\}i}) = P(X_i\mid X_{N_i})$$

Hammersley-Clifford 定理

Hammersley-Clifford 定理：

如果分布是严格正的并且满足局部马尔科夫性质，那么它对应的无向图G可以因子分解为定义在团上的正函数的乘积，这些团覆盖了G的所有顶点和边

对应于图$G=(V,E)$的一个分布具有局部马尔科夫性：

给定任意一节点的邻居，该节点和其余节点条件独立

基于此定理，可知上述两种方式是等价的