本篇文章我们来解决，在给定模型和观测序列的情况下，求出最可能出现的对应的隐状态序列。
HMM模型的解码问题最常用的算法是维特比算法，接下来我们将利用维特比算法来解决上述问题。
1、维特比算法概述
维特比算法是一个通用的解码算法，是基于动态规划的求序列最短路径的方法，既然是动态规划算法，那么久需要找到合适的局部状态，以及局部状态的递推公式。在HMM中，维特比算法定义了两个局部状态用于递推。
第一个局部状态是在时刻t隐藏状态为i所有可能的状态转移路径i1,i2,...it中的概率最大值。记为δt(i):
由δt(i)的定义可以得到δ的递推表达式：
第二个局部状态由第一个局部状态递推得到。我们定义在时刻t隐藏状态为i的所有单个状态转移路径(i1,i2,...,it−1,i)中概率最大的转移路径中第t−1个节点的隐藏状态为Ψt(i)（表示该隐状态）,其递推表达式可以表示为：
有了这两个局部状态，我们就可以从时刻0一直递推到时刻T，然后利用Ψt(i)记录的前一个最可能的状态节点回溯，直到找到最优的隐藏状态序列。
2、维特比算法流程总结
输入：HMM模型λ=(A,B,Π)，观测序列O=(o1,o2,...oT)
输出：最有可能的隐藏状态序列I∗={i∗1,i∗2,...i∗T}
-
进行动态规划递推时刻t=2,3,...T时刻的局部状态：
-
计算时刻T最大的δT(i),即为最可能隐藏状态序列出现的概率。计算时刻T最大的Ψt(i),即为时刻T最可能的隐藏状态。
-
利用局部状态Ψ(i)开始回溯。对于t=T−1,T−2,...,1：
最终得到最有可能的隐藏状态序列I∗={i∗1,i∗2,...i∗T}
3、HMM维特比算法求解实例
我们的观察集合是:
V={红，白}，M=2
我们的状态集合是：
={盒子1，盒子2，盒子3}，N=3
而观察序列和状态序列的长度为3.
初始状态分布为：
状态转移概率分布矩阵为：
球的颜色的观测序列:
O={红，白，红}
按照我们上一节的维特比算法，首先需要得到三个隐藏状态在时刻1时对应的各自两个局部状态，此时观测状态为1：
t=1时刻
现在开始递推三个隐藏状态在时刻2时对应的各自两个局部状态，此时观测状态为2：
t=2时刻
继续递推三个隐藏状态在时刻3时对应的各自两个局部状态，此时观测状态为1：
t=3时刻
现在得到最后的时刻，开始准备回溯。
t=3:
最大概率为δ3(3),从而得到i∗3 = 3，
t=2:
最大概率为δ2(3),从而得到i∗2 = 3，
t=1:
最大概率为δ1(3),从而得到i∗1 = 3，
最终得到的状态序列为（3,3,3）
