本篇笔记来自李航老师的《统计学习方法》一书
条件随机场最早由Lafferty等人2001年提出，其模型思想的主要来源是最大熵模型，模型的三个基本问题的解决用到了HMMs模型中的方法如forward-backward和Viterbi。我们可以把条件随机场看成是一个无向图模型或马尔科夫随机场，它是一种用来标记和切分序列化数据的统计模型。该模型在给定需要标记观察序列的条件下，计算整个标记序列的联合概率，而不是在给定当前状态条件下，定义一个状态的分布。标记序列的分布条件属性，可以让CRFs很好的拟合现实数据，而在这些数据中，标记序列的条件概率依赖于观察序列中非独立的、相互作用的特征，并通过赋予特征不同权值来表示特征的重要程度。
概率无向图模型
概率图模型(Graphical Models)
概率图模型是一类用图的形式表示随机变量之间条件依赖关系的概率模型，是概率论与图论的集合。图中的节点表示随机变量，缺少边表示条件独立假设。根据图中边有无方向，分为有向图和无向图。概率无向图，又称为马尔科夫随机场，是一个可以由无向图表示的联合概率分布。
图是由节点以及连接节点的边组成的集合。节点和边分别记作为v和e，节点和边的集合分别记作V和E，图记作G=(V,E)。无向图是指边没有方向的图。概率图模型是由图表示的概率分布。设有联合概率分布$P(Y),Y \in \cal 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|Y_O)=P(Y_u|Y_O)P(Y_v|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$是独立的，即：
(注：图引自:http://www.cnblogs.com/Determined22/p/6915730.html)
$$P(Y_v,Y_O|Y_W)=P(Y_v|Y_w)P(Y_O|Y_W)$$
在$P(Y_O|Y_W)>0$时，等价地：$P(Y_v|Y_W)=P(Y_v|Y_W,Y_O)$
全局马尔科夫性
设结点集合A、B是在无向图G中被结点集合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)，由无向图G(V,E)表示，在图G中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布P(Y)满足成对、局部和全局马尔科夫性，就称此联合概率分布为概率无向图模型或马尔科夫随机场。
以上是概率无向图模型的定义，实际上，我们更关心如何求其联合概率分布。对于给定的概率无向图模型，我们希望将整体的联合概率写成若干子联合概率乘积的形式，也就是将联合概率进行因子分解，这样便于模型的学习与计算。事实上，概率无向图模型的最大特点就是易于因子分解，下面介绍这一知识点。
首先给出无向图中的团和最大团的定义：
无向图G中任何两个结点，均有边连接的结点子集称为团(clique)。若C是无向图G的一个团，并且不能再加进任何一个G的结点使其成为一个更大的团，则称此C为最大团(maximal clique)。
例如，下图表示由4个结点组成的无向图。图中的2个结点组成的团有5个：${Y_1,Y_2},{Y_2,Y_3},{Y_3,Y_4},{Y_4,Y_2},{Y_1,Y_3}$。有2个最大团：${Y_1,Y_2,Y_3},{Y_2,Y_3,Y_4}$。而${Y_1,Y_2,Y_3,Y_4}$不是一个团，因为$Y_1$和$Y_4$没有边连接
将概率无向图模型的联合概率分布表示为其最大团上的随机变量的函数的乘积形式的操作，称为概率无向图模型的因子分解(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 factror)，由公式：
$$
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上定义的严格正函数，乘积是在无向图所有的最大团上进行的。
条件随机场定义
条件随机场(conditional random field)是在给定随机变量X条件下，随机变量Y的马尔科夫随机场。这里主要介绍定义在线性链上的特殊的条件随机场，称为线性链条件随机场(linear chain conditional random field)。线性链条件随机场可以用于标注等问题。这时，在条件概率模型P(Y|X)中，Y是输出变量，表示标记序列，X是输入变量，表示需要标注的观测序列。也把标记序列称为状态序列。学习时，利用训练数据集通过极大似然估计或正则化的极大似然估计得到条件概率模型$\hat P(Y|X)$;预测时，对于给定的输入序列x，求出条件概率$\hat P(y|x)$最大的输出序列$\hat y$。
首先定义一般的条件随机场，然后定义线性链条件随机场。
(条件随机场)，设X与Y是随机变量，P(Y|X)是在给定X的条件下Y的条件概率分布。若随机变量Y构成一个由无向图G=(V,E)表示的马尔科夫随机场，即：
$$P(Y_v|X, w\neq v)=P(Y_v|X,Y_w, w \sim v)$$
对任意结点v成立，则称条件概率分布P(Y|X)为条件随机场。式中$w \sim v$表示在图G=(V,E)中与结点v有结点v有边连接的所有结点w，$w \neq v$结点v以外的所有结点，$Y_v,Y_u与Y_w$为结点v,u与w对应的随机变量。
在定义中没有要求X和Y具有相同的结构。现实中，一般假设X和Y有相同的图结构。本书主要考虑无向图为下图所示的线性链的情况，即：
$$G=(V={1,2,…,n},E={(i,i+1)}), i=1,2,…, n-1$$
在此情况下，$X=(X_1,X_2,…,X_n)，Y=(Y_1,Y_2,…,Y_n)$，最大团是相邻两个结点的集合。
线性链条件随机场有下面的定义：
设$X=(X_1,X_2,…,X_n)，Y=(Y_1,Y_2,…,Y_n)$均为线性链表示的随机变量序列，若下给定随机变量序列X的条件下，随机变量序列Y的条件概率分布P(Y|X)构成条件随机场，即满足马尔科夫性：
$$
P(Y_i|X,Y_1,..,Y_{i-1},…,Y_n)= P(Y_i|X, Y_{i-1},Y_{i+1})\\
i=1,2,…,n(在i=1和n时只考虑单边)
$$
则称P(Y|X)为线性链条件随机场。在标注问题中，X表示输入观测序列，Y表示对应的输出标记序列或状态序列。
参数化形式
根据Hammersley-Clifford定理,可以给出线性链条件随机场P(Y|X)的因子分解式，各因子是定义在相邻两个结点上的函数。
定理(线性链条件随机场的参数化形式) 设P(Y|X)为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率具有如下形式：
$$
p(y|x)= \frac {1}{Z(x)} exp {\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_{l}s_l(y_i, x,i)}
$$
其中，
$$
Z(x)=\sum_y exp ({\sum_{i,k}\lambda_kt_k(y_{i-1},y_i,x,i)+\sum_{i,l}\mu_{l}s_l(y_i, x,i)})
$$
式中，$t_k和s_l$是特征函数，$\lambda_k和\mu_l$是对应的权值。$Z(x)$是规范化因子，求和是在所有可能的输出序列上进行的。
上面的两个式子是线性链条件随机场模型的基本形式，表示给定输入序列x，对输出序列y预测的条件概率。$t_k$是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置，$s_l$是定义在结点上的特征函数，称为状态特征，依赖于当前位置。$t_k和s_l$都依赖于位置，是局部特征函数。通常，特征函数$t_k和s_l$取值为1或0;当满足特征条件时取值为1，否则为0。条件随机场完全由特征函数$t_k,s_l$和对应的权值$\lambda_k,\mu_l$确定。
线性链条件随机场也是对数线性模型(log linear model)。
简化形式
条件随机场还可以由简化形式表示。注意到条件随机场式中同一特征在各个位置都有定义，可以对同一个特征在各个位置求和，将局部特征函数转化为一个全局特征函数，这样就可以将条件随机场写成权值向量和特征向量的内积形式，即条件随机场的简化形式。
为简便起见，首先将转移特征和状态特征及其权值用统一的符号表示。设有$K_1$个转移特征，$K_2$个状态特征，$K=K_1+K_2$，记：
$$
f_k(y_{i-1},y_i, x,i) = \begin{cases}
t_k(y_{i-1},y_i, x, i)& k=1,2,…,K_1\\
s_l(y_i, x, i)& k=K_1+l; l=1,2,…,K_2
\end{cases}
$$
然后，对转移与状态特征在各个位置i求和，记作：
$$f_k(y,x) = \sum_{i=1}^n f_k(y_{i-1}, y_i, x,i), k=1,2,..,K$$
用$w_k$表示特征$f_k(y,x)$的权值，即：
$$
w_k = \begin{cases}
\lambda_k, & k=1,2,…,K_1\\
\mu_l, & k=K_1+l; l=1,2,…,K_2
\end{cases}
$$
于是，条件随机场可以表示为：
$$
P(y|x) = \frac {1}{Z(x)}exp \sum_{k=1}^K w_kf_k(y,x)\\
Z(x) = \sum_y exp \sum_{k=1}^K w_kf_k(y,x)
$$
若以w表示权值向量，即：
$$w = (w_1,w_2,…,w_K)^T$$
以F(y,x)表示全局特征向量，即：
$$F(y,x) = (f_1(y,x),f_2(y,x),…,f_k(y,x))^T$$
则条件随机场可以写成向量w与F(y,x)的内积形式：
$$
P_w(y|x) = \frac {exp(w\cdot F(y,x))}{Z_w(x)}
$$
其中，
$$Z_w(x) = \sum_y exp(w\cdot F(y,x))$$
矩阵形式
条件随机场还可以由矩阵表示。假设$P_w(y|x)$是由内积形式给出的线性链条件随机场，表示对给定观测序列x，相应的标记序列y的条件概率。引进特殊的起点和终点状态标记$y_0=start,y_{n+1}=stop$，这时$P_w(y|x)$可以通过矩阵的形式表示。
对观察序列x的每个位置i=1,2,…,n+1，定义一个m阶矩阵(m是标记$y_i$取值个数)
$$
M_i(x) = [M_i(y_{i-1},y_i|x)]\\
M_i(y_{i-1},y_i|x)=exp(W_i(y_{i-1},y_i|x))\\
W_i(y_{i-1},y_i|x) = \sum_{i=1}^K w_kf_k(y_{i-1},y_i,x,i)
$$
这样，给定观测序列x，标记序列y的非规范化概率可以通过n+1个矩阵的乘积$\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$表示，于是，条件概率$P_w(y|x)$是:
$$
P_w(y|x)=\frac {1}{Z_w(x)}\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)
$$
其中，$Z_w(x)$为规范化因子，是n+1个矩阵的乘积(start,stop)元素：
$$
Z_w(x)= (M_1(x)M_2(x)…M_{n+1}(x))_{start,stop}
$$
注意，$y_0=start与y_{n+1}=stop$表示开始状态与终止状态，规范化因子$Z_w(x)$是以start为起点stop为终点通过状态的所有路径$y_1y_2,…,y_m$的非规范化概率$\prod_{i=1}^{n+1}M_i(y_{i-1},y_i|x)$之和。
这个M矩阵和一阶HMM中的转移概率矩阵，因为链式CRF中只有相邻两个结点之间才有连接边。
三个问题
概率计算问题
条件随机场的概率计算问题是给定条件随机场P(Y|X)，输入序列x和输出序列y，计算条件概率$
P(Y_i=y_i|x),P(Y_{i-1}=y_{i-1},Y_i=y_i|x)$以及相应的数学期望问题。为了方便起见，像隐马尔科夫模型那样，引进前向-后向向量，递归地计算以上概率及期望值。像这样的算法称为前向-后向算法。
前向-后向算法
对每个指标$i=0,1,…,n+1$，定义前向向量$\alpha_i(x)$:
$$
\alpha_0(y|x)=\begin{cases}
1, & y=start \\
0, & 否则
\end{cases}
$$
递推公式为：
$$
\alpha_i^T(y_i|x)=\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x),i=1,2,…,n+1
$$
又可以表示为：
$$
\alpha_i^T(x) = \alpha_{i-1}^T(x)M_i(x)
$$
$\alpha_i(y_i|x)$表示在位置i的标记是$y_i$并且到位置i的前面部分标记序列的非规范化概率，$y_i$可取的值有m个，所以$\alpha_i(x)$是m维列向量。
同样，对于每个位置$i=0,1,…,n+1$，定义后向向量$\beta_i(x)$:
$$
\beta_{n+1}(y_{n+1}|x)=\begin{cases}
1, & y=stop \\
0, & 否则
\end{cases}\\
\beta_i(y_i|x)=M_{i+1}(y_i,y_{i+1}|x)\beta_{i+1}(y_{i+1}|x),i=1,2,…,n+1
$$
又可以表示为：
$$
\beta_i(y_i|x)=M_{i+1}(x)\beta_{i+1}(x)
$$
$\beta_i(y_i|x)$表示在位置i的标记$y_i$并且从i+1到n的后面标记序列的非规范化概率。
由前向-后向向量定义不难得到：
$$
Z(x) = \alpha_n^T(x)\cdot 1 = 1^T \cdot \beta_1(x)
$$
这里的1是元素均为1的m维列向量。
概率计算
按照前向-后向向量的定义，很容易计算标记序列在为位置i是标记$y_i$的条件概率和在位置$i-1$与i的标记$y_{i-1}和y_i$的条件概率。
$$
\begin{align}
&P(Y_i=y_i|x) =\frac {\alpha_i^T(y_i|x)\beta_i(y_i|x)}{Z(x)}\\
&P(Y_{i-1}=y_{i-1},Y_i=y_i|x)=\frac {\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i,|x)}{Z(x)}\\&其中，Z(x)=\alpha_n^T(x)\cdot 1
\end{align}
$$
期望计算
利用前向-后向向量，可以计算特征函数关于联合分布P(X,Y)和条件分布P(Y|X)的数学期望。
特征函数$f_k$关于条件分布P(Y|X)的数学期望是：
$$
\begin{align}E_{P(Y|X)}[f_k]
&= \sum_y P(y|x)f_k(y,x)\\
&=\sum_{i=1}^{n+1} \sum_{y_{i-1},y_i}f_k(y_{i-1},y_i,x,i)\frac {\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i,|x)}{Z(x)}\\
& k=1,2,…,K
\end{align}$$
其中，
$$
Z(x) = \alpha_n^T(x)\cdot 1
$$
假设经验分布$\widetilde P(X)$，特征函数$f_k$关于联合分布P(X,Y)的数学期望是:
$$
\begin{align}E_{P(X,Y)}[f_k]
&=\sum_{x,y}P(x,y)\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\\
&=\sum_x \widetilde P(x)\sum_y P(y|x)\sum_{i=1}^{n+1}f_k(y_{i-1},y_i,x,i)\\
&=\sum_x \widetilde p(x)\sum_{i=1}^{n+1}\sum_{y_{i-1}y_i}f_k(y_{i-1},y_i,x,i)\frac {\alpha_{i-1}^T(y_{i-1}|x)M_i(y_{i-1},y_i|x)\beta_i(y_i|x)}{Z(x)}\\k=1,2,…,K
\end{align}
$$
其中，
$$
Z(x)=\alpha_n^T(x) \cdot 1
$$
对于转移特征$t_k(y_{i-1},y_i,x,i),k=1,2,…,K_1$，可以将式中的$f_k$替换成$t_k$；对于状态特征，可以将式中的$f_k$替换为$s_i$，表示为$s_l(y_i,x,u),k=K_1+l,l=1,2,…,K_2$。
有了上面的公式，对于给定的观测序列x与标记序列y，可以通过一次前向扫描计算$\alpha_i及Z(x)$，通过一次后向扫描计算$\beta_i$，从而计算所有的概率和特征的期望。
学习方法
条件随机场在时序数据上的对数线性模型，使用MLE或带正则的MLE来训练。类似于最大熵模型，可以采用改进的迭代尺度法(IIS)和拟牛顿法(如BFGS算法)来训练。
训练数据${(x^{j},y^{j})}_{j=1}^N$的对数似然函数为：
$$
\begin{align}
L(w) &= L_{\widetilde P}(P_w)\\
&=ln \prod_{j=1}^N P_w(Y=y^{(j)}|x^{(j)})\\
&=\sum_{j=1}^N ln P_w(Y=y^{(j)}| x^{(j)})\\
&=\sum_{j=1}^N ln \frac {exp \sum_{k=1}^K w_kf_k(y^{(j)},x^{(j)}) }{Z_w(x^{(j)})}\\
&=\sum_{j=1}^N (\sum_{k=1}^K w_kf_k(y^{(j)},x^{(j)}) - ln Z_w(x^{(j)}) )
\end{align}
$$
或者可以写成这样：
$$
\begin{aligned}L(\textbf w)=L_{\widetilde P}(P_\textbf w)&=\ln\prod_{x,y}P_{\textbf w}(Y=y|x)^{\widetilde P(x,y)}\\&=\sum_{x,y}\widetilde P(x,y)\ln P_{\textbf w}(Y=y|x)\\&=\sum_{x,y}\widetilde P(x,y)\ln \frac{\exp\sum_{k=1}^Kw_kf_k(y,x)}{Z_{\textbf w}(x)}\\&=\sum_{x,y}\widetilde P(x,y)\sum_{k=1}^Kw_kf_k(y,x)-\sum_{x,y}\widetilde P(x,y)\ln Z_{\textbf w}(x)\\&=\sum_{x,y}\widetilde P(x,y)\sum_{k=1}^Kw_kf_k(y,x)-\sum_{x}\widetilde P(x)\ln Z_{\textbf w}(x)\end{aligned}
$$
最后一个等号是因为$\sum_y P(Y=y|x)=1$。顺便求个导：
$$
\begin{aligned}\frac{\partial L(\textbf w)}{\partial w_i}&=\sum_{x,y}\widetilde P(x,y)f_i(x,y)-\sum_{x,y}\widetilde P(x)P_{\textbf w}(Y=y|x)f_i(x,y)\\&=\mathbb E_{\widetilde P(X,Y)}[f_i]-\sum_{x,y}\widetilde P(x)P_{\textbf w}(Y=y|x)f_i(x,y)\end{aligned}
$$
似然函数中的$ln Z_w(x)$项是一个指数函数的和的对数的形式。
预测算法
条件随机场的预测问题是给定条件随机场P(Y|X)和输入序列（观测序列）x,求条件概率最大的输出序列（标记序列）$y^*$，即对观测序列进行标注。条件随机场预测算法是采用维特比算法。
由$P_w(y|x)=\frac {exp(w\cdot F(y,x))}{Z_w(x)}$可得：
$$\begin{align}
y^{*}&=arg max_yP_w(y|x)\\
&=arg max_y \frac {exp(w \cdot F(y,x))}{Z_w(x)}\\
&=arg max_y exp(w \cdot F(y,x))\\
&=arg max_y(w \cdot F(y,x))
\end{align}$$
于是，条件随机场预测问题就成为求非规范化概率最大的最优路径问题：
$$
max_y(w \cdot F(y,x))
$$
这里，路径表示标记序列，其中，
$$\begin{align}
&w = (w_1,w_2,…,w_K)^T\\
&F(y,x) = (f_1(y,x),f_2(y,x),…,f_K(y,x))^T\\
&f_k(y,x)=\sum_{i=1}^n f_k(y_{i-1},y_i, x,i), k=1,2,…,K
\end{align}$$
注意，这时只需计算非规范化概率，而不必计算概率，可以大大提高效率。为了求解路径，将$max_y(w \cdot F(y,x))$写成如下形式：
$$max_y \sum_{i=1}^n w\cdot F_i(y_{i-1,y_i,x})$$
其中，
$$
F_i(y_{i-1},y_i,x) = (f_1(y_{i-1},y_i,x,i), f_2(y_{i-1}, y_i, x,i), … , f_K(y_{i-1},y_i,x,i))^T
$$
是局部特征向量。
下面叙述维特比算法，首先求出位置1的各个标记j=1,2,…,m的非规范化概率：
$$
\delta_1(j) = w \cdot F_1(y_0=start, y_1=j,x), j=1,2,…,m
$$
一般地，由地推公式，求出到位置i的各个标记l=1,2,..,m的非规范化概率的最大值，同时记录非规范化概率最大值的路径：
$$
\delta_i(l) = max_{1\le j \le m} {\delta_{i-1}(j)+w \cdot F_i(y_{i-1}=j, y_i=l,x)},l=1,2,…,m\\
\Psi_i(l) = arg max_{1 \le j \le m} { \delta_{i-1}(j) + w \cdot F_i(y_{i-1}=j, y_i=l,x)}, l =1,2,…,,m
$$
直到i=n时终止。这时求得非规范化概率的最大值为：
$$
max_y (w \cdot F(y,x)) = max_{1 \le j \le m}\delta_n(j)
$$
及最优的终点：
$$
y_n^ = \Psi_{i+1}(y_{i+1}^),i = n-1,n-2,…,1
$$
求得最优路径$y^ = (y_1^, y_2^, …, y_n^)^T$
维特比算法如下：
