1、徐志明哈工大语言技术中心目录Markov模型HMM词性标注Markov模型描述：一个随机过程上的随机变量序列，X=X1,X2Xt随机变量取值于有限集 S=s1,s2 sN。S称为状态空间。XXXX状态序列Markov模型模型描述一个随机过程，存在着一个随机变量序列 X=X1,X2Xt随机变量的取值于有限集 S=s1,s2 sN,S称为状态空间。两个假设：有限视野：P(Xt+1|X1,X2Xt)=P(Xt+1|Xt)时间不变性:这种条件依赖，不随时间的改变而改变。若随机过程满足上述假设，则是一个Markov 过程（链）。Markov模型模型表示：三元组(S,p,A)S：状态的集合，S=s1,s2
2、 sN。p：初始状态的概率。p=p1,p2pN;pi=P(X1=si)A：状态转移概率矩阵。A=aij;aij=P(Xt+1=sj|Xt=si)状态图相当于一个有限状态自动机转移弧上有概率11niip11njijaMarkov模型状态空间 S=t,i,p,a,h,e初始概率 p=1.0,0,0,0,0状态转移概率矩阵 aij t i p a h e t 0.3 0.3 0.4 i 0.4 0.6 p 1.0 a 0.4 0.6 h 1.0 e 1.0 Markov模型计算状态序列的概率例子：1111211211212111)|()|()()|()|()(),(TtXXXtttttTTaXXPX
3、XPXPXXXXPXXPXPXXXPp18,06.0*3.0*0.1)|()|()(),(23121iXpXPtXiXPtXPpitPThe Markov Chain Ex 2例：Markov模型描述道琼斯工业指数。0.3 0.5,0.2,ip5 个连续上涨交易日的概率个连续上涨交易日的概率0.06480.60.5aaaas,s,s,s,sP up up up up upP411111111111111pMarkov模型Bigram：一阶Markov模型.)|()|()()(oeptoptptoepHMMHMM，从状态产生输出HMMHMM，不同状态可能产生相同输出HMMHMM，从弧中产生输出H
4、MMHMM，输出带有概率Hidden Markov Model（HMM）模型原理表层事件：可观察序列；底层事件：隐藏的、不可见的；状态序列。表层事件是由底层事件引起的。根据表层事件的可观察序列，推测生成它的底层事件的序列。例子：观察一个人每天带雨伞情况，推测天气情况。隐藏的状态序列表层的可观察序列HMM应用例子例子：序列标注序列标注 观察序列观察序列 隐藏的状态序列隐藏的状态序列 分词 字序列 词序列 词性标注 词序列 词性序列 句法分析 词序列 句子结构 HMM假设一个随机过程，有一个观察序列 O=O1,O2.OT，该过程隐含着一个状态序列 X=X1,X2.XT假设Markov假设假设1：有
5、限历史假设：P(Xi|X1,X2Xi-1)=P(Xi|Xi-1)假设2：时间不动性假设输出条件独立性假设输出仅与当前状态有关P(O1,O2.OT|X1,X2.XT)=t P(Ot|Xt)HMM模型图示两个随机过程Markov链（p,A）符号输出过程（B）状态序列状态序列观察值序列观察值序列X1,X2.XTO1,O2.OTHMM的组成示意图的组成示意图HMM模型图示状态空间观察序列时间状态序列 X1 X2 XT-1 XT-1 HMM模型图示oTo1otot-1ot+1x1xt+1xTxtxt-1HMM模型表示模型表示五元组(S,V,p,A,B)符号表S：状态集合，s1,sN。V：输出字母表，v1
6、,vM模型参数p：初始状态概率。p =pi;A：状态转移概率。A=aij;B：符号输出概率。B=bjk;序列状态序列：X=X1,X2XT输出序列：O=O1,O2 OTSiSji,VkSj,SXtVOtHMM过程HMM过程描述t=1；初始状态概率分布为p。从状态si开始的概率为pi；Forever do 从状态si 向状态sj转移,并输出观察符号Ot=k。其中，状态转移概率为aij。符号输出概率为 bjk t=t+1End HMM的三个基本问题给定一个观察序列O=O1,O2OT和模型=(A,B,p)问题1：如何有效计算观察序列 O=O1,O2OT 的概率P(O|)？评价问题问题2：如何寻找最佳的
7、状态序列 X=X1,X2 XT？解码问题问题3：如何训练模型参数=(A,B,p)，使得P(O|)概率最大？模型参数学习、训练问题HMM相关的算法评价问题：向前算法定义向前变量采用动态规划算法解码问题：Viterbi算法采用动态规划算法模型参数训练、学习问题：向前-向后算法EM算法问题1：评价（Evaluation）给定一个模型=(A,B,p)，计算某一观察序列 O=O1,O2OT 的概率P(O|)HMM例子假设：某一时刻只有一种疾病，且只依赖于上一时刻疾病（有限历史假设）一种疾病只有一种症状，且只依赖于当时的疾病（输出条件独立性假设）症状(观察值)：O=O1,O2 OT发烧，咳嗽，咽喉肿痛，流
8、涕疾病(状态值)：X=X1,X2XT 感冒，肺炎，扁桃体炎转移概率：A从一种疾病转变到另一种疾病的概率输出概率：B某一疾病呈现出某一症状的概率初始分布p：初始疾病的概率问题：给定：某人症状为：咳嗽咽喉痛流涕发烧。O=O1,O2 OT计算：这个观察序列的概率P(O)HMM例子TTxxxxxxxN2i1iiT2aaaxxPxPxxxPXP132211.)|()()|.()|(11p方案1TToxoxoxN1iiiTT2bbbxoPxxxOOOPXOP.)|(),.|.,(),|(2211211XXXPXOPXOPOP)|(),|()|,()|(oTo1otot-1ot+1x1xt+1xTxtxt-
9、1输出条件独立假设有限历史假设XXB,PBP)()(P(A,B|C)=P(A|B,C)P(B|C)方案1oTo1otot-1ot+1x1xt+1xTxtxt-1算法时间复杂度太高，需要 O(T*NT)111111111.)|(ttttToxxxTtxxoxxbabOPp方案2-向前算法使用动态规划方法实现更加高效的算法定义定义:向前变量向前变量t时刻，输出序列O1,O2 Ot且状态xt=si的概率。oTo1otot-1ot+1x1xt+1xTxtxt-1)|,.()(1itttsxOOPi方案2-向前算法XXB,PBP)()(P(A,B|C)=P(A|B,C)P(B|C)输出条件独立假设&有限
10、历史假设1,111112121112111212111121111211112111211)()|()|()|,(),|(),|()|,(),|,()|,()|,()|,()|,()(tojNiijtitjtjttNiittittjtjtitttNiittittjttNiittNijttittNijtittjtttbaisxsxPsxoPsxoooPsxooosxPsxsxooooPsxoooPsxooosxoPsxoooPsxosxoooPsxsxoooPsxoooPj向前算法：图示1,11)()(tojNiijttbaijNiTNiiTT21T21i|sxOO,OP|OO,OP|OP11)
11、(),()()(方案2-向前算法1、初始化2、递归3、总合njTtbaijtojijNitt1,11)()(1,11向前变量的定义XXB,PBP)()(1,1)|,()(oiii11bsxOPipStateT123123N2(1)2(2)2(3)2(N)3(1)3(2)3(3)3(N)1(1)1(2)1(N)1(3)T(N)T(3)T(2)T(1)向前算法图示Trellis or Lattice(栅格)1,11)()(tOjNiijttbaijNiTiOP1)()(1,1)(Oiibip算法描述从初始状态开始扩展在t时刻扩展得到的状态必须能够产生观察序列在t时刻的输出在t+1时刻，只能对在t时
12、刻保留下来的状态节点进行扩展每条路径上的概率做累乘，不同路径的概率做累加直到观察序列全部考察完毕，算法结束向前算法例RRGB1.6.60.2.00.0.0.6.2.2.2.5.3.0.3.7RGB.5.6.4.4.1p=1 0 0T.5.6.18.6.2.048.0.4.2.1.0.4.0.5.2.018.6.5.0504.01116.4.5.1.3.4.3.5.2.0018.6.3.01123.01537.4.3.1.7.4.7向前算法的计算复杂性一般的计算方法的计算复杂性为O(T*NT)向前算法的计算复杂性为 O(N2T)方案3-向后算法与向前算法类似，计算顺序相反。定义向后变量定义向后变
13、量t时刻，状态xt=si情况下，模型输出序列Ot+1,.,OT 的概率。11),|,()(21TtsxOOOPiitTttt)(),|(),|(),|(),|(),|(),|(),|(),|(),|,(),|()(11,1121111112111111111111jbasxsxPsxOOPsxOPsxsxPsxsxOOOPsxsxOPsxsxPsxsxOOPsxsxOOPsxOOPitNiOjijitjtjtTtNjjttitjtitjttTtNjitjttitjtNjitjtTtNjitjtTtitTtttXXB,PBP)()(P(A,B|C)=P(A|B,C)P(B|C)输出条件独立假设向
14、后算法图示NjtOjijtjbait11,)()(1方案3-向后算法后向算法后向算法1、初始化2、递归3、总合TtiT11)(niTTTtjbaitNiOjijtt1,.,2,1)()(11,1NioiiNiiTiNiiTibsxOOOPsxOPsxOOOPOP11,1112111121)(),|()|,()|,()|(1pXXB,PBP)()(P(A,B|C)=P(A|B,C)P(B|C)向后算法的计算复杂性向后算法的计算复杂性，与向前算法相同。向后算法的计算复杂性为 O(N2T)问题2:Decoding（解码）给定一个观察序列O=O1,O2OT，模型=(A,B,p)解码问题：如何寻找最佳的
15、状态序列 X=X1,X2XT 如果要枚举所有的状态序列，时间复杂度是O(NT)解码算法和向前算法相似，解码算法定义一个向前变量，意义：t时刻沿着某一条路径到达状态si，且输出观察值O1Ot的最大概率解码算法和向前算法区别：不是求和，而是最大值。)|,(maxarg),|(maxarg uOXPuOXPXXX)|,(max)(2121titXtOOOsXXXPi)(it区别S1 S2 S3 Sj :SN t t+1)(it )(1jt 1,11)()(:)(tOjNiijttbaij求和向前算法中的向前变量t,11)(max)(Ojijtnitbaij（求最大值）：解码算法中的向前变量Viter
16、bi 算法初始化：递归：结束：路径回朔：Ni1iNi1biOii,0)()(1,11pNjTtbaijNjTtbaijttOjijtNitOjijtNit1,2,)(maxarg)(1,2,)(max)(,11,11)(maxarg)(max1*1*ixiPTNiTTNi1,.,2,1),(*11*TTtxxttt累计变量，记忆节点概率返回指针，记忆返回路径最优路径的概率最优路径的终点状态从终点状态，进行回朔，生成最优路经123statesViterbi算法例.6.2.2.2.5.3.0.3.7RGB.5.6.4.4.1p=1 0 0TRRGB.5.2.0018.00648.01008.4.3
17、.1.7.4.7.6.3.61.60.2.00.0.0.5.2.018.6.5.036.00576.4.5.1.3.4.3.5.6.18.6.2.048.0.4.2.1.0.4.0Viterbi算法思想Viterbi能够找到最佳解，其思想精髓在于将全局最佳解的计算过程分解为阶段最佳解的计算。Viterbi算法的时间复杂度：O(N2T)Viterbi算法思想三重循环第一重：遍历每一个观察值第二重：遍历当前观察值所对应的每一个状态第三重：遍历能够到达当前观察值当前状态的上一时刻的每一个状态计算假设上一时刻为t-1，t-1时刻的的状态为i，t时刻的状态为j，t时刻的观察值为k，则计算：t时刻状态j的
18、返回指针指向t-1时刻的状态输出三重循环都结束后，在最后时刻找到值最大的终点状态，并从该状态开始，根据返回指针查找各时刻的处于最佳路径上的状态，反序输出。)(jtttOjijtNitOjijtNitbaijbaij,11,11)(maxarg)()(max)(问题3：HMM模型参数训练根据：可观察序列初始的模型优化模型参数：寻找更好的模型 ，满足优化三种模型参数初始状态概率分布：状态转移概率：输出符号概率：),(pBA),(pBA)|(maxarg OPTOOOO,21ipj iakj,bHMM：有监督学习有监督学习方法：最大似然估计方法（MLE）在 上，标注状态 进行统计。统计对象：符号输出
19、次数状态转移次数状态出现次数用于计算 模型参数),(pBA)(),()|(ijiijijscsscssPa)(),()|(iiitiksckscsxkOPb),(jissc)(isc),(kivsc)()()(1i1i1ixcsxcsxPpTxxxX,21TOOOO,21HMM：无监督学习HMM的状态序列通常是不可见的。换言之，由于缺少人工标注的状态数据，实际上很难用MLE直接估计模型参数。HMM的参数训练一般采用无监督的参数学习方法。Baum-Welch算法（向前-向后算法）是一种EM(Expectation-Maximization)算法的特例EM算法：1、初始化模型参数 2、E 步骤：根
20、据 ，遍历所有可能的状态序列，计算期望值。3、M步骤：根据期望值，重估新的模型参数4、新模型 代替旧模型 5、如果 ，训练结束。oldoldnewnewold预定的值)|()|(oldnewOPOPE 步骤定义一组概率状态转移概率：定义：给定了整个观察序列O，在t时刻从状态si到状态sj转移的概率。数学推导),|,(),(1OsxsxPjijtitt)()()(),|(),|()()(),|,()|(),()()()(jbaijsx,O,sxOPsx,OsxPisx|OPsx,OsxOPsx,OPsx,sx,O|OP|sx,sx,OP|sx,sx,O,OP|sx,sxO,PtjOijttitt
21、jt1tittjttjttittjttittjtitttjtittjtitttjtitt111111111111111111N1iN1jtjOijtN1iN1jjtitjbai|sx,sxO,POPt)()()()|(111N1iN1jtjOijttjOijtjtitjtittjbaijbaiOPsxsxOPOsxsxPjitt)()()()()|()|,(),|,(),(111111P(A,B|C)=P(A|B,C)P(B|C)XXB,PBP)()(Baum-Welch算法图示 N1iN1jtjOijtN1iN1jjtitjbai|sx,sxO,POPt)()()()|(111N1ittN1
22、iitii|sxO,POP)()()()|(E 步骤定义一组概率状态概率：定义：给定了整个观察序列O，在t时刻，状态xt=si的出现概率。数学推导)()(),|()()()(iiOsxOp|sx,OP|sx,O,OP|sxO,PtttittittitttitP(A,B|C)=P(A|B,C)P(B|C)XXB,PBP)()(N1jtittjiOsxPi),(),|()(N1ittttitittiiiiOPOsxPOsxPi)()()()()|()|,(),|()(E 步骤期望值可观察到11),(Ttjitssji转移的期望次数到状态从状态11)(Ttitsi出发的转移的期望次数从状态的概率初始
23、状态为i1si)(TtittksikO1 1的期望次数输出符号状态)(),(M 步骤重估公式1111,)(),(TttTttjiijia)(1iipTttTtttkiiikob11,)()(),(词性(Part of Speech)词的句法类别词性集合：名词、动词、形容词、副词、介词、助动词开放词类(Open Class)和封闭词类(Closed Class)可称为：语法类、句法类、POS标记、词类等词的兼类现象例如打人=动词一打衬衫=量词词性标注确定每个词在特定的句子中词性POS举例Penn Treebank词性集POS歧义(在Brown语料库中)目前的性能容易评价，只需计算标注正确的词性数
24、量目前准确率大约在97%左右Baseline也可以达到90%Baseline算法:对每一个词用它的最高频的词性进行标注未登录词全部标为名词词性标注的常用方法词性标注（Part-of-Speech tagging）回顾：作用：句法分析的前期步骤难点：兼类词处理基于规则的词性标注基于转换的错误驱动的词性标注基于HMM的词性标注基于HMM的词性标注HMM模型五元组(S,V,p,A,B)S：状态集合；词性集合 S=t1,.,tm.V：输出符号集；词典 V=w1,.,wv.模型参数=(A,B,p)pi:P(x1=ti)词性ti的初始概率aij:P(tj|ti)从词性ti到词性tj的转移概率bjk:P(w
25、k|tj)从词性tj到词wk的输出概率序列 观察序列：词汇序列：W=w1,w2wn状态序列：词性序列：T=t1,t2tn基于HMM的词性标注词性标注属于HMM的解码问题给定观察序列和模型，求解最佳的状态序列。具体任务 给定一个词序列 W=w1,w2wn 求解最佳的词性序列 T=t1,t2tn)|()|(maxarg)|,(maxarg)|()|,(maxarg),|(maxarg uT,WPuTPuWTPuWPuWTPuWTPTTTTTBest基于HMM的词性标注数学推导niiinntwPutt twwwPuT,WP12121)|(),|()|(输出条件独立性假设ni-iinttPutt tP
26、u|TP1121)|()|()(有限历史假设ni-iiiittPtwPuT,WPuTP11)|()|()|()|(ni-iiiiTBestttPtwPT11)|()|(maxargHMM：有指导的参数学习模型的参数未知假设有已经标注好的语料库:W=w1,w2wnT =t1,t2tn如何从语料库中得到这样的参数使用最大似然估计（MLE）)(),()|(jjijitcttcttP)(),()|(iiiiitcwtctwP用带标记的语料进行训练HMM：无指导的参数学习语料库只是词的序列，没有人工标注词性。完全无指导的学习是不可能的至少要知道：词性集每个词可能的词性（根据词典）使用Baum-Welch
27、算法词网格词网格：对于输入的词序列，根据语法词典，列出每个词可能的词性候选，构成词网格，即状态空间。（是完整的栅格状态空间的子空间）采用Viterbi算法搜索词网格，搜索最佳路径（词性序列、状态序列）。计算相关概率时，取-log对数形式，目的是将乘法运算变成加法运算。同时，将求最大概率的路径问题转换成求最小费用的路径问题将求最大概率的路径问题转换成求最小费用的路径问题。词网格Viterbi解码算法定义向前变量：计算第一列计算第t列选择最优路径路径回朔)|,(max)(ittTittTwwwPt2 21 10 01 11 1)()|()()(1iiiiittwPtTPt)|()|()(maxarg)()|()|()(max)(11jjijit-ttjtjjijit-ttjttwPttPtttwPttPttii1 11 1列列)(maxarg*iTTtTtxi列第)(*1 11 1tttxxViterbi搜索例子3.15小结 本课件参考了哈工大关毅教授和刘挺教授的课件
