HMM模型和詞性標(biāo)注課件

1、HMM模型和詞性標(biāo)注徐志明哈工大語(yǔ)言技術(shù)中心目錄Markov模型HMM詞性標(biāo)注Markov模型描述：一個(gè)隨機(jī)過(guò)程上的隨機(jī)變量序列，X = X1, X2Xt隨機(jī)變量取值于有限集 S = s1,s2 sN。S稱為狀態(tài)空間。XXXX狀態(tài)序列Markov模型模型描述一個(gè)隨機(jī)過(guò)程，存在著一個(gè)隨機(jī)變量序列 X = X1, X2Xt隨機(jī)變量的取值于有限集 S = s1,s2 sN, S稱為狀態(tài)空間。兩個(gè)假設(shè)：有限視野： P(Xt+1| X1, X2Xt) = P(Xt+1|Xt) 時(shí)間不變性: 這種條件依賴，不隨時(shí)間的改變而改變。若隨機(jī)過(guò)程滿足上述假設(shè)，則是一個(gè)Markov 過(guò)程（鏈）。Markov模型模型

2、表示：三元組(S, p , A)S ：狀態(tài)的集合， S = s1,s2 sN。p：初始狀態(tài)的概率。 p =p1,p2pN; pi =P(X1= si)A ：狀態(tài)轉(zhuǎn)移概率矩陣。 A=aij; aij = P(Xt+1=sj|Xt=si)狀態(tài)圖相當(dāng)于一個(gè)有限狀態(tài)自動(dòng)機(jī)轉(zhuǎn)移弧上有概率Markov模型狀態(tài)空間 S=t,i,p,a,h,e初始概率 p =1.0,0,0,0,0狀態(tài)轉(zhuǎn)移概率矩陣Markov模型計(jì)算狀態(tài)序列的概率例子：The Markov Chain Ex 2例：Markov模型描述道瓊斯工業(yè)指數(shù)。5 個(gè)連續(xù)上漲交易日的概率Markov模型Bigram：一階Markov模型.HMMHMM，從

3、狀態(tài)產(chǎn)生輸出HMMHMM，不同狀態(tài)可能產(chǎn)生相同輸出HMMHMM，從弧中產(chǎn)生輸出HMMHMM，輸出帶有概率Hidden Markov Model（HMM）模型原理表層事件：可觀察序列；底層事件：隱藏的、不可見(jiàn)的；狀態(tài)序列。表層事件是由底層事件引起的。根據(jù)表層事件的可觀察序列，推測(cè)生成它的底層事件的序列。例子：觀察一個(gè)人每天帶雨傘情況，推測(cè)天氣情況。隱藏的狀態(tài)序列表層的可觀察序列HMM應(yīng)用例子例子：HMM假設(shè)一個(gè)隨機(jī)過(guò)程，有一個(gè)觀察序列 O=O1 , O2.OT ，該過(guò)程隱含著一個(gè)狀態(tài)序列 X=X1 , X2 . XT假設(shè)Markov假設(shè)假設(shè)1：有限歷史假設(shè)：P(Xi|X1 , X2Xi-1) =

4、 P(Xi|Xi-1)假設(shè)2：時(shí)間不動(dòng)性假設(shè)輸出條件獨(dú)立性假設(shè)輸出僅與當(dāng)前狀態(tài)有關(guān)P(O1 , O2.OT | X1 , X2 . XT) = t P(Ot|Xt) HMM模型圖示兩個(gè)隨機(jī)過(guò)程Markov鏈（, A）符號(hào)輸出過(guò)程（B）狀態(tài)序列觀察值序列X1, X2 . XTO1 , O2 . OTHMM的組成示意圖HMM模型圖示狀態(tài)空間觀察序列時(shí)間狀態(tài)序列 X1 X2 XT-1 XT-1 HMM模型圖示oTo1otot-1ot+1x1xt+1xTxtxt-1HMM模型表示模型表示五元組(S, V, p ,A,B)符號(hào)表S ：狀態(tài)集合，s1, , sN。V：輸出字母表，v1, , vM模型參數(shù)p

