隐马尔科夫模型和词性标注学习培训课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《隐马尔科夫模型和词性标注学习培训课件.ppt》由用户(林田)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 隐马尔科夫 模型 词性 标注 学习 培训 课件
- 资源描述:
-
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
展开阅读全文