在给定了一个可观察序列和HMM的情况下，我们可以考虑递归的来寻找最可能的隐藏序列。我们可以先定义一个部分概率 δ，即到达某个中间状态的概率。接下来我们将讨论如何计算 t=1 和 t=n (n>1) 的部分概率。

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

　　1) 部分概率和部分最优路径

　　考虑下面这个图以及可观察序列 (dry, damp, soggy) 的一阶转移

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

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

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

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

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

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

　　3) 计算 t>1 时刻的部分概率

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

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

　　(状态序列)，. . .，A，X (状态序列)，. . .，B，X (状态序列)，. . .，C，X

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

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

Pr (到达A的最优路径) . Pr (X | A) . Pr (观察状态 | X)

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

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

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

　　4) 后向指针

　　考虑下图

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

　　考虑到要计算 t 时刻的部分概率，我们只需要知道 t-1 时刻的部分概率，所以我们只需要记录那个导致了 t 时刻最大部分概率的的状态，也就是说，在任意时刻，系统都必须处在一个能在下一时刻产生最大部分概率的状态。如下图所示：

　　我们可以利用一个后向指针 φ 来记录导致某个状态最大局部概率的前一个状态，即

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

　　5) 优点

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

　　a) 通过使用递归来减少复杂度，这点和之前的前向算法是一样的

　　b) 可以根据可观察序列找到最优的隐藏序列，这个的计算公式是：

其中 

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

　　3. 补充