隐马尔可夫模型 Hidden Markov Model
问题定义
| 评估观测序列概率，即给定模型 \(\lambda=(A,B,\Pi)\) 和观测序列 \(O=\{o_1,o_2,..o_t\}\),计算在模型下观测序列出现的概率$$P(O | \lambda)$$ |
解决方案
以继续以上文天气作为例子
穷举法
穷举出所有可能出现该观测序列的隐藏序列，然后计算他们的概率求和。
若三天的观测序列\(O=\{Clean, Walk,Shop\}\)，则可能出现的隐藏序列，每天两种可能天气，则一共\(2^3=8\)种隐藏序列
\[I_1=\{Sunny,Sunny,Sunny\} \\ I_2=\{Sunny,Sunny,Rainy\} \\ . \\. \\. \\ I_8 =\{Rainy,Rainy,Rainy\}\]选取\(I_1\)计算概率
\[P(O,I_1|\lambda)=\Pi_{Sunny}*B_{s-clean}*A_{s-s}*B_{s-walk}*A_{s-s}*B_{s-shop}\] \[P(O,I_1|\lambda)=0.4 *0.1*0.6*0.6*0.6*0.3=0.002592\] \[P(O|\lambda)=\sum_i^{N^T}P(O,I_i|\lambda)\]分析复杂度 \(TN^T\)
显然这个复杂度是一个随着观测序列子数级增长的。
为了解决这个问题前向后向算法被提出。
Forward Algorithm (前向算法)
前向算法本质上属于动态规划算法，找到局部状态的递推式，从子问题来一步步得到整个问题的解。
我们定义前向概率来定义动态规划的局部状态。前向概率：定义时刻t时隐藏状态为\(q_i\),观测状态的序列为\(o_1,o_2,...o_t\)的概念为前向概率。
\[\alpha_t(i)=P(o_1,o_2,...o_t,i_t=q_i|\lambda)\]现在我们要递推出t+1时各个隐藏状态的前向概率。
若时刻t+1隐藏状态 \(q_j\),则到达该隐藏状态的概率，为t时刻所有可能隐藏状态转换到\(q_j\)的概率之和,
\[\sum_i^N\alpha_t(i)a_{ij}\]若t+1时刻的观测状态为\(o_{t+1}\)，则t+1时刻生成概率为\(b_j(o_{t+1})\),前向概率为
\[\alpha_{t+1}(j)=[\sum_{i=1}^N\alpha_t(i)a_{ij}]b_j(o_{t+1})\]从时刻t=1开始，到时刻$T$结束，当到达时刻T时，我们会得到所有可能隐藏状态的前向概率，我们只需要将所有隐藏状态的概率相加，即\(\sum_{i=1}^N\alpha_T(i)\)就得到了观测序列所对应的最大概率。
Summary
输入： HMM模型 \(\lambda=(A,B,\Pi)\)，观测序列\(O=\{o_1,o_2,..o_t\}\)
| 输出：观测序列的概率$$P(O | \lambda)$$ |
-
计算时刻1各个隐藏状态的初始前向概率：
\[\alpha_1(i)=\pi_ib_i(o_1) \ \ \ i=1,2,...,N\] -
递推2，3，…,T时刻的前向概率:
\[\alpha_{t+1}(j)=[\sum_{i=1}^N\alpha_t(i)a_{ij}]b_j(o_{t+1}) \ \ \ i=1,2,...,N\] -
计算最终结果
\[P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)\]
复杂度分析\(O(TN^2)\)
Example
同样观测序列\(O=\{Clean, Walk,Shop\}\)
按照算法流程
当t=1时 \(\alpha_1(sunny)=\pi_{sunny}*b_{sunny}(clean)=0.4*0.1=0.04\)
\[\alpha_1(rainy)=\pi_{rainy}*b_{sunny}(clean)=0.6*0.5=0.3\]当t=2时 \(\alpha_2(sunny)=(\alpha_1(sunny)*a_{s-s}*+\alpha_1(rainy)*a_{r-s})*b_{sunny}(walk)\)
\[\alpha_2(sunny)=(0.04*0.6+0.3*0.3)*0.6=0.0684\] \[\alpha_2(rainy)=(\alpha_1(sunny)*a_{s-r}+\alpha_1(rainy)*a_{r-r})*b_{rainy}(walk)\] \[\alpha_2(rainy)=(0.04*0.4+0.3*0.7)*0.1=0.0226\]当t=3时 \(\alpha_3(sunny)=(\alpha_2(sunny)*a_{s-s}*+\alpha_2(rainy)*a_{r-s})*b_{sunny}(shop)\)
\[\alpha_3(sunny)=(0.0684*0.6+0.0226*0.3)*0.3=0.014346\] \[\alpha_3(rainy)=(\alpha_2(sunny)*a_{s-r}+\alpha_2(rainy)*a_{r-r})*b_{rainy}(shop)\] \[\alpha_3(rainy)=(0.0684*0.4+0.0226*0.7)*0.4=0.017272\]计算最终结果
\[P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)=\alpha_3(rainy)+\alpha_3(sunny)=0.031618\]Backward Algorithm (后向算法)
Note:
个人感觉对于解决HMM提出的第一个问题，Forward Algorithm已经够用了。
后向算法的提出和算法的假设，我一直不太能确定该算法对应到确定的物理场景，但是计算结果和前向算法相同。
后向算法
定义时刻t时，隐藏状态为\(q_i\),从时刻t+1到最后时刻T的观测状态的序列\(o_{t+1},o_{t+2},...o_{T}\)的概率为后向概率，记为
\[\beta_t(i)=P(o_{t+1},o_{t+2},...o_T|i_t=q_i,\lambda)\]| 设我们现在已经知道了t+1时刻的后向概率$$\beta_{t+1}(j)=P(o_{t+2},o_{t+3},…o_T | i_t=q_i,\lambda)\(,当t时刻隐藏状态为$q_i$,t+1时刻隐藏状态为$q_j$概率\)\beta_{t+1}(j)*a_{ij}\(，考虑到此时观测序列为\)o_{t+1}\( 因此后向概率还需要乘上一个生成概率\)b_{j}(o_{t+1})\(，t+1时刻的隐藏状态可能为N种，所以t时刻，隐藏状态为\)q_i$$的后向概率为 |
上式为后向算法递推式。
Summary
输入： HMM模型 \(\lambda=(A,B,\Pi)\)，观测序列\(O=\{o_1,o_2,..o_t\}\)
| 输出：观测序列的概率$$P(O | \lambda)$$ |
-
初始化时刻T各个隐藏状态的后向概率：（都为1，虽然我没太懂）
\[\beta_T(i)=1,\ \ \ i=1,2,...,N\] -
递推T-1，T-2，…,1时刻的后向概率:
\[\beta_t(i)=\sum_{j=1}^N\beta_{t+1}(j)*\alpha_{ij}*b_j(o_{t+1})\] -
计算最终结果,最终结果相乘的事初始状态分布概率
\[P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o1)\beta_1(i)\]
复杂度分析\(O(TN^2)\)
Example
同样观测序列\(O=\{Clean, Walk,Shop\}\)
当t=3时，后向概率初始化为1
\[\beta_T(i)=1,\ \ \ i=sunny,rainy\]当t=2时：
\[\beta_2(sunny)=\beta_3(sunny)*a_{s-s}*b_s(Shop)+\beta_3(rainy)*a_{s-r}*b_r(Shop)\] \[\beta_2(sunny)=1*0.6*0.3+1*0.4*0.4=0.34\] \[\beta_2(rainy)=\beta_3(sunny)*a_{r-s}*b_s(Shop)+\beta_3(rainy)*a_{r-r}*b_r(Shop)\] \[\beta_2(rainy)=1*0.3*0.3+1*0.7*0.4=0.37\]当t=1时
\[\beta_1(sunny)=\beta_2(sunny)*a_{s-s}*b_s(Walk)+\beta_2(rainy)*a_{s-r}*b_r(Walk)\] \[\beta_1(sunny)=0.34*0.6*0.6+0.37*0.4*0.1=0.1372\] \[\beta_1(rainy)=\beta_2(sunny)*a_{r-s}*b_s(Walk)+\beta_2(rainy)*a_{r-r}*b_r(Walk)\] \[\beta_1(rainy)=0.34*0.3*0.6+0.37*0.7*0.1=0.0871\]计算最终结果，
\[P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o1)\beta_1(i)\] \[P(O|\lambda)=\pi_{sunny}*b_s(Clean)*\beta_1(sunny)+\pi_{rainy}*b_r(Clean)*\beta_1(rainy)\] \[P(O|\lambda)=0.4*0.1*0.1372+0.6*0.5*0.0871=0.031618\]我们发现，唉好神奇，居然和前向算法算出来相同。。。。。
虽然我还是觉得很难理解后向算法的递推公式的细节
