动态贝叶斯网络 Dynamic Bayesian Networks∗

Dynamic Bayesian Networks

动态贝叶斯网络

https://webdocs.cs.ualberta.ca/~rgreiner/C-366/RG-2002-SLIDES/dbn-murphy.pdf

概述

Dynamic Bayesian Networks 是一篇综述性论文，其核心重点在于系统地介绍和分析动态贝叶斯网络这一强大的概率图模型框架。

文章的主要内容和重点可以概括为以下几点：

1. 统一框架的建立：文章旨在将多种广泛应用于时间序列建模和推断的模型（如隐马尔可夫模型HMM、卡尔曼滤波KF、状态空间模型SSM、因子化HMM、耦合HMM、分层HMM等）纳入一个统一的DBN框架下进行理解和比较。这有助于揭示不同模型之间的内在联系和区别。

2. 核心算法与推断：深入探讨了在DBN中进行高效推断的核心算法，特别是前向-后向算法及其各种变体（如广义α-β算法、对数空间平滑、常数空间平滑），并分析了它们的时间和空间复杂度。此外，还介绍了更高级的推断技术，如基于连接树的精确推断、粒子滤波（包括Rao-Blackwell化）、期望传播和结构化变分近似等。

3. 模型扩展与应用：讨论了DBN的各种扩展形式，例如：

   • 切换状态空间模型 (Switching SSMs)

     ：用于故障诊断等场景。

   • 二维HMMs

     ：用于处理图像等二维数据。

   • 分层HMMs (HHMMs)

     ：用于建模具有层次结构的时间序列。

   • 埋藏式马尔可夫模型 (Buried Markov Models)

     ：允许观测节点间存在非线性依赖。

4. 历史沿革与文献综述：文章通过详尽的参考文献，梳理了DBN及相关概念（如HMM、KF、粒子滤波等）的发展历史和重要里程碑，为读者提供了丰富的背景知识和研究脉络。

5. 理论与实践结合：不仅阐述了理论基础和算法原理，还通过具体的例子（如双水箱系统故障诊断、语音识别、机器人导航、SLAM等）展示了DBN在实际工程问题中的强大建模能力和应用价值。

总而言之，本文的重点是构建一个全面、系统的DBN知识体系，从基础概念、核心算法到高级扩展和实际应用，旨在为研究者和工程师提供一个理解和运用这一强大工具的权威指南。

1 引言

第??章介绍了隐马尔可夫模型（HMMs），第??章介绍了状态空间模型（SSMs）；这两类模型虽广为使用，但在建模序列数据时仍显不够灵活。本章将探讨更为复杂的模型。其核心推广在于：将隐状态表示为一组随机变量，而非单一随机变量；类似地，观测也可采用因子化（factorized）或分布式（distributed）方式加以表示。随后，我们可借助图模型来刻画这些变量之间的条件独立性——既包括同一时刻（within-slice）的变量间关系，也包括跨时刻（across time steps）的依赖结构。

序列数据主要有两种形式：

• 时序（时间序列）数据 ：由某种因果过程依次生成；
• 序列数据 （例如生物序列或自然语言）：我们对其生成机制持更开放（agnostic）的态度。

对于时序数据建模，采用有向图模型（directed graphical models）是自然的选择，因其能体现时间单向流动的特性。“时间片内”（within a time-slice）的弧可为有向或无向，用以刻画变量间的“瞬时”相关性；若所有弧——包括片内与片间——均为有向，则该模型称为动态贝叶斯网络（Dynamic Bayesian Network, DBN）。此处“动态”意指我们所建模的是一个动态系统，并非指图结构随时间变化。DBN因其易于解释与学习而广受欢迎：由于图结构是有向的，每个节点的条件概率分布（CPD）可被独立估计。本章将聚焦于DBN。

对于非时序的序列数据建模，既可采用有向图模型，也可采用无向图模型。本章关于时序模型的离线推断（offline inference）讨论，多数同样适用于非时序模型；而所介绍的在线推断（online inference）方法虽主要面向时序模型，亦可用于静态模型的序列学习（sequential learning）——当数据具有非平稳性或规模过大、难以采用批处理（batch）方法时，这一能力尤为有用。

