# 概率无向图模型

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

## 概率图模型的定义

图是由结点和连接结点的边组成的集合, 结点和边分别记作$$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))$$