前向后向算法

定义$O$表示观测状态，$Q$表示隐含状态，则：

$$begin{align} P(O mid Q,mu) &= prod_{t = 1}^{T-1} P(O_t mid qt,q{t-1},mu) end{align}$$

$mu$表示给定模型。

所以:

$$P(O mid mu) = sum_{Q_i in Q} P(O mid Q_i,mu)$$

但是我们没法穷举所有的$Q_i​$所以这就是前向算法所要解决的问题。

定义$alpha_t(i) = P(O_1,O_2,…,O_t,Q_t=s_i|mu)$

那么，则有：

$$alpha{t+1}(j) = (sum{i=1}^N alphat(i)a{ij})bj(O{t+1})$$

所以：

$$P(O mid mu) = sum_{i=1}^N alpha_T(i)$$

同样的想要计算$P(O mid mu)$还可以使用类似的后向算法。

定义后向变量$betat(j) = P(O{t+1},O_{t+2},…,O_T mid q_t = s_j,mu)$

所以：

$$betat(i) = sum{j=1}^N a{ij}bj(O{t+1}) beta{t+1}(j)$$

所以:

$$P(O mid mu) = sum_{i=1}^N pi_i b_i(O_1) beta_1(i)$$