1、隱馬爾可夫模型基本概念

隱馬爾可夫模型是關(guān)于時序的概率模型，描述由一個隱藏的馬爾科夫鏈隨機(jī)生成不可觀測的狀態(tài)隨機(jī)序列，再由各個狀態(tài)生成一個觀測從而產(chǎn)生觀測隨機(jī)序列的過程。

隱馬爾可夫模型的形式定義如下：

設(shè) $Q$ 是所有可能狀態(tài)的集合， $V$ 是所有可能觀測的集合：

$Q=\{q_1,q_2,\dots,q_N\}\quad V=\{v_1,v_2,\dots,v_M\}$

其中 $N$ 為可能狀態(tài)數(shù)， $M$ 為可能觀測數(shù)。

$I$ 是長度為 $T$ 的狀態(tài)序列， $O$ 是對應(yīng)的觀測序列：

$I=(i_1,i_2,\dots,i_T)\quad O=(o_1,o_2,\dots,o_T)$

$A$ 是狀態(tài)轉(zhuǎn)移概率矩陣：

$A=[a_{ij}]_{N\times N}$

其中：

$a_{ij}=P(i_{t+1}=q_j|i_t=q_i)$

$B$ 是觀測概率矩陣：

$B=[b_j(k)]_{N\times M}$

其中：

$b_j(k)=P(o_t=v_k|i_t=q_j)$

$\pi$ 是初始狀態(tài)概率向量：

$\pi=(\pi_i)$

其中：

$\pi_i=P(i_1=q_i)$

隱馬爾可夫模型由初始狀態(tài)概率向量 $\pi$ 、狀態(tài)轉(zhuǎn)移概率矩陣 $A$ 和觀測概率矩陣 $B$ 決定。因此隱馬爾可夫模型 $\lambda$ 可表示為：

$\lambda=(A,B,\pi)$

具體來說，長度為 $T$ 的觀測序列的生成過程如下：按照初始狀態(tài)分布 $\pi$ 產(chǎn)生狀態(tài) $i_1$ ，按狀態(tài) $i_t$ 的觀測概率分布 $b_{i_t}(k)$ 生成 $o_t$ ，按狀態(tài) $i_t$ 的狀態(tài)轉(zhuǎn)移概率分布 $\{a_{i_t i_{t+1}} \}$ 產(chǎn)生狀態(tài) $i_{t+1}$ ，依次遞推。

由定義可知隱馬爾可夫模型的兩個基本假設(shè)：

（1）齊次馬爾可夫性假設(shè)，即隱藏的馬爾科夫鏈在任意時刻 $t$ 的狀態(tài)只依賴于其前一時刻的狀態(tài)，與其他時刻狀態(tài)及觀測無關(guān)，也與時刻 $t$ 無關(guān)。

（2）觀測獨(dú)立性假設(shè)，即任意時刻的觀測只依賴于該時刻的馬爾科夫鏈狀態(tài)，與其它觀測狀態(tài)無關(guān)。

隱馬爾可夫模型的三個基本問題如下：

（1）概率計算問題：給定模型 $\lambda=(A,B,\pi)$ 和觀測序列 $O=(o_1,o_2,\dots,o_T)$ ，計算在模型 $\lambda$ 下序列 $O$ 出現(xiàn)的概率 $P(O|\lambda)$ 。

（2）學(xué)習(xí)問題：已知觀測序列 $O=(o_1,o_2,\dots,o_T)$ ，估計模型 $\lambda=(A,B,\pi)$ 參數(shù)，使得在該模型下觀測序列 $P(O|\lambda)$ 最大。

（3）預(yù)測問題：已知模型 $\lambda=(A,B,\pi)$ 和觀測序列 $O=(o_1,o_2,\dots,o_T)$ ，求使得 $P(I|O)$ 最大的狀態(tài)序列 $I=(i_1,i_2,\dots,i_T)$ 。

接下來分別闡述這三個問題的解決方法。

2、概率計算算法

2.1、直接計算法

狀態(tài) $I=(i_1,i_2,\dots,i_T)$ 的概率是：

$P(I|\lambda)=\pi_{i_1}a_{i_1 i_2}\dots,a_{i_{T-1}i_T}$

對固定的 $I=(i_1,i_2,\dots,i_T)$ 觀測序列 $O=(o_1,o_2,\dots,o_T)$ 的概率是：

$P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)\dots,b_{i_T}(o_T)$

$O,I$ 同時出現(xiàn)的聯(lián)合概率為：

$P(O,I|\lambda)=P(O|I,\lambda)P(I|\lambda)$

從而：

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

可以看到，上式是對所有可能的 $I$ 序列求和，而長度為 $T$ 的 $I$ 序列的數(shù)量是 $O(N^T)$ 數(shù)量級的，而 $P(O,I|\lambda)$ 的計算量是 $O(T)$ 級別的，因此計算量為 $O(TN^T)$ ，非常大，這種算法在實際中不可行。

2.2、前向算法

首先定義前向概率：給定隱馬爾可夫模型 $\lambda$ ，定義到時刻 $t$ 部分觀測序列為 $o_1,o_2,\dots,o_t$ 且狀態(tài)為 $q_i$ 的概率為前向概率，記作：

