概率模型（四）：条件随机场(CRF)

概率图模型用图的形式表示一组随机变量。图中的节点表示一个或一组随机变量，图中的边代表随机变量间的依赖关系。

概率图模型分为有向图模型和无向图模型，如下：

下面将依次介绍

有向图模型

有向图模型中，我们主要考虑贝叶斯网络，它满足下面特征的模型：

对于一个无向图$G$以及它表示的一组随机变量$X={x_1,x_2,...,x_N}$,$x_i$的所有父节点组成的集合我们记作$X_{\pi i}$,如果$X$的联合概率分布可以表示为：

$p(X)=\prod_{i=1}^Np(x_i|x_{\pi i})$

那么$G$被称为一个贝叶斯网络

常见的贝叶斯网络有：sigmoid信念网络（SBN），朴素贝叶斯模型，以及上篇的隐马尔科夫模型。

模型的局部条件概率表示为：

$p(x_k\mathrm{}{X}_{\pi k},W)=\sigma (w_0+\sum _{x_i\in X_{\pi k}}{w}_i{x}_i)$

模型的局部条件表示为：

$P\left(x_k\mathrm{}{X}_{\pi k}\right)=\frac{P\left(X_{\pi k}\mathrm{}{x}_k\right)P\left(x_k\right)}{P\left(X_{\pi k}\right)}$

$\propto P(X_{\pi k}|x_k)P(x_k)$
$=P(x_k)\prod_{x_i\in X_{\pi k}} P(x_i|x_k)$

上一篇详细介绍了此模型，它的联合分布概率表示为：
$P(Q,V)=\prod _{q_t\in Q,v_t\in V}P\left(v_t\mathrm{}{v}_{t1}\right)P\left(q_t\mathrm{}{v}_t\right)$

其中$P(v_t|v_{t-1})$是转移概率，$P(q_t|v_t)$为输出概率。

对于无向图模型，我们主要考虑马尔科夫随机场(Markov Random Field,MRF),也称为马尔科夫网络(Markov Network).

无向图G,图中的节点表示随机变量，边表示随机变量间的依赖关系。如果图中随机变量的联合概率分布P(X)满足成对、局部或全局马尔可夫性，则G被称为马尔科夫随机场

那么我们分别来解释下成对、局部、全局马尔科夫性分别是什么性质。

成对马尔科夫性

无向图中的任意不直接相连的两个节点$x_i,x_j$，以及除它们之外的所有节点组成的集合,记作$X_O$.

如果给定$X_O$的情况下，$x_i,x_j$条件独立，则称无向图满足成对马尔科夫性质,即：

$P(x_i,x_j|X_O)=P(x_i|X_O)P(x_j|X_O)$

无向图中的任意一个节点$x_k$, 与之直接向量的节点组成的集合，记作$X_{N(k)}$,$x_k$之外的所以其他节点组成的集合，记作$X_{-k}$.

如果：

$P(x_k|X_{N(k)})=P(x_k|X_{-k})$

则称无向图满足局部马尔科夫性。

无向图中不直接相邻节点集合$X_A,X_B$,已经连接他们的节点组成的集合$X_C$。

如果:

$P(X_A,X_B|X_C)=P(X_A|X_C)P(X_B|X_C)$

则称无向图满足全局马尔科夫性。

有向图中联合概率分布可以分解为局部条件概率的乘积形式，无向图中的联合概率分布如果计算呢？

无向图中的边不表示因果依赖关系，所以不能运用链式法则分解为条件概率的乘积形式。在介绍无向图联合概率分解方法之前，先引入团的概念。

无向图中的全联通子图，有称为团，如果一个团加入任何一个节点后不能构成团，则称之为最大团

无向图满足成对、局部或全局马尔科夫性，当且仅当联合分布概率可以表示一系列定义在最大团上的非负函数的乘积形式，即：

$P\left(X\right)=\frac{1}{Z}\prod _{X_c\in C}\left(X_c\right)$
其中，
$Z=\sum_{X_c\in C}\phi(X_c)$

称为配平函数(partition function),$\phi(X_c)\ge0$称为势能函数，$X_c$为一个最大团，$C$为最大团组成的集合。

由于势能函数必须是非负的，所以经常采用势能函数：

$\phi(X_c)=exp(-E(X_c))$

其中$E(X_c)$被称为能量函数。如此，联合概率分布可表示为：

$P(X)=\frac{1}{Z}\prod_{X_c\in C}\phi(X_c)$
$=\frac{1}{Z}\prod_{X_c\in C}exp(-E(X_c))$
$=\frac{1}{Z}exp(\sum_{X_c\in C}-E(X_C))$

条件随机场就是常见的无向图模型之一，另外常见的无向图模型还有对数线性模型、玻尔兹曼机和受限玻尔兹曼机。介绍条件随机场之前，先简单介绍一下对数线性模型，玻尔兹曼机与受限玻尔兹曼机在之前的文章里已有介绍，不再赘述。

势能函数采用：
${}_c\left(X_c\mathrm{}{\theta }_c\right)=exp\left({\theta }_c^T{f}_c\right(X_c\left)\right)$

所以联合分布概率表示为：

$P(X|\theta)=\frac{1}{z(\theta)}\prod_{X_c\in C}exp(\theta_C^T f_c(X_c))$

$log(P(X|\theta))=log(\prod_{X_c\in C}exp(\theta_c^T f_c(X_c)))-log(z(\theta))$