动态贝叶斯网络中条件独立性的时序特性

动态贝叶斯网络中条件独立性的时序特性

Temporal Properties of Conditional Independence in Dynamic Bayesian Networks

https://arxiv.org/pdf/2511.10266

摘要 动态贝叶斯网络（DBNs）是一种紧凑的图模型，用于刻画概率性系统——其中相互依赖的随机变量及其概率分布随时间演化。本文研究如何针对时序逻辑规范，验证条件独立性（CI）命题的演化过程。为此，我们考虑两种在CI命题之上的形式化规范：线性时序逻辑（LTL）和非确定性布奇自动机（NBA）。该问题存在两个变体：随机性CI性质，需考虑给定的具体概率分布；结构性CI性质，则仅依赖DBN的图结构本身。我们证明：判定一个随机性CI命题是否“最终成立”，其难度至少等同于数论中长期悬而未决的线性递推序列Skolem问题；而针对LTL与NBA规范验证结构性CI命题的演化，则属于PSPACE复杂度类，且均为NP-难与coNP-难。此外，我们还识别出DBN图结构中若干自然的限制条件，可使结构性CI性质的验证变得可行（tractable）。

1 引言 贝叶斯网络（BNs）（Pearl 1985, 1988；Neapolitan 1990）是数据科学与人工智能领域的核心工具，支持在不确定性条件下的建模与推理。BN通过有向无环图（DAG）这一模板，简洁地表示完整的联合概率分布：图中的节点对应随机变量，边刻画变量间的依赖关系，并为每个变量指定其在父节点条件下的概率分布。BN已成功应用于医疗AI（Lucas等，2004）、自然语言处理（Manning & Schütze，1999）、机器人学（Thrun等，2005）、生物信息学（Friedman，2000）以及风险评估（Fenton & Neil，2012）等领域。

动态贝叶斯网络（DBNs）将BN扩展至变量结果随时间演化的系统建模（Murphy，2002；Koller & Friedman，2009）。DBNs通过对一组随机变量的联合概率分布序列进行紧凑表示：即首先用一个初始BN定义时间点0（记为 V0）的初始联合分布；再通过一个步进BN（step BN）定义下一时刻 Vt+1的联合分布（以当前时刻变量 Vt为条件）。这两个BN对应的DAG共同构成所谓的DBN模板；将该模板实例化为具体的条件概率分布（CPDs），即可得到一个具体的DBN。

DBN所具备的时序维度推动其在机器人学（Thrun等，2005）与系统生物学（Palaniappan & Thiagarajan，2012）中的应用。如今，DBN广泛应用于诸多领域；以下实例说明其在现代AI中的持续重要性：

• 将DBN融入计算机视觉算法可提升其适应性与效率（Piedade & Miraldo，2023）；
• DBN与大语言模型（LLMs）相结合，已被用于构建能依据上下文、与用户进行多模态交互的智能系统（Han等，2025）；
• 在医疗领域，DBN可在保持可解释性、并对缺失数据鲁棒的前提下，支持重症监护室（ICU）中脓毒症的早期预测（Agard等，2025）；
• 近期神经科学研究采用多时间尺度DBN推断脑区之间具有行为依赖性的有向交互作用，在高质量数据集上展现出良好性能（Das等，2024）；
• 医学之外，DBN还被用于太阳能发电预测（Zhang等，2024）及交通网络等动态工程系统的韧性分析（Kammouh等，2020）。

鉴于其重要性，从数据中学习DBN结构的算法仍是当前活跃的研究方向（参见，例如Meng等，2024）。

为了表达系统的时序属性，线性时序逻辑（LTL）和非确定性布希自动机（NBAs），捕获所有ω-正则语言的使用，在过去几十年中已成为一个成功的故事（参见，例如，（Baier和Katoen 2008））。我们旨在利用这些形式化方法来讨论CI的时序方面。

1.1 贡献

1. 在第3节中，我们介绍了用于DBN模板和DBN中结构或随机CI命题演变的时间规范机制，分别使用LTL和NBAs。我们制定了由此产生的结构和随机CI模型检查问题。
2. 在第4节中，我们展示了DBN模板对LTL公式和NBAs的结构CI模型检查问题在PSPACE中是NP难的，并且也是coNP难的。在DBN模板的初始模板仅包含在步骤模板中也作为时间片内边出现的边的自然限制下，我们证明了这些问题是P类问题。
3. 给定具有CPDs的完整DBNs，我们在第5节中展示了检查最终随机CI与检查线性递归序列的Skolem问题一样难，这是一个著名的数论问题，其可判定性状态已经开放了几十年。这意味着如果没有在解析数论中的突破，随机CI模型检查问题的可判定性结果是遥不可及的。

1.2 相关工作

