初学者报道(3) CRF 中文分词解码过程理解

好久没有来写文章了,这段时间我研究了一下CRF,也找人请教过,下面写下自己的一些理解,在网络上也找过CRF的资料,大多为英文,对于解码的描述,就说用viterbe 实现,如何实现,却很少提及,以下为我的理解,如有错误欢迎指正,这样可以帮助我理解,先行谢过!

一,标记问题解决分词:就是将 词语开始和结束的字标记出来,就能对一个句子完成分词,假设使用两个标记B (开始),E(结束)对句子进行处理,如:“民主是普世价值”,民B主E是B普B世E价B值E, 这样标记明确,分词结果就明确了。

二,如何找到最好的标记结果:知道如何用标记的方式解决分词,那么怎么为一个句子找到一个最好的标记序列呢,CRF为这样的问题提供了一个解决方案,对于输入序列X1,X2…Xn(对于分词,就是那个句子),求这个输入序列条件下 某个 标记序列(Y1,Y2…Yn)的概率 极值。

三,解码过程:

这里用一个例子来说明,对于CRF的原理,我不做详述,我是半吊子,怕解释不好,只说一下我理解的解码过程。

CRF的公式:P(y|x,λ)=Σj λjFj(y,x)/Z(x)     //这里的j都是下标

先说问题:

使用4标记,B-开始,O-单独成词,M-词语中间的字,E-结束,

特征:一元特征,V-1 当前字的前一个字,V0当前字,V1当前字的后一个字

二元特征,各标记间的转移特征

句子如下:

民   主   是   普   世   价   值

B     B    B    B   B    B    B

O    O   O    O   O    O     O

M   M   M   M   M   M   M

E     E    E    E    E    E     E

Viterbe解码就是在以上由标记组成的 数组中 搜索一条 最优的路径。

对于每一列的每一个标记,我们都要计算到达该标记的分数,这个分数由三部分组成,它本身的一元特征权重W,它前面一个字标记的 路径分数PreScore,前面一个字标记到当前标记转移特征权重TransW,

1. 计算第一列的分数(score),对于,‘民’来说,我们要算 B,O,M,E的Score,因为是第一列,所以PreSocre和TransW都是0,就不用计算,只需要计算自己的一元特征的权重:

对于标记,B,我们计算它的Score,记为S1B=W1B=w(null,民,B)+w(民,B)+w(民,B,主)  //这些特征的意思是: (null,民,B),当前字为 ‘民’标记为B,前面一个字为空,(民,B):当前字为‘民’,标记为B,(民,B,主):当前字为’民’,标记为B,当前字的后一个字为‘主’。特征的权重都是在训练时得到的。

对于标记,O,M,E,一样要计算W1O,W1M,W1E,从而得到分数S1O,S1M,S1E

2.对于第二列,首先要计算是每个标记的 一元权重W2B,W2O,W2M,W2E.

对于B,到达该标记的最大分数为:S2B=Max((v(BB)+S1B),(v(OB)+S1O),(v(MB)+S1M),(v(EB)+S1E))+W2B,其中v(BB)等为B到B的转移特征的权重。这个也是由训练得到的。同样对于第二列的O,M,E也要计算S2O,S2M,S2E

3.一直计算到最后一列,‘值’字的所有标记,得到S7B,S7O,S7M,S7E.比较这四个值中的最大值,即为最优路径的分数,然后以该值的标记点为始点 回溯得到最优路径(这里在计算过程中,要记录到达该标记的前一个标记,用于回溯)

终于写好!:)

 

此条目发表在中文分词, 条件随机场, 自然语言处理分类目录。将固定链接加入收藏夹。

