亚洲经典九九在线视频,9热8在线视频,国产欧美精品一二区

機(jī)器學(xué)習(xí)之隱馬爾科夫模型（HMM）

1、隱馬爾科夫模型介紹
2、隱馬爾科夫數(shù)學(xué)原理
3、Python代碼實(shí)現(xiàn)隱馬爾科夫模型
4、總結(jié)

隱馬爾可夫模型介紹

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

下面我們來從概率學(xué)角度定義馬爾科夫模型，從一個典型例子開始：

假設(shè)有4個盒子，每個盒子里面有不同數(shù)量的紅、白兩種顏色的球，具體如下表：

盒子編號	1	2	3	4
紅球數(shù)	5	3	6	8
白球數(shù)	5	7	4	2

現(xiàn)在從這些盒子中取出T個球，取樣規(guī)則為每次選擇一個盒子取出一個球，記錄其顏色，放回。在這個過程中，我們只能觀測到球的顏色的序列，觀測不到球是從哪個盒子中取出來的，即觀測不到盒子的序列，這里有兩個隨機(jī)序列，一個是盒子的序列（狀態(tài)序列），一個是球的顏色的觀測序列（觀測序列），前者是隱藏的，只有后者是可觀測的。這里就構(gòu)成了一個馬爾科夫的例子。
定義 $Q$ 是所有的可能的狀態(tài)集合，V是所有的可能的觀測的集合：
$Q = \{q_1,q_2,\cdots,q_N\},　　　　　V = \{v_1,v_2,\cdots,v_M\}$
其中，Ｎ是可能的狀態(tài)數(shù)，Ｍ是可能的觀測數(shù)，例如上例中Ｎ＝４，Ｍ＝２。

$I$ 是長度為T的狀態(tài)序列， $O$ 是對應(yīng)的觀測序列：
$I = (i_1,i_2,\cdots,i_T),　　　　　　O = (o_1,o_2,\cdots,o_T)$
A是狀態(tài)轉(zhuǎn)移概率矩陣：
$A = [a_{i,j}]_{N \times N}$
其中， $a_{i,j} = P(i_{t+1} = q_j|i_t = q_i),　i=1,2,\cdots,N;j=1,2,\cdots,N$ 是指在時刻 $t$ 處于狀態(tài) $q_i$ 的條件下在時刻 $t+1$ 轉(zhuǎn)移到狀態(tài) $q_j$ 的概率。

B是觀測概率矩陣：
$B = [b_j(k)]_{N \times M}$
其中， $b_j(k) = P(o_t = v_k|i_t = q_j),　k=1,2,\cdots,M;j=1,2,\cdots,N$ 是指在時刻 $t$ 處于狀態(tài) $q_j$ 的條件下生成觀測 $v_k$ 的概率。

$\pi$ 是初始狀態(tài)概率向量：
$\pi = (\pi_i)$
其中， $\pi_i = P(i_1 = q_i),　i=1,2,\cdots,N$ 是指在時刻 $t$ =1處于狀態(tài) $q_i$ 的概率。

由此可得到，隱馬爾可夫模型 $\lambda$ 的三元符號表示，即
$\lambda = (A,B,\pi)$
$A,B,\pi$ 稱為隱馬爾可夫模型的三要素。

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

(1)齊次馬爾科夫性假設(shè)，即假設(shè)隱藏的馬爾科夫鏈在任意時刻 $t$ 的狀態(tài)只和 $t$ -1狀態(tài)有關(guān)；
$P(i_t|i_{t-1},o_{t-1},\cdots,i_1,o_1) = P(i_t|i_{t-1}),　　　　t=1,2,\cdots,T$
(2)觀測獨(dú)立性假設(shè)，觀測只和當(dāng)前時刻狀態(tài)有關(guān)；
$P(o_t|i_T,i_{T-1},o_{T-1},\cdots,i_{t+1},o_{t+1},i_t,i_{t-1},o_{t-1},\cdots,i_1,o_1) = P(O_t|i_t)$
仍以上面的盒子取球為例，假設(shè)我們定義盒子和球模型：

狀態(tài)集合： $Q$ = {盒子1，盒子2，盒子3，盒子4}， N=4
觀測集合： $V$ = {紅球，白球} M=2
初始化概率分布：
$\pi = (0.25,0.25,0.25,0.25)^T$
狀態(tài)轉(zhuǎn)移矩陣：
$A = \left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 0.4 & 0 & 0.6 & 0 \\ 0 & 0.4 & 0 & 0.6 \\ 0 & 0 & 0.5 & 0.5 \end{matrix} \right]$
觀測矩陣:
$B = \left[ \begin{matrix} 0.5 & 0.5 \\ 0.3 & 0.7 \\ 0.6 & 0.4 \\ 0.8 & 0.2 \end{matrix} \right]$

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

1、概率計算問題

給定： $\lambda = (A,B,\pi)　O=(o_1,o_2,\cdots,o_T)$

