高阶马尔可夫毯发现通过对忠实性假设的k阶放宽

High-Order Markov Blanket Discoveryvia a k-Order Relaxation of the Faithfulness Assumption

高阶马尔可夫毯发现通过对忠实性假设的k阶放宽

https://arxiv.org/pdf/2607.26357

摘要

从数据中学习变量的图形马尔可夫毯（MB）这一问题，在诸如贝叶斯网络和马尔可夫随机场的结构学习、因果发现以及特征选择等许多领域中都有应用。然而，大多数方法所做的一个常见假设是，分布中的条件独立性意味着图形结构中相同的分离——也被称为忠实性假设。不幸的是，这一假设可能会被高阶依赖关系（如异或和奇偶校验类型关系）所违反，并且在有限样本上，会被经验性违反所违背，在极端情况下，这些违反甚至会导致真实分布中不存在的虚假依赖关系。因此，在本文中，我们提出了一种忠实性假设的“k阶”放宽，它捕捉了k+2个变量之间的奇偶校验类型关系。我们进而提出了一种称为k阶马尔可夫毯（kOMB）的概念验证算法，该算法利用这种放宽来进行MB发现。最后，我们通过实证表明，kOMB如何在忠实性的真实违反和经验违反两种情况下恢复变量的MB。代码可在以下网址获取：https://github.com/lklee9/k-order-Markov-blanket。

1 引言

马尔可夫毯（MB）发现问题的目标是，在给定从联合分布 P P中采样的数据集 D 的情况下，推断图 G 中某个变量 Y 的 MB。MB 发现问题起源于贝叶斯网络和因果学习文献 [Margaritis and Thrun, 1999, Tsamardinos et al., 2003a, Ling et al., 2021, Hu and Zheng, 2024]，它也在特征选择文献中被讨论和使用 [Tsamardinos and Aliferis, 2003, Wang et al., 2020]。更最近，MB 发现也被用作大规模 BN 结构学习的分布式、分治方法中的子程序 [Dong et al., 2025]。话虽如此，我们对推断贝叶斯网络（BN）和马尔可夫随机场（MRF）中的 MB 都感兴趣。因此，只要有可能，我们将尽量使我们的符号和阐述对图 G 的图类型保持中立。

大多数现有的 MB 发现方法在两个主要假设下运行。第一个是 G 中的任何分离都意味着 P 中相同的条件独立性。第二个假设——被称为忠实性假设——则方向相反，即 P 中的任何条件独立性都意味着 G 中相同的分离。

在理论上，存在忠实性违反的 BN 具有零勒贝格测度 [Meek, 1995, Spirtes et al., 2001, Boeken et al., 2025]；然而这些“典型性”结果取决于一些有些随意的选择，比如 σ σ-理想的选择 [Boeken et al., 2025]。存在一些众所周知的、非常简单的违反忠实性的关系示例。最著名的是涉及三个变量的（噪声）异或函数违反 [Inazumi et al., 2011, Marx et al., 2021]；它是（噪声）奇偶校验函数的一个特例，我们在示例 1 中详述了其高阶忠实性违反。

话虽如此，即使不忠实的 BN 和 MRF 在自然界中确实几乎不存在，样本不足仍然可能导致经验性忠实性违反 [Uhler et al., 2013, Lemeire et al., 2012, Boeken et al., 2025]。例如，图 1 中的小例子就是这种情况，其中真实的 BN 是忠实的，但由于有限样本，经验性忠实性违反发生了——这可以通过我们稍后在第 5 节中提出的算法来克服。关于经验性忠实性违反的完整演示可以在后面第 3 节下的示例 2 中找到。此外，在极端情况下，有限的样本量可能导致 MB 发现算法错误地发现真实分布中不存在的虚假依赖关系。我们稍后将在第 6.1 节下的图 4 中观察到这一现象，表现为不同 MB 发现方法在低样本量下呈现出的低精度。

与忠实性相比，有几种更弱的假设，例如邻接忠实性 [Spirtes et al., 2001]、Pearl-最小性 [Pearl, 1988, 2009]、SGS-最小性 [Spirtes et al., 2001]、脆弱性 [Forster et al., 2018]，以及最近提出的 2-邻接忠实性 [Marx et al., 2021]。2-邻接忠实性尤其相当实用，因为它将忠实性违反限制在“不忠实三元组”上，从而产生一种与脆弱性相比搜索空间小得多的算法。然而，尽管 2-邻接忠实性可以找到 XOR 类型的关系，但它无法找到超过 3 个变量的高阶奇偶校验关系。

2 概率图模型与独立性

3 忠实性违反与现有放宽

尽管我们现在知道一个同时违反忠实性和 2-邻接忠实性的 BN，但这些类型的变量间关系在自然界中很可能并不常见。事实上，已经表明不忠实的 BN 具有零勒贝格测度 [Meek, 1995, Spirtes et al., 2001, Boeken et al., 2025]。然而，由于有限样本导致的经验性忠实性违反可能相当常见 [Uhler et al., 2013, Lemeire et al., 2012, Boeken et al., 2025]。因此，在示例 2 中，我们将呈现一个场景，其中即使真实 BN 是忠实的；由于采样误差，BN 的 DAG 对从样本获得的经验分布也不忠实。

幸运的是，在示例 2 中，图 3 中的 DAG 仍然对经验分布是 2-邻接忠实的，因此完整的 MB 仍然可以通过 Marx et al. [2021] 中概述的算法恢复。然而，情况并非总是如此，正如我们将在第 6.1 节中看到的，有时考虑变量之间的更高阶关系可以帮助更好地克服经验性忠实性违反。

