CRF简介
逐标签Softmax
CRF常见于序列标注相关的任务中。假如我们的模型输入为Q,输出目标是一个序列a1,a2,…,an,那么按照我们通常的建模逻辑,我们当然是希望目标序列的概率最大P(a1,a2,…,an|Q)。
不管用传统方法还是用深度学习方法,直接对完整的序列建模是比较艰难的,因此我们通常会使用一些假设来简化它,比如直接使用朴素假设,就得到P(a1,a2,…,an|Q)=P(a1|Q)P(a2|Q)…P(an|Q)。
注意这里的Q不一定是原始输入,比如它可能是经过多层LSTM之后的隐藏输出q1,q2,…,qn,并且我们认为全局的关联意境由前面的模型捕捉完成了,因此在最后一步,我们可以认为特征之间互不相关,那么:
- P(a1|Q)=P(a1|q1,q2,…,qn)=P(a1|q1)
- P(a2|Q)=P(a2|q1,q2,…,qn)=P(a2|q2)
- P(an|Q)=P(an|q1,q2,…,qn)=P(an|qn)
从而P(a1,a2,…,an|Q)=P(a1|q1)P(a2|q2)…P(an|qn)
这就得到了我们最常用的方案:直接逐标签输出最大概率的那个标签。而前面的模型通常是多层的双向LSTM。
CRF
CRF的序列标注问题中,我们要计算的是条件概率。形式为对数线性模型。
逐标签Softmax是一种简单有效的方法,但有时候会出现不合理的结果。
逐标签Softmax方案会出问题,归根结底就是我们在建模的时候,使用了输出完全独立的朴素假设(一元模型),但我们真实的输出序列又是上下文有关的,因此造成了优化目标与模型假设不吻合。能不能直接把上下文考虑进去呢?很简单,使用二元模型即可。
即:PQ(a1,a2,…,an)=PQ(a1)PQ(a2|a1)PQ(a3|a1,a2)…PQ(an|a1,…,an−1)=PQ(a1)PQ(a2|a1)PQ(a3|a2)…PQ(an|an−1)
这里为了使得表达式更好看一些,我把输入Q放到了下标中。这已经很接近CRF了!
CRF的做法非常一般,首先它定义了一个函数f(x,y;Q)(它可能是一些简单的特征函数之和,但具体的形式其实不重要),然后直接令:
PQ(a1,a2,…,an)=(1/Z)exp(∑k f(ak−1,ak;Q))
其中Z是归一化因子。跟前一式相比,两者的区别在于,PQ(ak|ak−1)是有概率意义的(条件概率),而单项的exp(f(ak−1,ak;Q))/Z是没有概率意义的,所以CRF是更一般的形式。这就是CRF的全部。
线性链CRF
这里介绍一个经常用的版本:线性链CRF,它就是tensorflow自带的版本。
PQ(a1,a2,…,an)=PQ(a1)PQ(a2|a1)PQ(a3|a2)…PQ(an|an−1)=PQ(a1) PQ(a1,a2)/(PQ(a1)PQ(a2)) PQ(a2) PQ(a2,a3)/(PQ(a2)PQ(a3)) PQ(a3) … PQ(an−1,an)/(PQ(an−1)PQ(an)) PQ(an)
根据CRF的一般思路,我们放弃每一项的概率意义,直接写出
PQ(a1,a2,…,an)=(1/Z)exp[f(a1;Q)+g(a1,a2;Q)+f(a2;Q)+……+g(an−1,an;Q)+f(an;Q)]
所谓线性链,就是直接认为函数g实际上跟Q没关系,任何情况都共用一个g(ak−1,ak),这样它不过是个待确定的矩阵而已。剩下的则跟逐标签Softmax的情形差不多了,认为f(ak;Q)=f(ak;qk)。按照极大似然的思想,loss为-log(PQ)。
相对于逐标签Softmax,CRF不过是换了一个loss罢了,当然,还多了一个互信息矩阵,并且解码的时候需要用到viterbi算法。
线性链CRF和HMM
从形式看,线性链CRF跟HMM是没有区别的。它们的区别在于,CRF去掉了每一项的概率意义,直接定义了f(a1;Q)、g(a2,a1;Q)这些函数表示它们的关系(你可以认为是某种得分),然后最后再整体归一化。
这样子操作的话,HMM实际上就是描述每个点的概率分布,而CRF则直接描述每条路径的概率,由于它的建模对象是一条路径而不是逐点,而已在全局规划上效果会更好。
CRF的三个基本问题
概率计算问题
在已知参数和求给定观测序列的概率的时候,只需要依次从前到后计算每一个最大团的向量乘积即可。
学习问题
具体的实现算法有改进的迭代尺度法、梯度下降法以及拟牛顿法。
http://x-algo.cn/index.php/2016/02/18/iis-improved-iterative-scaling-improved-iteration-method/
预测问题
维特比算法。
预测问题,就是从多个候选标注中挑选出来一种标注概率最高的。由于归一化因子不影响值的比较,所以只需要比较分子部分的非规范化概率。
CRF的keras实现
CRF引入了输出的关联;当然,如果仅仅是引入输出的关联,还不仅仅是CRF的全部,CRF的真正精巧的地方,是它以路径为单位,考虑的是路径的概率。
逐帧Softmax和CRF的根本不同了:前者将序列标注看成是n个k分类问题,后者将序列标注看成是1个k^n分类问题。
在CRF的序列标注问题中,我们要计算的是条件概率:
P(y1,…,yn|x1,…,xn)=P(y1,…,yn|x),x=(x1,…,xn)
为了得到这个概率的估计,CRF做了两个假设:
- 假设一:该分布是指数族分布。
- 假设二:输出之间的关联仅发生在相邻位置,并且关联是指数加性的。
损失函数
为了训练CRF模型,用最大似然函数−logP(y1,…,yn|x)做为损失函数。
归一化因子的计算
logZ(x)的计算。
寻找最优路径
模型训练完成之后,寻找最优路径的方法是:viterbi算法。
CRF++
源码分析
源码中包括了拟牛顿法的目标函数、梯度、L2正则化、L-BFGS优化、概率图构建、前向后向算法、维特比算法。
平均地将句子分给每个线程。每个线程的工作其实只是计算梯度。
工具包文件
- doc文件夹:就是官方主页的内容。
- example文件夹:有四个任务的训练数据、测试数据和模板文件。
- sdk文件夹:CRF++的头文件和静态链接库。
- crf_learn:CRF++的训练程序。
- crf_test:CRF++的预测程序
- libcrfpp.so:训练程序和预测程序需要使用的链接库。
实际上,需要使用的就是crf_learn,crf_test和libcrfpp.s0这三个文件。
模板文件
- Unigram template:first character,’U’。
- Bigram template:first character,’B’。
训练命令
crf_learn -f 3 -p 4 -c 4.0 template_file train_file model_file > train.rst
有四个主要的参数可以调整:
- -a CRF-L2 or CRF-L1。规范化算法选择。默认是CRF-L2。一般来说L2算法效果要比L1算法稍微好一点,虽然L1算法中非零特征的数值要比L2中大幅度的小。
- -c float。这个参数设置CRF的hyper-parameter。c的数值越大,CRF拟合训练数据的程度越高。这个参数可以调整过度拟合和不拟合之间的平衡度。这个参数可以通过交叉验证等方法寻找较优的参数。
- -f NUM。这个参数设置特征的cut-off threshold。CRF++使用训练数据中至少NUM次出现的特征。默认值为1。当使用CRF++到大规模数据时,只出现一次的特征可能会有几百万,这个选项就会在这样的情况下起到作用。
- -p NUM。如果电脑有多个CPU,那么那么可以通过多线程提升训练速度。NUM是线程数量。
测试命令
crf_test -m model_file test_files > test.rst
CRF++没有单独的结果文件,预测结果通过标准输出流输出了,因此上面的命令将结果重定向到文件中去。结果文件比测试文件多了一列,即为预测的标签。我们可以通过计算最后两列,一列是标注的标签,一列是预测的标签,来得到标签预测的准确率。
CRF++词性标注
训练和测试的语料都是人民日报98年标注语料,训练和测试比例是10:1。
直接通过CRF++标注词性的准确率:0.933882。
特征有一千多万个,训练时间比较长。机器cpu是48核,通过crf++,指定并线数量-p为40,训练了大概七个小时才结束。
CRF++地名实体识别(特征为词性和词)
这里使用的语料库是1998年1月人民日报语料集。
类似使用CRF实现分词和词性标注,地域识别也是需要生成相应的tag进行标注。
最终学习出来的模型,对复杂的地名识别准确率(F值)非常低,推测是预料中对地名的标注多处是前后矛盾。例如 [华南/ns 地区/n]ns 标为地名实体,但是 东北/f 地区/n 确分开标注,类似错误还有很多。
CRF++中文分词
生成训练数据的时候,支持4tag和6tag两个格式,6tag的格式是:S 单个词;B 词首;E 词尾;M1/M2/M 词中。4tag和6tag的区别就是没有词中顺序状态。
使用人民日报语料,90%数据作为训练数据,10%的数据作为测试数据。
6Tag的效果比4Tag有细微的差距,当然是6Tag好。
6Tag的标注方法差异:
- 把M放在E之前:发 B 展 M1 中 M2 国 M 家 E
- 把M放在B后:发 B 展 M 中 M1 国 M2 家 E
- 把M放在M1和M2之间:发 B 展 M1 中 M 国 M2 家 E
第1种方式效果最好,有细微的差距。