計算： $P(O|\lambda)$
2、學(xué)習(xí)問題

已知： $O=(o_1,o_2,\cdots,o_T)$

估計： $\lambda = (A,B,\pi)$ ,使 $P(O|\lambda)$ 最大
3、預(yù)測問題（解碼）

已知： $\lambda = (A,B,\pi)　O=(o_1,o_2,\cdots,o_T)$

求：使 $P(I|O)$ 最大的狀態(tài)序列 $I=(i_1,i_2,\cdots,i_T)$

下面我們使用python代碼寫一個HMM模型生成序列 $O$ 的示例代碼

import numpy as np

class HMM(object):
    def __init__(self, N, M, pi=None, A=None, B=None):
        self.N = N
        self.M = M
        self.pi = pi
        self.A = A
        self.B = B

    def get_data_with_distribute(self, dist): # 根據(jù)給定的概率分布隨機(jī)返回數(shù)據(jù)（索引）
        r = np.random.rand()
        for i, p in enumerate(dist):
            if r < p: return i
            r -= p

    def generate(self, T: int):
        '''
        根據(jù)給定的參數(shù)生成觀測序列
        T: 指定要生成觀測序列的長度
        '''
        result = []
        for ind in range(T):        # 依次生成狀態(tài)和觀測數(shù)據(jù)
            if ind==0:
                i = self.get_data_with_distribute(self.pi)
            else:
                i = self.get_data_with_distribute(self.A[i])
            o = self.get_data_with_distribute(self.B[i])
            result.append(o)
        return result

if __name__ == "__main__":
    pi = np.array([0.25, 0.25, 0.25, 0.25])
    A = np.array([
        [0,  1,  0, 0],
        [0.4, 0, 0.6, 0],
        [0, 0.4, 0, 0.6],
        [0, 0, 0.5, 0.5]])
    B = np.array([
        [0.5, 0.5],
        [0.3, 0.7],
        [0.6, 0.4],
        [0.8, 0.2]])
    hmm = HMM(4, 2, pi, A, B)
    print(hmm.generate(10))  # 生成10個數(shù)據(jù)
 
# 生成結(jié)果如下
[0, 0, 0, 0, 1, 1, 1, 1, 0, 0]   # 0代表紅球，1代表白球

隱馬爾可夫模型數(shù)學(xué)原理

下面我們從隱馬爾可夫模型的三個基本問題出發(fā)，逐個解釋問題解法：

1、概率計算問題
- 直接計算法
- 前向算法
- 后向算法
直接計算法：
- 狀態(tài)序列 $I=(i_1,i_2,\cdots,i_T)$ 概率： $P(I|\lambda)=\pi_{i_1} a_{i_1 i_2} a_{i_2 i_3}\cdots a_{i_{T-1}i_T}$
- 對固定的狀態(tài)序列 $I$ ，觀測序列 $O$ 的概率： $P(O|I,\lambda)$
  $P(O|I,\lambda) = b_{i_1}(o_1) b_{i_2}(o_2) \cdots b_{i_T}(o_T)$
- $O$ 和 $I$ 同時出現(xiàn)的聯(lián)合概率為：
  $P(O,I|\lambda) = P(O|I,\lambda)P(I|\lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1 i_2} b_{i_2}(o_2) \cdots a_{i_{T-1}i_T}b_{i_T}(o_T)$
- 對所有的可能的狀態(tài)序列 $I$ 求和，得到觀測序列 $O$ 的概率：
  $P(O|\pi) = \sum_I{P(O|i,\lambda)P(I|\lambda)} = \sum_{i_1,i_2,\cdots,i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1 i_2} b_{i_2}(o_2) \cdots a_{i_{T-1}i_T}b_{i_T}(o_T)$
  此算法的復(fù)雜度為 $O(TN^T)$ ，計算量太大，不可行。
前向算法：
- 前向概率定義：給定隱馬爾科夫模型 $\lambda$ ，定義到時刻t部分觀測序列為： $o_1,o_2,\cdots,o_t$ ，且狀態(tài)為 $q_i$ 的概率為前向概率，記作：
  $\alpha_t(i) = P(o_1,o_2,\cdots,o_t,i_t=q_t|\lambda)$
  輸入：隱馬爾可夫模型 $\lambda$ ，觀測序列 $O$ ；
  
  輸出：觀測序列概率 $P(O|\lambda)$
  
  初值： $\alpha_1(i) = \pi_ib_i(o_1)，i=1,2,\cdots,N$
  
  遞推： $\alpha_{t+1}(i) = \left[ \sum_{j=1}^N \alpha_t(j) a_{_ji} \right]b_i(o_{t+1}),i=1,2,\cdots,N$
  
  終止： $P(O|\lambda) = \sum_{i=1}^N \alpha_T(i)$
  
  算法復(fù)雜度 $O(N^2T)$ ，算法復(fù)雜度大大降低
  
  因為： $\alpha_T(i) = P(o_1,o_2,\cdots,o_T,i_T=q_i|\lambda)$
  
  所以： $P(O|\lambda) = \sum_{i=1}^N \alpha_T(i)$
