隐马尔科夫模型HMM（二） -- 估计问题

叁歲伎倆 2022-01-23 02:59 227阅读 0赞

首先我们来研究HMM的第一个问题 – 估计问题。给定一个HMM模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)和观察序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT，如何快速地计算出给定模型 μ \\mu μ的情况下，观察序列O的概率，即 P ( O ∣ μ ) P\\left ( O|\\mu \\right ) P(O∣μ)？这就是解码问题，这里介绍穷尽所有可能的状态序列、前向算法、后向算法以及前向后向相结合的算法四种方法。

## 一、穷尽法 ##

此种方法是穷尽所有的状态序列，计算出观察序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT出现的概率。对于任意的状态序列 Q = q 1 q 2 q 3 . . . q T Q=q\_\{1\}q\_\{2\}q\_\{3\}...q\_\{T\} Q=q1q2q3...qT，有 P ( O ∣ Q , μ ) = ∏ t = 1 T − 1 P ( O t ∣ q t , q t + 1 , μ ) = b q 1 ( O 1 ) × b q 2 ( O 2 ) × . . . b q T ( O T ) P\\left ( O|Q,\\mu \\right )=\\prod\_\{t=1\}^\{T-1\}P\\left ( O\_\{t\}|q\_\{t\},q\_\{t+1\},\\mu \\right )\\\\=b\_\{q\_\{1\}\}\\left ( O\_\{1\} \\right )\\times b\_\{q\_\{2\}\}\\left ( O\_\{2\} \\right )\\times ...b\_\{q\_\{T\}\}\\left ( O\_\{T\} \\right ) P(O∣Q,μ)=t=1∏T−1P(Ot∣qt,qt\+1,μ)=bq1(O1)×bq2(O2)×...bqT(OT)  
       并且 P ( Q ∣ μ ) = π q 1 a q 1 q 2 a q 2 q 3 . . . a q T − 1 q T P\\left ( Q|\\mu \\right )=\\pi \_\{q\_\{1\}\}a\_\{q\_\{1\}q\_\{2\}\}a\_\{q\_\{2\}q\_\{3\}\}...a\_\{q\_\{T-1\}q\_\{T\}\} P(Q∣μ)=πq1aq1q2aq2q3...aqT−1qT  
       由于 P ( O , Q ∣ μ ) = P ( O ∣ Q , μ ) P ( Q ∣ μ ) P\\left ( O,Q|\\mu \\right )=P\\left ( O|Q,\\mu \\right )P\\left ( Q|\\mu \\right ) P(O,Q∣μ)=P(O∣Q,μ)P(Q∣μ)  
       因此 P ( O ∣ μ ) = ∑ Q P ( O , Q ∣ μ ) = ∑ Q P ( O ∣ Q , μ ) P ( Q ∣ μ ) = ∑ Q π q 1 b q 1 ( O 1 ) ∏ t = 1 T − 1 a q t q t + 1 b q t + 1 ( O t + 1 ) P\\left ( O|\\mu \\right )=\\sum\_\{Q\}P\\left ( O,Q|\\mu \\right )\\\\ =\\sum\_\{Q\}P\\left ( O|Q,\\mu \\right )P\\left ( Q|\\mu \\right )\\\\ =\\sum\_\{Q\}\\pi \_\{q\_\{1\}\}b\_\{q\_\{1\}\}\\left ( O\_\{1\} \\right )\\prod\_\{t=1\}^\{T-1\}a\_\{q\_\{t\}q\_\{t+1\}\}b\_\{q\_\{t+1\}\}\\left ( O\_\{t+1\} \\right ) P(O∣μ)=Q∑P(O,Q∣μ)=Q∑P(O∣Q,μ)P(Q∣μ)=Q∑πq1bq1(O1)t=1∏T−1aqtqt\+1bqt\+1(Ot\+1)  
       上述推导方法很直接，但是面临一个很大的困难，必须穷尽所有可能的状态序列，如果模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)中有N个不同的状态，观察序列的长度为T，那么将有 N T N^\{T\} NT个可能的状态序列。这样，计算量会出现指数爆炸，当T很大时，几乎不可能有效的执行这个算法。

