Simple implementation of mmseg with python

Since I heard of MMSEG Chinese word segmentation algorithm (http://technology.chtsai.org/mmseg/) many years ago, I finally implemented it with Python as a programing practice in my team, dictionary file and character frequencies from mmseg4j project.

rnnlm代码分析

这几天分析了一下rnnlm-0.3e的代码,做了一点点笔记,很多细节自己还没搞清楚,写的也非常粗略。因为懒得贴过来排版了,直接share一下evernote上的链接吧,请大家多多指正!

为像我这样的初学者了解rnnlm所需要的一些预备知识,sigmod和softmax的cost function和derivative,如何展开rnn,以及如何更新rnn的weights。

open-gram项目简介

open-gram项目是由sunpinyin开发团队发起的一个open-source项目,主要是tchaikov同学在drive,主要目标是为中文输入法在内的NLP类项目,提供开放的词表和n-gram频率数据。项目中的代码将以GPLv3发布,数据文件将以creative-common license发布。

open-phrase对于词表和unigram(词频)数据来说,已经做得很好了。但是对于其词库的原始来源,以及生成数据的发布协议,都不是很清晰。(也许这也是ubuntu至今没有收录ibus-pinyin-data包的原因之一?)其仅在项目页面上提到,采用GPLv2协议。如果的确如此,这个协议对于广大软件开发者来说,无疑是过于严苛了。

open-gram将采用cc-cedict的词库(同样以creative-common license发布)为基础,在处理语料时发现的新词也将采用相同的协议,并希望能贡献回cc-cedict。open-gram不仅仅针对简体中文,我们希望将来也能包括繁体中文、甚至中英混合的统计信息。最终提供给大家的包括词表和n-gram频率数据,都会采用文本文件的方式。

tchaikov同学已经发布了一个适用于sunpinyin-2.0的,基于cc-cedict和zh.wikipedia的词库和语言模型,可以在此下载,用以替换sunpinyin-2.0中原有的数据文件。替换之后,可能有些词条会和您的用户词典中有重叠(我们将尽快加入删除用户自造词的功能),而且建议您清除掉history cache文件。

tchaikov同学做了大量艰苦的工作,训练了用于新词发现的CRF模型,手工校对了许多词条及其注音,等等。我们也热切盼望更多朋友的加入!

Updated by tchaikov:

ibus-pinyin-data 现在叫 ibus-pinyin-db-open-phrase,已经进入了 ubuntu 和 debian。license 是 GPLv2。

maxent分词补遗

在和同事讨论最大熵时,介绍了以前一个用最大熵分词的实验,突然对为什么每个事件需要U03~U05这三项产生了疑惑,当时也没有细想。

... ...
E U00-人 U01-们 U02-常 U03-人/们 U04-们/常 U05-人/常 B
... ...

再重新整理了一下头绪,在张乐的工具包中,事件并非是样本,样本应该是那个三字窗口。例如“人们常”,这个样本产生了7个feature,分别是(U00-人,
E), (U01-们, E), (U02-常, E), (U03-人/们, E), (U04-们/常, E),(U05-人/常),(B,
E),这些feature构成了一个事件。(U00-人,
E)描述的是,一个三字窗口,起始字符为“人”时,中间的字符被标记为“E”的情况;(U05-人/常,
E)描述的是,三字窗口的左右分别是“人”和“常”时,中间字符被标记为“E”的情况;(B,
E)描述的是,三字窗口的第一个字符(也就是前一个观测)被标记为B时,中间字符被标记为E的情况。

如此看来,我们原先训练的应该是加入状态转移约束的ME,而不是MEMM。MEMM的feature是,将ME的每个feature,额外加入上一个状态作为条件。因此,用来训练MEMM的事件,应该写成这个样子,

... ...
E U00-人-B U01-们-B U02-常-B U03-人/们-B U04-们/常-B U05-人/常-B
... ...

实验的结果,对msr的数据集准确率有小幅提高,但是对pku的数据集有小幅降低。

实验maxent分词

使用张乐博士maxent工具包,应用赵海博士的6 tags + 3字窗口法,对bakeoff2005公开的语料进行实验。用python写了个简单的转换脚本,将CRF++的训练语料转换为maxent支持的格式。训练模型的时间比CRF要少了许多。对MSR的语料和测试集,得到预测的准确度为96.4357%。与Yandong使用4 tags + 3字窗口的结果接近(96.2225%)。400多万个样本,其中只出现一次、被cut掉的event居然有240多万个。不知道是不是我使用的输入格式有问题?


S U00-_B U01-“ U02-人 U03-_B/“ U04-“/人 U05-_B/人 E
B U00-“ U01-人 U02-们 U03-“/人 U04-人/们 U05-“/们 S
E U00-人 U01-们 U02-常 U03-人/们 U04-们/常 U05-人/常 B
S U00-们 U01-常 U02-说 U03-们/常 U04-常/说 U05-们/说 E
S U00-常 U01-说 U02-生 U03-常/说 U04-说/生 U05-常/生 S
B U00-说 U01-生 U02-活 U03-说/生 U04-生/活 U05-说/活 S
E U00-生 U01-活 U02-是 U03-生/活 U04-活/是 U05-生/是 B
S U00-活 U01-是 U02-一 U03-活/是 U04-是/一 U05-活/一 E
S U00-是 U01-一 U02-部 U03-是/一 U04-一/部 U05-是/部 S
S U00-一 U01-部 U02-教 U03-一/部 U04-部/教 U05-一/教 S
B U00-部 U01-教 U02-科 U03-部/教 U04-教/科 U05-部/科 S
B2 U00-教 U01-科 U02-书 U03-教/科 U04-科/书 U05-教/书 B
E U00-科 U01-书 U02-, U03-科/书 U04-书/, U05-科/,B2
... ...

实验CRF++

使用赵海博士的6 tags + 6 templates法,对bakeoff2005公开的语料进行实验。用python写了个简单的转换脚本,将UTF-8编码的训练语料转换为CRF++支持的格式。MSR的语料库转换之后是24M,训练模型花了大概26个小时,得到的模型为25M,对MSR的测试数据F-score可以达到96%(python的评估脚本),对PKU的测试数据只有82%多。PKU的语料库转换之后是11M,训练模型花了近13个小时,得到的模型有14M,对PKU的测试数据F-score有92%多,对MSR的测试数据也只有82%左右。看来MSR和PKU训练语料的分词风格有较大的差异,导致交叉测试的分数比较低。

另外,大概是C++的STL线程安全有问题,在Linux、Solaris和Mac OS上使用多线程都SEGFAULT了,所以都是单线程训练的。不敢想象如果用数百兆的语料,会花多长时间、用多少内存...

下面是特征模板的定义:

# Unigram
U00:%x[-1,0]
U01:%x[0,0]
U02:%x[1,0]
U03:%x[-1,0]/%x[0,0]
U04:%x[0,0]/%x[1,0]
U05:%x[-1,0]/%x[1,0]
# Bigram
B

A Beginner's Note of CRF++

Thanks for Yandong's help and guidance, that I got some basic ideas about CRF (Conditional Random Filed) and how the CRF model looks like. The encoder of CRF++, crf_learn, could generate a model in text format with the '-t' option. Take the Japanese word segmentation demonstration (example/seg) as an example, the following is the model in text format:

ersion: 100
cost-factor: 1
maxid: 1386      /* the number of feature functions */
xsize: 1

B                /* the tag lists, in this case, we have two tags */
I

U00:%x[-2,0]     /* unigram feature templates */
U01:%x[-1,0]
U02:%x[0,0]
U03:%x[1,0]
U04:%x[2,0]
U05:%x[-2,0]/%x[-1,0]/%x[0,0]
U06:%x[-1,0]/%x[0,0]/%x[1,0]
U07:%x[0,0]/%x[1,0]/%x[2,0]
U08:%x[-1,0]/%x[0,0]
U09:%x[0,0]/%x[1,0]
B               /* bigram feature template */

0 B             /* bigram of the tags for C_{-1} and C_0,  */
                /* number of features are 2^(# of tags).   */

4 U00:_B-1      /* _B-1 is the starting of a sentence */
                /* _B+1 is the ending of a sentence   */

6 U00:_B-2      /* _B-2 is the pre-token of _B-1  */
                /* _B+2 is the post-token of _B+1 */

8 U00:
10 U00:、       /* feature function id, template id, and observation */
12 U00:〇       /* since we only have two tags, each entry could     */
14 U00:「       /* be expanded to 2 feature functions                */
20 U00:う
... ...
... ...
1382 U09:3/年
1384 U09:9/3

-0.0799963416235706     /* the weight for each feature function */
0.4346315510326526      /* the negative value indicates the     */
-0.1044728887459596     /* feature is rarely seen, and we have  */
-0.2501623206703318     /* 1386 weights in total.               */
... ...