隱馬爾科夫模型和詞性標注大綱隱馬爾科夫模型隱馬爾科夫模型概述任務1：計算觀察序列的概率任務2：計算能夠解釋觀察序列的最大可能的狀態(tài)序列任務3：根據(jù)觀察序列尋找最佳參數(shù)模型詞性標注隱馬爾科夫模型概述馬爾科夫鏈狀態(tài)序列:X1,X2,X3,…常常是“時序”的從Xt-1到Xt的轉(zhuǎn)換只依賴于Xt-1X2X3X4X1轉(zhuǎn)移概率

TransitionProbabilities假設一個狀態(tài)Xt有N個可能的值Xt=s1,Xt=s2,…..,Xt=sN.轉(zhuǎn)移概率的數(shù)量為：N2P(Xt=si|Xt-1=sj),1≤i,j≤N轉(zhuǎn)移概率可以表示為N×N的矩陣或者有向圖MMBigramMM(一階MM)MMTrigramMM(二階MM)有限狀態(tài)自動機狀態(tài)：輸入輸出字母表中的符號弧：狀態(tài)的轉(zhuǎn)移仍然是VMM(VisibleMM)HMMHMM，從狀態(tài)產(chǎn)生輸出HMMHMM，不同狀態(tài)可能產(chǎn)生相同輸出HMMHMM，從弧產(chǎn)生輸出HMMHMM，輸出帶有概率HMMHMM，兩個狀態(tài)間有多條弧，具有不同的概率隱馬爾可夫模型

HiddenMarkovModel估算隱藏于表面事件背后的事件的概率觀察到一個人每天帶雨傘的情況，反過來推測天氣情況HiddenMarkovModelHMM是一個五元組(S,S0,Y,Ps,PY

).S:{s1…sT}是狀態(tài)集，S0是初始狀態(tài)Y:{y1…yV}是輸出字母表PS(sj|si):轉(zhuǎn)移(transition)概率的分布，也表示為aijPY(yk|si,sj):發(fā)射(emission)概率的分布，也表示為bijk給定一個HMM和一個輸出序列Y={y1,y2,…,yk)任務1：計算觀察序列的概率任務2：計算能夠解釋觀察序列的最大可能的狀態(tài)序列任務3：根據(jù)觀察序列尋找最佳參數(shù)模型任務1：計算觀察序列的概率計算觀察序列的概率前提：HMM模型的參數(shù)已經(jīng)訓練完畢想知道：根據(jù)該模型輸出某一個觀察序列的概率是多少應用：基于類的語言模型，將詞進行歸類，變計算詞與詞之間的轉(zhuǎn)移概率為類與類之間的轉(zhuǎn)移概率，由于類的數(shù)量比詞少得多，因此一定程度避免了數(shù)據(jù)稀疏問題TrellisorLattice(柵格)發(fā)射概率為1的情況Y=“toe”算法描述從初始狀態(tài)開始擴展在時間點t擴展得到的狀態(tài)必須能夠產(chǎn)生與觀察序列在t時刻相同的輸出比如在t=1時，觀察序列輸出‘t’，因此只有狀態(tài)A和C得到了擴展在t+1時刻，只能對在t時刻保留下來的狀態(tài)節(jié)點進行擴展比如在t=2時，只能對t=1時刻的A和C兩個狀態(tài)進行擴展每條路徑上的概率做累乘，不同路徑的概率做累加直到觀察序列全部考察完畢，算法結(jié)束發(fā)射概率不為1的情況就是在上述模型下“toe”出現(xiàn)的概率Trigram的情況以Bigram為狀態(tài)基于類的Trigram模型N-gramclassLMp(wi|wi-2,wi-1)p(wi|ci)p(ci|ci-2,ci-1)C:Consonant(輔音)，V:Vowel(元音)ClassTrigram的Trellis輸出Y=“toy”重疊(overlapping)

