条件随机场

条件随机场（conditional random field，CRF）是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔可夫随机场。

1. 定义

条件随机场是给定随机变量\(X\)条件下，随机变量\(Y\)的马尔可夫随机场。

条件随机场：设\(X\)和\(Y\)是随机变量，\(P(Y|X)\)是在给定\(X\)的条件下\(Y\)的条件概率分布。若随机变量\(Y\)构成一个由无向图\(G = (V,E)\)表示的马尔可夫随机场，即 \[P(Y_v|X,Y_w, w \neq v) = P(Y_v|X,Y_w,w \sim v)\] 对任意结点\(v\)成立，则称条件概率分布\(P(Y|X)\)为条件随机场。式中\(w \sim v\)表示在图\(G = (V,E)\)中与结点\(v\)有边连接的所有结点\(w\)，\(w \neq v\)表示结点\(v\)以外的所有结点，\(Y_v,Y_u\)与\(Y_w\)为结点\(v,u\)和\(w\)对应的随机变量。

定义中并没有要求\(X\)和\(Y\)具有相同的结构。现实中，一般假设\(X\)和\(Y\)有相同的图结构。此处主要考虑无向图为图11.4和图11.5所示的线性链的情况，即 \[G = (V = \{1,2,\cdots,n\}, \quad E = \{(i,i+1)\}), \quad i=1,2,\cdots,n-1\] 在此情况下，\(X=(X_1,X_2,\cdots,X_n), \quad Y=(Y_1,Y_2,\cdots,Y_n)\)，最大团是相邻两个结点的集合。

线性链条件随机场：设\(X=(X_1,X_2,\cdots,X_n), \quad Y=(Y_1,Y_2,\cdots,Y_n)\)均为线性链表示的随机变量序列，若在给定随机变量序列\(X\)的条件下，随机变量序列\(Y\)的条件概率分布\(P(Y|X)\)构成条件随机场，即满足马尔可夫性 \[\begin{equation} P(Y_i|X,Y_1,\cdots,Y_{i-1},Y_{i+1},\cdots,Y_n) = P(Y_i|X,Y_{i-1},Y_{i+1}) \nonumber \\ i = 1,2,\cdots,n(在i=1和n时只考虑单边) \nonumber \end{equation}\]

则称\(P(Y|X)\)为线性链条件随机场。在标注问题中，\(X\)表示输入观测序列，\(Y\)表示对应的输出标记序列或状态序列。

2. 参数化形式

