第六章：N元语法模型

大纲 概述 参数估计 平滑算法

概述

噪声通道模型 原型 模型：出错的概率 举例：p(0|1)=0.3, p(1|1)=0.7, p(1|0)=0.4, p(0|0)=0.6 任务是： 已知带有噪声的输出 想知道输入是什么（也称为：Decoding) 0,1,1,1,0,1,0,1 通道 （增加噪声） 0,1,1,0,0,1,1,0 输入 输出

噪声通道的应用 OCR 手写识别 语音识别 机器翻译 其它：词性标注 文本打印(引入噪声), 扫描图像 文本神经肌肉(引入噪声), 扫描图像 语音识别 文本朗读(引入噪声) 声学波形 机器翻译 目标语言翻译(引入噪声) 源语言 其它：词性标注 词性序列选择词形文本

噪声通道：黄金规则 适用于OCR，手写识别，语音识别，机器翻译，词性标注等各个问题 贝叶斯公式：P(A|B)=P(B|A)P(A)/P(B) Abest=argmaxA P(B|A)P(A) P(B|A)是声学/图像/翻译等模型 在不同领域用不同的术语来描述 P(A)是语言模型

什么是语言模型(Language Model) 语言模型是用来计算一个句子的概率的概率模型 例如：P(w1,w2,…,wn) 语言模型的用途 决定哪一个词序列的可能性更大 已知若干个词，预测下一个词 应用 语音识别 机器翻译 上下文敏感的拼写检查

应用于语音识别 有的词序列听起来很像，但并不都是正确的句子 例子1： 例子2： I went to a party. √ Eye went two a bar tea. 例子2： 你现在在干什么？ √ 你西安载感什么？

应用于机器翻译 给定一个汉语句子 例如：王刚出现在电视上。 英文译文： Wang Gang appeared in TV. In Wang Gang appeared TV. Wang Gang appeared on TV. √

应用于拼写检查 我自己知道 √ 我自已知道 举例 汉语 英语 Wang Gang appeared on TV. √ Wang Gang appeared of TV.

参数估计

完美的语言模型 对于词序列W=w1,w2,…,wn 如何计算p(W)？ 根据链式规则：p(W)=p(w1)p(w2|w1)…p(wn|w1,…,wn-1) 即使对于很小的n，上面的理想公式也很难计算，因为参数太多

马尔科夫链 有限的记忆能力 p(W)=∏i=1…dp(wi|wi-k,…,wi-1), d=|W| 不考虑太“老”的历史 只记住前k个词w1,…,wk 称为k阶马尔科夫近似 p(W)=∏i=1…dp(wi|wi-k,…,wi-1), d=|W|

N元语言模型 n-1阶马尔科夫近似称为n元语言模型(LM, Language Model) p(W)=∏i=1…dp(wi|wi-n+1,…,wi-1), d=|W| n越大，需要估计的参数越多，假设词汇量为20,000 模型 需要的参数数量 0阶(一元Unigram) 20,000 1阶(二元bigram) 20,000*19,999 = 400 million 2阶(三元trigram) 20,0002*19,999 = 8 trillion万亿 3阶(四元four-gram) 20,0003*19,999 = 1.6*1017

语言模型的讨论 n多大？ 目前一般直接计算词形，不进行语言学处理，如形态还原等 理论上讲，越大越好 经验值：3，trigram用的最多 four-gram需要太多的参数，很难估计了 目前一般直接计算词形，不进行语言学处理，如形态还原等 可靠性(Reliability)和可区别性(Discrimination)成反比，需要折中 n越大，区别力越大；n越小，可靠性越高

语言模型的讨论 “large green ___________” tree? mountain? frog? car? “swallowed the large green ________” 吞下 pill? candy?

可靠性和区别性 可靠性(Reliability )和可区别性(discrimination) 为了有效地推导一个特征，我们希望通过模型的其它特征来预测它，把这些特征分成等价类便于我们预测新的数据。 分类特征越多，对未知分布的目标特征的预测就更精确，即有较好的可区别性，但是这样对每一个分类其实例就较少，统计的数据就不可靠，所以在划分等价类时要在可靠性和可区别性之间找一个折衷点。

