隱馬爾科夫模型

1、.,隱馬爾科夫模型（HMM）,.,Table of Contents,馬爾科夫模型 隱馬爾科夫模型 HMM基本問(wèn)題 3.1 HMM評(píng)估問(wèn)題 3.2 HMM解碼問(wèn)題 3.3 HMM學(xué)習(xí)問(wèn)題 HMM應(yīng)用背景 4.1 自動(dòng)文本分類(lèi) 4.2 漢語(yǔ)詞性標(biāo)注 4.3 漢語(yǔ)自動(dòng)分詞 4.4 文本信息抽取 4.5 其他應(yīng)用領(lǐng)域,.,1.馬爾科夫模型,馬爾科夫(Markov)模型是由俄羅斯數(shù)學(xué)家Andrei AMarkov于20世紀(jì)初提出的一個(gè)統(tǒng)計(jì)模型。,有限狀態(tài)的離散時(shí)間Markov鏈?zhǔn)且粋€(gè)長(zhǎng)度為T(mén)的隨機(jī)變量序列 ， 的取值范圍是有限狀態(tài)集 。,假定它滿足以下兩個(gè)條件：（1）任一時(shí)刻的隨機(jī)變量只依賴于前一時(shí)刻

2、的隨機(jī)變量：,（2）時(shí)間無(wú)關(guān)性（馬爾科夫性）：,則顯然有：,.,以上隨機(jī)過(guò)程可以稱為可觀測(cè)Markov模型，因?yàn)榇诉^(guò)程的輸出在每一個(gè)時(shí)間點(diǎn)是一個(gè)狀態(tài)，并且每一個(gè)狀態(tài)對(duì)應(yīng)一個(gè)可觀測(cè)事件。,上述模型稱為一階Markov模型。,如把條件（1）適當(dāng)放松，任一時(shí)刻的隨機(jī)變量只依賴于前兩（三，k）個(gè)時(shí)刻的隨機(jī)變量，則此模型為兩（三，k）階Markov模型。,Markov模型,.,2.隱馬爾科夫模型,一個(gè)HMM是不確定的、隨機(jī)的有限狀態(tài)自動(dòng)機(jī)，由不可觀測(cè)的狀態(tài)轉(zhuǎn)移過(guò)程(一個(gè)Markov鏈)和可觀測(cè)的觀察生成過(guò)程組成。按觀測(cè)值是離散還是連續(xù)的，HMM可分為離散型和連續(xù)型。我們這里主要介紹離散HMM。,一階離散

3、HMM是一個(gè)五元組： ，可以簡(jiǎn)寫(xiě)為 ，其中N是Markov鏈狀態(tài)數(shù);M是狀態(tài)可能生成的觀察值數(shù); 表示初始狀態(tài)概率向量，其中,A為狀態(tài)轉(zhuǎn)換概率分布矩陣，表示i狀態(tài)向j狀態(tài)轉(zhuǎn)換的概率： ，其中:,B為觀察值概率分布矩陣，表示在j狀態(tài)輸出觀察值k的概率： ，其中:,隱馬爾可夫模型（HMM）是一種在Markov鏈的基礎(chǔ)上發(fā)展起來(lái)的統(tǒng)計(jì)信號(hào)模型，能夠利用收集的訓(xùn)練樣本進(jìn)行自適應(yīng)學(xué)習(xí)。,.,隱馬爾科夫模型,.,HMM拓?fù)浣Y(jié)構(gòu),左右型的HMM,全連通的HMM,含并行結(jié)構(gòu)的HMM,含間隔跳轉(zhuǎn)的HMM,.,3.HHM基本問(wèn)題,HMM理論有3個(gè)基本問(wèn)題：,（2）解碼問(wèn)題 給定一個(gè)HHM的模型 和觀測(cè)序列 ，如何

4、選擇對(duì)應(yīng)最佳的狀態(tài)序列，使它在某種狀態(tài)下最優(yōu)（出現(xiàn)的概率最大），以較好地解釋觀測(cè)值,（1）評(píng)估問(wèn)題 給定一個(gè)HHM的模型 和觀測(cè)序列 ，如何高效的計(jì)算此模型產(chǎn)生的觀測(cè)序列的概率,（3）學(xué)習(xí)問(wèn)題（訓(xùn)練問(wèn)題） 給定觀測(cè)序列 ，如何調(diào)整模型參數(shù) ，以使得觀察序列出現(xiàn)的概率 最大化,.,3.1評(píng)估問(wèn)題,解決HHM評(píng)估問(wèn)題的典型算法有窮舉搜索直接計(jì)算法、前向算法和后向算法：,一、窮舉搜索直接計(jì)算,1、算法思想 列舉長(zhǎng)度為T(mén)的所有可能的狀態(tài)序列 ，分別求解各個(gè)狀態(tài)序列與觀測(cè)序列的聯(lián)合概率 ，最后求和得到,2、算法過(guò)程,（1）狀態(tài)序列 出現(xiàn)的概率為：,（2）對(duì)于其中一種狀態(tài)序列，觀測(cè)序列的概率為： 依據(jù)貝葉

