1. 总述

  给定模型$\lambda =(A,B,\pi )$和观测序列$O=(o_1,0_2,...o_T)$，计算在模型$\lambda$下观测序列 O 出现的概率$P(O|\lambda )$。该问题可以说是依靠学习问题，因为该问题既需要知道 O 还需要知道$\lambda$。解决该问题经常使用前向算法或者后向算法。注意这里的隐藏序列 I 是未知的。下面先用直接计算法求解，然后讲解概率计算的两种方法：前向算法和后向算法。

• 三个重要推导：

• 推导$P(I|\lambda )={\pi }_{i_1}{a}_{i_1{i}_2}...a_{i_{T-2}{i}_{T-1}}{a}_{i_{T-1i_T}}$
  

• 首先根据假设：

$\begin{array}{rl}P(I|\lambda )& =P(i_1,i_2,...,i_T|\lambda )=P(i_T|i_{T-1},...,i_1)P(i_{T-1}|i_{T-2,...,i_1})\ast ...\ast P(i_2|i_1)\ast P(i_1)\\ & =P(i_T|i_{T-1})P(i_{T-1}|i_{T-2})...P(i_2|i_1)P(i_1)\\ & =a_{i_{T-1i_T}}{a}_{i_{T-2}{i}_{T-1}}...a_{i_1{i}_2}{\pi }_{i_1}\end{array}$

• 推导$P(O,I|\lambda )={\pi }_{i_1}{a}_{i_1{i}_2}...a_{i_{T-1i_T}}{b}_{i_1}(o_1)...b_{i_T}(o_T)$
  

推导$P(O|\lambda )={\sum }_I{\pi }_{i_1}{a}_{i_1{i}_2}...a_{i_{T-1i_T}}{b}_{i_1}(o_1)...b_{i_T}(o_T)$

2. 直接计算法

  第一章将推论时其实已经把答案解出来了，概率问题的目的就是求$P(O|\lambda )$，因此概率问题的解为${\sum }_I{\pi }_{i_1}{a}_{i_1{i}_2}...a_{i_{T-1i_T}}{b}_{i_1}(o_1)...b_{i_T}(o_T)$。但是观察该解，要对$I$进行求和，也就是说要遍历所有可能的隐藏序列，仅从隐藏序列的角度就有$N^T$种可能，再加上观测序列的时间为 T，因此时间复杂度是$O(T{N}^T)$，这种解法时间复杂度太高，因此需要考虑其他解法。

3. 前向算法

• 首先，给出一个定义：给定$\lambda$，定义到时刻 t 时，已经得到部分的观测序列$o_1,o_2,...,o_t$（已知）,且该时刻的隐藏状态为 q_i 的概率为前向概率，用数学公式表达为：${\alpha }_t(i)=P(o_1,...,o_t,i_t=q_i|\lambda )$
  

• 通过定义我们可以得到初始值${\alpha }_1(i)=P(o_1,i_1=q_i|\lambda )=P(o_1|i_1=q_i)P(i_1=q_i)={\pi }_i{b}_i(o_1)$
  

• 推导递推公式：

• 推导最终表达式$P(O|\lambda )=\sum _{i=1}^N{\alpha }_T(i)$
  

4. 后向算法

• 后向算法与前向算法思想想类似，前项是从 t=0 开始往后计算，而后向是从 t=T 时刻，开始往前计算。

• 给出一个定义：给定$\lambda$，定义时刻 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 )$
  

• 初始值：${\beta }_T(i)=1,i=1,2,...,N$。由于 T 时刻已经是最后一个时刻了，故不存在$o_{T+1}$，因而${\beta }_T(i)$没有意义，故人为规定其为 1

• 推导递推公式：

• 推导最终表达式：$P(O|\lambda )=\sum _{i=1}^N{\pi }_i{b}_i(o_1){\beta }_1(i)$
  

5. 一些概率与期望值的计算

• 利用前向概率和后向概率，可以得到关于单个状态和两个状态的概率计算公式：

• 给定模型$\lambda$和观测 O，在时刻 t 处于状态$q_i$的概率，记做${\gamma }_t(i)=P(i_t=q_i|O,\lambda )$，==则 ${\gamma }_t(i)=\frac{{\alpha }_t(i){\beta }_t(i)}{P(O|\lambda }=\frac{{\alpha }_t(i){\beta }_t(i)}{\sum _{j=1}^N{\alpha }_t(j){\beta }_t(j)}$。== 推导如下：

• 给定给定模型 $\lambda$和观测 O，在时刻 t 处于状态 $q_i$且在时刻 t+1 处于状态 $q_j$的概率记做${\xi }_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,\lambda )$，则${\xi }_t(i,j)=\frac{{\alpha }_t(i)a_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)}{\sum _{i=1}^N\sum _{j=1}^N{\alpha }_t(i)a_{ij}{b}_j(o_{t+1}),{\beta }_{t+1}(j)}$。推导如下：

- 将${\gamma }_t(i)$和${\xi }_t(i,j)$对各个时刻 t 求和，可以得到一些有用的期望值：

- 在观测 O 下状态为 i 出现的期望值$\sum _{t=1}^T{\gamma }_t(i)$

- 在观测 O 下状态 i 转移的期望值$\sum _{t=1}^{T-1}{\gamma }_t(i)$

- 在观测 O 下状态 i 转移到状态 j 的期望值$\sum _{t=1}^{T-1}{\xi }_t(i,j)$

6. 总结

$P(I|\lambda )={\pi }_{i_1}{a}_{i_1{i}_2}...a_{i_{T-2}{i}_{T-1}}{a}_{i_{T-1i_T}}$

$P(i_t=q_i,O|\lambda )={\alpha }_t(i){\beta }_t(i)$；$\lambda ,O$为已知量