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的矩阵或者有向图M
2、M 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,PY).S:s1sT
3、是状态集，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.236608就是在上述模型下“toe”出现
5、的概率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的计算对于Forward-Backward（也
6、称为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 尽管搜索还没有完全结束，但是D2已经找到了最佳返回节点Viterbi示例 a
7、rgmaxXYZP(XYZ|rry)Viterbi计算Viterbi算法 三重循环 第一重：遍历每一个观察值 第二重：遍历当前观察值所对应的每一个状态 第三重：遍历能够到达当前观察值当前状态的上一时刻的每一个状态 计算 假设上一时刻为t，t时刻的的状态为i，t+1时刻的状态为j，t+1时刻的观察值为k，则计算：j(t+1)=max1iNi(t)aijbijk j(t+1)=argmax1iNi(t)aijbijk t+1时刻状态j的返回指针指向t时刻的状态j(t+1)输出 三重循环都结束后，在最后时刻找到值最大的状态，并从该状态开始，根据返回指针查找各时刻的处于最佳路径上的状态，并反序输出。N
8、-best计算 保留n个最佳结果，而不是1个 最优解：VCV；次优解：CCVN-Best Paths 以分词为例（以分词为例（MM模型）模型）例句：例句：“结合成分子结合成分子”每条弧上的值是该弧所对应的词的每条弧上的值是该弧所对应的词的Unigram概率概率的负对数，即的负对数，即-logp(w)结结 合合 成成 分分 子子N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre0 0 0 0valuepre0 0 0 0valuepre00 0 0valuepre000 0valuepre
9、0000N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre0 0 0 0valuepre00 0 0valuepre000 0valuepre0000N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.760 0 0 0valuepre00 0 0valuepre000 0valuepre0000N-Be
10、st Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre00 0 0valuepre000 0valuepre0000N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre21.510 0 0valuepre000 0valuepre00
11、00N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.6 2 0valuepre000 0valuepre0000N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62
12、 0valuepre18.2230.520 0valuepre0000N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre0000N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0
13、 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre25.2331.2300N-Best Paths A sampleThe sentence“结合成分子“.结结 合合 成成 分分 子子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre25.2329.1431.2333.94N-Best Pat
14、hs 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在每一个时刻，如果Trel
15、lis上的状态过多，怎么办？答案是剪枝：1、按的阈值剪枝，太低的路径不再继续搜索2、按状态的数量剪枝，超过多少个状态就不再扩展了任务3：根据观察序列寻找最佳参数模型问题 给定一个观察值序列，但是没有标注每个观察值所对应的状态（无指导），在这种条件下如何估计隐马尔可夫模型中的参数，包括转移概率的分布和发射概率的分布 例如：给定一个语料库，语料库只是一个词的序列，没有词性标记，能否估计出词性标注的HMM模型？是EM算法的特例，象一个魔法(MAGIC)！找到一个能够最佳地解释观察值序列的模型Baum-Welch算法也称为Forward-Backward算法 1.初始化PS，PY 可能是随机给出的 2
16、.计算前向概率(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,s)(s,i+1)c(s,s)=yYc(y,s
17、,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,alleged ADV adverb quickly,frankly,.P pre
18、position 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 不存在标准的词性标注集 有的是用比较粗糙的标记集，例如：N,V,A,Aux,.有的使用更细致的分类：(例如：Penn Treebank)
19、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,Canada,)NNPS:plural proper names(Americas,Carolinas,)Penn Treebank词性集PRPPRP$词性标注 词常常有
20、多个词性，以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 tags2644 tags615 tags126 tags27 tags1(Derose,1988)词性标注的应用 文语转换 怎样朗读”lead”动词一般形式：li:d 过去式：led 是句法分析的基础 辅助词义消歧
21、 等，动词等待 等，量词等级目前的性能 容易评价，只需计算标注正确的词性数量 目前准确率大约在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,td)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)有指导的学习 训练时事先对语料库进行了人工的词
22、性标注，因此在训练时看到了状态（词性），属于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)：线性差值用带标记的语料进行训练 Pierre/NNP Vinken/NNP,61/CD years/NNS old/JJ,/,will/MD join/VB the/DT board/NN as/IN a/DT nonexecutive/J
23、J 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/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 nonexecu
24、tive/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。完全无指导的学习是不可能的 至少要知道：词性集 每个词可能的词性（据词典）使用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 我
25、们能够学习到什么？D,N,V的概率大于D,V,V，Cat应该标注为N V,P,D的概率大于V,Aux,D或V,R,D，因此to和on应标为P未登录词 考虑所有词性 只考虑开放类词性 Uniform（平均分配概率）Unigram（考虑每个词性独立出现的概率）根据未登录词的前缀和后缀猜测其词性运行词性标注器人民收入和生活水平进一步提高nnhncpvnvnandnv无论是对有指导的学习，还是对无指导的学习，在搜索阶段都一样：使用Viterbi算法！人民收入和生活水平进一步提高n n=2.52=2.52b bn n(人民人民)=7.37)=7.37nnnhcpvnvnaadnv9.89人民收入和生活水
26、平进一步提高b bn n(收入收入)=6.98)=6.98a annnn=2.76=2.76nnnhcpvnvnaadnv9.8920.02人民收入和生活水平进一步提高b bnhnh(和和)=20)=20a an nhn nh=20=20nnnhcpvnvnaadnv9.8920.0260.02人民收入和生活水平进一步提高b bc c(和和)=1.72)=1.72a an cn c=3.58=3.58nnnhcpvnvnaadnv9.8920.0260.0225.32人民收入和生活水平进一步提高b bn n(生活生活)=5.75)=5.75a anh nnh n=20=20nnnhcpvnvn
27、aadnv9.8920.0260.0225.3227.6631.2685.77Viterbi算法举例人民收入和生活水平进一步提高nnhncpvnvnandnv人民收入和生活水平进一步提高n n=2.52=2.52b bn n(人民人民)=7.37)=7.37nnnhcpvnvnaadnv9.89人民收入和生活水平进一步提高b bn n(收入收入)=6.98)=6.98a annnn=2.76=2.76nnnhcpvnvnaadnv9.8920.02人民收入和生活水平进一步提高b bnhnh(和和)=20)=20a an nhn nh=20=20nnnhcpvnvnaadnv9.8920.026
28、0.02人民收入和生活水平进一步提高b bn n(生活生活)=5.75)=5.75a anh nnh n=20=20nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.77人民收入和生活水平进一步提高b bn n(生活生活)=5.75)=5.75a ac nc n=1.84=1.84nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.91人民收入和生活水平进一步提高b bn n(生活生活)=5.75)=5.75a ap np n=1.28=1.28nnnhcpvnvnaadnv9.8920.0260.
29、0225.3227.6631.2685.7732.9134.69人民收入和生活水平进一步提高b bn n(生活生活)=5.75)=5.75a av nv n=1.92=1.92nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.9134.6938.93人民收入和生活水平进一步提高nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.9134.6938.93人民收入和生活水平进一步提高nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.91人民收入和生活
30、水平进一步提高nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.9134.6人民收入和生活水平进一步提高nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.9134.643.1656.7452.6755.7160.7668.15人民收入和生活水平进一步提高nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.9134.643.1656.7452.6755.7160.7668.15人民/n 收入/n 和/c 生活/n 水平/n 进一步/d 提高/v收入和生活进一步提高np
31、cvnvadnv收入和生活进一步提高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.62c0012.28收入和生活进一步提高n-16.98v0018.22n1019.870021.652025.89v1020.86
32、0023.92027.61a0032.420134.21036.16dnvp0014.62c0012.28收入和生活进一步提高n-16.98v0018.22n1019.870021.652025.89v1020.860023.92027.61a0032.420134.21036.16d0029.380131.161031.38nvp0014.62c0012.28收入和生活进一步提高n-16.98v0018.22n1019.870021.652025.89v1020.860023.92027.61a0032.420134.21036.16d0029.380131.161031.38n1044.5
33、90044.881146.37v1037.471139.251239.47p0014.62c0012.28收入和生活进一步提高n-16.98v0018.22n1019.870021.652025.89v1020.860023.92027.61a0032.420134.21036.16d0029.380131.161031.38n1044.590044.881146.37v1037.471139.251239.47p0014.62c0012.28收入和生活进一步提高n-16.98v0018.22n1019.870021.652025.89v1020.860023.92027.61a0032.42
34、0134.21036.16d0029.380131.161031.38n1044.590044.881146.37v1037.471139.251239.47p0014.62c0012.28收入和生活进一步提高n-16.98v0018.22n1019.870021.652025.89v1020.860023.92027.61a0032.420134.21036.16d0029.380131.161031.38n1044.590044.881146.37v1037.471139.251239.47p0014.62c0012.28N-Best Search结果1)收入/n 和/c 生活/n 进一步/d 提高/v37.472)收入/n 和/p 生活/n 进一步/d 提高/v39.253)收入/n 和/c 生活/v 进一步/d 提高/v39.47谢谢！
