Question

1. 生成式概率图模型是直接对联合分布进行建模，如隐马尔可夫模型和马尔可夫随机场都是生成式模型。

   判别式概率图模型是对条件分布进行建模，如条件随机场Conditional Random Field:CRF。

2. 条件随机场试图对多个随机变量（它们代表标记序列）在给定观测序列的值之后的条件概率进行建模：

   令 $ MathJax-Element-280 $ 为观测变量序列， $ MathJax-Element-352 $ 为对应的标记变量序列。条件随机场的目标是构建条件概率模型 $ MathJax-Element-267 $ 。

   即：已知观测变量序列的条件下，标记序列发生的概率。

3. 标记随机变量序列 $ MathJax-Element-621 $ 的成员之间可能具有某种结构：

   • 在自然语言处理的词性标注任务中，观测数据为单词序列，标记为对应的词性序列（即动词、名词等词性的序列），标记序列具有线性的序列结构。
   • 在自然语言处理的语法分析任务中，观测数据为单词序列，标记序列是语法树，标记序列具有树形结构。

4. 令 $ MathJax-Element-269 $ 表示与观测变量序列 $ MathJax-Element-670 $ 和标记变量序列 $ MathJax-Element-621 $ 对应的无向图， $ MathJax-Element-277 $ 表示与结点 $ MathJax-Element-275 $ 对应的标记随机变量， $ MathJax-Element-274 $ 表示结点 $ MathJax-Element-275 $ 的邻接结点集。若图 $ MathJax-Element-279 $ 中结点对应的每个变量 $ MathJax-Element-277 $ 都满足马尔可夫性，即：

   $ P(Y_v\mid \mathbf X,\mathbf Y_{\mathbb V-\{v\}})=P(Y_v \mid \mathbf X,Y_{n(v)}) $

   则 $ MathJax-Element-278 $ 构成了一个条件随机场。

4.1 链式条件随机场

1. 理论上讲，图 $ MathJax-Element-279 $ 可以具有任意结构，只要能表示标记变量之间的条件独立性关系即可。

   但在现实应用中，尤其是对标记序列建模时，最常用的是链式结构，即链式条件随机场chain-structured CRF。

   如果没有特殊说明，这里讨论是基于链式条件随机场。

   

2. 给定观测变量序列 $ MathJax-Element-280 $ ，链式条件随机场主要包含两种关于标记变量的团：

   • 单个标记变量与 $ MathJax-Element-670 $ 构成的团： $ MathJax-Element-282 $ 。
   • 相邻标记变量与 $ MathJax-Element-670 $ 构成的团： $ MathJax-Element-284 $ 。

3. 与马尔可夫随机场定义联合概率的方式类似，条件随机场使用势函数和团来定义条件概率 $ MathJax-Element-615 $ 。

   采用指数势函数，并引入特征函数feature function，定义条件概率：

   $ P(\mathbf Y\mid \mathbf X)=\frac 1Z \exp\left(\sum_{j=1}^{K_1}\sum_{i=1}^{n-1}\lambda_jt_j(Y_i,Y_{i+1},\mathbf X,i)+\sum_{k=1}^{K_2}\sum_{i=1}^{n}\mu_ks_k(Y_i,\mathbf X,i)\right) $

   其中：

   • $ MathJax-Element-286 $ ：在已知观测序列情况下，两个相邻标记位置上的转移特征函数transition feature function。

     • 它刻画了相邻标记变量之间的相关关系，以及观察序列 $ MathJax-Element-670 $ 对它们的影响。
     • 位置变量 $ MathJax-Element-673 $ 也对势函数有影响。比如：已知观测序列情况下，相邻标记取值(代词，动词)出现在序列头部可能性较高，而(动词，代词)出现在序列头部的可能性较低。

   • $ MathJax-Element-289 $ ：在已知观察序列情况下，标记位置 $ MathJax-Element-673 $ 上的状态特征函数status feature function。

     • 它刻画了观测序列 $ MathJax-Element-670 $ 对于标记变量的影响。
     • 位置变量 $ MathJax-Element-673 $ 也对势函数有影响。比如：已知观测序列情况下，标记取值 名词出现在序列头部可能性较高，而 动词 出现在序列头部的可能性较低。

   • $ MathJax-Element-293 $ 为参数， $ MathJax-Element-620 $ 为规范化因子（它用于确保上式满足概率的定义）。

     $ MathJax-Element-305 $ 为转移特征函数的个数， $ MathJax-Element-306 $ 为状态特征函数的个数。

4. 特征函数通常是实值函数，用来刻画数据的一些很可能成立或者预期成立的经验特性。

   一个特征函数的例子（词性标注）：

   $ t_j(Y_i,Y_{i+1},\mathbf X,i)=\begin{cases} 1,& \text{if} \quad Y_{i+1}=\text{[P]},\;Y_i=\text{[V]} \;\text{and}\; X_i=\text{"knock"}\\ 0,& \text{otherwise} \end{cases}\\ s_k(Y_i,\mathbf X,i)=\begin{cases} 1,& \text{if} \quad Y_i=\text{[V]} \;\text{and}\; X_i=\text{"knock"}\\ 0,& \text{otherwise} \end{cases} $
   • 转移特征函数刻画的是：第 $ MathJax-Element-673 $ 个观测值 $ MathJax-Element-302 $ 为单词 "knock" 时，相应的标记 $ MathJax-Element-672 $ 和 $ MathJax-Element-405 $ 很可能分别为 [V]和[P] 。
   • 状态特征函数刻画的是： 第 $ MathJax-Element-673 $ 个观测值 $ MathJax-Element-302 $ 为单词 "knock" 时，标记 $ MathJax-Element-672 $ 很可能为 [V] 。

5. 条件随机场与马尔可夫随机场均使用团上的势函数定义概率，二者在形式上没有显著区别。

   条件随机场处理的是条件概率，马尔可夫随机场处理的是联合概率。

6. $ MathJax-Element-615 $ 的形式类似于逻辑回归。事实上，条件随机场是逻辑回归的序列化版本。

   • 逻辑回归是用于分类问题的对数线性模型。
   • 条件随机场是用于序列化标注的对数线性模型。

4.1.1 CRF 的简化形式

1. 注意到条件随机场中的同一个特征函数在各个位置都有定义，因此可以对同一个特征在各个位置求和，将局部特征函数转化为一个全局特征函数。

   这样就可以将条件随机场写成权值向量和特征向量的内积形式，即条件随机场的简化形式。

2. 设有 $ MathJax-Element-305 $ 个转移特征函数， $ MathJax-Element-306 $ 个状态特征函数。令 $ MathJax-Element-307 $ ，定义：

   $ f_k(Y_i,Y_{i+1},\mathbf X,i)=\begin{cases} t_k(Y_i,Y_{i+1},\mathbf X,i),&k=1,2,\cdots,K_1\\ s_l(Y_i,\mathbf X,i),&k=K_1+l;l=1,2,\cdots,K_2 \end{cases} $

   注意： $ MathJax-Element-308 $ 要求 $ MathJax-Element-309 $ ， 而 $ MathJax-Element-310 $ 要求 $ MathJax-Element-311 $ ，因此对于边界条件要特殊处理。

   对转移与状态函数在各个位置 $ MathJax-Element-673 $ 求和，记作：

   $ f_k(\mathbf Y,\mathbf X)=\sum_{i=1}^{n} f_k(Y_i,Y_{i+1},\mathbf X,i),\quad k=1,2,\cdots,K $

   其中 $ MathJax-Element-352 $ 为标记变量序列， $ MathJax-Element-314 $ 为观测变量序列。

   该式子刻画的是特征函数在所有位置上的和，可以理解为特征函数在所有位置上的得的总分。

