《马尔科夫模型》PPT课件

1、隐马尔科夫模型和词性标注大纲 隐马尔科夫模型 隐马尔科夫模型概述 义务1：计算察看序列的概率 义务2：计算可以解释察看序列的最大能够的形状序列 义务3：根据察看序列寻觅最正确参数模型 词性标注隐马尔科夫模型概述隐马尔科夫模型概述马尔科夫链马尔科夫链 形状序列: X1, X2, X3, 经常是“时序的 从Xt-1到Xt的转换只依赖于Xt-1X2X3X4X1转移概率转移概率Transition Probabilities 假设一个形状Xt有N个能够的值 Xt=s1, Xt=s2,., Xt=sN. 转移概率的数量为：N2 P(Xt=si|Xt-1=sj), 1 i, j N 转移概率可以表示为NN

2、的矩阵或者有向图MM Bigram MM(一阶MM)MM Trigram MM(二阶MM)有限形状自动机 形状：输入输出字母表中的符号 弧：形状的转移 依然是VMM (Visible MM)HMM HMM，从形状产生输出HMM HMM，不同形状能够产生一样输出HMM HMM，从弧产生输出HMM HMM，输出带有概率HMM HMM，两个形状间有多条弧，具有不同的概率隐马尔可夫模型隐马尔可夫模型Hidden Markov Model 估算隐藏于外表事件背后的事件的概率 察看到一个人每天带雨伞的情况，反过来推测天气情况Hidden Markov Model HMM是一个五元组(S, S0,Y, Ps

3、, PY ). S : s1sT 是形状集，S0是初始形状 Y : y1yV 是输出字母表 PS(sj|si):转移(transition)概率的分布，也表示为aij PY(yk|si,sj): 发射(emission)概率的分布，也表示为bijk 给定一个HMM和一个输出序列Y=y1,y2,yk) 义务1：计算察看序列的概率 义务2：计算可以解释察看序列的最大能够的形状序列 义务3：根据察看序列寻觅最正确参数模型义务1：计算察看序列的概率计算察看序列的概率 前提：HMM模型的参数曾经训练终了 想知道：根据该模型输出某一个察看序列的概率是多少 运用：基于类的言语模型，将词进展归类，变计算词与词

4、之间的转移概率为类与类之间的转移概率，由于类的数量比词少得多，因此一定程度防止了数据稀疏问题Trellis or Lattice(栅格)发射概率为1的情况 Y=“toe P(Y)=0.60.881+0.40.11=0.568算法描画 从初始形状开场扩展 在时间点t扩展得到的形状必需可以产生与察看序列在t时辰一样的输出 比如在t=1时，察看序列输出t，因此只需形状A和C得到了扩展 在t+1时辰，只能对在t时辰保管下来的形状节点进展扩展 比如在t=2时，只能对t=1时辰的A和C两个形状进展扩展 每条途径上的概率做累乘，不同途径的概率做累加 直到察看序列全部调查终了，算法终了发射概率不为1的情况 0

5、.236608就是在上述模型下“toe出现的概率Trigram的情况 以Bigram为形状基于类的Trigram模型 N-gram class LM p(wi|wi-2,wi-1) p(wi|ci)p(ci|ci-2,ci-1) C:Consonant(辅音)，V:Vowel(元音)Class Trigram的Trellis 输出Y=“toy重叠(overlapping)的Class Trigram “r有时是元音，有时是辅音，因此p(r|C)和p(r|V)都不为零重叠的类Trigram的Trellis讨论 我们既可以从左向右计算，也可以从右向左计算，甚至可以从中间向两头计算 Trellis的

6、计算对于Forward-Backward也称为Baum-Welch)参数估计很有用义务2：计算可以解释察看序列的最大能够的形状序列Viterbi算法 用于搜索可以生成察看序列的最大约率的形状序列 Sbest=argmaxSP(S|Y) =argmaxSP(S,Y)/P(Y) =argmaxSi=1kp(yi|si,si-1)p(si|si-1) Viterbi可以找到最正确解，其思想精华在于将全局最正确解的计算过程分解为阶段最正确解的计算表示 从D2前往Stage 1的最正确形状为C1 由于p(A1-D2)=0.60.5=0.3 而p(C1-D2)=0.40.8=0.32 虽然搜索还没有完全终

