隱馬爾科夫模型和詞性標(biāo)注--張宇

1、隱馬爾科夫模型和詞性標(biāo)注大綱隱馬爾科夫模型隱馬爾科夫模型概述任務(wù)1：計(jì)算觀察序列的概率任務(wù)2：計(jì)算能夠解釋觀察序列的最大可能的狀態(tài)序列任務(wù)3：根據(jù)觀察序列尋找最佳參數(shù)模型詞性標(biāo)注隱馬爾科夫模型概述馬爾科夫鏈狀態(tài)序列: X1, X2, X3, 常常是“時(shí)序”的從Xt-1到Xt的轉(zhuǎn)換只依賴于Xt-1X2X3X4X1轉(zhuǎn)移概率Transition Probabilities假設(shè)一個(gè)狀態(tài)Xt有N個(gè)可能的值Xt=s1, Xt=s2,., Xt=sN.轉(zhuǎn)移概率的數(shù)量為：N2P(Xt=si|Xt-1=sj), 1 i, j N轉(zhuǎn)移概率可以表示為NN的矩陣或者有向圖MMBigram MM(一階MM)MMTrig

2、ram MM(二階MM)有限狀態(tài)自動(dòng)機(jī)狀態(tài)：輸入輸出字母表中的符號(hào)?。籂顟B(tài)的轉(zhuǎn)移仍然是VMM (Visible MM)HMMHMM，從狀態(tài)產(chǎn)生輸出HMMHMM，不同狀態(tài)可能產(chǎn)生相同輸出HMMHMM，從弧產(chǎn)生輸出HMMHMM，輸出帶有概率HMMHMM，兩個(gè)狀態(tài)間有多條弧，具有不同的概率隱馬爾可夫模型Hidden Markov Model估算隱藏于表面事件背后的事件的概率觀察到一個(gè)人每天帶雨傘的情況，反過(guò)來(lái)推測(cè)天氣情況Hidden Markov ModelHMM是一個(gè)五元組(S, S0,Y, Ps, PY ).S : s1sT 是狀態(tài)集，S0是初始狀態(tài)Y : y1yV 是輸出字母表PS(sj|si

3、):轉(zhuǎn)移(transition)概率的分布，也表示為aijPY(yk|si,sj): 發(fā)射(emission)概率的分布，也表示為bijk給定一個(gè)HMM和一個(gè)輸出序列Y=y1,y2,yk)任務(wù)1：計(jì)算觀察序列的概率任務(wù)2：計(jì)算能夠解釋觀察序列的最大可能的狀態(tài)序列任務(wù)3：根據(jù)觀察序列尋找最佳參數(shù)模型任務(wù)1：計(jì)算觀察序列的概率計(jì)算觀察序列的概率前提：HMM模型的參數(shù)已經(jīng)訓(xùn)練完畢想知道：根據(jù)該模型輸出某一個(gè)觀察序列的概率是多少應(yīng)用：基于類的語(yǔ)言模型，將詞進(jìn)行歸類，變計(jì)算詞與詞之間的轉(zhuǎn)移概率為類與類之間的轉(zhuǎn)移概率，由于類的數(shù)量比詞少得多，因此一定程度避免了數(shù)據(jù)稀疏問(wèn)題Trellis or Lattic

4、e(柵格)發(fā)射概率為1的情況Y=“toe”P(pán)(Y)=0.60.881+0.40.11=0.568算法描述從初始狀態(tài)開(kāi)始擴(kuò)展在時(shí)間點(diǎn)t擴(kuò)展得到的狀態(tài)必須能夠產(chǎn)生與觀察序列在t時(shí)刻相同的輸出比如在t=1時(shí)，觀察序列輸出t，因此只有狀態(tài)A和C得到了擴(kuò)展在t+1時(shí)刻，只能對(duì)在t時(shí)刻保留下來(lái)的狀態(tài)節(jié)點(diǎn)進(jìn)行擴(kuò)展比如在t=2時(shí)，只能對(duì)t=1時(shí)刻的A和C兩個(gè)狀態(tài)進(jìn)行擴(kuò)展每條路徑上的概率做累乘，不同路徑的概率做累加直到觀察序列全部考察完畢，算法結(jié)束發(fā)射概率不為1的情況0.236608就是在上述模型下“toe”出現(xiàn)的概率Trigram的情況以Bigram為狀態(tài)基于類的Trigram模型N-gram class L