线性链条件随机场的参数化形式：设\(P(Y|X)\)为线性链条件随机场，则在随机变量\(X\)取值为\(\pmb{x}\)的条件下，随机变量\(Y\)取值为\(y\)的条件概率具有如下形式： \[P(y|\pmb{x}) = \frac{1}{Z(\pmb{x})} \exp \left( \sum_{i,k} \lambda_k t_k (y_{i-1},y_i, \pmb{x}, i) + \sum_{i,l} \mu_l s_l (y_i, \pmb{x}, i) \right)\] 其中 \[Z(\pmb{x}) = \sum_y \exp \left( \sum_{i,k} \lambda_k t_k (y_{i-1},y_i, \pmb{x}, i) + \sum_{i,l} \mu_l s_l (y_i, \pmb{x}, i) \right)\] 式中，\(t_k\)和\(s_l\)是特征函数，\(\lambda_k\)和\(\mu_l\)是对应的权值。\(Z(x)\)是规范化因子，求和是在所有可能的输出序列上进行的。
上述公式是线性条件随机场模型的基本形式，表示给定输入序列\(\pmb{x}\)，对输出序列\(\pmb{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\)确定。

线性链条件随机场也是对数线性模型。

3. 简化形式

条件随机场还可以由简化形式表示。条件随机场中同一特征在各个位置都有定义，可以对同一特征在各个位置求和，将局部特征函数转化为一个全局特征函数，这样就可以将条件随机场写成权值向量和特征向量的内积形式，即条件随机场的简化形式。

首先将转移特征和状态特征及其权值用统一的符号表示。，设有\(K_1\)个转移特征，\(K_2\)个状态特征，\(K = K_1 + K_2\)，记 \[f_k(y_{i-1},y_i,\pmb{x},i) = \begin{cases} t_k(y_{i-1},y_i,\pmb{x},i), \quad k=1,2,\cdots,K_1 \\ s_l(y_i,\pmb{x},i), \quad k=K_1 + l;l=1,2,\cdots,K_2 \end{cases}\]

然后，对转移与状态特征在各个位置\(i\)求和，记作 \[f_k (\pmb{y},\pmb{x}) = \sum_{i=1}^n f_k(y_{i-1},y_i,\pmb{x},i), \quad k=1,2,\cdots,K\] 用\(w_k\)表示特征\(f_k (\pmb{y},\pmb{x})\)的权值，即 \[w_k = \begin{cases} \lambda_k, \quad k=1,2,\cdots,K_1 \\ \mu_l, \quad k=K_1 + l;l=1,2,\cdots,K_2 \end{cases}\] 于是，条件随机场可表示为 \[\begin{align} P(\pmb{y}|\pmb{x}) &= \frac{1}{Z(\pmb{x})} \exp \sum_{k=1}^K w_k f_k(\pmb{y},\pmb{x}) \tag{11.15} \\ Z(\pmb{x}) &= \sum_{\pmb{y}} \exp \sum_{k=1}^K w_k f_k(\pmb{y},\pmb{x}) \tag{11.16} \end{align}\]

若以\(\pmb{w}\)表示权值向量，即 \[\pmb{w} = (w_1,w_2,\cdots,w_K)^T\] 以\(F(\pmb{y},\pmb{x})\)表示全局特征向量，即 \[F(\pmb{y}, \pmb{x}) = (f_1(\pmb{y},\pmb{x}),f_2(\pmb{y},\pmb{x}),\cdots,f_K(\pmb{y},\pmb{x}))^T\] 则条件随机场可以写成向量\(\pmb{w}\)与\(F(\pmb{y},\pmb{x})\)的内积的形式： \[P_{\pmb{w}}(\pmb{y}|\pmb{x}) = \frac{\exp(\pmb{w} \cdot F(\pmb{y},\pmb{x}))}{Z_{\pmb{w}}(\pmb{x})}\] 其中 \[Z_{\pmb{w}}(\pmb{x}) = \sum_{\pmb{y}} \exp(\pmb{w} \cdot F(\pmb{y},\pmb{x}))\]

4. 矩阵形式

条件随机场还可以由矩阵表示。假设\(P_{\pmb{w}}(\pmb{y}|\pmb{x})\)是式（11.15）~（11.16）给出的线性链条件随机场，表示对给定观测序列\(\pmb{x}\)，相应的标记序列\(\pmb{y}\)的条件概率。引入特殊的起点和终点状态标记\(y_0 = start,\quad y_{n+1} = stop\)，这时\(P_{\pmb{w}}(\pmb{y}|\pmb{x})\)可以通过矩阵形式表示。

对观测序列\(\pmb{x}\)的每一个位置\(i=1,2,\cdots,n+1\)，定义一个\(m\)阶矩阵（\(m\)是标记\(y_i\)取值的个数）： \[\begin{equation} M_i(\pmb{x}) = [M_i(y_{i-1},y_i|\pmb{x})] \nonumber \\ M_i(y_{i-1},y_i|\pmb{x}) = \exp(W_i(y_{i-1},y_i|\pmb{x})) \nonumber \\ W_i(y_{i-1},y_i|\pmb{x}) = \sum_{k=1}^K w_k f_k (y_{i-1},y_i,\pmb{x},i) \nonumber \end{equation}\] 这样，给定观测序列\(\pmb{x}\)，相应的标记序列\(\pmb{y}\)的非规范化概率可以通过该序列\(n+1\)个矩阵适当元素的乘积\(\prod_{i=1}^{n+1} M_i(y_{i-1},y_i|\pmb{x})\)表示。于是，条件概率\(P_{\pmb{w}}(\pmb{y}|\pmb{x})\)是 \[P_{\pmb{w}}(\pmb{y}|\pmb{x}) = \frac{1}{Z_{\pmb{w}}(\pmb{x})} \prod_{i=1}^{n+1} M_i(y_{i-1},y_i|\pmb{x})\] 其中，\(Z_{\pmb{w}}(\pmb{x})\)为规范化因子，是\(n+1\)个矩阵的乘积的（start，stop）元素： \[Z_{\pmb{w}}(\pmb{x}) = (M_1(\pmb{x})M_2(\pmb{x})\cdots M_{n+1}(\pmb{x}))_{start,stop}\] 注意，\(y_0 = start\)与\(y_{n+1} = stop\)表示开始状态与终止状态，规范化因子\(Z_{\pmb{w}}(\pmb{x})\)是以start为起点stop为终点通过状态的所有路径\(y_1 y_2 \cdots y_n\)的非规范化概率\(\prod_{i=1}^{n+1} M_i(y_{i-1},y_i|\pmb{x})\)之和。

示例：

5. 概率计算问题

条件随机场的概率计算问题是给定条件随机场\(P(Y|X)\)，输入序列\(\pmb{x}\)和输出序列\(\pmb{y}\)，计算条件概率\(P(Y_i = y_i|\pmb{x})\)，\(P(Y_{i-1}=y_{i-1},Y_i = y_i|\pmb{x})\)以及相应的数学期望的问题。与HMM相类似，引入前向-后向向量，递归地计算以上概率及期望值，这样的算法称为前向-后向算法。

5.1. 前向-后向算法

对每个指标\(i=0,1,\cdots,n+1\)，定义前向向量\(\alpha_i(\pmb{x})\)： \[\alpha_0 (\pmb{y}|\pmb{x}) = \begin{cases} 1, \quad \pmb{y}=start \\ 0, \quad 否则 \end{cases}\]

递推公式为 \[\alpha_i^T (y_i|\pmb{x}) = \alpha_{i-1}^T(y_{i-1}|\pmb{x}) [M_i(y_{i-1},y_i|\pmb{x})], \quad i=1,2,\cdots,n+1\] 又可表示为 \[\alpha_i^T (\pmb{x}) = \alpha_{i-1}^T (\pmb{x}) M_i(\pmb{x})\] \(\alpha_i(y_i|\pmb{x})\)表示在位置\(i\)的标记是\(y_i\)并且到位置\(i\)的前部分标记序列的非规范化概率，\(y_i\)可取的值有\(m\)个，所以\(\alpha_i(\pmb{x})\)是\(m\)维列向量。

同样，对每个指标\(i=0,1,\cdots,n+1\)，定义后向向量\(\beta_i(\pmb{x})\)： \[\begin{equation} \beta_{n+1}(y_{n+1}|\pmb{x}) = \begin{cases} 1, \quad y_{n+1} = stop \\ 0, \quad 否则 \end{cases} \nonumber \\ \beta_i(y_i|\pmb{x}) = [M_i(y_i,y_{i+1}|\pmb{x})] \beta_{i+1} (y_{i+1}|\pmb{x}) \nonumber \end{equation}\]

又可表示为 \[\beta_i(\pmb{x}) = M_{i+1} (\pmb{x}) \beta_{i+1} (\pmb{x})\] \(\beta_i(y_i|\pmb{x})\)表示在位置\(i\)的标记为\(y_i\)并且从\(i+1\)到\(n\)的后部分标记序列的非规范化概率。

由前向-后向向量定义可以得到： \[Z(\pmb{x}) = \alpha_n^T (\pmb{x}) \cdot \pmb{1} = \pmb{1}^T \cdot \beta_1(\pmb{x})\] \(\pmb{1}\)是元素均为1的\(m\)维列向量。

5.2. 概率计算

按照前向-后向向量的定义，可以计算标记序列在位置\(i\)是标记\(y_i\)的条件概率和在位置\(i-1\)与\(i\)是标记\(y_{i-1}\)和\(y_i\)的条件概率： \[\begin{align} P(Y_i = y_i|\pmb{x}) &= \frac{\alpha_i^T (y_i|\pmb{x}) \beta_i(y_i|\pmb{x})}{Z(\pmb{x})} \nonumber \\ P(Y_{i-1} = y_{i-1},Y_i = y_i |\pmb{x}) &= \frac{\alpha_{i-1}^T (y_{i-1}|\pmb{x}) M_i(y_{i-1},y_i|\pmb{x}) \beta_i(y_i|\pmb{x})}{Z(\pmb{x})} \nonumber \end{align}\] 其中 \[Z(\pmb{x}) = \alpha_n^T (\pmb{x}) \cdot \pmb{1}\]

5.3. 期望值计算

利用前向-后向向量，可以计算特征函数关于联合分布\(P(X,Y)\)和条件分布\(P(Y|X)\)的数学期望。
特征函数\(f_k\)关于条件分布\(P(Y|X)\)的数学期望是 \[\begin{align} E_{P(Y|X)} [f_k] &= \sum_{\pmb{y}} P(\pmb{y}|\pmb{x}) f_k(\pmb{y},\pmb{x}) \nonumber \\ &= \sum_{i=1}^{n+1} \sum_{y_{i-1}y_i} f_k(y_{i-1},y_i,\pmb{x},i) \frac{\alpha_{i-1}^T (y_{i-1}|\pmb{x})M_i(y_{i-1},y_i|\pmb{x}) \beta_i(y_i|\pmb{x})}{Z(\pmb{x})} \nonumber \\ & \qquad k=1,2,\cdots,K \nonumber \end{align}\] 其中， \[Z(\pmb{x}) = \alpha_n^T (\pmb{x}) \cdot \pmb{1}\]

假设经验分布为\(\tilde{P}(X)\)，特征函数\(f_k\)关于联合分布\(P(X,Y)\)的数学期望是 \[\begin{align} E_{P(X,Y)} [f_k] &= \sum_{\pmb{x},\pmb{y}} P(\pmb{x},\pmb{y}) \sum_{i=1}^{n+1} f_k(y_{i-1},y_i,\pmb{x},i) \nonumber \\ &= \sum_{\pmb{x}} \tilde{P}(\pmb{x}) \sum_{\pmb{y}} P(\pmb{y}|\pmb{x}) \sum_{i=1}^{n+1} f_k(y_{i-1},y_i,\pmb{x},i) \nonumber \\ &= \sum_{\pmb{x}} \tilde{P}(\pmb{x}) \sum_{i=1}^{n+1} \sum_{y_{i-1}y_i} f_k(y_{i-1},y_i,\pmb{x},i) \frac{\alpha_{i-1}^T(y_{i-1}|\pmb{x})M_i(y_{i-1},y_i|\pmb{x}) \beta_i(y_i|\pmb{x})}{Z(\pmb{x})} \nonumber \\ & \qquad k=1,2,\cdots,K \nonumber \end{align}\] 其中 \[Z(\pmb{x}) = \alpha_n^T (\pmb{x}) \cdot \pmb{1}\] 上述两个公式是特征函数数学期望的一般计算公式。对于转移特征\(t_k(y_{i-1},y_i,\pmb{x},i), \quad k=1,2,\cdots,K_1\)，可以将式中的\(f_k\)换成\(t_k\)；对于状态特征，可以将式中的\(f_k\)换成\(s_l\)，表示为\(s_l(y_i,\pmb{x},i), \quad k=K_1 + l, \quad l=1,2,\cdots,K_2\)。
对于给定的观测序列\(\pmb{x}\)与标记序列\(\pmb{y}\)，可以通过以此前向扫描计算\(\alpha_i\)及\(Z(\pmb{x})\)，通过一次后向扫描计算\(\beta_i\)，从而计算所有的概率和特征的期望。

6. 学习算法

条件随机场模型实际上是定义在时序数据上的对数线性模型，其学习方法包括极大似然估计和正则化的极大似然估计。具体地优化实现算法有改进的迭代尺度法IIS、梯度下降法以及拟牛顿法。

6.1. 改进的迭代尺度法

已知训练数据集，由此可知经验概率分布\(\tilde{P}(X,Y)\)。可以通过极大化训练数据的对数似然函数来求模型参数。

训练数据的对数似然函数为 \[L(\pmb{w}) = L_{\tilde{P}}(P_{\pmb{w}}) = \log \prod_{\pmb{x},\pmb{y}} P_{\pmb{w}} (\pmb{y}|\pmb{x})^{\tilde{P}(\pmb{x},\pmb{y})} = \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x},\pmb{y}) \log P_{\pmb{w}} (\pmb{y}|\pmb{x})\] 当\(P_{\pmb{w}}\)是一个由式（11.15）和（11.16）给出的条件随机场模型时，对数似然函数为 \[\begin{align} L(\pmb{w}) &= \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x},\pmb{y})\log P_{\pmb{w}} (\pmb{y}|\pmb{x}) \nonumber \\ &= \sum_{\pmb{x},\pmb{y}} \left[ \tilde{P}(\pmb{x},\pmb{y}) \sum_{k=1}^K w_k f_k (\pmb{y},\pmb{x}) - \tilde{P}(\pmb{x},\pmb{y}) \log Z_{\pmb{w}} (\pmb{x}) \right] \nonumber \\ &= \sum_{j=1}^N \sum_{k=1}^K w_k f_k(\pmb{y}_j,\pmb{x}_j) - \sum_{j=1}^N \log Z_{\pmb{w}} (\pmb{x}_j) \nonumber \end{align}\]

