贝叶斯网络的分解:局部和并行推理

贝叶斯网络的分解：局部与并行推理

Decomposition for Bayesian Networks: Local andParallel Inference

https://arxiv.org/pdf/2607.04650

摘要

高维贝叶斯网络中的概率推断十分困难，因为对联合分布进行精确处理的复杂度随网络规模呈指数级增长。我们提出了一种基于有向凸子图的分解框架，并引入了一个最小d-分解树。它们共同为经典的连接树构造提供了一种有理论依据的替代方案。所提出的框架通过可以单独学习和存储的低维子模型来表示联合分布。这种分解降低了计算成本，并自然地实现了并行计算。基于最小d-分解树，我们进一步开发了两种用于参数估计和概率推断的并行算法。实验表明，与连接树方法相比，所提出的方法在保持推断精度的同时大幅提高了计算效率，特别是对于低维查询。

索引词——贝叶斯网络，有向无环图，分解，有向凸子图。

I. 引言

贝叶斯网络（BNs）是概率图模型，通过有向无环图（DAGs）表示随机变量间的条件依赖结构[1]。该建模框架为表示高维数据中的复杂依赖关系提供了有原则且可解释的理论基础[2]。它还为不确定性下的概率表示和推理提供了数学上透明的框架。因此，它们已被广泛应用于数据分析及相关工程领域，包括机器学习[3],[4]、生物医学工程[5],[6]、决策支持系统[7],[8]和可靠性分析[9],[10]。

尽管有这些优势，在高维BNs中的学习和推理仍然具有挑战性[1]。高维设置的特征通常是数据稀疏性、变量间复杂的非线性依赖关系以及巨大的计算成本。这些因素使得对联合分布的直接估计变得困难，并需要更易处理的方法。

相关工作。由于分解对于高维BNs的可扩展学习和推理至关重要，许多研究已开发出基于分解的方法。早期的一条工作线是Pearl的[2]信念传播算法[15]，它构建一个联结树并通过消息传递对其进行校准。这种结构为缓存中间计算结果提供了一种有效机制。随后，Wu [15]提出了一种基于分治策略的无损BN分解方法。该方法首先执行全局参数学习，然后将联结树分离器上的势因子分解，并将其分发到相邻的树节点上。进一步表明，原始BN中编码的条件独立性在分解后的子网络中得以完全保留。尽管有效，但这两种方法仍然遵循全局范式。分解后，子网络分布仍然依赖于全局学习的量进行初始化。因此，这些方法并没有实现严格的局部建模或完全独立的推理。

其他研究则侧重于子模型本身的结构和统计特性。Kim和Kim [16]提出了分裂器分解方法，该方法在分解后的子模型内添加额外边以确保边际分布的一致性，使得子模型可以直接从局部数据中进行参数化。然而，这种策略不可避免地增加了子模型的结构复杂性，导致更高的数据存储和计算成本。这种“添边”操作的根本原因在于有向无环图在边际化下不封闭[17],[18]，这突显了BNs中分解的内在困难。

为了解决这些局限性，Li和Guo [19]提出使用完全的d-分离器来分解BN，并表明所得子模型自然满足条件独立性约束。他们的工作识别了BNs中一种类似于无向图模型[11]中原子分解的结构机制，允许子模型仅基于局部数据执行独立的参数学习和存储，同时还能用于后续推理。然而，他们的方法要求d-分解器满足完全性条件，而这对于可分解性来说并非必需，因此限制了其实际适用性。

主要贡献。我们的第一个贡献是对d-分解器的图论刻画：一个子集是d-分解器当且仅当它是一个有向凸的d-分离器。基于此观察，我们提出了一种BNs的分解框架，其中所得子图自然满足可压缩性。定理1给出了联合分布的诱导分解，并阐明了所得子模型的统计作用。

我们进一步开发了一种高效的分解算法，并将所得子图组织成一棵极小d-分解树，其中每个d-分解器对应一个d-凸的极小d-分离器。基于此结构，我们开发了两种算法，利用极小d-分解树在高维网络中进行并行参数估计和概率推理。在实验部分，我们对离散型和高斯贝叶斯网络进行了大规模模拟。结果表明，我们的方法在参数估计和推理方面都显著优于现有的基于联结树的方法，特别是在低维查询方面。

本文的其余部分组织如下。第二节介绍了本文使用的必要符号和背景。第三节介绍贝叶斯网络的有向分解并建立其基本性质。该节还构建了一棵极小d-分解树，并提出了一个用于推理的剪枝规则。第四节描述了使用极小d-分解树进行并行参数学习和概率推理的两种算法。第五节通过实证实验，将基于极小d-分解树的方法在参数估计和推理方面的性能与标准方法进行了评估。最后，第六节对本文进行了总结并给出简要讨论。