3. 用 $ MathJax-Element-585 $ 表示特征 $ MathJax-Element-438 $ 的权值，即：

   $ w_k=\begin{cases} \lambda_k,&k=1,2,\cdots,K_1\\ \mu_l,&k=K_1+l;l=1,2,\cdots,K_2 \end{cases} $

   则条件随机场可以简化为：

   $ P(\mathbf Y\mid \mathbf X)=\frac 1Z \exp\left(\sum_{j=1}^{K_1}\sum_{i=1}^{n-1}\lambda_jt_j(Y_i,Y_{i+1},\mathbf X,i)+\sum_{k=1}^{K_2}\sum_{i=1}^{n}\mu_ks_k(Y_i,\mathbf X,i)\right) \\ = \frac 1Z \exp\left(\sum_{k=1}^{K_1}\lambda_k\sum_{i=1}^{n-1}t_k(Y_i,Y_{i+1},\mathbf X,i)+\sum_{l=1}^{K_2}\mu_l\sum_{i=1}^{n}s_l(Y_i,\mathbf X,i)\right)\\ = \frac 1Z\exp\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right) $

   其中 $ MathJax-Element-466 $ ， $ MathJax-Element-500 $ 表示对所有可能的标记序列进行求和。

4. 定义权值向量为 $ MathJax-Element-495 $ ，定义全局特征向量为：

   $ \mathbf {\vec F}(\mathbf Y,\mathbf X)=(f_1(\mathbf Y,\mathbf X),f_2(\mathbf Y,\mathbf X),\cdots,f_K(\mathbf Y,\mathbf X))^{T} $

   则条件随机场可以简化为：

   $ P(\mathbf Y\mid \mathbf X)= \frac 1Z\exp\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right)=\frac 1Z \exp\left(\mathbf{\vec w}\cdot \mathbf {\vec F}(\mathbf Y,\mathbf X) \right) $

   其中 $ MathJax-Element-619 $ ， $ MathJax-Element-500 $ 表示对所有可能的标记序列进行求和。

   $ MathJax-Element-322 $ 的物理意义为：已知序列 $ MathJax-Element-670 $ 的条件下，标记序列为 $ MathJax-Element-621 $ 的未归一化的概率。它就是每个特征函数的总分的加权和（权重为特征函数的权重）。

4.1.2 CRF 的矩阵形式

1. 假设标记变量 $ MathJax-Element-325 $ 的取值集合为 $ MathJax-Element-326 $ ， 其中 $ MathJax-Element-644 $ 是标记的取值个数。

   对于观测变量序列和标记变量序列的每个位置 $ MathJax-Element-328 $ ，定义一个 $ MathJax-Element-644 $ 阶矩阵：

   $ \mathbf M_i(\mathbf X)=\begin{bmatrix} M_i( \tilde{ \mathbf y}_1, \tilde{ \mathbf y}_1\mid\mathbf X) &M_i( \tilde{ \mathbf y}_1, \tilde{ \mathbf y}_2\mid\mathbf X)&\cdots&M_i( \tilde{ \mathbf y}_1, \tilde{ \mathbf y}_m\mid\mathbf X)\\ M_i( \tilde{ \mathbf y}_2, \tilde{ \mathbf y}_1\mid\mathbf X) &M_i( \tilde{ \mathbf y}_2, \tilde{ \mathbf y}_2\mid\mathbf X)&\cdots&M_i( \tilde{ \mathbf y}_2, \tilde{ \mathbf y}_m\mid\mathbf X)\\ \vdots &\vdots&\ddots&\vdots\\ M_i( \tilde{ \mathbf y}_m, \tilde{ \mathbf y}_1\mid\mathbf X) &M_i( \tilde{ \mathbf y}_m, \tilde{ \mathbf y}_2\mid\mathbf X)&\cdots&M_i( \tilde{ \mathbf y}_m, \tilde{ \mathbf y}_m\mid\mathbf X)\\ \end{bmatrix}_{m\times m} $

   其中： $ MathJax-Element-330 $ 。i其中：

   $ M_i(Y_i=\tilde{ \mathbf y}_u, Y_{i+1}=\tilde{ \mathbf y}_v\mid \mathbf X)=\exp\left(\sum_{k=1}^{K}w_kf_k(Y_i=\tilde{ \mathbf y}_u,Y_{i+1}=\tilde{ \mathbf y}_v,\mathbf X,i)\right) $

   $ MathJax-Element-331 $ 物理意义是：在位置 $ MathJax-Element-673 $ ，所有转移特征函数值加上所有状态特征函数值。对其取指数则是非规范化概率。

2. 引入两个特殊的状态标记：起点状态标记 $ MathJax-Element-333 $ 表示起始符，终点状态标记 $ MathJax-Element-334 $ 表示终止符。

   • $ MathJax-Element-335 $ 表示第 0 个位置的标记为 $ MathJax-Element-342 $ ，第 1个位置的标记为 $ MathJax-Element-344 $ 。

     第 0 个位置是一个虚拟符号，表示这是一个新的序列。因为 $ MathJax-Element-353 $ 状态取值只能是 $ MathJax-Element-685 $ ，则：

     $ \mathbf M_0(\mathbf X)=\begin{bmatrix} M_0( start, \tilde{ \mathbf y}_1\mid\mathbf X) &M_0( start, \tilde{ \mathbf y}_2\mid\mathbf X)&\cdots&M_0( start, \tilde{ \mathbf y}_m\mid\mathbf X)\\ 0 &0&\cdots&0\\ 0 &0&\cdots&0\\ \vdots &\vdots&\ddots&\vdots\\ 0 &0&\cdots&0\\ \end{bmatrix}_{m\times m} $

   • $ MathJax-Element-340 $ 表示第 $ MathJax-Element-345 $ 个位置的标记为 $ MathJax-Element-342 $ ，第 $ MathJax-Element-346 $ 个位置的标记为 $ MathJax-Element-344 $ 。由于序列长度为 $ MathJax-Element-345 $ ，因此第 $ MathJax-Element-346 $ 个位置是一个虚拟符号，表示该序列结束。因为 $ MathJax-Element-356 $ 的取值只能是 $ MathJax-Element-366 $ ，则：

     $ \mathbf M_n(\mathbf X)=\begin{bmatrix} M_n( \tilde{ \mathbf y}_1, stop\mid\mathbf X) &0&0&\cdots&0\\ M_n( \tilde{ \mathbf y}_2, stop\mid\mathbf X) &0&0&\cdots&0\\ \vdots &\vdots&\vdots&\ddots&\vdots\\ M_n( \tilde{ \mathbf y}_m, stop\mid\mathbf X) &0&0&\cdots&0\\ \end{bmatrix}_{m\times m} $

     因此 $ MathJax-Element-349 $ 和 $ MathJax-Element-350 $ 中包含大量的 0 。

3. 给定观测变量序列 $ MathJax-Element-351 $ ， 标记变量序列 $ MathJax-Element-352 $ 可以这样产生：

   • 首先位于起点状态 $ MathJax-Element-353 $ 。
   • 然后从 $ MathJax-Element-672 $ 转移到 $ MathJax-Element-355 $ 。
   • 最后到达终点状态 $ MathJax-Element-356 $ 。

   于是条件概率为：

   $ P(\mathbf Y\mid \mathbf X)=\frac 1Z \prod_{i=0}^{n}M_i( Y_i, Y_{i+1}\mid \mathbf X) $

   其中 $ MathJax-Element-357 $ 是以 $ MathJax-Element-685 $ 为起点，以 $ MathJax-Element-366 $ 为终点的所有标记路径的非规范化概率 $ MathJax-Element-360 $ 之和 ：

   $ Z=\sum_{Y_i \in \{\tilde{ \mathbf y}_1,\tilde {\mathbf y}_2,\cdots,\tilde {\mathbf y}_m\}}\sum_{Y_{i+1} \in \{\tilde{ \mathbf y}_1,\tilde {\mathbf y}_2,\cdots,\tilde {\mathbf y}_m\}} \prod_{i=0}^{n}M_i( Y_i, Y_{i+1}\mid \mathbf X) $

   它也等于矩阵乘积 $ MathJax-Element-361 $ 的结果的第一个元素（位于第一行第一列）的元素。

   根据 $ MathJax-Element-362 $ 和 $ MathJax-Element-363 $ 的性质，该结果矩阵只有第一个元素非零，其他所有元素都为 0）。

