16.概率图与条件随机场 - 四、条件随机场 CRF - 《AI算法工程师手册》

四、条件随机场 CRF

四、条件随机场 CRF

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

判别式概率图模型是对条件分布进行建模，如条件随机场Conditional Random Field:CRF。
条件随机场试图对多个随机变量（它们代表标记序列）在给定观测序列的值之后的条件概率进行建模：

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

即：已知观测变量序列的条件下，标记序列发生的概率。
标记随机变量序列的成员之间可能具有某种结构：
- 在自然语言处理的词性标注任务中，观测数据为单词序列，标记为对应的词性序列（即动词、名词等词性的序列），标记序列具有线性的序列结构。
- 在自然语言处理的语法分析任务中，观测数据为单词序列，标记序列是语法树，标记序列具有树形结构。
令表示与观测变量序列和标记变量序列对应的无向图，表示与结点对应的标记随机变量，表示结点的邻接结点集。若图中结点对应的每个变量都满足马尔可夫性，即：

则构成了一个条件随机场。

4.1 链式条件随机场

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

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

如果没有特殊说明，这里讨论是基于链式条件随机场。
给定观测变量序列，链式条件随机场主要包含两种关于标记变量的团：
- 单个标记变量与构成的团：。
- 相邻标记变量与构成的团：。
与马尔可夫随机场定义联合概率的方式类似，条件随机场使用势函数和团来定义条件概率。

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

其中：
- ：在已知观测序列情况下，两个相邻标记位置上的转移特征函数transition feature function。
  - 它刻画了相邻标记变量之间的相关关系，以及观察序列对它们的影响。
  - 位置变量也对势函数有影响。比如：已知观测序列情况下，相邻标记取值(代词，动词)出现在序列头部可能性较高，而(动词，代词)出现在序列头部的可能性较低。
- ：在已知观察序列情况下，标记位置上的状态特征函数status feature function。
  - 它刻画了观测序列对于标记变量的影响。
  - 位置变量也对势函数有影响。比如：已知观测序列情况下，标记取值 名词出现在序列头部可能性较高，而 动词 出现在序列头部的可能性较低。
- 为参数，为规范化因子（它用于确保上式满足概率的定义）。
  
  为转移特征函数的个数，为状态特征函数的个数。
特征函数通常是实值函数，用来刻画数据的一些很可能成立或者预期成立的经验特性。

一个特征函数的例子（词性标注）：
- 转移特征函数刻画的是：第个观测值为单词 "knock" 时，相应的标记和很可能分别为 [V]和[P] 。
- 状态特征函数刻画的是：第个观测值为单词 "knock" 时，标记很可能为 [V] 。
条件随机场与马尔可夫随机场均使用团上的势函数定义概率，二者在形式上没有显著区别。

条件随机场处理的是条件概率，马尔可夫随机场处理的是联合概率。
的形式类似于逻辑回归。事实上，条件随机场是逻辑回归的序列化版本。
- 逻辑回归是用于分类问题的对数线性模型。
- 条件随机场是用于序列化标注的对数线性模型。

4.1.1 CRF 的简化形式

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

这样就可以将条件随机场写成权值向量和特征向量的内积形式，即条件随机场的简化形式。
设有个转移特征函数，个状态特征函数。令，定义：

注意：要求，而要求，因此对于边界条件要特殊处理。

对转移与状态函数在各个位置求和，记作：

其中为标记变量序列，为观测变量序列。

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

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

其中，表示对所有可能的标记序列进行求和。
定义权值向量为，定义全局特征向量为：

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

其中，表示对所有可能的标记序列进行求和。

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

4.1.2 CRF 的矩阵形式

假设标记变量的取值集合为，其中是标记的取值个数。

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

其中：。i其中：

物理意义是：在位置，所有转移特征函数值加上所有状态特征函数值。对其取指数则是非规范化概率。
引入两个特殊的状态标记：起点状态标记表示起始符，终点状态标记表示终止符。
- 表示第 0 个位置的标记为，第 1个位置的标记为。
  
  第 0 个位置是一个虚拟符号，表示这是一个新的序列。因为状态取值只能是，则：
- 表示第个位置的标记为，第个位置的标记为。由于序列长度为，因此第个位置是一个虚拟符号，表示该序列结束。因为的取值只能是，则：
  
  因此和中包含大量的 0 。
