基于自然語(yǔ)言處理學(xué)習(xí)系統(tǒng)

1隱馬爾可夫模型

及在NLP中的應(yīng)用

劉杰

2內(nèi)容提要：1、基本概念及算法2、隱馬爾可夫模型的類型3、應(yīng)用領(lǐng)域4、在漢字處理方面的應(yīng)用5、一些推廣算法3

AndreiA.MarkovRussianstatistician1856–1922馬爾可夫鏈理論

4s1s2s3N=3t=0q0=s3有N個(gè)狀態(tài)，S1,S2…SN一階離散馬爾可夫模型

下一個(gè)時(shí)刻所處的狀態(tài)是隨機(jī)出現(xiàn)的在每個(gè)時(shí)刻t，系統(tǒng)只能處于唯一一個(gè)狀態(tài)qt存在一個(gè)離散的時(shí)間序列

t=0,t=1……當(dāng)前狀態(tài)假設(shè)當(dāng)前狀態(tài)qt只與前面相鄰的一個(gè)狀態(tài)qt-1有關(guān)，與其他狀態(tài)無(wú)關(guān)5s1s2s3一階離散馬爾可夫模型

11/21/21/32/36s1s2s3一階離散馬爾可夫模型

11/21/21/32/3aij---轉(zhuǎn)移概率并且滿足如下的標(biāo)準(zhǔn)隨機(jī)約束條件:7下雨多云晴天0.30.20.60.40.20.10.30.10.8下雨---狀態(tài)1多云---狀態(tài)2晴天---狀態(tài)3一階離散馬爾可夫模型

8一階離散馬爾可夫模型

狀態(tài)序列S1,…,ST的概率：

其中，πi=P(q1=Si)，為初始狀態(tài)的概率9一階離散馬爾可夫模型

10問(wèn)題：連續(xù)8天的天氣狀況為“晴天-晴天-晴天-下雨-下雨-晴天-多云-晴天”的概率是多少？一階離散馬爾可夫模型

晴天晴天晴天下雨下雨晴天多云晴天0.80.80.10.40.30.10.211晴天晴天一階離散馬爾可夫鏈晴天下雨下雨tt+1晴天-晴天-晴天-下雨-下雨-晴天-多云-晴天晴天多云晴天t-1馬爾可夫鏈12起源于60年代后期Baum和他的同事首先提出Baker(CMU)和Jelinek(IBM)在70年代早期實(shí)現(xiàn)在語(yǔ)音處理上的應(yīng)用隱馬爾可夫鏈（HMM）理論

13隱馬爾可夫模型是在馬爾可夫鏈的基礎(chǔ)之上發(fā)展起來(lái)的。由于實(shí)際問(wèn)題比馬爾可夫鏈模型所描述的更為復(fù)雜，觀察到的事件并不是與狀態(tài)一一對(duì)應(yīng)，而是通過(guò)一組概率分布相聯(lián)系，這樣的模型就稱為隱馬爾可夫模型（HMM）。它是一個(gè)雙重隨機(jī)過(guò)程，其中之一是馬爾可夫鏈，這是基本隨機(jī)過(guò)程，它描述狀態(tài)的轉(zhuǎn)移。另一個(gè)隨機(jī)過(guò)程描述狀態(tài)和觀察值之間的統(tǒng)計(jì)對(duì)應(yīng)關(guān)系。這樣，站在觀察者的角度，只能看到觀察值，不像馬爾可夫鏈模型中的觀察值和狀態(tài)一一對(duì)應(yīng)，因此不能直接看到狀態(tài)，而是通過(guò)一個(gè)隨機(jī)過(guò)程去感知狀態(tài)的存在及其特性。因而稱之為“隱”馬爾可夫模型。14估計(jì)隱藏于表面事件背后的事件的概率——比如：觀察到一個(gè)人每天帶雨傘的情況，反過(guò)來(lái)推測(cè)天氣情況1516一個(gè)著名的說(shuō)明HMM概念的例子：球和缸實(shí)驗(yàn)。如圖所示設(shè)有N個(gè)缸，每個(gè)缸中裝有很多彩色的球，球的顏色由一組概率分布描述。實(shí)驗(yàn)是這樣進(jìn)行的：根據(jù)某個(gè)初始概率分布，隨機(jī)地選擇N個(gè)缸中的一個(gè)，例如第i個(gè)缸，再根據(jù)這個(gè)缸中彩色球顏色的概率分布，隨機(jī)地選擇一個(gè)球，記下球的顏色，記為O1

