马尔科夫模型.ppt
101页
隐马尔科夫模型和词性标注 大纲•隐马尔科夫模型–隐马尔科夫模型概述–任务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•转移概率可以表示为N×N的矩阵或者有向图 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, PY ).–S : {s1…sT }是状态集，S0是初始状态–Y : {y1…yV }是输出字母表–PS(sj|si):转移(transition)概率的分布，也表示为aij–PY(yk|si,sj): 发射(emission)概率的分布，也表示为bijk•给定一个HMM和一个输出序列Y={y1,y2,…,yk)–任务1：计算观察序列的概率–任务2：计算能够解释观察序列的最大可能的状态序列–任务3：根据观察序列寻找最佳参数模型 任务1：计算观察序列的概率 计算观察序列的概率•前提：HMM模型的参数已经训练完毕•想知道：根据该模型输出某一个观察序列的概率是多少•应用：基于类的语言模型，将词进行归类，变计算词与词之间的转移概率为类与类之间的转移概率，由于类的数量比词少得多，因此一定程度避免了数据稀疏问题 Trellis or Lattice(栅格) 发射概率为1的情况•Y=“toe”•P(Y)=0.6×0.88×1+0.4×0.1×1=0.568 算法描述•从初始状态开始扩展•在时间点t扩展得到的状态必须能够产生与观察序列在t时刻相同的输出–比如在t=1时，观察序列输出‘t’，因此只有状态A和C得到了扩展•在t+1时刻，只能对在t时刻保留下来的状态节点进行扩展–比如在t=2时，只能对t=1时刻的A和C两个状态进行扩展•每条路径上的概率做累乘，不同路径的概率做累加•直到观察序列全部考察完毕，算法结束 发射概率不为1的情况•0.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的计算对于Forward-Backward（也称为Baum-Welch)参数估计很有用 任务2：计算能够解释观察序列的最大可能的状态序列 Viterbi算法•用于搜索能够生成观察序列的最大概率的状态序列•Sbest=argmaxSP(S|Y) =argmaxSP(S,Y)/P(Y) =argmaxS∏i=1…kp(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示例•argmaxXYZP(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-best计算•保留n个最佳结果，而不是1个•最优解：VCV；次优解：CCV N-Best Paths•以分词为例（以分词为例（MM模型）模型）–例句：例句：“结合成分子结合成分子”–每条弧上的值是该弧所对应的词的每条弧上的值是该弧所对应的词的Unigram概率概率的负对数，即的负对数，即-logp(w)结结 合合 成成 分分 子子 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre∞0∞ 0∞ 0∞ 0valuepre∞0∞ 0∞ 0∞ 0valuepre∞0∞0∞ 0∞ 0valuepre∞0∞0∞0∞ 0valuepre∞0∞0∞0∞0 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10∞ 0∞ 0∞ 0valuepre∞0∞ 0∞ 0∞ 0valuepre∞0∞0∞ 0∞ 0valuepre∞0∞0∞0∞ 0valuepre∞0∞0∞0∞0 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10∞ 0∞ 0∞ 0valuepre7.760∞ 0∞ 0∞ 0valuepre∞0∞0∞ 0∞ 0valuepre∞0∞0∞0∞ 0valuepre∞0∞0∞0∞0 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10∞ 0∞ 0∞ 0valuepre7.76020.01∞ 0∞ 0valuepre∞0∞0∞ 0∞ 0valuepre∞0∞0∞0∞ 0valuepre∞0∞0∞0∞0 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10∞ 0∞ 0∞ 0valuepre7.76020.01∞ 0∞ 0valuepre21.51∞0∞ 0∞ 0valuepre∞0∞0∞0∞ 0valuepre∞0∞0∞0∞0 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10∞ 0∞ 0∞ 0valuepre7.76020.01∞ 0∞ 0valuepre14.4221.5127.6 2∞ 0valuepre∞0∞0∞0∞ 0valuepre∞0∞0∞0∞0 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10∞ 0∞ 0∞ 0valuepre7.76020.01∞ 0∞ 0valuepre14.4221.5127.62∞ 0valuepre18.2230.52∞0∞ 0valuepre∞0∞0∞0∞0 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10∞ 0∞ 0∞ 0valuepre7.76020.01∞ 0∞ 0valuepre14.4221.5127.62∞ 0valuepre18.2223.4330.0330.52valuepre∞0∞0∞0∞0 N-Best Paths–A sampleThe sentence “结合成分子 “.结结 合合 成成 分分 子子valuepre00000000valuePre10.10∞ 0∞ 0∞ 0valuepre7.76020.01∞ 0∞ 0valuepre14.4221.5127.62∞ 0valuepre18.2223.4330.0330.52valuepre25.2331.23∞0∞0 N-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.94 N-Best Paths–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在每一个时刻，如果Trellis上的状态过多，怎么办？答案是剪枝：1、按的阈值剪枝， 太低的路径不再继续搜索2、按状态的数量剪枝，超过多少个状态就不再扩展了 任务3：根据观察序列寻找最佳参数模型 问题•给定一个观察值序列，但是没有标注每个观察值所对应的状态（无指导），在这种条件下如何估计隐马尔可夫模型中的参数，包括转移概率的分布和发射概率的分布•例如：给定一个语料库，语料库只是一个词的序列，没有词性标记，能否估计出词性标注的HMM模型？•是EM算法的特例，象一个魔法(MAGIC)！找到一个能够最佳地解释观察值序列的模型 Baum-Welch算法也称为Forward-Backward算法•1. 初始化PS，PY–可能是随机给出的•2. 计算前向概率(Forward Probability)–(s’,i)=∑ss’(s,i-1)×p(s’|s)×p(yi|s,s’)–从左到右搜索过程中的累积值•3. 计算后向概率(Backward Probability)–(s’,i)=∑s’s (s,i+1)×p(s|s’)×p(yi+1|s’,s)–从右到左搜索过程中的累积值 前向概率后向概率示意图Xt=siXt+1=sjt-1tt+1t+2i(t)j(t+1)aijbijk观察值为k Baum-Welch算法（续）•4. 计数(pseudo count )–c(y,s,s’)=•∑i=0…k-1,y=yi+1(s,i)p(s’|s)p(yi+1|s,s’)(s’,i+1)–c(s,s’)=∑y∈Yc(y,s,s’)–c(s)=∑s∈Sc(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 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 •不存在标准的词性标注集–有的是用比较粗糙的标记集，例如：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, Canada, …)•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 tags2644 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=1…dp(wi|w1,…,wi-1,t1,…,td)–p(wi|w1,…,wi-1,t1,…,td) ≌p(wi|ti)•P(T)=∏i=1…dp(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)：线性差值 用带标记的语料进行训练•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/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。
•完全无指导的学习是不可能的–至少要知道：•词性集•每个词可能的词性（据词典）•使用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（考虑每个词性独立出现的概率）•根据未登录词的前缀和后缀猜测其词性 运行词性标注器无论是对有指导的学习，还是对无指导的学习，在搜索阶段都一样：使用Viterbi算法！ ΠΠ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 n nhnh=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 anhnh n n=20=20nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.77 Viterbi算法举例 ΠΠ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 n nhnh=20=20nnnhcpvnvnaadnv9.8920.0260.02 b bn n( (生活生活)=5.75)=5.75a anhnh n 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 p n n=1.28=1.28nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.9134.69 b bn n( (生活生活)=5.75)=5.75a av v n 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 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 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.62c0012.28 n-16.98v0018.22n1019.870021.652025.89v1020.860023.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.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.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.420134.21036.16d0029.380131.161031.38n1044.590044.881146.37v1037.471139.251239.47p0014.62c0012.28 N-Best Search结果1)收入/n 和/c 生活/n 进一步/d 提高/v37.472)收入/n 和/p 生活/n 进一步/d 提高/v39.25 3)收入/n 和/c 生活/v 进一步/d 提高/v39.47 谢谢！ 。