## 二、前向算法 ##

针对穷尽算法中存在的问题，一般采用动态规划的方法来解决这一问题，使得求解问题可以在时间复杂度 O ( N 2 T ) O\\left ( N^\{2\}T \\right ) O(N2T)的范围内解决。  
       为了实现前向算法，需要定义一个前向变量 α t ( i ) \\alpha \_\{t\}\\left ( i \\right ) αt(i)。  
       **定义**：前向变量 α t ( i ) \\alpha \_\{t\}\\left ( i \\right ) αt(i)是在时间t，HMM输出了序列 O 1 O 2 O 3 . . . O t O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{t\} O1O2O3...Ot，并且位于状态 s i s\_\{i\} si的概率： α t ( i ) = P ( O 1 O 2 O 3 . . . O t , q t = s i ∣ μ ) \\alpha \_\{t\}\\left ( i \\right )=P\\left ( O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{t\},q\_\{t\}=s\_\{i\}|\\mu \\right ) αt(i)=P(O1O2O3...Ot,qt=si∣μ)  
       前向算法的主要思想是，如果可以快速计算前向变量 α t ( i ) \\alpha \_\{t\}\\left ( i \\right ) αt(i)，那么就可以根据 α t ( i ) \\alpha \_\{t\}\\left ( i \\right ) αt(i)计算出 P ( O ∣ μ ) P\\left ( O|\\mu \\right ) P(O∣μ)，因为 P ( O ∣ μ ) P\\left ( O|\\mu \\right ) P(O∣μ)是在所有状态 q T q \_\{T\} qT下观察到序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT的概率：  
 P ( O ∣ μ ) = ∑ s i P ( O 1 O 2 O 3 . . . O T , q T = s i ∣ μ ) = ∑ i = 1 N α T ( i ) P\\left ( O|\\mu \\right )=\\sum\_\{s\_\{i\}\}P\\left ( O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\},q\_\{T\}=s\_\{i\}|\\mu \\right )\\\\ =\\sum\_\{i=1\}^\{N\}\\alpha \_\{T\}\\left ( i \\right ) P(O∣μ)=si∑P(O1O2O3...OT,qT=si∣μ)=i=1∑NαT(i)  
       在前向算法中，采用动态规划方法计算前向变量 α t ( i ) \\alpha \_\{t\}\\left ( i \\right ) αt(i)，其实现思想基于如下观察：在时间t+1的前向变量可以根据在时间t时的前向变量 α t ( 1 ) \\alpha \_\{t\}\\left ( 1 \\right ) αt(1)， α t ( 2 ) \\alpha \_\{t\}\\left ( 2 \\right ) αt(2) …  α t ( N ) \\alpha \_\{t\}\\left ( N \\right ) αt(N)的值来归纳计算：  
 α t + 1 ( j ) = ( ∑ i = 1 N α t ( i ) a i j ) b j ( O t + 1 ) \\alpha \_\{t+1\}\\left ( j \\right )=\\left ( \\sum\_\{i=1\}^\{N\}\\alpha \_\{t\}\\left ( i \\right )a\_\{ij\} \\right )b\_\{j\}\\left ( O\_\{t+1\} \\right ) αt\+1(j)=(i=1∑Nαt(i)aij)bj(Ot\+1)  
       如下图所示， α t + 1 ( j ) \\alpha \_\{t+1\}\\left ( j \\right ) αt\+1(j)存放在 ( s j , t + 1 ) \\left ( s\_\{j\},t+1 \\right ) (sj,t\+1)处的结点上，表示在已知观察序列 O = O 1 O 2 O 3 . . . O t O t + 1 O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{t\}O\_\{t+1\} O=O1O2O3...OtOt\+1的情况下，从时间t到下一个时间t+1的时状态为 s j s\_\{j\} sj的概率。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdodWliaWFu_size_16_color_FFFFFF_t_70]  
       从初始时间开始到t+1，HMM到状态 s j s\_\{j\} sj，并且输出观察序列 O 1 O 2 O 3 . . . O t + 1 O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{t+1\} O1O2O3...Ot\+1的过程可以分解为以下两个步骤：  