5、Mp(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”有時(shí)是元音，有時(shí)是輔音，因此p(r|C)和p(r|V)都不為零重疊的類Trigram的Trellis討論我們既可以從左向右計(jì)算，也可以從右向左計(jì)算，甚至可以從中間向兩頭計(jì)算Trellis的計(jì)算對(duì)于Forward-Backward（也稱為Baum-Welch)參數(shù)估計(jì)很有用任務(wù)2：計(jì)算能夠解釋觀察序列的最大可能的狀態(tài)序列Viterbi算法用于

6、搜索能夠生成觀察序列的最大概率的狀態(tài)序列Sbest=argmaxSP(S|Y) =argmaxSP(S,Y)/P(Y) =argmaxSi=1kp(yi|si,si-1)p(si|si-1)Viterbi能夠找到最佳解，其思想精髓在于將全局最佳解的計(jì)算過(guò)程分解為階段最佳解的計(jì)算示意從D2返回Stage 1的最佳狀態(tài)為C1因?yàn)閜(A1-D2)=0.60.5=0.3而p(C1-D2)=0.40.8=0.32盡管搜索還沒(méi)有完全結(jié)束，但是D2已經(jīng)找到了最佳返回節(jié)點(diǎn)Viterbi示例argmaxXYZP(XYZ|rry)Viterbi計(jì)算Viterbi算法三重循環(huán)第一重：遍歷每一個(gè)觀察值第二重：遍歷當(dāng)前

7、觀察值所對(duì)應(yīng)的每一個(gè)狀態(tài)第三重：遍歷能夠到達(dá)當(dāng)前觀察值當(dāng)前狀態(tài)的上一時(shí)刻的每一個(gè)狀態(tài)計(jì)算假設(shè)上一時(shí)刻為t，t時(shí)刻的的狀態(tài)為i，t+1時(shí)刻的狀態(tài)為j，t+1時(shí)刻的觀察值為k，則計(jì)算：j(t+1)=max1iNi(t)aijbijkj(t+1)=argmax1iNi(t)aijbijkt+1時(shí)刻狀態(tài)j的返回指針指向t時(shí)刻的狀態(tài)j(t+1)輸出三重循環(huán)都結(jié)束后，在最后時(shí)刻找到值最大的狀態(tài)，并從該狀態(tài)開(kāi)始，根據(jù)返回指針查找各時(shí)刻的處于最佳路徑上的狀態(tài)，并反序輸出。N-best計(jì)算保留n個(gè)最佳結(jié)果，而不是1個(gè)最優(yōu)解：VCV；次優(yōu)解：CCVN-Best Paths以分詞為例（MM模型）例句：“結(jié)合成分子”

8、每條弧上的值是該弧所對(duì)應(yīng)的詞的Unigram概率的負(fù)對(duì)數(shù)，即-logp(w)結(jié) 合 成 分 子N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre0 0 0 0valuepre0 0 0 0valuepre00 0 0valuepre000 0valuepre0000N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre0 0 0 0valuepre00 0 0va

9、luepre000 0valuepre0000N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre7.760 0 0 0valuepre00 0 0valuepre000 0valuepre0000N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre00 0 0valuepre000

10、 0valuepre0000N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre21.510 0 0valuepre000 0valuepre0000N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.6 2 0v

11、aluepre000 0valuepre0000N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2230.520 0valuepre0000N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0va

12、luepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre0000N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre25.2331.2300N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子value

13、pre00000000valuePre10.10 0 0 0valuepre7.76020.01 0 0valuepre14.4221.5127.62 0valuepre18.2223.4330.0330.52valuepre25.2329.1431.2333.94N-Best PathsA sampleThe sentence “結(jié)合成分子 “.結(jié) 合 成 分 子valuepre00000000valuePre10.10 0 0 0valuepre7.76020.0 1 0 0valuepre14.4221.5127.6 2 0valuepre18.2223.4330.0330.5 2val

