自然语言处理讲座6第六章马尔可夫模型课件.ppt

1、1噪声信道模型 噪声信道模型 目标:通过有噪声的输出信号试图恢复输入信号)()|(maxarg)()()|(maxarg)|(maxargIPIOPOPIPIOPOIPIIII2噪声信道模型的应用噪声信道模型的应用 噪声信道模型是一种普适性的模型，通过修改噪声信道模型是一种普适性的模型，通过修改噪声信道的定义，可以将如下应用纳入到这一噪声信道的定义，可以将如下应用纳入到这一模型的框架之中模型的框架之中 语音识别语音识别 一个声学信号对应于一个语句，一个语音识别器需找到其对应的可能性最大的语言文本 根据贝叶斯公式 信息源对应于以概率 生成语句文本，噪声信道对应于以概率分布 将语句文本转换成声音信

2、号。语音识别的目的就是由通过噪声信道而输出的声音信号恢复其原始的语句文本。)|(maxargATpTT)|()(maxarg)()|()(maxargTApTpApTApTpTTT)(Tp)|(TAp3噪声信道模型的应用噪声信道模型的应用 信源以概率 生成语句文本，信道为 ，语音/图像/翻译文本/字音转换模型 手写体汉字识别手写体汉字识别 文本书写文本书写(或者打印、扫描或者打印、扫描)图像图像 文本校错文本校错 文本输入编辑带有错误的文本文本输入编辑带有错误的文本 机器翻译机器翻译 目标语言的文本翻译源语言文本目标语言的文本翻译源语言文本 音字转换音字转换 文本字音转换汉字（拼音）编码文本字

3、音转换汉字（拼音）编码 信源以概率 生成词性标注序列，信道 为词性标注序列转为词序列的转换模型 词性标注词性标注 词性标注序列词性词串转换词串词性标注序列词性词串转换词串)(Tp(|)p O T)(Tp(|)p O T4语言模型语言模型 P(T):语言模型 如何计算P(T)?根据链规则 问题:参数空间过大,无法实用!1 212131 21 21()()(.)()(|)(|).(|.)nnnPTPSPww wp w p w w p w wwp w ww w5“香农游戏香农游戏(Shannon Game)”Claude E.Shannon.“Prediction and Entropy of Pr

4、inted English”,Bell System Technical Journal 30:50-64.1951.给定前给定前n-1个词个词(或者字母或者字母),预测下一个词预测下一个词(字母字母)从训练语料库中确定不同词序列概率从训练语料库中确定不同词序列概率6基本思想基本思想:考察一小段连续词汇序列（一个语句）考察一小段连续词汇序列（一个语句）该语句出现的可能性有多大？该语句出现的可能性有多大？“马尔科夫假设马尔科夫假设”下一个词的出现仅仅依赖下一个词的出现仅仅依赖于它前面的一于它前面的一 个词或者几个词个词或者几个词 假设下一个词的出现依赖于它前面的一个词假设下一个词的出现依赖于它前

5、面的一个词 :bigram 假设下一下一个词的出现依赖于它前面的两个词假设下一下一个词的出现依赖于它前面的两个词 :trigram).|().|()|()().()()(12121312121nnnwwwwpwwwpwwpwpwwwPSPIP)|().|()|()(123121nnwwpwwpwwpwp)|().|()|()(12213121nnnwwwpwwwpwwpwp7N-gram语言模型 最大相似度估计（Maximum Likelihood Estimate）“n-gram”=n个词构成的序列个词构成的序列 unigram bigram trigram four-gram(quadgr

6、am 4-gram)构造（训练）N-gram语言模型：在训练语料库中统计获得n-gram的频度信息).().().|(12121121nnnnwwwCwwwCwwwwP8N的选择：可靠性的选择：可靠性 vs.辨别力辨别力“我我 正在正在 _”讲课讲课?图书馆图书馆?听课听课?学习学习?借书借书?“我我 正在正在 图书馆图书馆 _”学习学习?借书借书?9可靠性可靠性 vs.辨别力辨别力 更大的更大的 n:对下一个词出现的约束性信息对下一个词出现的约束性信息更多，更大的辨别力更多，更大的辨别力 更小的更小的n:在训练语料库中出现的次数更在训练语料库中出现的次数更多，更可靠的统计结果，更高的可靠性多

7、，更可靠的统计结果，更高的可靠性 10N的选择的选择词表中词的个数词表中词的个数|V|=20,000 词词n所有可能的所有可能的n-gram的个数的个数2(bigrams)400,000,0003(trigrams)8,000,000,000,0004(4-grams)1.6 x 101711问题问题 假设我们使用假设我们使用trigram模型模型 如果某个如果某个 那么那么P(S)=0 数据稀疏问题数据稀疏问题 必须保证必须保证 从而使从而使)|().|()|()()(12213121nnnwwwpwwwpwwpwpSP0)()()|(121212iiiiiiiiwwCwwwCwwwp0C0

8、P12在训练语料库中在训练语料库中:13最大相似度估计最大相似度估计:14期望概率分布期望概率分布:15期望概率分布期望概率分布:16“平滑（平滑（Smoothing）”降低已出现的降低已出现的n-gram条件概率分布，以条件概率分布，以使未出现使未出现n-gram条件概率分布非条件概率分布非0 又可称为又可称为“折扣方法折扣方法”(Discounting methods)（确认）确认）“Validation”特指使用两个不特指使用两个不同的训练语料库的平滑方法同的训练语料库的平滑方法17拉普拉斯定律拉普拉斯定律LaPlaces Law(加一平滑法加一平滑法adding one)18拉普拉斯定

9、律拉普拉斯定律(adding one)(,1).().(2121nnnLapVBBNwwwCwwwP19拉普拉斯定律拉普拉斯定律20Lidstone 定律定律(Lidstones Law)P=n-gram w1w2wn的概率的概率C=n-gram w1w2wn在训练语料库中的个数在训练语料库中的个数N=训练语料库中的训练语料库中的 n-grams 总数总数B=所有可能的所有可能的n-gram个数个数 =一个小的整数一个小的整数M.L.E最大相似度估计最大相似度估计:=0LaPlaces Law拉普拉斯定律拉普拉斯定律:=1Jeffreys-Perks 定律定律:=11nLidnC(ww)P(w

10、w)NB21Jeffreys-Perks Law22Lidstones Law存在的问题存在的问题 的确定的确定.对所有未出现的对所有未出现的n-gram都给与相同的概都给与相同的概率率 与最大相似度估计成线性关系与最大相似度估计成线性关系23Good-Turing估计 如果 C(w1,.,wn)=r 0,PGT(w1,.,wn)=r*/N 此处:r*=(r+1)S(r+1)/S(r)(r+1)N(r+1)/N(r)这里S(r)是Nr的期望平滑估计.If C(w1,.,wn)=0,PGT(w1,.,wn)N1/(N0N)例：建立频度-n-gram(本例为bigram)个数表(词表中词数1458

11、5，语料库中出现的各不相同的bigram总数199252个，bigram总数为617091个)24Good-Turing估计示例 对于未出现的bigramPGT(w1,.,wn)N1/(N0N)=138741/(14585*14585-199252)*617091)=1.058*10E-911387412254133105314599753565624867175481342911061089625Good-Turing估计示例(续)对于仅出现过一次的bigram：r*=(r+1)N(r+1)/N(r)=2*25413/138741=0.3663简单简单 Good-Turing Gale&Sa

12、mpson,1995:对于比较大的 r,Nr=arb(b -1)用线性回归的方法估算 a 和 b:log Nr=log a+b log r,对于比较小的 r,直接使用Nr26关于Good-Turing平滑的两个问题 两个问题：Good-Turing估计是否合理？令 Good-Turing估计是如何推导出来的？Stanley F.Chen.Building Probabilistic Models for Natural Language.PhD thesis,Harvard University,June 1996.*0?rrr nN121212.12.(.)(.)1nnGTnw wwGTnw

13、 wwfw wwPw wwN12(.)*GTnfw wwr*11000(1)(1)rrrrrrrrNr NrNrNNN27平滑方法可以分成两类平滑方法可以分成两类 修改频率值修改频率值:Lidstones Law(incl.LaPlaces Law and Jeffreys-Perks Law);Good Turing Smoothing;其他方法其他方法:修改条件概率修改条件概率.28简单线性插值平滑211 12213312(|,)()(|)(|,)01,1linnnnnnnnniiiP wwwP wP wwP www 如何确定 经验设定 优化算法设定(Expectation Maximiz

14、ation Algorithm)29其他常用平滑方法 Held out 平滑 Back-off 平滑 Witten-Bell平滑等等30平滑的效果 数据平滑的效果与训练语料库的规模有关 数据平滑技术是构造高鲁棒性语言模型的重要手段 训练语料库规模越小,数据平滑的效果越显著,训练语料库规模越大,数据平滑的效果越不显著,甚至可以忽略不计31现有的主要语言模型 上下文的定义决定了语言模型的不同.如果 这样的语言模型称为上下文无关模型 采用MLE:又称为一元文法统计模型)|(CwwPi)()|(wwPCwwPiiNNwwPwi)(32现有的主要语言模型 N元文法统计模型 自从几十年前在大词表语言识别系

15、统中首次使用Trigram以来,直到现在,Trigram模型仍旧是在实际应用中表现最佳的语言模型,并且成为许多其他的语言模型的重要组成部分.)|()|(1,1 iniiiwwwPCwwP33现有的主要语言模型 N-pos模型或者表示词w的词类 参数空间较小 ,不如n-gram语言模型精确)().()(|()|(121ininiiiwgwgwgwwPCwwP)(wgVGN 1)(|()().()(|)()|(121iiininiiiwgwwPwgwgwgwgPCwwP34一元模型,N-gram模型与N-pos模型之间的关系 考察N-pos模型的极端情况,即当整个模型只有一个词类,与每一个词都有一

16、个各自不同的词类的情况:如果N-pos模型只有一个词类,那么前N-1个词类没有提供任何上下文信息,于是N-pos模型退化为Unigram模型;如果每一个词都有一个各不相同的词类,那么这样的N-pos模型等价于N-gram模型.Unigram模型经常使用的N-pos模型词类数一般在25500之间N-gram模型35动态、自适应、基于缓存的语言模型 在自然语言中，经常出现某些在文本中通常很少出现的词，在某一局部文本中突然大量出现的情况。能够根据词在局部文本中出现情况动态地调整语言模型中的概率分布数据的语言模型称为动态、自适应或者基于缓存的语言模型。36动态、自适应、基于缓存的语言模型 方法 将N个

17、最近出现过的词 存于一个缓存中,作为独立的训练数据.通过这些数据,计算动态频度分布数据 将动态频度分布数据与静态分布数据(由大规模性语料训练得到)通过线性插值的方法相结合:11.iNiNiwww)|(12iiidynamicwwwP)|()1()|()|(121212iiistaticiiidynamiciiincombinatiowwwPwwwPwwwP1037语言模型的评价 如何评价语言模型的优劣 根据其在实用系统中的表现 优点：直截了当 缺点：不客观、干扰因素过多、缺乏针对性 统计语言模型的专用评价量度-交叉熵38Kullback-Leibler(KL)距离 Kullback-Leibl

18、er(KL)距离（相关熵）两个概率密度函数p(x)与q(x)它们的相关熵由下式给出：描述了两个概率分布之间的差异（D(p|q)=0 iff p=q）非量度（不满足交换率和三角不等式）()(|)()log()xXp xD pqp xq x()(|)(log)()pp XDpqEq X39语言与其模型的交叉熵 我们构造的语言模型为q(x)，如何评价它的好坏?Idea:如果q(x)与正确的语言模型p(x)的相关熵越小，模型越好 问题是我们并不知道p(x)可以借助交叉熵 某语言L，其真实的概率分布为p(x)，我们构造的该语言的概率模型为q(x)，那么该语言与其模型的交叉熵为：(,)()(|)()log

19、()XH X qH XD pqp xq x 1111(,)lim()log()nnnnxH L mp xm xn 40语言与其模型的交叉熵 如果我们将语言视为平稳各态可遍历的随机过程：那么迷惑度1111(,)limlog()log()nnnH L mm xm xnn 11(,)11(,)2()nHxmnnnperplexity xmm x41马尔可夫模型 马尔可夫模型是一种统计模型,广泛地应用在语音识别，词性自动标注，音字转换，概率文法等各个自然语言处理的应用领域。马尔可夫(18561922)，苏联数学家。切比雪夫的学生。在概率论、数论、函数逼近论和微分方程等方面卓有成就。经过长期发展，尤其是

20、在语音识别中的成功应用，使它成为一种通用的统计工具。马尔可夫模型的典型应用:语音识别,音字转换,词性标注42回顾:n-gram语言模型 链规则：N-gram语言模型:N-1阶马尔可夫过程（链）仅适用一种概率分布进行统计推导，例如在trigram模型中，43马尔可夫假设（特征）设 X=(X1,.,Xt)是随机变量序列，其中每个随机变量的取值 在有限集 S=s1,sn,S称为状态空间,马尔可夫特征是：有限历史假设（有限历史假设（Limited(Horizon，Context,History）):P(Xt+1=sk|X1,.,Xt)=P(X t+1=sk|Xt)时间不变性假设（时间不变性假设（Tim

21、e Invariant）（）（马尔可夫马尔可夫过程的稳定性假设）过程的稳定性假设）:这种条件依赖，不随时间的改变而改变。如果X具有这些特征，那么这个随机变量序列称为一个马尔可夫过程（链）11,2,3.,(|)(|)iiiTy xS P Xy Xxp y x 44N阶马尔可夫模型 Trigram的情形：只需修改状态空间的定义 定义新的变量 使得 并且约定：SQiSSS45马尔可夫模型的形式化表示 一个马尔可夫模型是一个三元组(S,A)其中 S是状态的集合，是初始状态的概率,A是状态间的转移概率。46马尔可夫模型的图形表示47隐马尔可夫模型(HMM)各个状态（或者状态转移弧）都有一个输出,但是状态

22、是不可见的。最简单的情形:不同的状态只能有不同的输出48隐马尔可夫模型 增加一点灵活性：不同的状态，可以输出相同的输出：49隐马尔可夫模型 再增加一点灵活性：输出在状态转移中进行。50隐马尔可夫模型 最大的灵活性：在状态转移中以特定的概率分布输出51HMM的形式化定义 HMM是一个五元组(S,K,A,B)，其中 S是状态的集合，K是输出字符的集合，是初始状态的概率，A是状态转移的概率。B是状态转移时输出字符的概率。52马尔可夫过程程序t:=1;以概率i在状态 si 开始(i.e.,X1=i)Forever do Move from state si to state sj with proba

23、bility aij(i.e.,Xt+1=j)Emit observation symbol ot=k with probability bijkt:=t+1End 53隐马尔科夫模型的三个基本问题 给定一个模型 ，如何高效地计算某一输出字符序列的概率 给定一个输出字符序列O，和一个模型 ，如何确定产生这一序列概率最大的状态序列 给定一个输出字符的序列O，如何调整模型的参数使得产生这一序列的概率最大(S,K,A,B)(|)PO121(,.,)TXXX54网格（Trellis）55问题1评价（Evaluation）给定一个模型 ，如何高效地计算某一输出字符序列的概率(S,K,A,B)(|)POo

24、To1otot-1ot+11(.),(,)(|)TOooA BP O计算56方案1)|(),|()|,(XPXOPXOPTToxoxoxbbbXOP.),|(2211TTxxxxxxxaaaXP132211.)|(XXPXOPOP)|(),|()|(oTo1otot-1ot+1x1xt+1xTxtxt-157方案1（Cont.）111111111.)|(ttttToxxxTtxxoxxbabOPoTo1otot-1ot+1x1xt+1xTxtxt-1算法复杂度太高，需要)2(TTnO 58方案2向前过程（forward procedure）使用动态规划方法实现更加高效的算法 动机：对于任意一个

25、长度为动机：对于任意一个长度为t+1的状态序列来说，的状态序列来说，其前其前t个输出字符出现的概率是相同的个输出字符出现的概率是相同的 定义定义:向前变量向前变量oTo1otot-1ot+1x1xt+1xTxtxt-1)|,.()(1ixooPttti59方案2向前过程（forward procedure）cont.)|(),.()()|()|.()()|.(),.(1111111111111111jxoPjxooPjxPjxoPjxooPjxPjxooPjxooPtttttttttttttt)1(tj60方案2向前过程（forward procedure）cont.NijoijittttNi

26、tttttNitttttNittttbatjxoPixjxPixooPjxoPixPixjxooPjxoPjxixooP.1111.1111.11111.1111)()|()|(),.()|()()|,.()|(),.(61向前过程算法 1、初始化 2、推导 3、总合1(1)()iiibo11.(1)(),1,1tjiijjoiNtt a btTjN1(|)(1)NiiP OT62向前过程例RRGB1.6.60.2.00.0.0.6.2.2.2.5.3.0.3.7RGB.5.6.4.4.1=1 0 0T.5.6.18.6.2.048.0.4.2.1.0.4.0.5.2.018.6.5.0504

27、.01116.4.5.1.3.4.3.5.2.0018.6.3.01123.01537.4.3.1.7.4.763问题2 解码（decoding）给定一个输出字符序列O，和一个模型 ，如何确定产生这一序列概率最大的状态序列121(,.,)TXXXoTo1otot-1ot+1)|(maxargOXPX(,)argmax(|)argmaxargmax(,)()XXXP X OP X OP X OP O64问题2 解码（decoding）cont.),.,.(max)(1111.11ttttxxjojxooxxPtt在t时刻到达状态j，输出字符Ot时，输出前面t-1个字符的最可能路径的概率65Vit

28、erbi algorithm初始化递归结束得到最优路径11()()iiib o111()max()()ttijjti Nji a b o)(max1iPTNi0)(1i111()argmax()()ttijjti Nji a b o)(maxarg1iqTNiT1,1 ),(11Ttqqttt123states66Viterbi算法例.6.2.2.2.5.3.0.3.7RGB.5.6.4.4.1=1 0 0TRRGB.5.2.0018.00648.01008.4.3.1.7.4.7.6.3.61.60.2.00.0.0.5.2.018.6.5.036.00576.4.5.1.3.4.3.5.6

29、.18.6.2.048.0.4.2.1.0.4.067问题3 参数估计已知输出字符序列，找到产生该序列可能性最大的模型无法用分析方法求解给定一个模型和输出字符序列，任意设定初始参数值，通过不断循环更新参数的方法，设法达到最优Baum 1970oTo1otot-1ot+1a r g m a x(|)PO68基本思想1.设定模型的初始值,old.2.基于old，计算输出O 的概率3.如果 P(O|new)-P(O|old)Sj的转移概率Njtijipt.1),()(处于状态Si的概率70Baum-Welch算法（cont.）71Baum-Welch(cont.)oTo1otot-1ot+1ABAA

30、ABBBB)1(iiNow we can compute the new estimates of the model parameters.TtiTttijtjipa11)(),(Ttikottiktibt1:)()(72Baum-Welch(cont.)又称为向前向后算法（Forward-backward algorithm）Baum 等人证明了 经常得到局部最优解-爬山法的固有缺点 一种通用机器学习算法-期望最大值（Expectation Maximum Algorithm）算法的特殊形式 一种无指导的机器学习算法，效果较有指导为差。(|)(|)P OP O 73基于HMM的词性标注 词

31、性标注（Part-of-Speech tagging）回顾：作用：句法分析的前期步骤 难点：兼类词 基于规则的词性标注 基于转换的错误驱动的词性标注 基于HMM的词性标注74基于HMM的词性标注 问题的形式化 设词性标记为M个 标记集合:t_1,.,t_M.词表中词的个数为 V 词集合:w_1,.,w_V.设有一个由n个词构成的词序列S=w1,w2wn 目标为找到最优的词性序列T=t1,t2tnargmaxPr(|)bestTTT S75基于HMM的词性标注 如何计算 和?为使问题简化，假定：词wi 的出现，仅仅依赖于它的词性标记，不依赖于其他因素（例如它前一个词的出现）标记 ti 的出现仅仅

32、条件依赖于它前面的标记ti-1(马尔科夫假设)argmaxPr(|)argmax(|)()bestTTTT SP S T P T(|)P S T()P T11Pr(|)Pr()(|)(|)niiiiiS TTp w t p tt76基于HMM的词性标注 HMM的状态集合：词性标记集合 HMM输出字符集合：词汇集合notation:ti is the ith tag in a tag sequence,t_i represents the ith tag in the tag set t_1,.,t_M i:p(t_i|*start*)状态t_i的起始概率 aij:p(t_j|t_i)从状态 t

33、_i 到状态 t_j的转移概率 bjk:p(w_k|t_j)状态t_j的词w_k发射概率77参数训练 模型的参数未知 假设有已经标注好的语料库:S=w1,w2wn T=t1,t2tn 如何从语料库中得到这样的参数 使用最大相似度估计()(|)()j iijiC t tP ttC tkjkjjC(w,t)p(w|t)=C(t)78音字转换 状态集：词 发射字符集：拼音i:p(t_i|*start*)状态t_i的起始概率 aij:p(t_j|t_i)从状态 t_i 到状态 t_j的转移概率 bjk:p(w_k|t_j)状态t_j的词w_k发射概率79什么是句法分析 判断输入的词序列能否构成一个合乎

34、语法的句子，确定合乎语法句子的句法结构 运用句法规则和其他知识将输入句子中词之间的线性次序，变成一个非线性的数据结构（例如短语结构树或有向无环图）80为什么要进行句法分析 例一：音字转换例 一只小花猫 例二：机器翻译例（Prepositional Phrase Attachment）Jan hit the girl with long hair Jan hit the girl with a hammer 例三：信息检索例 哪个球队获得了亚洲杯冠军？日本队击败中国队获得亚洲杯冠军81句法分析的难点 句法分析的难点：语法歧义：一个句子对应着几种句法分析结果“咬死了猎人的狗”“那只狼咬死了猎人的狗

35、”“那只咬死了猎人的狗失踪了”汉语句法分析的独特性（朱德熙语法答问语法讲义）汉语没有形态 语序灵活 词类和句法成分不存在一一对应的关系 汉语句子的构造原则与词组的构造原则基本上是一致的 汉语语法形式化工作滞后 深层分析与浅层分析82句法分析系统 一个句法分析系统通常由两部分组成 形式语法体系 匹配模式 短语结构语法 扩充转移网络 树邻接语法(TAG)基于合一运算的语法（广义短语结构语法、词汇功能语法、功能合一语法、基于中心词驱动的短语结构语法(HPSG)）基于词的语法（链语法、依存语法、配价语法）分析控制机制 模式匹配技术 基于短语结构语法分析算法（厄尔利（Earley）分析算法、富田胜（To

36、mida）分析算法、线图（Chart）分析算法、确定性分析算法等等）基于扩充转移网络的分析算法 链分析算法83概率上下文无关文法（Probabilistic(Stochastic)Context Free Grammar）随机上下文无关语法可以直接统计语言学中词与词、词与词组以及词组与词组的规约信息，并且可以由语法规则生成给定句子的概率。定义：一个随机上下文无关语法（PCFG）由以下5部分组成：（1）一个非终结符号集N（2）一个终结符号集（3）一个开始非终结符SN（4）一个产生式集R（5）对于任意产生式rR，其概率为P(r)产生式具有形式XY，其中，X N,Y(N)*()1P X84PCFG的

37、三个基本假设 CFG的简单概率拓广 基本假设 位置无关(Place invariance)上下文无关(Context-free)祖先无关(Ancestor-free)分析树的概率等于所有施用规则概率之积()1P X85举例 给定如下概率文法G(1)S-AA p1=1/2(2)S-B p2=1/2(3)A-a p3=2/3(4)A-b p4=1/3(5)B-aa p5=1/2(6)B-bb p6=1/2那么：P(tree1)=1/2*2/3*2/3=2/9P(tree2)=1/2*1/3*1/3=1/18P(tree3)=1/2*1/2=1/4P(tree4)=1/2*1/2=1/486PCFG

38、的三个基本问题 1、一个语句W=w1w2.wn的P(W|G),也就是产生语句W的概率？2、在语句W的句法结构有歧义的情况下,如何快速选择最佳的语法分析(parse)?3、如何从语料库中训练G的概率参数,使得P(W|G)最大(|)P WGarg m ax(|,)treeP tree WGarg max(|)GP WG87问题1&2 思路 运用动态规划以及剪枝技术计算得出一个语句的多个句法分析形式的概率，选择概率最高的结果作为句法分析的结果88向内（Inside）算法 非终结符A的内部概率（Inside probability）定义为根据文法G从A推出词串 的概率，记为 称为向内变量SABC11.

39、iww.ikww1.kjww1.jnww.ijww,()i jAij,()i jA89问题1 1、一个语句W=w1w2.wn的P(W|G),也就是产生语句W的概率？(|)P WG90向内概率公式 ,()(.|)i jijAP wwAij1,(.,.,|)ikkjB C kP ww B ww C A1,(,|)(.|,)(.|.,)ikkjikB C kP B C A P w wA B C P ww w w A B C1,(,|)(.|)(.|)ikkjB C kP B C A P w wB P ww C,1,()()()i kkjB C kP ABCBC独立性假设独立性假设祖先无关假设,()(

40、)i jiAP Awij91向内算法（自底向上）输入：G=(S,N,R,P),字符串 输出：1、初始化：2、归纳计算：j从1到n，i从1到n-j，重复下面计算 3、结束：12.nWw ww1,(|)()nP WGS,()(),1i iiAP AwA Nin,1,()()()()i iji kkijB C N i k ijAP ABCBC 11,(.|)()nnP SwwGS92向内算法计算示例 SNP VP 1.0NPNP PP 0.4 PPP NP 1.0 NPJohn 0.1 VPV NP 0.7NPbone 0.18 VPVP PP 0.3NPstar 0.04 Pwith 1.0NPf

41、ish 0.18 Vate 1.0NPtelescope 0.193向内算法计算示例1234567初始化89101194向内算法计算示例初始化 1 NPJohn 0.1 2 Vate 1.0 3 NPfish 0.18 4 Pwith 1.0 5 NPbone 0.18递归计算 6 VPV NP 0.7 7 PPP NP 1.0 8 SNP VP 1.0 9 NPNP PP 0.4 10 VPVP PP 0.3 VPV NP 0.7结束 SNP VP 1.01,1()0.1N P2,2()1.0V4,4()1.0P3,3()0.1 8N P5,5()0.1 8N P2,3()0.7*1.0*0

42、.180.126VP4,5()1.0*1.0*0.180.18PP1,3()1.0*0.1*0.1260.0126S3,5()0.4*0.18*0.180.01296S2,5()0.3*0.126*0.180.7*1.0*0.012960.015876S1,5()1*0.1*0.015876=0.0015876S95问题2 在语句W的句法结构有歧义的情况下,如何快速选择最佳的语法分析(parse)?arg max(|,)treeP tree W G96Viterbi 算法 输入：G=(S,N,R,P),字符串 输出：t*(W在G下最可能的分析树)算法：1、初始化 2、动态规划：j从1到n,i从

43、1到n-j,重复如下步骤 3、结束 t*的根节点为S（文法开始符号）；从 开始回溯，得到S的最优树结构 记录了非终结符及其统摄的起止位置1,(*)()nP tS12.nWw ww,()()i iiAP Aw,1ANin,1,;,1,;()max()()()()arg max()()()i iji kkijB CN i k iji iji kkijB CN i k ijAP ABCBCAP ABCBC 1,()nS,()i ijA97Viterbi算法示例98问题3 参数训练问题 从树库直接统计Treebank Grammar 最大似然估计 依赖于艰巨的工程：树库建设 向内向外算法 迭代过程 与

44、初始参数相关99向内向外算法.ijww,()ijA.ijwwij100外部概率公式1,1,()0,nASAAS,1111111,1111,1,1,()(.,.|)(.,.)()(.)(.,.)()(.)()()()()()()i jijniknjkB C j khjnhiB C h ii kjkh jh iB C j kBAP wwA wwGP wwC ww P CAB P BwwP wwC ww P CBA P BwwC P CABBC P CBAB,C h i101计算外部概率示例（自顶向下）102规则的概率 文法中每条规则的概率，采用下式估算 S-NP VP VP-V NP NP-N N

45、P-NP 的 NP NP-VP 的 NP()()()N um berAPAN um berA()()()()()Number NPNPNPNNumber NPNNumber NPNP NPNumber NPVP NP的的103规则的概率Penn Treebank(S(NP-SBJ The move)(VP followed(NP(NP a round)(PP of(NP(NP similar increases)(PP by(NP other lenders)(PP against(NP Arizona real estate loans),(S-ADV(NP-SBJ*)(VP reflect

46、ing(NP(NP a continuing decline)(PP-LOC in(NP that market).)104规则使用次数的数学期望105规则使用次数的数学期望106向内向外算法 EM算法运用于PCFG的参数估计的具体算法。初始化：随机地给P(A-)赋值，使得P(A-)=1.由此得到语法G0.iBC)和C(A-a)M步骤：用E-步骤所得的期望值,利用:重新估计P(A-),得到语法Gi+1 循环计算:i+,重复EM步骤,直至P(A-)收敛.)()()(ACACAP107PCFG的优缺点 优点 可以对句法分析的歧义结果进行概率排序 提高文法的容错能力（robustness）缺点 没有

47、考虑词对结构分析的影响 没有考虑上下文对结构分析的影响 许多当前的获得较高精度的句法分析系统以PCFG为基础108浅层句法分析技术 从完全句法分析（complete parsing）到浅层句法分析（shallow parsing）真实语料的复杂性 语言知识的不足 提高分析的效率 应用目标驱动 浅层分析的其他名称：部分分析（partial parsing），组块分析（chunking）109部分分析示例110基于HMM的浅层分析技术 识别目标：非递归的NP 组块分析：在线性序列中插入括号，来标示组块边界 The/DT prosecutor/NN said/VB in/IN closing/NN

48、that/CS 111短语边界 一对词性标记 表示一个NP组块的开始 表示一个NP组块的结束 表示两个NP组块相邻 I表示不是NP组块边界，且处于NP内部 O表示不是NP组块边界，且处于NP外部,112基于HMM的NP组块边界标注 带有词性标记、组块边界标记的语料库 可观察符号序列：词性标记对序列 隐状态：5个可能的NP组块边界标记 通过对语料库统计，得到 状态转移矩阵 每个状态输出不同词性标记对的概率,$The prosecutor said in closing that I O 113级联式有限状态句法分析 级联式有限状态分析（Cascaded Finite-State Parsing）

49、114级联式有限状态句法分析过程（1）从左向右扫描输入字符串，按照Li层级上的正则表达式模式进行归约，得到新的模式序列，对于输入串中无法归约的符号，直接输出；（2）i=i+1，在新的Li层级上，用正则表达式模式进行归约（3）不断进行上述步骤，直到无法归约为止；（4）如果归约过程中有多种选择，以覆盖范围最大的归约子串为输入结果115级联式有限状态句法分析示例116写在最后写在最后成功的基础在于好的学习习惯成功的基础在于好的学习习惯The foundation of success lies in good habits117 结束语当你尽了自己的最大努力时，失败也是伟大的，所以不要放弃，坚持就是正确的。When You Do Your Best,Failure Is Great,So DonT Give Up,Stick To The End演讲人：XXXXXX 时 间：XX年XX月XX日