动态贝叶斯网络中的精确推理

15.5.2 动态贝叶斯网络中的精确推理

已经勾勒了一些将复杂过程表示为动态贝叶斯网络的思想，现在我们转到推理问题上来。从某种意义上来说，这个问题已经得到解答：动态贝叶斯网络仍然是贝叶斯网络，而我们已经了解了贝叶斯网络中的推理算法。给定一个观察序列，我们可以构造动态贝叶斯网络的全贝叶斯网络表示，通过复制时间片的方式，直到网络大到足以容纳该观测序列，如图 15.14 所示。这种技术称为展开（unrolling）。（从技术的角度讲，动态贝叶斯网络等价于通过不断地展开而得到的半无限网络。在最后一次观察之后才加入的时间片对观察期间的推理没有任何影响，因此可以忽略。）一旦动态贝叶斯网络被展开，就可以使用在第十四章中描述过的任何推理算法——变量消元、联合树方法，等等。

不幸的是，展开的朴素应用并不特别有效。如果我们想要对一个很长的观察序列e1:t进行滤波或者平滑，通过展开所得到的网络将需要O(t)的存储空间，而且因此随着更多观察结果的不断加入，所需的存储空间将无限增长。另外，如果每当新的观察结果加入时我们只是简单地重新运行推理算法，那么每次更新所需的时间也同样以O(t)的速度增长。

图 15.14 展开一个动态贝叶斯网络：时间片被复制以容纳观察序列（灰暗节点）。更多的时间片对观测期内的推理没有影响

回顾第15.2节，我们看到当计算过程可以通过递归方式实现时，每次滤波更新都能够在常数时间和空间内实现。本质来看，公式（15.3）中的滤波更新的工作机制是对前一时间步的状态变量进行求和消元，从而得到新时间步上的分布。对变量的求和消元其实就是变量消元（图14.10）算法所做的事情，而且其实按照变量的时序次序运行变量消元，正好模仿了公式（15.3）中的递归滤波更新操作。在任意时刻，修改后的算法至多在内存中保存两个时间片：从时间片0开始，我们加入时间片1，通过求和消去时间片0，再加入时间片2，然后通过求和消去时间片1，依此类推。用这种方法，我们能够在常数时间和空间内完成每次滤波更新（对联合树算法进行适当的修正我们就能够实现同样的性能表现）。习题15.10会要求你为雨伞网络验证这个事实。

好消息到此为止；后面是坏消息：在几乎所有的情况下，每次更新所需要的所谓“常数”时间与空间复杂度，其实是状态变量个数的指数级。发生的情况是，随着变量消元算法的进行，这些因子会逐渐增长以包括所有的状态变量（或者更准确地说，所有那些在前一个时间片中有父节点的状态变量）。最大因子的规模是O(dn+1)，而更新代价为O(dn+2)。

当然，这比隐马尔可夫模型的更新代价，即 O(d2n)要低得多，但当变量个数很多时仍然是不可行的。这个残酷的事实让人有些难以接受。它意味着即使我们可以使用动态贝叶斯网络表示非常复杂但变量间联系却很稀疏的时序过程，我们仍然不能对这些过程进行有效而精确的推理。表示在所有变量上的先验联合分布的动态贝叶斯网络模型本身可以分解成构成它的条件概率表，但是在观察序列上条件化的后验联合概率分布——即，前向消息——通常不是可分解的。到目前为止，还没有人找到绕过这个问题的途径，尽管很多科学与工程的重要领域都将从这个问题的解决中受益匪浅。因此，我们不得不再回头求助于近似方法。