统计自然语言处理基本概念

语言模型大纲•概述•参数估计•基本平滑算法•其它平滑算法概述噪声通道模型•原型•模型：出错的概率•举例：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,10,1,1,0,0,1,1,0输入输出噪声通道的应用•OCR–文本打印(引入噪声),扫描图像•手写识别–文本神经肌肉(引入噪声),扫描图像•语音识别–文本朗读(引入噪声)声学波形•机器翻译–目标语言翻译(引入噪声)源语言•其它：词性标注–词性序列选择词形文本噪声通道：黄金规则•适用于OCR，手写识别，语音识别，机器翻译，词性标注等各个问题•贝叶斯公式：P(A|B)=P(B|A)P(A)/P(B)•Abest=argmaxAP(B|A)P(A)•P(B|A)是声学/图像/翻译等模型–在不同领域用不同的术语来描述•P(A)是语言模型什么是语言模型(LanguageModel)•语言模型是用来计算一个句子的概率的概率模型–例如：P(w1,w2,…,wn)•语言模型的用途–决定哪一个词序列的可能性更大–已知若干个词，预测下一个词•应用–语音识别–机器翻译–上下文敏感的拼写检查应用于语音识别•有的词序列听起来很像，但并不都是正确的句子–例子1：•Iwenttoaparty.√•Eyewenttwoabartea.–例子2：•你现在在干什么？√•你西安载感什么？应用于机器翻译•给定一个汉语句子–例如：王刚出现在电视上。–英文译文：•WangGangappearedinTV.•InWangGangappearedTV.•WangGangappearedonTV.√应用于拼写检查•举例–汉语•我自己知道√•我自已知道–英语•WangGangappearedonTV.√•WangGangappearedofTV.参数估计完美的语言模型•对于词序列W=w1,w2,…,wn•如何计算p(W)？•根据链式规则：p(W)=p(w1)p(w2|w1)…p(wn|w1,…,wn-1)•即使对于很小的n，上面的理想公式也很难计算，因为参数太多马尔科夫链•有限的记忆能力–不考虑太“老”的历史–只记住前k个词w1,…,wk–称为k阶马尔科夫近似•p(W)=∏i=1…dp(wi|wi-k,…,wi-1),d=|W|N元语言模型•n-1阶马尔科夫近似称为n元语言模型(LM,LanguageModel)–p(W)=∏i=1…dp(wi|wi-n+1,…,wi-1),d=|W|•n越大，需要估计的参数越多，假设词汇量为20,000模型需要的参数数量0阶(一元Unigram)20,0001阶(二元bigram)20,000*19,999=400million2阶(三元trigram)20,0002*19,999=8trillion3阶(四元four-gram)20,0003*19,999=1.6*1017语言模型的讨论•n多大？–理论上讲，越大越好–经验值：3，trigram用的最多•four-gram需要太多的参数，很难估计了•目前一般直接计算词形，不进行语言学处理，如形态还原等•可靠性(Reliability)和可区别性(Discrimination)成反比，需要折中–n越大，区别力越大；n越小，可靠性越高可靠性和区别性•可靠性(Reliability)和可区别性(discrimination)•为了有效地推导一个特征，我们希望通过模型的其它特征来预测它，把这些特征分成等价类便于我们预测新的数据。•分类特征越多，对未知分布的目标特征的预测就更精确，即有较好的可区别性，但是这样对每一个分类其实例就较少，统计的数据就不可靠，所以在划分等价类时要在可靠性和可区别性之间找一个折衷点。长度问题•n;wnp(w)=1•n=1…wnp(w)1()•我们试图对所有的词序列建立模型–对于固定长度的任务，没有问题，n一旦固定，累计和为1•比如Tagging等–对于变长的任务，需要对比较短的句子进行折扣•一般模型–对于长度为n的词序列•P’(w)=np(w),n=1…n=1•n=1…wnp’(w)=1•从数据中估计n参数估计•参数：用来计算p(w|h)的数值•从数据中得到•数据准备–去掉格式符号–定义词的边界–定义句子边界(插入s和/s等记号)–字母的大小写（保留、忽略或者智能识别）–数字（保留、替换为num等）最大似然估计•最大似然估计MLE–是对训练数据的最佳估计•从训练数据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选择的参数使训练语料具有最高的概率，它没有浪费任何概率在于没有出现的现象中•但是MLE通常是不适合NLP的统计语言推导的，因为数据稀疏，如果一个为0，会向下传播…•一个例子说明数据稀疏：从IBMLaserPatentText语料中1.5Million的词进行训练，在同一语料中的测试文本中，新出现23%的trigramtokens.举例1•p(z|xy)=?•假设训练语料为：…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，因为数据比较充足•对交叉语言的比较很有用•基于字和基于词的交叉熵的换算关系–HS(pc)=HS(pw)/句子S中的平均词长举例2•训练数据:–s0sHecanbuyyouthecanofsoda/s–Unigram:(8wordsinvocabulary)•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交叉熵•交叉熵–S=s0sItwasthegreatestbuyofall/s•HS(p1)=HS(p2)=HS(p3)=∞，原因是：–所有的unigrams除了p1(the),p1(buy),andp1(of)都是0–所有bigram的概率都是0.–所有trigram的概率都是0.•我们希望使每个概率都是非零的零概率问题•原始的Trigram模型估计–一定会有很多概率为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)•务必确保•有许多数据平滑的方法discountedwDwpwp))(')((wwp1)('折扣discounting•回退Back-off–如果n-gram的值为零，则用n-1gram来计算•平滑Smoothing–将MLE方法与其它方向相混合，保证没有0概率的值加1平滑•最简单，但不是真的能用–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:swhatisitwhatissmall?|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(whatisit?)=0.252*0.1252≈0.001p(itisflying.)=0.125*0.25*02=0–p’(it)=0.1,p’(what)=0.15,p’(.)=0.05,p’(whatisit?)=0.152*0.12≈0.0002p’(itisflying.)=0.1*0.15*0.052≈0.00004Trigramthey,do,approach1they,do,have2they,do,Link1they,do,not7they,do,on3they,do,open1they,do,so1they,do,under5Bigramdo,anything2do,approach1do,no1do,not97do,Novell1do,offer1...they,do22Unigramdo384...C(they,do,not)C(do,not)=7=97PMLE(not|they,do)PMLE(not|do)=7/22=0.318=97/384=0.253PMLE(offer|they,do)=0/22=0PMLE(have|they,do)=2/22=0.091举例Addone举例P+1(not|they,do)P+1(offer|they,do)P+1(have|they,do)757000.0543,10228543,10,1,,dotheyCnotdotheyC9470000.0543,10221543,10,1,,dotheyClikedotheyC284000.0543,10223543,10,,,dotheyChavedotheyCVocabularySize(V)=10,543小于1平滑•加入λ系数-T:训练数据,V:词表,w:词预测p’(w|h)=(c(h,w)+λ)/(c(h)+λ|V|),λ1特别:非条件分布时p’(w)=(c(w)+λ)/(|T|+λ|V|)•举例：T:swhatisitwhatissmall?|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(whatisit?)=0.252*0.1252≈0.001p(itisflying.)=0.125*0.25*02=0–取λ=0.1–p’(it)=0.12,p’(what)=0.23,p’(.)=0.01,–p’(whatisit?)=0.232*0.122≈0.0007p’(itis