4.4 前向后向算法评估观察序列概率

学习目标

• 知道用前向算法求HMM观测序列的概率
• 知道用后向算法求HMM观测序列的概率

本节我们就关注HMM第一个基本问题的解决方法，即已知模型和观测序列，求观测序列出现的概率。

1 回顾HMM问题一：求观测序列的概率

首先我们回顾下HMM模型的问题一。这个问题是这样的。

我们已知HMM模型的参数$\lambda =(A,B,\Pi)$。

其中A是隐藏状态转移概率的矩阵，

B是观测状态生成概率的矩阵，

$\Pi$ 是隐藏状态的初始概率分布。

同时我们也已经得到了观测序列$O=\{o_1,o_2,...o_T\}$,

现在我们要求观测序列O在模型$\lambda$ 下出现的条件概率$P(O|\lambda )$。

乍一看，这个问题很简单。因为我们知道所有的隐藏状态之间的转移概率和所有从隐藏状态到观测状态生成概率，那么我们是可以暴力求解的。

我们可以列举出所有可能出现的长度为T的隐藏序列$i=\{i_1,i_2,...,i_T\}$,分别求出这些隐藏序列与观测序列$O=\{o_1,o_2,...o_T\}$的联合概率分布$P(O,i|\lambda )$，这样我们就可以很容易的求出边缘分布$P(O|\lambda )$了。

具体暴力求解的方法是这样的：

• 首先，任意隐藏序列$i={i_1,i_2,...,i_T}$出现的概率是：

  • $P(i|\lambda )=\Pi _{i1}a_{i1,i2}a_{i2,i3}...a_{iT-1,iT}$

• 对于固定的状态序列$i={i_1,i_2,...,i_T}$，我们要求的观察序列$O={o_1,o_2,...o_T}$出现的概率是：

  • $P(O|i,\lambda )=b_{i1}(o_1)b_{i2}(o_2)...b_{iT}(o_T)$

• 则O和i联合出现的概率是：

• 然后求边缘概率分布，即可得到观测序列O在模型$\lambda$ 下出现的条件概率P(O|$\lambda$ )P(O|$\lambda$ )：

虽然上述方法有效，但是如果我们的隐藏状态数N非常多的那就麻烦了，此时我们预测状态有$N^T$种组合，算法的时间复杂度是$O(TN^T)$阶的。

因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。

前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。

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

前向后向算法是前向算法和后向算法的统称，这两个算法都可以用来求HMM观测序列的概率。我们先来看看前向算法是如何求解这个问题的。

2.1 流程梳理

前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。

• 在前向算法中，通过定义“前向概率”来定义动态规划的这个局部状态。

• 什么是前向概率呢, 其实定义很简单：定义时刻t时隐藏状态为$q_i$, 观测状态的序列为$o_1,o_2,...o_t$的概率为前向概率。记为：

• 既然是动态规划，我们就要递推了，现在假设我们已经找到了在时刻t时各个隐藏状态的前向概率，现在我们需要递推出时刻t+1时各个隐藏状态的前向概率。

• 我们可以基于时刻t时各个隐藏状态的前向概率，再乘以对应的状态转移概率，即$\alpha _t(j)a_{ji}$就是在时刻t观测到$o_1,o_2,...o_t$，并且时刻t隐藏状态$q_j$, 时刻t+1隐藏状态$q_i$的概率。

• 如果将下面所有的线对应的概率求和，即就是在时刻t观测到$o_1,o_2,...o_t$，并且时刻t+1隐藏状态$q_i$的概率。
• 继续一步，由于观测状态$o_{t+1}$只依赖于t+1时刻隐藏状态$q_i$, 这样就是在时刻t+1观测到$o_1,o_2,...o_t,o_{t+1}$，并且时刻t+1隐藏状态$q_i$的概率。
• 而这个概率，恰恰就是时刻t+1对应的隐藏状态i的前向概率，这样我们得到了前向概率的递推关系式如下：

我们的动态规划从时刻1开始，到时刻T结束，由于$\alpha _T(i)$表示在时刻T观测序列为$o_1,o_2,...o_T$，并且时刻T隐藏状态$q_i$的概率，我们只要将所有隐藏状态对应的概率相加，即就得到了在时刻T观测序列为$o_1,o_2,...o_t$的概率。

2.2 算法总结。

• 输入：HMM模型$\lambda =(A,B,\Pi )$，观测序列$O=(o_1,o_2,...o_T)$

• 输出：观测序列概率$P(O|\lambda )$

  • 1) 计算时刻1的各个隐藏状态前向概率：
  • 2) 递推时刻2,3,... ...T时刻的前向概率：
  • 3) 计算最终结果：

从递推公式可以看出，我们的算法时间复杂度是$O(TN^2)$，比暴力解法的时间复杂度$O(TN^T)$少了几个数量级。

3 HMM前向算法求解实例

这里我们用前面盒子与球的例子来显示前向概率的计算。 我们的观察集合是:

我们的状态集合是：

而观察序列和状态序列的长度为3.

初始状态分布为：

状态转移概率分布矩阵为：

观测状态概率矩阵为：

球的颜色的观测序列:

按照我们上一节的前向算法。首先计算时刻1三个状态的前向概率：

时刻1是红色球，

• 隐藏状态是盒子1的概率为：

• 隐藏状态是盒子2的概率为：

• 隐藏状态是盒子3的概率为：

现在我们可以开始递推了，首先递推时刻2三个状态的前向概率：

时刻2是白色球，

• 隐藏状态是盒子1的概率为：

• 隐藏状态是盒子2的概率为：

• 隐藏状态是盒子3的概率为：

继续递推，现在我们递推时刻3三个状态的前向概率：

时刻3是红色球，

• 隐藏状态是盒子1的概率为：

• 隐藏状态是盒子2的概率为：

• 隐藏状态是盒子3的概率为：

最终我们求出观测序列:O=红，白，红的概率为：

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

4.1 流程梳理

熟悉了用前向算法求HMM观测序列的概率，现在我们再来看看怎么用后向算法求HMM观测序列的概率。

后向算法和前向算法非常类似，都是用的动态规划，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”。

4.2 后向算法流程

以下是后向算法的流程,注意下和前向算法的相同点和不同点：

• 输入：HMM模型$\lambda =(A,B,\Pi )$，观测序列$O=(o_1,o_2,...o_T)$
• 输出：观测序列概率$P(O|\lambda )$
  • 初始化时刻T的各个隐藏状态后向概率：
  • 递推时刻T−1,T−2,...1时刻的后向概率：
  • 计算最终结果：

此时我们的算法时间复杂度仍然是$O(TN^2)$

5 小结

• 前向算法求HMM观测序列

  • 输入：HMM模型$\lambda =(A,B,\Pi )$，观测序列$O=(o_1,o_2,...o_T)$
  • 输出：观测序列概率$P(O|\lambda )$
    • 1) 计算时刻1的各个隐藏状态前向概率：
    • 2) 递推时刻2,3,... ...T时刻的前向概率：
    • 3) 计算最终结果：

• 后向算法求HMM观测序列

  • 输入：HMM模型$\lambda =(A,B,\Pi )$，观测序列$O=(o_1,o_2,...o_T)$
  • 输出：观测序列概率$P(O|\lambda )$
    • 初始化时刻T的各个隐藏状态后向概率：
    • 递推时刻T−1,T−2,...1时刻的后向概率：
    • 计算最终结果：