7、了，但是D2曾经找到了最正确前往节点Viterbi例如 argmaxXYZP(XYZ|rry)Viterbi计算Viterbi算法 三重循环 第一重：遍历每一个察看值 第二重：遍历当前察看值所对应的每一个形状 第三重：遍历可以到达当前察看值当前形状的上一时辰的每一个形状 计算 假设上一时辰为t，t时辰的的形状为i，t+1时辰的形状为j，t+1时辰的察看值为k，那么计算：j(t+1)=max1iNi(t)aijbijkj(t+1)=argmax1iNi(t)aijbijk t+1时辰形状j的前往指针指向t时辰的形状j(t+1) 输出 三重循环都终了后，在最后时辰找到值最大的形状，并从该形状开场，

8、根据前往指针查找各时辰的处于最正确途径上的形状，并反序输出。N-best计算 保管n个最正确结果，而不是1个 最优解：VCV；次优解：CCVN-Best Paths以分词为例MM模型例句：“结合成分子每条弧上的值是该弧所对应的词的Unigram概率的负对数，即-logp(w)结结 合合 成成 分分 子子N-Best PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre0 0 0 0valuepre0 0 0 0valuepre00 0 0valuepre000 0valuepre0000N-Best

9、PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre0 0 0 0valuepre00 0 0valuepre000 0valuepre0000N-Best PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.760 0 0 0valuepre00 0 0valuepre000 0valuepre0000N-Best PathsA

10、 sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre00 0 0valuepre000 0valuepre0000N-Best PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre21.510 0 0valuepre000 0valuepre0000N-Bes

11、t PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.6 2 0valuepre000 0valuepre0000N-Best PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0val

12、uepre18.2230.520 0valuepre0000N-Best PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre0000N-Best PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0v

13、aluepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre25.2331.2300N-Best PathsA sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre25.2329.1431.2333.94N-Best Paths

14、A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.0 1 0 0valuepre14.4221.5127.6 2 0valuepre18.2223.4330.0330.5 2valuepre25.2329.1431.2333.94结果 四条最正确途径为： 1. 结合/成/分子 2. 结合/成分/子 3. 结/合成/分子 4. 结合/成/分/子 时间复杂度 假设搜索图中共有k条边 要求获得N条最正确途径 那么时间复杂度为O(k*N2)剪枝Pruning在每一

15、个时辰，假设Trellis上的形状过多，怎样办？答案是剪枝：1、按的阈值剪枝， 太低的途径不再继续搜索2、按形状的数量剪枝，超越多少个形状就不再扩展了义务3：根据察看序列寻觅最正确参数模型问题 给定一个察看值序列，但是没有标注每个察看值所对应的形状无指点，在这种条件下如何估计隐马尔可夫模型中的参数，包括转移概率的分布和发射概率的分布 例如：给定一个语料库，语料库只是一个词的序列，没有词性标志，能否估计出词性标注的HMM模型？ 是EM算法的特例，象一个魔法(MAGIC)！找到一个可以最正确地解释察看值序列的模型Baum-Welch算法也称为Forward-Backward算法 1. 初始化PS，

16、PY 能够是随机给出的 2. 计算前向概率(Forward Probability) (s,i)=ss(s,i-1)p(s|s)p(yi|s,s) 从左到右搜索过程中的累积值 3. 计算后向概率(Backward Probability) (s,i)=ss (s,i+1)p(s|s)p(yi+1|s,s) 从右到左搜索过程中的累积值前向概率后向概率表示图Xt=siXt+1=sjt-1tt+1t+2i(t)j(t+1)aijbijk察看值为kBaum-Welch算法续 4. 计数(pseudo count ) c(y,s,s)= i=0k-1,y=yi+1(s,i)p(s|s)p(yi+1|s,

17、s)(s,i+1) c(s,s)=yYc(y,s,s) c(s)=sSc(s,s) 5. 重新估算 p(s|s)=c(s,s)/c(s), p(y|s,s)=c(y,s,s)/c(s,s) 6. 反复运转2-5，直至结果不再有较大变化词性标注词性(Part of Speech) 词的句法类别 名词、动词、描画词、副词、介词、助动词 分为开放词类(Open Class)和封锁词类(Closed Class) 也成为：语法类、句法类、POS标志、词类等POS举例N noun baby, toy V verb see, kiss ADJ adjective tall, grateful, alleg