4. 如下图所示，上半部分是条件随机场的示意图，下半部分是条件随机场所有可能的路径。

   • 除了起点和终点外，每个节点都有 $ MathJax-Element-644 $ 个可能的取值。
   • 起点取值只能是 $ MathJax-Element-685 $ ， 终点取值只能是 $ MathJax-Element-366 $ 。
   • 红色粗实线给出了从起点到终点的一条可能的路径。

   

   ​

5. 矩阵形式和前述形式是统一的：

   $ P(\mathbf Y\mid \mathbf X)=\frac 1Z \prod_{i=0}^{n}M_i( Y_i, Y_{i+1}\mid \mathbf X)=\frac 1Z \prod_{i=0}^{n}\exp\left(\sum_{k=1}^{K}w_kf_k(Y_i ,Y_{i+1},\mathbf X,i)\right) \\ =\frac 1Z \exp\left(\sum_{i=0}^{n}\sum_{k=1}^{K}w_kf_k(Y_i ,Y_{i+1},\mathbf X,i)\right) $

   与前述形式区别在于：这里由于引入了两个特殊的状态标记：起点状态标记、终点状态标记，从而累加的区间为 $ MathJax-Element-367 $ 。

   由于引入的状态标记是人为引入且状态固定的，因此相当于引入了常量。它会相应的改变 $ MathJax-Element-620 $ 的值，最终结果是统一的。

4.2 概率计算问题

4.2.1 概率计算

1. 条件随机场的概率计算问题是：已知条件随机场 $ MathJax-Element-615 $ ，其中 $ MathJax-Element-672 $ 的取值集合为 $ MathJax-Element-371 $ ， 给定观测值序列 $ MathJax-Element-666 $ ， 给定标记值序列 $ MathJax-Element-413 $ ，其中 $ MathJax-Element-414 $ ：

   • 计算条件概率： $ MathJax-Element-375 $ 。
   • 计算条件概率： $ MathJax-Element-376 $ 。

   类似隐马尔可夫模型，可以通过前向-后向算法解决条件随机场的概率计算问题。

2. 采用 CRF 的矩阵形式，对于每个指标 $ MathJax-Element-377 $ ，（包括了起点标记和终点标记）：

   • 定义前向概率 $ MathJax-Element-378 $ ：表示在位置 $ MathJax-Element-673 $ 的标记是 $ MathJax-Element-672 $ ，并且到位置 $ MathJax-Element-673 $ 的前半部分标记序列的非规范化概率。

     由于 $ MathJax-Element-672 $ 的取值有 $ MathJax-Element-644 $ 个，因此前向概率向量 $ MathJax-Element-398 $ 是 $ MathJax-Element-644 $ 维列向量：

     $ \vec\alpha_{i}(\tilde{\mathbf X})=\begin{bmatrix} \alpha_i(Y_i=\mathbf y_1 \mid\tilde{\mathbf X})\\ \alpha_i(Y_i= \mathbf y_2 \mid\tilde{\mathbf X})\\ \vdots\\ \alpha_i(Y_i=\mathbf y_m \mid\tilde{\mathbf X}) \end{bmatrix} $

   • 定义后向概率 $ MathJax-Element-386 $ 表示在位置 $ MathJax-Element-673 $ 的标记是 $ MathJax-Element-672 $ ，并且从位置 $ MathJax-Element-419 $ 的后半部分标记序列的非规范化概率。

     由于 $ MathJax-Element-672 $ 的取值有 $ MathJax-Element-644 $ 个，因此后向概率向量 $ MathJax-Element-407 $ 也是 $ MathJax-Element-644 $ 维列向量：

     $ \vec\beta_{i}(\tilde{\mathbf X})=\begin{bmatrix} \beta_i(Y_i= \mathbf y_1 \mid\tilde{\mathbf X})\\ \beta_i(Y_i= \mathbf y_2 \mid\tilde{\mathbf X})\\ \vdots\\ \beta_i(Y_i=\mathbf y_m \mid\tilde{\mathbf X}) \end{bmatrix} $

3. 根据 CRF 的矩阵形式， 前向概率 $ MathJax-Element-394 $ 的递推形式为：

   $ \alpha_0(Y_0 \mid\tilde{\mathbf X})=\begin{cases} 1,& \text{if}\quad Y_0=start\\ 0,&\text{otherwise} \end{cases}\\ \alpha_{i+1} (Y_{i+1} \mid\tilde{\mathbf X}) =\sum_{Y_i\in \{\tilde{ \mathbf y}_1,\tilde {\mathbf y}_2,\cdots,\tilde {\mathbf y}_m\}} \alpha_i (Y_i \mid\tilde{\mathbf X})M_i(Y_i,Y_{i+1} \mid\tilde{\mathbf X}),\quad i=0,1,\cdots,n $

   • 其物理意义是：所有从起点到 $ MathJax-Element-395 $ 的路径再通过 $ MathJax-Element-396 $ 转移到 $ MathJax-Element-405 $ 。

   • 根据前向概率向量 $ MathJax-Element-398 $ 的定义，则也可以表示为：

     $ \vec\alpha_{i+1}^{T}(\tilde{\mathbf X})=\vec\alpha_{i}^{T}(\tilde{\mathbf X}) M_i(\tilde{\mathbf X}),\quad i=0,1,\cdots,n $

4. 根据 CRF 的矩阵形式，后向概率 $ MathJax-Element-399 $ 的递归形式为：

   $ \beta_{n+1}(Y_{n+1}\mid\tilde{\mathbf X})=\begin{cases} 1,& \text{if}\quad Y_{n+1}=stop\\ 0,&\text{otherwise} \end{cases}\\ \beta_i(Y_i\mid\tilde{\mathbf X}) =\sum_{Y_{i+1}\in \{\tilde{ \mathbf y}_1,\tilde {\mathbf y}_2,\cdots,\tilde {\mathbf y}_m\}}\beta_{i+1} (Y_{i+1}\mid\tilde{\mathbf X})M_i(Y_i,Y_{i+1}\mid\tilde{\mathbf X}),\quad i=0,1,\cdots,n $

   • 其物理意义可以这样理解：从 $ MathJax-Element-672 $ 到终点的路径可以这样分解：

     • 先通过 $ MathJax-Element-401 $ 从 $ MathJax-Element-672 $ 到 $ MathJax-Element-405 $ 。
     • 再通过 $ MathJax-Element-405 $ 到终点。
     • 对所有可能的 $ MathJax-Element-405 $ 累加，即得到从 $ MathJax-Element-672 $ 到终点的路径。

   • 根据后向概率向量 $ MathJax-Element-407 $ 的定义，则也可以表示为：

     $ \vec\beta_i(\tilde{\mathbf X})=M_i(\tilde{\mathbf X})\vec\beta_{i+1}(\tilde{\mathbf X}),i=0,1,\cdots,n $

5. 根据前向-后向向量定义可以得到： $ MathJax-Element-421 $ 。其中：

   • $ MathJax-Element-620 $ 为 CRF 的矩阵形式中的归一化因子。
   • $ MathJax-Element-410 $ 为元素均为 1 的 $ MathJax-Element-644 $ 维列向量。

