一、条件随机场的学习问题
条件随机场模型实际上是定义在时序数据上的对数线形模型，其学习方法包括极大似然估计和正则化的极大似然估计。具体的优化实现算法有改进的迭代尺度法IIS、梯度下降法以及拟牛顿法。（其中，主流的CRF软件之CRF++采用了拟牛顿法+L-BFGS优化，所以着重看这种训练方法即可。）
1.1、改进的迭代尺度法
已知训练数据集，由此可知经验概率分布$\hat(P)(X,Y)$,可以通过极大化训练数据的对数似然函数来求模型参数。
训练数据的对数似然函数为
$$
L(w)=L_{\hat(P)}(P(w))=log\prod_{x,y}P_{w}(x|y)^{\hat{P}(x,y)}=\sum_{x,y}\hat{P}(x,y)logP_{w}(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))$给出的条件随机场模型时，对数似然函数为
$$
\begin{split}
L(w){} & =\sum_{x,y}\hat{P}(x,y)logP_{w}(y|x)\\
{} & =\sum_{x,y}\Bigg(\hat{P}(x,y)\sum_{k=1}^{K}w_{k}f_{k}(y,x)-\hat{P}(x,y)logZ_{w}(x)\Bigg)\\
{} & =\sum_{j=1}^{N}\sum_{k=1}^{K}w_{k}f_{k}(y_{j},x_{j})-\sum_{j=1}^{N}logZ_{w}(x_{j})
\end{split}
$$
改进的迭代尺度法通过迭代的方法不断优化对数似然函数改变量的下界，达到极大化对数似然函数的目的。假设模型的当前参数向量$w=(w_{1},w_{2},….,w_{k})^T$向量的增量为$\delta=(\delta_{1},\delta_{2},….,\delta_{k})^T$,更新向量参数为$w+\delta=(w_{1}+\delta_{1},w_{2}+\delta_{2},…,w_{k}+\delta_{k})^T$在每步迭代过程中，改进的迭代尺度法通过依次求解下面两个式子,得到$\delta=(\delta_{1},\delta_{2},….,\delta_{k})^T$。推导可参考《改进的迭代尺度法》
关于转移特征$t_{k}$的更新方程为
$$
\begin{split}
E_{\hat{P}}(t_{k}){} & =\hat{P}(x,y)\sum_{i=1}^{n+1}t_{k}(y_{i-1},y_{i},x,i)\\
{} & =\sum_{x,y}\hat{P}(x)P(y|x)\sum_{i=1}^{n+1}t_{k}(y_{i-1},y_{i},x,i)exp(\delta_{k}T(x,y)),k=1,2,….,K_{1}
\end{split}
$$
关于状态特征$s_{l}$的更新方程为
$$
\begin{split}
E_{\hat{P}}(s_{l}){} & =\hat{P}(x,y)\sum_{i=1}^{n+1}s_{l}(y_{i},x,i)\\
{} & =\sum_{x,y}\hat{P}(x)P(y|x)\sum_{i=1}^{n}s_{l}(y_{i},x,i)exp(\delta_{K_{1}+l}T(x,y)),k=1,2,….,K_{2}
\end{split}
$$
这里，$T(x,y)$是在数据$(x,y)$中出现所有特征数的总和：
$$
T(x,y)=\sum_{k}f_{k}(y,x)=\sum_{k=1}^{K}\sum_{i=1}^{n+1}f_{k}(y_{i-1},y_{i},x,i)\quad\quad\quad(1.1)
$$
条件随机场模型学习的改进的迭代尺度法
输入：特征函数$t_{1},t_{2},t_{3},….,t_{K_{1}}$,$s_{1},s_{2},…..,s_{K_{2}}$;经验分布$\hat{P}(x,y)$
输出：参数估计值$\hat{w}$;模型$P_{\hat{w}}$
(1) 对所有$k \in {1,2,…,K}$,取初值$w_{k}=0$
(2) 对每一个$k \in {1,2,…,K}$:
(a)当$k \in {1,2,…,K_{1}}$时，令$\delta_{k}$是方程
$$
\sum_{x,y}\hat{P}(x)P(y|x)\sum_{i=1}^{n+1}t_{k}(y_{i-1},y_{i},x,i)exp(\delta_{k}T(x,y))=E_{\hat{P}}[t_{k}]
$$
的解。
当$k=K_{1}+l$，$l=1,2,…,K_{2}$时，令$\delta_{k+1}$是方程
$$
\sum_{x,y}\hat{P}(x)P(y|x)\sum_{i=1}^{n} s_{l}(y_{i},x,i)exp(\delta_{K_{1}+l}T(x,y))=E_{\hat{P}}[s_{l}]
$$
的解,式中$T(x,y$是由式子(1.1)给出。
(b)更新$w_{k}$值:$w_{k} \longleftarrow w_{k}+\delta_{k}$
(c)如果不是所有的$w_{k}$都收敛，重复步骤(2)
在$t_{k}$的更新方程和状态特征$s_{l}$的更新方程中$T(x,y$表示数据$(x,y)$的特征总数，对不同的数据$(x,y)$可能取值不同。为了处理这个问题，定义松弛特征
$$
s(x,y)=S-\sum_{i=1}^{n+1}\sum_{k=1}^{K}f_{k}(y_{i-1},y_{i},x,i)
$$
式中S是一个常数。选择足够大的常数S使得对训练数据集的所有数据$(x,y)$,$s(x,y)\geq0$,这时特征总数可取S。
由转移特征$t_{k}$的更新方程,对于状态特征$t_{k}$和$delta_{k}$的更新方程是
$$
\sum_{x,y}\hat{P}(x,y)P(y|x)\sum_{i=1}^{n+1}t_{k}(y_{i-1},y_{i},x,i)exp(\delta_{k}S)=E_{\hat{P}}(t_{k})\\
\delta_{k}=\frac{1}{S}log\frac{E_{\hat{P}}(t_{k})}{E_{p}(t_{k})}
$$
其中，
$$
E_{p}(t_{k})=\sum_{k}\hat{P}(x)\sum_{i=1}^{n+1}\sum_{y_{i-1},y_{i}}t_{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)}
$$
同样,由状态特征$s_{l}$的更新方程,对于状态特征$s_{l}$和$delta_{k}$的更新方程是
$$
\sum_{x,y}\hat{P}(x,y)P(y|x)\sum_{i=1}^{n}s_{l}(y_{i},x,i)exp(\delta_{k}S)=E_{\hat{P}}(s_{l})\\
\delta_{k}=\frac{1}{S}log\frac{E_{\hat{P}}(s_{l})}{E_{p}(s_{l})}
$$
以上算法称为算法S。在算法S中需要使常数S取足够大，这样一来，每步迭代的增量向量会变大，算法收敛会变慢。算法T试图解决这个问题。算法T对每个观测序列x计算其特征总数最大值$T(x)$:
$$
T(x)=\max_{y}T(x,y)
$$
利用前向-后向递推公式，可以很容易地计算$T(x)=t$
这时，关于转移特征参数的更新方程可以写成：
$$
\begin{split}
E_{\hat{P}}(t_{k}){} & =\sum_{x,y}\hat{P}(x)P(y|x)\sum_{i=1}^{n+1}t_{k}(y_{i-1},y_{i},x,i)exp(\delta_{k}T(x)) \\
{} & =\sum_{x}\hat{P}(x)\sum_{y}P(y|x)\sum_{i=1}^{n+1}t_{k}(y_{i-1},y_{i},x,i)exp(\delta_{k}T(x)) \\
{} & =\sum_{x}\hat{P}(x)a_{k,l}exp(\delta_{k}\cdot t)\\
{} & =\sum_{t=0}^{T_{\max}}a_{k,l}\beta_{k}^{t}
\end{split}
$$
这里,$a_{k,l}$是特征$t_{k}$的期望值，$\delta_{k}=log\beta_{k}$,$\beta_{k}$是多项式方程唯一的实根,可以用牛顿法求得。从而求得相关的$\delta_{k}$。
同样，关于状态特征的参数更新方程可以写成：
$$
\begin{split}
E_{\hat{P}}(s_{l}){} & =\sum_{x,y}\hat{P}(x)P(y|x)\sum_{i=1}^{n}s_{l}(y_{i},x,i)exp(\delta_{K_{1}+1}T(x)) \\
{} & =\sum_{x}\hat{P}(x)\sum_{y}P(y|x)\sum_{i=1}^{n}s_{l}(y_{i},x,i)exp(\delta_{K_{1}+1}T(x)) \\
{} & =\sum_{x}\hat{P}(x)b_{k,l}exp(\delta_{l}\cdot t)\\
{} & =\sum_{t=0}^{T_{\max}}b_{k,l}\gamma_{l}^{i}
\end{split}
$$
这里,$b_{k,l}$是特征$s_{l}$的期望值，$\delta_{l}=log\gamma_{l}$,$\gamma_{l}$是多项式方程唯一的实根,可以用牛顿法求得。从而求得相关的$\delta_{k}$。
1.2、拟牛顿法
条件随机场模型学习还可以应用牛顿法或拟牛顿法。对于条件随机场模型
$$
P_{w}(y|x)=\frac{exp\Bigg(\sum_{i=1}^{n}w_{i}f_{i}(x,y)\Bigg)}{\sum_{y}exp\Bigg(\sum_{i=1}^{n}w_{i}f_{i}(x,y)\Bigg)}
$$
学习的优化目标函数是
$$
\min_{w \in R^n}f(w)=\sum_{x}\hat{P}(x)log\sum_{y}exp\Bigg(\sum_{i=1}^{n}w_{i}f_{i}(x,y)\Bigg)-\sum_{x,y}\hat{P}(x,y)\sum_{i=1}^{n}w_{i}f_{i}(x,y)
$$
其梯度函数是
$$
g(w)=\sum_{x,y}\hat{P}(x)P_{w}(y|x)f(x,y)-E_{\hat{P}}(f)
$$
拟牛顿法的BFGS算法如下。
算法(条件随机场模型学习的BFGS算法）
输入：特征函数$f_{1},f_{2},….,f_{n}$;经验分布$\hat(P)(x,y)$;
输出：最优参数值$\hat(w)$;最优模型$P_{\hat{w}}(y|x)$
(1)选定初始点$w^{(0)}$,取$B_{0}$为为正定对称矩阵，置$k=0$
(2)计算$g_{k}=g(w^{(k)})$,若$g_{k}=0$则停止计算；否则转(3)
(3)由$B_{k}p_{k}=-g_{k}$求出$p_{k}$
(4)一维搜索：求$\lambda_{k}$使得
$$
f(w^{(k)}+\lambda_{k}p_{k})=\min_{\lambda\geq0}f(w^{(k)}+\lambda p_{k})
$$
(5)置$w^{(k+1)}=w^{(k)}+\lambda_{k}p_{k}$
(6)计算$g_{k+1}=g(w^{(k+1)})$，若$g_{k}=0$则停止计算；否则，按下式求出$B_{k+1}$:
$$
B_{k+1}=B_{k}+\frac{y_{k}y_{k}^{T}}{y_{k}^{T}\delta_{k}}-\frac{B_{k}\delta_{k}\delta_{k}^{T}B_{k}}{\delta_{k}^{T}B_{k}\delta_{k}}
$$
其中，
$$
y_{k}=g_{k+1}-g_{k},\delta_{k}=w^{(k+1)}-w^{(k)}
$$
(7)置$k=k+1$，转(3)
二、条件随机场的预测问题
条件随机场的预测问题是给定条件随机场$P(Y|X)$和输入序列（观测序列）x,求条件概率最大的输出序列(标记序列)$y^{*}$即对观测序列进行标注。条件随机场的预测算法是著名的维特比算法。
由式$P_{w}(y|x)=\frac{exp(w\cdot F(y,x))}{Z_{w}(x)}$可得:
$$
\begin{split}
y^{*} {} & =arg \max_{y}P_{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{split}
$$
于是，条件随机场的预测问题成为求非规范化概率最大的最优路径问题
$$
max_{y}(w\cdot F(y,x))
$$
这里，路径表示标记序列。其中，
$$
\begin{split}
{} & 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{split}
$$
注意，这时只需计算非规范化概率，而不必计算概率，可以大大提高效率。为了求解最优路径，将$\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),f_{2}(y_{i-1},y_{i},x),…..,f_{K}(y_{i-1},y_{i},x))
$$
是局部特征向量。
下面叙述维特比算法。首先求出位置1的各个标记j=1,2,…，m的非规范化概率:
$$
\delta_l(j)=w\cdot F_{l}(y_{0}=start,y_{1}=j,x), j=1,2,…,m
$$
一般地，由递推公式，求出到位置i的各个标记$l=1,2,…,m$的非规范化概率的最大值，同时记录非规范化概率最大值的路径
$$
\begin{split}
{} & \delta_{i}(l)=\max_{1\leq j \leq 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\leq j \leq m}{\delta_{i-1}(j)+w\cdot F_{i}(y_{i-1}=j,y_{i}=l,x)},l=1,2,….,m
\end{split}
$$
直到$i=n$时终止。这时求得非规范化概率的最大值为
$$
max_{y}(w\cdot F(y,x))=\max_{1\leq j \leq m}\delta_{n}(j)
$$
及最优路径的终点
$$
y_{n}^{*}=arg \max_{1\leq j \leq m}\delta_{n}(j)
$$
由此最优路径终点返回,
$$
y_{i}^{*}=\psi_{i+1}(y_{i+1}^{*}),i=n-1,n-2,…,1
$$
求得最优路径$y^{*}=(y_{1}^{*},y_{1}^{*},y_{2}^{*}…,y_{n}^{*})^{T}$
综上所述，得到条件随机场预测的维特比算法:
输入：模型特征向量$F(y,x)$和权值向量$w$，观测序列$x=(x_{1},x_{2},…,x_{n})$
输出：最优路径$y^{*}=(y_{1}^{*},y_{1}^{*},y_{2}^{*}…,y_{n}^{*})^{T}$
(1) 初始化：
$$
\delta_l(j)=w\cdot F_{l}(y_{0}=start,y_{1}=j,x), j=1,2,…,m
$$
(2) 递推，对$i=2,3,…,n$
$$
\begin{split}
{} & \delta_{i}(l)=\max_{1\leq j \leq 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\leq j \leq m}{\delta_{i-1}(j)+w\cdot F_{i}(y_{i-1}=j,y_{i}=l,x)},l=1,2,….,m
\end{split}
$$
(3)终止
$$
max_{y}(w\cdot F(y,x))=\max_{1\leq j \leq m}\delta_{n}(j)
y_{n}^{*}=arg \max_{1\leq j \leq m}\delta_{n}(j)
$$
4)返回路径
$$
y_{i}^{*}=\psi_{i+1}(y_{i+1}^{*}),i=n-1,n-2,…,1
$$
求得最优路径$y^{*}=(y_{1}^{*},y_{1}^{*},y_{2}^{*}…,y_{n}^{*})^{T}$
三、总结
与HMM区别
- HMM是生成时模型，用到EM算法。CRF是判别式模型，一般方法是最大似然估计，结合梯度下降
- HMM是假定满足HMM独立假设。CRF没有，所以CRF能容纳更多上下文信息。
- CRF计算的是全局最优解，不是局部最优值。
- CRF是给定观察序列的条件下，计算整个标记序列的联合概率。而HMM是给定当前状态，计算下一个状态。
- CRF比较依赖特征的选择和特征函数的格式，并且训练计算量大
四、参考
- 《统计学习方法》,李航
- 条件随机场(码农场)
- 果壳中的条件随机场(CRF In A Nutshell)