作者：哈工大SCIR碩士生 樂遠
隱馬爾可夫模型(HMM)是可用於標註問題的統計學習模型，描述由隱藏的馬爾可夫鏈隨機生成觀測序列的過程，屬於生成模型。
說到隱馬爾可夫模型(HMM)，我們先來了解下馬爾可夫模型(Markov模型)，Markov模型是一種統計模型，廣泛地應用在語音識別，詞性自動標註，音字轉換，概率文法等各個自然語言處理的應用領域。
一. 馬爾可夫模型(Markov模型)
設是隨機變量序列，其中每個隨機變量的取值在有限集，稱為狀態空間。Markov特徵是
如果 具有這些特徵，那麼這個隨機變量序列稱為一個馬爾可夫過程（鏈）。
Markov的形式化表示：一個馬爾可夫模型是一個三元組 ，其中 是狀態的集合，是初始狀態的概率，是狀態間的轉移概率。具體例子用圖形表示如下，
相應的分別是，
隱馬爾可夫模型與馬爾可夫模型不同的是各個狀態（或者狀態轉移弧）都有一個輸出，但是狀態是不可見的。
最簡單的情形：不同的狀態只能有不同的輸出，
增加一點靈活性：不同的狀態，可以輸出相同的輸出，
再增加一點靈活性：輸出在狀態轉移中進行，
最大的靈活性：在狀態轉移中以特定的概率分布輸出，
這就得到了我們要講的隱馬爾可夫模型。
二. 隱馬爾可夫模型(HMM)
1.HMM的形式化定義
HMM是一個五元組，其中是狀態的集合，是輸出字符的集合，是初始狀態的概率，是狀態轉移的概率, 是狀態轉移時輸出字符的概率。
一個HMM的例子用圖形表示如下，
2. 隱馬爾可夫模型的三個基本問題
3. 評估問題的解法
已知，，計算？
我們先來化簡一下，
窮舉所有可能的的情況，求和得到，但是時間複雜度太高，為。
使用動態規劃使得算法更高效，定義一個前向變量表示到時刻部分觀測序列為且狀態為的概率為向前概率，記為，即
則可以遞推得到，
前向過程算法如下，
一個簡單的前向過程例子如下，
同樣的道理，我們定義在時刻狀態為的條件下，從到的部分觀測序列為的概率為後向概率，記作，即
直接採用遞推即可得到後向算法。
後向算法過程如下,
4. 解碼問題的解法
給定一個輸出字符序列，和一個模型，如何確定產生這一序列概率最大的狀態序列？
即
我們定義表示為在時刻到達狀態，輸出字符時，輸出前面個字符的最可能路徑的概率，
則有
這樣我們就得到了維特比算法(Viterbi Algorithm)，算法過程如下：
一個簡單的viterbi算法舉例如下，
5. 學習問題解法
給定一個輸出字符的序列，如何調整模型的參數使得產生這一序列的概率最大?
隱馬爾可夫模型的學習，根據訓練數據是包括觀測數據和對應的狀態序列還是只有觀測序列，可以分為有監督學習和無監督學習，其中無監督的學習即是利用EM算法思想的Baum-Welch算法。
假設訓練數據包含個長度相同的觀測序列和對應的狀態序列，那麼可以利用極大似然估計法來估計隱馬爾可夫模型的參數，具體估計方法如下：
1. 轉移概率的估計
設樣本中時刻處於狀態時刻處於狀態的頻數為，那麼狀態轉移概率的估計是
2. 觀測概率的估計
設樣本中狀態為並觀測為的頻數是，那麼狀態為觀測為的概率的估計是
由於監督學習的方法需要使用訓練數據，而人工標註的代價往往很高，有時會採用非監督學習的方法。
假設給定的訓練數據只包含個長度為的觀測序列而沒有對應的狀態序列，目標是學習隱馬爾可夫模型的參數。我們將觀測序列數據看做觀測數據，狀態序列數據看做不可觀測數據，那麼隱馬爾可夫模型事實上是一個包含隱變量的概率模型
它的參數學習可以由EM算法實現。
（算法推導過程）
(1) 確定完全數據的對數似然函數所有觀測數據寫成，所有的隱數據寫成，完全數據是。完全數據的對數似然函數是。
(2) EM算法的E步：求函數的。
其中是隱馬爾可夫模型參數的當前估計值，是要極大化的隱馬爾可夫模型參數。因為，
所以函數可以拆分寫成
式中求和都是對所有訓練數據的序列總長度進行的。
(3) EM算法的M步：極大化函數，求模型參數。
由於要極大化的參數在函數式子中單獨的出現在三個項中，所以只需要對各項分別極大化。第一項可以寫成，
注意到滿足，利用拉格朗日乘子法，寫出拉格朗日函數
對其求導數並令結果為0，
得到
對求和得到,
再代入上式子得到，
第二項可以寫成
類似於第一項，利用具有約束條件的拉格朗日乘子法惡意求出
第三項可以寫成，
同樣利用拉格朗日乘子法，約束條件是，注意只有在時對的偏導數才不為0，以表示，得到，
為了簡便，我們使用一下式子簡化，給定模型和觀測，在時刻處於狀態的概率記
有如下公式：
給定模型和觀測，在時刻處於狀態的概率記 :
有如下推倒：
我們結合上文以及EM算法可以推導如下公式
Baum-Welch算法過程：
輸入：觀測數據；
輸出：隱馬爾可夫模型參數。
1. 初始化。對，選取得到模型
2. 遞推。對
3. 終止。得到模型參數
參考資料
[1]公式參考李航《統計學習方法》
[2]圖片選自哈爾濱工業大學關毅教授《自然語言處理》課程PPT
本期責任編輯：丁 效
本期編輯：劉元興
「哈工大SCIR」公眾號
主編：車萬翔
副主編：張偉男，丁效
責任編輯：張偉男，丁效，劉一佳，崔一鳴
編輯：李家琦，吳洋，劉元興，蔡碧波，孫卓，賴勇魁
長按下圖並點擊 「識別圖中二維碼」，即可關注哈爾濱工業大學社會計算與信息檢索研究中心微信公共號：」哈工大SCIR」 。