（1）从初始时间到时间t，HMM到达状态 s i s\_\{i\} si，并输出观察序列 O 1 O 2 O 3 . . . O t O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{t\} O1O2O3...Ot；  
（2）从状态 s i s\_\{i\} si转移到状态 s j s\_\{j\} sj，并在状态 s j s\_\{j\} sj输出 O t + 1 O\_\{t+1\} Ot\+1。  
       这里 s i s\_\{i\} si可以是HMM的任意状态。根据前向变量 α t ( i ) \\alpha \_\{t\}\\left ( i\\right ) αt(i)的定义，从一个状态 s i s\_\{i\} si出发完成第一步的概率就是 α t ( i ) \\alpha \_\{t\}\\left ( i\\right ) αt(i)，而实现第二步的概率为 a i j b j ( O t + 1 ) a\_\{ij\} b\_\{j\}\\left ( O\_\{t+1\} \\right ) aijbj(Ot\+1)。因此，从初始时间到t+1整个过程的概率是 α t ( i ) × a i j × b j ( O t + 1 ) \\alpha \_\{t\}\\left ( i\\right )\\times a\_\{ij\} \\times b\_\{j\}\\left ( O\_\{t+1\} \\right ) αt(i)×aij×bj(Ot\+1)。由于HMM可以从不同的 s i s\_\{i\} si转移到 s j s\_\{j\} sj，总共有N个不同的状态，因此可以得到： α t + 1 ( j ) = ( ∑ i = 1 N α t ( i ) a i j ) b j ( O t + 1 ) \\alpha \_\{t+1\}\\left ( j \\right )=\\left ( \\sum\_\{i=1\}^\{N\}\\alpha \_\{t\}\\left ( i \\right )a\_\{ij\} \\right )b\_\{j\}\\left ( O\_\{t+1\} \\right ) αt\+1(j)=(i=1∑Nαt(i)aij)bj(Ot\+1)  
       **前向算法过程**：  
输入：HMM模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)，观察序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT  
输出： P ( O ∣ μ ) P\\left ( O|\\mu \\right ) P(O∣μ)  
过程：  
（1）初始化： α 1 ( i ) = π i b i ( O 1 ) , 1 ≤ i ≤ N \\alpha \_\{1\}\\left ( i\\right )=\\pi \_\{i\}b\_\{i\}\\left ( O\_\{1\} \\right ),1\\leq i\\leq N α1(i)=πibi(O1),1≤i≤N  
（2）归纳计算：  
 α t + 1 ( j ) = ( ∑ i = 1 N α t ( i ) a i j ) b j ( O t + 1 ) , 1 ≤ t ≤ T − 1 \\alpha \_\{t+1\}\\left ( j \\right )=\\left ( \\sum\_\{i=1\}^\{N\}\\alpha \_\{t\}\\left ( i \\right )a\_\{ij\} \\right )b\_\{j\}\\left ( O\_\{t+1\} \\right ),1\\leq t\\leq T-1 αt\+1(j)=(i=1∑Nαt(i)aij)bj(Ot\+1),1≤t≤T−1  
（3）求和总结：  
 P ( O ∣ μ ) = ∑ i = 1 N α T ( i ) P\\left ( O|\\mu \\right )=\\sum\_\{i=1\}^\{N\}\\alpha \_\{T\}\\left ( i \\right ) P(O∣μ)=i=1∑NαT(i)  
       在初始化步骤中， π i \\pi \_\{i\} πi是初始状态 s i s \_\{i\} si的概率， b i ( O 1 ) b\_\{i\}\\left ( O\_\{1\} \\right ) bi(O1)是在 s i s \_\{i\} si状态输出 O 1 O\_\{1\} O1的概率，那么 π i b i ( O 1 ) \\pi \_\{i\}b\_\{i\}\\left ( O\_\{1\} \\right ) πibi(O1)就是在时间t=1时，HMM在 s i s \_\{i\} si状态输出序列 O 1 O\_\{1\} O1的概率，即前向变量 α 1 ( i ) \\alpha \_\{1\}\\left ( i\\right ) α1(i)。一共有N个状态，因此需要初始化N个前向变量 α 1 ( 1 ) , α 1 ( 2 ) . . . α 1 ( N ) \\alpha \_\{1\}\\left ( 1\\right ),\\alpha \_\{1\}\\left ( 2\\right )...\\alpha \_\{1\}\\left ( N\\right ) α1(1),α1(2)...α1(N)。