II、预备知识

我们首先介绍贯穿本文使用的符号和定义。

C. 贝叶斯网络与边缘分布模型

则

III. 贝叶斯网络的分解

A. 有向凸子图

B. 基于d-凸子图的分解

我们现在正式定义贝叶斯网络的分解。

命题3表明，每个分解后的子模型与原始网络对应的边缘模型一致。这使得参数学习可以直接在每个子网络上使用局部数据进行，并将结果存储以备后续使用。因此，推理效率得到显著提高，计算成本得以降低。基于这一性质，定理1形式化了网络联合分布在分解上的因式分解。

根据定理1，本研究所提出的分解方法具有若干关键优势。首先，局部子模型的边缘分布可以直接从子图数据中计算并存储，可坍缩性保证了其正确性。其次，分解不会引入额外的有向边，保留了原始子图拓扑结构，进一步提升了推理效率和准确性。

在实际应用中，准确识别合适的 d-分解器并高效分解贝叶斯网络仍然具有挑战性。这一困难源于有向无环图中可能存在大量 d-分离器，这使得顺序进行 d-凸性验证和分解在计算上代价高昂。在下一小节中，我们通过使用基于树的结构来有效构建最小 d-分解树，从而应对这一挑战，实现可扩展的参数学习和概率推理。

C. 一种高效的分解算法

该定义同时规定了边上的分离器条件和节点上的不可约条件。一般而言，满足这些条件的最小 d-分解树并不唯一。

条件（i）要求，对于树的每条边，相应节点的交集是 GG中的一个最小 d-分解器。该条件确保贝叶斯网络

沿该边被正确分解为两个子模型。

条件（ii）进一步要求，没有任何最小 d-分解器能够分解与树中任一节点相关联的子模型。这保证了每个子模型在结构上是不可约的。

在实践中，有向无环图的最小 d-分解树可以从最小 d-分离树构建，后者是 Liu 等人 [23] 为结构学习引入的一个概念。在构建过程中，交集形成非凸 d-分离器的相邻节点会被迭代合并，直到无法进一步合并为止。该过程生成该有向无环图的最小 d-分解树。基于这一方法，我们提出了一种构建有向无环图 GG的最小 d-分解树的算法，如算法2所述，随后对其正确性和计算复杂度进行简要讨论。

IV. 基于分解的并行学习与局部推理

本节介绍两个过程。我们首先在分解后的子网络上进行并行参数学习。然后，基于最小 d-分解树的剪枝，开发一种局部推理算法。

A. 并行参数学习

并行参数学习通过将全局任务拆分为更小的子问题，提升了高维贝叶斯网络的可扩展性。利用最小 d-分解树，全局估计任务被划分为对应于每个簇及其两两交集的独立子问题。对于每个子问题，我们提取相应的数据，并通过最大似然或贝叶斯方法估计局部参数。然后，利用推论1重构全局联合分布。详细过程如算法3所述。

由推论1可知，若一个贝叶斯网络可以分解为 kk个 d-凸子图的并集，则其联合分布完全由这 kk个子图上的边缘分布以及它们两两交集中的 k−1k−1个边缘分布所决定。这种分解既降低了计算和存储成本，也为使用最小 d-分解树进行高效参数学习和概率推理奠定了基础。

IV. 基于分解的并行学习与局部推理

本节介绍两个过程。我们首先在分解后的子网络上进行并行参数学习。然后，基于最小 d-分解树的剪枝，开发一种局部推理算法。

A. 并行参数学习

并行参数学习通过将全局任务拆分为更小的子问题，提升了高维贝叶斯网络的可扩展性。利用最小 d-分解树，全局估计任务被划分为对应于每个簇及其两两交集的独立子问题。对于每个子问题，我们提取相应的数据，并通过最大似然或贝叶斯方法估计局部参数。然后，利用推论1重构全局联合分布。详细过程如算法3所述。

B. 局部统计推理

大规模贝叶斯网络中概率推理的目标是高效计算指定目标子集上的分布。最小 d-分解树通常包含大量与查询变量无关的节点，直接使用整棵树会带来不必要的计算开销。为解决这一问题，我们引入递归约简规则，从最小 d-分解树中剪除无关的叶子节点，从而提高推理的效率和可扩展性。

命题4提供了从最小 d-分解树中剪除叶子节点而不影响查询变量推理准确性的判据。其核心思想在于，这些叶子节点中与查询或证据变量相关的任何信息已包含在剩余节点中，且模型