的ClassTrigram“r”有時是元音，有時是輔音，因此p(r|C)和p(r|V)都不為零重疊的類Trigram的Trellis討論我們既可以從左向右計算，也可以從右向左計算，甚至可以從中間向兩頭計算Trellis的計算對于Forward-Backward（也稱為Baum-Welch)參數(shù)估計很有用任務2：計算能夠解釋觀察序列的最大可能的狀態(tài)序列Viterbi算法用于搜索能夠生成觀察序列的最大概率的狀態(tài)序列Sbest=argmaxSP(S|Y) =argmaxSP(S,Y)/P(Y) =argmaxS∏i=1…kp(yi|si,si-1)p(si|si-1)Viterbi能夠找到最佳解，其思想精髓在于將全局最佳解的計算過程分解為階段最佳解的計算示意從D2返回Stage1的最佳狀態(tài)為C1因為而盡管搜索還沒有完全結(jié)束，但是D2已經(jīng)找到了最佳返回節(jié)點Viterbi示例argmaxXYZP(XYZ|rry)Viterbi計算Viterbi算法三重循環(huán)第一重：遍歷每一個觀察值第二重：遍歷當前觀察值所對應的每一個狀態(tài)第三重：遍歷能夠到達當前觀察值當前狀態(tài)的上一時刻的每一個狀態(tài)計算假設上一時刻為t，t時刻的的狀態(tài)為i，t+1時刻的狀態(tài)為j，t+1時刻的觀察值為k，則計算：j(t+1)=max1iNi(t)aijbijkj(t+1)=argmax1iNi(t)aijbijkt+1時刻狀態(tài)j的返回指針指向t時刻的狀態(tài)j(t+1)輸出三重循環(huán)都結(jié)束后，在最后時刻找到值最大的狀態(tài)，并從該狀態(tài)開始，根據(jù)返回指針查找各時刻的處于最佳路徑上的狀態(tài)，并反序輸出。N-best計算保留n個最佳結(jié)果，而不是1個最優(yōu)解：VCV；次優(yōu)解：CCVN-BestPaths以分詞為例（MM模型）例句：“結(jié)合成分子”每條弧上的值是該弧所對應的詞的Unigram概率的負對數(shù)，即-logp(w)

結(jié)合成分子N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre∞0∞

0∞

0∞

0valuepre∞0∞

0∞

0∞

0valuepre∞0∞0∞

0∞

0valuepre∞0∞0∞0∞

0valuepre∞0∞0∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre∞0∞

0∞

0∞

0valuepre∞0∞0∞

0∞

0valuepre∞0∞0∞0∞

0valuepre∞0∞0∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.760∞

0∞

0∞

0valuepre∞0∞0∞

0∞

0valuepre∞0∞0∞0∞

0valuepre∞0∞0∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.76020.01∞

0∞

0valuepre∞0∞0∞

0∞

0valuepre∞0∞0∞0∞

0valuepre∞0∞0∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.76020.01∞

0∞

0valuepre21.51∞0∞

0∞

0valuepre∞0∞0∞0∞

0valuepre∞0∞0∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.76020.01∞

0∞

0valuepre14.4221.5127.6

2∞

0valuepre∞0∞0∞0∞

0valuepre∞0∞0∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.76020.01∞

0∞

0valuepre14.4221.5127.62∞

0valuepre18.2230.52∞0∞

0valuepre∞0∞0∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.76020.01∞

0∞

0valuepre14.4221.5127.62∞

0valuepre18.2223.4330.0330.52valuepre∞0∞0∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.76020.01∞

0∞

0valuepre14.4221.5127.62∞

0valuepre18.2223.4330.0330.52valuepre25.2331.23∞0∞0N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.76020.01∞

0∞

0valuepre14.4221.5127.62∞

0valuepre18.2223.4330.0330.52valuepre25.2329.1431.2333.94N-BestPathsAsample

Thesentence“結(jié)合成分子“.

結(jié)合成分子valuepre00000000valuePre10.10∞

0∞

0∞

0valuepre7.76020.0

1∞

0∞

0valuepre14.4221.5127.6

2∞

0valuepre18.2223.4330.0330.5

2valuepre25.2329.1431.2333.94結(jié)果四條最佳路徑為：1.結(jié)合/成/分子2.結(jié)合/成分/子3.結(jié)/合成/分子4.結(jié)合/成/分/子時間復雜度假設搜索圖中共有k條邊要求獲得N條最佳路徑則時間復雜度為O(k*N2)剪枝Pruning在每一個時刻，如果Trellis上的狀態(tài)過多，怎么辦？答案是剪枝：1、按的閾值剪枝，太低的路徑不再繼續(xù)搜索2、按狀態(tài)的數(shù)量剪枝，超過多少個狀態(tài)就不再擴展了任務3：根據(jù)觀察序列尋找最佳參數(shù)模型問題給定一個觀察值序列，但是沒有標注每個觀察值所對應的狀態(tài)（無指導），在這種條件下如何估計隱馬爾可夫模型中的參數(shù)，包括轉(zhuǎn)移概率的分布和發(fā)射概率的分布例如：給定一個語料庫，語料庫只是一個詞的序列，沒有詞性標記，能否估計出詞性標注的HMM模型？是EM算法的特例，象一個魔法(MAGIC)！找到一個能夠最佳地解釋觀察值序列的模型Baum-Welch算法

也稱為Forward-Backward算法1.初始化PS，PY可能是隨機給出的2.計算前向概率(ForwardProbability)(s’,i)=∑ss’(s,i-1)×p(s’|s)×p(yi|s,s’)從左到右搜索過程中的累積值3.計算后向概率(BackwardProbability)(s’,i)=∑s’s(s,i+1)×p(s|s’)×p(yi+1|s’,s)從右到左搜索過程中的累積值前向概率后向概率示意圖Xt=siXt+1=sjt-1tt+1t+2ai(t)bj(t+1)aijbijk觀察值為kBaum-Welch算法（續(xù)）4.計數(shù)(pseudocount)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，直至結(jié)果不再有較大變化詞性標注詞性(PartofSpeech)詞的句法類別名詞、動詞、形容詞、副詞、介詞、助動詞分為開放詞類(OpenClass)和封閉詞類(ClosedClass)也成為：語法類、句法類、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

