理解隱馬爾可夫模型

全文PDF下載鏈接：http://sigai.cn/paper_99.html

隱馬爾可夫模型（Hidden Markov Model，簡稱HMM）由Baum等人在1966年提出[1]，是一種概率圖模型，用於解決序列預測問題，可以對序列數據中的上下文信息建模。所謂概率圖模型，指用圖為相互依賴的一組隨機變量進行建模，圖的頂點為隨機變量，邊為變量之間的概率關係。

在隱馬爾可夫模型中，有兩種類型的節點，分別為觀測值序列與狀態值序列，後者是不可見的，它們的值需要通過從觀測值序列進行推斷而得到。很多現實應用可以抽象為此類問題，如語音識別，自然語言處理中的分詞、詞性標註，計算機視覺中的動作識別。隱馬爾可夫模型在這些問題中得到了成功的應用。本文作為已經出版的《機器學習與應用》，清華大學出版社，雷明著第16章“循環神經網絡”中隱馬爾可夫模型一節的擴充，已經被獨立成一章，在第二版中出版。為降低閱讀與理解難度，本文儘量不過多涉及概率圖模型的概念，而是從序列建模的角度對HMM進行解釋。

馬爾可夫過程與馬爾可夫模型

馬爾可夫過程是隨機過程的典型代表。所謂隨機過程，是指一個系統的狀態隨著時間線隨機的演化。這種模型可以計算出系統每一時刻處於各種狀態的概率以及這些狀態之間的轉移概率。首先定義狀態的概念，在

t時刻系統的狀態為Zt，在這裡是一個離散型隨機變量，取值來自一個有限集：

例如我們要為天氣進行建模，需觀察每一天的天氣，則狀態集為：

為簡化表示，將狀態用整數編號，可以寫成：

從1時刻開始到T時刻為止，系統所有時刻的狀態值構成一個隨機變量序列：

系統在不同時刻可以處於同一種狀態，但在任一時刻只能有一種狀態。不同時刻的狀態之間是有關係的。例如，如果今天是陰天，明天下雨的可能性會更大，在時刻t的狀態由它之前時刻的狀態決定，可以表示為如下的條件概率：

即在從1到t-1時刻系統的狀態值分別為Z1,...,Zt-1的前提下，時刻t系統的狀態為Zt的概率。如果要考慮之前所有時刻的狀態計算太複雜。為此進行簡化，假設t時刻的狀態只與t-1時刻的狀態有關，與更早的時刻無關，即忘記了更早的信息。上面的概率可以簡化為

該假設稱為一階馬爾可夫假設，滿足這一假設的馬爾可夫模型稱為一階馬爾可夫模型。如果狀態有n種取值，在t時刻取任何一個值與t-1時刻取任何一個值的條件概率構成一個n×n的矩陣A，稱為狀態轉移概率矩陣，其元素為

該值表示t-1時刻的狀態為i，t時刻的狀態為j，即從狀態i轉移到狀態j的概率。如果知道了狀態轉移矩陣，就可以計算出任意時刻系統狀態取每個值的概率。狀態轉移概率矩陣的元素必須滿足如下約束：

第一條是因為概率值必須在[0,1]之間，第二條是因為無論t時刻的狀態值是什麼，在下一個時刻一定會轉向n個狀態中的一個，因此它們的轉移概率和必須為1。以天氣為例，假設狀態轉移矩陣為

其對應的狀態轉移圖（狀態機）如下圖所示，圖中每個頂點表示狀態，邊表示狀態轉移概率，是有向圖

有一個需要考慮的問題是系統初始時刻處於何種狀態，這同樣是隨機的，可以用向量π

表示。以天氣為例，假設初始時處於晴天的概率是0.5，處於陰天的概率是0.4，處於雨天的概率是0.1，則π為

為簡化表述，引入一個特殊的狀態s0 消掉π，該狀態的編號為0。它是系統初始時所處的狀態，即

z0 = s0，在接下來的時刻從它轉向其他狀態，但在後續任何時刻都不會再進入此狀態。加入初始狀態之後，對狀態轉移矩陣也進行擴充，行和列的下標變為從0開始。以天氣問題為例，擴充後的狀態轉移矩陣為

給定一階馬爾可夫過程的參數，由該模型產生一個狀態序列

Z1,...,ZT的概率為

結果就是狀態轉移矩陣的元素乘積。在這裡假設任何一個時刻的狀態轉移矩陣都是相同的，即狀態轉移矩陣與時刻無關。

