隱馬爾科夫模型（HMM）是一種有向圖模型，是結(jié)構(gòu)最簡單的動態(tài)貝葉斯網(wǎng)，是可用于標注問題的統(tǒng)計學習模型，描述由隱藏的馬爾科夫鏈隨機生成觀測序列的過程，屬于“生成式模型”。本文介紹HMM的基本概念和三個基本問題的算法推導。

1、HMM是什么

如圖所示是HMM的基本結(jié)構(gòu)。它有兩組變量，上面是不可觀測的狀態(tài)變量，表示某一時刻的系統(tǒng)狀態(tài)；下面是可以被觀測到的觀測變量，表示某一時刻的觀測值。一般地，系統(tǒng)狀態(tài)變量是離散的，觀測變量是離散或連續(xù)的，這里僅討論離散的情況。

HMM的基本結(jié)構(gòu)

圖中的箭頭表示了隱馬爾科夫模型的依賴關(guān)系，也是馬爾科夫鏈的基本特點：系統(tǒng)下一時刻的狀態(tài)僅與前一時刻的狀態(tài)有關(guān)，系統(tǒng)當前時刻的觀測值僅與當前時刻的狀態(tài)有關(guān)。這是研究HMM問題的大前提。基于這種依賴關(guān)系，可以得到所有變量的聯(lián)合概率分布：

$P(X,Y)=P(x_1,y_1,...,x_n,y_n)=P(y_1)P(x_1|y_1)\prod_{i=2}^n P(y_i|y_{i-1})P(x_i|y_i)\\$

設(shè)狀態(tài)集合 $S=(s_1,s_2,...,s_N)$ ，所有可觀測變量的集合 $X=(o_1,o_2,...,o_M)$ 。要確定一個HMM結(jié)構(gòu)，需要以下關(guān)鍵的三組參數(shù)，也稱為HMM的三要素：

① 狀態(tài)轉(zhuǎn)移概率：在圖中表示為 $y_i$ 之間的轉(zhuǎn)換概率，記為矩陣 $A=[a_{ij}]_{N×N}$ ，其中

$a_{ij}=P(y_{t+1}=s_j|y_t=s_i)\\$

② 輸出觀測概率：在圖中表示為某一時刻縱向的推測概率，即根據(jù)當前狀態(tài)得到各個觀測值的概率，記為矩陣 $B=[b_{ij}]_{N×M}$ ，其中

$b_{ij}=P(x_t=o_j|y_t=s_i)\\$

③ 初始狀態(tài)概率：表示初始狀態(tài)即 $y_1$ 的各種取值出現(xiàn)的概率，記為 $\pi =(\pi_1,\pi_2,...,\pi_N)$ ，其中

$\pi_i=P(y_1=s_i)\\$

如果已知了狀態(tài)空間、觀測空間、三組參數(shù)，就可以確定一個HMM模型了。首先根據(jù)初始狀態(tài)概率 $\pi$ 確定 $y_1$ ，再根據(jù) $B$ 向下確定當前時刻觀測值，根據(jù) $A$ 向右確定轉(zhuǎn)移狀態(tài)，一直反復進行直到最后。

在HMM中，人們關(guān)心三個問題，這三個問題分別代表三種應(yīng)用的角度，對應(yīng)若干解決該問題的算法：

① 概率計算問題：給定模型的參數(shù) $\lambda =(A,B,\pi)$ 和某一個觀測到的序列 $O=(o_1,o_2,...,o_T)$ ，計算該觀測序列出現(xiàn)的概率 $P(O|\lambda )$ 。涉及到前向算法和后向算法。

② 學習問題：給定觀測序列 $O=(o_1,o_2,...,o_T)$ ，估計模型參數(shù) $\lambda =(A,B,\pi)$ ，使得產(chǎn)生該觀測序列的概率 $P(O|\lambda )$ 最大。涉及到監(jiān)督學習算法和EM算法。