6. 概率计算： 给定观测序列 $ MathJax-Element-666 $ ，给定标记值序列 $ MathJax-Element-413 $ ，其中 $ MathJax-Element-414 $ ，据前向-后向向量的定义，有：

   • 标记序列在位置 $ MathJax-Element-673 $ 处标记 $ MathJax-Element-418 $ 的条件概率为：
   $ P(Y_i=\tilde{ \mathbf y}_i\mid \tilde{\mathbf X})=\frac{\alpha_i(Y_i=\tilde{ \mathbf y}_i\mid\tilde{\mathbf X})\beta_i(Y_i=\tilde{ \mathbf y}_i\mid\tilde{\mathbf X})}{Z} $

   • 标记序列在位置 $ MathJax-Element-673 $ 处标记 $ MathJax-Element-418 $ ，且在位置 $ MathJax-Element-419 $ 处标记 $ MathJax-Element-420 $ 的条件概率为：

     $ P(Y_i=\tilde{ \mathbf y}_i,Y_{i+1}=\tilde{ \mathbf y}_{i+1} \mid\tilde{\mathbf X})\\ =\frac{\alpha_i(Y_i=\tilde{ \mathbf y}_i\mid\tilde{\mathbf X})M_i(Y_i=\tilde{ \mathbf y}_i,Y_{i+1}=\tilde{ \mathbf y}_{i+1}\mid\tilde{\mathbf X})\beta_{i+1}(Y_{i+1}=\tilde{ \mathbf y}_{i+1}\mid\tilde{\mathbf X})}{Z} $

     其中： $ MathJax-Element-421 $ 。

4.2.2 期望值计算

1. 利用前向-后向向量可以计算特征函数 $ MathJax-Element-422 $ 关于联合分布 $ MathJax-Element-435 $ 和条件分布 $ MathJax-Element-615 $ 的数学期望。

   • 特征函数 $ MathJax-Element-434 $ 关于条件分布 $ MathJax-Element-426 $ 的数学期望为：

     $ \mathbb E_{P(\mathbf Y\mid\mathbf X)}[f_k(Y_i,Y_{i+1},\mathbf X,i)]=\sum_{\mathbf Y}P(\mathbf Y\mid\mathbf X)f_k(Y_i,Y_{i+1},\mathbf X,i)\\ = \sum_{Y_i,Y_{i+1}}f_k(Y_i,Y_{i+1},\mathbf X,i)\frac{ \alpha_i(Y_i\mid\mathbf X)M_i(Y_i,Y_{i+1}\mid\mathbf X)\beta_{i+1}(Y_{i+1}\mid\mathbf X)}{Z} $

     其中 $ MathJax-Element-427 $ 。

     如果合并所有的位置 $ MathJax-Element-673 $ ，则有特征函数 $ MathJax-Element-438 $ 的期望为：

     $ \mathbb E_{P(\mathbf Y\mid\mathbf X)}[f_k(\mathbf Y,\mathbf X)]=\sum_{i=0}^n\mathbb E_{P(\mathbf Y\mid\mathbf X)}[f_k(Y_i,Y_{i+1},\mathbf X,i)] $

     其物理意义为：在指定观测序列 $ MathJax-Element-670 $ 的条件下，特征 $ MathJax-Element-438 $ 的均值。

   • 假设 $ MathJax-Element-670 $ 的经验分布为 $ MathJax-Element-575 $ ，则特征函数 $ MathJax-Element-434 $ 关于联合分布 $ MathJax-Element-435 $ 的数学期望为：

     $ \mathbb E_{P(\mathbf X,\mathbf Y)}[f_k(Y_i,Y_{i+1},\mathbf X,i)]=\sum_{\mathbf X,\mathbf Y}P(\mathbf X,\mathbf Y)f_k(f_k(Y_i,Y_{i+1},\mathbf X,i)\\ = \sum_{\mathbf X}\tilde P(\mathbf X)\sum_{\mathbf Y}P(\mathbf Y\mid\mathbf X)f_k( Y_i,Y_{i+1},\mathbf X,i)\\ =\sum_{\mathbf X}\tilde P(\mathbf X)\sum_{Y_i,Y_{i+1}}f_k(Y_i,Y_{i+1},\mathbf X,i)\frac{ \alpha_i(Y_i\mid\mathbf X)M_i(Y_i,Y_{i+1}\mid\mathbf X)\beta_{i+1}(Y_{i+1}\mid\mathbf X)}{Z} $

     如果合并所有的位置 $ MathJax-Element-673 $ ，则有特征函数 $ MathJax-Element-438 $ 的期望为：

     $ \mathbb E_{P(\mathbf X,\mathbf Y)}[f_k(\mathbf Y,\mathbf X,i)]=\sum_{i=0}^n\mathbb E_{P(\mathbf X,\mathbf Y)}[f_k(Y_i,Y_{i+1},\mathbf X,i)] $

     其物理意义为：在所有可能观测序列和标记序列中， $ MathJax-Element-438 $ 预期发生的次数。

2. 上述两个式子是特征函数数学期望的一般计算公式。

   • 对于转移特征函数 $ MathJax-Element-439 $ ， 可以将上式中的 $ MathJax-Element-573 $ 替换成 $ MathJax-Element-441 $ ，即得到转移特征函数的两个期望。
   • 对于状态特征函数 $ MathJax-Element-442 $ ，可以将 $ MathJax-Element-573 $ 替换成 $ MathJax-Element-444 $ ，即得到状态特征函数的两个期望。

4.3 CRF 的学习算法

1. 条件随机场模型实际上是定义在时序数据上的对数线性模型，其学习方法包括：极大似然估计、正则化的极大似然估计。

   具体的实现算法有：改进的迭代尺度法Improved Iterative Scaling:IIS、 梯度下降法、拟牛顿法。

2. 给定训练数据集 $ MathJax-Element-445 $ ，其中：

   • $ MathJax-Element-446 $ 代表第 $ MathJax-Element-673 $ 个观测序列，其长度为 $ MathJax-Element-454 $ 。

     $ MathJax-Element-449 $ 代表第 $ MathJax-Element-673 $ 个观测序列的第 $ MathJax-Element-457 $ 个位置的值。

   • $ MathJax-Element-452 $ 代表第 $ MathJax-Element-673 $ 个标记序列，其长度为 $ MathJax-Element-454 $ 。

     $ MathJax-Element-455 $ 代表第 $ MathJax-Element-673 $ 个标记序列的第 $ MathJax-Element-457 $ 个位置的值，其中 $ MathJax-Element-458 $ 。

   • 同一组观测序列和标记序列的长度相同，不同组的观测序列之间的长度可以不同。

   给定 $ MathJax-Element-464 $ 个特征函数 $ MathJax-Element-460 $ ，其中：

   $ f_k(Y_i,Y_{i+1},\mathbf X,i)=\begin{cases} t_k(Y_i,Y_{i+1},\mathbf X,i),&k=1,2,\cdots,K_1\\ s_l(Y_i,\mathbf X,i),&k=K_1+l;l=1,2,\cdots,K_2 \end{cases} $

   而 $ MathJax-Element-461 $ 为转移特征函数， $ MathJax-Element-462 $ 为状态特征函数。

   条件随机场的学习问题是：给定训练数据集 $ MathJax-Element-505 $ 和 $ MathJax-Element-464 $ 个特征函数，估计条件随机场的模型参数。即模型中的参数 $ MathJax-Element-465 $ ：

   $ P(\mathbf Y\mid \mathbf X)= \frac 1Z\exp\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right) $

   其中 $ MathJax-Element-466 $ 为归一化参数。

   注意到： $ MathJax-Element-620 $ 包含参数 $ MathJax-Element-585 $ ，同时 $ MathJax-Element-620 $ 也受 $ MathJax-Element-670 $ 影响，因此 将 $ MathJax-Element-620 $ 记作 $ MathJax-Element-472 $ 。因此将待求解的模型重新写作：

   $ P_{\mathbf{\vec w}}(\mathbf Y\mid \mathbf X)= \frac {1}{Z_{\mathbf{\vec w}}(\mathbf X)}\exp\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right) $

   $ MathJax-Element-620 $ 不受 $ MathJax-Element-621 $ 的影响，因为 $ MathJax-Element-500 $ 将变量 $ MathJax-Element-621 $ 吸收掉。