- 下面以一個具體的例子來演示前向算法計算過程：
  $A = \left[ \begin{matrix} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 & 0.5 \end{matrix} \right], B = \left[ \begin{matrix} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{matrix} \right], \pi = (0.2,0.4,0.4)^T$
  假設(shè)T = 3，O = (紅，白，紅)，使用前向算法計算 $P(O|\lambda)$ ，模型 $\lambda = (A,B,\pi)$ ，狀態(tài)集合 $Q=\{1,2,3\}$ ，觀測集合 $V = \{紅，白\}$
  
  （1）計算初值
  $\alpha_1(1) = \pi_1 b_1(o_1) = 0.2\times0.5 = 0.1 \\ \alpha_1(2) = \pi_2 b_2(o_1) = 0.4\times0.4 = 0.16 \\ \alpha_1(3) = \pi_3 b_3(o_1) = 0.4\times0.7 = 0.28$
  （2）遞推計算
  $\begin{align} \alpha_2(1) & = \left[ \begin{matrix} \sum_{i=1}^3\alpha_1(i)a_{i1} \end{matrix} \right]b_1(o_2) = (0.1\times0.5+0.16\times0.3+0.28\times0.2)\times0.5 = 0.154\times0.5 = 0.077 \\ \alpha_1(2) & = \left[ \begin{matrix} \sum_{i=1}^3\alpha_1(i)a_{i2} \end{matrix} \right]b_2(o_2) = 0.184\times0.6 = 0.1104 \\ \alpha_1(3) & = \left[ \begin{matrix} \sum_{i=1}^3\alpha_1(i)a_{i3} \end{matrix} \right]b_3(o_2) = 0.202\times0.3 = 0.0606 \\ \alpha_3(1) & = \left[ \begin{matrix} \sum_{i=1}^3\alpha_2(i)a_{i1} \end{matrix} \right]b_1(o_3) = 0.04187 \\ \alpha_3(2) & = \left[ \begin{matrix} \sum_{i=1}^3\alpha_2(i)a_{i2} \end{matrix} \right]b_2(o_3) = 0.03551 \\ \alpha_3(3) & = \left[ \begin{matrix} \sum_{i=1}^3\alpha_2(i)a_{i3} \end{matrix} \right]b_3(o_3) = 0.05284 \end{align}$
  （3）終止
  $P(O|\lambda) = \sum_{i=1}^3 \alpha_3(i) = 0.13022$
后向算法：
- 后向概率定義：給定隱馬爾可夫模型 $\lambda$ ，定義在時刻t狀態(tài)為 $q_i$ 的條件下，從t+1到T的部分觀測序列為： $o_{i+1},o_{i+2},\cdots,o_T$ 的概率為后向概率，記作：
  $\beta_t(i) = P(o_{t+1},o_{t+2},\cdots,o_T|i_t=q_i,\lambda)$
  仍然可以使用遞推的方法求得后向概率 $\beta_t(i)$ 及觀測序列概率 $P(O|\lambda)$
  
  輸入：隱馬爾科夫模型 $\lambda$ ，觀測序列O；
  
  輸出：觀測序列概率 $P(O|\lambda)$ .
  
  （1）　　　　　　　　　　　　 $\beta_T(i) = 1,　i=1,2,\cdots,N$
  
  （2）對 $t=T-1,T-2,\cdots,1$
  
  $\beta_t(i)=\sum_{j=1}^N a_{ij}b_j(o_{t+1})\beta_{t+1}(j), i=1,2,\cdots,N$
  
  （3 $P(O|\lambda)=\sum_{i=1}^N \pi_ib_i(o_1)\beta_1(i)$
  
  前后向統(tǒng)一寫為：（t=1和t=T-1分別對應(yīng)）
  $P(O|\lambda) = \sum_{i=1}^N \sum_{j=1}^N \alpha_t(i)a_{ij}b_j(o_{t+1}) \beta_{t+1}(j), 　t=1,2,\cdots,T-1$
  一些概率和期望值計算方式：
  
  1、給定模型 $\lambda$ 和觀測 $O$ ，在時刻 $t$ 處于狀態(tài) $q_i$ 的概率，記 $\gamma_t(i)=P(i_t=q_t|O,\lambda)$
  $\gamma_t(i)=P(i_t=q_t|O,\lambda)=\frac{P(i_t=q_t,O|\lambda)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N \alpha_t(j)\beta_t(j)}$
  2、給定模型 $\lambda$ 和觀測 $O$ ，在時刻 $t$ 處于狀態(tài) $q_i$ 且在時刻 $t+1$ 處于 $q_j$ 概率，記 $\xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,\lambda)$
  $\xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j,O|\lambda)=\frac{P(i_t=q_t,i_{t+1}=q_j,O|\lambda)}{P(O|\lambda)}=\frac{P(i_t=q_t,i_{t+1}=q_j,O|\lambda)}{\sum_{i=1}^N \sum_{j=1}^N P(i_t=q_i,i_{t+1}=q_j,O|\lambda)} = \frac{\alpha_t(i)a_{ij}b_j(o_{t+1}) \beta_{t+1}(j)}{\sum_{i=1}^N \sum_{j=1}^N \alpha_t(i)a_{ij}b_j(o_{t+1}) \beta_{t+1}(j)}$
  3、由1和2可得，(1)在觀測O下狀態(tài)i出現(xiàn)的期望值： $\sum_{t=1}^T \gamma_t(i)$ ，（2）在觀測O下由狀態(tài)i轉(zhuǎn)移的期望值： $\sum_{t=1}^{T-1} \gamma_t(i)$ ，（3）在觀測O下由狀態(tài)i轉(zhuǎn)移到狀態(tài)j的期望值： $\sum_{t=1}^{T-1} \xi_t(i,j)$ 。
