动态贝叶斯网络中的近似推理

15.5.3 动态贝叶斯网络中的近似推理

第十四章描述了两种近似算法：似然加权（图 14.14）和马尔可夫链蒙特卡洛算法（MCMC，图14.15）。这两种方法中，前者能够很容易应用于动态贝叶斯网络背景中。然而我们将看到，在一个实用的方法出现之前，还需要对标准的似然加权算法进行一些改进。

回顾一下，似然加权算法的工作方式是按照网络的拓扑次序对网络中的非证据节点进行采样，并根据每个样本关于观察到的证据变量的似然而对其赋以权值。如同精确算法一样，我们可以将似然加权算法直接应用于未展开的动态贝叶斯网络，但这同样会遇到每次更新所需要的时间与空间随观察序列增长而增长的问题。问题在于标准算法在对整个网络的处理过程中依次处理每个样本。替代地，我们可以简单地一次一个时间片地沿动态贝叶斯网络一并处理全部 N个样本。修正后的算法与滤波算法的一般模式相一致，其中N个样本的集合可看作是前向消息。那么，第一个关键的创新在于，使用样本本身作为当前状态分布的近似表示。这符合每次更新时的“常数”时间要求，虽然这个常数依赖于为了保持对真实后验分布的合理近似所需要的样本数。这里同样不需要展开动态贝叶斯网络，因为我们在内存中只需要保存当前时间片和下一个时间片。

在第十四章关于似然加权的讨论中，我们指出如果证据变量位于被采样变量的“下游”，那么算法的精度会大打折扣，因为在这种情况下所生成的样本不受证据的任何影响。考察一下动态贝叶斯网络的典型结构——比如说，图 15.14中所示的雨伞 DBN——我们发现后面的证据变量确实没有为前面状态变量的采样带来任何益处。事实上，更仔细地观察这个问题，我们就会发现任何状态变量的祖先节点中都不包含任何证据变量！因此，尽管每个样本的权值都应该取决于证据，实际生成的样本集合却完全不依赖于证据。例如，即使老板每天都带着雨伞，采样过程仍然会产生有无尽的晴天的幻觉。这意味着在现实中与真实的事件序列保持相当接近的样本比例将随着观察序列的长度t增加而呈指数级下降；换句话说，为了保持一定的精度水平，我们需要增加的样本数会随t呈指数级增长。限定实时运行的滤波算法只能使用固定数目的样本，这使得算法误差将在少数几次更新步骤之后放大。

显然，我们需要一个更好的解决方案。第二个关键的创新在于将采样集合集中于状态空间的高概率区域。根据观察值的计算结果，通过舍弃一些权值非常低的样本，同时增加高权值样本，我们能够做到这一点。通过这种方式，样本的总体能够保持与现实相当接近。如果我们认为样本是对后验概率进行建模的资源，那么使用更多的处于后验概率较高的状态空间区域的样本是有意义的。

一个称为粒子滤波的算法族就是为此而设计的。粒子滤波算法的工作机理如下：首先，根据时刻0的先验分布P(X0)进行采样得到N个样本构成的总体。然后对每个时间步重复下面的更新循环：

• 对于每个样本，通过转移模型P(Xt+1|xt)，在给定样本的当前状态值xt条件下，对下一个状态值xt+1进行采样使得每个样本前向传播。

• 对于每个样本，通过它赋予新证据的似然值P(et+1|xt+1)进行加权。

• 对总体样本进行重新采样以生成一个新的N样本总体。从当前的总体中选出每个新样本；某个样本被选中的概率与其权值成正比。新的样本未被赋权。

详细算法如图15.15所示；图15.16用实例说明了算法在雨伞动态贝叶斯网络上的操作。

图15.15 作为对状态（样本集）的递归更新操作而实现的粒子滤波算法。每个采样步骤都涉及到按照拓扑次序对相关时间片内的变量进行采样，非常类似于PRIOR-SAMPLE。而WEIGHT-SAMPLE-WITH-REPLACEMENT操作的实现则可以在期望时间O(N)内完成运行

图15.16 N=10时雨伞动态贝叶斯网络的粒子滤波更新循环，图中显示了每种状态的样本总体。（a）在时刻t，8个样本表明Rain（下雨），2个样本表明¬Rain（不下雨）。通过转移模型对下一个状态进行采样，每个样本都向前传递。在时刻t+1，6个样本表明Rain，4个样本表明¬Rain。（b）在时刻t+1观察到¬Umbrella（主管没有带雨伞）。根据每个样本与这个观察的似然程度给样本赋予权值，图中用小圆圈的大小表示。（c）通过对当前的样本集合进行加权随机选择得到一个10样本的新集合，结果有2个样本表明Rain，8个样本表明¬Rain

通过考虑算法在一次更新循环中所发生的事情，我们可以证明该算法是一致的——当 N 趋于无穷大时算法能够给出正确的概率。我们假设采样总体是从时刻t的前向消息f1 : t的正确表示开始的。用N(xt|e1 : t)表示处理完观察e1: t之后时具有状态xt的样本个数，因此对于足够大的N我们有：

现在我们在给定时刻t的样本值的条件下，通过在时刻t+1对状态变量进行采样而将每个样本向前传播。从每个xt状态到达状态xt+1的样本个数等于转移概率乘以xt的总量；因此到达状态xt+1的总样本数等于：

现在我们根据每个样本对于时刻t+1的证据的似然为其赋权。处于状态xt+1的样本得到权值P(et+1|xt+1)。因此在观察到证据et+1后处于状态xt+1的样本总权值为：

W(xt+1|e1:t+1)=P(et+1|xt+1)N(xt+1|e1:t)

现在考虑重新采样步骤。既然每一个样本都以与其权值成正比的概率被复制，重新采样后处于状态xt+1的样本数与重新采样前的状态xt+1中的总权值成正比：

从而，经过一次更新循环后的样本总体正确地表示了时刻t+1的前向消息。

因此，例子滤波算法是一致的，但它是高效的吗？实际中，这个问题的答案看来是肯定的：粒子滤波似乎能够通过常数数目的样本维持对真实后验概率的良好近似。不过迄今为止，仍然缺乏理论的保证；目前粒子滤波算法是一个研究强度比较大的领域。提出了很多变体与改进，并且其应用集也在快速增长。因为它是一个采样算法，粒子滤波能够很容易在混合的和连续的动态贝叶斯网络中使用，允许其应用于诸如视频中的复杂运动模式跟踪（Isard和Blake，1996）以及股票市场预测（de Freitas等人，2000）这样的领域中。