14、uepre25.2329.1431.2333.94結(jié)果四條最佳路徑為：1. 結(jié)合/成/分子2. 結(jié)合/成分/子3. 結(jié)/合成/分子4. 結(jié)合/成/分/子時(shí)間復(fù)雜度假設(shè)搜索圖中共有k條邊要求獲得N條最佳路徑則時(shí)間復(fù)雜度為O(k*N2)剪枝Pruning在每一個(gè)時(shí)刻，如果Trellis上的狀態(tài)過(guò)多，怎么辦？答案是剪枝：1、按的閾值剪枝， 太低的路徑不再繼續(xù)搜索2、按狀態(tài)的數(shù)量剪枝，超過(guò)多少個(gè)狀態(tài)就不再擴(kuò)展了任務(wù)3：根據(jù)觀察序列尋找最佳參數(shù)模型問(wèn)題給定一個(gè)觀察值序列，但是沒(méi)有標(biāo)注每個(gè)觀察值所對(duì)應(yīng)的狀態(tài)（無(wú)指導(dǎo)），在這種條件下如何估計(jì)隱馬爾可夫模型中的參數(shù)，包括轉(zhuǎn)移概率的分布和發(fā)射概率的分布例如：給定

15、一個(gè)語(yǔ)料庫(kù)，語(yǔ)料庫(kù)只是一個(gè)詞的序列，沒(méi)有詞性標(biāo)記，能否估計(jì)出詞性標(biāo)注的HMM模型？是EM算法的特例，象一個(gè)魔法(MAGIC)！找到一個(gè)能夠最佳地解釋觀察值序列的模型Baum-Welch算法也稱為Forward-Backward算法1. 初始化PS，PY可能是隨機(jī)給出的2. 計(jì)算前向概率(Forward Probability)(s,i)=ss(s,i-1)p(s|s)p(yi|s,s)從左到右搜索過(guò)程中的累積值3. 計(jì)算后向概率(Backward Probability)(s,i)=ss (s,i+1)p(s|s)p(yi+1|s,s)從右到左搜索過(guò)程中的累積值前向概率后向概率示意圖Xt=si

16、Xt+1=sjt-1tt+1t+2ai(t)bj(t+1)aijbijk觀察值為kBaum-Welch算法（續(xù)）4. 計(jì)數(shù)(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,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. 重復(fù)運(yùn)行2-5，直至結(jié)果不再有較大變化詞性標(biāo)注詞性(Part of Speech)詞的句法類別名詞、動(dòng)詞、形容詞、副詞、介詞、助動(dòng)詞分為開(kāi)放詞類(Open Class)和封閉詞類

17、(Closed Class)也成為：語(yǔ)法類、句法類、POS標(biāo)記、詞類等POS舉例N nounbaby, 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-pronounwho, what, which, COORD coordinatorand, or開(kāi)放類替代性測(cè)試兩個(gè)詞屬于同一個(gè)詞類，當(dāng)且僅當(dāng)它們相互替換時(shí)不改變句子的語(yǔ)法特征The _

18、 is angry.（名詞）The _ dog is angry.（形容詞）Fifi _ .（不及物動(dòng)詞）Fifi _ the book.（及物動(dòng)詞）POS Tags 不存在標(biāo)準(zhǔn)的詞性標(biāo)注集有的是用比較粗糙的標(biāo)記集，例如：N, V, A, Aux, .有的使用更細(xì)致的分類：(例如： 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,

19、theorem, )NNS: plural common nouns (doors, theorems, women, )NNP: singular proper names (Fifi, IBM, Canada, )NNPS: plural proper names (Americas, Carolinas, )Penn Treebank詞性集PRPPRP$詞性標(biāo)注詞常常有多個(gè)詞性，以back為例The back door = JJOn my back = NNWin the voters back = RBPromised to back the bill = VB詞性標(biāo)注問(wèn)題就是針對(duì)確定

20、詞在一個(gè)特定實(shí)例中的詞性POS歧義 (在Brown語(yǔ)料庫(kù)中)無(wú)歧義的詞(1 tag): 35,340個(gè)有歧義的詞 (2-7 tags): 4,100個(gè)2 tags3,7603 tags2644 tags615 tags126 tags27 tags1(Derose, 1988)詞性標(biāo)注的應(yīng)用文語(yǔ)轉(zhuǎn)換 怎樣朗讀”lead”動(dòng)詞一般形式：li:d過(guò)去式：led是句法分析的基礎(chǔ)輔助詞義消歧等，動(dòng)詞等待等，量詞等級(jí)目前的性能容易評(píng)價(jià)，只需計(jì)算標(biāo)注正確的詞性數(shù)量目前準(zhǔn)確率大約在97%左右Baseline也可以達(dá)到90%Baseline算法:對(duì)每一個(gè)詞用它的最高頻的詞性進(jìn)行標(biāo)注未登錄詞全部標(biāo)為名詞詞性標(biāo)注

21、P(T|W)=P(W|T)P(T)/P(W)argmaxTp(T|W)=argmaxTp(W|T)p(T)P(W|T)=i=1dp(wi|w1,wi-1,t1,td)p(wi|w1,wi-1,t1,td) p(wi|ti)P(T)=i=1dp(ti|t1,ti-1)p(ti|t1,ti-1)=p(ti|ti-n+1,ti-1)有指導(dǎo)的學(xué)習(xí)訓(xùn)練時(shí)事先對(duì)語(yǔ)料庫(kù)進(jìn)行了人工的詞性標(biāo)注，因此在訓(xùn)練時(shí)看到了狀態(tài)（詞性），屬于VMM，在測(cè)試時(shí)，只能看到觀察值（詞序列），因此屬于HMM。應(yīng)用最大似然估計(jì)p(wi|ti)=cwt(ti,wi)/ct(ti)p(ti|ti-n+1,ti-1)=ctn(ti-n+1

22、,ti-1,ti)/ct(n-1)(ti-n+1,ti-1)平滑p(wi|ti)：加1平滑p(ti|ti-n+1,ti-1)：線性差值用帶標(biāo)記的語(yǔ)料進(jìn)行訓(xùn)練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 Dut

23、ch/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(N

24、N|JJ)=4/7無(wú)指導(dǎo)的學(xué)習(xí)語(yǔ)料庫(kù)只是詞的序列，沒(méi)有人工標(biāo)注詞性，是Plain Text。完全無(wú)指導(dǎo)的學(xué)習(xí)是不可能的至少要知道：詞性集每個(gè)詞可能的詞性（據(jù)詞典）使用Baum-Welch算法無(wú)指導(dǎo)學(xué)習(xí)的秘訣語(yǔ)料庫(kù)(只有兩個(gè)句子)A lion ran to the rockD N V P D N Aux VThe cat slept on the mat D N V P D N V R我們能夠?qū)W習(xí)到什么？D, N, V的概率大于D, V, V，Cat應(yīng)該標(biāo)注為NV, P, D的概率大于V, Aux, D或V, R, D，因此to和on應(yīng)標(biāo)為P未登錄詞考慮所有詞性只考慮開(kāi)放類詞性Uniform（平

