# 隐马尔科夫模型HMM（二）前向后向算法评估观察序列概率

+关注继续查看

在隐马尔科夫模型HMM（一）HMM模型中，我们讲到了HMM模型的基础知识和HMM的三个基本问题，本篇我们就关注于HMM第一个基本问题的解决方法，即已知模型和观测序列，求观测序列出现的概率。
1. 回顾HMM问题一：求观测序列的概率

$$P(I|\lambda) = \pi_{i_1} a_{i_1i_2} a_{i_2i_3}... a_{i_{T-1}\;\;i_T}$$

$$P(O|I, \lambda) = b_{i_1}(o_1)b_{i_2}(o_2)...b_{i_T}(o_T)$$

$$P(O,I|\lambda) = P(I|\lambda)P(O|I, \lambda) = \pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}\;\;i_T}b_{i_T}(o_T)$$

$$P(O|\lambda) = \sum\limits_{I}P(O,I|\lambda) = \sum\limits_{i_1,i_2,...i_T}\pi_{i_1}b_{i_1}(o_1)a_{i_1i_2}b_{i_2}(o_2)...a_{i_{T-1}\;\;i_T}b_{i_T}(o_T)$$

2. 用前向算法求HMM观测序列的概率

$$\alpha_t(i) = P(o_1,o_2,...o_t, i_t =q_i | \lambda)$$

$$\alpha_{t+1}(i) = \Big[\sum\limits_{j=1}^N\alpha_t(j)a_{ji}\Big]b_i(o_{t+1})$$

1. 计算时刻1的各个隐藏状态前向概率：

$$\alpha_1(i) = \pi_ib_i(o_1),\; i=1,2,...N$$

1. 递推时刻$2,3,...T$时刻的前向概率：

$$\alpha_{t+1}(i) = \Big[\sum\limits_{j=1}^N\alpha_t(j)a_{ji}\Big]b_i(o_{t+1}),\; i=1,2,...N$$

1. 计算最终结果：

$$P(O|\lambda) = \sum\limits_{i=1}^N\alpha_T(i)$$

3. HMM前向算法求解实例

$$V=\{红，白\}，M=2$$

$$Q =\{盒子1，盒子2，盒子3\}， N=3$$

$$\Pi = (0.2,0.4,0.4)^T$$

$$A = \left( \begin{array} {ccc} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 &0.5 \end{array} \right)$$

$$B = \left( \begin{array} {ccc} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{array} \right)$$

$$O=\{红，白，红\}$$

$$\alpha_1(1) = \pi_1b_1(o_1) = 0.2 \times 0.5 = 0.1$$

$$\alpha_1(2) = \pi_2b_2(o_1) = 0.4 \times 0.4 = 0.16$$

$$\alpha_1(3) = \pi_3b_3(o_1) = 0.4 \times 0.7 = 0.28$$

$$\alpha_2(1) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i1}\Big]b_1(o_2) = [0.1*0.5+0.16*0.3+0.28*0.2 ] \times 0.5 = 0.077$$

$$\alpha_2(2) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i2}\Big]b_2(o_2) = [0.1*0.2+0.16*0.5+0.28*0.3 ] \times 0.6 = 0.1104$$

$$\alpha_2(3) = \Big[\sum\limits_{i=1}^3\alpha_1(i)a_{i3}\Big]b_3(o_2) = [0.1*0.3+0.16*0.2+0.28*0.5 ] \times 0.3 = 0.0606$$

$$\alpha_3(1) = \Big[\sum\limits_{i=1}^3\alpha_2(i)a_{i1}\Big]b_1(o_3) = [0.077*0.5+0.1104*0.3+0.0606*0.2 ] \times 0.5 = 0.04187$$

$$\alpha_3(2) = \Big[\sum\limits_{i=1}^3\alpha_2(i)a_{i2}\Big]b_2(o_3) = [0.077*0.2+0.1104*0.5+0.0606*0.3 ] \times 0.4 = 0.03551$$

$$\alpha_3(3) = \Big[\sum\limits_{i=1}^3\alpha_3(i)a_{i3}\Big]b_3(o_3) = [0.077*0.3+0.1104*0.2+0.0606*0.5 ] \times 0.7 = 0.05284$$

$$P(O|\lambda) = \sum\limits_{i=1}^3\alpha_3(i) = 0.13022$$

4. 用后向算法求HMM观测序列的概率

$$\beta_t(i) = P(o_{t+1},o_{t+2},...o_T| i_t =q_i , \lambda)$$

$$\beta_{t}(i) = \sum\limits_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j)$$

1. 初始化时刻$T$的各个隐藏状态后向概率：

$$\beta_T(i) = 1,\; i=1,2,...N$$

1. 递推时刻$T−1,T−2,...1$时刻的后向概率：

$$\beta_{t}(i) = \sum\limits_{j=1}^{N}a_{ij}b_j(o_{t+1})\beta_{t+1}(j),\; i=1,2,...N$$

1. 计算最终结果：

$$P(O|\lambda) = \sum\limits_{i=1}^N\pi_ib_i(o_1)\beta_1(i)$$

5. HMM常用概率的计算

1. 给定模型λλ和观测序列$O$,在时刻$t$处于状态$q_i$的概率记为:

$$\gamma_t(i) = P(i_t = q_i | O,\lambda) = \frac{P(i_t = q_i ,O|\lambda)}{P(O|\lambda)}$$

$$P(i_t = q_i ,O|\lambda) = \alpha_t(i)\beta_t(i)$$

$$\gamma_t(i) = \frac{ \alpha_t(i)\beta_t(i)}{\sum\limits_{j=1}^N \alpha_t(j)\beta_t(j)}$$

1. 给定模型λλ和观测序列$O$,在时刻$t$处于状态$q_i$，且时刻$t+1$处于状态$q_j$的概率记为:

$$\xi_t(i,j) = P(i_t = q_i, i_{t+1}=q_j | O,\lambda) = \frac{ P(i_t = q_i, i_{t+1}=q_j , O|\lambda)}{P(O|\lambda)}$$

$$P(i_t = q_i, i_{t+1}=q_j , O|\lambda) = \alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)$$

$$\xi_t(i,j) = \frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum\limits_{r=1}^N\sum\limits_{s=1}^N\alpha_t(r)a_{rs}b_s(o_{t+1})\beta_{t+1}(s)}$$

1. 将$\gamma_t(i)$和$\xi_t(i,j)$在各个时刻$t$求和，可以得到：
在观测序列$O$下状态$i$出现的期望值$\sum\limits_{t=1}^T\gamma_t(i)$

MaxCompute数据仓库在更新插入、直接加载、全量历史表三大算法中的数据转换实践
2018“MaxCompute开发者交流”钉钉群直播分享，由阿里云数据技术专家彬甫带来以“MaxCompute数据仓库数据转换实践”为题的演讲。本文首先介绍了MaxCompute的数据架构和流程，其次介绍了ETL算法中的三大算法，即更新插入算法、直接加载算法、全量历史表算法，再次介绍了在OLTP系统中怎样处理NULL值，最后对ETL相关知识进行了详细地介绍。
4738 0

747 0

864 0
+关注
77

0

《2021云上架构与运维峰会演讲合集》

《零基础CSS入门教程》

《零基础HTML入门教程》