第 26 章 维特比和他的维特比算法
Last updated
Last updated
维特比算法是一个特殊的但应用最广泛的动态规划算法，维特比算法主要解决篱笆网络的有向图的最短路径问题。它之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码。
假设在隐含马尔可夫链中，总共有个节点，节点最多的状态有个节点，也就是整个网格的宽度为，那么找出任何相邻两个状态节点的最短路径的复杂度不超过 。由于网格的长度是，所以整个维特比的复杂度是。
从前有个村儿，村里的人的身体情况只有两种可能：健康或者发烧。 唯一判断他身体情况的途径就是到村头李飞飞的小诊所询问。 飞飞通过询问村民的感觉，判断她的病情，再假设村民只会回答正常、头晕或冷。 有一天村里吴恩达就去飞飞那去询问了。 第一天他告诉飞飞他感觉正常。 第二天他告诉飞飞感觉有点冷。 第三天他告诉飞飞感觉有点头晕。 那么问题来了，飞飞如何根据阿达的描述的情况，推断出这三天中阿达的一个身体状态呢? 为此飞飞上百度搜 google ，一番狂搜，发现维特比算法正好能解决这个问题。飞飞乐了。
隐含的身体状态 = { 健康 , 发烧 }
可观察的感觉状态 = { 正常 , 冷 , 头晕 }
飞飞预判的阿达身体状态的概率分布 = { 健康：0.6 , 发烧： 0.4 }
这就是初始状态序列。
飞飞认为的阿达身体健康状态的转换概率分布 = { 健康 -> 健康： 0.7 , 健康 -> 发烧： 0.3 , 发烧 -> 健康： 0.4 , 发烧 -> 发烧： 0.6 }
这样就可以列出相应的状态转移矩阵。
飞飞认为的在相应健康状况条件下，阿达的感觉的概率分布 = { (健康，正常)：0.5 ，(健康，冷)：0.4 ，(健康，头晕)：0.1 , (发烧，正常)：0.1 ，(发烧，冷)：0.3 ，(发烧，头晕)：0.6 }
这样就可以列出相应的观测矩阵。
由上面我们可以发现，HMM的三要素都齐备了，下面就是解决问题了。
阿达连续三天的身体感觉依次是： 正常、冷、头晕 。
已知如上，求：阿达这三天的身体健康状态变化的过程是怎么样的？即已知观测序列和HMM模型的情况下，求状态序列。
第一天的时候，对每一个状态（健康或者发烧），分别求出第一天身体感觉正常的概率：
P(第一天健康) = P(正常|健康)*P(健康|初始情况) = 0.5 * 0.6 = 0.3
P(第一天发烧) = P(正常|发烧)*P(发烧|初始情况) = 0.1 * 0.4 = 0.04
计算在阿达感觉冷的情况下最可能的身体状态。那么第二天有四种情况，由于第一天的发烧或者健康转换到第二天的发烧或者健康。
P(前一天发烧，今天发烧) = P(前一天发烧)*P(发烧->发烧)*P(冷|发烧) = 0.04 * 0.6 * 0.3 = 0.0072
P(前一天发烧，今天健康) = P(前一天发烧)*P(发烧->健康)*P(冷|健康) = 0.04 * 0.4 * 0.4 = 0.0064
P(前一天健康，今天健康) = P(前一天健康)*P(健康->健康)*P(冷|健康) = 0.3 * 0.7 * 0.4 = 0.084
P(前一天健康，今天发烧) = P(前一天健康)*P(健康->发烧)*P(冷|发烧) = 0.3 * 0.3 *.03 = 0.027
第二天的时候，对每个状态，分别求在第一天状态为健康或者发烧情况下观察到冷的最大概率。在维特比算法中，我们先要求得路径的单个路径的最大概率，然后再乘上观测概率。P(第二天健康) = max{0.3*0.7, 0.04*0.4}*0.4=0.3*0.7*0.4 = 0.084
此时我们需要记录概率最大的路径的前一个状态，即 0.084 路径的前一个状态，我们在小本本上记下，第一天健康。 P(第二天发烧)=max{0.3*0.3, 0.04*0.6}*0.3 = 0.027 , 同样的在 0.027 这个路径上，第一天也是健康的。
计算在阿达感觉头晕的情况下最可能的身体状态。
P(前一天发烧，今天发烧) = P(前一天发烧)*P(发烧->发烧)*P(头晕|发烧) = 0.027 * 0.6 * 0.6 = 0.00972
P(前一天发烧，今天健康) = P(前一天发烧)*P(发烧->健康)*P(头晕|健康) = 0.027 * 0.4 * 0.1 = 0.00108
P(前一天健康，今天健康) = P(前一天健康)*P(健康->健康)*P(头晕|健康) = 0.084 * 0.7 * 0.1 = 0.00588
P(前一天健康，今天发烧) = P(前一天健康)*P(健康->发烧)*P(头晕|发烧) = 0.084 * 0.3 *0.6 = 0.01512
第三天的时候，跟第二天一样。P(第三天健康)=max{0.084*0.7, 0.027*0.4}*0.1 = 0.00588，在这条路径上，第二天是健康的。P(第三天发烧)=max{0.084*0.3, 0.027*0.6}*0.6 = 0.01512，在这条路径上，第二天是健康的。
最后一天的状态概率分布即为最优路径的概率，即P(最优)=0.01512，这样我们可以得到最优路径的终点，是发烧。
请看我们的小本本，在求得第三天发烧概率的时候，我们的小本本上面写的是第二天健康，好了，第二天就应该是健康的状态，然后在第二天健康的情况下，我们记录的第一天是健康的。这样，我们的状态序列逆推出来了。即为：健康，健康，发烧。
这儿的箭头指向就是一个回溯查询小本本的过程，我们在编写算法的时候，其实也得注意，每一个概率最大的单条路径上都要把前一个状态记录下来。
在维特比算法中，对于每一个给定的起始点、终止点，如果列出所有可能的路径，从中找出最短路径，计算复杂度呈指数增长。