18、ed ADV adverb quickly, frankly, . P preposition in, on, near DET determiner the, a, that WhPronwh-pronoun who, what, which, COORD coordinator and, or开放类替代性测试 两个词属于同一个词类，当且仅当它们相互交换时不改动句子的语法特征 The _ is angry.名词 The _ dog is angry.描画词 Fifi _ .不及物动词 Fifi _ the book.及物动词POS Tags 不存在规范的词性标注集 有的是用比较粗糙的标志集，

19、例如：N, V, A, Aux, . 有的运用更细致的分类：(例如： Penn Treebank) PRP: personal pronouns (you, me, she, he, them, him, her, ) PRP$: possessive pronouns (my, our, her, his, ) NN: singular common nouns (sky, door, theorem, ) NNS: plural common nouns (doors, theorems, women, ) NNP: singular proper names (Fifi, IBM, Ca

20、nada, ) NNPS: plural proper names (Americas, Carolinas, )Penn Treebank词性集PRPPRP$词性标注 词经常有多个词性，以back为例 The back door = JJ On my back = NN Win the voters back = RB Promised to back the bill = VB 词性标注问题就是针对确定词在一个特定实例中的词性POS歧义 (在Brown语料库中)无歧义的词(1 tag): 35,340个有歧义的词 (2-7 tags): 4,100个2 tags3,7603 tags264

21、4 tags615 tags126 tags27 tags1(Derose, 1988)词性标注的运用 文语转换 怎样朗诵lead 动词普通方式：li:d 过去式：led 是句法分析的根底 辅助词义消歧 等，动词等待 等，量词等级目前的性能 容易评价，只需计算标注正确的词性数量 目前准确率大约在97%左右 Baseline也可以到达90% Baseline算法: 对每一个词用它的最高频的词性进展标注 未登录词全部标为名词词性标注 P(T|W)=P(W|T)P(T)/P(W) argmaxTp(T|W)=argmaxTp(W|T)p(T) P(W|T)=i=1dp(wi|w1,wi-1,t1,t

22、d) p(wi|w1,wi-1,t1,td) p(wi|ti) P(T)=i=1dp(ti|t1,ti-1) p(ti|t1,ti-1)=p(ti|ti-n+1,ti-1)有指点的学习 训练时事先对语料库进展了人工的词性标注，因此在训练时看到了形状词性，属于VMM，在测试时，只能看到察看值词序列，因此属于HMM。 运用最大似然估计 p(wi|ti)=cwt(ti,wi)/ct(ti) p(ti|ti-n+1,ti-1) =ctn(ti-n+1,ti-1,ti)/ct(n-1)(ti-n+1,ti-1) 平滑 p(wi|ti)：加1平滑 p(ti|ti-n+1,ti-1)：线性差值用带标志的语料

23、进展训练 Pierre/NNP Vinken/NNP , , 61/CD years/NNS old/JJ ,/, will/MD join/VB the/DT board/NN as/IN a/DT nonexecutive/JJ director/NN Nov./NNP 29/CD ./. Mr./NNP Vinken/NNP is/VBZ chairman/NN of/IN Elsevier/NNP N.V./NNP ,/, the/DT Dutch/NNP publishing/VBG group/NN . . Rudolph/NNP Agnew/NNP ,/, 55/CD years

24、/NNS old/JJ and/CC former/JJ chairman/NN of/IN Consolidated/NNP Gold/NNP Fields/NNP PLC/NNP ,/, was/VBD named/VBN a/DT nonexecutive/JJ director/NN of/IN this/DT British/JJ industrial/JJ conglomerate/NN ./.c(JJ)=7 c(JJ, NN)=4, P(NN|JJ)=4/7无指点的学习 语料库只是词的序列，没有人工标注词性，是Plain Text。 完全无指点的学习是不能够的 至少要知道： 词性

