一种多维度的arpa统计语言模型聚类算法.docxVIP

一种多维度的arpa统计语言模型聚类算法 0 n-gram语言模型压缩 应用句子级智能输入应使用语言模型。要实现句子级智能输入，必须使用语言模型。统计语言模型在对特定的语料库进行统计和学习后,推测出自然语言的规律性。现在最常用的语言模型是N-gram语言模型。理论上,N-gram语言模型的N越大,提供的语境信息也越多,但代价就越大,且需训练语料多;N较小时,提供的信息比较少,但计算代价小,且无需太多训练语料。目前输入法中的常用语言模型有Tri-gram(N=3)和Bi-gram(N=2),其中微软拼音、智能狂拼使用的是Tri-gram,而谷歌拼音、搜狗拼音和紫光则使用的是Bi-gram。 采用大量的训练语料,在保证训练得到的语言模型的性能的同时,也导致了语言模型的体积过于庞大,常用的Bi-gram与Tri-gram所占的空间占整个输入法软件大小的90%以上。并且手机等移动设备的空间和运算资源有限,因此对应用于移动平台上的语言模型进行压缩显得非常必要。 文中所介绍的是针对SRILM工具训练语料所得的N-gram语言模型文件的压缩方法,基于K均值聚类算法对语言模型中的转移概率和回退概率压缩,并通过多级索引技术提高查找速度。实现数据表明,在兼顾语言模型的困惑度和整体性能的同时,获得了良好的压缩效果,并提高了查找速率。 1 模型使用用模型 现在输入法中应用最普遍的语言模型是统计语言模型中的N-gram模型。诸如微软拼音、谷歌拼音、搜狗拼音等主流输入法均使用该模型。SRILM(Stanford Research Institute Language Modeling Toolkit)是著名的约翰霍金斯夏季研讨会(Johns Hopkins Summer Workshop)的产物,诞生于1995年,由SRI实验室的Andreas Stolcke负责开发维护,用来构建和应用统计语言模型。 1.1 训练语料中的作用 统计语言模型建模方法中,由于N-gram其简单有效,得到了广泛的应用。N-gram模型基于这样一种假设:第n个词的出现只与前面n-1个词相关,而与其它任何词都不相关。用w1,…,wn来表示这n个词,那么词wn出现的概率就可以写为p(wn|wn?111n-1),这里wn?111n-1表示词串w1,…,wn-1。 在有大量训练语料保证的前提下,根据最大似然准则,可以得到: p(wn|wn?11)=c(wn1)c(wn?11)p(wn|w1n-1)=c(w1n)c(w1n-1) c(wn11n)和c(wn?111n-1)分别表示词串w1,…,wn和w1,…,wn-1在训练语料中出现的次数。对于n个词构成的句子W,那么这句话的先验概率是: p(W)=∏i=1np(wi|wi?1i?n+1)p(W)=∏i=1np(wi|wi-n+1i-1) 之所以把这种模型称为N-gram模型,就在于其反映了连续n个词之间的相关信息。当n=1、2和3时,分别称为Uni-gram、Bi-gram和Tri-gram模型。 1.2 语言模型的困惑度 SRILM的主要目标是支持语言模型的估计和评测。其最基础和最核心的模块是N-gram模块,这也是最早实现的模块,包括两个工具:ngram-count和ngram,相应地被用来估计语言模型和计算语言模型的困惑度。 以生成的语言模型文件ime_chars.2g.lm(8,372,523 Byte)为例,为 ARPA文件格式。 为了说明方便,文件中的括号是笔者加上的注释: \data\ ngram 1=7165 (注:一元词有7165个 ) ngram 2=458382 (注:二元词有458382个) \1-grams:(注:以下为一元词的基本情况) -5.116223 (注:log(概率),以10为底)! -5.212389% -0.6116316(注:回退权重log,以10为底) … \2-grams: -0.1648012% </s> -2.008501% 中 -2.161202% 人 … 2 k-mean聚集算法和多段索引技术 2.1 聚类中心聚类 K-means算法是很典型的基于距离的聚类算法,使用误差平方和准则函数来评价聚类性能。给定数据集X,其中只包含描述属性,不包含类别属性。假设X包含k个聚类子集X1,X2,…,XK;各个聚类子集中的样本数量分别为n1,n2,…,nk;各个聚类子集的均值代表点(也称聚类中心),分别为m1,m2,…,mk。则误差平方和准则函数公式为: E=∑i=1k∑p∈Xi∥p?mi∥2E=∑i=1k∑p∈Xi∥p-mi∥2 算法把得到紧凑且独立的簇作为最终目标,即通过迭代需求符合某个准则函数的聚类中心。 K-means算法的工作过程说明如下:首先从n个数据对象任意选择k个对象作为初始聚