概率图模型(2)——马尔科夫随机场

2019-08-23 本文已影响0人 To_QT

概念导图

1. MarKov随机场的直观理解

干货|如何轻松愉快的理解条件随机场（CRF）？

2. 一些基本概念

2.1 无向图

无向图

在无向图中，A、B、C、D为顶点，各顶点之间的连接线称为边。

2.2 概率图：

用图表达概率分布的方式。图中的每个节点表示一个随机变量，与之相连的边则表示了各随机变量之间的概率依赖关系。所以，图表示联合概率分布。以上图为例，设有联合概率分布 $P(Y)$ ， $Y$ 是一组随机变量，那么在图中，节点A表示一个随机变量 $Y_A$ ，节点A与节点B的边表示随机变量A与随机变量B之间的依赖关系。

无向图表示MarKov的三个性质：
- 成对马尔科夫性
  
  成对马尔科夫示意图
  节点u、v互不相连，其他所有节点记为O，其所对应的随机变量为 $Y_u, Y_v$ 和 $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)$
- 局部马尔可夫性
  
  局部马尔科夫示意图
  在图中任意取一个结点，将与之有边相连的结点均记为W，O是除v、W之外的所有点，v表示随机变量 $Y_v$ ，W表示随机变量组为 $Y_W$ ，O表示随机变量组 $Y_O$ ，则：在给定随机变量组 $Y_W$ 的情况下， $Y_v, Y_O$ 条件独立，即有
  $\begin{align} P(Y_v, Y_O|Y_W)&=P(Y_v|Y_W) P(Y_O|Y_W)\\\\ \Rightarrow \frac{P(Y_v, Y_O, Y_W)}{P(Y_W)}&=P(Y_v|Y_W) \frac{P(Y_O, Y_W)}{P(Y_W)}\\\\ \Rightarrow \frac{P(Y_v, Y_O, Y_W)}{P(Y_O, Y_W)}&=P(Y_v|Y_W)\\\\ \Rightarrow P(Y_v| Y_O, Y_W)&=P(Y_v|Y_W) \end{align}$
- 全局马尔科夫性
  
  全局马尔科夫示意图
  在图中设有集合A,B是被集合C分开的任意结点集合，其所对应的随机变量组分别为 $Y_A.Y_B,Y_C$ ，则在此条件下，认定随机变量组 $Y_C$ 条件下，随机变量组 $Y_A.Y_B$ 是条件独立的。
  $P(Y_A, Y_B|Y_C)=P(Y_A|Y_C) P(Y_B|Y_C)$

2.3 概率图模型：

如果联合概率分布 $Y$ 满足成对、局部或全局马尔可夫性，则该联合概率分布为概率无向图模型（马尔科夫随机场）。

概率图模型中的团和最大团：

一条小团团
在无向图中任何两个结点均有边连接的结点子集称为团，例如，在下图中，假设有随机变量，则构成了一个团，未构成团。

此时，再往团中加入任意一个结点，若集合不满足成团的条件，则称加入结点之前的团为最大团。如，往集合 $\left \{Y_1,Y_2 \right \}$ 中加入 $Y_2$ ，依然满足成团的条件，继续加入结点 $Y_4$ ，由于 $Y_1$ 不与 $Y_4$ 相连，故而 $\left \{Y_1,Y_2, Y_3 \right \}$ 为最大团。

无向图的团和最大团

概率图模型中因式分解

谈这个问题之前，先看一看贝叶斯模型和概率图模型的区别：

两个贝叶斯模型

贝叶斯网络1
贝叶斯网络1的联合概率 $P(R, C, W, S)=P(R)P(C)P(W|C,R)P(S|W)$
贝叶斯网络2

贝叶斯网络2是一个无效的网络，因为按照公式有
$P(A,B,C)=P(B|A)P(C|B)P(A|C) =P(B,C|A)P(A|C)=P(ABC|C)$

概率图模型：
但是在概率图模型中就不一样了
概率图模型
有人找了一个函数，能够使得，概率图中的最大团们有：
$P(A,B,C,D,E)\propto \Psi(A,B)\Psi(B,C)\Psi(B,D)\Psi(C,E)\Psi(D,E)$

概率图模型中因式分解：将概率图中的联合概率分布表示为其最大团上的随机变量函数成绩的形式。
$\begin{align} P(Y)=&\frac{1}{Z} \prod_{C}\Psi _C(Y_C) \tag{2.1}\\ Z=&\sum_{Y}\prod_{C}\Psi _C(Y_C) \tag{2.2} \end{align}$
其中，C是无向图的最大团， $Y_C$ 是C的结点对应的随机变量， $\Psi _C(Y_C)$ 是势函数，是C上定义的严格正函数，乘积是在无向图所有的最大团上进行的。