## 三、后向算法 ##

同时，我们还可以采用后向算法的方法来解决估计问题。为了实现后向算法，需要定义一个后向变量 β t ( i ) \\beta \_\{t\}\\left ( i \\right ) βt(i)。  
       **定义**：后向变量 β t ( i ) \\beta \_\{t\}\\left ( i \\right ) βt(i)是在给定模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)，并且在时间t状态为 s i s\_\{i\} si的条件下，HMM输出观察序列 O t + 1 O t + 2 . . . O T O\_\{t+1\}O\_\{t+2\}...O\_\{T\} Ot\+1Ot\+2...OT的概率： β t ( i ) = P ( O t + 1 O t + 2 . . . O T ∣ q t = s i , μ ) \\beta \_\{t\}\\left ( i \\right )=P\\left ( O\_\{t+1\}O\_\{t+2\}...O\_\{T\}|q\_\{t\}=s\_\{i\},\\mu \\right ) βt(i)=P(Ot\+1Ot\+2...OT∣qt=si,μ)  
       与计算前向变量的思路一致，可以用动态规划的方法计算后向变量。类似地，在时间t状态为 s i s\_\{i\} si的条件下，HMM输出观察序列 O t + 1 O t + 2 . . . O T O\_\{t+1\}O\_\{t+2\}...O\_\{T\} Ot\+1Ot\+2...OT的过程可以分解为以下两个步骤：  
（1）从时间t到时间t+1，HMM由状态 s i s\_\{i\} si到状态 s j s\_\{j\} sj，并从状态 s j s\_\{j\} sj输出 O t + 1 O\_\{t+1\} Ot\+1；  
（2）在时间t+1的状态为 s j s\_\{j\} sj的条件下，HMM输出观察序列 O t + 2 . . . O T O\_\{t+2\}...O\_\{T\} Ot\+2...OT；  
       第一步中输出 O t + 1 O\_\{t+1\} Ot\+1的概率是： a i j b j ( O t + 1 ) a\_\{ij\} b\_\{j\}\\left ( O\_\{t+1\} \\right ) aijbj(Ot\+1)；第二步中根据后向变量的定义，HMM输出观察序列 O t + 2 . . . O T O\_\{t+2\}...O\_\{T\} Ot\+2...OT的概率就是 β t + 1 ( j ) \\beta \_\{t+1\}\\left ( j \\right ) βt\+1(j)。于是，得到如下归纳关系： β t ( i ) = ∑ j = 1 N a i j b j ( O t + 1 ) β t + 1 ( j ) \\beta \_\{t\}\\left ( i \\right )= \\sum\_\{j=1\}^\{N\}a\_\{ij\} b\_\{j\}\\left ( O\_\{t+1\} \\right )\\beta \_\{t+1\}\\left ( j \\right ) βt(i)=j=1∑Naijbj(Ot\+1)βt\+1(j)  
其归纳关系如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdodWliaWFu_size_16_color_FFFFFF_t_70 1]  
       **后向算法过程**：  
输入：HMM模型 μ = ( S , K , A , B , π ) \\mu =\\left ( S,K,A,B,\\pi \\right ) μ=(S,K,A,B,π)，观察序列 O = O 1 O 2 O 3 . . . O T O=O\_\{1\}O\_\{2\}O\_\{3\}...O\_\{T\} O=O1O2O3...OT  
输出： P ( O ∣ μ ) P\\left ( O|\\mu \\right ) P(O∣μ)  
过程：  
（1）初始化： β T ( i ) = 1 , 1 ≤ i ≤ N \\beta \_\{T\}\\left ( i\\right )=1,1\\leq i\\leq N βT(i)=1,1≤i≤N  
（2）归纳计算：  
 β t ( i ) = ∑ j = 1 N a i j b j ( O t + 1 ) β t + 1 ( j ) , 1 ≤ t ≤ T − 1 , 1 ≤ i ≤ N \\beta \_\{t\}\\left ( i \\right )= \\sum\_\{j=1\}^\{N\}a\_\{ij\} b\_\{j\}\\left ( O\_\{t+1\} \\right )\\beta \_\{t+1\}\\left ( j \\right ),1\\leq t\\leq T-1,1\\leq i\\leq N βt(i)=j=1∑Naijbj(Ot\+1)βt\+1(j),1≤t≤T−1,1≤i≤N  