长度问题 n; wn p(w)=1  n=1… wn p(w) >> 1 () 我们试图对所有的词序列建立模型 对于固定长度的任务，没有问题，n一旦固定，累计和为1 比如Tagging等 对于变长的任务，需要对比较短的句子进行折扣 (句法分析） 一般模型 对于长度为n的词序列 P’(w)=np(w), n=1… n=1 n=1… wn p’(w)=1 从数据中估计n

参数估计 参数：用来计算p(w|h)的数值 从数据中得到 数据准备 去掉格式符号 定义词的边界 定义句子边界(插入<s>和</s>等记号) 字母的大小写（保留、忽略或者智能识别） 数字（保留、替换为<num>等）

最大似然估计 最大似然估计MLE 从训练数据T中获得Trigrams 是对训练数据的最佳估计 从训练数据T中获得Trigrams 统计T中三个词连续出现的次数C3(wi-2,wi-1,wi) 统计T中两个词连续出现的次数C2(wi-2,wi-1) pMLE(wi|wi-2,wi-1) = C3(wi-2,wi-1,wi) / C2(wi-2,wi-1)

MLE不适合用于NLP MLE选择的参数使训练语料具有最高的概率，它没有浪费任何概率在于没有出现的现象中 一个例子说明数据稀疏：从IBM Laser Patent(专利权)Text语料中1.5 Million 的词进行训练，在同一语料中的测试文本中，新出现23%的trigram 词次。.

举例1 p(z|xy)=? 假设训练语料为： xyz没有出现过 我们能够说： … xya …; … xyd …; … xyd … xyz没有出现过 我们能够说： p(a|xy)=1/3, p(d|xy)=2/3, p(z|xy)=0/3吗？ 不能，因为xyz可能是一个常见的组合，但在现有的训练集中不应有的缺失了

分析 被除数越小，越不可靠 1/3可能太高, 100/300可能是对的 除数越小，越不可靠 1/300可能太高，100/30000可能是对的

字符语言模型 使用单独的字符而不是词 使用相同的公式和方法 可以考虑使用4-gram，5-gram，因为数据比较充足 对交叉语言的比较很有用 基于字和基于词的交叉熵的换算关系 H(pc , S) = H(pw , S) / 句子S中的平均词长,

举例2 训练数据: <s0> <s> He can buy you the can of soda </s> Unigram: (词汇上8个词 ) p1(He) = p1(buy) = p1 (you) = p1 (the) = p1(of) = p1(soda)= .125, p1(can) = .25 Bigram: p2(He|<s>) = 1, p2(can|He) = 1, p2(buy|can) = .5, p2(of|can) = .5, p2(you |buy) = 1,... Trigram: p3(He|<s0>,<s>) = 1, p3(can|<s>,He) = 1, p3(buy|He,can) = 1, p3(of|the,can)= 1, ..., p3(</s>|of,soda) = 1. 熵: H(p1) = 2.75, H(p2) = 1, H(p3) = 0

举例3 给定的观测训练数据……. 为预测未来的事件如何建立一个模型(概率分布)？ 语料库: five Jane Austen novels N = 617,091词， V = 14,585 词次 任务: 预测下一个三元语法的词 “inferior to ___” 从测试数据 , Persuasion: “[In person, she was] inferior to both [sisters.]” 给定的观测训练数据……. 为预测未来的事件如何建立一个模型(概率分布)？

训练数据的实例 : “inferior to___”

实际概率分布

最大似然估计

比较

交叉熵 交叉熵 H(p1 ,s) = H(p2 ,s) = H(p3 ,s) =∞，原因是： 我们希望使每个概率都是非零的 S = <s0> <s> It was the greatest buy of all </s> H(p1 ,s) = H(p2 ,s) = H(p3 ,s) =∞，原因是： 所有的unigrams除了p1(the), p1(buy), and p1(of) 都是0 所有bigram的概率都是 0. 所有trigram的概率都是 0. 我们希望使每个概率都是非零的

零概率问题 原始的Trigram模型估计 一定会有很多概率为0的情况 哪些参数真的应该是0呢？ 我们必须去除概率为0的情况 因为参数空间太大，trigram:8T，而数据只有1G 哪些参数真的应该是0呢？ 理想情况是：最低频的trigram也应该出现几次，以便把它的概率和其它trigram的概率区别开来 但是理想情况不会发生，到底需要多少数据，我们不知道 我们必须去除概率为0的情况 包括：p(w|h)=0，或者p(h)=0

为什么我们需要非零的概率？ 避免无穷大的交叉熵 使系统更健壮 当测试数据中出现了一个在训练数据中没有出现过的事件，就会发生H(p)=∞的情况 低频的估计值 更加细腻(detailed)，但相对来说很少出现 高频的估计值 更可靠但是不够细腻

平滑算法

避免零概率：数据平滑 p’(w) ≈p(w), 但p’(w)≠0 对一些p(w)>0,生成p’(w)<p(w) 分配D给所有概率为0的w: p’(w)>p(w)=0 可能对于概率值较低的词也作调整 可能有些w: p’(w)=p(w) 务必确保 有许多数据平滑的方法

折扣discounting 回退Back-off 平滑Smoothing 如果n-gram的值为零，则用n-1 gram来计算 将MLE方法与其它方向相混合，保证没有0概率的值

Laplace法则 （加1平滑） 最简单，但不是真的能用 预测 p’(w|h)=(c(h,w)+1)/(c(h)+|V|) T:训练数据,V:词表,w: 词 预测 p’(w|h)=(c(h,w)+1)/(c(h)+|V|) 特别:非条件分布时p’(w)=(c(w)+1)/(|T|+|V|) 问题：经常会|V|>c(h)，甚至|V|>>c(h) 举例：T: <s>what is it what is small? |T|=8 V={what,is,it,small,?,<s>,flying,birds,are,a,bird,.}, |V|=12 p(it)=0.125, p(what)=0.25, p(.)=0, p(what is it?)=0.252*0.1252≈0.001 p(it is flying.)=0.125*0.25*02=0 p’(it)=0.1, p’(what)=0.15,p’(.)=0.05, p’(what is it?)=0.152*0.12 ≈0.0002 p’(it is flying.)=0.1*0.15*0.052 ≈0.00004

举例 Trigram they,do,approach 1 they,do,have 2 they,do,Link 1 they,do,not 7 they,do,on 3 they,do,open 1 they,do,so 1 they,do,under 5 Bigram do,anything 2 do,approach 1 do,no 1 do,not 97 do,Novell 1 do,offer 1 ... they,do 22 Unigram do 384 ... PMLE(not|they,do) = 7/22 = 0.318 C(they,do,not) = 7 PMLE(not|do) = 97/384 = 0.253 C(do,not) = 97 PMLE(offer|they,do) = 0/22 = 0 PMLE(have|they,do) = 2/22 = 0.091

Laplace法则的举例 P+1(not|they,do) P+1(offer|they,do) P+1(have|they,do) Vocabulary Size (V) = 10,543 P+1(not|they,do) P+1(offer|they,do) P+1(have|they,do)

Lidstone法则（小于1平滑） -T:训练数据,V:词表,w: 词 加入λ系数 预测 p’(w|h)=(c(h,w)+λ)/(c(h)+ λ |V|), λ<1 特别:非条件分布时p’(w)=(c(w)+ λ)/(|T|+ λ |V|) 举例：T: <s>what is it what is small? |T|=8 V={what,is,it,small,?,<s>,flying,birds,are,a,bird,.}, |V|=12 p(it)=0.125, p(what)=0.25, p(.)=0, p(what is it?)=0.252 *0.1252≈ 0.001 p(it is flying.)=0.125*0.25*02=0 取 λ=0.1 p’(it)=0.12, p’(what)=0.23,p’(.)=0.01, p’(what is it?)=0.232*0.122 ≈0.0007 p’(it is flying.)=0.12*0.23*0.012 ≈0.000003

Laplace法则 (原来的)

Laplace法则 (加1平滑的)

Laplace法则

Good-Turing 适用于评估大规模的数据 相似点： pr(w)=(c(w)+1)*N(c(w)+1)/(|T|*N(c(w))), 其中：N(c)是数目为c的词的数量 特别：对于训练集中没有出现的词，c(w)=0 pr(w)=N(1)/(|T|*N(0)) 有利于数量少的词语（<5-10, 但N(c)较大） “调富济贫” 归一化（可以得到 ）

Good-Turing: 举例 例如：记住： pr(w)=(c(w)+1)*N(c(w)+1)/(|T|*N(c(w))) T: <s>what is it what is small? |T|=8 V={what,is,it,small,?,<s>,flying,birds,are,a,bird,.}, |V|=12 p(it)=0.125,p(what)=0.25,p(.)=0,p(what is it?)=0.252*0.1252≈0.001 p(it is flying.)=0.125*0.25*02=0 重新计算（N(0)=6,N(1)=4,N(2)=2,N(i)=0 当 i>2）: Pr(it)=(1+1)*N(1+1)/(8*N(1))=2*2/(8*4)=0.125 Pr(what)=(2+1)*N(2+1)/(8*N(2))=3*0/(8*2)=0: 使用原来的 p(what) Pr(.)=(0+1)*N(0+1)/(8*N(0))=1*4/(8*6)≈0.083 归一化（除以 1.5= ）并计算 p’(it) ≈ 0.08, p’(what) ≈ 0.17, p’(.) ≈ 0.06 p’(what is it?)=0172*0.082≈0.0002 p’(it is flying.) ≈ 0.08*0.17*0.062 ≈ 0.00004

平滑:例子

保存估计 Held-Out Estimator 多少概率分布应保留，以便处理以前未知的事件？ 通过保存训练数据的一部分，可以验证选择 多久在训练中的数据看（或没有看到） 事件发生一次在验证数据？

保存估计 对于每个n-元组, w1,..,wn , 计算 C1(w1,..,wn) 和 C2(w1,..,wn)： 训练和保存数据中w1,..,wn的频率 Nr 是出现r次（在训练数据中）n-gram 的数量. Tr 是所有在训练文本中出现r次的年-n-gram 在保存数据中出现的总数量。 频度r n-gram的平均频率是Tr/Nr 这些n-gram之一的频率的概率估计是: Pho(w1,..,wn)= (Tr/Nr )/N 其中 C(w1,..,wn) = r

测试模型 把这些数据划分为训练数据和测试数据。 训练数据:划分为一般训练和验证（平滑）数据 集合:大约训练数据的10% (少的参数） 训练数据:划分为一般训练和验证（平滑）数据 集合:大约训练数据的10% (少的参数） 测试数据: 区分“真正的”测试数据和 开发数据 使用开发数据调整模式，以便适应测试数据 最终测试数据：整个语料库的 5 – 10% 为了得到结果的偏差，测试多组测试数据的是很有用的 结果（好的或坏的）是不是偶然的结果？ 使用t-检验

交叉验证 Cross-Validation 如果有很多数据 ，保存估计是有用的。 如果不是，更好方法是使用每一部分的数据作为训练数据和保存数据。 删除估计：Deleted Estimation [Jelinek & Mercer, 1985] 留一法： Leave-One-Out [Ney et al., 1997]

删除估计 使用数据为训练和验证数据 A B + 划分数据为两个部分 训练 A, 验证 B 训练 B, 验证 A 结合了两种模型 训练 验证 模型 1 模型 2 + 最终模型

交叉验证 两个估计 : 结合的估计: 算术平均 Nra = a部分训练数据出现r次的n-gram的数量 。 两个估计 : Nra = a部分训练数据出现r次的n-gram的数量 。 Trab = a部分中出现的bigram在训练数据b部分出现的总词数。 结合的估计: 算术平均

典型n-gram语言模型的平滑 采用λ=(λ0,λ1,λ2,λ3): 归一化： λi>0, 就可以了（ λ0=1- ）（n=3） 极大似然估计 固定p3,p2,p1和|V|，根据训练数据确定参数 再寻找一组{λi}使得交叉熵达到最小 （使数据的概率达到最大）：

保存数据 Held-out Data 所以：不要采用训练数据来估计λ! 使用什么数据？ 为什么？ 在向量λ上最小化H(p’(λ)，T), p’(λ)=λ3p3T+ λ2p2T+ λ1p1T+ λ0/|V| 记住H(p’ λ ， T)=H(p3T)+D(p3T||p’ λ) ;( p3T fixed→H(p3T)fixed,best) 满足D(p3T||p’ λ) =0的p’ λ可以使得H(p’ λ ， T)达到最小 解是p3T（因为D(p||p)=0） If λ3=1,必有p’ λ= 1*p3T+ 0*p2T+ 0*p1T+ 0/|V|= p3T 所以：不要采用训练数据来估计λ! 必须留出部分训练数据（Held out data, H） 剩下的数据为真实原始的训练数据(training data,T) 测试数据 S（例如为了比较）：仍然是不同的数据！

公式 重复：在λ上最小化 λ的期望数值：j=0..3 “Next λ”：j=0..3

EM平滑算法 2、计算每个λj的期望数值 3、采用“Next λ”公式计算的λj新集合 4、返回2，除非遇到终止条件 终止条件为： λ收敛 1、从某些λ开始，如λj>0,所有j∈0..3 2、计算每个λj的期望数值 3、采用“Next λ”公式计算的λj新集合 4、返回2，除非遇到终止条件 终止条件为： λ收敛 简单设定一个ε，当step3中对每个j都有 |λj-λj ,next|< ε时终止

简单实例 开始于λ1=0.5； p’λ(b)=0.5*0.5+0.5/26=0.27 原始分布（unigram，对均匀分布平滑） p(a)=0.25,p(b)=0.5,p(α)=1/64,α∈{c..r} ,剩下的s,t,u,v,w,x,y,z均为0 Heldout数据：baby; 采用一个λ的集合（ λ1:unigram, λ 0:均匀分布） 开始于λ1=0.5； p’λ(b)=0.5*0.5+0.5/26=0.27 p’λ(a)=0.5*0.25+0.5/26=0.14 p’λ(y)=0.5*0+0.5/26=0.02 c(λ1)=0.5*0.5/0.27+0.5*0.25/0.14+0.5*0.5/0.27+0.5*0/0.2=2.72 c(λ0)=0.5*0.04/0.27+0.5*0.04/0.14+0.5*0.04/0.27+0.5*0.04/0.02=1.28 归一化： λ1,next=0.68, λ0,next=0.32 返回step2(重新计算p’ λ，然后 c(λ1)，…）。结束结束条件为当前的λ与前一组λ相差很小（比如，<0.01）

回退方法 Backoff 如果我们没有的高阶n-gram 回到了较低阶N-gram。 Trigram回退方法 :

Katz’s 回退方法 Back-off Katz的n-gram回退模型通过前面短一些的历史对当前n-gram进行估计。估计式如下：

回退方法的问题 如果 bigram w1 w2 is出现很多次，但是我们没看到 trigram w1 w2 w3。这就不是偶然或稀疏的差距，而是有意义的差距 也就是“语法上零概率 ” 在这种情况下，回退低阶概率是不适当的。

划分等价类的其它方法 Stemming 语义类Class-based LM Computer Computing Compute …… 时间类 人名类 地点类 机构名类

对语言模型进行评价 最佳方法: 混乱度(Perplexity): 将语言模型用于某一个应用中，例如拼写检查、机器翻译等 给测试集赋予较高的概率值的语言模型较好