本章暂不涉及学习问题（参数估计与模型选择），因相关技术仅是对静态模型学习方法的直接拓展。此外，序列决策问题（即控制或强化学习）的讨论将延至第??章。

2 表示

2.1 具有混合高斯输出的隐马尔可夫模型

2.2 自回归隐马尔可夫模型

2.3 混合记忆马尔可夫模型

2.4 阶乘隐马尔可夫模型

因此，自由参数，即方程右侧的成对转移矩阵，以一种难以拆解的方式组合在一起：见图8。相比之下，如果所有的条件概率分布（CPD）都是线性高斯的，那么得到的联合分布是一个多元高斯分布，稀疏的图形结构对应于传统意义上具有许多零的稀疏矩阵：见第2.9节。

2.5 耦合隐马尔可夫模型（Coupled HMMs）

2.6 变时隐马尔可夫模型（Variable-duration (semi-Markov) HMMs）

2.7 段模型

段模型的基本思想是每个隐马尔可夫模型（HMM）状态可以生成一系列观测值，如图12所示，而不仅仅是单个观测值。与变时隐马尔可夫模型（variable-duration HMM）的区别在于，我们不假设每个段内的观测值是条件独立的；相反，我们可以使用任意模型来表示它们的联合分布。似然性由以下公式给出：

2.8 层级隐马尔可夫模型（HHMMs）

层级隐马尔可夫模型（HHMM）是段隐马尔可夫模型（segment HMM）的推广。它允许段隐马尔可夫模型以层级方式由段子隐马尔可夫模型组成。图15展示了基本概念的示意图。此外，不是用随机变量指定每个段的长度，而是通过子隐马尔可夫模型进入其结束状态所需的时间隐式定义长度。（到结束状态的转换可能由某些环境条件触发。）进入结束状态会终止该段，并将控制权返回给调用状态，然后调用状态可以自由变化。

调用上下文被存储在一个深度受限的栈上。因此，HHMM比随机上下文无关文法（SCFGs）和递归转移网络（RTNs）的表达能力要弱，后者都可以处理无界深度的递归。然而，HHMM对于许多实际问题已经足够表达能力强，这些问题通常只涉及尾递归（即，自转移到一个抽象状态）。此外，HHMM可以比SCFGs更高效地进行计算。特别是，SCFGs的推理算法称为内外算法，其时间复杂度为，而我们可以使用第3节中讨论的任何技术在 时间内对HHMM进行推理。

2.8.1 HHMMs的应用

HHMMs 最明显的应用是语音识别。很自然地可以将单词视为由音素组成，这些音素产生子音素，从而产生声学信号。在实践中，从单词到音素的映射由音素字典固定，而从音素到声学的映射则通过假设一个具有高斯输出混合的三态左-右HMM来固定。因此，整个层次结构可以“折叠”成一个扁平的HMM，适当的参数绑定表示层次结构的底层可以在不同的更高层次上下文中重用。然而，如果对学习层次分解感兴趣，HHMM可能会很有用。有关语音识别的更多信息，请参见第 ?? 章。

HHMMs的另一个应用是移动机器人的地图学习。很自然地可以将类似室内办公室的环境视为由走廊和房间组成，而这些又由更细粒度的位置组成。对于这个应用，有必要对模型进行一些修改。首先，我们通常根据机器人执行的动作来条件化所有状态转换。其次，更微妙的是，当我们离开一个抽象状态（例如，走廊）时，新的具体状态（例如，走廊内的位置）取决于旧的具体状态，即，并不是所有的旧上下文在退出时都被“从栈中弹出”。（换句话说，走廊模型不是上下文无关的。）相反，我们根据旧状态的某个函数来条件化新的起始状态。我们把细节留作练习。

2.9 状态空间模型

状态空间模型（SSM）的图结构看起来与隐马尔可夫模型（HMM）的图结构相同，因为它做出了相同的条件独立性假设。通常还会包括一个输入节点，如图18所示。在状态空间模型中，所有节点都是连续的，所有的条件概率分布（CPDs）都是线性高斯的，即，

2.10 联合状态参数估计

在线参数估计问题可以通过将参数添加到状态空间来表示。

