隐马尔科夫模型(HMMs)之五：维特比算法及前向后向算法

灰太狼 2022-09-24 05:12 194阅读 0赞

**维特比算法(Viterbi Algorithm)**

**找到可能性最大的隐藏序列**

通常我们都有一个特定的HMM，然后根据一个可观察序列去找到最可能生成这个可观察序列的隐藏序列。

1.穷举搜索

我们可以在下图中看到每个状态和观察的关系。

![re][]

通过计算所有可能的隐藏序列的概率，我们可以找到一个可能性最大的隐藏序列，这个可能性最大的隐藏序列最大化了Pr(observed sequence | hidden state combination)。比如说，对于上图中的可观察序列（dry damp soggy），最可能的隐藏序列就是下面这些概率中最大的：

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的情况下，我们可以考虑递归的来寻找最可能的隐藏序列。我们可以先定义一个部分概率![d][]，既是到达某个中间状态的概率。接下来我们将讨论如果计算t = 1和t = n（ n > 1）的部分概率。

注意这里的部分概率和前向算法中的部分概率是不一样的，这里的**部分概率表示的是在t时刻最可能到达某个状态的一条路径的概率，而不是所有概率之和。**

2a.部分概率和部分最优路径

考虑下面这个图以及可观察序列（dry，damp，soggy）的一阶转移

![部分概率][trellis.1.gif]

对于每一个中间状态和终止状态（t = 3）都有一个最可能的路径。比如说，在t=3时刻的三个状态都有一个如下的最可能的路径：

![path][]

我们可以称这些路径为**部分最优路径**。这些部分最优路径都有一个概率，也就是部分概率![d][]。和前向算法中的部分概率不一样，这里的概率只是一个最可能路径的概率，而不是所有路径的概率和。

我们可以用![d][] (i,t)来表示在t时刻，到状态i的所有可能的序列（路径）中概率最大的序列的概率，部分最优路径就是达到这个最大概率的路径，对于每一个时刻的没一个状态都有这样一个概率和部分最优路径。

最后，我们通过计算t = T时刻的每一个状态的最大概率和部分最优路径，选择其中概率最大的状态和它的部分最优路径来得到全局的最优路径。

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

当t=1时刻的时候，到达某个状态最大可能的路径还不存在，但是我们可以直接使用在t=1时刻某个状态的概率和这个状态到可观察序列k1的转移概率：

![t = 1][t _ 1]

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

接下来我们可以根据t - 1时刻的部分概率来求t 时刻的部分概率

![t][]

我们可以计算所有到状态X的路径的概率，找到其中最可能的路径，也就是局部最优路径。注意到这里，到达X的路径必然会经过t - 1时刻的A、B和C，所以我们可以利用之前的结果。达到X的最可能的路径就是下面三个之一：

(sequence of states), . . ., A, X(sequence of states), . . ., B, Xor (sequence of states), . . ., C, X

我们需要做的就是找到以AX、BX和CX结尾的路径中概率最大的那个。

根据一阶马尔科夫的假设，一个状态的发生之和之前的一个状态有关系，所以X在某个序列的最后发生的概率只依赖于其之前的一个状态：

**Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)**

有个了这个公式，我们就可以利用t - 1时刻的结果和状态转移矩阵和混淆矩阵的数据：

![alg][]

将上面这个表达式推广一下，就可以得到t时刻可观察状态为kt的第i个状态的最大部分概率的计算公式：

![gener][]

其中aji表示从状态j转移到状态i的概率，bikt表示状态i被观察成kt的概率。

2d.后向指针

考虑下图

![back][trellis.1.gif]

在每一个中间状态和结束状态都有一个部分最优概率![d][] (i,t)。但是我们的目的是找到最可能的隐藏状态序列，所以我们需要一个方法去记住部分最优路径的每一个节点。

考虑到要计算t时刻的部分概率，我们只需要知道t-1时刻的部分概率，所以我们只需要记录那个导致了t时刻最大部分概率的的状态，也就是说，在任意的时刻，系统都必须处在一个能在下一时刻产生最大部分概率的状态。我们可以利用一个后向指针![f][]来记录导致某个状态最大部分概率的上一个状态，形式化的描述为：

![pointer][]

这里argmax表示能最大化后面公式的j值，同样可以发现这个公式之和t-1时刻的部分概率和转移概率有关，因为后向指针只是为了找到“我从哪里来”，这个问题和可观察没有关系，所以这里不需要再乘上混淆因子。

2e.优点

使用viterbi算法对一个可观察状态进行解码有两个重要的优点：

1.  通过使用递归来减少复杂度，这点和之前的前想算法是一样的
2.  可以根据可观察序列找到最优的隐藏序列，这个的计算公式是：

