隐马尔可夫模型 Hidden Markov Model
问题定义
对于HMM模型的解码问题，即给定模型 \(\lambda=(A,B,\Pi)\) 和观测序列 \(O=\{o_1,o_2,..o_t\}\),求最有可能出现的对应的状态序列。
对于这样的问题，当然也可以穷举，但是效率太差这里不做讨论。对于求最优解的问题，很容易想到贪心和动态规划，对于全局最优解的问题，动态规划算法要更加靠谱。这里我们使用维特比算法来解码HMM的最有可能的隐藏状态序列。
维特比算法（Viterbi Algorithmn）是基于动态规划+回溯法来进行的。
解决方案
Viterbi Algorithmn 定义了两个局部状态进行记录。
第一个局部状态是在时刻t隐藏状态为qi,所有可能的转移路径中的概率最大值，记为 \(\delta_t(q_i)\)
\[\delta_t(q_i)={max}_{i_1,i_2,...,i_t}P(i_t=q_i,i_1,i_2,...,i_t,o_1,o_2,...o_t|\lambda)\]可得当时刻t+1时，隐藏状态为qj, 时的概率最大值
\(\delta_{t+1}(q_j)={max}_{i=1}^N[\delta_t(q_i)a_{ij}]b_{q_j}(o_{t+1})\) 若隐藏状态用 \(i_j\)表示，更广义的递推式如下 \(\delta_{t+1}(i_j)={max}_{i=1}^N[\delta_t(i_i)a_{ij}]b_{i_j}(o_{t+1})\)
第二个局部状态由第一个局部状态递推得到，定义t时刻的隐藏状态为i的所有的单个状态转移路径\((i_1,i_2,...i_{t-1},i)\)中概率最大的转移路径中第t-1个节点的隐藏状态\(\Psi_t(i)\)，,递推式为:
\(\Phi_t(i)= arg \ \ \ max_{j=1}^N[\delta_{t-1}(j)a_{ji}]\) 定义了这两个局部状态进行递推。
Summary
输入： HMM模型 \(\lambda=(A,B,\Pi)\)，观测序列\(O=\{o_1,o_2,..o_t\}\)
输出：概率最大隐藏序列 \(I={i_1^*,i_2^*,...,i_t^*}\)
-
初始化局部状态 t=1 时
\[\delta_{1}(i)=\pi_ib_i(o1),\ \ i=1,2,...,N\] \[\Psi_1(i)=0,\ \ \ i=1,2,...,N\] -
进行动态规划递时刻 t=2,3,…,T 时刻的局部状态:
\[\delta_{t}(i)={max}_{i=1}^N[\delta_{t-1}(j)a_{ji}]b_{i}(o_{t}) \ \ \ i=1,2,...,N\]
-
当t=T时，选择最大的\(\delta_t(i)\),此时
\[i_T^*=i\] -
利用局部状态 \(\Psi(i)\)快开始回溯。对于t=T-1,…,2,1:
\[i_i^*=\Psi_{t+1}(i_{t+1}^*)\] -
最终得到\(I^*=\{i_1^*,i_2^*,...,i_T^*\}\)
Example
同样观测序列\(O=\{Clean, Walk,Shop\}\)
按照算法流程
t=1时
\[\delta_1(sunny)=\pi_{sunny}*b_{s}(Clean)=0.4*0.1=0.04\] \[\delta_1(rainy)=\pi_{rainy}*b_{r}(Clean)=0.6*0.5=0.2\] \[\Psi_1(sunny)=0 \ \ \ \Psi_1(rainy)=0\]t=2时
\[\delta_2(sunny)=max\{\delta_1(sunny)*a_{s-s},\delta_1(rainy)*a_{r-s} \}*b_s(Walk)\] \[\delta_2(sunny)=max\{0.04*0.6,0.2*0.3 \}*0.6=0.036\] \[\delta_2(rainy)=max\{\delta_1(sunny)*a_{s-r},\delta_1(rainy)*a_{r-r} \}*b_r(Walk)\] \[\delta_2(rainy)=max\{0.04*0.4,,0.2*0.7 \}*0.1=0.014\] \[\Psi_2(sunny)=argmax(\delta_1(sunny)*a_{s-s},\delta_1(rainy)*a_{r-s})\] \[\Psi_2(sunny)=argmax(0.024,0.06)=rainy\] \[\Psi_2(rainy)=argmax\{\delta_1(sunny)*a_{s-r},\delta_1(rainy)*a_{r-r} \}\] \[\Psi_2(rainy)=argmax\{0.04*0.4,,0.2*0.7 \}=rainy\]t=3时，同t=2
\[\delta_3(sunny)=max\{\delta_2(sunny)*a_{s-s},\delta_2(rainy)*a_{r-s} \}*b_s(Shop)\] \[\delta_3(sunny)=max\{0.036*0.6,0.014*0.3 \}*0.3=0.00648\] \[\delta_3(rainy)=max\{\delta_2(sunny)*a_{s-r},\delta_2(rainy)*a_{r-r} \}*b_r(Shop)\] \[\delta_3(rainy)=max\{0.036*0.4,0.014*0.7 \}*0.4=0.00572\] \[\Psi_3(sunny)=argmax(\delta_2(sunny)*a_{s-s},\delta_2(rainy)*a_{r-s})\] \[\Psi_3(sunny)==argmax(0.0216,0.0042)=sunny\] \[\Psi_3(rainy)=argmax\{\delta_2(sunny)*a_{s-r},\delta_2(rainy)*a_{r-r} \}\] \[\Psi_3(rainy)=argmax\{0.0098,,0.0144\}=rainy\]当t=3时，可以看到 \(\delta_3(sunny)\)最大，因此
\[i_{3}^*=sunny\]通过\(\Psi_t(i)\)进行回溯 \([rainy,sunny,sunny]\)
知乎上答题人应该算错了 QAQ，
对自己的答案绝对自信 ORZ