5、 ：初始狀態(tài)概率。 p = pi; A ：狀態(tài)轉(zhuǎn)移概率。 A = aij; B ：符號(hào)輸出概率。 B = bjk;序列狀態(tài)序列： X = X1 , X2XT輸出序列： O = O1 , O2 OTHMM過(guò)程HMM過(guò)程描述t = 1；初始狀態(tài)概率分布為。從狀態(tài)si開(kāi)始的概率為i；Forever do 從狀態(tài)si 向狀態(tài)sj轉(zhuǎn)移,并輸出觀察符號(hào)Ot = k 。 其中，狀態(tài)轉(zhuǎn)移概率為aij。符號(hào)輸出概率為 bjk t = t+1End HMM的三個(gè)基本問(wèn)題給定一個(gè)觀察序列O = O1, O2OT和模型=(A,B,)問(wèn)題1：如何有效計(jì)算觀察序列 O = O1, O2OT 的概率P(O|) ？評(píng)價(jià)問(wèn)題問(wèn)

6、題2：如何尋找最佳的狀態(tài)序列 X = X1, X2 XT ？解碼問(wèn)題問(wèn)題3：如何訓(xùn)練模型參數(shù)=(A,B,) ，使得P(O|)概率最大？模型參數(shù)學(xué)習(xí)、訓(xùn)練問(wèn)題HMM相關(guān)的算法評(píng)價(jià)問(wèn)題：向前算法定義向前變量采用動(dòng)態(tài)規(guī)劃算法解碼問(wèn)題：Viterbi算法采用動(dòng)態(tài)規(guī)劃算法模型參數(shù)訓(xùn)練、學(xué)習(xí)問(wèn)題：向前-向后算法EM算法問(wèn)題1：評(píng)價(jià)（Evaluation）給定一個(gè)模型= (A,B,) ，計(jì)算某一觀察序列 O = O1, O2OT 的概率P(O|)HMM例子假設(shè)：某一時(shí)刻只有一種疾病，且只依賴于上一時(shí)刻疾?。ㄓ邢逇v史假設(shè)）一種疾病只有一種癥狀，且只依賴于當(dāng)時(shí)的疾?。ㄝ敵鰲l件獨(dú)立性假設(shè)）癥狀(觀察值)： O =

7、 O1, O2 OT發(fā)燒，咳嗽，咽喉腫痛，流涕疾病(狀態(tài)值)： X = X1 , X2XT 感冒，肺炎，扁桃體炎轉(zhuǎn)移概率：A從一種疾病轉(zhuǎn)變到另一種疾病的概率輸出概率：B某一疾病呈現(xiàn)出某一癥狀的概率初始分布 ：初始疾病的概率問(wèn)題：給定：某人癥狀為：咳嗽咽喉痛流涕發(fā)燒。 O = O1, O2 OT計(jì)算：這個(gè)觀察序列的概率P(O)HMM例子方案1oTo1otot-1ot+1x1xt+1xTxtxt-1輸出條件獨(dú)立假設(shè)有限歷史假設(shè)P(A,B|C) = P(A|B,C)P(B|C)方案1oTo1otot-1ot+1x1xt+1xTxtxt-1算法時(shí)間復(fù)雜度太高，需要 O(T*NT)方案2-向前算法使用動(dòng)

