概率计算问题 - 前向算法

定义

前向概率：给定马尔可夫模型$\lambda$，定义“到时刻t为止，部分观测序列为o1,o2,...,ot，且t时刻的状态为qi”的概率为前向概率，记作：

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

原理

这是状态DP的思想。 局部计算前向概率，利用路径结构将前向概率递推到全局（这一句没看懂）。 每一次计算直接利用前一个时刻的计算结果，避免重复计算。

过程

输入： 隐马尔可夫模型$\lambda$ 观测序列O 输出： 观测序列概率$P(O|\lambda)$ 过程： 1. 初值：

$$\alpha_1(i) = \pi_ib_i(o_1)$$

1. 递推：

   $$\alpha_{t+1}(i) = [\sum_{j=1}^N\alpha_t(j)a_{ji}]b_i(o_{t+1})$$
2. 终止：

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

注意$\alpha$和$a$的不同