2、學(xué)習(xí)問題

監(jiān)督學(xué)習(xí)方法：
- 假設(shè)訓(xùn)練數(shù)據(jù)是包括觀測序列O和對應(yīng)的狀態(tài)序列I， ${(O_1,I_1),(O_2,I_2),\cdots,(O_S,I_S)}$
- 可以利用極大似然估計發(fā)來估計隱馬爾可夫模型參數(shù)。
已知： ${(O_1,I_1)(O_2,I_2),\cdots,(O_S,I_S)}$

（1）轉(zhuǎn)移概率 $a_{ij}$ 的估計：假設(shè)樣本中時刻t處于狀態(tài)i，時刻t+1轉(zhuǎn)移到狀態(tài)j的頻數(shù)為 $A_{ij}$ 那么轉(zhuǎn)臺轉(zhuǎn)移概率 $a_{ij}$ 的估計是：
$\hat{a}_{ij} = \frac{A_{ij}}{\sum_{j=1}^N A_{ij}},　i=1,2,\cdots,N;j=1,2,\cdots,N$
（2）觀測概率 $b_j(k)$ 的估計：設(shè)樣本中狀態(tài)為j并觀測為k的頻數(shù)是 $B_j(k)$ 那么狀態(tài)j觀測為k的概率
$\hat_j(k) = \frac{B_{jk}}{\sum_{k=1}^M B_{jk}}，　j=1,2,\cdots,N;k=1,2,\cdots,M$
（3）初始狀態(tài)概率 $\pi_i$ 的估計 $\hat{\pi}_i$ 為S個樣本中初始狀態(tài)為 $q_i$ 的頻率。

非監(jiān)督學(xué)習(xí)方法：

Baum-Welch算法

假定訓(xùn)練數(shù)據(jù)只包括{O1,O2,...Os}，求模型參數(shù) $\lambda=(A,B,\pi)$ ，實(shí)質(zhì)上是有隱變量的概率模型：EM算法 $P(O|\lambda)=\sum_I P(O|I,\lambda)P(I|\lambda)$ 。

（1）確定完全數(shù)據(jù)的對數(shù)似然函數(shù)

完全數(shù)據(jù) $(O,I)=(o_1,o_2,\cdots,o_T,i_1,i_2,\cdots,i_r)$

完全數(shù)據(jù)的對數(shù)似然函數(shù) $logP(O,I|\lambda)$

（2）EM的E步，求Q函數(shù) $Q(\lambda,\bar{\lambda})=\sum_I logP(O,I|\lambda)P(O,I|\bar{\lambda})$ ， $P(O,I|\lambda)=\pi_{i_1}b_{i_1}(O_1)a_{i_1 i_2}b_{i_2}(o_2)\cdots a_{i_{T-1}i_T}b_{i_T}(O_T)$ 則：
$Q(\lambda,\bar{\lambda})=\sum_I log\pi_{i_1}P(O,I|\hat{\lambda})+\sum_I(\sum_{t=1}^{T-1}log a_{i_t i_{t+1}})P(O,I|\bar{\lambda})+\sum_I(\sum_{t=1}^T logb_{i_t}(o_t))P(O,I|\bar{\lambda})$
對序列總長度T進(jìn)行

（3）EM算法的M步，極大化 $Q(\lambda,\bar{\lambda})$ 求模型參數(shù) $A,B,\pi$