，再把球放回缸中，又根據(jù)描述缸的轉(zhuǎn)移概率分布，隨機(jī)選擇下一個(gè)缸，例如第j個(gè)缸，再?gòu)母字须S機(jī)選一個(gè)球，記下球的顏色，記為O2

，這樣一直進(jìn)行下去?？梢缘玫揭粋€(gè)描述球的顏色的序列L,O1O2。。。，由于這是觀察到的事件，因而稱之為觀察值序列。但缸之間的轉(zhuǎn)移以及每次選取的缸被隱藏起來(lái)了，并不能直接觀察到。而且，從每個(gè)缸中選取球的顏色并不是與缸一一對(duì)應(yīng)，而是由該缸中彩球顏色概率分布隨機(jī)決定的。此外，每次選取哪個(gè)缸則由一組轉(zhuǎn)移概率所決定。17一個(gè)隱馬爾可夫模型可以由下列參數(shù)描述：1．N：模型中馬爾可夫鏈狀態(tài)數(shù)目。記N個(gè)狀態(tài)為S1、S2、S3……SN

，記t時(shí)刻馬爾可夫鏈所處的狀態(tài)為qt，顯然q

t

?(S1、S2、S3……SN)。(罐子的數(shù)量)

2．M：每個(gè)狀態(tài)對(duì)應(yīng)的可能觀察值（觀察符號(hào)）數(shù)目。記M個(gè)觀察值為V1

???VM

，記t時(shí)刻觀察到的觀察值為Ot，其中

Ot?(V1???VM)

。（不同顏色球的數(shù)目）。183．

：初始狀態(tài)概率分布，

=(1???N),其中：

i=p(q1=Si)，1

￡i￡N在球與罐子實(shí)驗(yàn)中指開(kāi)始時(shí)選取某個(gè)缸的概率。4．A：狀態(tài)轉(zhuǎn)移概率矩陣，

在球與罐子實(shí)驗(yàn)中指描述每次在當(dāng)前選取的罐子的條件下選取下一個(gè)缸的概率。

aij=p(qt+1=sj|qt=si)，1￡i

,

j￡N195.從狀態(tài)Sj

觀察到某一特定符號(hào)vk

的概率分布矩陣為：

其中，bj(k)為實(shí)驗(yàn)員從第j個(gè)袋子中取出第k種顏色的球的概率。

在球與罐子的實(shí)驗(yàn)中,bjk就是第j個(gè)缸中球的顏色k出現(xiàn)的概率。

20這樣，一個(gè)HMM就可以記為：

=(N,M,A,B,

)這里討論的HMM，由于其觀察值是M個(gè)離散可數(shù)的觀察值中的一個(gè)，故稱為離散隱馬爾可夫模型。此外，還有連續(xù)隱馬爾可夫模型和半連續(xù)隱馬爾可夫模型等。本文所討論的隱馬爾可夫模型都是指離散隱馬爾可夫模型21罐子小球紅球黑球黃球蘭球綠球罐子120112罐子201201罐子31001122對(duì)比兩個(gè)模型可見(jiàn)：馬爾可夫模型的觀測(cè)序列本身就是狀態(tài)序列；隱馬爾可夫模型的觀測(cè)序列不是狀態(tài)序列；23問(wèn)題一：給定模型參數(shù)和觀測(cè)序列，如何快速求出在該模型下觀測(cè)事件序列發(fā)生的概率？問(wèn)題二：給定模型參數(shù)和觀測(cè)序列，如何找出一個(gè)最佳狀態(tài)序列？使得該狀態(tài)序列“最好的解釋”觀察序列？問(wèn)題三：如何得到模型中的五個(gè)參數(shù)？

即對(duì)于給定的一個(gè)觀察值序列，調(diào)整參數(shù)λ，使得觀察值出現(xiàn)的概率p(σ|λ)最大。隱馬爾可夫模型的三個(gè)基本問(wèn)題24隱馬爾可夫模型的類型：1、離散隱馬爾可夫模型、連續(xù)隱馬爾可夫模型和半連續(xù)隱馬爾可夫模型等。2、一階、二階等高階隱馬爾可夫模型，假設(shè)t時(shí)刻的狀態(tài)只與t-1時(shí)刻的狀態(tài)有關(guān)稱為一階隱馬爾可夫模型，假設(shè)t時(shí)刻的狀態(tài)與t-1及t-2時(shí)刻的狀態(tài)有關(guān)稱為二階隱馬爾可夫模型。25隱馬爾可夫模型適用領(lǐng)域：隱馬爾可夫模型（HMM）是一種非常有用的隨機(jī)過(guò)程模型，在計(jì)算機(jī)科學(xué)中占有重要的地位。作為一種強(qiáng)有力的統(tǒng)計(jì)學(xué)模型，主要被應(yīng)用在一些連續(xù)性的或時(shí)間延續(xù)性的事件建模上。主要的應(yīng)用領(lǐng)域：語(yǔ)音識(shí)別系統(tǒng)。生物學(xué)中的DNA/protein序列的分析機(jī)器人的控制。文本文件的信息提取。圖像處理26估計(jì)問(wèn)題:前向算法和后向算法解碼問(wèn)題:Viterbi算法