初学者报道(3) CRF 中文分词解码过程理解》有 31 条评论

  1. 52nlp说:

    辛苦了,非常感谢!

    [回复]

  2. gladys说:

    S2B=Max((v(BB)+S1B),(v(OB)+S1O),(v(MB)+S1M),(v(EB)+S1E)+W2B,
    请问这个公式是不是少了个右括号,因为我是第一次想学习一下条件随机场,所以对每一句话都看的很细。是不是应该写成:
    S2B=Max((v(BB)+S1B),(v(OB)+S1O),(v(MB)+S1M),(v(EB)+S1E))+W2B 呢?如果我错了的话恳求及时纠正,因为这是我第一次认真的想学会CRF,如果我第一次就搞错了,以后也会一直错下去的。

    [回复]

    ricky 回复:

    谢谢你仔细的阅读,你是对的,我已经做了修正,抱歉给你带来困扰!
    如果还有疑问或文章中有错误之处还请指正!大家相互学习!

    [回复]

  3. goog说:

    真的好,首次了解crf里面。

    [回复]

  4. ricky说:

    谢谢你们积极的评论!!!!

    [回复]

  5. sam说:

    S2B=Max((v(BB)+S1B),(v(OB)+S1O),(v(MB)+S1M),(v(EB)+S1E))+W2B
    这里有个疑问,这个地方v(BB)+S1B 是该用加号么?是不是该用乘号?

    [回复]

    sam 回复:

    另外,理论上来说,在对“主”进行标注的时候CRF应该也还要考虑“是”的标注结果作为条件的吧?而不仅仅是考虑“民”的标注结果。
    所以总的来看,CRF的工作机制应该是否应该是先通过考虑O序列预测出所有可能的S序列,然后才进行的整体的全局最优序列选择?
    个人观点,纯属讨论。

    [回复]

    ricky 回复:

    你的意思是,标记序列应该是 不仅考虑 前一个标记到 当前标记的转移概率,还要考虑 当前标记 到后一个标记的转移概率吗?
    我倒是觉得,在某一个时刻只能 考虑前一个标记到当期标记的转移概率,而不能考虑到 后面的标记,否则就不能用 vertibi 解码了。
    欢迎讨论!:)

    [回复]

    sam 回复:

    嗯,CRF++ 是一种chain 状的CRFs,所以只与前一个状态有关,你说的没错。呵呵~

    ricky 回复:

    这里的加号 ,是在转化为 求对数 Log之后的,
    所以是加号。

    [回复]

    sam 回复:

    明白了。

    [回复]

  6. 周立伟说:

    S1B=W1B=w(null,民,B)+w(民,B)+w(民,B,主) ,这里面w(民,B)和w(民,B,主)应该存在某种关系吧?w(民,B)在训练的时候是怎么统计的呢?是民单独成词的时候才计算,还是类似“民主”这种情况也计算在内?
    W2B~W7B只有两项:W2B=w(主,B)+w(主,B,是)……W7B=w(值,B)+w(值,B,null),我理解的对么?
    CRF我还没太看懂,不过看您这里面写的,感觉CRF和HMM有些相似,如果一元特征的权重,比如W1B=w(民,B),不考虑字和字之间的邻接关系,这样的话貌似就是HMM了?
    我是初学者,问题有点多,不好意思哈。如果方便的话请加我QQ:642380072,有很多CRF的问题想请教,谢谢。

    [回复]

    ricky 回复:

    1.这里我举例用了三个一元特征模板,如果你看到开源如CRF++里的特征模板,我的例子里的模板可以写成:U00:%x[-1,0]/%x[0,0]; U01:%x[0,0];U02:%x[0,0]/%x[1,0]。
    w(民,B) 训练时是要统计,民字 标记为B时的个数的,然后用公式算权重的。
    2.每个节点权重,应该包含三项,当前节点的一元权重,前一个节点的权重,前一个节点到当前节点的转移权重。你这里只列出了节点的一元权重。
    3.可以这么理解,CRF的特征可以设定的和HMM一样,当前节点的x和y的权重,相当于HMM的发射概率,然后就是各个y之间的状态转移概率。
    我也是初学者,对于训练的细节,我理解的也不透彻,我平时上班也不用qq的,你要是有什么问题可以给我发邮件,乐意交流,ricky.zhiyang#gmail.com (#是@)。不能保证及时回复,但一般会当天回复,不好意思!

    [回复]

    周立伟 回复:

    谢谢您的指点。针对第二个问题,每个节点权重的三项我都理解,我想问的是每个节点一元权重的计算:W1B=w(null,民,B)+w(民,B)+w(民,B,主),第一个节点一元权重包含三项,而后续节点应该只有两项吧?比如W2B=w(主,B)+w(主,B,是),没有w(民,B,主)这项,我理解的对么?

    [回复]

  7. 梦里不知身是客说:

    非常感谢博主,看了很多论文,看了一周多的文献,大部分CRF讲的都是公式的推导等,数学原理方面有些模糊的理解,但是没有实际的例子,所以总是感觉似是而非。非常感谢博主精彩的分析及举例,有恍然大悟的感觉。
    看前言楼主讲的是维特比算法的实现?看完感觉是历遍所有路径后然后反馈回去找一条最优路径?请问理解对吗?那么和穷举法有什么区别啊?

    [回复]

    ricky 回复:

    维特比算法的时间复杂度为n*m*m, n 是输入序列的长度,m是标记的个数,而穷举的时间复杂度是,m的n次方,维特比 就是解决穷举时间复杂度太高。
    在维特比算法过程中,每一步只保留了一个或几个最好的值,那些不可能到最佳路径的节点已经抛弃了,所以时间复杂度较 穷举低。

    [回复]

    梦里不知身是客 回复:

    也就是说,其一,放弃了不好的一些值;其二,利用了递推的方法,减少了运算次数?
    楼主举得例子是CRF的例子只不过是用维特比算法来解码的吧?在CRF的课件或者论文中,首先是用向前向后算法求出CRF的模型参数,然后用维特比算法来解码,不知道我的理解对不?
    最近看CRF,维特比似乎有些明白了,但是CRF不是很明白,貌似CRF只是比最大熵多了个全局概率?那他的优势在哪里?
    谢谢牛博主的教诲啊

    [回复]

    ricky 回复:

    我不是博主(52nlp), 我只是在这里写了个CRF的解码过程理解,牛,万不敢当,其实我也是个初学者。你说的CRF的向前和向后算法,以及训练过程,我不是很了解的。至于CRF的较最大熵的优势,大部分CRF的论文都说了,是路径的bias问题,最大熵只能找局部最优,CRF是全局最优,至于如何个全局最优,如何局部最优,我解释不好。
    你说你看过CRF的课件,不知道是什么样的课件,可否分享一下,我的邮箱是ricky.zhiyang@gmail.com, 待我学习一下,我们再讨论,共同学习,共同进步!多谢

    liu 回复:

    维特比算法实现是用的动态规划,不是穷举

    [回复]

  8. 梦里不知身是客说:

    你好,已经给你发了邮件,我从网上下的,评价比较好。我自己看的似懂非懂,希望能得到你的指教,谢谢啊

    [回复]

  9. 梦里不知身是客说:

    再次请问博主,那个归一化的Z是怎么求的啊?能举个例子吗?

    [回复]

    Isaac124 回复:

    Z就是把所有 Y 向量的情况代入进Z上面的分子,然后求和。

    [回复]

    Isaac124 回复:

    所以Z是 以X为参数的,也就是说给定不同的X向量的话,Z有不同的值。

    [回复]

  10. Isaac124说:

    看了一周的CRF,其中有些细节还是模糊,您的资料很好,解决了我一些疑问。我想问一下,如果您说您这个例子的unigram feature template是 U00:%x[-1,0]/%x[0,0]; U01:%x[0,0];U02:%x[0,0]/%x[1,0], 这个看上去跟您的例子是自恰的,就是说他们分别生成的 feature function sets是“if (前与当前一起是 民主,且当前输出是 E) true; else false”,“if (当前是 主,且当前输出是 E) true; else false”,“if (当前与之后是 主是,且当前输出是 E) true; else false” ,这三个分别对应您那三个w()权重function。 那么我一直不明白很多 template里还写 U00:%x[-1,0] 这样的,有什么意义呢?总是说这是前一行第一列的feature,但是这生成什么 feature function呢?如果单纯对前一个作分析,那么当前一行作为当前行的时候,自己的 U00:%x[0,0] 已经可以表达了,如果是要联系前一个和当前的关系,那么您的 U00:%x[-1,0]/%x[0,0] 这个才是对的啊。 急求解惑,万分感谢!

    [回复]

    ricky 回复:

    这里面的“当前” 指的是当前的 label,
    每个feature都要 和 当前的label 组合起来,表示一个特征。
    如果例子中有4个label, 那么U00:%x[0,0]就要与 4个label进行组合,统计4个U00:%x[0,0]的权重。
    U00:%x[-1,0]/%x[0,0] 这个特征模板依然要和当前的4个label进行组合,分别组成特征,统计权重。

    [回复]

  11. ricky说:

    说实话,我解释不好。
    公式有很多文章很多论文,http://www.52nlp.cn/%E6%9D%A1%E4%BB%B6%E9%9A%8F%E6%9C%BA%E5%9C%BA%E6%96%87%E7%8C%AE%E9%98%85%E8%AF%BB%E6%8C%87%E5%8D%97,这个链接可能有帮助,另外训练,可以看论文,也可以看CRF++的源码。

    [回复]

  12. Sanqiang说:

    能否问下 S1B W1B 中的S B分别是什么意思 是不是PreScore和TranW

    [回复]

  13. 勃沙特人说:

    如果“民”不在训练集中出现,在验证环节,如何计算权重?

    [回复]

  14. 勃沙特人说:

    如果“民”不在训练集中出现,如何计算权重?

    [回复]

    rickyyang 回复:

    如果不在训练集中,则读不到该特征值,直接就放弃该特征了。

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注