對於上面的天氣問題，連續3天全部為晴天的概率為

狀態轉移矩陣通過訓練樣本學習得到，採用最大似然估計。給定一個狀態序列z，馬爾可夫過程的對數似然函數為

這裡使用了指示變量來方便表述。因為狀態轉移矩陣要滿足上面的兩條約束，因此要求解的是如下帶約束的最優化問題

由於對數函數的定義域要求自變量大於0，因此可以去掉不等式約束，上面的最優化問題變成帶等式約束的優化問題，可以用拉格朗日乘數法求解。構造拉格朗日乘子函數

對aij 求偏導數並令導數為0，可以到得

解得

對ai 求偏導數並令導數為0，可以得到

將aij 代入上式可以得到

解得

合併後得到下面的結果

這一結果也符合我們的直觀認識：從i狀態轉移到j狀態的概率估計值就是在訓練樣本中，從i狀態轉移到j狀態的次數除以從狀態轉移到下一個狀態的總次數。對於多個狀態序列，方法與單個狀態序列相同。

隱馬爾可夫模型

在實際應用中，有些時候我們不能直接觀察到狀態的值，即狀態的值是隱含的，只能得到觀測的值。為此對馬爾可夫模型進行擴充，得到隱馬爾可夫模型。

隱馬爾可夫模型描述了觀測變量和狀態變量之間的概率關係。與馬爾可夫模型相比，隱馬爾可夫模型不僅對狀態建模，而且對觀測值建模。不同時刻的狀態值之間，同一時刻的狀態值和觀測值之間，都存在概率關係。

首先定義觀測序列

這是直接能觀察或者計算得到的值。任一時刻的觀測值來自有限的觀測集

接下來定義狀態序列

任一時刻的狀態值也來自有限的狀態集

這與馬爾可夫模型中的狀態定義相同。在這裡，狀態是因，觀測是果，即因為處於某種狀態所以才有某一觀測值。

例如，如果我們要識別視頻中的動作，狀態就是要識別的動作，有站立、坐下、行走等取值，在進行識別之前無法得到其值。觀測是能直接得到的值如人體各個關節點的座標，隱馬爾可夫模型的作用是通過觀測值推斷出狀態值，即識別出動作。

除之前已定義的狀態轉移矩陣之外，再定義觀測矩陣B，其元素為

該值表示t時刻狀態值為si時觀測值vj 為的概率。顯然該矩陣也要滿足和狀態轉移矩陣同樣的約束條件：

另外還要給出初始時狀態取每種值的概率π。隱馬爾可夫模型可以表示為一個五元組

如果加上初始狀態則可以消掉參數π

，只剩下A和B。在實際應用中，一般假設矩陣A和B在任何時刻都是相同的即與時間無關，這樣簡化了問題的計算。

任意一個狀態序列可以看做是這樣產生的：系統在1時刻處於狀態z1，在該狀態下得到觀測值x1 。接下來從z1轉移到z2 ，並在此狀態下得到觀測值x2 。以此類推，得到整個觀測序列。由於每一時刻的觀測值只依賴於本時刻的狀態值，因此在狀態序列z下出現觀測序列的概率x為

這就是所有時刻的狀態轉移概率，觀測概率的乘積。

以天氣問題為例，假設我們不知道每天的天氣，但能觀察到一個人在各種天氣下的活動，根據這一現象來推斷天氣。這裡的活動有3種情況，睡覺，跑步，逛街。對於這個問題，天氣是狀態值，活動是觀測值。該隱馬爾可夫模型如下圖所示

這一問題的觀測矩陣為

在隱馬爾可夫模型中，隱藏狀態和觀測值的數量是根據實際問題人工設定的；狀態轉移矩陣和混淆矩陣通過樣本學習得到。隱馬爾可夫模型需要解決以下三個問題：

1.估值問題，給定隱馬爾可夫模型的參數A和B，計算一個觀測序列出現的概率值p(x)。

2.解碼問題，給定隱馬爾可夫模型的參數A和B以及一個觀測序列x，計算最有可能產生此觀測序列的狀態序列z。

3.學習問題，給定隱馬爾可夫模型的結構，但參數未知，給定一組訓練樣本，確定隱馬爾可夫模型的參數A和B。

按照定義，隱馬爾可夫模型對條件概率p(x|z)建模，因此是一種生成模型。

中文分詞問題

下面以中文分詞問題為例，介紹隱馬爾可夫模型如何用於實際問題，這是典型的序列標註問題。中文分詞即斷句，是自然語言處理中的核心、基礎問題。因為中文和英文不同，各個詞之間沒有空格隔開。對於下面的句子