第一項 $\sum_I log\pi_{i_0}P(O,I|\hat{\lambda})=\sum_{i=1}^N log\pi_i P(O,i_1=i|\bar{\lambda})$ ，由約束條件： $\sum_{i=1}^N \pi_i = 1$ 利用拉格朗日乘子 $\sum_{i=1}^N log\pi_iP(O,i_1=i|\bar{\lambda})+\gamma(\sum_{i=1}^N \pi_i -1)$ 求偏導(dǎo)數(shù)，并令結(jié)果等于0
$\frac{\partial}{\partial \pi_i}[\sum_{i=1}^N log\pi_i P(O,i_1=i|\bar{\lambda})+\gamma(\sum_{i=1}^N \pi_i -1)]=0$
得： $P(O,i_1 = i|\bar{\lambda})+\gamma\pi_i = 0$ $\gamma=-P(O|\bar{\lambda})$ $\pi_i = \frac{P(O,i_1=i|\bar{\lambda})}{P(O|\bar{\lambda})}$

第二項可寫成 $\sum_I(\sum_{t=1}^{T-1}log a_{i_t i_{t+1}})P(O,I|\bar{\lambda})=\sum_{i=1}^N \sum_{j=1}^N \sum_{t=1}^{T-1} log a_{ij}P(O,i_t=i,i_{t+1}=j|\bar{\lambda})$ 由約束條件 $\sum_{j=1}^N a_{ij}=1$ ，拉格朗日乘子法得：
$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})}$
第三項 $\sum_I(\sum_{t=1}^T logb_{i_t}(o_t))P(O,I|\bar{\lambda})=\sum_{j=1}^N \sum_{t=1}^T logb_j(o_t)P(O,i_t=j|\bar{\lambda})$ 由約束條件 $\sum_{k=1}^M b_j(k)=1$ ，注意，只有在 $o_t=v_k$ 時 $b_j(o_t)$ 對 $b_j(k)$ 的偏導(dǎo)數(shù)才不為0，以 $I(o_t=v_k)$ 表示，求得
$b_j(k)=\frac{\sum_{t=1}^T P(O,i_t=j|\bar{\lambda})I(o_t=v_k)}{\sum_{t=1}^N P(O,i_t=j|\bar{\lambda})}$
將以上得到的概率分別用 $\gamma_t(i)，\xi_t(i,j)$ 表示
$a_{ij}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)} \\ b_j(k)=\frac{\sum_{t=1,o_t=v_k}^T \gamma_t(j)}{\sum_{t=1}^T \gamma_t(j)} \\ \pi_i = \gamma_1(i)$
Baum-Welch算法流程：

輸入：觀測數(shù)據(jù) $O=(o_1,o_2,\cdots,o_T)$ ；

輸出：隱馬爾可夫模型參數(shù)。

（1）初始化

對n=0，選取 $a_{ij}^{(0)}，b_j(k)^{(0)}，\pi_i^{(0)}$ 得到模型 $\lambda^{(0)}=(A^{(0)},B^{(0)},\pi^{(0)})$

（2）遞推，對n=1,2,...,
$a_{ij}^{(n+1)}=\frac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)} \\ b_j(k)^{(n+1)}=\frac{\sum_{t=1,o_t=v_k}^T \gamma_t(j)}{\sum_{t=1}^T \gamma_t(j)} \\ \pi_i^{(n+1)} = \gamma_1(i)$
右側(cè)各值按照觀測 $O=(o_1,o_2,\cdots,o_T)$ 和模型 $\lambda^{(n)}=(A^{(n)},B^{(n)},\pi^{(n)})$ 計算

（3）終止，得到模型參數(shù) $\lambda^{(n+1)}=(A^{(n+1)},B^{(n+1)},\pi^{(n+1)})$
3、預(yù)測問題

預(yù)測算法

（1）近似算法

想法：在每個時刻t選擇在該時刻最后可能的狀態(tài) $i_t^*$ ，從而得到一個序列狀態(tài)序列 $I^*=(i_1^*,i_2^*,\cdots,i_T^*)$ ，將它作為預(yù)測的結(jié)果，在時刻t處于狀態(tài) $q_i$ 的概率：
$\gamma_t(i)=\frac{\alpha_t(i) \beta_t(i)}{P(O|\lambda)}=\frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)}$
在每一時刻t最有可能的狀態(tài)是： $i_t^*=\underset{1\leq i \leq N}{\operatorname{argmax}}[\gamma_t(i)],t=1,2,\cdots,T$

從而得到狀態(tài)序列： $I_*=(i_1^*,i_2^*,\cdots,i_T^*)$

得到的狀態(tài)有可能實(shí)際不發(fā)生

（2）維比特算法