8、態(tài)規(guī)劃方法實(shí)現(xiàn)更加高效的算法定義:向前變量t時(shí)刻，輸出序列O1, O2 Ot且狀態(tài)xt=si的概率。oTo1otot-1ot+1x1xt+1xTxtxt-1方案2-向前算法P(A,B|C) = P(A|B,C)P(B|C)輸出條件獨(dú)立假設(shè)&有限歷史假設(shè)向前算法：圖示方案2-向前算法1、初始化2、遞歸3、總合StateT123123N2(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(柵格)算法描述從初始狀態(tài)開(kāi)始擴(kuò)展在t時(shí)刻擴(kuò)展得到的狀態(tài)必須能夠產(chǎn)生觀察序列在t時(shí)刻的輸出

9、在t+1時(shí)刻，只能對(duì)在t時(shí)刻保留下來(lái)的狀態(tài)節(jié)點(diǎn)進(jìn)行擴(kuò)展每條路徑上的概率做累乘，不同路徑的概率做累加直到觀察序列全部考察完畢，算法結(jié)束向前算法例RRGB1.6.60.2.00.0.0.6.2.2.2.5.3.0.3.7RGB.5.6.4.4.1 =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向前算法的計(jì)算復(fù)雜性一般的計(jì)算方法的計(jì)算復(fù)雜性為O( T*NT )向前算法的計(jì)算復(fù)雜性為 O(N2T)方案3-向后算法與向前算法類似，計(jì)算順

10、序相反。定義向后變量t時(shí)刻，狀態(tài)xt = si情況下，模型輸出序列Ot+1, .,OT 的概率。P(A,B|C) = P(A|B,C)P(B|C)輸出條件獨(dú)立假設(shè)向后算法圖示方案3-向后算法后向算法1、初始化2、遞歸3、總合P(A,B|C) = P(A|B,C)P(B|C)向后算法的計(jì)算復(fù)雜性向后算法的計(jì)算復(fù)雜性，與向前算法相同。向后算法的計(jì)算復(fù)雜性為 O(N2T)問(wèn)題2: Decoding（解碼） 給定一個(gè)觀察序列O = O1, O2OT ，模型=(A,B,)解碼問(wèn)題：如何尋找最佳的狀態(tài)序列 X=X1, X2XT 如果要枚舉所有的狀態(tài)序列，時(shí)間復(fù)雜度是O(NT)解碼算法和向前算法相似，解碼算

11、法定義一個(gè)向前變量，意義：t時(shí)刻沿著某一條路徑到達(dá)狀態(tài)si，且輸出觀察值O1Ot的最大概率解碼算法和向前算法區(qū)別：不是求和，而是最大值。區(qū)別Viterbi 算法初始化：遞歸：結(jié)束：路徑回朔：累計(jì)變量，記憶節(jié)點(diǎn)概率返回指針，記憶返回路徑最優(yōu)路徑的概率最優(yōu)路徑的終點(diǎn)狀態(tài)從終點(diǎn)狀態(tài)，進(jìn)行回朔，生成最優(yōu)路經(jīng)123statesViterbi算法例.6.2.2.2.5.3.0.3.7RGB.5.6.4.4.1 =1 0 0TRRGB.5.2.0018.00648.01008.4.3.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

12、.6.18.6.2.048.0.4.2.1.0.4.0Viterbi算法思想Viterbi能夠找到最佳解，其思想精髓在于將全局最佳解的計(jì)算過(guò)程分解為階段最佳解的計(jì)算。Viterbi算法的時(shí)間復(fù)雜度：O(N2T)Viterbi算法思想三重循環(huán)第一重：遍歷每一個(gè)觀察值第二重：遍歷當(dāng)前觀察值所對(duì)應(yīng)的每一個(gè)狀態(tài)第三重：遍歷能夠到達(dá)當(dāng)前觀察值當(dāng)前狀態(tài)的上一時(shí)刻的每一個(gè)狀態(tài)計(jì)算假設(shè)上一時(shí)刻為t-1，t-1時(shí)刻的的狀態(tài)為i，t時(shí)刻的狀態(tài)為j，t時(shí)刻的觀察值為k，則計(jì)算：t時(shí)刻狀態(tài)j的返回指針指向t-1時(shí)刻的狀態(tài)輸出三重循環(huán)都結(jié)束后，在最后時(shí)刻找到值最大的終點(diǎn)狀態(tài)，并從該狀態(tài)開(kāi)始，根據(jù)返回指針查找各時(shí)刻的處于

13、最佳路徑上的狀態(tài)，反序輸出。問(wèn)題3：HMM模型參數(shù)訓(xùn)練根據(jù)：可觀察序列初始的模型優(yōu)化模型參數(shù)：尋找更好的模型 ，滿足優(yōu)化三種模型參數(shù)初始狀態(tài)概率分布：狀態(tài)轉(zhuǎn)移概率：輸出符號(hào)概率：HMM：有監(jiān)督學(xué)習(xí)有監(jiān)督學(xué)習(xí)方法：最大似然估計(jì)方法（MLE）在 上，標(biāo)注狀態(tài) 進(jìn)行統(tǒng)計(jì)。統(tǒng)計(jì)對(duì)象：符號(hào)輸出次數(shù)狀態(tài)轉(zhuǎn)移次數(shù)狀態(tài)出現(xiàn)次數(shù)用于計(jì)算 模型參數(shù)HMM：無(wú)監(jiān)督學(xué)習(xí)HMM的狀態(tài)序列通常是不可見(jiàn)的。換言之，由于缺少人工標(biāo)注的狀態(tài)數(shù)據(jù)，實(shí)際上很難用MLE直接估計(jì)模型參數(shù)。HMM的參數(shù)訓(xùn)練一般采用無(wú)監(jiān)督的參數(shù)學(xué)習(xí)方法。Baum-Welch算法（向前-向后算法）是一種EM (Expectation-Maximizatio

14、n)算法的特例EM算法：1、初始化模型參數(shù) 2、E 步驟：根據(jù) ，遍歷所有可能的狀態(tài)序列，計(jì)算期望值。3、M步驟：根據(jù)期望值，重估新的模型參數(shù)4、新模型 代替舊模型 5、如果 ，訓(xùn)練結(jié)束。E 步驟定義一組概率狀態(tài)轉(zhuǎn)移概率：定義：給定了整個(gè)觀察序列O，在t時(shí)刻從狀態(tài)si到狀態(tài)sj轉(zhuǎn)移的概率。數(shù)學(xué)推導(dǎo)P(A,B|C) = P(A|B,C)P(B|C)Baum-Welch算法圖示E 步驟定義一組概率狀態(tài)概率：定義：給定了整個(gè)觀察序列O，在t時(shí)刻，狀態(tài)xt=si的出現(xiàn)概率。數(shù)學(xué)推導(dǎo)P(A,B|C) = P(A|B,C)P(B|C)E 步驟期望值可觀察到M 步驟重估公式詞性標(biāo)注詞性(Part of Sp

15、eech)詞的句法類別詞性集合：名詞、動(dòng)詞、形容詞、副詞、介詞、助動(dòng)詞開(kāi)放詞類(Open Class)和封閉詞類(Closed Class)可稱為：語(yǔ)法類、句法類、POS標(biāo)記、詞類等詞的兼類現(xiàn)象例如打人 = 動(dòng)詞一打襯衫 = 量詞詞性標(biāo)注確定每個(gè)詞在特定的句子中詞性POS舉例Penn Treebank詞性集POS歧義(在Brown語(yǔ)料庫(kù)中)目前的性能容易評(píng)價(jià)，只需計(jì)算標(biāo)注正確的詞性數(shù)量目前準(zhǔn)確率大約在97%左右Baseline也可以達(dá)到90%Baseline算法:對(duì)每一個(gè)詞用它的最高頻的詞性進(jìn)行標(biāo)注未登錄詞全部標(biāo)為名詞詞性標(biāo)注的常用方法詞性標(biāo)注（Part-of-Speech tagging）回

16、顧：作用：句法分析的前期步驟難點(diǎn)：兼類詞處理基于規(guī)則的詞性標(biāo)注基于轉(zhuǎn)換的錯(cuò)誤驅(qū)動(dòng)的詞性標(biāo)注基于HMM的詞性標(biāo)注基于HMM的詞性標(biāo)注HMM模型五元組(S, V, p ,A,B)S： 狀態(tài)集合；詞性集合 S=t1,., tm.V ：輸出符號(hào)集；詞典 V=w1,.,wv.模型參數(shù)= (A,B,) i : P(x1 = ti) 詞性ti的初始概率aij : P(tj|ti)從詞性ti到詞性tj的轉(zhuǎn)移概率bjk: P(wk| tj)從詞性tj到詞wk的輸出概率序列 觀察序列：詞匯序列：W = w1,w2wn狀態(tài)序列：詞性序列： T = t1,t2tn基于HMM的詞性標(biāo)注詞性標(biāo)注屬于HMM的解碼問(wèn)題給定觀察序列和模型，求解最佳的狀態(tài)序列。具體任務(wù) 給定一個(gè)詞序列 W = w1,w2wn 求解最佳的詞性序列 T = t1,t2tn基于HMM的詞性標(biāo)注數(shù)學(xué)推導(dǎo)輸出條件獨(dú)立性假設(shè)有限歷史假設(shè)HMM：有指導(dǎo)的參數(shù)學(xué)習(xí)模型的參數(shù)未知假設(shè)有已經(jīng)標(biāo)注好的語(yǔ)料庫(kù):W = w1,w2wnT = t1,t2tn如何從語(yǔ)料庫(kù)中得到這樣的參數(shù)使用最大似然估計(jì)（MLE）用帶標(biāo)記的語(yǔ)料進(jìn)行訓(xùn)練HMM：無(wú)指導(dǎo)的參數(shù)學(xué)習(xí)語(yǔ)料庫(kù)只是詞的序列，沒(méi)有人工標(biāo)注詞性。完全無(wú)指導(dǎo)的學(xué)習(xí)是不可能的至少要知道：詞性集每個(gè)詞可能的