4 K阶忠实性放宽

5 KOMB：K阶马尔可夫毯

5.2 KOMB 的计算复杂度

由于 kOMB 是一个概念验证，我们将正确性和清晰性置于效率之上。尽管如此，刻画其最坏情况时间复杂度仍然是有启发性的，我们在推论 1 中陈述该复杂度，其证明见附录 D。

6 实验

为了对 kOMB 进行实证测试，我们将该算法实现为一个用 Rust 编写的 Python 包。该实现尽可能使用 G-Test 作为其首选的条件独立性检验，显著性水平 α = 0.01 ，并在 G-Test 对于所进行的检验来说太弱时——即当每个单元格的平均频率 < 5 时——回退到 SCI 检验 [Marx and Vreeken, 2019]。我们 kOMB 实现的公共仓库和实验代码可在 https://github.com/lklee9/k-order-Markov-blanket找到。所有实验均在 Apple M4 Mac mini 上运行。

在本节中，我们将把 kOMB 与现有的马尔可夫毯（MB）发现方法进行比较。具体来说，我们将与以下八种 MB 发现方法进行比较：GS [Margaritis and Thrun, 1999]、IAMB [Tsamardinos et al., 2003a]、HITON [Aliferis et al., 2003]、MMMB [Tsamardinos et al., 2003b]、PCMB [Peña et al., 2007]、LRH [Liu and Liu, 2016]、STMB [Gao and Ji, 2017]、BAMB [Ling et al., 2019]。我们将使用 pyCausalFS Python 库 [Yu et al., 2020] 中找到的这些方法的实现，任何统计检验的显著性水平也均为 0.01。

6.1 合成贝叶斯网络实验

从表 1 的结果中，我们可以观察到 kOMB 在 MB 发现方面始终优于其他方法。更有趣的是——即使对于贝叶斯网络是忠实的问题——随着我们增加 k k并观察更高阶关系，kOMB 获得更好的 F1 分数，因此能够更好地克服经验性不忠实。此外，奇偶校验问题的 MB 仅在 k = 2 时可恢复，这证实了 kOMB 找到这些高阶奇偶校验类关系的能力。

为了更好地理解低样本量情况下这些经验性不忠实的来源，图 4 追踪了随着样本量从 50 增长到 100 时的 precision、recall 和 F1 分数。正如预期，只有 kOMB-2-2 能够恢复奇偶校验网络的高阶依赖，无论样本量如何。从其他忠实网络中，我们可以观察到在小样本量下，所有方法都表现出较低的 recall 和 precision，这分别表明 MB 发现方法遗漏的依赖和所述方法错误检测到的虚假依赖。话虽如此，我们也可以观察到对于 kOMB，使用的 k k值越高，其在低样本机制下的性能越好，并且它恢复所有变量的真实 MB 的速度越快。

6.2 基准贝叶斯网络实验

为了进一步探索 kOMB 在更现实场景中的表现，我们随后重复了与第 6.1 节相同的过程，但使用 MB 发现文献中一些众所周知的基准数据集⁴。本节实验的主要区别在于我们使用了 5000 个样本，并且我们仅让每种方法寻找贝叶斯网络中具有最大邻域的 10 个变量的 MB。此外，为了节省空间，我们在表 2 中也省略了一些表现较差的方法。

从表 2 的结果中，我们可以观察到 kOMB 通常优于其他现有的 MB 发现方法。然而，更高阶是否有帮助取决于网络的基数。在较低基数的 Alarm1 和 Insurance 网络上，阶数 2 的 kOMB 比阶数 1 有所改进，而在高基数的 Barley 和 Mildew 网络上，阶数 1 最好，阶数 2 则明显更差——在那里，较大的条件集使高阶 CI 测试在此样本量下功效不足。运行时间则随着阶数 k k 和网络基数而增长。具体来说，基线方法在每个数据集上大约 6 秒内完成，而 kOMB 范围从在较低基数网络（Alarm1、Insurance）上阶数 1 时的相当，到在高基数网络（Barley、Mildew）上阶数 2 时的慢几百倍。每种方法和每种 ( k , l ) 配置的完整结果和运行时间见附录 G 中的表 5 和表 6。

7 结论

我们引入了忠实性的 k k阶放宽，它明确解释了 k + 2 个变量之间的奇偶校验类依赖，并用它推导出一个概念验证马尔可夫毯（MB）发现算法 kOMB；具有理论保证，即在所提出的假设下 kOMB 恢复图形 MB。在经验上，kOMB 在合成问题上克服了真实和经验性忠实性违反，并且在常用基准数据集上表现具有竞争力。

由于 kOMB 是一个概念验证，表明利用高阶依赖可以改进 MB 发现，未来工作的一个重要方向是开发近似算法，以 kOMB 的最坏情况成本之外的方式揭示这些高阶依赖——例如，通过更复杂的修剪规则使 kOMB 在更大的 k k值下更好地扩展。其次，尽管我们的消融（附录 G）表明 l = k 且 k ≤ 2 是稳健的默认值，但在没有专家知识的情况下，有原则地先验选择 k k和 l l仍然悬而未决。一个实用的替代方案是对多个 k 和 l 值运行 kOMB，同时跨运行记忆结果以加速总运行时间。最后，我们的评估使用 G-test（带 SCI 回退）进行条件独立性，与已建立的基于约束的 MB 发现方法进行比较。因此，利用更新的替代 CI 测试是未来工作的另一个途径。

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