25、均分配概率）Unigram（考慮每個(gè)詞性獨(dú)立出現(xiàn)的概率）根據(jù)未登錄詞的前綴和后綴猜測(cè)其詞性運(yùn)行詞性標(biāo)注器無(wú)論是對(duì)有指導(dǎo)的學(xué)習(xí)，還是對(duì)無(wú)指導(dǎo)的學(xué)習(xí)，在搜索階段都一樣：使用Viterbi算法！n=2.52bn(人民)=7.37nnnhcpvnvnaadnv9.89bn(收入)=6.98ann=2.76nnnhcpvnvnaadnv9.8920.02bnh(和)=20an nh=20nnnhcpvnvnaadnv9.8920.0260.02bc(和)=1.72an c=3.58nnnhcpvnvnaadnv9.8920.0260.0225.32bn(生活)=5.75anh n=20nnnhcpvnv

26、naadnv9.8920.0260.0225.3227.6631.2685.77Viterbi算法舉例n=2.52bn(人民)=7.37nnnhcpvnvnaadnv9.89bn(收入)=6.98ann=2.76nnnhcpvnvnaadnv9.8920.02bnh(和)=20an nh=20nnnhcpvnvnaadnv9.8920.0260.02bn(生活)=5.75anh n=20nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.77bn(生活)=5.75ac n=1.84nnnhcpvnvnaadnv9.8920.0260.0225.3227

27、.6631.2685.7732.91bn(生活)=5.75ap n=1.28nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.9134.69bn(生活)=5.75av n=1.92nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.9134.6938.93nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2685.7732.9134.6938.93nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.91nnnhcp

28、vnvnaadnv9.8920.0260.0225.3227.6631.2632.9134.6nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.9134.643.1656.7452.6755.7160.7668.15nnnhcpvnvnaadnv9.8920.0260.0225.3227.6631.2632.9134.643.1656.7452.6755.7160.7668.15人民/n 收入/n 和/c 生活/n 水平/n 進(jì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