隐马尔科夫模型(HMMs)之四：前向算法

r囧r小猫 2022-09-24 05:12 203阅读 0赞

**前向算法(Forward Algorithm)**

**一、如果计算一个可观察序列的概率？  **

1.穷举搜索

加入给定一个HMM，也就是说(![P][],A,B)这个三元组已知，我们想计算出某个可观察序列的概率。考虑天气的例子，我们知道一个描述天气和海藻状态的HMM，而且我们还有一个海藻状态的序列。假设这个状态中的某三天是（dry，damp，soggy），在这三天中的每一天，天气都可能是晴朗，多云或者下雨，我们可以用下图来描述观察序列和隐藏序列：

![ob][]

在这个图中的每一列表示天气的状态可能，并且每个状态都指向相邻的列的每个状态，每个状态装换在状态转移矩阵中都有一个概率。每一列的下面是当天的可观察的海藻的状态，在每种状态下出现这种可观察状态的概率是由混淆矩阵给出的。

一个可能的计算可观察概率的方法是找到每一个可能的隐藏状态的序列，这里有3^3 = 27种，这个时候的可观察序列的概率就是 Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)。

很显然，这种计算的效率非常低，尤其是当模型中的状态非常多或者序列很长的时候。事实上，我们可以利用概率不随时间变化这个假设来降低时间的开销。

2.使用递归来降低复杂度

我们可以考虑给定HMM的情况下，递归的计算一个可观察序列的概率。我们可以首先定义一个部分概率，表示达到某个中间状态的概率。接下来我们将看到这些部分概率是如何在time=1和time = n（n > 1）的时候计算的。

假设一个T时间段的可观察序列是：

![seq][]

2a.部分概率

下面这张图表示了一个观察序列（dry，damp，soggy）的一阶转移

![tr][]

我们可以通过计算到达某个状态的所有路径的概率和来计算到达某个中间状态的概率。比如说，t = 2时刻clody的概率用三条路径的概率之和来表示：

![paths][]

我们用![a][]t(j)来表示在t时刻是状态j的概率，![a][]t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)。

最后一个观察状态的部分概率就表示了整个序列最后达到某个状态的所有可能的路径的概率和，比如说在这个例子中，最后一列的部分状态

是通过下列路径计算得到的：

![final][]

因为最后一列的部分概率是所有可能的路径的概率和，所以就是这个观察序列在给定HMM下的概率了。

2b.计算 t = 1时候的部分概率

计算部分概率的公式是：![a][] t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)

当t = 1的时候，没有路径到某个状态，所以这里是初始概率， Pr( state | t = 1) = ![P][](state)，这样我们就可以计算t=1时候的部分概率为：

![ini][]

因为在初始的时候，是状态j的概率不仅和这个状态本身相关，还和观察状态有关，所以这里用到了混淆矩阵的值，k1表示第一个观察状态，bjk1表示隐藏状态是j，但是观察成k1的概率。

2c.计算t > 1时候的部分概率

还是看计算部分概率的公式：![a][] t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)

这个公式的左边是从混淆矩阵中已知的，我只需要计算右边部分，很显然右边是所有路径的和：

![cal][]

需要计算的路径数是和观察序列的长度的平方相关的，但是t时刻的部分概率已经计算过了之前的所有路径，所以在t+1时刻只需要根据t时刻的概率来计算就可以了：

![t时刻][t]

这里简单解释下，bjkt+1 就是在t+1时刻的第j个隐藏状态被认为是当前的观察状态的概率，后面一部分是所有t时刻的隐藏状态到t+1时候的隐藏状态j的转移的概率的和。这样我们每一步的计算都可以利用上一步的结果，节省了很多时间。

2d.降低计算复杂度

我们可以比较穷举和递归算法的复杂度。假设有一个HMM l  =(![P][],A,B)，其中有n个隐藏状态，我们有一个长度为T的观察序列。

穷举算法的需要计算所有可能的隐藏序列：

![穷举][5.1.2.4_1.gif]

需要计算：

![穷举][5.1.2.4_2.gif]

很显然穷举算法的时间开销是和T指数相关的，而如果采用递归算法，由于我们每一步都可以利用上一步的结果，所以是和T线性相关的。（这里认为n是一个常数）

3.总结

这里我们的目的是在某个给定的HMM下，计算出某个可观察序列的概率。我们通过先计算部分概率的方式递归的计算整个序列的所有路径的概率，大大节省了时间。在t=1的时候，使用了初始概率和混淆矩阵的概率，而在t时刻的概率则可以利用t - 1时刻的结果。

二、**前向算法的定义**

我们使用前向算法去计算T长度序列的概率：

![seq][seq 1]

每一个y就是观察状态。在t=1时刻的中间节点的部分状态可以用下面的公式计算：

![def][ini]

对于t>1的情况，部分概率的计算可以用下面的公式：

![中间][5.2_3.gif]

**这里，我觉得是原作者的笔误，后面的应该是bjkt+1**

这样我们就可以用递归的方式来计算所有可能的路径的概率和，最后，所有的部分概率的计算公式为

![all][]

使用天气的例子，计算t = 2时刻的cloud状态的概率方法如图：

![例子][example.forward.gif]

**三、总结**

我们使用前向算法在给定的一个HMM下计算某个可观察序列的概率。前向算法主要采用的是递归的思想，利用之前的计算结果。有了这个算法，我们就可以在一堆HMM中，找到一个最满足当前的可观察序列的模型（前向算法计算出来的概率最大）。

[P]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/graphics/pi.gif
[ob]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/trellis.gif
[seq]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.1.2_A.gif
[tr]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/trellis.1.gif
[paths]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/paths.to.cloudy.gif
[a]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/graphics/alpha.gif
[final]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/alphas.at.t_eq_3.gif
[ini]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.2_2.gif
[cal]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/allpath.gif
[t]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.1.2.3_1.gif
[5.1.2.4_1.gif]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.1.2.4_1.gif
[5.1.2.4_2.gif]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.1.2.4_2.gif
[seq 1]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.2_1.gif
[5.2_3.gif]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.2_3.gif
[all]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.2_4.gif
[example.forward.gif]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/example.forward.gif