學(xué)習(xí)問(wèn)題：Baum-Welch算法如何解決三個(gè)基本問(wèn)題

27估計(jì)問(wèn)題—前向算法28估計(jì)問(wèn)題—前向算法29估計(jì)問(wèn)題—前向算法30估計(jì)問(wèn)題—前向算法31估計(jì)問(wèn)題—前向算法前向變量：

表示模型下，在時(shí)刻t，觀測(cè)事件為Ot，狀態(tài)為i的概率。

s1s2sNsj時(shí)刻tt+1a1ja2jaNj32估計(jì)問(wèn)題—前向算法遞歸求解：初始：遞歸：中止：33StateT123123N2(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)34估計(jì)問(wèn)題—前向算法35363738394041Alpha=(((0.37800002*0.5)+(0.0425*0.375)+(0.010000001*0.125))*0.15)=0.0309281342Alpha=(((0.37800002*0.25)+(0.0425*0.125)+(0.010000001*0.675))*0.25)=0.02664062843Alpha=(((0.37800002*0.25)+(0.0425*0.375)+(0.010000001*0.375))*0.35)=0.03996562644Alpha=(((0.03092813*0.5)+(0.026640628*0.375)+(0.039965626*0.125))*0.05)=0.45Alpha=(((0.03092813*0.25)+(0.026640628*0.125)+(0.039965626*0.675))*0.25)=0.00950972746Alpha=(((0.03092813*0.25)+(0.026640628*0.375)+(0.039965626*0.375))*0.5)=0.016354694748計(jì)算觀察序列的概率前提：HMM模型的參數(shù)已經(jīng)訓(xùn)練完畢想知道：根據(jù)該模型輸出某一個(gè)觀察序列的概率是多少應(yīng)用：基于類的語(yǔ)言模型，將詞進(jìn)行歸類，變計(jì)算詞與詞之間的轉(zhuǎn)移概率為類與類之間的轉(zhuǎn)移概率，由于類的數(shù)量比詞少得多，因此一定程度避免了數(shù)據(jù)稀疏問(wèn)題49505152估計(jì)問(wèn)題—后向算法(不講）定義后向變量：

表示從終止時(shí)刻T到時(shí)刻t+1的觀測(cè)事件序列是并且時(shí)刻t的狀態(tài)是i的概率

s1s2sNsi時(shí)刻tt+1ai1ai2aiN53估計(jì)問(wèn)題—后向算法遞歸求解：初始：遞歸：54解碼問(wèn)題—Viterbi算法1、窮舉搜索方法

我們可以通過(guò)窮舉的方式列出所有可能隱含狀態(tài)序列，并算出每一種隱狀態(tài)序列組合對(duì)應(yīng)的觀察狀態(tài)序列的概率。概率最大的那個(gè)組合對(duì)應(yīng)的就是最可能的隱狀態(tài)序列組合。

55解碼問(wèn)題—Viterbi算法比如說(shuō)上圖中的trellis中，最有可能的隱狀態(tài)序列是使得概率：Pr(dry,damp,soggy|sunny,sunny,sunny),Pr(dry,damp,soggy|sunny,sunny,cloudy),Pr(dry,damp,soggy|sunny,sunny,rainy),....Pr(dry,damp,soggy|rainy,rainy,rainy)得到最大值的序列。同樣這種窮舉法的計(jì)算量太大了。為了解決這個(gè)問(wèn)題，我們可以利用和Forwardalgorithm一樣的原理—遞歸算法來(lái)減少計(jì)算量。

56解碼問(wèn)題—Viterbi算法用遞歸方式減少?gòu)?fù)雜度

