原理

条件随机场（conditional random field，CRF）是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔科夫随机场。条件随机场可以用于不同的预测问题，此处仅考虑标注问题的应用。因此主要讲述线性链（linear chain）条件随机场，这时，问题变成了由输入序列对输出序列预测的判别模型，形式为对数线性模型，其学习方法通常是极大似然估计或正则化的极大似然估计。

概率无向图模型

概率无向图模型（Probabilistic undirected graphical model），又称为马尔可夫随机场（Markov random field），是一个可以由无向图表示的联合概率分布。

模型定义

图（graph）是由结点（node）及连接结点的边（edge）组成的集合。结点和边分别记作v和e，结点和边的集合分别记作V和E，图记作G=(V,E)。无向图是指没有方向的图。

概率图模型（probability graphical model）是由图表示的概率分布。设有联合概率分布\(P(Y), Y \in Y\)是一组随机变量。由无向图G=(V,E)表示概率分布P(Y)，即在图G中，结点\(v \in V\)表示一个随机变量\(Y_v, Y=(Y_v)_{v \in V}\)；边\(e \in E\)表示随机变量之间的概率依赖关系。

给定一个联合概率分布P(Y)和表示它的无向图G。首先定义无向图表示的随机变量之间存在的成对马尔可夫性（pairwise Markov property）、局部马尔可夫性（local Markov property）和全局马尔可夫性（global Markov property）。

成对马尔可夫性：设u和v是无向图G中任意两个没有边链接的结点，结点u和v分别对应随机变量\(Y_u\)和\(Y_v\)。其他所有结点为O，对应的随机变量组是\(Y_O\)。成对马尔可夫性是指给定随机变量组\(Y_O\)的条件下随机变量\(Y_u\)和\(Y_v\)是条件独立的，即

\[P(Y_u,Y_v \mid Y_O) = P(Y_u \mid Y_O) P(Y_v \mid Y_O)\]

局部马尔可夫性：设\(v \in V\)是无向图G中任意一个结点，W是与v有边连接的所有结点，O是v，W以外的的其他所有结点。v表示的随机变量是\(Y_v\)，W表示的随机变量组是\(Y_W\)，O表示的随机变量组是\(Y_O\)。局部马尔可夫性是指在给定变量组\(Y_W\)的条件下随机变量\(Y_v\)与随机变量组\(Y_O\)是独立的，即

\[P(Y_v, Y_O \mid Y_W) = P(Y_v \mid Y_W) P(Y_O \mid Y_W)\]

在$$P(Y_O \mid Y_W) > 0时，等价地

\[P(Y_v \mid Y_W) = P(Y_v \mid Y_W, Y_O)\]

全局马尔可夫性：设结点集合A，B是在无向图G中被结点集合C分开的任意结点集合。结点集合A,B和C所对应的随机变量组分别是\(Y_A,Y_B和Y_C\)。全局马尔可夫性是指给定随机变量组\(Y_C\)条件下随机变量组\(Y_A\)和\(Y_B\)是条件独立的，即

\[P(Y_A,Y_B \mid Y_C) = P(Y_A \mid Y_C) P(Y_B \mid Y_C)\]

上述成对的、局部的、全局的马尔可夫性是等价的。

概率无向图模型：设有联合概率分布P(Y)，由无向图G=(V,E)表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布P(Y)满足成对、局部或全局马尔可夫性，就称此联合分布为概率无向图模型（probability undirected graphical model），或马尔可夫随机场（Markov random field）。

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

以上是概率无向图模型的定义，实际上，我们更关心的是如何求其联合概率分布。对给定的概率无向图模型，我们希望将整体的联合概率写成若干子联合概率的乘积的形式，也就是将联合概率进行因子分解，这样便于模型的学习与计算。事实上，概率无向图模型的最大特点就是易于因子分解。

首先给出无向图中的团与最大团的定义。

团与最大团：无向图G中任何两个结点均有边连接的结点子集称为团（clique）。若C是无向图G的一个团，并且不能再加进任何一个G的结点使其成为一个更大的团，则称此C为最大团（maximal clique）。

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

给定概率无向图模型，设其无向图为G，C为G上的最大团，\(Y_C\)表示C对应的随机变量。那么概率无向图模型的联合概率分布P(Y)可写作图中所有最大团C上的函数\(\Psi_C(Y_C)\)的乘积形式，即

\[P(Y)=\frac{1}{Z} \prod_C \Psi_C (Y_C)\]

其中，Z是规范化因子（normalization factor），由式

\[Z = \sum_Y \prod_C \Psi_C (Y_C)\]

给出。规范化因子保证P(Y)构成一个概率分布。函数\(\Psi_C(Y_C)\)称为势函数（potential function）。这里要求势函数\(\Psi_C(Y_C)\)是严格正的，通常定义为指数函数：

\[\Psi_C(Y_C) = exp{-E(Y_C)}\]

概率无向图模型的因子分解由下述定理来保证。

Hammersley-Clifford定理：概率无向图模型的联合概率分布P(Y)可以表示为如下形式：

\[P(Y)=\frac{1}{Z} \prod_C \Psi_C (Y_C)\] \[Z = \sum_Y \prod_C \Psi_C (Y_C)\]

其中，C是无向图的最大团，\(Y_C\)是C的结点对应的随机变量，\(\Psi_C(Y_C)\)是C上定义的严格正函数，乘积是在无向图所有的最大团上进行的。