3. 考虑观测序列和标记序列 $ MathJax-Element-477 $ ， 根据经验分布 $ MathJax-Element-574 $ ， 该对序列出现的次数为 $ MathJax-Element-479 $ 。

   • 利用条件概率和经验分布 $ MathJax-Element-575 $ ，出现如此多次数的 $ MathJax-Element-481 $ 概率为：
   $ \left[\tilde P(\mathbf X=\tilde{\mathbf X}_i)P_{\mathbf{\vec w}}(\mathbf Y=\tilde{\mathbf Y}_i\mid \mathbf X=\tilde{\mathbf X}_i)\right]^{N\times \tilde P(\mathbf X=\tilde{\mathbf X}_i,\mathbf Y=\tilde{\mathbf Y}_i)} $

   • 考虑整个训练集，则训练数据集 $ MathJax-Element-505 $ 发生的概率为： $ MathJax-Element-483 $ 。

     其对数似然函数为：

     $ L_{\mathbf {\vec w}}=\log \prod_{\mathbf X,\mathbf Y}\left[\tilde P(\mathbf X )P_{\mathbf{\vec w}}(\mathbf Y \mid \mathbf X)\right]^{N\tilde P(\mathbf X ,\mathbf Y )} = \sum_{\mathbf X,\mathbf Y} \log \left[\tilde P(\mathbf X )P_{\mathbf{\vec w}}(\mathbf Y \mid\mathbf X)\right]^{N\tilde P(\mathbf X ,\mathbf Y )}\\ = \sum_{\mathbf X,\mathbf Y} \left[N\tilde P(\mathbf X ,\mathbf Y )\log \left[\tilde P(\mathbf X )P_{\mathbf{\vec w}}(\mathbf Y \mid\mathbf X)\right]\right]\\ =\sum_{\mathbf X,\mathbf Y} \left[N\tilde P(\mathbf X ,\mathbf Y )\log \tilde P(\mathbf X )\right]+\sum_{\mathbf X,\mathbf Y} \left[N\tilde P(\mathbf X ,\mathbf Y )\log P_{\mathbf{\vec w}}(\mathbf Y \mid\mathbf X) \right] $

   • 因为最终需要求解对数似然的最大值，考虑到 $ MathJax-Element-484 $ 为常数，所以去掉该项，则有：

     $ L_{\mathbf {\vec w}}= \sum_{\mathbf X,\mathbf Y} \left[N\tilde P(\mathbf X ,\mathbf Y )\log P_{\mathbf{\vec w}}(\mathbf Y \mid\mathbf X) \right] $

     忽略约去常系数 $ MathJax-Element-485 $ ，则有： $ MathJax-Element-486 $ 。

     与最大熵情况类似，这里使用了经验分布 $ MathJax-Element-487 $ ，但是并没有使用 $ MathJax-Element-488 $ 来作为 $ MathJax-Element-489 $ 的估计值，因为我们是针对该条件概率建模。

   • 根据 $ MathJax-Element-490 $ 的定义，有：

     $ L_{\mathbf {\vec w}}= \sum_{\mathbf X,\mathbf Y} \left[\tilde P(\mathbf X ,\mathbf Y )\log \frac {1}{Z_{\mathbf{\vec w}}(\mathbf X)}\exp\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right) \right] \\ = \sum_{\mathbf X,\mathbf Y} \left[\tilde P(\mathbf X ,\mathbf Y )\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right)-\tilde P(\mathbf X ,\mathbf Y )\log Z_{\mathbf{\vec w}}(\mathbf X)\right]\\ =\sum_{\mathbf X,\mathbf Y} \left[\tilde P(\mathbf X ,\mathbf Y )\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right)\right]-\sum_{\mathbf X,\mathbf Y} \left[\tilde P(\mathbf X ,\mathbf Y )\log Z_{\mathbf{\vec w}}(\mathbf X)\right]\\ =\sum_{\mathbf X,\mathbf Y} \left[\tilde P(\mathbf X ,\mathbf Y )\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right)\right]-\sum_{\mathbf X} \left[\tilde P(\mathbf X )\log Z_{\mathbf{\vec w}}(\mathbf X)\right] $

     其形式和最大熵算法完全一致，因此可以直接使用最大熵算法的学习算法。

     这也说明了，从最大熵原理可以推导出条件随机场的条件概率表示形式。

4. 给定训练数据集 $ MathJax-Element-505 $ ，则可以获取经验概率分布 $ MathJax-Element-574 $ 和 $ MathJax-Element-575 $ ，从而可以通过极大化训练数据的对数似然函数 $ MathJax-Element-588 $ 来求解模型。

4.3.1 改进的迭代尺度法

1. IIS 算法通过迭代的方法不断优化对数似然函数增量的下界，达到极大化对数似然函数的目的。具体推导可以参看最大熵算法。

2. 假设模型的当前参数向量是 $ MathJax-Element-495 $ ， 参数向量的增量为 $ MathJax-Element-496 $ 。更新的参数向量为 $ MathJax-Element-497 $ 。

   IIS 推导的结果为：每一轮迭代中， $ MathJax-Element-582 $ 满足：

   $ \sum_{\mathbf X}\left(\tilde P(\mathbf X)\sum_{\mathbf Y}[P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k f^{o}(\mathbf Y,\mathbf X))]\right)=\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k) $

   将 $ MathJax-Element-575 $ 放到 $ MathJax-Element-500 $ 右侧，重新整理为：

   $ \sum_{\mathbf X,\mathbf Y}\left(\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid \mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k f^{o}(\mathbf Y,\mathbf X))\right)=E_{\tilde P(\mathbf X,\mathbf Y)}(f_k) $

   其中：

   • $ MathJax-Element-501 $ ：为所有特征函数在序列 $ MathJax-Element-522 $ 的所有位置的总和。
   • $ MathJax-Element-503 $ ：为特征函数 $ MathJax-Element-573 $ 在训练集 $ MathJax-Element-505 $ 中对所有序列样本的所有位置上的求和。

3. CRF学习的改进迭代尺度算法IIS：

   • 输入：

     • 特征函数 $ MathJax-Element-573 $
     • 经验分布 $ MathJax-Element-574 $
     • 经验分布 $ MathJax-Element-575 $

   • 输出：

     • 参数估计值 $ MathJax-Element-576 $
     • 模型 $ MathJax-Element-577 $

   • 算法步骤：

     • 初始化：对所有的 $ MathJax-Element-581 $ ，取值 $ MathJax-Element-579 $ 。

     • 迭代，迭代的停止条件是：所有 $ MathJax-Element-585 $ 都收敛。迭代步骤为：

       • 对每一个 $ MathJax-Element-581 $ ，从方程中计算出 $ MathJax-Element-582 $ ：

         $ \sum_{\mathbf X}\left(\tilde P(\mathbf X)\sum_{\mathbf Y}[P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k f^{o}(\mathbf Y,\mathbf X))]\right)=\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k) $

       • 更新 $ MathJax-Element-585 $ 的值： $ MathJax-Element-584 $ 。如果不是所有 $ MathJax-Element-585 $ 都收敛，继续迭代。

     • 迭代终止时， $ MathJax-Element-586 $ 。

4.3.1.1 算法 S

1. 在IIS算法中， $ MathJax-Element-523 $ 为所有特征函数在序列 $ MathJax-Element-522 $ 的所有位置的总和。对于不同的数据 $ MathJax-Element-522 $ ， $ MathJax-Element-523 $ 很有可能不同。

   选择一个常数 $ MathJax-Element-557 $ ，定义松弛特征： $ MathJax-Element-525 $ 。

   • 通常选择足够大的常数 $ MathJax-Element-557 $ ，使得对于训练数据集的所有数据 $ MathJax-Element-527 $ ， $ MathJax-Element-528 $ 成立。
   • 当每个特征函数的取值范围都是 $ MathJax-Element-676 $ 时，则可以将 $ MathJax-Element-557 $ 选取为： $ MathJax-Element-531 $ 。其物理意义为：所有潜在的特征函数取 1 的位置的总数，乘以特征函数的数量。

