初学者报道(3) CRF 中文分词解码过程理解 – 我爱自然语言处理

您所在的位置:网站首页 维特比算法时间复杂度是什么 初学者报道(3) CRF 中文分词解码过程理解 – 我爱自然语言处理

初学者报道(3) CRF 中文分词解码过程理解 – 我爱自然语言处理

2024-04-15 11:54| 来源: 网络整理| 查看: 265

好久没有来写文章了,这段时间我研究了一下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.比较这四个值中的最大值,即为最优路径的分数,然后以该值的标记点为始点 回溯得到最优路径(这里在计算过程中,要记录到达该标记的前一个标记,用于回溯)

终于写好!:)

 

相关文章: 初学者报道(2):实现 1-gram分词算法 stardict2.4.8的main函数简要说明与注释 基于哈希表和二叉树的词典研究(一) MIT自然语言处理第一讲:简介和概述(第二部分)


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3