$\alpha_t(i)=P(o_1,o_2,\dots,o_t,i_t=q_i|\lambda)$

觀測序列概率的前向算法如下：

（1）初值：

$\alpha_1(i)=\pi_i b_i(o_1),\quad i=1,2,\dots,N$

（2）遞推，對 $t=1,2,\dots,T-1$ ：

$\alpha_{t+1}(i)=\lbrack\sum_{j=1}^N \alpha_t(j) a_{ji}\rbrack b_i(o_{t+1}),\quad i=1,2,\dots,N$

（3）終止：

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

前向算法高效的關(guān)鍵是局部計算前向概率，然后利用路徑結(jié)構(gòu)將前向概率遞推到全局，得到 $P(O|\lambda)$ 。前向概率算法計算量是 $O(TN^2)$ 級別的。

2.3、后向算法

首先定義后向概率：給定隱馬爾可夫模型 $\lambda$ ，定義在時刻 $t$ 狀態(tài)為 $q_i$ 的條件下，從 $t+1$ 到 $T$ 部分觀測序列為 $o_{t+1},o_{t+2},\dots,o_T$ 的概率為后向概率，記作：

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

觀測序列概率的后向算法如下：

（1）初值：

$\beta_T(i)=1,\quad i=1,2,\dots,N$

（2）遞推，對 $t=T-1,T-2,\dots,1$ ：

$\beta_t(i)=\sum_{j=1}^N a_{ij}b_j (o_{t+1})\beta_{t+1}(j)$

（3）終止：

$P(O|\lambda)=\sum_{i=1}^N \pi_i b_i(o_1)\beta_1(i)$

3、學(xué)習(xí)算法

3.1、監(jiān)督學(xué)習(xí)方法

若有 $S$ 個長度相同觀測序列和對應(yīng)狀態(tài)序列 $\{(O_1,I_1),(O_2,I_2),\dots,(O_S,I_S) \}$ 則可利用極大似然估計得到隱馬爾可夫模型參數(shù)：

設(shè)樣本中時刻 $t$ 處于狀態(tài) $i$ 時刻 $t+1$ 轉(zhuǎn)移到狀態(tài) $j$ 的頻數(shù)為 $A_{ij}$ ，那么狀態(tài)轉(zhuǎn)移概率 $a_{ij}$ 的估計為：

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

設(shè)樣本中狀態(tài)為 $j$ 觀測為 $k$ 的頻數(shù)為 $B_{jk}$ ，那么觀測概率 $b_j(k)$ 的估計為：

$\hat_j(k)=\frac{B_{jk}}{\sum_{k=1}^M B_{jk}}$

初始狀態(tài) $\pi_i$ 的估計 $\hat{\pi}_i$ 為 $S$ 個樣本中初始狀態(tài)為 $q_i$ 的頻率。

3.2、無監(jiān)督學(xué)習(xí)方法（Baum-Welch算法）

假設(shè)給定訓(xùn)練數(shù)據(jù)只包含 $S$ 個長度為 $T$ 的觀測序列 $\{O_1,O_2,\dots,O_S \}$ 而沒有對應(yīng)狀態(tài)序列，我們可以把狀態(tài)數(shù)據(jù)看作不可觀測的隱數(shù)據(jù) $I$ ，則隱馬爾可夫模型事實上是一個含有隱變量的概率模型：

$P(O|\lambda)=\sum_I P(O|I,\lambda)P(I|\lambda)$

其參數(shù)可由EM算法實現(xiàn)。

4、預(yù)測算法

4.1、近似算法

近似算法的思想是，在每個時刻 $t$ 選擇在該時刻最有可能出現(xiàn)的狀態(tài) $i_t^*$ ，從而得到一個狀態(tài)序列 $I^*=(i_1^*,i_2^*,\dots,i_T^*)$ 。

近似算法的優(yōu)點(diǎn)是計算簡單，缺點(diǎn)是不能保證預(yù)測的狀態(tài)序列整體是最有可能的狀態(tài)序列，因為預(yù)測的狀態(tài)序列可能有實際不發(fā)生的部分，比如存在轉(zhuǎn)移概率為0的相鄰狀態(tài)。盡管如此，近似算法還是有用的。

4.2、維特比算法

維特比算法實際上是用動態(tài)規(guī)劃解隱馬爾可夫模型預(yù)測問題，即用動態(tài)規(guī)劃求概率最大路徑（最優(yōu)路徑），此路徑對應(yīng)一個狀態(tài)序列。

定義在時刻 $t$ 狀態(tài)為 $i$ 的所有單個路徑 $(i_1,i_2,\dots,i_t)$ 中概率最大值為：

$\delta_t(i)=\max_{i_1,i_2,\dots,i_{t-1}}P(i_t=i,i_{t-1},\dots,i_1,o_t,o_{t-1},\dots,o_1|\lambda),\quad i=1,2,\dots,N$

由定義得遞推式：

$\begin{aligned} \delta_{t+1}(i)&=\max_{i_1,i_2,\dots,i_{t-1}}P(i_{t+1}=i,i_{t-1},\dots,i_1,o_t,o_{t-1},\dots,o_1|\lambda)\\ &=\max_{1\leq j\leq N}[\delta_t(j)a_{ji}]b_i(o_{t+1}) \end{aligned}$