用動態(tài)規(guī)劃解概率最大路徑，一個路徑對應(yīng)一個狀態(tài)序列。
最優(yōu)路徑具有這樣的特性：如果最優(yōu)路徑在時刻t通過結(jié)點(diǎn) $i_t^*$ ，那么這一路徑從結(jié)點(diǎn) $i_t^*$ 到終點(diǎn) $i_T^*$ 的部分路徑，對于從 $i_t^*$ 到 $i_T^*$ 的所有可能的部分路徑來說，必須是最優(yōu)的。
只需從時刻t=1開始，遞推地計算在時刻t狀態(tài)為i的各條部分路徑的最大概率，直至得到時刻t=T狀態(tài)為i的各條路徑的最大概率，時刻t=T的最大概率即為最優(yōu)路徑的概率 $P^*$ 最有路徑的終結(jié)點(diǎn) $i_T^*$ 也同時得到。
之后，為了找出最優(yōu)路徑的各個結(jié)點(diǎn)，從終結(jié)點(diǎn)開始，由后向前逐步求得結(jié)點(diǎn) $i_{T-1}^*,\cdots,i_1^*$ ，得到最優(yōu)路徑 $I^*=(i_1^*,i_2^*,\cdots,i_T^*)$

導(dǎo)入兩個變量 $\delta$ 和 $\psi$ ，定義在時刻t狀態(tài)為i的所有單個路徑 $(i_1,i_2,\cdots,i_t)$ 中概率最大值為：
$\delta_t(i)=\underset{i_1,i_2,\cdots,i_{t-1}}{\operatorname{max}}P(i_t=i,i_{t-1},\cdots,i_1,o_t,\cdots,o_1|\lambda),i=1,2,\cdots,N$
由定義可得變量 $\delta$ 的遞推公式：
$\delta_{t+1}(i)=\underset{i_1,i_2,\cdots,i_t}{\operatorname{max}}P(i_{t+1}=i,i_t,\cdots,i_1,o_{t+1},\cdots,o_1|\lambda)=\underset{1\leq j \leq N}{\operatorname{max}}[\delta_t(j)a_{ji}]b_i(o_{t+1}),　　i=1,2,\cdots,N;t=1,2,\cdots,T-1$
定義在時刻t狀態(tài)為i的所有單個路徑 $(i_1,i_2,\cdots,i_{t-1},i)$ 中概率最大的路徑的第t-1個結(jié)點(diǎn)為
$\psi_t(i)=\underset{1\leq j \leq N}{\operatorname{argmax}}[\delta_{t-1}(j)a_{ji}],　　i=1,2,\cdots,N$
輸入：模型 $\lambda=(A,B,\pi)$ 和觀測 $O=(o_1,o_2,\cdots,o_T)$ ；

輸出：最優(yōu)路徑 $I^*=(i_1^*,i_2^*,\cdots,i_T^*)$ .

①初始化
$\delta_1(i)=\pi_ib_i(o_1),　　i=1,2,\cdots,N \\ \psi_1(i)=0,　　i=1,2,\cdots,N$
②遞推，對 $t=2,3,\cdots,T$
$\delta_t(i)=\underset{1\leq j \leq N}{\operatorname{max}}[\delta_{t-1}(j)a_{ji}]b_i(o_t),　　i=1,2,\cdots,N \\ \psi_t(i)=\underset{1\leq j \leq N}{\operatorname{argmax}}[\delta_{t-1}(j)a_{ji}],　　i=1,2,\cdots,N$
③終止
$P*=\underset{1\leq i \leq N}{\operatorname{max}}\delta_T(i) \\ i_T^*=\underset{1\leq i \leq N}{\operatorname{argmax}}[\delta_T(i)]$
④最優(yōu)路徑回溯，對 $t=T-1,T-2,\cdots,1$
$i_t^*=\psi_{t+1}(i_{t+1}^*)$
求得最優(yōu)路徑 $I^*=(i_1^*,i_2^*,\cdots,i_T^*)$
示例：
$A= \left[\begin{matrix} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 & 0.5 \end{matrix}\right]， B = \left[\begin{matrix} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{matrix}\right]， \pi = (0.2,0.4,0.4)^T$
O=(紅，白，紅)，試求最優(yōu)狀態(tài)序列，即最優(yōu)路徑 $I^*=(i_1^*,i_2^*,i_3^*)$

①初始化：在t=1時，對每一個狀態(tài)i，i=1,2,3，求狀態(tài)i觀測O1為紅的概率，記為： $\delta_1(i)=\pi_ib_i(o_1)=\pi_ib_i(紅),i=1,2,3$

代入實(shí)際數(shù)據(jù)： $\delta_1(1)=0.10，\delta_1(2)=0.16，\delta_1(3)=0.28$ ，記 $\psi_1(i)=0,i=1,2,3$

②在t=2時，對每一個狀態(tài)i，i=1,2,3，求在t=1時狀態(tài)為j觀測O1為紅并在t=2時狀態(tài)為i觀測O2為白的路徑的最大概率，記為 $\delta_2(i)$
$\delta_2(i)=\underset{1\leq j \leq 3}{\operatorname{max}}[\delta_1(j)a_{ji}]b_i(o_2)$
同時，對每個狀態(tài)i，記錄概率最大路徑的前一個狀態(tài)j， $\psi_2(i)=\underset{1 \leq j \leq 3}{\operatorname{argmax}}[\delta_1(j)a_{ji}]，i=1,2,3$

