CRF

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的序列标注问题中，我们要计算的是条件概率。形式为对数线性模型。

逐标签Softmax是一种简单有效的方法，但有时候会出现不合理的结果。

逐标签Softmax方案会出问题，归根结底就是我们在建模的时候，使用了输出完全独立的朴素假设（一元模型），但我们真实的输出序列又是上下文有关的，因此造成了优化目标与模型假设不吻合。能不能直接把上下文考虑进去呢？很简单，使用二元模型即可。

这里为了使得表达式更好看一些，我把输入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是线程数量。