寻找最可能序列

15.2.3 寻找最可能序列

假设警卫在上班的头5天观察到的雨伞序列为[true, true, false, true, true]。那么哪种天气序列能最好地解释这个雨伞序列呢？第3天没出现雨伞意味着当天没有下雨还是主管忘了带？如果第3天没有下雨，可能第4天也不会下雨（因为天气有保持的趋势），而主管带伞只是为了以防万一。总的来说，有25种可能的天气序列供我们选择。有没有一种方法找到最有可能的那个序列，而不用把所有的序列统统枚举出来呢？

我们打算尝试的一种方法是下面的线性时间过程：用平滑算法找到每个时间步上的天气后验概率；然后用每个时间步上与后验概率最接近一致的天气来构造这个序列。这种方法应该引起读者的警觉，因为通过平滑计算得到的是单个时间步上的后验概率分布，然而要寻找最可能序列，我们必须考虑所有时间步上的联合概率。事实上这两个结果之间可能有非常大的差异（参见习题15.4）。

确实存在线性时间算法可以用来找到最可能序列，但是它需要稍微多一点的思考。它依赖于马尔可夫特性，而我们已经利用同样的马尔可夫特性产生了有效的滤波和平滑算法。思考这个问题最简单的方法是将每个序列视为在以每个时间步上的可能状态为节点所构成的图中的一条路径。图15.5（a）中显示了为雨伞世界绘制的这样一幅图。现在考虑寻找穿过这幅图的最可能路径的任务，其中任何一条路径的似然是沿该路径的转移概率和每个状态的给定观察结果的乘积。让我们把注意力特别集中于能够到达状态Rain5= true的路径上。由于马尔可夫特性，最可能到达状态Rain5= true的路径包含了到达时刻 4 的某个状态的最可能路径，伴随着到状态 Rain5= true 的转移；而在时刻 4 将成为到达Rain5= true的路径的一部分的状态就是使该路径的似然达到最大的那个状态。换句话说，在到达每个状态xt+1的最可能路径与到达每个状态xt的最可能路径之间存在一种递归关系。我们可以把这种关系写成与路径概率相联系的公式：

图15.5（a）Raint的可能状态序列可以被视为由每个时间步的可能状态所构成的图中的路径。（为了避免与贝叶斯网络中的节点相混淆，这里用方形节点表示状态。）（b）针对雨伞的观察序列 [true,true,false,true,true] 的Viterbi算法的操作。对每个时间步t，我们已经给出了消息m1:t的取值，m1:t给出了在时刻t到达每个状态的最佳序列的概率。同样对于每个状态，指向它的粗箭头指出了其最佳先辈节点。从m1:5中最可能的状态出发，沿着粗箭头反向的方向就可以得到最可能序列

除了以下区别外，公式（15.9）和滤波公式（15.3）是相同的：

（1）前向消息f1 : t= P(Xt|e1 : t)被消息

所代替，即到达每个状态xt的最可能路径的概率；以及

（2）公式（15.3）中对xt的求和在公式（15.9）中被对xt取极大所代替。

因此，计算最可能序列的算法和滤波是非常相似的：它沿着序列向前的方向运行，通过公式（15.9）计算每个时间步上的消息 m；图 15.5（b）中显示了计算过程。在结束的时候，就得到了到达每个最终状态的最可能序列的概率。于是我们能够很容易地选择总体上的最可能序列（粗箭头标出的状态）。为了标明实际序列而不仅仅是计算其概率，算法还需要保存从每个状态返回到达该状态的最佳状态的指针（用粗体表示）；从最佳的最终状态沿这些指针的反向进行，可以确定最可能序列。

我们刚刚描述的算法称为Viterbi算法，是根据算法提出者的姓氏命名的。和滤波算法类似，其时间复杂度与序列长度 t 呈线性关系。然而，与滤波算法不同的是，其空间需求同样与 t 呈线性关系。这是因为Viterbi算法需要保存标明到达每个状态的最佳序列的指针。