CRF算法学习——自己动手实现一个简单的CRF分词(java)

这篇博客主要分三个点吧,首先理解CRF,然后利用CRF++去做参数训练,最后写一个CRF分词的程序,具体程序在我的GitHub上。
参考书籍:《统计学习方法》、《PRML》

CRF算法理解

书上的定义:条件随机场(conditional random field, CRF)是给定一组输入随机变量条件下另一组输出随机变量的条件概率分布模型,其特点是假设输出随机变量构成马尔可夫随机场。条件随机场可以用于不同的预测问题,本章主要讲述线性链(linear chain)条件随机场在标注问题的应用,这时问题变成了由输入序列对输出序列预测的判别模型,形式为对数线性模型,其学习方法通常是极大似然估计或正则化的极大似然估计。
说人话,就是上上一篇讲HMM的时候已经提前说过:“CRF是判别式模型,就是训练得到的是P(Y|X)的映射的参数;而HMM是生成式模型,训练P(X,Y)的参数,然后P(X)一出现,P(Y|X)就得到了。”
而且一般在谈序列预测问题的时候,说的CRF就是线性链CRF,这个在2001年的时候才被提出。

从RF到MRF到CRF到Linear Chain CRF

RF是随机场,MRF是马尔可夫随机场,又称概率图模型,CRF是条件随机场,Linear Chain CRF是线性链CRF

拿“一个群体中人的性格,群体中一个人的性格可能会影响另一个的性格”举例:
定义“我从小到大所有认识的人+我女朋友从小到大所有认识的人”就是这个空间,“空间里每个人的性格”都是一个变量,那么:

RF :这个空间里每个人的性格变量都是随机的,所有人的性格变量的集合就是一个RF

MRF :假设现在有这么个条件,我不认识的人根本不影响我的性格(成对马尔可夫性),那么就是MRF了。

CRF:刚才只说了性格变量互相影响,说的很虚,因为你需要有一些东西衡量性格呀,所以我又假设了一个条件,假设我能观测到“所有人在认识的人和她接触时她的笑的时间”,那么这时候的性格影响就不是那么不可描述了,我说她天生笑的多就是天生就是性格乐观,这个人和这个人一起跟她说话他笑得比平均高,那就是这两个人对他性格乐观的影响大,这时候你把笑声考虑进去研究性格,出现了条件概率,那就是CRF了。

线性链CRF:上面说的每个人可能认识很多人,这个情况就很复杂,你现在在假设一种情况,每个人都有编号,你只认识比你大一号或者比你小一号的那两个人,于是你的性格就只受那两个人的性格影响,而不管什么人,他们发出笑声还是能或多或少影响你,那就是线性链CRF

如果再严格一点,不是所有人的笑声影响你,就你自己真的笑了才影响你,那就是X和Y结构相同的线性链CRF,这样的好处在于最大团的定义的话就是任意被连接两个点都是最大团,比较好计算图概率

其他关系

先说M和C:

M就是马尔可夫的意思,代表具有三种马尔可夫性(等价的,满足一个另外两个自然满足),就是和我没关系的点根本不影响我的概率分布(成对马尔可夫性);只有和我有关系的才能影响我的概率分布,整个群体对我的概率分布就是周围人影响下的我的概率分布(局部马尔可夫性),我的高中同学和大学同学,这两拨同学之间互不认识,那么我对这两拨同学的概率分布的影响是独立的(全局马尔可夫性)
C就是条件,没有C就是意味着探讨P(Y)的分布,有了C就是探讨P(Y|X),所以这个C是条件概率下的那个条件的意思。

细说马尔可夫的意义

上回HMM的东西太多,就没说啥,这回特别想说一下这个人——安德雷·安德耶维齐·马尔可夫,没有这个人(不光他自己)有可能概率论都不算数学了,百度百科有一段很夸张的说辞,不过也有道理:

在当代科学与社会的广阔天地里,人们都可以看到一种叫作随机过程的数学模型:从银河亮度的起伏到星系空间的物质分布、从分子的布朗运动到原子的蜕变过程,从化学反应动力学到电话通讯理论、从谣言的传播到传染病的流行、从市场预测到密码破译,随机过程理论及其应用几乎无所不在。人类历史上第一个从理论上提出并加以研究的过程模型是马尔科夫链,它是马尔科夫对概率论乃至人类思想发展作出的又一伟大贡献。

通俗理解:一只被切除了大脑的白鼠在若干个洞穴间的蹿动就构成一个马尔科夫链。因为这只白鼠已没有了记忆,瞬间而生的念头决定了它从一个洞穴蹿到另一个洞穴;当其所在位置确定时,它下一步蹿往何处与它以往经过的路径无关
哲学意义因为现在,过去和未来毫不相干。

CRF的各种表达形式

参数化表达形式



Z就是各种可能的输出序列的情况概率之和。

t是转移特征函数,可以类比转移概率矩阵中下雨天—>晴天转移这件事,λ就像下雨天—>晴天转移的概率。

s是状态特征函数,可以类比观测概率矩阵中出去运动是晴天这件事,μ就是出去运动是晴天的概率。
每个y2计算的时候不像原来以来那么直接,要考虑

参数简化表达形式


大概就是都是转移特征函数和系数相乘,那就合在一起吧。含义和上面差不多。

矩阵形式


和上面没什么两样,尤其是java的矩阵又不好用,还不如上面拆开写利用实现java程序。

HMM、线性链CRF和MEMM在标注问题上的差异

有向图和无向图

其实线性链CRF和HMM关键的差别就在于HMM是有向图,CRF是无向图。他们俩的概率计算本身就是不一样的,这一部分引用了 https://blog.csdn.net/scotfield_msn/article/details/79195517.