可坍缩到该剩余集合上。通过迭代移除此类叶子节点，最小 d-分解树在实现结构约简的同时，保留了推理所需的所有依赖关系。这一性质确保了局部后验概率可以高效计算，而无需处理整个网络，如下列算法所形式化描述。

算法4利用最小 d-分解树对贝叶斯网络执行局部推理。该过程移除那些查询或证据变量已包含在剩余簇中的叶子节点。此剪枝过程持续进行，直到所有剩余叶子节点都与查询或证据相关。若仅剩一个簇，则应用变量消除法。

否则，在剪枝后的最小 d-分解树上应用置信传播，以计算给定证据下查询变量的后验概率。由此实现了精确推理，同时避免了在网络中与目标后验无关的部分上进行计算。

V. 实证研究

在本节中，我们报告了在所提出的最小 d-分解树框架下，评估参数学习、模型精度和推理效率的数值实验。实验在配备 Intel(R) Xeon(R) Silver 4215R CPU（2 个处理器）和 128 GiB 内存的系统上进行。本研究所用所有代码可在 https://github.com/Balance-H/Decomposition-for-BNs获取。

A. 参数学习

我们首先将分解后子网络上的参数估计与直接全局估计进行比较。使用了 BNlearn 库中的六个代表性贝叶斯网络——Child、Alarm、Hailfinder、Hepar2、Win95pts 和 Pigs——其顶点数量从 20 到 441 不等。实验按以下步骤进行：

备注1：在这些贝叶斯网络中，所有变量均为二值变量。参数估计采用最大似然估计，固定样本量为150,000。分解方法中的并行核心数根据子模型数量动态分配，最多使用9个核心。为确保公平比较，所报告的运行时间仅包含参数学习阶段。

图2展示了参数估计效率随网络规模的变化情况，网络按从小到大的顺序排列。对于较小的网络，如Child和Alarm，由于并行计算的开销，分解方法带来的效率提升有限。随着网络规模增大，分解的优势变得更加明显。对于大型网络，在子模型上进行并行估计相比于全局估计实现了显著的加速。在这六个基准网络上，串行部分平均占总计算时间的不到20%。有关网络树宽以及分解后子图维度分布的详细信息，请参见补充材料S.2。

小的网络，如Child和Alarm，由于并行计算的开销，分解方法带来的效率提升有限。随着网络规模增大，分解的优势变得更加明显。对于大型网络，在子模型上进行并行估计相比于全局估计实现了显著的加速。在这六个基准网络上，串行部分平均占总计算时间的不到20%。有关网络树宽以及分解后子图维度分布的详细信息，请参见补充材料S.2。

Remark 1. In these Bayesian networks, all variables are binary. Parameters are estimated by maximum likelihood with a fixed sample size of 150,000. The number of parallel cores in the decomposition method is assigned dynamically based on the number of sub-models, with a maximum of 9 cores. To ensure a fair comparison, the reported running times include only the parameter learning phase.直译

备注1：在这些贝叶斯网络中，所有变量均为二值变量。参数估计采用最大似然估计，固定样本量为150,000。分解方法中的并行核心数根据子模型数量动态分配，最多使用9个核心。为确保公平比较，所报告的运行时间仅包含参数学习阶段。

合并图片内容直译

B. 并行学习的准确性

C. 最小 d-分解树中的局部推理

前述实验表明，学习得到的分解模型在分布上与原始模型非常匹配。因此，我们转而关注推理效率，评估在最小 d-分解树框架下联合概率查询的计算成本。同时，通过逐步增加查询变量的维度来进行压力测试，以评估剪枝机制在高维设置下的优势。

VI. 结论与讨论

我们提出了一个贝叶斯网络的分解框架，将原始网络划分为若干子图，这些子图所对应的子模型可以并行学习和存储。我们还构建了一个最小 d-分解树，并配以用于局部推理的剪枝规则。基于该框架，我们开发了用于参数估计和概率推理的两个算法。实验表明，所提方法在参数估计和推理两方面均提高了计算效率，尤其在查询维度较小时更为显著。

最小 d-分解树并非唯一，如何为给定网络找到使计算成本最小化的分解仍是一个开放性问题。对于分解后仍然高维的子图，可以应用第二阶段分解来构建嵌套 d-分解树，类似于文献[24]中的嵌套联结树。此类扩展可能进一步提高推理效率，值得未来研究。

所提方法也存在局限性。该方法对稠密网络和高维查询的效果较差。然而，这一局限性也是精确推理方法普遍存在的。

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