5、斯公式：,.,（3）求和：,3、算法評(píng)價(jià),由于每一時(shí)刻點(diǎn)所到達(dá)的狀態(tài)有N種可能，所以總的不同的狀態(tài)序列有 種。其中每一個(gè)狀態(tài)序列需要2T-1次乘法運(yùn)算。所以總的運(yùn)算量為 次乘法運(yùn)算（此外還需要 次加法運(yùn)算）。,窮舉算法的時(shí)間復(fù)雜度為 ，在求解 的過(guò)程中存在大量的重復(fù)計(jì)算，不適用于大的模型和較長(zhǎng)的序列。,.,二、前向算法,1、算法思想,到達(dá)某網(wǎng)格節(jié)點(diǎn)的概率可以用前一時(shí)刻N(yùn)個(gè)節(jié)點(diǎn)的概率表示出來(lái)。 前向算法通過(guò)已經(jīng)保存了的子路徑來(lái)計(jì)算新路徑的概率。,HHM網(wǎng)狀結(jié)構(gòu),.,(3)終止，在時(shí)刻T所有隱狀態(tài)（對(duì)應(yīng)觀測(cè)值 ）的概率求和:,(2)遞歸，計(jì)算t+1時(shí)刻處于各隱狀態(tài)（對(duì)應(yīng)觀測(cè)值為 ）的概率:,2、算

6、法過(guò)程,定義到時(shí)刻t，部分觀測(cè)序列為 ，狀態(tài) 的前向概率為：,(1)初始化,計(jì)算t=1時(shí)處于各隱狀態(tài)（對(duì)應(yīng)觀測(cè)值為 ）的概率:,.,t時(shí)刻前向概率的遞歸關(guān)系,3、算法評(píng)價(jià),由以上算法過(guò)程可知，計(jì)算 總共需要 次乘法運(yùn)算和 次加法運(yùn)算。,前向算法的復(fù)雜度為 ，相比于窮舉法計(jì)算，復(fù)雜度降低了幾個(gè)數(shù)量級(jí)，減少了重復(fù)計(jì)算。,.,2后向算法,(1)初始化,最終時(shí)刻的所有狀態(tài)的概率規(guī)定為：,定義從時(shí)刻t+1到時(shí)刻T，部分觀測(cè)序列為 ，狀態(tài) 的后向概率為:,1、算法思想 和前向算法基本一致，唯一的區(qū)別是選擇的局部狀態(tài)不同。,2、算法過(guò)程,(2)遞歸，計(jì)算t時(shí)刻處于各隱狀態(tài)（對(duì)應(yīng)觀測(cè)值為 ）的概率:,.,(3

7、)終止：,3、算法評(píng)價(jià),t時(shí)刻后向概率的遞歸關(guān)系,由以上算法過(guò)程可知，計(jì)算 總共需要 次 乘法運(yùn)算和 次加法運(yùn)算。,后向算法的復(fù)雜度與前向算法相等，都是 。,.,3.2解碼問(wèn)題,1、算法思想,解答解碼問(wèn)題，即尋求對(duì)于給定觀測(cè)序列的最優(yōu)狀態(tài)序列。有好幾種標(biāo)準(zhǔn)可用于定義最優(yōu)狀態(tài)序列。比如，其中一個(gè)可能的優(yōu)化標(biāo)準(zhǔn)是分別選擇每個(gè)時(shí)刻各自最可能的狀態(tài)。 但是每個(gè)時(shí)刻最可能的狀態(tài)的疊加不一定能得到最可能的狀態(tài)序列。可能這種得到的最優(yōu)序列根本是“不合法”的。這種算法僅簡(jiǎn)單地考慮了每一個(gè)時(shí)刻點(diǎn)各自最可能的狀態(tài)，而沒(méi)有考慮到狀態(tài)序列發(fā)生的概率。,定義優(yōu)化標(biāo)準(zhǔn)為：尋求單一最佳狀態(tài)序列，以最大化 ，運(yùn)用貝葉斯原理，