WhPron wh-pronoun who,what,which,…COORD coordinator and,or開放類替代性測試兩個詞屬于同一個詞類，當且僅當它們相互替換時不改變句子的語法特征The_____isangry.（名詞）The____dogisangry.（形容詞）Fifi____.（不及物動詞）Fifi____thebook.（及物動詞）POSTagsPennTreebank詞性集PRPPRP$詞性標注詞常常有多個詞性，以back為例Thebackdoor=JJOnmyback=NNWinthevotersback=RBPromisedtobackthebill=VB詞性標注問題就是針對確定詞在一個特定實例中的詞性POS歧義(在Brown語料庫中)無歧義的詞(1tag):35,340個有歧義的詞(2-7tags):4,100個2tags3,7603tags2644tags615tags126tags27tags1(Derose,1988)詞性標注的應用文語轉(zhuǎn)換怎樣朗讀”lead”動詞一般形式：[li:d]過去式：[led]是句法分析的基礎輔助詞義消歧等，動詞等待等，量詞等級目前的性能容易評價，只需計算標注正確的詞性數(shù)量目前準確率大約在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)有指導的學習訓練時事先對語料庫進行了人工的詞性標注，因此在訓練時看到了狀態(tài)（詞性），屬于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/NNPVinken/NNP,,61/CDyears/NNSold/JJ,/,will/MDjoin/VBthe/DTboard/NNas/INa/DTnonexecutive/JJdirector/NNNov./NNP29/CD./.Mr./NNPVinken/NNPis/VBZchairman/NNof/INElsevier/NNPN.V./NNP,/,the/DTDutch/NNPpublishing/VBGgroup/NN..Rudolph/NNPAgnew/NNP,/,55/CDyears/NNSold/JJand/CCformer/JJchairman/NNof/INConsolidated/NNPGold/NNPFields/NNPPLC/NNP,/,was/VBDnamed/VBNa/DTnonexecutive/JJdirector/NNof/INthis/DTBritish/JJindustrial/JJconglomerate/NN./.c(JJ)=7c(JJ,NN)=4,P(NN|JJ)=4/7無指導的學習語料庫只是詞的序列，沒有人工標注詞性，是PlainText。完全無指導的學習是不可能的至少要知道：詞性集每個詞可能的詞性（據(jù)詞典）使用Baum-Welch算法無指導學習的秘訣語料庫(只有兩個句子)AlionrantotherockDNVPDNAuxVThecatsleptonthematDNVPDNVR我們能夠?qū)W習到什么？D,N,V的概率大于D,V,V，Cat應該標注為NV,P,D的概率大于V,Aux,D或V,R,D，因此to和on應標為P未登錄詞考慮所有詞性只考慮開放類詞性Uniform（平均分配概率）Unigram（考慮每個詞性獨立出現(xiàn)的概率）根據(jù)未登錄詞的前綴和后綴猜測其詞性運行詞性標注器無論是對有指導的學習，還是對無指導的學習，在搜索階段都一樣：使用Viterbi算法！Πn=2.52 bn(人民nnnhcpvnvnaadnvbn(收入)=6.98 annnnnhcpvnvnaadnvbnh(和)=20 annh=20nnnhcpvnvnaadnvbc(和)=1.72 ancnnnhcpvnvnaadnvbn(生活)=5.75 anhn=20nnnhcpvnvnaadnvViterbi算法舉例Πn=2.52 bn(人民nnnhcpvnvnaadnvbn(收入)=6.98 annnnnhcpvnvnaadnvbnh(和)=20 annh=20nnnhcpvnvnaadnvbn(生活)=5.75 anhn=20nnnhcpvnvnaadnvbn(生活)=5.75 acnnnnhcpvnvnaadnvbn(生活)=5.75 apnnnnhcpvnvnaadnvbn(生活)=5.75 avnnnnhcpvnvnaadnvnnnhcpvnvnaadnvnnnhcpvnvnaadnvnnnhcpvnvnaadnvnnnhcpvnvnaadnvnnnhcpvnvnaadnv人民/n收入/n和/c生活/n水平/n進一步/d提高/vnpcvnvadnvn-16.98pcvnvadnvN-Best結(jié)果n-16.98p0014.62c0012.28v0018.22nvadnvn-16.98v0018.22n1019.870021.652025.89vadnvp0014.62c0012.28n-16.98v0018.22n1019.870021.652025.89v1020.860023.92027.61adnvp0014.62c0012.28n-16.98v0018.22n1019.870021.652025.89v1020.860023.92027.61a0032.420134.21036.