（3）求和总结：  
 P ( O ∣ μ ) = ∑ i = 1 N π i b i ( O 1 ) β 1 ( i ) P\\left ( O|\\mu \\right )=\\sum\_\{i=1\}^\{N\}\\pi \_\{i\}b\_\{i\}\\left ( O\_\{1\} \\right )\\beta \_\{1\}\\left ( i \\right ) P(O∣μ)=i=1∑Nπibi(O1)β1(i)

## 三、前向后向相结合的算法 ##

更一般地，我们可以采用前向后向算法结合的方法来计算观察序列的概率。  
 P ( O , q t = s i ∣ μ ) = P ( O 1 . . . O T , q t = s i ∣ μ ) = P ( O 1 . . . O t , q t = s i , O t + 1 . . . O T ∣ μ ) = P ( O 1 . . . O t , q t = s i ∣ μ ) × P ( O t + 1 . . . O T ∣ O 1 . . . O t + 1 , q t = s i , μ ) = P ( O 1 . . . O t , q t = s i ∣ μ ) × P ( O t + 1 . . . O T ∣ q t + 1 = s i , μ ) = α t ( i ) β t ( i ) P\\left ( O,q\_\{t\}=s\_\{i\}|\\mu \\right )=P\\left ( O\_\{1\}...O\_\{T\},q\_\{t\}=s\_\{i\}|\\mu \\right )\\\\ =P\\left ( O\_\{1\}...O\_\{t\},q\_\{t\}=s\_\{i\},O\_\{t+1\}...O\_\{T\}|\\mu \\right )\\\\ =P\\left ( O\_\{1\}...O\_\{t\},q\_\{t\}=s\_\{i\}|\\mu \\right )\\times P\\left (O\_\{t+1\}...O\_\{T\}| O\_\{1\}...O\_\{t+1\},q\_\{t\}=s\_\{i\},\\mu \\right )\\\\ =P\\left ( O\_\{1\}...O\_\{t\},q\_\{t\}=s\_\{i\}|\\mu \\right )\\times P\\left (O\_\{t+1\}...O\_\{T\}|q\_\{t+1\}=s\_\{i\},\\mu \\right )\\\\ =\\alpha \_\{t\}\\left ( i\\right )\\beta \_\{t\}\\left ( i\\right ) P(O,qt=si∣μ)=P(O1...OT,qt=si∣μ)=P(O1...Ot,qt=si,Ot\+1...OT∣μ)=P(O1...Ot,qt=si∣μ)×P(Ot\+1...OT∣O1...Ot\+1,qt=si,μ)=P(O1...Ot,qt=si∣μ)×P(Ot\+1...OT∣qt\+1=si,μ)=αt(i)βt(i)  
因此 P ( O ∣ μ ) = ∑ i = 1 N α t ( i ) β t ( i ) , 1 ≤ t ≤ T P\\left ( O|\\mu \\right )=\\sum\_\{i=1\}^\{N\}\\alpha \_\{t\}\\left ( i\\right )\\beta \_\{t\}\\left ( i\\right ),1\\leq t\\leq T P(O∣μ)=i=1∑Nαt(i)βt(i),1≤t≤T

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdodWliaWFu_size_16_color_FFFFFF_t_70]: /images/20220123/a41c95addd494308bb5c1da8b18893e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlbmdodWliaWFu_size_16_color_FFFFFF_t_70 1]: /images/20220123/c99945e047994065a53cd1b13d59b0ac.png