改进的迭代尺度法通过迭代的方法不断优化对数似然函数改变量的下界，达到极大化对数似然函数的目的。假设模型的当前参数向量为\(\pmb{w} = (w_1,w_2,\cdots,w_K)^T\)，向量的增量为\(\pmb{\delta} = (\delta_1,\delta_2,\cdots,\delta_K)^T\)，更新参数向量为\(\pmb{w} + \pmb{\delta} = (w_1+\delta_1,w_2+\delta_2,\cdots,w_K+\delta_K)^T\)。在每步迭代过程中，改进的迭代尺度法通过依次求解下述两个公式，得到\(\pmb{\delta} = (\delta_1,\delta_2,\cdots,\delta_K)^T\)。

关于转移特征\(t_k\)的更新方程为 \[\begin{align} E_{\tilde{P}} [t_k] &= \sum_{\pmb{x},\pmb{y}} \tilde{P} (\pmb{x},\pmb{y}) \sum_{i=1}^{n+1} t_k(y_{i-1},y_i,\pmb{x},i) \nonumber \\ &= \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x}) P(\pmb{y}|\pmb{x}) \sum_{i=1}^{n+1} t_k(y_{i-1},y_i,\pmb{x},i) \exp(\delta_k T(\pmb{x},\pmb{y})) \nonumber \\ & \qquad k=1,2,\cdots,K_1 \tag{11.36} \end{align}\] 关于状态特征\(s_l\)的更新方程为 \[\begin{align} E_{\tilde{P}}[s_l] &= \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x},\pmb{y}) \sum_{i=1}^{n+1} s_l(y_i,\pmb{x},i) \nonumber \\ &= \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x})P(\pmb{y}|\pmb{x})\sum_{i=1}^n s_l(y_i,\pmb{x},i) \exp(\delta_{K_1+l} T(\pmb{x},\pmb{y})) \nonumber \\ & \qquad l=1,2,\cdots,K_2 \tag{11.37} \end{align}\] 式中\(T(\pmb{x},\pmb{y})\)是在数据\((\pmb{x},\pmb{y})\)中出现的所有特征数的总和： \[T(\pmb{x},\pmb{y}) = \sum_k f_k(\pmb{y},\pmb{x}) = \sum_{k=1}^K \sum_{i=1}^{n+1} f_k(y_{i-1},y_i,\pmb{x},i) \tag{11.38}\]