:在給定的觀察序列和HMM模型下，我們用一種遞歸的方式找到最有可能的隱狀態(tài)序列。同樣我們給定部分概率，即在trellis中到達(dá)某一中間狀態(tài)的概率。然后介紹如何在初始時(shí)刻t=1和t>1的時(shí)刻分別求解這個(gè)部分概率。但要注意，這里的部分概率是到達(dá)某一中間狀態(tài)的概率最大的路徑而不是所有概率之和。

57對(duì)于trellis中的每個(gè)中間狀態(tài)和結(jié)束狀態(tài)，都存在一條到達(dá)它的最優(yōu)路徑。他可能是下圖這樣：

解碼問(wèn)題—Viterbi算法58解碼問(wèn)題—Viterbi算法找一個(gè)狀態(tài)序列，這個(gè)狀態(tài)序列在t時(shí)狀態(tài)為i，并且狀態(tài)i與前面t-1個(gè)狀態(tài)構(gòu)成的狀態(tài)序列的概率值最大

s1s2sNsj時(shí)刻tt+1a1ja2jaNj59現(xiàn)在我們可以得到到達(dá)每一個(gè)中間或者終點(diǎn)狀態(tài)的概率最大的路徑。但是我們需要采取一些方法來(lái)記錄這條路徑。這就需要在每個(gè)狀態(tài)記錄得到該狀態(tài)最優(yōu)路徑的前一狀態(tài)。記為：這樣argmax操作符就會(huì)選擇使得括號(hào)中式子最大的索引j。

60解碼問(wèn)題—Viterbi算法初始化：遞推計(jì)算：結(jié)束條件：61626364656667Delta=max((0.37800002*0.5),(0.0425*0.375),(0.010000001*0.125))*0.15=0.02835000368Delta=max((0.37800002*0.25),(0.0425*0.125),(0.010000001*0.675))*0.25=0.02362500169Delta=max((0.37800002*0.25),(0.0425*0.375),(0.010000001*0.375))*0.35=0.03307570Delta=max((0.028350003*0.5),(0.023625001*0.375),(0.033075*0.125))*0.05=7.087501E-471Delta=max((0.028350003*0.25),(0.023625001*0.125),(0.033075*0.675))*0.25=0.72Delta=max((0.028350003*0.25),(0.023625001*0.375),(0.033075*0.375))*0.5=0.7374123a12a21a22a11a23a32a13a31a33每個(gè)硬幣代表一個(gè)狀態(tài);每個(gè)狀態(tài)有兩個(gè)觀測(cè)值:正面H和反面T;每個(gè)狀態(tài)產(chǎn)生H的概率為P(H);每個(gè)狀態(tài)產(chǎn)生T的概率為1-P(H)隱馬爾可夫鏈—三個(gè)硬幣隱馬爾可夫模型

75三硬幣隱馬爾可夫模型

狀態(tài)1狀態(tài)2狀態(tài)30.50.750.250.50.250.75P(H)P(T)

觀測(cè)序列O=(HHHHTHTT)設(shè)初始狀態(tài)概率和狀態(tài)轉(zhuǎn)移概率都是1/3，忽略這些概率s1s2s3s1s2s3s1s2s3s1s2s3s1s2s3s1s2s3s1s2s3s1s2s30.50.75t0.250.75*0.50.7520.75*0.250.752*0.50.7530.752*0.250.753*0.50.7540.753*0.250.754*0.50.754*0.250.7550.755*0.50.7560.755*0.250.756*0.50.756*0.250.7570.757*0.50.757*0.250.75876三硬幣隱馬爾可夫模型

狀態(tài)1狀態(tài)2狀態(tài)30.50.750.250.50.250.75P(H)P(T)

觀測(cè)序列O=(HHHHTHTT)設(shè)初始狀態(tài)概率和狀態(tài)轉(zhuǎn)移概率都是1/3，忽略這些概率s1s2s3s1s2s3s1s2s3s1s2s3s1s2s3s1s2s3s1s2s3s1s2s30.50.75t0.250.75*0.50.7520.75*0.250.752*0.50.7530.752*0.250.753*0.50.7540.753*0.250.754*0.50.754*0.250.7550.755*0.50.7560.755*0.250.756*0.50.756*0.250.7570.757*0.50.757*0.250.75877摘錄一段原始語(yǔ)料如下：咱們中國(guó)這么大的一個(gè)多民族的國(guó)家如果不團(tuán)結(jié)，就不可能發(fā)展經(jīng)濟(jì)，人民生活水平也就不可能得到改善和提高。依據(jù)《規(guī)范2001》，加工后的語(yǔ)料如下所示：咱們/r中國(guó)/ns這么/r大/a的/u一個(gè)/m多/a民族/n的/u國(guó)家/n如果/c不/d團(tuán)結(jié)/a，/w就/d不/d可能/v發(fā)展/v經(jīng)濟(jì)/n，/w人民/n生活/n水平/n也/d就/d不/d可能/v得到/v改善/vn和/c提高/vn。/w詞語(yǔ)之間有了空格，斜杠之后的字母是該詞語(yǔ)的標(biāo)記。

