初学者报道(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.比较这四个值中的最大值，即为最优路径的分数，然后以该值的标记点为始点 回溯得到最优路径（这里在计算过程中，要记录到达该标记的前一个标记，用于回溯）

终于写好！:)

 

相关文章:

1. 初学者报道（2）：实现 1-gram分词算法
2. stardict2.4.8的main函数简要说明与注释
3. 基于哈希表和二叉树的词典研究(一)
4. MIT自然语言处理第一讲：简介和概述（第二部分）
5. MIT自然语言处理第二讲：单词计数（第四部分）
6. 条件随机场文献阅读指南