算法如下：

\(T(\pmb{x},\pmb{y})\)表示数据\((\pmb{x},\pmb{y})\)中的特征总数，对不同的数据\((\pmb{x},\pmb{y})\)取值可能不同。为了处理这个问题，定义松弛特征 \[s(\pmb{x},\pmb{y}) = S - \sum_{i=1}^{n+1} \sum_{k=1}^K f_k(y_{i-1},y_i,\pmb{x},i)\] 式中\(S\)是一个常数，选择足够大的常数\(S\)使得对训练数据集的所有数据\((\pmb{x},\pmb{y})\)，\(s(\pmb{x},\pmb{y}) \geqslant 0\)成立。这时特征总数可取\(S\)。

由式（11.36）,对于转移特征\(t_k\)，\(\delta_k\)的更新方程是 \[\begin{equation} \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x}) P(\pmb{y}|\pmb{x}) \sum_{i=1}^{n+1} t_k(y_{i-1},y_i,\pmb{x},i) \exp(\delta_k S) = E_{\tilde{p}}[t_k] \nonumber \\ \delta_k = \frac{1}{S} \log \frac{E_{\tilde{p}}[t_k]}{E_P[t_k]} \nonumber \end{equation}\]
其中， \[E_P(t_k) = \sum_{\pmb{x}} \tilde{P} (\pmb{x}) \sum_{i=1}^{n+1} \sum_{y_{i-1},y_i} t_k(y_{i-1},y_i,\pmb{x},i) \frac{\alpha_{i-1}^T (y_{i-1}|\pmb{x}) M_i(y_{i-1},y_i|\pmb{x}) \beta_i(y_i|\pmb{x})}{Z(\pmb{x})}\] 同样由式（11.37），对于状态特征\(s_l\)，\(\delta_k\)的更新方程是 \[\begin{equation} \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x}) P(\pmb{y}|\pmb{x}) \sum_{i=1}^n s_l (y_i,\pmb{x},i) \exp(\delta_{K_1+l}S) = E_{\tilde{P}}[s_l] \nonumber \\ \delta_{K_1+l} = \frac{1}{S} \log \frac{E_{\tilde{P}}[s_l]}{E_P[s_l]} \nonumber \end{equation}\] 其中， \[E_P(s_l) = \sum_{\pmb{x}} \tilde{P} (\pmb{x}) \sum_{i=1}^n \sum_{y_i} s_l (y_i,\pmb{x},i) \frac{\alpha_i^T (y_i|\pmb{x}) \beta_i (y_i|\pmb{x})}{Z(\pmb{x})}\]

