隱馬爾科夫模型

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 其他應用領域,1.馬爾科夫模型,馬爾科夫(Markov)模型是由俄羅斯數學家Andrei AMarkov于20世紀初提出的一個統(tǒng)計模型。,以上隨機過程可以稱為可觀測Markov模型，因為此過程的輸出在每一個時間點是一個狀態(tài)，并且每一個狀態(tài)對應一個可觀測事件。,上述模型稱為一階Markov模型。,如把條件（1

2、）適當放松，任一時刻的隨機變量只依賴于前兩（三，k）個時刻的隨機變量，則此模型為兩（三，k）階Markov模型。,Markov模型,2.隱馬爾科夫模型,一個HMM是不確定的、隨機的有限狀態(tài)自動機，由不可觀測的狀態(tài)轉移過程(一個Markov鏈)和可觀測的觀察生成過程組成。按觀測值是離散還是連續(xù)的，HMM可分為離散型和連續(xù)型。我們這里主要介紹離散HMM。,隱馬爾可夫模型（HMM）是一種在Markov鏈的基礎上發(fā)展起來的統(tǒng)計信號模型，能夠利用收集的訓練樣本進行自適應學習。,隱馬爾科夫模型,HMM拓撲結構,左右型的HMM,全連通的HMM,含并行結構的HMM,含間隔跳轉的HMM,3.HHM基本問題,HM

3、M理論有3個基本問題：,3.1評估問題,解決HHM評估問題的典型算法有窮舉搜索直接計算法、前向算法和后向算法：,一、窮舉搜索直接計算,2、算法過程,3、算法評價,二、前向算法,1、算法思想,到達某網格節(jié)點的概率可以用前一時刻N個節(jié)點的概率表示出來。 前向算法通過已經保存了的子路徑來計算新路徑的概率。,HHM網狀結構,2、算法過程,t時刻前向概率的遞歸關系,3、算法評價,2后向算法,1、算法思想 和前向算法基本一致，唯一的區(qū)別是選擇的局部狀態(tài)不同。,2、算法過程,3、算法評價,t時刻后向概率的遞歸關系,3.2解碼問題,1、算法思想,解答解碼問題，即尋求對于給定觀測序列的最優(yōu)狀態(tài)序列。有好幾種標準

4、可用于定義最優(yōu)狀態(tài)序列。比如，其中一個可能的優(yōu)化標準是分別選擇每個時刻各自最可能的狀態(tài)。 但是每個時刻最可能的狀態(tài)的疊加不一定能得到最可能的狀態(tài)序列?？赡苓@種得到的最優(yōu)序列根本是“不合法”的。這種算法僅簡單地考慮了每一個時刻點各自最可能的狀態(tài)，而沒有考慮到狀態(tài)序列發(fā)生的概率。,對于上述問題的一個可行的解決方案就是修改優(yōu)化標準。于是提出了解決HMM解碼問題的一個典型算法 Viterbi算法。,2、算法過程,在實現上，Viterbi算法和前向算法十分相似。最主要的區(qū)別在于在Viterbi算法中遞歸時對以前的狀態(tài)取最大值，而在前向算法中則對以前的狀態(tài)取加和。,3、算法評價,維特比算法的時間復雜度也是

5、O(N2T),3.3學習問題,解決HMM學習問題的常用算法有前向-后向算法（Baum-Welch算法）：,第三個問題用來解答如何調整一個給定HMM的參數使得在某種準則下，該HMM最大化觀測序列的概率，這也是三個問題中難度最大的問題。目前還沒有方法可解析地求解模型的參數使得能最大化觀測序列的概率。事實上，對于任何一個用作訓練用的有限長的觀測序列，還沒有一個全局最優(yōu)的模型參數估計的方法。,1、算法思想,2、算法過程,對模型參數進行重估：,3、算法評價,4.HHM應用背景,4.1自動文本分類,自動文本分類領域近年來已經產生了若干成熟的分類算法，如支持向量機(SVM)、K近鄰(KNN)、樸素貝葉斯(N

6、B)等算法，但這些算法主要基于概率統(tǒng)計模型，沒有與文本自身的語法和語義建立起聯(lián)系。,楊健, 汪海航. 基于隱馬爾可夫模型的文本分類算法J. 計算機應用, 2010, 30(9):2348-2350.提出了將隱馬爾可夫序列分析模型(HMM)用于自動文本分類的算法。,該模型通過觀察文本的特征詞組成及頻率對不同類別文本進行分類，分別建立HMM分類器。HMM中的觀察輸出就是特征詞的組成。HMM的狀態(tài)轉換，可以看做是從與該類別不是很相關的詞組成的文檔輸出分布，向與該類別非常相關的詞組成的文檔輸出分布轉化的一種過程。因此，狀態(tài)從起始點向終結點轉化對應著類別相關詞匯的強化。,HMM分類器訓練,HMM分類器應

7、用,HMM評估問題,4.2漢語詞性標注,王敏, 鄭家恒. 基于改進的隱馬爾科夫模型的漢語詞性標注J. 計算機應用, 2006, 26(s2):197-198.介紹了一種改進的HMM，更能體現詞語的上下文依賴關系。,詞性標注的任務是計算機通過學習自動地標注出有歧義的詞的詞性。現有的詞性標注所采用的語言模型主要可以分為基于規(guī)則的方法和基于統(tǒng)計的方法?；谝?guī)則的方法適應性較差，并且非統(tǒng)計模型的本質使它通常作為一個獨立的標注器，而很難被用作更大概率模型的組件部分。,傳統(tǒng)的HMM只考慮到了上文對當前詞的依賴關系，沒有考慮到該詞后面即下文與該詞的依賴關系。,詞性標注問題可描述為HMM解碼問題，即在給定觀察

8、序列（詞序列）的條件下搜索最佳的隱馬爾科夫狀態(tài)序列（詞性序列）的問題。,傳統(tǒng)HMM與改進HMM的測試結果比較,4.3漢語自動分詞,李家福, 張亞非. 一種基于概率模型的分詞系統(tǒng)J. 系統(tǒng)仿真學報, 2002, 14(5):544-546.提出了一種基于生語料庫（語料庫未作任何切分）的算法，基于詞的出現概率，根據極大似然原則進行分詞。,詞是自然語言處理系統(tǒng)中重要的知識載體與基本操作單元。在書面漢語中詞與詞之間沒有明顯的切分標志。,HMM模型的訓練,EM算法：,分詞算法性能比較,4.4文本信息抽取,在一階隱馬爾可夫模型中，假設狀態(tài)轉移概率和觀察值輸出概率僅依賴于模型當前的狀態(tài)，一定程度降低了信息抽取的精確度。而二階隱馬爾可夫模型合理地考慮了概率和模型歷史狀態(tài)的關聯(lián)性，對錯誤信息有更強的識別能力。,信息抽取是指從文本中抽取特定的事實信息，被抽取出來的信息以結構化的形式描述，直接存入數據庫中，供用戶查詢以及進一步分析利用。,周順先, 林亞平, 王耀南,等. 基于二階隱馬爾可夫模型的文本信息抽取J. 電子學報, 2007, 35(11):2226-2231.提出了一種基于二階HMM的文本信息抽取算法。,假設1： 在HMM中，隱藏的狀態(tài)序列是一個二階Markov鏈，即在t+1時刻的狀態(tài)的轉移概率不僅依賴于t時刻的狀態(tài)，同時依賴于t-1時刻的狀態(tài)。