我是中國人

正確的分詞結果為

我 是 中國人

在這裡觀測序列是輸入的語句，每個字為每個時刻的觀測值。狀態序列為分詞的結果，每個時刻的狀態值有如下幾種情況

其中B表示當前字為一個詞的開始，M表示當前字是一個詞的中間位置，E表示當前字是一個詞的結尾，S表示單字詞。則上面這個句子的分詞標註結果為

我/S 是/S 中/B 國/M 人/E

顯然，得到了這個標註結果，我們就可以得到分詞結果，做法很簡單：

遇到S，則為一個單字詞；遇到B，則為一個詞的開始，直到遇到下一個E，則為一個詞的結尾。

分詞問題為給定觀測序列，計算出概率最大的狀態序列，對應的就是分詞的結果。這通過解碼算法實現。隱馬爾可夫模型的參數則通過用語料庫訓練得到。下圖是分詞的隱馬爾可夫模型按時間線展開後的結果

對於中文分詞，詞性標註等問題，在《機器學習與應用》中有詳細的講解，包括如何用循環神經網絡解決此問題，感興趣的讀者可以進一步閱讀。

估值問題

估值問題需要計算隱馬爾可夫模型產生一個觀測序列x={x1, ..., xT}的概率。因為任意一種狀態序列取值都可能會導致出現此觀測序列，根據全概率公式，其值為

上式列舉所有可能的狀態序列，以及該狀態序列產生此觀測序列的概率，要對nT 項求和。因為每一時刻的狀態取值有n種可能，因此長度為T的狀態序列總共有nT 種可能。下圖展示了這一過程

已經推導過，任意一個狀態序列出現的概率為

由於每一時刻的觀測值只依賴於本時刻的狀態值，因此有

產生一個觀測序列的概率為

直接計算這個值的複雜度是O(nT T)。顯然上面的公式有很多重複計算。例如要計算產生觀測序列(x1,...,x5)的概率，產生它的狀態序列為(z1,...,z5)，假設狀態取值有3種情況。無論z5取什麼值，為了計算整個序列出現的概率，任何一個長度為4的子序列(z1,...,z4)產生觀測子序列(x1,...,x4)的概率都要被重複計算3次。利用這一特點可以使用動態規劃算法高效求解。

假設已經計算出了長度為t-1的觀測序列的概率，現在要計算長度為t的觀測序列的概率。如果狀態的取值有

n種可能，則zt的取值有n種可能。定義變量

這個變量是到時刻t為止的觀測序列，產生它的狀態序列中，最後一個狀態為

i，即zt = i的概率。因此有

根據定義可以得到這個變量的遞歸計算公式

由此得到計算觀測序列概率的高效算法。

上面算法的時間複雜度為O(n2 T)，這比之前大為減少。此算法稱為前向算法，也可以實現後向算法，即從後向前計算。這需要定義變量β然後反向遞推計算，原理與前向算法相同。

下面給出前向算法的直觀解釋。如果將狀態序列所有時刻的路徑展開，可以形成如下圖所示的樹結構

前向變量是對上圖中以某一節點為根的子樹中所有路徑求和的結果。在上圖中在3時刻的值z3經過值a的所有路徑構成的子樹以藍色表示，這一子樹求和的結果即為aa(3)。只要得到所有子樹的求和結果，通過遞推可以得到以它們的父節點為根的子樹的結果。

解碼問題

解碼問題指已知一個觀測序列，尋找出最有可能產生它的狀態序列，這是實際應用時最常見的問題。根據貝葉斯公式，解碼問題可以形式化的定義為如下最大後驗概率問題

和貝葉斯分類器相同，忽略掉分母，因為它對所有狀態序列是相同的。貝葉斯分類器是已知特徵向量計算類後驗概率，這裡是已知觀測序列反算狀態序列的條件概率。

最簡單的方法是列舉所有可能的狀態序列，然後計算它們產生該觀測序列的概率，找出概率最大的那個。但這是沒有必要的，通過使用動態規劃算法，可以高效的解決此問題。動態規劃求解最優路徑時的核心結論是：要保證一個解是全局最優解，其部分解也必須是最優的。根據這一結論，可以得到經典的維特比（Viterbi）算法。

要保證p(x1,...,xT,z1,...,zT)的概率最大，就需要保證p(x1,...,xT-1,z1,...,z

T-1)的概率最大，這相當於尋找一條產生最大概率的路徑，這條路徑對應著一個狀態序列。這和前面的前向算法類似，只要把求和換成求最大值即可。