给定观测变量序列，标记变量序列可以这样产生：
- 首先位于起点状态。
- 然后从转移到。
- 最后到达终点状态。
于是条件概率为：

其中是以为起点，以为终点的所有标记路径的非规范化概率之和：

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

根据和的性质，该结果矩阵只有第一个元素非零，其他所有元素都为 0）。
如下图所示，上半部分是条件随机场的示意图，下半部分是条件随机场所有可能的路径。
- 除了起点和终点外，每个节点都有个可能的取值。
- 起点取值只能是，终点取值只能是。
- 红色粗实线给出了从起点到终点的一条可能的路径。
矩阵形式和前述形式是统一的：

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

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

4.2 概率计算问题

4.2.1 概率计算

条件随机场的概率计算问题是：已知条件随机场，其中的取值集合为，给定观测值序列，给定标记值序列，其中：
- 计算条件概率：。
- 计算条件概率：。
类似隐马尔可夫模型，可以通过前向-后向算法解决条件随机场的概率计算问题。
采用 CRF 的矩阵形式，对于每个指标，（包括了起点标记和终点标记）：
- 定义前向概率：表示在位置的标记是，并且到位置的前半部分标记序列的非规范化概率。
  
  由于的取值有个，因此前向概率向量是维列向量：
- 定义后向概率表示在位置的标记是，并且从位置的后半部分标记序列的非规范化概率。
  
  由于的取值有个，因此后向概率向量也是维列向量：
根据 CRF 的矩阵形式，前向概率的递推形式为：
- 其物理意义是：所有从起点到的路径再通过转移到。
- 根据前向概率向量的定义，则也可以表示为：
根据 CRF 的矩阵形式，后向概率的递归形式为：
- 其物理意义可以这样理解：从到终点的路径可以这样分解：
  - 先通过从到。
  - 再通过到终点。
  - 对所有可能的累加，即得到从到终点的路径。
- 根据后向概率向量的定义，则也可以表示为：
根据前向-后向向量定义可以得到：。其中：
- 为 CRF 的矩阵形式中的归一化因子。
- 为元素均为 1 的维列向量。
概率计算：给定观测序列，给定标记值序列，其中，据前向-后向向量的定义，有：
- 标记序列在位置处标记的条件概率为：
- 标记序列在位置处标记，且在位置处标记的条件概率为：
  
  其中：。

4.2.2 期望值计算

利用前向-后向向量可以计算特征函数关于联合分布和条件分布的数学期望。
- 特征函数关于条件分布的数学期望为：
  
  其中。
  
  如果合并所有的位置，则有特征函数的期望为：
  
  其物理意义为：在指定观测序列的条件下，特征的均值。
- 假设的经验分布为，则特征函数关于联合分布的数学期望为：
  
  如果合并所有的位置，则有特征函数的期望为：
  
  其物理意义为：在所有可能观测序列和标记序列中，预期发生的次数。
上述两个式子是特征函数数学期望的一般计算公式。
- 对于转移特征函数，可以将上式中的替换成，即得到转移特征函数的两个期望。
- 对于状态特征函数，可以将替换成，即得到状态特征函数的两个期望。

4.3 CRF 的学习算法

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

具体的实现算法有：改进的迭代尺度法Improved Iterative Scaling:IIS、梯度下降法、拟牛顿法。
给定训练数据集，其中：
- 代表第个观测序列，其长度为。
  
  代表第个观测序列的第个位置的值。
- 代表第个标记序列，其长度为。
  
  代表第个标记序列的第个位置的值，其中。
- 同一组观测序列和标记序列的长度相同，不同组的观测序列之间的长度可以不同。
给定个特征函数，其中：

而为转移特征函数，为状态特征函数。

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

其中为归一化参数。

注意到：包含参数，同时也受影响，因此将记作。因此将待求解的模型重新写作：

不受的影响，因为将变量吸收掉。
考虑观测序列和标记序列，根据经验分布，该对序列出现的次数为。
- 利用条件概率和经验分布，出现如此多次数的概率为：
- 考虑整个训练集，则训练数据集发生的概率为：。
  
  其对数似然函数为：
