win8 64bit下srilm+cygwin实现ngram语言模型

ngram语言模型+win8 64bit下安装srilm+cygwin实现

最近导师给了个新项目关于信息抽取（给了三篇论文，实验室混一年，动手能力没怎么提高但是看论文倒是飞快），会用到语言模型，虽然自己本身NLP出身但是实现论文的方法会涉及很多工程性问题。

论文需要实现ngram中的Good Turing平滑和回退模型的Katz Backoff平滑（怪自己研一的主修课没认真实践，扫了一遍研一课件（常宝宝），看懂公式到看懂别人的代码花了大半天时间），这里先讲了下两种平滑，Turing平滑的思想是将高频n元组频率调整到低频n元组：

$$r(Turing^*) = (r+1)\dfrac{N_{r+1}}{N_r} (1)$$
数据集中存在没有频度为(r+1)的n元组情况，需要改造公式（引入 $$S(r+1) :N_{r+1}$$ 的平滑)：
$$r^* = (r+1)\dfrac{S(r+1)}{S(r)}$$
这里变成了简单Good Turing平滑，函数S(r+1)：
$$S(r) = \dfrac{N_r}{0.5*(r_{larger}-r_{smaller})}$$
这里有lager和smaller表示第一个比r更大和更小的频率（同时N不为0）即临近频率，可以先只考虑对S(r)的平滑，这里提供了线性平滑：
$$log(S(r)) =a+b*log(r)$$
那么可以直接对整个数据集进行平滑，求平均的a和b值(其实最后只用到b)，那么最后：
$$r(Good Turing^*) = (r+1)exp[b*(log(r+1)-log(r))]$$
一般来说，Turing平滑比Good Turing平滑可靠，当Turing估计值和Good Turing估计值绝对差小于1.65倍的Turing估计值的标准差，可以使用Good Turing平滑代替Turing平滑。
Turing方差近似计算如下：
$$Var(Turing^*)= (r+1)^2\dfrac{N_{r+1}}{N_{r}^2}(1+\dfrac{N_{r+1}}{N_{r}})$$
相关公式推导可以参考论文： [1] Church, K. and W. Gale, (1991), A comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams, Computer Speech and Language, v. 5, pp. 19-54.
其实最后计算概率时候可以将r=0的那部分拿出来，其他部分如某个出现频次为r的单词的概率为：
$$P(r_+)= (1-\dfrac{N_{1}}{N_{all}})\dfrac{r^*}{\sum\limits_{r=1} r^*}$$
那么r=0的那部分需要先统计测试集在训练集上未出现词的词汇量，然后平分：
$$P(r_0)= \dfrac{1}{N_{vocab}}\dfrac{N_{1}}{N_{all}}$$
具体实现细节可以参考NLP开源代码，这里可以看看snowseg中good_turing.py，请自行网上搜索。

Good Turing平滑的缺陷在于高阶ngram无法融合可靠性更高的低阶ngram（即低阶频率高）。接下来Katz backoff便利用这个优势。回退模型中涉及到条件概率，对r进行分段分析（设阈值k=5，Katz）：
(1)r>k：不平滑。
(2)r=0：即未出现，Turing估计中未出现词估计值为

$$N_1$$ 这需要从r>0那部分平滑过来，即从k>=r>0中平滑过来的频次，满足： $$\sum\limits_{r=1}^kN_rr(1-d_r)=N_1$$ 其中 $$d_r$$ 即下面的折扣率。另一方面需要回退到(n-1)gram，并需要将这部分概率归一化到从k=>r>0平滑出的全局概率，使得最后概率值和为1。
(3)k=>r>0：先进行Good Turing平滑，r*/r实际是对r的折扣，另外 $$d_r$$ 满足
$$1-d_r=u*(1-\dfrac{r^*}{r})$$
结合上面的式子，其实u为常量。

其他平滑请参考http://www.flickering.cn/nlp/2015/02/%E6%88%91%E4%BB%AC%E6%98%AF%E8%BF%99%E6%A0%B7%E7%90%86%E8%A7%A3%E8%AF%AD%E8%A8%80%E7%9A%84-2%E7%BB%9F%E8%AE%A1%E8%AF%AD%E8%A8%80%E6%A8%A1%E5%9E%8B/。

接下来就是srilm安装，srilm安装环境为linux，由于win8电脑不能关机（跑了快一周的数据），那么需要安装cygwin，这里安装需要注意srilm/doc/README.windows-cygwin提到的cygwin依赖库（make, gcc, binutils, libiconv, gzip, tcltk, and gawk以及tcl，实际运行时候报错缺什么安装什么，安装时候需要勾选），这里选择的是163镜像网址比较快，接下来便是将srilm解压缩到cygwin目录下，并将home/[username]/.bashrc文件添加环境变量如下行：

export SRILM=/srilm
export MACHINE_TYPE=cygwin
export PATH=$PATH:$pwd:$SRILM/bin/cygwin64
export MANPATH=$MANPATH:$SRILM/man

在srilm/Makefile 增加一行SRILM=/srilm，每一行请检查，这里需要保证和实际路径一致，uname -m测试保证机器变量和实际一致。
接下来便是运行cygwin，在命令行模式下进入cd /srilm依次执行make World、make all、make cleanest编译srilm，如遇到任何问题反复安装cygwin并勾选没有安装好的依赖库，整个过程差不多半个小时。运行如下：

srilm是一个强大的nlp库，具体见
http://www.speech.sri.com/projects/srilm/download.html，http://blog.csdn.net/zhoubl668/article/details/7759042。
cygwin和srilm安装参考http://m.blog.csdn.net/blog/lv_xinmy/8572496。
ubuntu上安装srilm参考http://www.leexiang.com/how-to-configure-srilm-on-ubuntu。

下节讨论基于上面基础之上的HMM模型。