如果整體路徑是最優的，那麼子路徑也是最優的。假設概率最大的路徑是(z1,...,zT)，在t時刻經過的節點為zTt，路徑序列zt,...,zT 必須是最優的。假設它不是最優的，則存在另外一個序列zt,...,zT 的概率值更大，這與(z1,...,zT )是最優解矛盾。下圖是維特比算法求解的示意圖

上圖中最優路徑用加粗線表示。如果得到了1時刻到3時刻的最優路徑，根據遞推公式可以得到更長的序列的最優路徑。

基於這個思想，從1時刻開始，遞推的計算t時刻狀態zt = i的子序列的最大概率路徑，最後就可以得到整個問題的最優解。這一過程與前向算法、後向算法類似，區別在於是求極大值而不是求和。定義如下變量

即產生觀測序列(x1,...,xt)的所有狀態序列(z1,...,zt)中，t時刻的狀態zt = i的概率的最大值。根據它的定義，可以得到遞推計算公式

最後可以得到產生觀測序列的最大概率為

上面的定義只能得到最大概率，但要求解的得到這個最大概率的狀態序列，為此定義下面的變量記住這個最優路徑

即t時刻的狀態zt = i 概率最大的狀態序列中，t-1時刻的狀態值。有了這兩個變量，就可以得到維特比算法。

在算法實現時，需要存儲所有的βt (i)，而只用存儲當前步的αt (i)。這個算法的時間複雜度為O(nT)。

訓練算法

訓練時給定一組樣本，確定狀態轉移矩陣和觀測矩陣。目標是狀態轉移矩陣和觀測矩陣能很好的解釋這組樣本，通過最大似然估計實現。如果已知訓練樣本集中每個觀測序列對應的狀態序列，則可以直接根據最大似然估計得到模型參數，具體方法已經介紹，不同的是增加了觀測矩陣。

下面考慮第二種情況，訓練樣本集只有觀測值而沒有狀態值。假設有l個訓練樣本，第i個樣本的觀測序列為xi ，其對應的狀態序列為zi ，序列長度為T，zi 未知，計算xi 的邊緣概率時要對其所有可能的取值求和。假設狀態集的大小為n，觀測集的大小為m。為簡化表述，考慮對單個樣本的情況，對數似然函數為

這裡含有隱變量（狀態變量），因此需要用EM算法求解。EM算法的詳細原理在SIGAI之前的公眾號文章“理解EM算法”以及《機器學習與應用》一書中有詳細的講解。

按照EM算法框架，在E步根據參數A和B的當前估計值計算隱變量

z的條件概率

在M步計算數學期望，構造下界函數

在這裡lnQ(z)是與A和B無關的常數，可以忽略。由於狀態轉移矩陣和觀測矩陣滿足等式約束，構造拉格朗日乘子函數

對aij求偏導數並令其為0，可以得到

解得

對bjk求偏導數並令其為0，可以得到

解得

對μi 求偏導數，並令其為0，可以得到

解得

對vj 求偏導數，並令其為0，可以得到

解得

將μi 和vj 的值分別代入aij和bjk的解，可以得到

但上面兩個值直接計算的成本太高，狀態序列z的所有可能取值有nT種。這一問題可用估值問題中使用的技巧解決，遞推的計算這兩個值。

類似的有

因此有

用同樣的方法可以計算出bjk。由此得到求解隱馬爾可夫模型訓練問題的Baum-Welch算法。

用隨機數初始化矩陣A和B的元素，矩陣元素要滿足等式約束條件

參考文獻

[1] Baum, L. E., Petrie, T. Statistical Inference for Probabilistic Functions of Finite State Markov Chains. The Annals of Mathematical Statistics. 37 (6): 1554–1563. 1966.

[2] Baum, L. E., Eagon, J. A. An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bulletin of the American Mathematical Society. 73 (3): 360. 1967.

[3] Baum, L. E., Petrie, T., Soules, G., Weiss, N. A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains. The Annals of Mathematical Statistics. 41: 164. 1970

[4] Baum, L.E. An Inequality and Associated Maximization Technique in Statistical Estimation of Probabilistic Functions of a Markov Process. Inequalities. 3: 1–8. 1972.

[5] Lawrence R. Rabiner. A tutorial on Hidden Markov Models and selected applications in speech recognition. Proceedings of the IEEE. 77 (2): 257–286. 1989.

全文PDF下載地址：http://sigai.cn/paper_99.html