- 因为最终需要求解对数似然的最大值，考虑到为常数，所以去掉该项，则有：
  
  忽略约去常系数，则有：。
  
  与最大熵情况类似，这里使用了经验分布，但是并没有使用来作为的估计值，因为我们是针对该条件概率建模。
- 根据的定义，有：
  
  其形式和最大熵算法完全一致，因此可以直接使用最大熵算法的学习算法。
  
  这也说明了，从最大熵原理可以推导出条件随机场的条件概率表示形式。
给定训练数据集，则可以获取经验概率分布和，从而可以通过极大化训练数据的对数似然函数来求解模型。

4.3.1 改进的迭代尺度法

IIS 算法通过迭代的方法不断优化对数似然函数增量的下界，达到极大化对数似然函数的目的。具体推导可以参看最大熵算法。
假设模型的当前参数向量是，参数向量的增量为。更新的参数向量为。

IIS 推导的结果为：每一轮迭代中，满足：

将放到右侧，重新整理为：

其中：
- ：为所有特征函数在序列的所有位置的总和。
- ：为特征函数在训练集中对所有序列样本的所有位置上的求和。
CRF学习的改进迭代尺度算法IIS：
- 输入：
  - 特征函数
  - 经验分布
  - 经验分布
- 输出：
  - 参数估计值
  - 模型
- 算法步骤：
  - 初始化：对所有的，取值。
  - 迭代，迭代的停止条件是：所有都收敛。迭代步骤为：
    - 对每一个，从方程中计算出：
    - 更新的值：。如果不是所有都收敛，继续迭代。
  - 迭代终止时，。

4.3.1.1 算法 S

在IIS算法中，为所有特征函数在序列的所有位置的总和。对于不同的数据，很有可能不同。

选择一个常数，定义松弛特征：。
- 通常选择足够大的常数，使得对于训练数据集的所有数据，成立。
- 当每个特征函数的取值范围都是时，则可以将选取为：。其物理意义为：所有潜在的特征函数取 1 的位置的总数，乘以特征函数的数量。
将松弛特征代入，有：

考虑到在上恒成立，因此有：

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

必然有：。

如果，则有：

因此可以将作为的一个近似。其物理意义为：更新的值（）时，选择一个较小的更新幅度。
对于方程，其解为：

其中。
CRF学习的算法 S：
- 输入：
  - 特征函数
  - 经验分布
  - 经验分布
- 输出：
  - 参数估计值
  - 模型
- 算法步骤：
  - 初始化：对所有的，取值。
  - 迭代，迭代的停止条件是：所有都收敛。迭代步骤为：
    - 对每一个，计算：
      
      其中。
    - 更新的值：。如果不是所有都收敛，继续迭代。
  - 迭代终止时，。

4.3.1.2 算法 T

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

算法T试图解决这个问题。
算法T 对每个观测序列，计算其特征总数最大值：

记，由于，则对于下面两个方程的解：

必然有：，原因与算法S 相同。

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

由于，因此算法 T 求解的会相对于算法 S 更大，使得算法收敛的更快。
对于方程，有：

令：，则有：

它就是一个以为变量的非线性方程，求解该方程即可得到的解。
CRF学习的算法 T：
- 输入：
  - 特征函数
  - 经验分布
  - 经验分布
- 输出：
  - 参数估计值
  - 模型
- 算法步骤：
  - 初始化：对所有的，取值。
  - 迭代，迭代的停止条件是：所有都收敛。迭代步骤为：
    - 对每一个，从方程中计算出：
    - 更新的值：。如果不是所有都收敛，继续迭代。
  - 迭代终止时，。

4.3.2 拟牛顿法

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

其中：。

学习的优化目标是最大化对数似然函数。

令：

于是学习优化目标是最小化。
计算梯度:
CRF 学习的 BFGS算法：
- 输入：
  - 特征函数
  - 经验分布
  - 目标函数
  - 梯度
  - 精度要求
- 输出：
  - 最优参数值
  - 最优模型
- 算法步骤：
  - 选定初始点，取为正定对阵矩阵，置
  - 计算 :
    - 若，停止计算，得到
    - 若 :
      - 由求得
      - 一维搜索：求出：
      - 置
      - 计算。若，停止计算，得到
      - 否则计算 :
        
        其中：
      - 置，继续迭代。

4.4 预测算法

