隐马尔科夫模型HMM（三） -- 序列问题

小鱼儿 2022-01-20 23:59 252阅读 0赞

接下来，我们研究第二个问题，序列问题。也即是给定一个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，如何快速有效地选择在一定意义下“最优”的状态序列 Q = q 1 q 2 q 3 . . . q T Q=q\_\{1\}q\_\{2\}q\_\{3\}...q\_\{T\} Q=q1q2q3...qT，使得该状态序列“最好的解释”观察序列，也即是 P ( Q ∣ μ , O ) P\\left ( Q|\\mu,O \\right ) P(Q∣μ,O)最大？

## 第一种理解 ##

为了得到“最优”的状态序列，只需要使得该序列中的每一个状态都单独地具有最大概率，即要使得 γ t ( i ) = P ( q t = s i ∣ μ , O ) \\gamma \_\{t\}(i)=P\\left ( q\_\{t\}=s\_\{i\}|\\mu,O \\right ) γt(i)=P(qt=si∣μ,O)最大。  
       根据贝叶斯公式，有 γ t ( i ) = P ( q t = s i ∣ μ , O ) = P ( q t = s i , O ∣ μ ) P ( O ∣ μ ) \\gamma \_\{t\}(i)=P\\left ( q\_\{t\}=s\_\{i\}|\\mu,O \\right )\\\\=\\frac\{P\\left ( q\_\{t\}=s\_\{i\},O|\\mu \\right )\}\{P(O|\\mu)\} γt(i)=P(qt=si∣μ,O)=P(O∣μ)P(qt=si,O∣μ)，  
       参考上节的公式 P ( O , q t = s i ∣ μ ) = α t ( i ) β t ( i ) P\\left ( O,q\_\{t\}=s\_\{i\}|\\mu \\right )=\\alpha \_\{t\}\\left ( i\\right )\\beta \_\{t\}\\left ( i\\right ) P(O,qt=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  
因此有 γ t ( i ) = α t ( i ) β t ( i ) ∑ i = 1 N α t ( i ) β t ( i ) \\gamma \_\{t\}(i)=\\frac\{\\alpha \_\{t\}\\left ( i\\right )\\beta \_\{t\}\\left ( i\\right )\}\{\\sum\_\{i=1\}^\{N\}\\alpha \_\{t\}\\left ( i\\right )\\beta \_\{t\}\\left ( i\\right )\} γt(i)=∑i=1Nαt(i)βt(i)αt(i)βt(i)  
       因此，在时间t的最优状态是 q t ^ = a r g m a x 1 ≤ i ≤ N \[ γ t ( i ) \] \\hat\{q\_\{t\}\}=argmax\_\{1\\leq i\\leq N\}\[\\gamma \_\{t\}(i)\] qt^=argmax1≤i≤N\[γt(i)\]  
       由于这里只考虑使每个状态的出现都单独达到最大概率，而忽略了状态序列中两个状态之间的关系，很可能导致两个状态 q t ^ \\hat\{q\_\{t\}\} qt^和 q t + 1 ^ \\hat\{q\_\{t+1\}\} qt\+1^之间的转移概率为0，即 a q t ^ q t + 1 ^ = 0 a\\hat\{q\_\{t\}\}\\hat\{q\_\{t+1\}\}=0 aqt^qt\+1^=0。那么，在这种情况下，所谓的“最优”状态序列根本不是合法的序列。因此，这种方法不可行。

## 维特比算法 ##

维特比算法用于求解HMM中的第二个问题，也即是序列问题。维特比算法运用动态规划的搜索算法求解这种“最优”状态序列。为了实现这种搜索，首先定义一个维特比变量 δ t ( i ) \\delta \_\{t\}(i) δt(i)。  
       **定义**：维特比变量 δ t ( i ) \\delta \_\{t\}(i) δt(i)是在时间t时，HMM沿着某一条路径到达状态 s i s\_\{i\} si，并输出观察序列 O 1 O 2 . . . O t O\_\{1\}O\_\{2\}...O\_\{t\} O1O2...Ot的最大概率：  
 δ t ( i ) = m a x q 1 , q 2 , . . . , q t − 1 P （ q 1 , q 2 , . . . , q t = s i , O 1 O 2 . . . O t ∣ μ ） \\delta \_\{t\}(i)=max\_\{q\_\{1\},q\_\{2\},...,q\_\{t-1\}\}P（q\_\{1\},q\_\{2\},...,q\_\{t\}=s\_\{i\},O\_\{1\}O\_\{2\}...O\_\{t\}|\\mu ） δt(i)=maxq1,q2,...,qt−1P（q1,q2,...,qt=si,O1O2...Ot∣μ）  
则， δ t + 1 ( i ) = m a x j \[ δ t ( j ) ∗ a j i \] ∗ b i ( O t + 1 ) \\delta \_\{t+1\}(i)=max\_\{j\}\[\\delta \_\{t\}(j)\*a\_\{ji\}\]\*b\_\{i\}(O\_\{t+1\}) δt\+1(i)=maxj\[δt(j)∗aji\]∗bi(Ot\+1)  
       这种递归关系使我们能够运用动态规划搜索技术。为了记录在时间t时，HMM通过一条概率最大的路径到达状态 s i s\_\{i\} si，维特比算法设置了另外一个变量 φ t ( i ) \\varphi \_\{t\}(i) φt(i)用于路径记忆，让 φ t ( i ) \\varphi \_\{t\}(i) φt(i)记录该路径上状态 s i s\_\{i\} si的前一个（在时间t-1）状态。根据这种思路，给出**维特比算法**如下：  
（1）初始化：  
 δ 1 （ i ） = π i b i ( O 1 ) , 1 ≤ i ≤ N φ 1 ( i ) = 0 \\delta \_\{1\}（i）=\\pi \_\{i\}b\_\{i\}(O\_\{1\}),1\\leq i\\leq N\\\\\\varphi \_\{1\}(i)=0 δ1（i）=πibi(O1),1≤i≤Nφ1(i)=0  
（2）归纳计算：  
 δ t （ j ） = m a x 1 ≤ i ≤ N \[ δ t − 1 ( i ) ∗ a i j \] ∗ b j ( O t ) , 2 ≤ t ≤ T ; 1 ≤ j ≤ N \\delta \_\{t\}（j）=max\_\{1\\leq i\\leq N\}\[\\delta \_\{t-1\}(i)\*a\_\{ij\}\]\*b\_\{j\}(O\_\{t\}),2\\leq t\\leq T;1\\leq j\\leq N δt（j）=max1≤i≤N\[δt−1(i)∗aij\]∗bj(Ot),2≤t≤T;1≤j≤N  
记忆回退路径：  
 φ t （ j ） = a r g m a x 1 ≤ i ≤ N \[ δ t − 1 ( i ) ∗ a i j \] ∗ b j ( O t ) , 2 ≤ t ≤ T ; 1 ≤ j ≤ N \\varphi \_\{t\}（j）=argmax\_\{1\\leq i\\leq N\}\[\\delta \_\{t-1\}(i)\*a\_\{ij\}\]\*b\_\{j\}(O\_\{t\}),2\\leq t\\leq T;1\\leq j\\leq N φt（j）=argmax1≤i≤N\[δt−1(i)∗aij\]∗bj(Ot),2≤t≤T;1≤j≤N  
（3）终结：  
 Q T ^ = a r g m a x 1 ≤ i ≤ N \[ δ T （ i ） \] \\hat\{Q\_\{T\}\}=argmax\_\{1\\leq i\\leq N\}\[\\delta \_\{T\}（i）\] QT^=argmax1≤i≤N\[δT（i）\]  
 P ( Q T ^ ) ^ = m a x 1 ≤ i ≤ N \[ δ T （ i ） \] \\hat\{P(\\hat\{Q\_\{T\}\})\}=max\_\{1\\leq i\\leq N\}\[\\delta \_\{T\}（i）\] P(QT^)^=max1≤i≤N\[δT（i）\]  
（4）路径（状态序列）回溯：  
 q t ^ = φ t + 1 （ q t + 1 ^ ） , t = T − 1 , T − 2 , . . . , 1 \\hat\{q\_\{t\}\}=\\varphi \_\{t+1\}（\\hat\{q\_\{t+1\}\}）,t=T-1,T-2,...,1 qt^=φt\+1（qt\+1^）,t=T−1,T−2,...,1  
       维特比算法的时间复杂性与前向算法、后向算法的时间复杂度一样，也是 O ( N 2 T ) O(N^\{2\}T) O(N2T)。