8、也即最大化,對(duì)于上述問(wèn)題的一個(gè)可行的解決方案就是修改優(yōu)化標(biāo)準(zhǔn)。于是提出了解決HMM解碼問(wèn)題的一個(gè)典型算法 Viterbi算法。,.,(3)終結(jié)：,(4)狀態(tài)序列路徑回溯：,(1)初始化：,(2)遞歸：,2、算法過(guò)程,定義 為時(shí)刻t系統(tǒng)沿單一路徑的最高得分，它解釋了前t個(gè)觀測(cè)符號(hào)，并結(jié)束于 ：,同時(shí)，定義一個(gè)參數(shù)數(shù)組 ，記錄目標(biāo)狀態(tài)序列的每個(gè)時(shí)刻t和狀態(tài),.,在實(shí)現(xiàn)上，Viterbi算法和前向算法十分相似。最主要的區(qū)別在于在Viterbi算法中遞歸時(shí)對(duì)以前的狀態(tài)取最大值，而在前向算法中則對(duì)以前的狀態(tài)取加和。,3、算法評(píng)價(jià),維特比算法的時(shí)間復(fù)雜度也是O(N2T),維特比算法的時(shí)間復(fù)雜度也是 。,.

9、,3.3學(xué)習(xí)問(wèn)題,解決HMM學(xué)習(xí)問(wèn)題的常用算法有前向-后向算法（Baum-Welch算法）：,第三個(gè)問(wèn)題用來(lái)解答如何調(diào)整一個(gè)給定HMM的參數(shù)使得在某種準(zhǔn)則下，該HMM最大化觀測(cè)序列的概率，這也是三個(gè)問(wèn)題中難度最大的問(wèn)題。目前還沒(méi)有方法可解析地求解模型的參數(shù)使得能最大化觀測(cè)序列的概率。事實(shí)上，對(duì)于任何一個(gè)用作訓(xùn)練用的有限長(zhǎng)的觀測(cè)序列，還沒(méi)有一個(gè)全局最優(yōu)的模型參數(shù)估計(jì)的方法。,1、算法思想,BW算法運(yùn)用了機(jī)器學(xué)習(xí)中的梯度下降的思想。首先對(duì)于HMM的參數(shù) 進(jìn)行一個(gè)初始的估計(jì)（很可能是錯(cuò)誤的），然后通過(guò)訓(xùn)練評(píng)估參數(shù) 的有效性并減少它們所引起的錯(cuò)誤來(lái)更新 ，使得和給定的訓(xùn)練數(shù)據(jù)的誤差變小。,.,定義 為

10、給定訓(xùn)練序列O和模型 時(shí)，時(shí)刻t時(shí)Markov鏈處于狀態(tài) 和時(shí)刻t+1時(shí)狀態(tài)為 的概率，即,2、算法過(guò)程,.,.,網(wǎng)格計(jì)算關(guān)系圖,.,對(duì)模型參數(shù)進(jìn)行重估：,定義后驗(yàn)概率函數(shù)：,有：,于是，我們從某個(gè)模型 開(kāi)始（可以預(yù)先或隨機(jī)選擇），可以推出如下新的模型：,利用上述公式進(jìn)行反復(fù)的參數(shù)估計(jì)，直到 不再有明顯提高。,.,3、算法評(píng)價(jià),BW算法是一種反復(fù)爬山法，是EM(期望值最大化)算法的一個(gè)特例。最大化過(guò)程被稱為在訓(xùn)練集上的訓(xùn)練。它只能找到局部最優(yōu)解。為了使得到的是全局極大，必須要求 的初始值給得接近全局極大。這是應(yīng)用本法的一項(xiàng)難點(diǎn)。,.,4.HHM應(yīng)用背景,.,4.1自動(dòng)文本分類(lèi),自動(dòng)文本分類(lèi)領(lǐng)域