给定条件随机场以及输入序列（观测序列）的情况下，求条件概率最大的输出序列（标记序列），其中。
根据条件随机场的简化形式：

其中。

于是：

考虑到与无关，于是：

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

其中：

其中就是非规范化概率。
定义局部特征向量：

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

于是：。

为了便于统一描述，这里引入了两个人工标记：。它们具有唯一的、固定的取值（不是随机变量）。
维特比算法用动态规划来求解条件随机场的预测问题。它用动态规划求解概率最大路径（最优路径），这时一条路径对应着一个标记序列。
- 根据动态规划原理，最优路径具有这样的特性：如果最优路径在位置通过结点，则这一路径从结点到终点的部分路径，对于从到的所有可能路径来说，也必须是最优的。
- 只需要从位置开始，递推地计算从位置 1 到位置且位置的标记为的各条部分路径的最大非规范化概率。
  
  于是在位置的最大非规范化概率即为最优路径的非规范化概率，最优路径的终结点也同时得到。
- 之后为了找出最优路径的各个结点，从终结点开始，由后向前逐步求得结点，得到最优路径。
假设标记的取值集合为，其中是标记的取值个数。
- 首先求出位置 1 的各个标记值的非规范化概率：
- 根据递推公式，求出到位置的各个标记取值的非规范化概率的最大值，同时记录非规范化概率最大值的路径：
  - 其中为：到位置、且标记取值为的非规范化概率的最大值。
  - 为：到位置且标记取值为的最优路径中，位置处的标记的取值的编号。
- 到时，这时求得非规范化概率的最大值，以及最优路径的终点：
- 根据最优路径得到：。
  
  最终得到最优路径：。
CRF 预测的维特比算法：
- - 输入：
    - 模型特征向量，其中标记的取值集合为
    - 权值向量
    - 观测序列
  - 输出：最优路径
  - 算法步骤：
    - 初始化：。
    - 递推：对：
    - 终止：
    - 回溯路径：。
    - 返回路径：。

4.5 词性标注任务

在词性标注任务中，给定单词序列，需要给出每个单词对应的词性。如： 他们吃苹果 对应的标注序列为 代词动词名词 。
- 给定一个单词序列，可选的标注序列有很多种，需要从中挑选出一个最靠谱的作为标注结果。
- 标注序列是否靠谱，是通过利用特征函数来对序列打分来获得。序列的得分越高（意味着非规范化概率越大），则越靠谱。
CRF 中的特征函数接受四个参数：
- 单词序列。
- 位置，表示序列中第个单词。
- 标记，表示第个单词的标注词性。
- 标记，表示第个单词的标注词性。
特征函数的输出值为，表示满足/不满足这个特征。
每个特征函数对应一个权重。
- 若权重为正，则说明该特征贡献一个正的分数；如果权重为负，则说明该特征贡献一个负的分数。
- 权重越大，则说明该特征靠谱的可能性越大（对于正的权重），或者该特征不靠谱的程度越大（对于负的权重）。
- 该权重是模型的参数，从训练集中训练得到。

4.6 CRF 与 HMM 模型

设已知隐马尔科夫模型的参数，则给定观察序列，以及标记序列，其出现的概率为：
- 对于 HMM 中的每一个转移概率，定义特征函数：
  
  定义其权重为：。
- 对于 HMM中每一个发射概率，定义特征函数：
  
  定义其权重为：。
- 则有：
  
  其中为人工引入的结点。
  
  因此的物理意义为：所有特征函数在所有位置之和。将其归一化之后就得到了CRF的公式。
从推导中可以看出：每一个HMM模型都等价于某个CRF模型。
- CRF模型比HMM模型更强大。
  
  因为CRF模型能定义数量更多、更丰富多样的特征函数，能使用任意形式的权重。
- HMM模型中当前的标注结果只依赖于当前的单词，以及前一个标注结果。
- HMM模型转换过来的形式中，权重是条件概率的对数，因此权重都是负的。
HMM 是生成式模型，而CRF是判别式模型
- 生成式模型对联合概率建模，可以生成样本。
  
  生成式模型定义的是联合概率，必须列举所有观察序列的可能值。在很多场景下，这是很困难的。
- 判别式模型对条件概率建模，无法生成样本，只能判断分类。