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

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

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

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

　　　　我们可以列举出所有可能出现的长度为

　　　　具体暴力求解的方法是这样的：首先，任意一个隐藏序列

P (I | λ) = π i 1 a i 1 i 2 a i 2 i 3 . . . a i

　　　　对于固定的状态序列

P (O | I, λ) = b i 1 (o 1) b i 2 (o 2) . . . b i T (

　　　　则

P (O, I | λ) = P (I | λ) P (O | I, λ) = π i 1 b i 1 (o

　　　　然后求边缘概率分布，即可得到观测序列

P (O | λ) = \sum I P (O, I | λ) = \sum i 1, i 2, . . . i T π

　　　　虽然上述方法有效，但是如果我们的隐藏状态数

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

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

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

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

　　　　在前向算法中，通过定义“前向概率”来定义动态规划的这个局部状态。什么是前向概率呢, 其实定义很简单：定义时刻

α t (i) = P (o 1, o 2, . . . o t, i t = q i | λ)

　　　　既然是动态规划，我们就要递推了，现在我们假设我们已经找到了在时刻

　　　　从下图可以看出，我们可以基于时刻

α t + 1 (i) = [\sum j = 1 N α t (j) a j i] b i (o t +

　　　　我们的动态规划从时刻1开始，到时刻

　　　　下面总结下前向算法。

　　　　输入：HMM模型

　　　　输出：观测序列概率

　　　　1) 计算时刻1的各个隐藏状态前向概率：

α 1 (i) = π i b i (o 1),

　　　　2) 递推时刻

α t + 1 (i) = [\sum j = 1 N α t (j) a j i] b i (o t +

　　　　3) 计算最终结果：

P (O | λ) = \sum i = 1 N α T (i)

　　　　从递推公式可以看出，我们的算法时间复杂度是

3. HMM前向算法求解实例

　　　　这里我们用隐马尔科夫模型HMM（一）HMM模型中盒子与球的例子来显示前向概率的计算。

　　　　我们的观察集合是:

V = {红 ， 白} ， M = 2

　　　　我们的状态集合是：

Q = {盒 子 1 ， 盒 子 2 ， 盒 子 3} ， N = 3

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

　　　　初始状态分布为：

Π = (0.2, 0.4, 0.4) T

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

A = ⎛⎝⎜ 0.5 0.3 0.2 0.2 0.5 0.3 0.3 0.2 0.5 ⎞⎠⎟

　　　　观测状态概率矩阵为：

B = ⎛⎝⎜ 0.5 0.4 0.7 0.5 0.6 0.3 ⎞⎠⎟

　　　　球的颜色的观测序列:

O = {红 ， 白 ， 红}

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

　　　　时刻1是红色球，隐藏状态是盒子1的概率为：

α 1 (1) = π 1 b 1 (o 1) = 0.2 \times 0.5 = 0.1

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

α 1 (2) = π 2 b 2 (o 1) = 0.4 \times 0.4 = 0.16

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

α 1 (3) = π 3 b 3 (o 1) = 0.4 \times 0.7 = 0.28

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

　　　　时刻2是白色球，隐藏状态是盒子1的概率为：

α 2 (1) = [\sum i = 1 3 α 1 (i) a i 1] b 1 (o 2) = [0.1 * 0.5 +

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

α 2 (2) = [\sum i = 1 3 α 1 (i) a i 2] b 2 (o 2) = [0.1 * 0.2 +

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

α 2 (3) = [\sum i = 1 3 α 1 (i) a i 3] b 3 (o 2) = [0.1 * 0.3 +

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

　　　　时刻3是红色球，隐藏状态是盒子1的概率为：

α 3 (1) = [\sum i = 1 3 α 2 (i) a i 1] b 1 (o 3) = [0.077 * 0.5 +

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

α 3 (2) = [\sum i = 1 3 α 2 (i) a i 2] b 2 (o 3) = [0.077 * 0.2 +

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

α 3 (3) = [\sum i = 1 3 α 3 (i) a i 3] b 3 (o 3) = [0.077 * 0.3 +

　　　　最终我们求出观测序列:

P (O | λ) = \sum i = 1 3 α 3 (i) = 0.13022

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

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

　　　　后向算法和前向算法非常类似，都是用的动态规划，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”，那么后向概率是如何定义的呢？

　　　　定义时刻

β t (i) = P (o t + 1, o t + 2, . . . o T, i t = q i | λ)

　　　　后向概率的动态规划递推公式和前向概率是相反的。现在我们假设我们已经找到了在时刻

　　　　这样我们得到了后向概率的递推关系式如下：

β t (i) = \sum j = 1 N a i j b j (o t + 1) β t + 1 (j)

　　　　现在我们总结下后向算法的流程,注意下和前向算法的相同点和不同点：

　　　　输入：HMM模型

　　　　输出：观测序列概率

　　　　1) 初始化时刻

β T (i) = 1,

　　　　2) 递推时刻

β t (i) = \sum j = 1 N a i j b j (o t + 1) β t + 1 (j)

　　　　3) 计算最终结果：

P (O | λ) = \sum i = 1 N π i b i (o 1) β 1 (i)

　　　　此时我们的算法时间复杂度仍然是

5. HMM常用概率的计算

　　　　利用前向概率和后向概率，我们可以计算出HMM中单个状态和两个状态的概率公式。

　　　　1）给定模型

γ t (i) = P (i t = q i | O, λ) = P ( i t = q i , O | λ ) P ( O

　　　　利用前向概率和后向概率的定义可知：

P (i t = q i, O | λ) = α t (i) β t (i)

　　　　于是我们得到：

γ t (i) = α t ( i ) β t ( i ) \sum j = 1 N α t ( j ) β t ( j )

　　　　2）给定模型

ξ t (i, j) = P (i t = q i, i t + 1 = q j | O, λ) = P ( i t =

　　　　而

P (i t = q i, i t + 1 = q j, O | λ) = α t (i) a i j b j (o

　　　　从而最终我们得到

ξ t (i, j) = α t ( i ) a i j b j ( o t + 1 ) β t + 1 ( j )

　　　　3) 将

　　　　在观测序列

　　　　上面这些常用的概率值在求解HMM问题二，即求解HMM模型参数的时候需要用到。我们在这个系列的第三篇来讨论求解HMM参数的问题和解法。

转载处：http://www.cnblogs.com/pinard/p/6955871.html