![exe][]

where

![exet][]

这里就是一个从左往右翻译的过程，通过前面的翻译结果得到后面的结果，起始点是初始向量![p][]。

2.补充

但在序列某个地方有噪声干扰的时候，某些方法可能会和正确答案相差的较远。

但是Viterbi算法会查看整个序列来决定最可能的终止状态，然后通过后向指针来找到之前的状态，这对忽略孤立的噪声非常有用。

3.总结

Viterbi算法提供了一个根据可观察序列计算隐藏序列的很高效的方法，它利用递归来降低计算复杂度，并且使用之前全部的序列来做判断，可以很好的容忍噪声。

在计算的过程中，这个算法计算每一个时刻每一个状态的部分概率，并且使用一个后向指针来记录达到当前状态的最大可能的上一个状态。最后，最可能的终止状态就是隐藏序列的最后一个状态，然后通过后向指针来查找整个序列的全部状态。

--------------------

**前向后向算法（Forward-Backward Algorithm）**

**和隐马尔科夫模型相关的有趣的问题就是判断一个模型的实用性（前向算法）和找到一个隐藏在可观察序列背后的隐藏序列（Viterbi算法）。当然，这两个过程都需要知道HMM的一些信息，比如转移矩阵，混淆矩阵以及初始的π向量。**

**但是在很多实际的情况下，HMM不能被直接的判断，这就变成了一个学习问题，前向后向算法可以根据一系列可观察序列来对HMM进行评测。一个可能的例子就是一个很大的语音处理数据库，语音序列可能被建模为一个马尔科夫链，可观察的序列可以被建模为可识别的状态，但是不能直接获得一些其他的相关信息。**

**前向后向算法理解起来并不困难，但是却要比前向算法和Viterbi算法要复杂，所以这里我们不再详细的介绍。总的来说，这个算法先对一些参数进行猜测，然后再通过评估这些参数的价值来修改这些参数，使得和给定的训练数据的误差变小，这其实是[机器学习][Link 1]中的梯度下降的思想。**

**前向后向算法的名称来源于对于每一个状态，这个算法既要计算到达这一状态的前一个状态的概率，也要计算产生终止状态的后向状态的概率，这两个概率都可以通过递归的方法来实现。对HMM参数的调整可以提高中间概率的准确性，并且这些调整是算法迭代的基础。**

--------------------

**总结（summary）**

通常一个特别的模式不是单独的出现，而是作为某一个时间段下的序列出现。对于以时间为单位的过程有一个假设，一个状态的出现之和其前N个时间单位的状态有关系，这样就是一个N阶马尔科夫链，最简单的情况就是一阶马尔科夫链。

很多情况下，真实的状态序列是不能被直接观察到的，但是可以在一定概率下被间接观察到，这个观察的结果就是另一个可观察的序列，这样我们就可以定义一个隐马尔科夫模型，这个模型在现在的某些领域体现了很大的价值，尤其是语音识别。

这种关于真实序列的模型有三个相关的问题：

1.  评价：一个给定的模型在多大的概率下能产生某个可观察的序列，这个问题可以用前向算法来解决。
2.  解码：给定一个模型和某个可观察序列，最可能的隐藏序列是什么，这个问题可以用Viterbi算法来解决。
3.  学习：给定某个可观察序列，怎么知道这个模型的一些参数，这个问题可以用前向后向算法来解决。

隐马尔科夫模型在分析真实系统的时候表现出了巨大的价值，但是它也有一些缺点，一个最大的缺点就是由于之前的假设导致的过于简化——一个状态只依赖其之间的状态，而且这种依赖是时间无关的。

**参考资料**

http://jedlik.phy.bme.hu/~gerjanos/HMM/node2.html

http://blog.csdn.net/eaglex/article/details/6376826(本文转载出处)

*L R Rabiner and B H Juang, \`An introduction to HMMs', iEEE ASSP Magazine, 3, 4-16.*

[re]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/trellis.gif
[d]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/graphics/delta.gif
[trellis.1.gif]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/trellis.1.gif
[path]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/paths.for.t_3.gif
[t _ 1]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/6.1.2.2_a.gif
[t]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/abcxtrellis.gif
[alg]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/6.1.2.3_a.gif
[gener]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/6.1.2.3_b.gif
[f]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/graphics/phi.gif
[pointer]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/6.1.2.4_a.gif
[exe]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/6.1.2.5_a.gif
[exet]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/viterbi_algorithm/graphics/6.1.2.5_b.gif
[p]: http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/graphics/pi.gif
[Link 1]: http://lib.csdn.net/base/2