例如，假设我们想要递归地（即顺序地）估计线性回归模型中的系数 α，其中我们假设噪声水平 R 是已知的。这可以如图20所示进行建模。条件概率分布（CPDs）如下：

2.11 切换状态空间模型（Switching SSMs）

在图22中，我们展示了一个切换状态空间模型（也称为切换线性动态系统（LDS）、跳跃马尔可夫模型、跳跃线性系统、条件动态线性模型（DLM）等）。基本思想是模型可以在不同类型的动态“模式”或“状态”之间切换。（由此产生的分段线性是近似非线性动态的一种方式。）这些模式本身的动态由一个离散状态马尔可夫链控制。因此，条件概率分布（CPDs）如下：

由于该模型同时具有离散和连续的隐藏变量，因此有时被称为混合动态贝叶斯网络（DBN）。在这种模型中进行精确推断是非常困难的，正如我们在第5.2.4节中讨论的那样。与自回归隐马尔可夫模型（HMM）（第2.2节）形成对比，后者所有隐藏变量都是离散的，使得精确推断变得容易。

2.11.1 数据关联

由于其军事重要性，已经投入了大量精力来解决在混乱环境中跟踪多个目标的问题。详见第5.5节以获取进一步讨论。

3 推理

在观察了大量不同的动态贝叶斯网络（DBNs）之后，我们现在讨论如何在这些模型中执行推断。我们可能感兴趣的推断问题有多种（参见图24以获取摘要）：

我们将专注于在线过滤和离线平滑；其他问题可以通过类似的方法解决。区分所有隐藏节点都是离散的模型和一些（或全部）隐藏节点是连续的模型会很有帮助，因为它们需要不同的解决技术（正如我们在HMM中的推断与SSM中的推断需要不同的技术一样）。

4 离散状态模型中的精确推断

4.1 前向-后向算法

4.2 展开的连接树

不幸的是，当我们从展开的DBN创建一个连接树时，团（cliques）往往非常大，这常常使得精确推断变得难以处理。特别是，对于每个时间切片（可能除了序列的开始和结束附近），通常会有一个团包含该切片中所有具有跨切片连接的节点。（我们将在下面更详细地说明）。参见图25中的一个例子。图26说明了这一点的直观原因：即使切片内的节点没有直接相关，它们最终也会因为共享过去的共同祖先而变得相关。

4.2.1 约束消除排序

4.2.2 无约束消除排序

如果我们使用无约束的消除排序会发生什么？原则上我们可以做得更好。然而，实际上这种情况很少发生。回想一下，找到最优的消除排序是NP难的。因此，大多数消除排序是使用局部搜索算法计算的。经验上，许多研究人员发现，在受限的空间中进行搜索通常会提高找到的局部最优解的质量。例如，无约束算法可能会选择在每个切片中依次消除第一个节点，然后是第二个，等等，创建跨越许多时间切片的宽“水平”团，而不是在时间上局部化的窄“垂直”团。这样的水平排序通常比垂直排序有更大的团大小（对于足够大的 T），因此不会被一个好的搜索算法选择。然而，一个贪婪搜索算法（例如，基于最小填充启发式）可能很容易选择这样的次优排序。

无约束排序的另一个问题是以下内容。我们不希望每次改变序列长度时都不得不计算一个新的消除排序，因为这太慢了。相反，我们希望对一个固定大小的DBN进行三角化，识别结果连接树中的团，然后通过复制重复结构来重用它们，适用于所有序列长度。为了确保连接树中出现这样的重复结构，我们必须使用时间上受限的消除排序。即便如此，涉及动态改变连接树结构的簿记工作也变得相当棘手。

4.3 前沿算法

4.4 接口算法

4.5 条件可追踪子结构

5 近似过滤

5.1 信念状态 = 离散分布

直观上，即使投影在每个时间步引入了错误，转换的随机性质和观测的信息性质足以减少错误，以防止其累积。

BK算法的准确性取决于我们用来近似信念状态的簇。精确推断对应于使用一个包含所有接口节点的单个簇。最具侵略性的近似对应于每个变量使用一个簇（“完全分解”近似）。

5.1.2 束搜索