③ 預(yù)測問題（解碼問題）：給定模型參數(shù) $\lambda =(A,B,\pi)$ 和觀測序列 $O=(o_1,o_2,...,o_T)$ ，求最匹配的狀態(tài)序列 $I=(i_1,i_2,...,i_T)$ ，即最大化 $P(I|O)$ 。涉及到近似算法和維特比算法。

二、概率計算問題

2.1 前向算法

定義前向概率：給定HMM模型的參數(shù) $\lambda$ ，定義從開始到時刻 $t$ 的觀測序列為 $o_1,o_2,...,o_t$ ，并且此時狀態(tài)為 $q_i$ 的概率為前向概率，記為：

$\alpha _i(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)\\$

計算方法如下：

① 計算初值：

$\alpha _1(i)=\pi_ib_i(o_1), i=1,2,...,N\\$

② 遞推公式：

$\alpha _{t+1}(i)=[\sum_{j=1}^N \alpha _t(j)a_{ji}]*b_i(o_{t+1}),\\其中i=1,2,...,N,t=1,2,...,T-1\\$

③ 終止：

$P(O|\lambda )=\sum_{i=1}^N \alpha _T(i)\\$

解釋一下，第一步初始化前向概率，實際上根據(jù)定義求的是聯(lián)合概率，第二步遞推公式中，中括號內(nèi)計算了前一時刻所有可能的狀態(tài)轉(zhuǎn)移為當前時刻狀態(tài)的概率和。實際上前向概率算法是計算了狀態(tài)轉(zhuǎn)移過程中所有的可能路徑的前向概率并求和，其計算量是 $O(N^2T)$ 。

2.2 后向算法

定義后向概率：給定HMM模型的參數(shù) $\lambda$ ，定義時刻 $t$ 狀態(tài)為 $q_i$ 的條件下，從下一時刻開始到最后時刻的觀測序列為 $o_{t+1},o_{t+2},...,o_T$ 的概率為后向概率，記為

$\beta _t(i)=P(o_{t+1},o_{t+2},...,o_T|i_t=q_i,\lambda )\\$

計算方法如下：

① 初始化規(guī)定：

$\beta _T(i)=1,i=1,2,...,N\\$

② 遞推公式，對 $t=T-1,T-2,...,1$ 有：

$\beta _t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta _{t+1}(j),i=1,2,...,N\\$

③ 終止：

$P(O|\lambda )=\sum_{i=1}^N \pi_ib_i(o_1)\beta _1(i)\\$

解釋一下，第一步初始化所有的后向概率為1是規(guī)定，第二步與前向概率的遞歸思路相似，將后一時刻所有可能的狀態(tài)乘以狀態(tài)轉(zhuǎn)換概率 $a_{ij}$ 和輸出觀測概率 $b_{ij}$ 并累加，第三步也是如此，記得用 $\pi _i$ 代替 $a_{ij}$ 。

三、學習問題

學習問題是給定觀測序列，求參數(shù)的估計，即參數(shù)值是多少的時候該觀測序列出現(xiàn)的概率最大。

3.1 監(jiān)督學習方法

假設(shè)給定了S個長度相同的觀測序列和對應(yīng)的狀態(tài)序列，即 $(O_1,I_1),(O_2,I_2),...,(O_S,I_S)$ ，那么利用極大似然法估計參數(shù)，也就是根據(jù)頻數(shù)估計參數(shù)：

$\hat{a} _{ij}=\frac{A_{ij}}{\sum_{j=1}^N A_{ij}} \\\hat _{ij}=\frac{B_{ij}}{\sum_{j=1}^N B_{ij}} \\$

$\hat{\pi} _i$ 是根據(jù)不同初始狀態(tài)出現(xiàn)的頻率求得的相應(yīng)概率。

這種方法需要大量的訓練數(shù)據(jù)，代價較高，所以更實際的方案是非監(jiān)督學習方法--EM算法。

3.2 EM算法

假設(shè)給定的數(shù)據(jù)只有S個長度相同的觀測序列 $(O_1,O_2,...,O_S)$ ，對應(yīng)的狀態(tài)序列不可見并記為 $I$ ，那么HMM是一個含有隱變量的概率模型：

