基于统计学习方法角度谈谈CRF

（白宁超 2018年8月29日15:44:48）

【摘要】：条件随机场用于序列标注，数据分割等自然语言处理中，表现出很好的效果。在中文分词、中文人名识别和歧义消解等任务中都有应用。本文源于笔者做语句识别序列标注过程中，对条件随机场的了解，逐步研究基于自然语言处理方面的应用。成文主要源于自然语言处理、机器学习、统计学习方法和部分网上资料对CRF介绍的相关的相关，最后进行大量研究整理汇总成体系知识。文章布局如下：第一节介绍CRF相关的基础统计知识；第二节介绍基于自然语言角度的CRF介绍；第三节基于机器学习角度对CRF介绍，第四节基于统计学习角度对相关知识介绍；第五节对统计学习深度介绍CRF，可以作为了解内容。（本文原创，转载请注明出处：基于统计学习方法角度谈谈CRF。)

引言

---

条件随机场（CRF）：是给定一组输入随机变量条件下，另一组输出随机变量的条件概率分布模型，其特点是假设输出随机变量构成马尔科夫随机场，条件随机场可用于不同预测问题，由输入序列对输出序列预测的判别式模型，形式为对数线性模型，其学习方法通常是极大似然估计。

1 条件随机场(CRF)的定义与形式

---

简单的说，条件随机场(CRF)类似于MRF，只不过CRF比MRF多了一个观察集合，或者说，CRF本质上就是给定了观察值集合的MRF。

条件随机场：设G=(V,E)是一个无向图，Y={Y_v|v∈V}是以G中节点v为索引的随机变量Y_v构成的集合。在给定X的条件下，如果每个随机变量Y_v服从马尔可夫性，即，则条件概率分布P(Y|X)就是一个条件随机场。上式中的w ~ v表示在图G=(V, E)中与节点v有边连接的所有节点，w≠v表示v以外的所有节点，Y_v,Y_u, Y_w为w对节点v，u，w对应的随机变量。

线性链条件随机场：  

设X = (X1, X2,..., Xn), Y = (Y1, Y2, ..., Yn)均为线性链表示的随机变量序列，若在给定随机变量序列X的条件下，随机变量序列Y的条件概率分布P(Y|X)构成条件随机场，即满足马尔可夫性(见本文最开始的“模型定义”部分)： P(Y_i| X, Y₁, ..., Y_i-1, Y_i+1, ...., Y_n)= P(Y_i | X, Y_i-1, Y_i+1)  i= 1, 2, ..., n (在i=1和n时只考虑单边)，则称P(Y|X)为线性链条件随机场。

注意：在标注问题中，X表示输入观测序列，Y表示对应的输出标记序列或状态序列。

2 条件随机场的参数化形式

---

P(Y|X)为线性链条件随机场，则在随机变量X取值为x的条件下，随机变量Y取值为y的条件概率具有如下形式：

 

其中，

式中，tk和sl是特征函数，λk和μl是对应的权值。Z(x)是规范化因子，求和时在所有可能的输出序列上进行的。

通常：特征函数t和s取值是1或0，当满足特征条件取值1，反之取值0，条件随机场完全由特征函数t，s和对应的数值λ，μ确定。

注意：线性CRF也是对数性模型。

实例解析：

设有一个天气预测问题：输入观察序列（连续三天的天气情况）为X = (X1, X2, X3)，输出标记序列（每天对应天气热冷的预测）为 Y = (Y1, Y2, Y3)， Y1, Y2, Y3 的取值于y= {H, C},其中H表示天热，C表示天冷。假设特征tk,sl和对应的权值λk，μl如下：

其中，上式代表着特征值为H的条件，即：y_i-1= H, y_i=C, x, i = 2, 3 时特征值取1。而特征值取0的条件被省略了。

PS：如果写全的话是这样：

于是对给定的观测序列x，求标记序列为y =(y1, y2, y3) = (H, C, C),即第一天热，第二天第三天连续冷的非规范化条件概率（即没有除以规范化因子的条件概率）

实例分析：

由以上问题可知，观察序列是天数的集合，标记序列是对应天气热冷的集合，由此分析显然是随机条件场的编码问题，基于随机条件场，可以将上述情形转换为图形化形式分析，然后进行模型构建，算法实现，算法优化和结果分析即可。本节重点实现分析，图形表示，模型构建。

天气预测问题转化为图形表示如下：