一种完全不同的近似方法是假设只有少量可能的假设。从每个这样可能的先验状态，我们尝试找到下一个最可能的状态集合。我们可以保留 k 个最可能的状态，或者保留足够的状态以确保我们覆盖了足够多的概率质量。这种方法在语音识别中广泛使用，我们只跟踪句子最可能的解释，以及在故障诊断中，我们只跟踪最可能的故障。

5.2 信念状态 = 高斯分布

5.2.1 卡尔曼滤波器（KF）

我们可以通过使用第4节中讨论的连接树算法，并将求和、乘法和除法的定义修改为可以应用于高斯势而不是离散势，从而将卡尔曼滤波方程推广到任何线性高斯DBN。

5.2.2 扩展卡尔曼滤波器（EKF）

扩展卡尔曼滤波器（EKF）可以应用于形式如下的模型：

其中 f 和 g 是任意可微函数。基本思想是使用二阶泰勒展开将 f 和 g 在先前的状态估计上进行线性化，然后应用标准的卡尔曼滤波器方程。（方程中的噪声方差（Q 和 R）不变，即，由于线性化而产生的额外误差没有被建模。）因此，我们用非平稳线性动态系统来近似平稳非线性动态系统。也就是说，在时间 t，我们通过以下方式近似模型：

我们可以看到，UKF是对标准KF的简单修改，但可以比EKF更准确地处理非线性，而无需计算导数。

5.2.4 假设密度滤波器（ADF）/ 矩匹配滤波器

我们已经在第5.1.1节中遇到了ADF，其中我们假设信念状态可以表示为离散边际的乘积。在本节中，我们假设信念状态由高斯分布表示。目标是找到这个高斯分布的参数。

例如，考虑一个具有线性高斯动态但非线性、非高斯观测的系统（例如，高斯混合模型，这不能通过EKF或UKF处理）。我们从一个近似高斯先验开始：

5.3 信念状态 = 高斯混合

5.4 信念状态 = 样本集合（粒子滤波）

粒子滤波的基本思想是通过一组加权粒子或样本来近似信念状态：

5.4.1 重采样步骤

到目前为止描述的算法被称为序贯重要性采样（SIS）。SIS的一个众所周知的问题是，随着时间的推移，一个归一化的重要性权重趋向于1，而其他权重趋向于零（即使我们使用最优的提议分布：参见第5.4.2节）。因此，大量样本实际上被浪费了，因为它们的权重可以忽略不计。这被称为粒子“贫化”。

“有效”样本数量的估计由以下公式给出：

对于预测未来，从转移先验中采样是足够的，因为没有未来的证据。但对于监控/过滤来说，这并不高效，因为这相当于“猜直到猜对”。例如，如果转换具有高度随机性，从先验中采样将导致粒子在整个状态空间中被提出；如果观测具有高度信息性，大多数粒子将被“淘汰”（即，被赋予低权重）。在这种情况下，首先查看证据 ，然后提出建议更有意义：

5.4.3 拉奥-布莱克韦尔化粒子滤波（RBPF）

拉奥-布莱克韦尔定理展示了如何在每个凸损失函数下改进任何给定的估计器。其核心是以下众所周知的恒等式：

修改后的算法如图444所示。这比从转移先验中采样更昂贵，因为对于每个粒子 i，我们必须遍历所有状态 s 以计算提议分布。然而，这可能需要更少的粒子，从而总体上更快。

5.4.4 DBN的粒子滤波

结合粒子滤波与分解的信念状态 可以将粒子滤波与Boyen-Koller算法（参见第5.1.1节）结合使用，即通过

5.5 信念状态 = 可变大小

在某些应用中，状态空间的大小事先不是固定的。例如，当我们跟踪多个对象时，每个测量可能由它们中的任何一个引起，背景，或者可能是进入“场景”的新对象。这个问题出现在视觉跟踪、雷达跟踪导弹以及移动机器人中，特别是在SLAM（同时定位与地图构建）问题中。

检测新对象存在的标准启发式方法是，如果观测出现在未预期的位置。如果我们对每个对象的位置有先验，我们可以计算预期测量位置的分布：

