本篇继续讨论隐马尔科夫模型的第二个基本问题——解码问题

在讨论之前，还是欢迎我们的主角——隐马尔科夫模型(HMM)出场！

Problem 2. 解码问题 (Decoding Problem)

已知HMM模型λ=(A, B, π)，以及观测序列O，求最可能的状态序列。之前的博文http://blog.sciencenet.cn/blog-2970729-1188964.html 中讨论的问题就属于这一类问题。

其实这个问题和之前讨论的评估问题(第一类问题)相比，已知的条件是一致的，只是所求不同。因此理论上也可以用枚举法，事实上，在第一篇隐马尔科夫模型简介博文中我们也这样做了。同样因为计算量比较大，所以枚举法并不可取。在此介绍一种目前主流的解决方案，叫做维特比算法(Viterbi Algorithm)，算法演示如下：

Viterbi Algorithm.gif

Viterbi算法的思想是步步为营，每一步都是当前最佳的路。如果用气温和年轮的例子来说：

1. 首先写出第一年的情况

因为第一年观测到的是小年轮，于是δ₁(H)表示第一年观测到小年轮的同时气温为高温的概率：

δ₁(H) = 0.6×0.1=0.06

注：其中0.6表示初始为H的概率，0.1表示观测到小年轮而且为高温的概率。

同时，第一年观测到小年轮而且气温为低温的概率为：

δ₁(C) = 0.4×0.7=0.28

δ₁(C) >δ₁(H)，因此第一年为低温的可能性更大，所以下一步计算时不考虑第一年为高温的情况

2. 计算第二年的情况

第二年观测到的是中年轮(M)，于是

δ₂(H) =δ₁(C)×0.4×0.4 = 0.0448

注：第一个0.4表示由低温转高温的概率，第二个0.4为观测为中年轮，且状态为高温的概率

同理，δ₂(C) =δ₁(C)×0.6×0.2 = 0.0336

δ₂(H) >δ₂(C)，因此第二年为高温的可能性更大，所以下一步计算时不考虑第二年为低温的情况。

3. 计算第三年的情况

第三年观测为小年轮，计算方法同第二年，直接写出结果如下：

δ₃(H) =δ₂(H)×0.7×0.1 = 0.003136

δ₃(C) =δ₂(H)×0.3×0.7 = 0.009408

δ₃(C) >δ₃(H)，因此第三年是低温的可能更高，所以下一步计算时不考虑第三年为高温的情况。

4. 计算第四年的情况

第四年观测为大年轮，计算方法同第二年，直接写出结果如下：

δ₄(H) =δ₃(C)×0.4×0.5 = 0.0018816

δ₄(C) =δ₃(C)×0.6×0.1 = 0.00056448

δ₃(H) >δ₃(C)，因此第四年是高温的可能更高。综上，这四年最可能的状态是C-H-C-H，这一结果和第一篇隐马尔科夫简介博文(http://blog.sciencenet.cn/blog-2970729-1188964.html)中HMM算法得到的结果一致。但是通过计算过程来看，更加高效。

如果用数学公式表示，如下：

参考材料：

https://sens.tistory.com/m/320?category=501289

Guy Leonard Kouemou. History and Theoretical Basics of Hidden Markov Models

Mark Stamp. A Revealing Introduction to Hidden Markov Models

李航. 统计学习方法