数学之美笔记（十九）

1. 维特比算法是一个特殊但应用最广的动态规划算法。
   

2. 假设输入的可见序列是y₁，y₂，...，y_N，而产生它们的隐含序列是x₁，x₂，...，x_N。

   x₁，x₂，...，x_N=ArgMax P（x₁，x₂，...，x_N | y₁，y₂，...，y_N）=ArgMax ∏P（y_i | x_i）· P（x_i | x_i-1）。

   

   这是一个没有状态跳跃，也没有状态自环的相对简单的隐含马尔科夫链。

   P（y_i | x_i）是每个状态的产生概率，P（x_i | x_i-1）是状态间的转移概率。

   这个马尔可夫链的每个状态的输出是固定的，但是每个状态的值可以发生变化。如果把每个状态的值展开，就得到下面这个篱笆网络（Lattice）。

   

   维特比算法是针对篱笆网络的有向图的最短路径提出的。

3. 维特比算法的基础：

   1. 如果概率最大的路径P（即最短路径）经过某个点，比如图中的x₂₂，那么这条路径从起始点S到x₂₂的这一段子路径Q，一定是S到x₂₂之间的最短路径。否则用S到x₂₂的最短路径R代替Q，便构成了一条比P更短的路径，这显然是矛盾的。

   2. 从S到E的路径必然经过第i时刻的某个状态，假定第i个时刻有k个状态，那么如果记录了从S到第i个状态的所有k个节点的最短路径必然经过其中的一条。这样，在任意时刻，只要考虑非常有限条最短路径即可。

   3. 假定当我们从状态i进入到状态i-1时，从S到状态i上各个节点的最短路径已经找到，并且记录在这些节点上，那么计算从起点S到第i+1状态的某个节点x_i+1的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这k个节点到x_i+1，j的距离即可。

4. 维特比算法：

   1. 从点S出发，对于第一个状态x_i的各个节点不妨假设有n₁个，计算出S待它们之间的距离d（S，x_1i），其中X_1i代表任意状态1的节点。因为只有一步，所以这些距离都是S扫它们各自的最短距离。

   2. 对于第二个状态x₂的所有节点，要计算出S到它们的最短距离。对于特定节点x_2i，从S到它的路径可以经过状态1 的n₁中的任何一个节点x_1i，对应的路径长度就是d（S，x_2i）=d（S，x_1j）+d（x_1j，x_2i）。由于j有n₁种可能性，所以要计算找到最小值。

      按照上述方法，从第二个状态走到第三个状态，一直走到最后一个状态，就得到了整个网络从头到尾的最短路径。

本文涉及到的人物及其著作：

安德鲁 · 维特比、欧文 · 雅克布斯、海蒂 · 拉玛尔、乔治 · 安泰尔