如图所示，横坐标x1，x2，x3分别对应天，是观察序列具备时序性，纵坐标是标记序列即可能隐藏的所有标记情况，start和end表示开始和结束状态（这点参照笔者Viterbi算法一节的介绍），其中t表示转移概率，t=0.5有具体权值的，标注转移概率是50%机会。X对应的s表示发射概率或者生产概率，显然，如上满足条件随机场，回顾下条件随机场模型，线性链条件随机场模型为：

于是对给定的观测序列x，标记序列y=(H,C,C)的非规范化条件概率为

上式数值计算，参照已知条件和图形分析，很容易计算，这里具体计算过程省略。

3 条件随机场的简化形式

---

将局部特征转化为一个全局特征函数，可将CRF写成权值向量和特征向量的内积形式即是条件随机场的简化形式，具体参见如下笔记：

① 将转移特征和状态特征以及其数值用统一符号表示，设有K1个转移贴纸，K2个状态特征，K=K1+K2，记：

② 对转移状态各个位置i求和，记作：

③ 用w_k表示特征f_k(y,x)的权值，即：

           

④ 于是，条件随机场可表示为

                       

⑤ 以w表示权值向量，即

                      

⑥ 以F(y, x)表示全局特征向量，即

                  

则条件随机场可以写成向量w与F(y, x)的内积的形势：

 

4 条件随机场预测算法

---

 形式化描述： 条件随机场的预测问题是给定义条件随机场P(Y|X)和输入序列(观测序列)x，求条件概率最大的输出序列(标记序列)y*，即对观测序列进行标注。 条件随机场的预测算法是著名的维特比算法。

你对维特比算法是什么就有概念了吧，下面来看看其数学描述。维特比算法不做深入讲解，如果读者还不清楚，参考本人系列文章之揭秘马尔科夫模型系统文章，有专门章节详细介绍viterbi算法。

    

这里，路径表示标记序列，其中

           

注意，这时只需计算非规范化概率，而不必计算概论，可以大大提高效率。

为了求解最优路径，将式写成如下形式：

            

其中

                

就是局部特征向量。

下面叙述维特比算法。

实例解析

用维特比算法求给定的输入序列(观测序列)x对应的输出序列(标记序列)y* = (y₁^*, y₂^*, y₃^*)；

解析：

1)第一步初始化：因为y1=1和y1=2是最初，所以就不用考虑转移的情况了(实际上也没有“表达从y0转移到y1的情况”的t函数(转移函数))，直接从状态函数(s函数中找)，发现，s1和s2分别对应y1=1和y1=2，说明y1=1和y1=2这个状态都是存在的，而s1和s2的权值分别是1和0.5，且上面列出的s函数们和t函数们值都为1，所以y1=1和y2=1的可能性分别是1和0.5。所以，到达y1的非规范化概率最大值为：δ₁(1) = 1，δ₁(2) = 0.5。

2)第二步递推：i=2(达第二处目的地集合{y2=1, y2=2})：首先是路线(仅说明到达y2=1的情况)：

上图可知，到达y2=1的路线有如下几条：

 路线1：从y1=1出发 ----(经过t2)---->到达y2=1；

 路线2：从y1=2出发 ----(经过t4)---->到达y2=1；

 接着是状态(仅说明到达y2=1的情况)：

根据题目可知：i=2时的状态函数只有s2和s3，而y2=1对应的函数是s3

所以到达y2=1的非规范化概率最大值为：δ₂(1) = max{1+λ₂t₂ + u₃s₃,0.5 + λ₄t₄ + u₃s₃}= 2.4

非规范化概率最大值的路径为： ψ₂(1) = 1

δ₂(2)同理。

i=3也一样（只不过对于δ₃(1)中的u₅s₅，我认为应该是u₃s₃，先不说s3对应的是y3=1的情况，而且原题中根本没有s5函数）。

3)第三步终止：这步就简单了，在δ₃(l)中δ₃(1) = 4.3最大，所以y3中取1的可能性最大，即y₃^*=1。

4)第四步返回：然后反着推：

从y2的哪个值到y3可能性最大呢？在第二部已经解出：ψ₃(1) = 2，即y2到达y3=1的路线中权值最大的是y2=2，即y₂^*=2。

同理，从y1=1到y2=2的可能性最大，即y₁^*=1。

5)就得到标记序列:*= (y₁^*, y₂^*, y₃^*)= (1, 2, 1)

5 参考文献

---

【1】 数学之美 吴军 著

【2】 机器学习  周志华 著

【3】 统计自然语言处理 宗成庆 著（第二版）

【4】 统计学习方法（191---208） 李航

【5】 知乎 网络资源