资源描述:
《隐马尔科夫模型和词性标注 .ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、隐马尔科夫模型和词性标注大纲隐马尔科夫模型隐马尔科夫模型概述任务1:计算观察序列的概率任务2:计算能够解释观察序列的最大可能的状态序列任务3:根据观察序列寻找最佳参数模型词性标注隐马尔科夫模型概述马尔科夫链状态序列:X1,X2,X3,…常常是“时序”的从Xt-1到Xt的转换只依赖于Xt-1X2X3X4X1转移概率TransitionProbabilities假设一个状态Xt有N个可能的值Xt=s1,Xt=s2,…..,Xt=sN.转移概率的数量为:N2P(Xt=si
2、Xt-1=sj),1≤i,j≤N转移概率可以表示为N×N的矩阵或者有向图MMBigramMM(一阶M
3、M)MMTrigramMM(二阶MM)有限状态自动机状态:输入输出字母表中的符号弧:状态的转移仍然是VMM(VisibleMM)HMMHMM,从状态产生输出HMMHMM,不同状态可能产生相同输出HMMHMM,从弧产生输出HMMHMM,输出带有概率HMMHMM,两个状态间有多条弧,具有不同的概率隐马尔可夫模型HiddenMarkovModel估算隐藏于表面事件背后的事件的概率观察到一个人每天带雨伞的情况,反过来推测天气情况HiddenMarkovModelHMM是一个五元组(S,S0,Y,Ps,PY).S:{s1…sT}是状态集,S0是初始状态Y:{y1…yV}是输出
4、字母表PS(sj
5、si):转移(transition)概率的分布,也表示为aijPY(yk
6、si,sj):发射(emission)概率的分布,也表示为bijk给定一个HMM和一个输出序列Y={y1,y2,…,yk)任务1:计算观察序列的概率任务2:计算能够解释观察序列的最大可能的状态序列任务3:根据观察序列寻找最佳参数模型任务1:计算观察序列的概率计算观察序列的概率前提:HMM模型的参数已经训练完毕想知道:根据该模型输出某一个观察序列的概率是多少应用:基于类的语言模型,将词进行归类,变计算词与词之间的转移概率为类与类之间的转移概率,由于类的数量比词少得多,因此一定程
7、度避免了数据稀疏问题TrellisorLattice(栅格)发射概率为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”出现的概率Tr
8、igram的情况以Bigram为状态基于类的Trigram模型N-gramclassLMp(wi
9、wi-2,wi-1)p(wi
10、ci)p(ci
11、ci-2,ci-1)C:Consonant(辅音),V:Vowel(元音)ClassTrigram的Trellis输出Y=“toy”重叠(overlapping)的ClassTrigram“r”有时是元音,有时是辅音,因此p(r
12、C)和p(r
13、V)都不为零重叠的类Trigram的Trellis讨论我们既可以从左向右计算,也可以从右向左计算,甚至可以从中间向两头计算Trellis的计算对于Forward-Backward(也
14、称为Baum-Welch)参数估计很有用任务2:计算能够解释观察序列的最大可能的状态序列Viterbi算法用于搜索能够生成观察序列的最大概率的状态序列Sbest=argmaxSP(S
15、Y)=argmaxSP(S,Y)/P(Y)=argmaxS∏i=1…kp(yi
16、si,si-1)p(si
17、si-1)Viterbi能够找到最佳解,其思想精髓在于将全局最佳解的计算过程分解为阶段最佳解的计算示意从D2返回Stage1的最佳状态为C1因为p(A1-D2)=0.60.5=0.3而p(C1-D2)=0.40.8=0.32尽管搜索还没有完全结束,但是D2已经找到了最佳返回节点
18、Viterbi示例argmaxXYZP(XYZ
19、rry)Viterbi计算Viterbi算法三重循环第一重:遍历每一个观察值第二重:遍历当前观察值所对应的每一个状态第三重:遍历能够到达当前观察值当前状态的上一时刻的每一个状态计算假设上一时刻为t,t时刻的的状态为i,t+1时刻的状态为j,t+1时刻的观察值为k,则计算:j(t+1)=max1iNi(t)aijbijkj(t+1)=argmax1iNi(t)aijbijkt+1时刻状态j的返回指针指向t时刻的状态j(t+1)输出三重循环都结束后,在最后时刻找到值最大的状态,并从该状态开始,根据返