报告人:李荣陆 E-Mail:lironglu@163.net N-Gram及其平滑技术 报告人:李荣陆 E-Mail:lironglu@163.net
相关资料 吴立德等,《大规模中文文本处理》,“稀疏事件的概率估计”,pp.53~62。
统计语言模型 假设一个句子S可以表示为一个序列S=w1w2…wn,语言模型就是要求句子S的概率P(S): 这个概率的计算量太大,解决问题的方法是将所有历史w1w2…wi-1按照某个规则映射到等价类S(w1w2…wi-1),等价类的数目远远小于不同历史的数目,即假定:
N-Gram模型 当两个历史的最近的N-1个词(或字)相同时,映射两个历史到同一个等价类,在此情况下的模型称之为N-Gram模型。 根据最大似然估计,语言模型的参数: 其中,C(w1w2…wi)表示w1w2…wi在训练数据中出现的次数
平滑技术的引入(1) 传统的估计方法对于随机变量£的N次独立观察的样本容量N有如下要求: N>>K 实际语言模型中往往无法满足这个要求。 例如:词性标注问题,共有140个可能的标记,考虑当前词前后两个词的影响的三阶模型。 K=140*140*140=2,744,000 给定一个10万词左右的人工标注训练集,即 N=100,00,可见训练数据显得非常不足。
平滑技术的引入(2) 假设k泛指某一事件,N(k)表示事件k观察到的频数,极大似然法使用相对频数作为对事件k的概率估计: p(k)=N(k)/N 在语言模型中,训练语料中大量的事件N(k)=0,这显然没有反映真实情况。我们把这个问题称为数据稀疏问题。 这种零值的概率估计会导致语言模型算法的失败,例如:概率值作为乘数会使结果为0,而且不能做log运算。
计数等价类 根据对称性原理,事件除了出现次数之外不应具有细节特征,即所有具有相同计数r=N(k)的事件k(事件出现的次数称为事件的计数)应当具有相同的概率估计值,这些计数相同的事件称为计数等价,将它们组成的一个等价类记为计数等价类Gr。 对于计数为r的计数等价类,定义nr为等价类中成员的个数,pr为等价类中事件的概率,R是最大可能出现的计数次数,则
交叉检验(1) 交叉检验就是把训练样本分为m份,其中一份作为保留部分,其余m-1份作为训练部分。训练部分作为训练集估计概率pr,保留部分作为测试集进行测试。 我们使用Cr表示保留部分中计数为r的计数等价类的观察个数。对于保留部分使用最大似然法对进行概率pr进行估计,即使对数似然函数最大化:
交叉检验(2) 使用拉格朗日乘子解决约束条件下的最大值问题,即: 对pr求偏导,得到交叉检验估计: 如果测试部分也作为保留部分的话,就是典型的极大似然估计:
留一估计 留一方法是交叉检验方法的扩展,基本思想是将给定N个样本分为N-1个样本作为训练部分,另外一个样本作为保留部分。这个过程持续N次,使每个样本都被用作过保留样本。 优点:充分利用了给定样本,对于N中的每个观察,留一法都模拟了一遍没有被观察到的情形。 对于留一方法,pr的极大似然估计为:
Turing-Good公式 因为nRpR与1相比一般可以忽略,留一估计公式可以近似为:
空等价类 留一估计中要求么个nr均不为0,在实际问题中当r=5时,这个要求通常都不能满足,即计数等价类G1,…,GR中存在空的等价类。这时按照出现次数进行排序: 对应的出现r(l)次的事件的个数记为nr(l),在进行留一估计时,使用下一个非空的等价类Gr(l+1)代替可能为空的等价类Gr(l)+1,留一估计公式变为: 式中对空的等价类没有估计概率,因为空等价类并没有对应任何有效事件。
Turing-Good估计的优缺点和适用范围 缺点:( 1 )无法保证概率估计的“有序性”,即出现次数多的事件的概率大于出现次数少的事件的概率。(2)pr与r/N不能很好地近似,好的估计应当保证pr<=r/N。 优点:其它平滑技术的基础。 适用范围:对0<r<6的小计数事件进行估计。
约束留一估计 单调性约束:pr-1<=pr;折扣约束:p<=r/N。 在这个约束下,单调性约束自然满足。 计算方法:计算时检查每个pr是否满足约束,不然就用约束的上下界进行裁剪,然后重新计算,一直迭代下去直到所有pr满足约束。
折扣模型 Katz指出Turing-Good公式实质是对模型中观察到的事件进行折扣,将折扣得来的概率摊到所n0个未现事件中。在这个思想的指导下,估计公式可以下成如下形式: 其中,dr是对计数为r的事件的计数的一个折扣函数。
绝对折扣模型 若折扣函数定义为:dr=b,其中b为一个大于0的常数。那么未现事件的总概率为: 对应绝对折扣模型的估计公式为:
线性折扣模型 若折扣函数定义为:dr=·r,其中为一个大于0的常数。那么未现事件的总概率为: 对应线性折扣模型的估计公式为: 若=n1/N,则n0p0=n1/N,与Turing-Good估计相同。
删除插值法(Deleted Interpolation) 其基本思想是,由于N-Gram比N+1-Gram出现的可能性大的多,所以使用N-Gram估计N+1-Gram的概率,例如trigram的计算公式如下: 其中, 参数的确定:将训练数据分为两部分,一部分用于估计f(wi| w1w2…wi-1),一部分用于计算参数,求使语言模型的困惑度最小的。