如果这些密度是高斯分布，这通常表示为置信椭圆或验证门。如果观测值落在这个椭圆内，我们假设它是由对象生成的。如果椭圆内有多个观测值，或者观测值落在多个椭圆内，我们可以将观测值分配给最近的（使用马氏距离）目标，或者计算所有可能的观测值到目标的联合分配的似然度，并选择最有可能的一个（注意，最近邻规则可能会将相同的测量值分配给多个对象，这会导致不准确）。

如果观测值没有落在任何现有对象的验证门内，它可能是由于新对象，或者是由于背景干扰。因此我们考虑这两种假设，并将新对象添加到临时列表中。一旦临时列表中的对象在其验证门内接收到最小数量的测量值，它就被添加到状态空间中。

对象也可能从状态空间中被移除，如果它最近没有更新（例如，它离开了场景）。因此，一般来说，我们必须允许状态空间动态地增长和收缩。

在这种可变大小状态空间模型中进行推断的更严格方法是使用粒子滤波。这很容易，因为每个粒子可以有不同的维度。我们在下面详细举例说明，在线模型选择的背景下。

6 近似平滑

有两种主要类型的近似平滑算法：那些对数据进行单次前后向通过的算法（双滤波平滑器），以及那些进行多次通过的算法。精确推断算法只需要进行一次前后向通过，但在一般情况下，如果允许进行多次通过，近似推断可以实现更好的结果。我们将简要讨论以下各种算法。

6.1 双滤波平滑

无迹卡尔曼平滑器 可以对后向通过的 β 或 γ 版本应用无迹变换，得到无迹卡尔曼平滑器。我们把细节留作练习。

ADF/矩匹配平滑器 我们将在第6.1.3节的切换SSM中讨论矩匹配平滑器的上下文中，以及第6.2节的期望传播上下文中讨论。

6.1.3 信念状态 = 高斯混合

GPB2滤波对应于以下连接树中的收集操作，我们使用弱边缘化从高斯混合中边缘化离散节点：

6.2 期望传播（EP）

期望传播将假设密度滤波（第5.2.4节）推广到批处理的上下文中。它对贝叶斯更新的顺序不太敏感，因为它可以在其他项的上下文中来回优化整体似然度的每个项。我们在下面更详细解释这一点。

回想一下，在ADF中，精确的后验概率由以下公式给出：

EP的另一个应用是迭代BK算法。这允许算法从早期通过中不正确的独立性假设中恢复。通常2-3次通过足以提高性能。

6.3 变分式方法

变分式方法在第？？章中讨论，可以以直接的方式应用于DBN。其中一些方法，如结构化变分近似和变分EM，使用第4节中的精确推断程序作为子程序。

由于在此模型中精确推断是难以处理的，我们选择以下形式的可处理近似：

对该模型的一些简单实验表明，使用确定性退火的变分近似与ADF算法（未退火EP）的性能相当；如果不进行退火，性能会差得多。

6.4 吉布斯采样

一般来说，MCMC方法和吉布斯采样在第？？章中讨论，可以直接应用于DBN。其中一些方法，如结构化变分近似和变分EM，使用第4节中的精确推断程序作为子程序。

一个可能使用此方法的示例是在切换SSM中。（在这种情况下，使用吉布斯采样而不是EP或变分方法的优势是，算法最终可能会收敛到正确答案。）基本算法如下：

7 练习

7.1 隐马尔可夫模型

“埋藏式”马尔可夫模型通过允许可观测节点之间存在非线性依赖关系，推广了自回归HMMs（第2.2节）。此外，依赖关系的性质会根据Qt的取值而改变：参见图51中的示例。此类模型被称为动态贝叶斯“多网络”，因为它是不同网络的混合体。讨论为在这些模型中进行推断，前向-后向算法需要做出哪些（如有）修改。

7.2 二维HMMs

考虑为扫描文本等二维数据定义似然函数。自然地，可以使用一个HMM对图像的每一行建模，并使用另一个HMM对行与行之间的连接进行建模。这被称为伪二维或嵌入式HMM。基本思想如图52所示，其中我们有2行，每行长度为3。

1. 此模型与第2.7节讨论的分段HMMs有何关系？