以上算法称为算法S。在算法S中需要使常数S取足够大，这样一来，每步迭代的增量向量会变小，算法收敛会变慢。算法T试图解决这个问题。算法T对每个观测序列\(\pmb{x}\)计算其特征总数最大值\(T(\pmb{x})\)： \[T(\pmb{x}) = \max_{\pmb{y}} T(\pmb{x},\pmb{y})\] 利用前向-后向递推公式，可以很容易计算\(T(\pmb{x}) = t\)。
此时，关于转移特征参数的更新方程可以写成： \[\begin{align} E_{\tilde{P}} [t_k] &= \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x}) P(\pmb{y}|\pmb{x}) \sum_{i=1}^{n+1} t_k(y_{i-1},y_i,\pmb{x},i) \exp(\delta_k T(\pmb{x})) \nonumber \\ &= \sum_{\pmb{x}} \tilde{P}(\pmb{x}) \sum_{\pmb{y}} P(\pmb{y}|\pmb{x}) \sum_{i=1}^{n+1} t_k(y_{i-1},y_i,\pmb{x},i) \exp(\delta_k T(\pmb{x})) \nonumber \\ &= \sum_{\pmb{x}} \tilde{P} (\pmb{x}) a_{k,t} \exp(\delta_k \cdot t) \nonumber \\ &= \sum_{t=0}^{T_{max}} a_{k,t} \beta_k^t \nonumber \end{align}\] 式中，\(a_{k,t}\)是特征\(t_k\)的期望值，\(\delta_k = \log \beta_k\)。\(\beta_k\)是上述多项式方程唯一的实根，可以用牛顿法求得，从而求得相关的\(\delta_k\)。