11、近年來(lái)已經(jīng)產(chǎn)生了若干成熟的分類(lèi)算法，如支持向量機(jī)(SVM)、K近鄰(KNN)、樸素貝葉斯(NB)等算法，但這些算法主要基于概率統(tǒng)計(jì)模型，沒(méi)有與文本自身的語(yǔ)法和語(yǔ)義建立起聯(lián)系。,楊健, 汪海航. 基于隱馬爾可夫模型的文本分類(lèi)算法J. 計(jì)算機(jī)應(yīng)用, 2010, 30(9):2348-2350.提出了將隱馬爾可夫序列分析模型(HMM)用于自動(dòng)文本分類(lèi)的算法。,該模型通過(guò)觀察文本的特征詞組成及頻率對(duì)不同類(lèi)別文本進(jìn)行分類(lèi)，分別建立HMM分類(lèi)器。HMM中的觀察輸出就是特征詞的組成。HMM的狀態(tài)轉(zhuǎn)換，可以看做是從與該類(lèi)別不是很相關(guān)的詞組成的文檔輸出分布，向與該類(lèi)別非常相關(guān)的詞組成的文檔輸出分布轉(zhuǎn)化的一種過(guò)程

12、。因此，狀態(tài)從起始點(diǎn)向終結(jié)點(diǎn)轉(zhuǎn)化對(duì)應(yīng)著類(lèi)別相關(guān)詞匯的強(qiáng)化。,.,HMM分類(lèi)器訓(xùn)練,.,HMM分類(lèi)器應(yīng)用,HMM評(píng)估問(wèn)題,.,4.2漢語(yǔ)詞性標(biāo)注,王敏, 鄭家恒. 基于改進(jìn)的隱馬爾科夫模型的漢語(yǔ)詞性標(biāo)注J. 計(jì)算機(jī)應(yīng)用, 2006, 26(s2):197-198.介紹了一種改進(jìn)的HMM，更能體現(xiàn)詞語(yǔ)的上下文依賴關(guān)系。,詞性標(biāo)注的任務(wù)是計(jì)算機(jī)通過(guò)學(xué)習(xí)自動(dòng)地標(biāo)注出有歧義的詞的詞性?，F(xiàn)有的詞性標(biāo)注所采用的語(yǔ)言模型主要可以分為基于規(guī)則的方法和基于統(tǒng)計(jì)的方法?；谝?guī)則的方法適應(yīng)性較差，并且非統(tǒng)計(jì)模型的本質(zhì)使它通常作為一個(gè)獨(dú)立的標(biāo)注器，而很難被用作更大概率模型的組件部分。,傳統(tǒng)的HMM只考慮到了上文對(duì)當(dāng)前詞

13、的依賴關(guān)系，沒(méi)有考慮到該詞后面即下文與該詞的依賴關(guān)系。,詞性標(biāo)注問(wèn)題可描述為HMM解碼問(wèn)題，即在給定觀察序列（詞序列）的條件下搜索最佳的隱馬爾科夫狀態(tài)序列（詞性序列）的問(wèn)題。,.,傳統(tǒng)HMM與改進(jìn)HMM的測(cè)試結(jié)果比較,.,4.3漢語(yǔ)自動(dòng)分詞,李家福, 張亞非. 一種基于概率模型的分詞系統(tǒng)J. 系統(tǒng)仿真學(xué)報(bào), 2002, 14(5):544-546.提出了一種基于生語(yǔ)料庫(kù)（語(yǔ)料庫(kù)未作任何切分）的算法，基于詞的出現(xiàn)概率，根據(jù)極大似然原則進(jìn)行分詞。,詞是自然語(yǔ)言處理系統(tǒng)中重要的知識(shí)載體與基本操作單元。在書(shū)面漢語(yǔ)中詞與詞之間沒(méi)有明顯的切分標(biāo)志。,給定詞的出現(xiàn)概率，根據(jù)極大似然原則（MLP），一個(gè)句子分

14、成詞 ，須使 最大。本模型可以看成一個(gè)零階HHM。,.,HMM模型的訓(xùn)練,EM算法：,.,分詞算法性能比較,.,4.4文本信息抽取,在一階隱馬爾可夫模型中，假設(shè)狀態(tài)轉(zhuǎn)移概率和觀察值輸出概率僅依賴于模型當(dāng)前的狀態(tài)，一定程度降低了信息抽取的精確度。而二階隱馬爾可夫模型合理地考慮了概率和模型歷史狀態(tài)的關(guān)聯(lián)性，對(duì)錯(cuò)誤信息有更強(qiáng)的識(shí)別能力。,信息抽取是指從文本中抽取特定的事實(shí)信息，被抽取出來(lái)的信息以結(jié)構(gòu)化的形式描述，直接存入數(shù)據(jù)庫(kù)中，供用戶查詢以及進(jìn)一步分析利用。,周順先, 林亞平, 王耀南,等. 基于二階隱馬爾可夫模型的文本信息抽取J. 電子學(xué)報(bào), 2007, 35(11):2226-2231.提出了一種基于二階HMM的文本信息抽取算法。,.,