2. 将松弛特征代入，有：

   $ \sum_{\mathbf X}\left(\tilde P(\mathbf X)\sum_{\mathbf Y}[P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k f^{o}(\mathbf Y,\mathbf X))]\right)\\ =\sum_{\mathbf X,\mathbf Y}\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k (S-s(\mathbf Y,\mathbf X))) $

   考虑到 $ MathJax-Element-532 $ 在 $ MathJax-Element-533 $ 上恒成立，因此有：

   因此对于下面两个方程的解：

   $ \sum_{\mathbf X,\mathbf Y}\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k^{(1)} f^{o}(\mathbf Y,\mathbf X))=\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)\\ \sum_{\mathbf X,\mathbf Y}\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k^{(2)}S)=\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k) $

   必然有： $ MathJax-Element-562 $ 。

   如果 $ MathJax-Element-535 $ ，则有：

   $ \mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)=\sum_{\mathbf X,\mathbf Y}\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k^{(2)}S)\\ \gt \sum_{\mathbf X,\mathbf Y}\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k^{(1)} f^{o}(\mathbf Y,\mathbf X))=\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k) $

   因此可以将 $ MathJax-Element-563 $ 作为 $ MathJax-Element-564 $ 的一个近似。其物理意义为：更新 $ MathJax-Element-585 $ 的值（ $ MathJax-Element-584 $ ）时，选择一个较小的更新幅度。

3. 对于方程 $ MathJax-Element-540 $ ，其解为：

   $ \delta_k = \frac 1S \log \frac{\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)}{\sum_{\mathbf X,\mathbf Y}\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)} = \frac 1S \log \frac{\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)}{\mathbb E_{P(\mathbf X,\mathbf Y)}(f_k)} $

   其中 $ MathJax-Element-552 $ 。

4. CRF学习的算法 S：

   • 输入：

     • 特征函数 $ MathJax-Element-573 $
     • 经验分布 $ MathJax-Element-574 $
     • 经验分布 $ MathJax-Element-575 $

   • 输出：

     • 参数估计值 $ MathJax-Element-576 $
     • 模型 $ MathJax-Element-577 $

   • 算法步骤：

     • 初始化：对所有的 $ MathJax-Element-581 $ ，取值 $ MathJax-Element-579 $ 。

     • 迭代，迭代的停止条件是：所有 $ MathJax-Element-585 $ 都收敛。迭代步骤为：

       • 对每一个 $ MathJax-Element-581 $ ，计算 $ MathJax-Element-582 $ ：

         $ \delta_k = \frac 1S \log \frac{\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)}{\mathbb E_{P(\mathbf X,\mathbf Y)}(f_k)} $

         其中 $ MathJax-Element-552 $ 。

       • 更新 $ MathJax-Element-585 $ 的值： $ MathJax-Element-584 $ 。如果不是所有 $ MathJax-Element-585 $ 都收敛，继续迭代。

     • 迭代终止时， $ MathJax-Element-586 $ 。

4.3.1.2 算法 T

1. 在算法S中，通常需要使常数 $ MathJax-Element-557 $ 取得足够大，此时每一步迭代的增量向量会较小，算法收敛会变慢。

   算法T试图解决这个问题。

2. 算法T 对每个观测序列 $ MathJax-Element-558 $ ，计算其特征总数最大值 $ MathJax-Element-559 $ ：

   $ f^{o}(\tilde{\mathbf X}_i)=\max_{\mathbf Y}f^{o}(\mathbf Y,\mathbf X=\tilde{\mathbf X}_i) =\max_{\mathbf Y} \sum_{k=1}^{K}\sum_{l=0}^{n_i}f_k(Y_l,Y_{l+1},\mathbf X=\tilde{\mathbf X}_i,l) $

   记 $ MathJax-Element-560 $ ，由于 $ MathJax-Element-561 $ ，则对于下面两个方程的解：

   $ \sum_{\mathbf X,\mathbf Y}\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k^{(1)} f^{o}(\mathbf Y,\mathbf X))=\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)\\ \sum_{\mathbf X,\mathbf Y}\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(\mathbf Y,\mathbf X)\exp(\delta_k^{(2)}T(\mathbf X))=\mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k) $

   必然有： $ MathJax-Element-562 $ ，原因与算法S 相同。

   因此可以将 $ MathJax-Element-563 $ 作为 $ MathJax-Element-564 $ 的一个近似。其物理意义为：更新 $ MathJax-Element-585 $ 的值（ $ MathJax-Element-584 $ ）时，选择一个较小的更新幅度。

   由于 $ MathJax-Element-567 $ ，因此算法 T 求解的 $ MathJax-Element-568 $ 会相对于算法 S 更大，使得算法收敛的更快。

3. 对于方程 $ MathJax-Element-569 $ ，有：

   $ \mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)=\sum_{\mathbf X,\mathbf Y}\left(\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid \mathbf X)\sum_{i=0}^{n}f_k(Y_i,Y_{i+1},\mathbf X,i)\exp(\delta_k T(\mathbf X))\right)\\ =\sum_{\mathbf X}\left[\tilde P(\mathbf X)\exp(\delta_k T(\mathbf X))\sum_{\mathbf Y}\sum_{i=0}^{n}\left(P_{\mathbf{\vec w}}(\mathbf Y\mid\mathbf X)f_k(Y_i,Y_{i+1},\mathbf X,i)\right)\right] $

   令： $ MathJax-Element-570 $ ，则有：

   $ \mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)=\sum_{\mathbf X}\tilde P(\mathbf X)\exp(\delta_k T(\mathbf X))a_{k,\mathbf X} $

   它就是一个以 $ MathJax-Element-582 $ 为变量的非线性方程，求解该方程即可得到 $ MathJax-Element-582 $ 的解。

4. CRF学习的算法 T：

   • 输入：

     • 特征函数 $ MathJax-Element-573 $
     • 经验分布 $ MathJax-Element-574 $
     • 经验分布 $ MathJax-Element-575 $

   • 输出：

     • 参数估计值 $ MathJax-Element-576 $
     • 模型 $ MathJax-Element-577 $

   • 算法步骤：

     • 初始化：对所有的 $ MathJax-Element-581 $ ，取值 $ MathJax-Element-579 $ 。

     • 迭代，迭代的停止条件是：所有 $ MathJax-Element-585 $ 都收敛。迭代步骤为：

       • 对每一个 $ MathJax-Element-581 $ ，从方程中计算出 $ MathJax-Element-582 $ ：

         $ \mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k)=\sum_{\mathbf X}\tilde P(\mathbf X)\exp(\delta_k T(\mathbf X))a_{k,\mathbf X} $

       • 更新 $ MathJax-Element-585 $ 的值： $ MathJax-Element-584 $ 。如果不是所有 $ MathJax-Element-585 $ 都收敛，继续迭代。

     • 迭代终止时， $ MathJax-Element-586 $ 。

4.3.2 拟牛顿法

1. 条件随机场的对数似然函数为：

   $ L_{\mathbf {\vec w}}=\sum_{\mathbf X,\mathbf Y} \left[\tilde P(\mathbf X ,\mathbf Y )\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right)\right]-\sum_{\mathbf X} \left[\tilde P(\mathbf X )\log Z_{\mathbf{\vec w}}(\mathbf X)\right] $

   其中： $ MathJax-Element-587 $ 。

   学习的优化目标是最大化对数似然函数 $ MathJax-Element-588 $ 。

   令：

   $ F(\mathbf{\vec w})=-L_{\mathbf {\vec w}}\\ =\sum_{\mathbf X} \left[\tilde P(\mathbf X )\log \sum_{\mathbf Y} \exp\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right)\right]- \sum_{\mathbf X,\mathbf Y} \left[\tilde P(\mathbf X ,\mathbf Y )\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right)\right] $

   于是学习优化目标是最小化 $ MathJax-Element-589 $ 。