同样，关于状态特征的函数更新方程可以写成： \[\begin{align} E_{\tilde{P}} [t_k] &= \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x}) P(\pmb{y}|\pmb{x}) \sum_{i=1}^{n+1} s_l(y_i,\pmb{x},i) \exp(\delta_{K_1+l} T(\pmb{x})) \nonumber \\ &= \sum_{\pmb{x}} \tilde{P}(\pmb{x}) \sum_{\pmb{y}} P(\pmb{y}|\pmb{x}) \sum_{i=1}^{n+1} s_l(y_i,\pmb{x},i) \exp(\delta_{K_1+l} T(\pmb{x})) \nonumber \\ &= \sum_{\pmb{x}} \tilde{P} (\pmb{x}) b_{l,t} \exp(\delta_k \cdot t) \nonumber \\ &= \sum_{t=0}^{T_{max}} b_{l,t} \gamma_l^t \nonumber \end{align}\]

上式中\(b_{l,t}\)是特征\(s_l\)的期望值，\(\delta_l = \log \gamma_l\)，\(\gamma_l\)是上述多项式方程唯一的实根，也可以用牛顿法求得。

6.2. 拟牛顿法

条件随机场模型学习还可以应用牛顿法或拟牛顿法。对于条件随机场模型 \[P_{\pmb{w}} (\pmb{y}|\pmb{x}) = \frac{\exp \left( \sum_{i=1}^n w_i f_i(\pmb{x},\pmb{y}) \right)}{\sum_{\pmb{y}} \exp \left( \sum_{i=1}^n w_i f_i(\pmb{x},\pmb{y}) \right)}\] 学习的优化目标函数是 \[\min_{\pmb{w} \in \mathbf{R}^n} f(\pmb{w}) = \sum_{\pmb{x}} \tilde{P}(\pmb{x}) \log \sum_{\pmb{y}} \exp \left( \sum_{i=1}^n w_i f_i(\pmb{x},\pmb{y}) \right) - \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x},\pmb{y}) \sum_{i=1}^n w_i f_i(\pmb{x},\pmb{y}) \] 其梯度函数是 \[g(\pmb{w}) = \sum_{\pmb{x},\pmb{y}} \tilde{P}(\pmb{x}) P_{\pmb{w}}(\pmb{y}|\pmb{x}) f(\pmb{x},\pmb{y}) - E_{\tilde{P}}(f)\]

