条件随机场（Conditional Random Field，CRF）

$$\begin{align} \end{align}$$

图是由结点及连接结点的编组成的集合。
结点记作$v$，结点集合记作$V$；边记作$e$，边的集合记作$E$；图记作$G=\left(V,E\right)$。

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

成对马尔可夫性
\begin{align} \\& P\left(Y_{u},Y_{v}|Y_{O}\right)=P\left(Y_{u}|Y_{O}\right)P\left(Y_{v}|Y_{O}\right)\end{align}
其中，设$u$和$v$是无向图$G$中任意两个没有边连接的结点，分别对应随机变量$Y_{u}$和$Y_{v}$；其它所有结点为$O$，对应的随机变量组是$Y_{O}$。
即，给定随机变量组$Y_{O}$的条件下随机变量$Y_{u}$和$Y_{v}$是条件独立的。

局部马尔可夫性
\begin{align} \\& P\left(Y_{v},Y_{O}|Y_{W}\right)=P\left(Y_{v}|Y_{W}\right)P\left(Y_{O}|Y_{W}\right)\end{align}
其中，设$v \in V$是无向图$G$中任意一个结点，对应的随机变量是$Y_{v}$。$W$是与$v$有边连接的所有的结点，对应的随机变量组是$Y_{W}$。$O$是$v,W$以外的其它所有结点，对应的随机变量组是$Y_{O}$。
即，给定随机变量组$Y_{W}$的条件下随机变量$Y_{v}$和$Y_{O}$是条件独立的。

全局马尔可夫性
\begin{align} \\& P\left(Y_{A},Y_{B}|Y_{C}\right)=P\left(Y_{A}|Y_{C}\right)P\left(Y_{B}|Y_{C}\right)\end{align}
其中，设结点集合$A,B$是在无向图$G$中被结点集合$C$分开的任意结点集合，对应的随机变量组是$Y_{A},Y_{B},Y_{C}$。
即，给定随机变量组$Y_{C}$的条件下随机变量$Y_{A}$和$Y_{B}$是条件独立的。

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

团：无向图$G$中任意两个结点均有边连接的结点子集。
最大团：无向图$G$中的一个团，并且不能再加进任何一个结点使其成为一个更大的团。

概率无向图模型的联合概率分布
\begin{align} \\& P\left(Y\right)=\dfrac{1}{Z} \prod_{C} \varPsi_{C}\left(Y_{C}\right) \end{align}
其中，$C$是无向图的最大团，$Y_{C}$是$C$的结点对应的随机变量；势函数$\varPsi_{C}\left(Y_{C}\right)$是严格正的
\begin{align} \\& \varPsi_{C}\left(Y_{C}\right) = \exp \left\{-E\left(Y_{C}\right)\right\} \end{align}
$Z$是规范化因子，保证$P\left(Y\right)$构成一个概率分布
\begin{align} \\& Z = \sum_{Y} \prod_{C} \varPsi_{C}\left(Y_{C} \right) \end{align}
乘积是在无向图所有的最大团上进行的。

设$X$与$Y$是随机变量，$P\left(Y|X\right)$是在给定$X$的条件下$Y$的条件概率分布，若随机变量$Y$构成一个由无向图$G=\left(V,E\right)$表示的马尔可夫随机场，即
\begin{align} \\& P\left(Y_{v}|X,Y_{w},w \neq v \right)= P\left(X,Y_{w},w \thicksim v \right)\end{align}
对任意结点$v$成立，则称条件概率分布$P\left(Y|X\right)$为条件随机场。其中，$w \thicksim v$表示在图$G=\left(V,E\right)$中与结点$v$有边连接的所有结点$w$，$w \neq v$表示结点$v$以外的所有结点，$Y_{v}$与$Y_{w}$为结点$v$与$w$对应的随机变量。

设$X=\left(X_{1},X_{2}, \cdots, X_{n}\right)$，$Y=\left(Y_{1},Y_{2}, \cdots, Y_{n}\right)$均为线性链表示的随机变量序列，若在给定随机变量序列$X$的条件下，随机变量序列$Y$的条件概率分布$P\left(Y|X\right)$构成条件随机场，即满足马尔可夫性
\begin{align} \\& P\left(Y_{i}|X,Y_{1},\cdots,Y_{i-1},Y_{i+1},\cdots,Y_{n} \right)= P\left(Y_{i}|X,Y_{i-1},Y_{i+1}\right)\end{align}
称条件概率分布$P\left(Y|X\right)$为线性链条件随机场。