如何在BNs中检测结构CI的问题在1980年代和1990年代得到了回答，表明d-分离表征了所有遵循BN结构的结构CI，这在几乎所有CPDs选择下等同于随机CI，并且通过显示d-分离可以在多项式时间内计算这些结构CI（参见（Pearl 1988；Geiger, Verma和Pearl 1990；Meek 1995））。确切地确定随机CI是否成立需要精确计算必要的条件概率分布。然而，离散随机变量条件独立的近似测试方法是一个活跃的研究领域（参见，例如，（Canonne等，2018；Teymur和Filippi 2020））。通常，Boutilier等人（1996）研究了所谓的上下文敏感独立性，表示变量可能仅在对其他变量的特定值分配下独立。像随机CI一样，这种独立性取决于具体的CPDs。

我们不知道对DBNs中CI的d-分离和检测的彻底研究，更不用说DBNs中CI的时序属性的形式验证了。关于BNs的其他扩展，Shen等人（2019）研究了测试BNs，这是BNs的扩展，表示一组概率分布而不是单一分布，并表明d-分离仍然可以用来检测结构CI。

2 预备知识

贝叶斯网络 贝叶斯网络（BN）是一种概率图模型，它使用有向无环图（DAG）表达一组变量及其条件依赖关系，其中每个节点代表一个变量，边表示变量之间的直接概率依赖。

3 时间条件独立性属性的规范形式化

相反的方向，即d-分离对DBNs的完备性，结果证明是复杂的。我们在第6节中讨论这个问题。

4 结构条件独立性

为了传达这些困难结果的感觉，我们首先提供一个 DBN 模板家族的例子，其轨迹的周期是所用变量数量的指数级：

我们建立了判断

是否成立的NP难度：我们从一元DFA的NP完全交集问题（Blondin, Krebs, 和 McKenzie 2016）进行归约。由于我们还可以访问否定公式，我们也可以从互补问题进行归约。此外，这两种属性都可以用固定的NBAs表示，我们得到了以下结果，其证明是对上述例子的改编。

4.1 DBN通过转换系统追踪

4.2 限制性DBN的特殊情况

5 随机条件独立性

在本节中，我们建立了在给定具体条件概率分布时，关于随机条件独立性（CIs）推理的数论难度。具体来说，我们将展示判断形式为

的公式是否成立至少和有理线性递归序列（LRS）的Skolem问题一样难。

这种归约使用（Aghamohamadi et al. 2025, Cor. 1）将给定的LRS“嵌入”到马尔可夫链

中，然后使用引理 2.4 将马尔可夫链转换为DBN。我们注意到，作为推论，我们的构造也可以用来将LRS的密切相关的正性问题（参见，例如，(Quaknine and Worrell 2014)）用于数论难度的论证）归约为判断 Y 是否总是“正向影响” X 的问题。

6 讨论：DBN中的忠实性

命题3.1展示了DBNs中定理2.3的一个类似结果，尽管是单向的。然而，在未来的工作中，我们旨在正式证明结构独立性的概念在DBNs中对随机独立性是忠实的，从而为DBNs建立定理2.3的完整类似结果。与已知结果的区别在于，当过渡到DBNs时，我们通过在不同时间切片中识别相同变量的分布来对参数施加约束。这减少了参数空间的维度，导致在任何给定时间 t 可接受的贝叶斯网络家族严格更小。

我们注意到，定理2.3的证明（Meek 1995，第6.4节）依赖于一个局部依赖条件：如果

是一条边，那么 X 和 Y 必须是相关的。在贝叶斯网络中，条件概率分布（CPDs）可以被选择为使得沿着d-路径的变量是局部依赖的，而所有其他变量仍然与其他任何变量独立。这在动态贝叶斯网络中是不可能的，因为时间和结构约束阻止了这种隔离。这种限制是将论证扩展到DBN设置的一个关键障碍。一个潜在的方法是考虑一个CPD，其中当一个变量的大多数父节点为1时，该变量以更高的概率取值为1。虽然我们在这里专注于二元变量，但在这个设置中建立结果将直接产生一般情况作为直接推论。另一个有希望的方向来自代数统计（Sullivant 2018），它应用代数几何和组合学的工具来研究统计模型，特别是那些涉及离散数据的模型。在贝叶斯网络中，它将条件独立性编码为多项式方程，并分析由此产生的代数簇以理解结构和概率属性。另一种可能的方法可能涉及观察在时间 t 描述条件（不）依赖的多项式序列在多变量有理函数域上形成一个线性递归，并且可以合理地诉诸于Skolem-Mahler-Lech定理（特征为0的域上线性递归的零点集是有限集和有限多个有效算术级数的并集）。

7 结论

我们引入了基于LTL和NBA的规范形式来表达DBN中CIs的时间属性。这些形式化方法可以表达理想的系统属性，例如在安全应用中的非干扰性，并开放了验证系统以满足各种关于CIs时间演变的期望规范的可能性。

关于DBN中的随机CI，我们的Skolem难度结果对于验证系统相对于随机CI陈述的时间规范的潜力是令人清醒的——这可能会令人惊讶。获得这一难度结果的关键是建立LRS和DBN之间复杂的联系。

原文链接：https://arxiv.org/pdf/2511.10266