計算：
$\delta_2(1)=\underset{1 \leq j \leq 3}{\operatorname{max}}[\delta_1(j)a_{j1}]b_1(o_2)=\underset{j}{\operatorname{max}}\{0.10\times0.5,0.16\times0.3,0.28\times0.2\}\times0.5=0.028 \\ \psi_2(1)=3 \\ \delta_2(2)=0.0504，\psi_2(2)=3 \\ \delta_2(3)=0.042，\psi_2(3)=3$
同樣，在t=3時
$\delta_3(i)=\underset{1 \leq j \leq 3}{\operatorname{max}}[\delta_2(j)a_{ji}]b_i(o_3) \\ \psi_3(i)=\underset{1\leq j \leq 3}{\operatorname{argmax}}[\delta_2(j)a_{ji}] \\ \delta_3(1) = 0.00756，\psi_3(1)=2 \\ \delta_3(2) = 0.01008，\psi_3(2)=2 \\ \delta_3(3) = 0.0147，\psi_3(3)=3$
③以P*表示最優(yōu)路徑的概率：
$P^*=\underset{1 \leq i \leq 3}{\operatorname{max}}\delta_3(i)=0.0147$
最優(yōu)路徑的終點(diǎn)是：
$i_3^* = \underset{i}{\operatorname{argmax}}[\delta_3(i)]=3$
④由最優(yōu)路徑的終點(diǎn) $i_3^*$ ，逆向找到 $i_2^*,i_1^*$
$在t=2時，i_2^*=\psi_3(i_3^*)=\psi_3(3)=3 \\ 在t=1時，i_1^*=\psi_2(i_2^*)=\psi_2(3)=3 \\$
于是求得最優(yōu)路徑，即最優(yōu)狀態(tài)序列：
$I^*=(i_1^*,i_2^*,i_3^*)=(3,3,3)$

隱馬爾科夫模型Python實(shí)現(xiàn)

import numpy as np

class HMM(object):
    def __init__(self, N, M, pi=None, A=None, B=None):
        self.N = N
        self.M = M
        self.pi = pi
        self.A = A
        self.B = B

    def get_data_with_distribute(self, dist): # 根據(jù)給定的概率分布隨機(jī)返回數(shù)據(jù)（索引）
        r = np.random.random()
        for i, p in enumerate(dist):
            if r < p: return i
            r -= p

    def generate(self, T: int):
        '''
        根據(jù)給定的參數(shù)生成觀測序列
        T: 指定要生成觀測序列的長度
        '''
        result = []
        i = 0
        for ind in range(T):        # 依次生成狀態(tài)和觀測數(shù)據(jù)
            if ind==0:
                i = self.get_data_with_distribute(self.pi)
            else:
                i = self.get_data_with_distribute(self.A[i,:])
            o = self.get_data_with_distribute(self.B[i,:])
            result.append(o)
        return result
    
    def forward(self,X):
        '''
        根據(jù)給定的參數(shù)計算條件概率(前向算法)
        X：觀測數(shù)據(jù)
        '''
        alpha = self.pi * self.B[:,X[0]]
        for x in X[1:]:
            #將alpha構(gòu)造成(N,1)維度，使用廣播機(jī)制
            alpha = np.sum(self.A * alpha[...,np.newaxis],axis=0) * self.B[:,x]
        
        return alpha.sum()
    
    def backward(self,X):
        '''
        根據(jù)給定的參數(shù)計算條件概率(后向算法)
        X：觀測數(shù)據(jù)
        '''
        beta = np.ones(self.N)
        for x in X[:0:-1]:
            #beta默認(rèn)為(1,N)維度，使用廣播機(jī)制
            beta = np.sum(self.A * self.B[:,x] * beta,axis=1)

        return np.sum(beta * self.pi * self.B[:,X[0]],axis=0)
    
    def get_alpha_beta(self,X):
        '''
        根據(jù)給定數(shù)據(jù)與參數(shù)，計算所有時刻的前向概率和后向概率
        '''
        T = len(X)
        alpha = np.zeros((T,self.N))
        alpha[0,:] = self.pi * self.B[:,X[0]]
        for t in range(T-1):
            alpha[t+1,:] = np.sum(self.A * alpha[t,:][...,np.newaxis],axis=0) * self.B[:,X[t+1]]
            
        beta = np.ones((T,self.N))
        for t in range(T-1,0,-1):
            beta[t-1,:] = np.sum(self.A * beta[t,:] * self.B[:,X[t]],axis=1)

        # print(alpha[T-1,:].sum(),np.sum(beta[0,:] * self.pi * self.B[:,X[0]],axis=0))        
        return alpha,beta
    
    def fit(self,X):
        '''
        根據(jù)觀測序列估計參數(shù)
        '''
        #初始化參數(shù)pi，A，B
        self.pi = np.random.random(self.N)
        self.pi /= np.sum(self.pi)
        self.A = np.random.random((self.N,self.N))
        self.A /= np.sum(self.A,axis=1)[:,np.newaxis]
        self.B = np.random.random((self.N,self.M))
        self.B /= np.sum(self.B,axis=1)[:,np.newaxis]
        
        T = len(X)
        for epoch in range(10):
            #根據(jù)公式計算下一時刻參數(shù)值
            alpha,beta = self.get_alpha_beta(X)
            gamma = alpha * beta
            for i in range(self.N):
                for j in range(self.N):
                    self.A[i,j] = np.sum(alpha[:-1,i] * beta[1:,j] * self.A[i,j] * self.B[j,X[1:]],axis=0) / np.sum(gamma[:-1,i],axis=0)
            for i in range(self.N):
                for j in range(self.M):
                    self.B[i,j] = np.sum(gamma[:,i] * (X == j),axis=0) / np.sum(gamma[:,i],axis=0)
                    
            self.pi = gamma[0] / gamma[0].sum()
            
    def decode(self,X):
        '''
        解碼問題，參數(shù)已知，根據(jù)給定的觀測序列，返回最大概率的隱藏序列
        '''
        T = len(X)
        x = X[0]
        delta = self.pi[:,np.newaxis] * self.B[:,x]
        varphi = np.zeros((T,self.N),dtype=np.int)
        path = [0] * T
        for t in range(1,T):
            # delta = delta.reshape(-1,1)
            tmp = delta * self.A
            varphi[t,:] = np.argmax(tmp,axis=0)
            delta = np.max(tmp,axis=0) * self.B[:,X[t]]

        path[-1] = np.argmax(delta)
        #回溯最優(yōu)路徑
        for t in range(T-1,0,-1):
            path[t-1] = varphi[t,path[t]]
            
        return path
 