25、集 每个词能够的词性据词典 运用Baum-Welch算法无指点学习的秘诀 语料库(只需两个句子) A lion ran to the rock D N V P D N Aux V The cat slept on the mat D N V P D N V R 我们可以学习到什么？ D, N, V的概率大于D, V, V，Cat应该标注为N V, P, D的概率大于V, Aux, D或V, R, D，因此to和on应标为P未登录词 思索一切词性 只思索开放类词性 Uniform平均分配概率 Unigram思索每个词性独立出现的概率 根据未登录词的前缀和后缀猜测其词性运转词性标注器人民收入和生活

26、水平进一步提高nnhncpvnvnandnv无论是对有指点的学习，还是对无指点的学习，在搜索阶段都一样：运用Viterbi算法！人民收入和生活水平进一步提高n=2.52n=2.52bn(bn(人民人民)=7.37)=7.37nnnhcpvnvnaadnv9.89人民收入和生活水平进一步提高bn(bn(收入收入)=6.98)=6.98ann=2.76ann=2.76nnnhcpvnvnaadnv9.8920.02人民收入和生活水平进一步提高bnh(bnh(和和)=20)=20an nh=20an nh=20nnnhcpvnvnaadnv9.8920.0260.02人民收入和生活水平进一步提高bc

27、(bc(和和)=1.72)=1.72an c=3.58an c=3.58nnnhcpvnvnaadnv9.8920.0260.0225.32人民收入和生活水平进一步提高bn(bn(生活生活)=5.75)=5.75anh n=20anh n=20nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.77Viterbi算法举例人民收入和生活水平进一步提高nnhncpvnvnandnv人民收入和生活水平进一步提高n=2.52n=2.52bn(bn(人民人民)=7.37)=7.37nnnhcpvnvnaadnv9.89人民收入和生活水平进一步提高bn(bn(收入

28、收入)=6.98)=6.98ann=2.76ann=2.76nnnhcpvnvnaadnv9.8920.02人民收入和生活水平进一步提高bnh(bnh(和和)=20)=20an nh=20an nh=20nnnhcpvnvnaadnv9.8920.0260.02人民收入和生活水平进一步提高bn(bn(生活生活)=5.75)=5.75anh n=20anh n=20nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.77人民收入和生活水平进一步提高bn(bn(生活生活)=5.75)=5.75ac n=1.84ac n=1.84nnnhcpvnvnaadn

29、v9.8920.0260.0225.3227.6631.2685.7732.91人民收入和生活水平进一步提高bn(bn(生活生活)=5.75)=5.75ap n=1.28ap n=1.28nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.9134.69人民收入和生活水平进一步提高bn(bn(生活生活)=5.75)=5.75av n=1.92av n=1.92nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.9134.6938.93人民收入和生活水平进一步提高nnnhcpvnvnaadnv

30、9.8920.0260.0225.3227.6631.2685.7732.9134.6938.93人民收入和生活水平进一步提高nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.91人民收入和生活水平进一步提高nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.9134.6人民收入和生活水平进一步提高nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.9134.643.1656.7452.6755.7160.7668.15人民收入和生活水平进一步提高nnnhcpvnvn

31、aadnv9.8920.0260.0225.3227.6631.2632.9134.643.1656.7452.6755.7160.7668.15人民/n 收入/n 和/c 生活/n 程度/n 进一步/d 提高/v收入和生活进一步提高npcvnvadnv收入和生活进一步提高n-16.98pcvnvadnvN-Best结果收入和生活进一步提高n-16.98p0014.62c0012.28v0018.22nvadnv收入和生活进一步提高n-16.98v0018.22n1019.870021.652025.89vadnvp0014.62c0012.28收入和生活进一步提高n-16.98v0018.22n1019.870021.652025.89v1020.860023.92027.61adnvp0014.62c