78如果依據(jù)《規(guī)范2003》，這一段語(yǔ)料的加工結(jié)果則如下所示：咱們/rr中國(guó)/ns這么/rz大{da4}/a的{de5}/ud一個(gè)/mq多/a民族/n的{de5}/ud國(guó)家/n如果/c不/df團(tuán)結(jié)/a，/wd就/d不/df可能/vu發(fā)展/v經(jīng)濟(jì)/n，/wd人民/n生活/n水平/n也/d就/d不/df可能/vu得到/v改善/vn和{he2}/c提高/vn。/wj多音字加上了拼音，單音字可到單音字的語(yǔ)音表里找。79現(xiàn)在的加工（詞語(yǔ)切分和詞性標(biāo)注）還只是初步的。還可以進(jìn)行更深入的加工，如短語(yǔ)標(biāo)注，依存關(guān)系標(biāo)注，句法功能標(biāo)注，句型標(biāo)注，義項(xiàng)標(biāo)注等等。但這些深加工都必須在詞語(yǔ)切分和詞性標(biāo)注的基礎(chǔ)上進(jìn)行。

80用隱馬爾可夫模型進(jìn)行詞性標(biāo)注：

隱馬模型要解決的問(wèn)題，就是對(duì)于一個(gè)單詞串（句子），要給這個(gè)單詞串中的每一個(gè)單詞做一個(gè)標(biāo)記（例如單詞的詞性）。并假設(shè)從統(tǒng)計(jì)規(guī)律上說(shuō)，每一個(gè)詞性的概率分布只與上一個(gè)詞的詞性有關(guān)（也就是一個(gè)詞性的二元語(yǔ)法），而每一個(gè)單詞的概率分布只與其詞性相關(guān)。如果我們已經(jīng)有了一個(gè)已經(jīng)標(biāo)記了詞性的語(yǔ)料庫(kù)，那么我們就可以通過(guò)統(tǒng)計(jì)得到以下兩個(gè)矩陣（實(shí)際上還有一個(gè)初始詞性概率分布矩陣）：

81詞性到詞性的轉(zhuǎn)移概率矩陣：A={aij}，aij=p(Xt+1=qj|Xt=qi)詞性到單詞的輸出概率矩陣：B={bik}，bik=p(Ot=vk|Xt=qi)這里q1,…,qn是詞性集合，v1,…,vm是單詞的集合。

對(duì)于詞性標(biāo)注問(wèn)題而言，轉(zhuǎn)移概率矩陣中的一個(gè)元素aij含義的就是上一個(gè)詞的詞性為qi時(shí)，下一個(gè)詞的詞性為qj的概率；輸出概率矩陣中的一個(gè)元素bik的含義就是對(duì)于一個(gè)詞性qi來(lái)說(shuō)，對(duì)應(yīng)的詞語(yǔ)為vk的概率。在有了這兩個(gè)矩陣之后，對(duì)于任何一個(gè)給定的觀察值序列（單詞串），我們總可以通過(guò)Viterbi算法，很快得到一個(gè)可能性最大的狀態(tài)值序列（詞性串）。算法的復(fù)雜度與觀察值序列的長(zhǎng)度（句子中的單詞個(gè)數(shù)）成正比。

8283848586878889909192nh:c:p:a:d:93949596979899100101學(xué)習(xí)問(wèn)題—Baum-Welch算法（不講）表示t時(shí)狀態(tài)為i以及t+1時(shí)狀態(tài)為j的概率

表示t時(shí)狀態(tài)為i的概率

102學(xué)習(xí)問(wèn)題—Baum-Welch算法表示時(shí)刻1經(jīng)過(guò)狀態(tài)i次數(shù)；

表示在時(shí)刻T內(nèi)，狀態(tài)i轉(zhuǎn)移到狀態(tài)j的總次數(shù)，除以在時(shí)刻T內(nèi)，狀態(tài)i被經(jīng)過(guò)的總次數(shù)；

表示在時(shí)刻T內(nèi)，經(jīng)過(guò)狀態(tài)j，并且狀態(tài)j對(duì)應(yīng)的觀測(cè)事件為vk的總數(shù)除以