BFGS算法如下：

7. 预测算法

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

由式\(P_{\pmb{w}}(\pmb{y}|\pmb{x}) = \frac{\exp(\pmb{w} \cdot F(\pmb{y},\pmb{x}))}{Z_{\pmb{w}}(\pmb{x})}\)可得： \[\begin{align} \pmb{y}^* &= \mathop{\arg \max}_{\pmb{y}} P_{\pmb{w}} (\pmb{y}|\pmb{x}) \nonumber \\ &= \mathop{\arg \max}_{\pmb{y}} \frac{\exp(\pmb{w} \cdot F(\pmb{y},\pmb{x}))}{Z_{\pmb{w}}(\pmb{x})} \nonumber \\ &= \mathop{\arg \max}_{\pmb{y}} \exp(\pmb{w} \cdot F(\pmb{y},\pmb{x})) \nonumber \\ &= \mathop{\arg \max}_{\pmb{y}} (\pmb{w} \cdot F(\pmb{y},\pmb{x})) \nonumber \end{align}\] 于是，条件随机场的预测问题称为非规范化概率最大的最优路径问题 \[\max_{\pmb{y}} \quad (\pmb{w} \cdot F(\pmb{y},\pmb{x})) \tag{11.52}\] 式中，路径表示标记序列，其中 \[\begin{equation} \pmb{w} = (w_1,w_2,\cdots,w_K)^T \nonumber \\ F(\pmb{y},\pmb{x}) = (f_1(\pmb{y},\pmb{x}),f_2(\pmb{y},\pmb{x}),\cdots,f_K(\pmb{y},\pmb{x}))^T \nonumber \\ f_k(\pmb{y},\pmb{x}) = \sum_{i=1}^n f_k(y_{i-1},y_i,\pmb{x},i), \quad k=1,2,\cdots,K \nonumber \end{equation}\]

