语言模型.

Presentation on theme: "语言模型."— Presentation transcript:

1 语言模型

2 大纲 概述 参数估计 基本平滑算法 其它平滑算法

3 概述

4 噪声通道模型 原型 模型：出错的概率 举例：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 输入 输出

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

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

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

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

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

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

11 参数估计

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

13 马尔科夫链 有限的记忆能力 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|

14 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

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

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

17 长度问题 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

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

19 最大似然估计 最大似然估计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)

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

21 举例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可能是一个常见的组合，但在现有的训练集中不应有的缺失了

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

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

24 举例2 训练数据: <s0> <s> He can buy you the can of soda </s> Unigram: (8 words in vocabulary) 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. Entropy: H(p1) = 2.75, H(p2) = 1, H(p3) = 0

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

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

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

28 基本平滑算法

29 避免零概率：数据平滑 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) 务必确保 有许多数据平滑的方法

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

31 加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 ≈

32 举例 Trigram they,do,approach 1 they,do,have 2 they,do,Link 1
they,do,not they,do,on they,do,open 1 they,do,so they,do,under 5 Bigram do,anything 2 do,approach 1 do,no do,not 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

33 Add one举例 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)

34 小于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 ≈

35 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)较大） “调富济贫” 归一化（可以得到 ）

36 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: keep orig. 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?)=01752*0.082≈0.0002 p’(it is flying.) ≈ 0.08*0.17*0.062 ≈

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

38 Held-out Data 所以：不要采用训练数据来估计λ! 使用什么数据？ 必须留出部分训练数据（Held out data, H）
为什么？ 在向量λ上最小化HT(p’(λ)), p’(λ)=λ3p3T+ λ2p2T+ λ1p1T+ λ0/|V| 记住HT(p’ λ)=H(p3T)+D(p3T||p’ λ) ;( p3T fixed→H(p3T)fixed,best) 满足D(p3T||p’ λ) =0的p’ λ可以使得HT(p’ λ)达到最小 解是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（例如为了比较）：仍然是不同的数据！

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

40 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|< ε时终止

41 简单实例 开始于λ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* /26=0.27 p’λ(a)=0.5* /26=0.14 p’λ(y)=0.5*0+0.5/26=0.02 c(λ1)=0.5*0.5/ *0.25/ *0.5/ *0/0.2=2.72 c(λ0)=0.5*0.04/ *0.04/ *0.04/ *0.04/0.02=1.28 归一化： λ1,next=0.68, λ0,next=0.32 返回step2(重新计算p’ λ，然后 c(λ1)，…）。结束结束条件为当前的λ与前一组λ相差很小（比如，<0.01）

42 其它平滑算法

43 线性插值 在简单线性插值中，权值仅仅是一个数，我们可以定一个更通用的和powerful的模型，其系数值是历史的函数，通用线性插值的形式是：
and

44 线性插值 “桶”平滑 根据历史频率信息，采用几个λ向量代替一个 事实上：不存在一个单独集合对应每个历史数据，但是可以对应近似的历史数据:
例如：h=(micrograms,per) 我们可以得到 λ(h)=(0.999,0.0009, , ) (因为“cubic”是唯一可以紧随的词语) 事实上：不存在一个单独集合对应每个历史数据，但是可以对应近似的历史数据: λ(b(h)),其中b: V2→N (对应三元模型) b 根据可靠性来区分历史数据（频率信息）

45 “桶”平滑算法 利用held out数据确定“桶”函数 根据桶数平分held out数据 对各个桶及其数据应用以上算法
预先设定需要的数量，如1000个桶 计算1个桶中的历史频率总数 fmax(b) 根据最高频bigram逐渐填满所有桶，使得频率总和不超过fmax(b)（可能会略微超过1000个桶） 根据桶数平分held out数据 对各个桶及其数据应用以上算法

46 绝对折扣 Absolute discounting
对所有的非0 MLE频率减一个较小的常数，把获得的频率分不到不出现的事件上。

47 线性折扣 linear discounting
非0的乘一个系数，把获得的概率分不到不出现的事件上

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

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

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