$P(O|\lambda )=\sum_{I} P(O|I,\lambda )P(I|\lambda )\\$

它的參數(shù)學習由EM算法實現(xiàn)。EM算法的推導過程很復雜，涉及到很多數(shù)學知識，這里直接用EM算法的模板來推導。步驟如下：

① 確定完全數(shù)據(jù)的對數(shù)似然函數(shù)。完全數(shù)據(jù)就是把觀測數(shù)據(jù)和狀態(tài)變量拼接（concat）起來，其似然函數(shù)表示為 $logP(O,I|\lambda )$ 。

② EM算法的E步。首先寫出Q函數(shù)，已知Q函數(shù)的定義

$Q(\lambda ,\bar{\lambda } )=E_I[logP(O,I|\lambda )|O,\bar{\lambda } ]\\$

寫出此問題的Q函數(shù)：

$Q(\lambda ,\bar{\lambda } )=\sum_{I}logP(O,I|\lambda )P(O,I| \bar{\lambda } )\\$

其中， $\bar{\lambda }$ 是當前的參數(shù)估計值， $\lambda$ 是要極大化的參數(shù)。觀察到對數(shù)函數(shù)的第一項是可以拆分細化的，先把它拆開：

$Q(\lambda ,\bar{\lambda } )=\sum_{I}log\pi _{i_1}P(O,I| \bar{\lambda } )+\sum_{I}(\sum_{t=1}^{T-1}log a_{i_ti_{t+1}} )P(O,I| \bar{\lambda } )+\sum_{I}(\sum_{t=1}^Tlog b_{i_t}(o_t) )P(O,I| \bar{\lambda } )\\$

③ EM算法的M步。Q函數(shù)由三項組成，由于三個參數(shù)分別在三個加式中，故三個參數(shù)的估計分別求出。分別找到相應(yīng)的約束條件使用拉格朗日數(shù)乘法，對拉格朗日函數(shù)求偏導，解得：

$\pi_i=\frac{P(O,i_1=i|\bar{\lambda }) }{P(O|\bar{\lambda })} \\a_{ij}=\frac{\sum_{t=1}^{T-1} P(O,i_t=i,i_{t+1}=j|\bar{\lambda })}{\sum_{t=1}^{T-1} P(O,i_t=i,|\bar{\lambda })} \\b_j(k)=\frac{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda }) I (o_t=v_k)}{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda })}$

四、預(yù)測問題

預(yù)測問題是已知模型參數(shù)和觀測序列求最佳匹配的狀態(tài)序列。

4.1 近似算法

近似算法的思想是，考慮每個時刻最有可能出現(xiàn)的狀態(tài)，這些狀態(tài)合起來就是要求的狀態(tài)序列。求解某一時刻的最有可能出現(xiàn)的狀態(tài)時，用到了該時刻的前向概率和后向概率。在時刻 $t$ 處于狀態(tài) $q_i$ 的概率為：

$\gamma _t(i)=\frac{\alpha _t(i)\beta _t(i)}{\sum_{j=1}^N \alpha _t(j)\beta _t(j)} \\$

在該時刻最有可能的狀態(tài)是：

$i_t^*=arg\max_{i\in [1,N]} [\gamma _t(i)]\\$

從而計算出所有時刻的最有可能的狀態(tài)。

這種算法的優(yōu)點是計算簡單，缺點是沒有考慮相鄰狀態(tài)之間的轉(zhuǎn)換概率，比如當某兩個相鄰時刻的轉(zhuǎn)換概率為0時，近似算法得到的時間序列實際上是不存在的。

4.2 維特比算法

維特比算法使用的動態(tài)規(guī)劃的原理求最優(yōu)路徑問題，路徑即狀態(tài)序列。動態(tài)規(guī)劃的原理是指，如果在時刻 $t$ 選擇了狀態(tài) $i$ ，那么前 $t-1$ 個時刻一定僅存在一個可計算的概率最大的路徑，當 $t=T$ 時，這條路徑就是模型的最優(yōu)路徑。（leetcode的最優(yōu)路徑題）