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

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

3、HMM是一個五元組： ，可以簡寫為 ，其中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ā)展起來的統(tǒng)計信號模型，能夠利用收集的訓練樣本進行自適應學習。,.,隱馬爾科夫模型,.,HMM拓撲結(jié)構(gòu),左右型的HMM,全連通的HMM,含并行結(jié)構(gòu)的HMM,含間隔跳轉(zhuǎn)的HMM,.,3.HHM基本問題,HMM理論有3個基本問題：,（2）解碼問題 給定一個HHM的模型 和觀測序列 ，如何

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

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

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

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

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

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

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

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

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

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

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