注意，此时只需计算非规范化概率，不必计算准确的概率，这样可以大大提高效率。为了求解最优路径，将式（11.52）写成如下形式： \[\max_{\pmb{y}} \quad \sum_{i=1}^n \pmb{w} \cdot F_i(y_{i-1},y_i,\pmb{x})\] 其中 \[F_i(y_{i-1},y_i,\pmb{x}) = (f_1(y_{i-1},y_i,\pmb{x},i),f_2(y_{i-1},y_i,\pmb{x},i),\cdots,f_K(y_{i-1},y_i,\pmb{x},i))^T\] 是局部特征变量。

维特比算法：
首先求出位置1的各个标记\(j=1,2,\cdots,m\)的非规范化概率： \[\delta_1(j) = \pmb{w} \cdot F_1(y_0 = start, y_1= j,\pmb{x}), \quad j=1,2,\cdots,m\] 一般的，由递推公式，求出位置\(i\)的各个标记\(l=1,2,\cdots,m\)的非规范化概率的最大值，同时记录非规范化概率最大值的路径 \[\begin{equation} \delta_i(l) = \max_{1 \leqslant j \leqslant m} \{ \delta_{i-1}(j) + \pmb{w} \cdot F_i(y_{i-1}=j,y_i = l, \pmb{x}) \}, \quad l=1,2,\cdots,m \nonumber \\ \Psi(l) = \mathop{\arg \max}_{1 \leqslant j \leqslant m} \{ \delta_{i-1}(j) + \pmb{w} \cdot F_i(y_{i-1} = j, y_i = l, \pmb{x}) \}, \quad l=1,2,\cdots,m \nonumber \end{equation}\] 直到\(i=n\)时终止。这时求得非规范化概率的最大值为 \[\max_{\pmb{y}}(\pmb{w} \cdot F(\pmb{y},\pmb{x})) = \max_{1 \leqslant j \leqslant m} \delta_n(j)\] 即最优路径的终点 \[y_n^* = \mathop{\arg \max}_{1 \leqslant j \leqslant m} \delta_n(j)\] 由此最优路径终点返回， \[y_i^* = \Psi_{i+1} (y_{i+1}^*), \quad i = n-1,n-2,\cdots,1\] 求得最优路径\(\pmb{y}^* = (y_1^*,y_2^*,\cdots,y_n^*)^T\)。
综上得到条件随机场预测的维特比算法。