2. 计算梯度:

   $ \vec g(\mathbf{\vec w})=(\frac{\partial F(\mathbf{\vec w})}{\partial w_1},\frac{\partial F(\mathbf{\vec w})}{\partial w_2},\cdots,\frac{\partial F(\mathbf{\vec w})}{\partial w_K})^{T},\\ \frac{\partial F(\mathbf{\vec w})}{\partial w_k}=\sum_{\mathbf X,\mathbf Y}[\tilde P(\mathbf X)P_{\mathbf{\vec w}}(\mathbf Y\mid \mathbf X)f_k(\mathbf Y,\mathbf X)]- \mathbb E_{\tilde P(\mathbf X,\mathbf Y)}(f_k),\quad k=1,2,\cdots,K $

3. CRF 学习的 BFGS算法：

   • 输入：

     • 特征函数 $ MathJax-Element-590 $
     • 经验分布 $ MathJax-Element-591 $
     • 目标函数 $ MathJax-Element-592 $
     • 梯度 $ MathJax-Element-593 $
     • 精度要求 $ MathJax-Element-594 $

   • 输出：

     • 最优参数值 $ MathJax-Element-595 $
     • 最优模型 $ MathJax-Element-596 $

   • 算法步骤：

     • 选定初始点 $ MathJax-Element-597 $ ，取 $ MathJax-Element-598 $ 为正定对阵矩阵，置 $ MathJax-Element-599 $

     • 计算 $ MathJax-Element-600 $ :

       • 若 $ MathJax-Element-601 $ ，停止计算，得到 $ MathJax-Element-602 $

       • 若 $ MathJax-Element-603 $ :

         • 由 $ MathJax-Element-604 $ 求得 $ MathJax-Element-605 $

         • 一维搜索：求出 $ MathJax-Element-606 $ ： $ MathJax-Element-607 $

         • 置 $ MathJax-Element-608 $

         • 计算 $ MathJax-Element-609 $ 。 若 $ MathJax-Element-610 $ ，停止计算，得到 $ MathJax-Element-611 $

         • 否则计算 $ MathJax-Element-612 $ :

           $ \mathbf B_{k+1}=\mathbf B_k+\frac{\mathbf{\vec y}_k \mathbf{\vec y}_k^{T}}{\mathbf{\vec y}_k^{T} \vec\delta_k}-\frac{\mathbf B_k \vec\delta_k \vec\delta_k^{T}\mathbf B_k}{\vec\delta_k^{T} B_k \vec\delta_k} $

           其中： $ MathJax-Element-613 $

         • 置 $ MathJax-Element-614 $ ，继续迭代。

4.4 预测算法

1. 给定条件随机场 $ MathJax-Element-615 $ 以及输入序列（观测序列） $ MathJax-Element-666 $ 的情况下，求条件概率最大的输出序列（标记序列） $ MathJax-Element-661 $ ，其中 $ MathJax-Element-618 $ 。

2. 根据条件随机场的简化形式：

   $ P(\mathbf Y\mid \mathbf X)= \frac 1Z\exp\left(\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X) \right)=\frac 1Z \exp\left(\mathbf{\vec w}\cdot \mathbf {\vec F}(\mathbf Y,\mathbf X) \right) $

   其中 $ MathJax-Element-619 $ 。

   于是：

   $ \mathbf Y^{*}=\arg\max_{\mathbf Y}P(\mathbf Y\mid \mathbf X=\tilde{\mathbf X})=\arg\max_{\mathbf Y}\frac 1Z \exp\left(\mathbf{\vec w}\cdot \mathbf {\vec F}(\mathbf Y,\mathbf X=\tilde{\mathbf X}) \right) $

   考虑到 $ MathJax-Element-620 $ 与 $ MathJax-Element-621 $ 无关，于是：

   $ \mathbf Y^{*}=\arg\max_{\mathbf Y} \exp\left(\mathbf{\vec w}\cdot \mathbf {\vec F}(\mathbf Y,\mathbf X=\tilde{\mathbf X}) \right)=\arg\max_{\mathbf Y}\mathbf{\vec w}\cdot \mathbf {\vec F}(\mathbf Y,\mathbf X=\tilde{\mathbf X}) $

   于是：条件随机场的预测问题就成为求非规范化概率最大的最优路径问题。

   其中：

   $ \mathbf{\vec w}\cdot \mathbf {\vec F}(\mathbf Y,\mathbf X=\tilde{\mathbf X})=\sum_{k=1}^{K}w_kf_k(\mathbf Y,\mathbf X=\tilde{\mathbf X})\\ =\sum_{k=1}^{K}w_k\sum_{i=0}^{n}f_k(Y_i,Y_{i+1},\mathbf X=\tilde{\mathbf X},i) $

   其中就是非规范化概率。

3. 定义局部特征向量：

   $ \mathbf {\vec F}_i(Y_i,Y_{i+1},\mathbf X=\tilde{\mathbf X})=(f_1(Y_i,Y_{i+1},\mathbf X=\tilde{\mathbf X},i),\cdots,f_K(Y_i,Y_{i+1},\mathbf X=\tilde{\mathbf X},i))^{T} $

   其物理意义为：每个特征函数在 $ MathJax-Element-622 $ 的条件下，在位置 $ MathJax-Element-673 $ 处的取值组成的向量。

   于是： $ MathJax-Element-624 $ 。

   为了便于统一描述，这里引入了两个人工标记： $ MathJax-Element-625 $ 。它们具有唯一的、固定的取值（不是随机变量）。

4. 维特比算法用动态规划来求解条件随机场的预测问题。它用动态规划求解概率最大路径（最优路径），这时一条路径对应着一个标记序列。

   • 根据动态规划原理，最优路径具有这样的特性：如果最优路径在位置 $ MathJax-Element-673 $ 通过结点 $ MathJax-Element-630 $ ， 则这一路径从结点 $ MathJax-Element-630 $ 到终点 $ MathJax-Element-639 $ 的部分路径，对于从 $ MathJax-Element-630 $ 到 $ MathJax-Element-639 $ 的所有可能路径来说，也必须是最优的。

   • 只需要从位置 $ MathJax-Element-632 $ 开始，递推地计算从位置 1 到位置 $ MathJax-Element-673 $ 且位置 $ MathJax-Element-673 $ 的标记为 $ MathJax-Element-635 $ 的各条部分路径的最大非规范化概率。

     于是在位置 $ MathJax-Element-653 $ 的最大非规范化概率即为最优路径的非规范化概率 $ MathJax-Element-637 $ ，最优路径的终结点 $ MathJax-Element-639 $ 也同时得到。

   • 之后为了找出最优路径的各个结点，从终结点 $ MathJax-Element-639 $ 开始，由后向前逐步求得结点 $ MathJax-Element-640 $ ，得到最优路径 $ MathJax-Element-641 $ 。