2. 为伪二维HMMs推导一种高效的基于消息传递的推断算法。提示：首先计算每行的似然度，然后在顶层HMM中使用这些似然度；在反向传递过程中，利用自上而下的信息在每一行-HMM内进行完整的平滑处理。

3. 通过修改第2.5节中的耦合HMM，推导出一个真正的二维“HMM”，使得每个节点都依赖于其上方和左侧最近的邻居。（此类模型有时被称为“因果”MRF。）

4. 在真正的二维HMM中，精确推断的复杂度是多少？

5. 与传统的无向MRF相比，因果MRF有哪些优缺点？

7.3 分层HMMs

本练习要求你为HHMM的DBN表示定义CPDs。我们分别考虑层次结构的底层、中层和顶层（因为它们具有不同的局部拓扑结构），以及第一个、中间和最后一个时间切片。

7.4 故障诊断

切换状态空间模型（SSMs）的一个重要应用是用于故障诊断。例如，考虑图53中的“双水箱”系统，这是故障诊断领域的一个基准问题（尽管通常人们会考虑n个水箱，其中n远大于2）。这是一个非线性系统，因为流量 = 压力 / 阻力（或流量 = 压力 × 电导率）。更成问题的是，阻力值可能会缓慢漂移，或因管道破裂而发生不连续变化。此外，传感器也可能间歇性失效并给出错误结果。请说明如何将此模型表示为动态贝叶斯网络（DBN）。

7.5 广义 α − β 算法

基于第4.4节中的广义 α − γ 算法，推导一个广义 α − β 算法。前向传递过程将完全相同，但后向传递过程应计算HMMs中公式(12.44)的类似形式：

讨论这两种算法的相对优劣。

7.6 对数空间平滑

本练习开发了一种前向-后向算法的版本，该算法在 O(S log T) 的工作空间内计算 P(Xₜ | y₁:ₜ)，而非 O(ST) 的空间（忽略表示算法输入和输出所需的空间）。这对于从长序列中学习模型很有用，因为充分统计量 Σₜ P(Xₜ | y₁:ₜ) 可以存储在常数空间内。

1. 为简化起见，假设 T 为奇数，并令中点 h = (T + 1)/2。证明：对于 t = 1 : h，仅凭 α₁、βₕ₊₁ 和 y₁:ₕ 即可计算出 P(Xₜ | y₁:ₜ)。

2. 对序列的后半部分证明类似的结果。

3. 基于上述结果，可以通过首先沿序列正向运行，然后从末尾反向运行，并仅在中间点和端点处存储所需的消息来构建一个分治算法。然后，在左右两半上递归调用该算法。请详细写出该算法。

4. 证明空间复杂度为 O(S log T)，其中 S 是 α 或 β 消息的大小。时间复杂度是多少？

5. 如果我们将序列划分为 k > 2 个部分，复杂度会如何变化？哪个 k 值能产生最小的空间占用？如果愿意等待的时间最多是标准算法的两倍，应使用哪个 k 值？

7.7 常数空间平滑

1. 给定一个 O(T²) 算法，该算法在常数空间内计算所有 t 对应的 P(Xₜ | y₁:ₜ)（忽略表示输入和输出所需的空间）。

2. 假设我们可以对前向算子进行求逆，使得 αₜ = Fwd⁻¹(αₜ₊₁, yₜ₊₁)。说明我们如何利用这一点在 O(1) 空间和 O(T) 时间内计算所有 t 对应的 P(Xₜ | y₁:ₜ)。提示：将 βₜ₊₁|ₜ 表示为矩阵乘积再乘以 βₜ₊₁|ₜ = 1；类似地，将 βₜ₋ₗ₊₂|ₜ₊₁ 表示为矩阵乘积再乘以 βₜ₊₂|ₜ₊₁ = 1；然后找出它们之间的关系。

3. 解释为什么一般来说前向（和后向）算子不可逆。给出一个反例。

7.8 BK 算法

修改图34中的前向算子，使其输入为因子化的先验 αₜ₋₁，并输出因子化的后验 αₜ。

https://webdocs.cs.ualberta.ca/~rgreiner/C-366/RG-2002-SLIDES/dbn-murphy.pdf