if __name__ == "__main__":
    pi = np.array([0.25, 0.25, 0.25, 0.25])
    A = np.array([
        [0,  1,  0, 0],
        [0.4, 0, 0.6, 0],
        [0, 0.4, 0, 0.6],
        [0, 0, 0.5, 0.5]])
    B = np.array([
        [0.5, 0.5],
        [0.3, 0.7],
        [0.6, 0.4],
        [0.8, 0.2]])
    hmm = HMM(4, 2, pi, A, B)
    print(hmm.generate(10))  # 生成10個數(shù)據(jù)
    X = [0,0,1,1,0] #觀測序列為紅，紅，白，白，紅
    print(hmm.forward(X))
    print(hmm.backward(X))

    import matplotlib.pyplot as plt
    def triangle_data(T):   # 生成三角波形狀的序列
        data = []
        for x in range(T):
            x = x % 2
            data.append(x if x <= 1 else 2-x)
        return data
    
    data = np.array(triangle_data(15))
    hmm.fit(data)
    gen_obs = hmm.generate(15)  # 再根據(jù)學(xué)習(xí)的參數(shù)生成數(shù)據(jù)
    x = np.arange(15)
    plt.scatter(x, gen_obs, marker='*', color='r')
    plt.plot(x, data, color='g')
    plt.show()

    pi = np.array([0.2, 0.4, 0.4])
    A = np.array([
        [0.5,  0.2,  0.3],
        [0.3, 0.5, 0.2],
        [0.2, 0.3, 0.5]])
    B = np.array([
        [0.5, 0.5],
        [0.4, 0.6],
        [0.7, 0.3]])
    O = [0,1,0]
    hmm = HMM(3, 2, pi, A, B)
    path = hmm.decode(O)
    print(path) #輸出(2,2,2)為索引

總結(jié)

隱馬爾可夫模型是關(guān)于時序的概率模型，由初始狀態(tài)概率向量 $\pi$ 、狀態(tài)轉(zhuǎn)移概率矩陣A和觀測概率矩陣B決定，可以寫成 $\lambda=(A,B,\pi)$ 的形式，隱馬爾可夫模型是一個生成模型，它的應(yīng)用很多，在分詞、詞性標(biāo)注、NLP、語音識別等領(lǐng)域都有著廣泛的應(yīng)用，是一個非常經(jīng)典的機(jī)器學(xué)習(xí)模型。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

機(jī)器學(xué)習(xí)之隱馬爾科夫模型（HMM）

機(jī)器學(xué)習(xí)之隱馬爾科夫模型（HMM）

機(jī)器學(xué)習(xí)之隱馬爾科夫模型（HMM）

隱馬爾可夫模型介紹

隱馬爾可夫模型數(shù)學(xué)原理

隱馬爾科夫模型Python實(shí)現(xiàn)

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

機(jī)器學(xué)習(xí)之隱馬爾科夫模型（HMM）

機(jī)器學(xué)習(xí)之隱馬爾科夫模型（HMM）

隱馬爾可夫模型介紹

隱馬爾可夫模型數(shù)學(xué)原理

隱馬爾科夫模型Python實(shí)現(xiàn)

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av