CRF好在那里?对比HMM和MEMM

HMM太讲究了

HMM有一种很讲究很谨慎的感觉,当前的隐藏状态依赖于前一个隐藏状态(齐次马尔可夫性假设),不乱搞暧昧。像下面这样:

CRF很随性,隐藏状态可以依赖于观测状态,只依赖于当前的观测状态肯定可以,不过你可以自己定一些比如依赖前一个或者后一个的观测状态,而隐藏状态也可以像HMM只依赖于前一个隐藏状态,不过你可以自己定依赖于前两个隐藏状态;对于观测状态来说,我现在可以构建多种特征函数直接对多个观测状态进行组合以后特征化,而不是只有一个观测对应的各种隐藏概率。

CRF没有HMM那样严格的独立性假设条件,因而可以容纳任意的上下文信息。所以CRF一般都比HMM的拟合效果要强,这是可以预见的。

MEMM的状态偏置

这个问题真的是很多博客都提到的问题,这里提它就一个目的,想说CRF比MEMM好。
MEMM是最大熵马尔科夫模型,有向图,属于判别式模型,和CRF比较像,因为也是定义各种关于X->Y的特征函数,所以是长下面这个样子。

假设一种情况,如下所示,各种隐藏状态转移分布非常不均匀。

于是计算路径概率会得到:路径1-1-1-1的概率: 0.4 * 0.45 * 0.5 = 0.09是最优的。
可是看图的时候,你会觉得每次隐藏为1的时候,明明是下一个变成2的概率比还是1的概率大,这不符合Viterbi算法(全局最优)进行解码的预期结果。
从MEMM的公式来看,对于每一个t时刻,状态i+1都是对前一个状态i进行局部归一化,所以当前一个状态转换的状态非常多时,这个转移概率就变低了。

下面是正确的viterbi算法的公式,MEMM使用这个公式的时候,第二部分就是来自于不同的状态的i-1时刻的概率就要被归一化,于是公式的第二部分就会成i的下一个状态可变化越多这个值就越小,这个规范因子Z(O)时时刻刻影响着某个时刻序列的状态选择,时时刻刻都在追求局部最优,这就产生了很多问题,而不像Viterbi所以为的全局最优,可能局部非最优。

总结:造成这一问题的根本原因是每个节点分支数不同,由于MEMM的局部归一化特性,使得转出概率的分布不均衡,最终导致状态的转移存在不公平的情况。
也正是MEMM的不完美,CMU的教授John Lafferty提出了更先进的CRF模型。
CRF是对一个序列全部的观测节点进行归一化,规范因子 Z(O) 是因为不规范化不会影响取最大值后的比较,所以Viterbi全局最优思想不影响。

再说生成式和判别式

其实开始我一直有个问题,比如分词问题不是都有观测序列O,去找隐藏状态I,不都是P(I|O)的问题,为什么会有生成式和判别式呢?
后来我想明白在于一个模型的参数是什么,比如HMM的i1到o1的那条线,其实都是在说观测o1状态i1怎么样的概率,你知道初始状态分布,你知道i1的情况,所以你知道同一个o1,不同的i1的状态哪个i1好,对于MEMM是o1到i1的那条线,他就是知道o1怎么对应不同的i1,具体i1的情况根本不知道

CRF面对的三个问题

概率计算:前向后向
参数学习:拟牛顿法、梯度下降等等
序列预测:viterbi

CRF++使用

CRF++地址
基本的安装还有一些例子怎么用,上面的里面说的都有。CRF++主要能训练模型里各种特征函数的参数,然后我们可以直接使用去进行分词。
主要理解比较麻烦的是,里面那些东西怎么对应在上面讲的各种东西。

CRF++里的特征模版

特征模版的定义就是傻瓜式的生成特征函数。当然你可以定义很多特征函数,但是分词的时候那么多字,特征函数又是差不多的结构,所以可以自己定义特征模版,让模版生成特征函数。
CRF++里的特征模版有两种U和B,正好对应那条竖着的线和横着的线
U是对于当前观测Ot来说,前前后后组合得到的各种观测O对当前状态It的影响
B是对于当前状态It开始,前前后后组合得到的各种观测I对当前状态It的影响
具体理解可以参考以下几个答案
crf++里的特征模板得怎么理解? - 苏克的回答 - 知乎
crf++里的特征模板得怎么理解? - 中年英雄王叔叔的回答 - 知乎
假如有n个unigram特征模板,m个位置(句子长度),L个标签个数:
U模版会产生n* m * L个特征函数,而B模版会n * L * L * m个特征函数
Standford NLP、Hanlp、Ansj都是使用的特征模版这个概念。

CRF++生成Model文件解析

注意train的时候,命令行最后加上-t,这样会生成txt文件,自己训练好打开大概就是这个样子

对照代码看

具体代码可以去https://github.com/1000-7/xinlp/blob/master/src/main/java/segment/crf/XinCRFModel.java,很多地方借用Hanlp的处理方式,但是没有什么封装,看起来比较直接
前四行是模型的一些描述信息,直接打印,然后空一行

然后是I的取值集合{B,E,M,S}

然后是特征模版信息,用FeatureTemplate封装了一下

然后是特征模版生成的特征函数信息,使用TreeMap即存取key-value的信息,又对key进行排序,以便读取特征函数对应的参数。

然后读取对应的参数,如果有B,先读转移函数的参数

然后读U模版的观测函数的参数,

好,全部拿到,就可以进行Viterbi分词了。

分词结果截图

发表评论

电子邮件地址不会被公开。