5. 假设标记 $ MathJax-Element-657 $ 的取值集合为 $ MathJax-Element-658 $ ， 其中 $ MathJax-Element-644 $ 是标记的取值个数。

   • 首先求出位置 1 的各个标记值的非规范化概率：
   $ \delta_1(j)=\mathbf{\vec w}\cdot\mathbf {\vec F}_0(Y_0=start,Y_{1}= \mathbf y_j,\mathbf X=\tilde{\mathbf X}),j=1,2,\cdots,m $

   • 根据递推公式，求出到位置 $ MathJax-Element-673 $ 的各个标记取值的非规范化概率的最大值，同时记录非规范化概率最大值的路径：

     $ \delta_i(l)=\max_{1\le j\le m}\{\delta_{i-1}(j)+\mathbf{\vec w}\cdot\mathbf {\vec F}_i(Y_i=\mathbf y_j,Y_{i+1}= \mathbf y_l,\mathbf X=\tilde{\mathbf X})\}\\ \Psi_i(l)=\arg\max_{1\le j\le m}\{\delta_{i-1}(j)+\mathbf{\vec w}\cdot\mathbf {\vec F}_i(Y_i= \mathbf y_j,Y_{i+1}=\mathbf y_l,\mathbf X=\tilde{\mathbf X})\}\\ l=1,2,\cdots,m;\quad i=1,2,\cdots,n $
     • 其中 $ MathJax-Element-646 $ 为：到位置 $ MathJax-Element-673 $ 、且标记取值为 $ MathJax-Element-648 $ 的非规范化概率的最大值。
     • $ MathJax-Element-649 $ 为：到位置 $ MathJax-Element-673 $ 且标记取值为 $ MathJax-Element-651 $ 的最优路径中，位置 $ MathJax-Element-675 $ 处的标记的取值的编号。

   • 到 $ MathJax-Element-653 $ 时，这时求得非规范化概率的最大值，以及最优路径的终点：

   $ \max_{\mathbf Y}\mathbf{\vec w}\cdot \mathbf {\vec F}(\mathbf Y,\mathbf X=\tilde{\mathbf X})=\max_{1\le j\le m}\delta_n(j),\quad \text{node}_n=\arg\max_{1\le j\le m}\delta_n(j),\quad \tilde {\mathbf y}_n^{*}=\mathbf y_{\text{node}_n} $

   • 根据最优路径得到： $ MathJax-Element-664 $ 。

     最终得到最优路径： $ MathJax-Element-665 $ 。

6. CRF 预测的维特比算法：

   • • 输入：

       • 模型特征向量 $ MathJax-Element-656 $ ，其中标记 $ MathJax-Element-657 $ 的取值集合为 $ MathJax-Element-658 $
       • 权值向量 $ MathJax-Element-659 $
       • 观测序列 $ MathJax-Element-666 $

     • 输出： 最优路径 $ MathJax-Element-661 $

     • 算法步骤：

       • 初始化： $ MathJax-Element-662 $ 。
       • 递推：对 $ MathJax-Element-663 $ ：
       $ \delta_i(l)=\max_{1\le j\le m}\{\delta_{i-1}(j)+\mathbf{\vec w}\cdot\mathbf {\vec F}_i(Y_i=\mathbf y_j,Y_{i+1}= \mathbf y_l,\mathbf X=\tilde{\mathbf X})\}\\ \Psi_i(l)=\arg\max_{1\le j\le m}\{\delta_{i-1}(j)+\mathbf{\vec w}\cdot\mathbf {\vec F}_i(Y_i= \mathbf y_j,Y_{i+1}=\mathbf y_l,\mathbf X=\tilde{\mathbf X})\}\\ l=1,2,\cdots,m;\quad i=1,2,\cdots,n $
       • 终止：
       $ \max_{\mathbf Y}\mathbf{\vec w}\cdot \mathbf {\vec F}(\mathbf Y,\mathbf X=\tilde{\mathbf X})=\max_{1\le j\le m}\delta_n(j),\quad \text{node}_n=\arg\max_{1\le j\le m}\delta_n(j),\quad \tilde {\mathbf y}_n^{*}=\mathbf y_{\text{node}_n} $
       • 回溯路径： $ MathJax-Element-664 $ 。
       • 返回路径 ： $ MathJax-Element-665 $ 。

4.5 词性标注任务

1. 在词性标注任务中，给定单词序列 $ MathJax-Element-666 $ ，需要给出每个单词对应的词性 $ MathJax-Element-667 $ 。如： 他们 吃 苹果 对应的标注序列为 代词 动词 名词 。

   • 给定一个单词序列，可选的标注序列有很多种，需要从中挑选出一个最靠谱的作为标注结果。
   • 标注序列是否靠谱，是通过利用特征函数来对序列打分来获得。序列的得分越高（意味着非规范化概率越大），则越靠谱。

2. CRF 中的特征函数接受四个参数：

   • 单词序列 $ MathJax-Element-670 $ 。
   • 位置 $ MathJax-Element-673 $ ，表示序列 $ MathJax-Element-670 $ 中第 $ MathJax-Element-673 $ 个单词。
   • 标记 $ MathJax-Element-672 $ ，表示第 $ MathJax-Element-673 $ 个单词的标注词性。
   • 标记 $ MathJax-Element-674 $ ，表示第 $ MathJax-Element-675 $ 个单词的标注词性。

   特征函数的输出值为 $ MathJax-Element-676 $ ，表示满足/不满足这个特征。

3. 每个特征函数对应一个权重 $ MathJax-Element-677 $ 。

   • 若权重为正，则说明该特征贡献一个正的分数；如果权重为负，则说明该特征贡献一个负的分数。
   • 权重越大，则说明该特征靠谱的可能性越大（对于正的权重），或者该特征不靠谱的程度越大（对于负的权重）。
   • 该权重是模型的参数，从训练集中训练得到。

4.6 CRF 与 HMM 模型

1. 设已知隐马尔科夫模型的参数，则给定观察序列 $ MathJax-Element-678 $ ，以及标记序列 $ MathJax-Element-679 $ ，其出现的概率为：

   $ P(\mathbf I,\mathbf O)=P(i_1)\times \left(\prod_{t=1}^{T-1}P( i_{t+1}\mid i_t)\right)\times\prod_{t=1}^{T} P( o_t\mid f i_t)\\ \rightarrow \log P(\mathbf I,\mathbf O)=\log P(i_1)+\sum_{t=1}^{T-1}\log P( i_{t+1}\mid i_t)+\sum_{t=1}^T\log P( o_t\mid i_t) $

   • 对于 HMM 中的每一个转移概率 $ MathJax-Element-680 $ ，定义特征函数：

     $ s_{i,j}(\mathbf O,t, i_{t}, i_{t+1})=\begin{cases} 1,& i_{t+1}=j \;\text{and}\;i_{t}=i\\ 0,&\text{else}\end{cases} $

     定义其权重为： $ MathJax-Element-681 $ 。

   • 对于 HMM中每一个发射概率 $ MathJax-Element-682 $ ，定义特征函数：

     $ t_{j,k}(\mathbf O,t, i_{t})=\begin{cases} 1,& i_{t}= j \;\text{and} \; o_t= k\\ 0,&\text{else}\end{cases} $

     定义其权重为： $ MathJax-Element-683 $ 。

   • 则有：

     $ \log P(\mathbf I,\mathbf O)=\log P(i_1)+\sum_{t=1}^{T-1}\log P( i_{t+1}\mid i_t)+\sum_{t=1}^T\log P(o_t\mid i_t)\\ =\sum_{t=0}^{T-1}\log P( i_{t+1}\mid i_t)+\sum_{t=1}^T\log P(o_t\mid i_t)\\ =\sum_{t=0}^{T-1} w^{(s)}_{i,j}s_{i,j}(\mathbf O,t, i_t, i_{t+1})+\sum_{t=1}^{T}w^{(t)}_{j,k}t_{j,k}(\mathbf O,t, i_t) $

     其中 $ MathJax-Element-684 $ 为人工引入的 $ MathJax-Element-685 $ 结点。

     因此 $ MathJax-Element-686 $ 的物理意义为：所有特征函数在所有位置之和。将其归一化之后就得到了CRF的公式。

2. 从推导中可以看出：每一个HMM模型都等价于某个CRF模型。

   • CRF模型比HMM模型更强大。

     因为CRF模型能定义数量更多、更丰富多样的特征函数，能使用任意形式的权重。

   • HMM模型中当前的标注结果只依赖于当前的单词，以及前一个标注结果。

   • HMM模型转换过来的形式中，权重是条件概率的对数，因此权重都是负的。

3. HMM 是生成式模型，而CRF是判别式模型

   • 生成式模型对联合概率建模，可以生成样本。

     生成式模型定义的是联合概率，必须列举所有观察序列的可能值。在很多场景下，这是很困难的。

   • 判别式模型对条件概率建模，无法生成样本，只能判断分类。