线性链条件随机场的参数化形式
设$P\left(Y|X\right)$为线性链条件随机场，则在随机变量$X$取值为$x$的条件下，随机变量$Y$取值为$y$的条件概率
\begin{align} \\& P\left(y|x\right)= \dfrac{1}{Z\left(x\right)} \exp \left(\sum_{i,k} \lambda_{k} t_{k} \left(y_{i-1},y_{i},x,i\right)+\sum_{i,l} \mu_{l}s_{l} \left(y_{i},x,i\right) \right)\end{align}
其中，
\begin{align} \\& Z\left(x\right) = \sum_{y} \exp \left(\sum_{i,k} \lambda_{k} t_{k} \left(y_{i-1},y_{i},x,i\right)+\sum_{i,l} \mu_{l}s_{l} \left(y_{i},x,i\right) \right)\end{align}
$t_{k}$是定义在边上特征函数，称为转移特征，依赖于当前和前一个位置；$s_{l}$是定义在结点上的特征函数，称为状态特征，依赖于当前位置。特征函数$t_{k}$和$s_{l}$取值为1或0。$\lambda_{k}$和$\mu_{l}$是对应的权值，$Z\left(x\right)$是规范化因子，求和是在所有可能的输出序列上进行的。

线性链条件随机场的简化化形式
设有$K_{1}$个转移特征，$K_{2}$个状态特征，$K=K_{1}+K_{2}$，记
\begin{align} f_{k}\left(y_{i-1},y_{i},x,i\right) = \left\{
\begin{aligned}
\ & t_{k}\left(y_{i-1},y_{i},x,i\right), \quad k=1,2,\cdots,K_{1}
\\ & s_{l}\left(y_{i},x,i\right), \quad k=K_{1}+l; \quad l=1,2,\cdots,K_{2}
\end{aligned}
\right.\end{align}

转移与状态特征在各个位置$i$求和，记作
\begin{align} \\& f_{k} \left(y,x\right) = \sum_{i=1}^{n} f_{k}\left(y_{i-1},y_{i},x,i\right), \quad k=1,2, \cdots,K\end{align}

用$w_{k}$表示特征$f_{k}\left(y,x\right)$的权值，即
\begin{align} w_{k} = \left\{
\begin{aligned}
\ & \lambda_{k}, \quad k=1,2,\cdots,K_{1}
\\ & \mu_{l}, \quad k=K_{1}+l; \quad l=1,2,\cdots,K_{2}
\end{aligned}
\right.\end{align}

则条件随机场可表示为
\begin{align} \\& P\left(y|x\right)= \dfrac{1}{Z\left(x\right)} \exp \sum_{k=1}^{K} w_{k} f_{k}\left(y,x\right)
\\ & Z\left(x\right) = \sum_{y} \exp \sum_{k=1}^{K} w_{k} f_{k}\left(y,x\right) \end{align}

以$w$表示权值向量，即
\begin{align} \\& w=\left(w_{1},w_{2}, \cdots, w_{K}\right)^{T}\end{align}

以$F\left(y,x\right)$表示权局特征向量，即
\begin{align} \\& F\left(y,x\right) = \left(f_{1}\left(y,x\right),f_{2}\left(y,x\right), \cdots, f_{K}\left(y,x\right)\right)^{T} \end{align}

则条件随机场可写成向量$w$与$F\left(y,x\right)$的内积的形式
\begin{align} \\& P\left(y|x\right) = \dfrac{\exp \left(w \cdot F\left(y,x\right)\right)}{Z_{w}\left(x\right)} \end{align}
其中，
\begin{align} \\& Z_{w}\left(x\right) = \sum_{y} \exp \left(w \cdot F\left(y,x\right)\right) \end{align}

假设$P_{w}\left(y|x\right)$是线性链条件随机场对给定观测序列$x$，相应的标记序列$y$的条件概率。引进特殊的起点标记$y_{0}=start$表示开始状态，特殊的终点标记$y_{n+1}=stop$表示终止状态。对观测序列$x$的每一个位置$i=1,2,\cdots,n+1$，定义一个$m$阶矩阵（$m$是标记$y_{i}$取值的个数）
\begin{align} \\& M_{i}\left(x\right) = \left[ M_{i} \left(y_{i-1},y_{i}|x\right) \right]_{m \times m}
\\ & M_{i} \left(y_{i-1},y_{i}|x\right) = \exp \left(W_{i} \left(y_{i-1},y_{i},|x\right)\right)
\\ & W_{i} \left(y_{i-1},y_{i},|x\right) = \sum_{i=1}^{K} w_{k} f_{k} \left(y_{i-1},y_{i},x,i\right)\end{align}
则
\begin{align} \\& P_{w}\left(y|x\right) = \dfrac{1}{Z_{w}\left(x\right)} \prod_{i=1}^{n+1} M_{i} \left(y_{i-1},y_{i}|x\right)\end{align}
其中，$Z_{w}$为规范化因子，是$n+1$个矩阵的乘积的元素，是以$start$为起点$stop$为终点通过状态的所有路径$y_{1}y_{2}\cdots y_{n}$的非规范化概率$\prod_{i=1}^{n+1} M_{i} \left(y_{i-1},y_{i}|x\right)$之和。
\begin{align} \\& Z_{w}\left(x\right) = \left(M_{1}\left(x\right),M_{2}\left(x\right), \cdots,M_{n+1}\left(x\right)\right)_{start,stop}\end{align}

对每个指标$i=0,1,\cdots,n+1$，定义前向向量$\alpha_{i}\left(x\right)$
\begin{align} \alpha_{0}\left(y|x\right) = \left\{
\begin{aligned}
\ & 1, \quad y=start
\\ & 0, \quad 否则
\end{aligned}
\right.\end{align}
递推公式
\begin{align} \\& \alpha_{i}^{T}\left(y_{i}|x\right) = \alpha_{i-1}^{T}\left(y_{i}|x\right) \left[M_{i}\left(y_{i-1},y_{i}|x\right)\right], \quad i=1,2,\cdots,n+1\end{align}
又表示为
\begin{align} \\& \alpha_{i}^{T} \left(x\right) = \alpha_{i-1}^{T} \left(x\right) M_{i}\left(x\right)\end{align}
$\alpha_{i}\left(y_{i}|x\right)$表示在位置$i$的标记是$y_{i}$并且到位置$i$的前部分标记序列的非规范化概率，$y_{i}$可取的值又$m$个，所以$\alpha_{i}\left(x\right)$是$m$维列向量。

对每个指标$i=0,1,\cdots,n+1$，定义后向向量$\beta_{i}\left(x\right)$
\begin{align} \beta_{n+1}\left(y_{n+1}|x\right) = \left\{
\begin{aligned}
\ & 1, \quad y_{n+1}=stop
\\ & 0, \quad 否则
\end{aligned}
\right.\end{align}
递推公式
\begin{align} \\& \beta_{i}\left(y_{i}|x\right) = \left[M_{i}\left(y_{i},y_{i+1}|x\right)\right]\beta_{i+1}\left(y_{i+1}|x\right) , \quad i=1,2,\cdots,n+1\end{align}
又表示为
\begin{align} \\& \beta_{i} \left(x\right) = M_{i+1}\left(x\right) \beta_{i+1} \left(x\right) \end{align}
$\beta_{i}\left(y_{i}|x\right)$表示在位置$i$的标记是$y_{i}$并且到位置$i+1$到$n$的后部分标记序列的非规范化概率。

由前向－后向向量，得
\begin{align} \\& Z\left(x\right)=\alpha_{n}^{T}\left(x\right) \cdot \mathbf{1} = \mathbf{1}^{T} \cdot \beta_{i}\left(x\right) \end{align}
其中，$\mathbf{1}$是元素均为1的$m$维列向量。

标记序列中，在位置$i$是标记$y_{i}$的条件概率
\begin{align} \\& P\left(Y_{i}=y_{i}|x\right) = \dfrac{\alpha_{i}^{T}\left(y_{i}|x\right) \beta_{i}\left(y_{i}|x\right)}{Z\left(x\right)}\end{align}

标记序列中，在位置$i－1$是标记$y_{i-1}$，在位置$i$是标记$y_{i}$的条件概率
\begin{align} \\& P\left(Y_{i－1}=y_{i-1},Y_{i}=y_{i}|x\right) = \dfrac{\alpha_{i-1}^{T}\left(y_{i-1}|x\right) M_{i}\left(y_{i-1},y_{i}|x\right)\beta_{i}\left(y_{i}|x\right)}{Z\left(x\right)}\end{align}

其中，
\begin{align} \\& Z\left(x\right)=\alpha_{n}^{T}\left(x\right) \cdot \mathbf{1} \end{align}

特征函数$f_{k}$关于条件分布$P\left(Y|X\right)$的数学期望
\begin{align} \\& E_{P\left(Y|X\right)} \left[f_{k}\right]=\sum_{y} P\left(y|x\right) f_{k}\left(y,x\right)
\\ & = \sum_{i=1}^{n+1} \sum_{y_{i-1},y_{i}} f_{k}\left(y_{i-1},y_{i},x,i\right) \dfrac{\alpha_{i-1}^{T}\left(y_{i-1}|x\right) M_{i}\left(y_{i-1},y_{i}|x\right)\beta_{i}\left(y_{i}|x\right)}{Z\left(x\right)}\end{align}

假设经验分布为$\tilde{P}\left(x\right)$，特征函数$f_{k}$关于联合分布$P\left(X,Y\right)$的数学期望
\begin{align} \\& E_{P\left(X,Y\right)} \left[f_{k}\right]=\sum_{x,y} P\left(x,y\right) \sum_{i=1}^{n+1} f_{k}\left(y_{i-1},y_{i},x,i\right)
\\ & = \sum_{x} \tilde{P}\left(x\right) \sum_{y} P\left(y|x\right) \sum_{i=1}^{n+1} f_{k}\left(y_{i-1},y_{i},x,i\right)
\\ & = \sum_{x} \tilde{P}\left(x\right) \sum_{i=1}^{n+1} \sum_{y_{i-1},y_{i}} f_{k}\left(y_{i-1},y_{i},x,i\right) \dfrac{\alpha_{i-1}^{T}\left(y_{i-1}|x\right) M_{i}\left(y_{i-1},y_{i}|x\right)\beta_{i}\left(y_{i}|x\right)}{Z\left(x\right)} \quad \quad k=1,2,\cdots,K
\end{align}

其中，
\begin{align} \\& Z\left(x\right)=\alpha_{n}^{T}\left(x\right) \cdot \mathbf{1} \end{align}

由训练数据集，得经验概率分布$\tilde{P}\left(X,Y\right)$。
训练数据的对数似然函数
\begin{align} \\& L\left(w\right)= L_{\tilde{P}}\left(P_{w}\right)=\log \prod_{x,y} P_{w}\left(y|x\right)^{\tilde{P}\left(x,y\right)} = \sum_{x,y} \tilde{P}\left(x,y\right) \log P_{w}\left(y|x\right)\end{align}

当$P_{w}$是条件随机场模型时，对数似然函数
\begin{align} \\& L\left(w\right)= \sum_{x,y} \tilde{P}\left(x,y\right) \log P_{w}\left(y|x\right)
\\ & = \sum_{x,y} \left[\tilde{P}\left(x,y\right) \sum_{k=1}^{K} w_{k} f_{k}\left(y,x\right) - \tilde{P}\left(x,y\right) \log Z_{w}\left(x\right) \right]
\\ & = \sum_{j=1}^{N} \sum_{k=1}^{K} w_{k} f_{k} \left(y_{j},x_{j}\right) - \sum_{j=1}^{N} \log Z_{w} \left(x_{j}\right) \end{align}

设模型当前参数向量
\begin{align} \\& w = \left(w_{1},w_{2},\cdots,w_{K}\right)^{T}\end{align}
向量的增量
\begin{align} \\& \delta = \left(\delta_{1},\delta_{2},\cdots,\delta_{K}\right)^{T}\end{align}
更新参数向量
\begin{align} \\& w+\delta = \left(w_{1}+\delta_{1},w_{2}+\delta_{2},\cdots,w_{K}+\delta_{K}\right)^{T}\end{align}

关于转移特征$t_{k}$的更新方程
\begin{align} \\& E_{\tilde{P}} \left[t_{k}\right]=\sum_{x,y} \tilde{P} \left(x,y\right) \sum_{i=1}^{n+1} t_{k}\left(y_{i-1},y_{i},x,i\right)
\\ & = \sum_{x,y} \tilde{P} \left(x\right) P\left(y|x\right) \sum_{i=1}^{n+1} t_{k}\left(y_{i-1},y_{i},x,i\right)\exp\left(\delta_{k}T\left(x,y\right)\right) \quad \quad k=1,2,\cdots,K
\end{align}

关于转移特征$s_{l}$的更新方程
\begin{align} \\& E_{\tilde{P}} \left[s_{l}\right]=\sum_{x,y} \tilde{P} \left(x,y\right) \sum_{i=1}^{n} s_{l}\left(y_{i},x,i\right)
\\ & = \sum_{x,y} \tilde{P} \left(x\right) P\left(y|x\right) \sum_{i=1}^{n} s_{l}\left(y_{i},x,i\right)\exp\left(\delta_{K_{1}+l}T\left(x,y\right)\right) \quad \quad l=1,2,\cdots,K_{2}
\end{align}

其中，$T\left(x,y\right)$是在数据$\left(x,y\right)$中出现的所有特征函数的总和
\begin{align} \\& T\left(x,y\right)=\sum_{k} f_{k}\left(y,x\right)=\sum_{k=1}^{K} \sum_{i=1}^{n+1} f_{k} \left(y_{i-1},y_{i},x,i\right)\end{align}

条件随机场模型学习的改进的迭代尺度法：
输入：特征函数$t_{1},t_{2},\cdots,t_{K_{1}}$，$s_{1},s_{2},\cdots,s_{K_{2}}$，经验分布$\tilde{P}\left(x,y\right)$
输出：参数估计值$\hat{w}\quad$ 模型$P_{\hat{w}}$

1. 对所有$k \in \left\{1,2,\cdots,K\right\}$，取初值$w_{k}=0$
2. 对每一个$k \in \left\{1,2,\cdots,K\right\}$
   2.1当$k=1,2,\cdots,K_{1}$时，令$\delta_{k}$是方程
   \begin{align} \\& \sum_{x,y} \tilde{P} \left(x\right) P\left(y|x\right) \sum_{i=1}^{n+1} t_{k}\left(y_{i-1},y_{i},x,i\right)\exp\left(\delta_{k}T\left(x,y\right)\right)=E_{\tilde{P}} \left[t_{k}\right]
   \end{align}
   的解
   当$k=K_{1}+l,l=1,2,\cdots,K_{2}$时，令$\delta_{K_{1}+l}$是方程
   \begin{align} \\& \sum_{x,y} \tilde{P} \left(x\right) P\left(y|x\right) \sum_{i=1}^{n} s_{l}\left(y_{i},x,i\right)\exp\left(\delta_{K_{1}+l}T\left(x,y\right)\right)=E_{\tilde{P}} \left[s_{l}\right]
   \end{align}
   的解
   2.2更新$w_{k}$的值：$w_{k} \leftarrow w_{k}+\delta_{k}$
3. 如果不是所有的$w_{k}$都收敛，重复步骤2.
   其中，
   \begin{align} \\& T\left(x,y\right)=\sum_{k} f_{k}\left(y,x\right)=\sum_{k=1}^{K} \sum_{i=1}^{n+1} f_{k} \left(y_{i-1},y_{i},x,i\right)\end{align}

算法$S$是解决$T\left(x,y\right)$表示数据$\left(x,y\right)$中特征总数时，对不同数据$\left(x,y\right)$取值可能不同的问题。引入松弛特征
\begin{align} \\& s\left(x,y\right) = S - \sum_{i=1}^{n+1} \sum_{k=1}^{K} f_{k} \left(y_{i-1},y_{i},x,i\right)\end{align}
其中，$S$是一个常数。选取足够大的常数$S$使得对训练数据集的所有数据$\left(x,y\right)$，$s\left(x,y\right) \geq 0$成立。这时特征总数可取$S$。

对转移特征$t_{k}$，$\delta_{k}$的更新方程
\begin{align} \\& \sum_{x,y} \tilde{P} \left(x\right) P\left(y|x\right) \sum_{i=1}^{n+1} t_{k}\left(y_{i-1},y_{i},x,i\right)\exp\left(\delta_{k}S\right)=E_{\tilde{P}} \left[t_{k}\right]
\\ & \delta_{k}=\dfrac{1}{S} \log \dfrac{E_{\tilde{P}}\left[t_{k}\right]}{E_{P}\left[t_{k}\right]}\end{align}
其中，
\begin{align} \\& E_{P} \left[t_{k}\right]=\sum_{x} \tilde{P}\left(x\right) \sum_{i=1}^{n+1} \sum_{y_{i-1},y_{i}} t_{k}\left(y_{i-1},y_{i},x,i\right) \dfrac{\alpha_{i-1}^{T}\left(y_{i-1}|x\right) M_{i}\left(y_{i-1},y_{i}|x\right)\beta_{i}\left(y_{i}|x\right)}{Z\left(x\right)}
\end{align}

对状态特征$s_{l}$，$\delta_{k}$的更新方程
\begin{align} \\& \sum_{x,y} \tilde{P} \left(x\right) P\left(y|x\right) \sum_{i=1}^{n} s_{l}\left(y_{i},x,i\right)\exp\left(\delta_{K_{1}}S\right)=E_{\tilde{P}} \left[s_{l}\right]
\\ & \delta_{K_{1}+l}=\dfrac{1}{S} \log \dfrac{E_{\tilde{P}}\left[s_{l}\right]}{E_{P}\left[s_{l}\right]}\end{align}
其中，
\begin{align} \\& E_{P} \left[s_{l}\right]=\sum_{x} \tilde{P}\left(x\right) \sum_{i=1}^{n} \sum_{y_{i-1},y_{i}} s_{l}\left(y_{i},x,i\right) \dfrac{\alpha_{i}^{T}\left(y_{i-1}|x\right) \beta_{i}\left(y_{i}|x\right)}{Z\left(x\right)}
\end{align}

算法$T$是解决算法$S$每步迭代增量向量变大，算法收敛变慢问题。对每个观测序列$x$计算其特征总数最大值$T\left(x\right)$
\begin{align} \\& T\left(x\right) = \max_{y} T\left(x,y\right)=t\end{align}

关于转移特征参数的更新方程
\begin{align} \\& E_{\tilde{P}} \left[t_{k}\right]=\sum_{x,y} \tilde{P} \left(x\right) P\left(y|x\right) \sum_{i=1}^{n+1} t_{k}\left(y_{i-1},y_{i},x,i\right)\exp\left(\delta_{k}T\left(x,y\right)\right)
\\ & = \sum_{x} \tilde{P} \left(x\right) \sum_{y} P\left(y|x\right) \sum_{i=1}^{n+1} t_{k}\left(y_{i-1},y_{i},x,i\right)\exp\left(\delta_{k}T\left(x,y\right)\right)
\\ & = \sum_{x} \tilde{P}\left(x\right) a_{k,t} \exp\left(\delta_k \cdot t\right)
\\ & = \sum_{t=0}^{T_{max}} a_{k,t} \beta_{k}^{t}
\end{align}
其中，$a_{k,t}$是特征$t_{k}$的期望，$\delta_{k}=\log \beta_{k}$，$\beta_{k}$是多项式方程唯一的实根，可以用牛顿法求得，从而得$\delta_{k}$。

关于状态特征的参数更新方程
\begin{align} \\& E_{\tilde{P}} \left[s_{l}\right]= \sum_{x,y} \tilde{P} \left(x\right) P\left(y|x\right) \sum_{i=1}^{n} s_{l}\left(y_{i},x,i\right)\exp\left(\delta_{K_{1}+l}T\left(x,y\right)\right)
\\ & = \sum_{x} \tilde{P} \left(x\right) \sum_{y} P\left(y|x\right) \sum_{i=1}^{n} s_{l}\left(y_{i},x,i\right)\exp\left(\delta_{K_{1}+l}T\left(x,y\right)\right)
\\ & = \sum_{x} \tilde{P} \left(x\right) b_{l,t} \exp \left(\delta_{k} \cdot t\right)
\\ & = \sum_{t=0}^{T_{max}} b_{l,t} \gamma_{l}^{t}
\end{align}
其中，$b_{l,t}$是特征$s_{l}$的期望，$\delta_{l}=\log \gamma_{l}$，$\gamma_{l}$是多项式方程唯一的实根，可以用牛顿法求得。

条件随机场的预测问题是给定条件随机场$P\left(Y|X\right)$和输入序列（观测序列）$x$，求条件概率最大的输出序列（标记序列）$y^{*}$，即对观测序列进行标注。
即，

$$\begin{align} y^{*}&=\arg\max_{y}P_{w}\left(y|x\right) \\ & = \arg\max_{y} \dfrac{\exp \left(w \cdot F\left(y,x\right)\right)}{Z_{w}\left(x\right)} \\ & = \arg\max_{y} \exp \left(w \cdot F\left(y,x\right)\right) \\ & = \arg\max_{y} \left(w \cdot F\left(y,x\right)\right) \end{align}$$

其中，
\begin{align} w &=\left(w_{1},w_{2},\cdots,w_{K}\right)^{T}
\\ F\left(y,x\right)&=\left(f_{1}\left(y,x\right),f_{2}\left(y,x\right),\cdots,f_{K}\left(y,x\right)\right)^{T}
\\ f_{k}\left(y,x\right)&=\sum_{i=1}^{n} f_{k} \left(y_{i-1},y_{i},x,i\right),\quad \quad k=1,2,\cdots,K
\end{align}
等价的
\begin{align} \\& \max_{y} \sum_{i=1}^{n} w \cdot F_{i} \left(y_{i-1},y_{i},x\right)\end{align}
其中，
\begin{align} \\& F_{i}\left(y_{i-1},y_{i},x\right) = \left(f_{1}\left(y_{i-1},y_{i},x,i\right),f_{2}\left(y_{i-1},y_{i},x,i\right),\cdots,f_{K}\left(y_{i-1},y_{i},x,i\right)\right)^{T}\end{align}

条件随机场预测的维特比算法：
输入：模型特征函数$F\left(y,x\right)$和权值向量$w$，观测序列$x=\left(x_{1},x_{2},\cdots,x_{n}\right)$
输出：最优序列$y^{}=\left(y_{1}^{},y_{2}^{},\cdots,y_{n}^{}\right)$

1. 初始化
   \begin{align} \\& \delta_{1}\left(j\right)=w \cdot F_{1}\left(y_{0}=start,y_{1}=j,x\right),\quad j=1,2,\cdots,m\end{align}
2. 递推，对$i=2,3,\cdots,n$
   \begin{align} \\& \delta_{i}\left(l\right)=\max_{1 \leq j \leq m}\left\{\delta_{i-1}\left(j\right)+w \cdot F_{i}\left(y_{i-1}=j,y_{i}=l,x\right)\right\},\quad l=1,2,\cdots,m
   \\ & \varPsi_{i}\left(l\right) = \arg \max_{1 \leq j \leq m}\left\{\delta_{i-1}\left(j\right)+w \cdot F_{i}\left(y_{i-1}=j,y_{i}=l,x\right)\right\},\quad l=1,2,\cdots,m\end{align}
3. 终止
   \begin{align} \\& \max_{y} \left(w \cdot F\left(y,x\right)\right)=\max_{1 \leq j \leq m} \delta_{n}\left(j\right)
   \\ & y_{n}^{*}=\arg \max_{1 \leq j \leq m}\delta_{n}\left(j\right) \end{align}
4. 返回路径 $$y_{i}^{*}=\varPsi_{i+1}\left(y_{i+1}^{*}\right),\quad i=n-1,n-2,\cdots,1$$ 最优路径 $$y_{i}^{*}=\left(y_{1}^{*},y_{2}^{*},\cdots,y_{n}^{*}\right)$$