原理

概率计算问题。给定模型\(\lambda=(A,B,\pi)\)和观测序列\(O=(o_1, o_2,...,o_T)\)，计算在模型\(\lambda\)下观测序列O出现的概率\(P(O \mid \lambda)\)。

直接计算法

给定模型\(\lambda=(A,B,\pi)\)和观测序列\(O=(o_1, o_2,...,o_T)\)，计算在模型\(\lambda\)下观测序列O出现的概率\(P(O \mid \lambda)\)。最直接的方法是按概率公式直接计算。通过列举所有可能的长度为T的状态序列\(I=(i_1, i_2,...,i_T)\)，求各个状态序列I与观测序列\(O=(o_1, o_2,...,o_T)\)的联合概率\(P(O, I \mid \lambda)\)，然后对所有可能的状态序列求和，得到\(P(O \mid \lambda)\)。

状态序列\(I=(i_1, i_2, ..., i_T)\)的概率是

\[P(I \mid \lambda) = \pi_{i_1} a_{i_1 i_2} a_{i_2 i_3} ... a_{i_{T-1} i_T}\]

对固定的状态序列\(I=(i_1, i_2, ..., i_T)\)，观测序列\(O=(o_1, o_2,...,o_T)\)的概率是\(P(O \mid I, \lambda)\)

\[P(O \mid I, \lambda) = b_{i_1}(o_1) b_{i_2}(o_2) ... b_{i_{i_T}}(o_T)\]

O和I同时出行的联合概率为

\[\begin{align} P(O, I \mid \lambda) &= P(O \mid I, \lambda) P(I \mid \lambda) \\ &= \pi_{i_1} b_{i_1}(o_1) a_{i_1 i_2} b_{i_2} (o_2) ... a_{i_{T-1} i_T}b_{i_T}(o_T) \\ \end{align}\]

然后，对所有可能的状态序列I求和，得到观测序列O的概率\(P(O \mid \lambda)\)，即

\[\begin{align} P(O \mid \lambda) &= \sum_I P(O \mid I, \lambda) P(I \mid \lambda) \\ &= \sum_{i_1, i_2, ..., i_T} \pi_{i_1} b_{i_1}(o_1) a_{i_1 i_2} b_{i_2} (o_2) ... a_{i_{T-1} i_T}b_{i_T}(o_T) \\ \end{align}\]

但是，上述公式的计算量很大，是\(O(TN^T)\)阶的，这种算法不可行。

前向算法

首先定义前向概率

前向概率：给定隐马尔科夫模型\(\lambda\)，定义到时刻t部分观测序列为\(o_1, o_2, ..., o_t\)，且状态为\(q_i\)的概率为前向概率，记作

\[\alpha_t (i) = P(o_1,o_2,..., o_t, i_t=q_i \mid \lambda)\]

可以递推求得前向概率\(\alpha_t (i)\)及观测序列概率\(P(O \mid \lambda)\)

观测序列概率的前向算法

输入：隐马尔可夫模型\(\lambda\)，观测序列O；

输出：观测序列概率\(P(O \mid \lambda)\)

(1) 初值

\[\alpha_1 (i) = \pi_i b_i (o_1), i=1,2,...,N\]

(2) 递推 对t=1,2,…,T-1

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

(3) 终止

\[P(O \mid \lambda) = \sum_{i=1}^N \alpha_T (i)\]