使用马尔可夫毯进行因果结构学习

使用马尔可夫毯进行因果结构学习

Using Markov Blankets for Causal Structure Learning

https://jmlr.org/papers/volume9/pellet08a/pellet08a.pdf

摘要

关键词：因果结构学习，特征选择，马尔可夫毯，偏相关，条件独立性统计检验

1. 引言

在本文中，我们感兴趣的是利用特征选择领域的概念来帮助因果结构学习。因果结构学习（Pearl, 2000; Spirtes et al., 2001）是一种多变量数据分析方法，旨在构建一个有向无环图（DAG），显示给定系统中感兴趣变量之间的直接因果关系。这些所谓的因果图可以与称为 do-calculus 的专用规则（Pearl, 1995）一起使用，以预测干预的效果，即数据生成过程中结构变化的效果。从这个意义上说，它显著不同于传统的机器学习技术：给定一组干预，我们可以预测一组变量的行为，这些变量的联合概率分布在模型训练后已经发生了变化。

构建因果图是一项艰巨的任务，受到一系列假设的约束，并且可证明正确的算法具有指数级的最坏情况复杂度。识别精确的因果图通常是不可能的。借助非干预数据，因果图只能识别到观测等价的程度：只有邻接关系和所谓的 V 型结构（两个独立原因导致同一结果）可以被精确指定（Pearl, 2000, p. 19）。因此，典型的结构学习算法返回部分定向无环图（PDAG）。这些算法大致可以分为两类：基于评分的算法将评分函数与给定训练数据集的 DAG 或 PDAG 相关联，并执行例如在 DAG 或 PDAG 空间中的贪婪搜索（例如，GES 算法，Chickering, 2002）；基于约束的算法寻找数据中的依赖关系和条件依赖关系，并相应地构建因果图。著名的例子有 PC（Spirtes et al., 2001）或 IC（Pearl and Verma, 1991）算法。为了兼得两者的优点，其他算法同时使用条件独立性检验和评分来构建网络；MMHC（Tsamardinos et al., 2006）就是这样一个例子。

典型算法能够处理的数据集范围是有限的：并非任何概率分布都能由 DAG 忠诚地表示。分布的忠诚性是一个定义明确的条件：它保证了 DAG 的存在，称为完美映射，其中 d -分离的图形准则与数据中的条件独立性之间存在一一映射。Nilsson et al. (2007) 讨论了忠诚分布以及其他类型的分布关于条件独立性的性质。在文献中，忠诚性是证明算法正确性的前提。

在实践中，现有的基于评分和基于约束的技术主要处理离散数据集。针对连续变量的基于评分的方法计算成本很高；至于基于约束的方法，只有多元高斯情况得到了有效处理（Scheines et al., 1995）。Margaritis (2005) 提出了一种无分布的条件独立性检验，其计算成本非常高，除了非常小的网络外，无法与当前的基于约束的算法一起使用。

来自机器学习社区的特征选择（John et al., 1994; Guyon and Elisseeff, 2003）是一种常见技术，旨在减少用于构建更高效或更鲁棒模型的变量或特征数量。技术已经发展到能够处理变量之间的非线性关系、冗余变量，无论是在离散域还是连续域。特征选择和因果结构学习通过一个共同概念相关联：变量 X 的马尔可夫毯是包含所有携带关于 X 的信息且无法从任何其他变量获得的信息的变量的最小集合 M b ( X ) 。在特征选择中，这是强相关特征的集合；即，携带关于目标的信息且无法从任何其他变量获得的特征（Kohavi and John, 1997）。在因果图中，这是 X 的所有父节点、子节点和配偶的集合。特征选择任务和因果图构建任务在某种程度上都可以表述为马尔可夫毯识别任务。

将特征选择与因果结构学习联系起来并不新鲜。已经提出了几种识别单个变量马尔可夫毯的算法，其技术灵感来自因果结构学习，作为忠诚分布情况下特征选择问题的最优解决方案。Tsamardinos 和 Aliferis (2003) 表明，对于忠诚分布，变量 Y 的马尔可夫毯恰好是强相关特征的集合，并证明了其唯一性。他们提出了增量关联马尔可夫毯（IAMB）算法来确定它。在相同的忠诚性假设下，最小-最大马尔可夫毯算法（MMMB）（Tsamardinos et al., 2003）通过调用子程序最小-最大父节点和子节点（MMPC）来识别变量 Y Y的马尔可夫毯。该子程序通过关联度量和条件独立性检验找到 Y 的直接父节点和子节点。然后再次对每个这些节点调用 MMPC 以找到 Y 的潜在配偶。然后通过条件独立性检验丢弃假阳性。Peña et al. (2005) 进一步讨论了 MMMB，他们提出了 AlgorithmMB，这是一种基于评分和条件独立性检验的类似方法，用于检索 M b ( Y ) 。HITON_MB 算法（Aliferis et al., 2003）在其主要步骤上类似，并在忠诚性假设下选择目标变量马尔可夫毯的最优子集。Nilsson et al. (2007) 还提出了一种理论算法，用于在严格正分布类别中以多项式时间一致地识别强相关特征。他们还认为，一些常见的后向特征消除算法，如递归特征消除（Guyon et al., 2002），实际上是一致的，即它们在大样本极限下返回强相关特征的集合。

这些是使用因果结构学习或类似基于约束的技术来帮助特征选择的例子（参见 Guyon et al., 2007，对这些技术的综述）。在本文中，我们提出了一个框架来做相反的事情。我们提出了一种通用方法，使用一致的特征选择算法 F S 的结果来构建真实因果图的近似结构。如果我们假设 F S 返回变量的马尔可夫毯，我们可以展示如何将这个称为道德图（Lauritzen and Spiegelhalter, 1988）的近似结果转换为一个可证明正确的 PDAG，描绘因果结构。这种方法也用于 Grow-Shrink 算法（Margaritis and Thrun, 1999），该算法在调整局部结构之前也构建了一个道德图。

本文贡献了一种构建因果图的通用算法，该算法清晰地将马尔可夫毯识别与所需的局部调整分开；一种执行这些调整的有效算法；以及针对多元高斯数据的通用算法的两个快速实例。本文的组织结构如下：在第 2 节中，我们首先回顾特征选择和因果性中所需的术语和定义。在第 3 节中，我们通过详述所需的局部调整并详述执行它们的有效方法，将特征选择算法的结果与因果图联系起来。我们直接将其应用于第 4 节，在那里我们描述如何使用 RFE 特征选择算法构建因果图。由于这种直接应用计算量非常大，我们随后展示了我们针对多元高斯情况优化的通用算法的更高效实例，即 TC 和算法。我们在第 5 节中列出了我们的实验结果，通过实证评估表明马尔可夫毯算法比参考 PC 算法更具可扩展性且更准确。我们最终在第 6 节中得出结论，并在附录 A 中列出证明。

1.1 符号说明

2. 背景

我们形式化了适合我们需求的特征选择任务，并提供了相关定义。我们对因果结构学习任务也做同样的事情，并为在下一节中在两者之间进行类比准备所需的基础。

2.1 特征选择

2.2 因果结构学习

因果模型所选择的图形表示是有向无环图（DAG）（Pearl, 2000）。在由 DAG 表示的因果图中，我们希望用变量对之间的弧来表示直接的因果关系。为此任务选择 DAG 意味着限制，其中一个明显的限制是因果反馈环被排除在分析之外。更形式化地说，联合概率分布必须是忠诚的（或 DAG 同构的，Pearl, 1988, p. 128）；也就是说，必须存在一个 DAG，它表示该分布所蕴含的所有（条件）依赖关系和独立关系。如果定义在变量上的条件独立性关系与定义在图形节点上的 d-分离准则之间存在一一映射，则这样的图被称为该分布的完美映射。

这被 Pearl (1988) 称为 I-map 性质。

忠诚性条件可以解释为因果马尔可夫条件的逆命题，它指出唯一成立的条件独立性就是那些由因果马尔可夫条件所指定的条件独立性：

有时可以通过查看已经定向的弧并传播约束，来进一步定向图中的弧，从而防止产生环以及创建除已检测到的 V 型结构之外的额外 V 型结构。经过此约束传播步骤后的图被称为完成 PDAG、最大定向 PDAG（CPDAG）或本质图，具体取决于作者。

3. 基于特征选择的因果网络构建

我们已经审视了 (1) 中特征选择的理想结果，以及如何解读 (6) 中的因果图。现在我们转向展示如何利用特征选择来构建因果图。从现在起以及本文的剩余部分，我们假设所有变量 V V上的联合概率分布是忠诚的。

3.1 识别马尔可夫毯

在有向图模型的背景下，节点 X X的马尔可夫毯，记为 M b ( X ) ，是 X X的父节点、子节点以及子节点的父节点（配偶）的集合。作为一个简单的性质，请注意我们有：

3.3 一种基于特征选择的通用算法

得益于上一节中解释的子程序，我们现在可以起草一种基于特征选择方法（返回强相关特征）的通用结构学习算法。算法 3 列出了该方法三个主要步骤的伪代码：

1. 利用特征选择找到每个变量的推测马尔可夫毯（Markov blanket），并构建道德图（moral graph）；

2. 利用碰撞集（collider sets）移除配偶链接并定向 V 型结构（V-structures）；

3. 传播定向约束。

为完整起见，步骤 3 的约束传播规则也已列出，位于一个单独的子程序中（见算法 4）。在结构学习中，为了获得完整的 PDAG（部分有向无环图）（Pearl and Verma, 1991），这些规则是常见的。Meek (1995) 证明，当给定一个其 V 型结构已定向的 PDAG 时，这三条规则确实能返回最大定向图。

这种方法的挑战是双重的。一个问题是效率：一致但缓慢的特征选择算法不会胜过现有的因果学习算法，因为它们必须运行的次数等于变量数 d 。第二个也是最大的问题是，为了证明这种通用算法的正确性，需要一致的特征选择算法，即特征选择的结果应等于强相关特征集。这一要求并不总能被满足。Hardin et al. (2004) 研究了一种 SVM 分类器并讨论了基于 w 权重的特征选择：尽管在大样本极限下不相关变量不会被选中，但他们表明，由于 SVM 的大间隔行为，弱相关变量的权重可以任意接近强相关变量的权重。前向特征选择已被证明会遗漏强相关变量（Guyon and Elisseeff, 2003）。Nilsson et al. (2007) 也描述前向选择是不一致的，但声称后向特征消除在大样本极限下实际上是一致的。⁹ 对于有限数据集，Statnikov et al. (2006) 进一步表明（除其他外），甚至不相关变量的权重也可能比相关变量的权重大，并且在某些情况下，弱相关变量比强相关变量被选中的频率更高。

4. 因果特征选择算法

在本节中，我们展示两种算法（以及一个变体）作为前述通用方法的实例化。首先，我们解释一种基于递归特征消除（RFE）算法（Guyon et al., 2002）的算法，作为现有方法的直接应用。然后我们描述全条件（Total Conditioning, TC），这是一种在多变量高斯假设下可被证明正确的快速算法。我们还展示了一个变体 TC_bw，它通过使用显式的后向特征选择启发式方法，在小样本量下提高了准确性。在第 5 节中，我们报告了包含这些算法的实验。

4.1 一种基于 RFE 的方法

为了实证检验该方法的合理性，我们提出在支持向量回归（SVR）学习器（Smola and Schölkopf, 1998）上使用带线性核的 RFE，在此示例中假设我们将处理多变量高斯数据。RFE 是后向特征消除算法的一个实例。给定某个学习器（在本例中为 SVR），它迭代地训练该学习器，根据某种标准对特征进行排序，并移除排序标准最小的特征（或 p 个特征）。该标准可以是学习器赋予特征的权重 w ，或者是特征的某种敏感度度量（Guyon et al., 2002）。在我们的案例中，我们使用了 Smola and Schölkopf (1998) 中描述的 SVR 的权重 w 。

使用 RFE，马尔可夫毯的识别分两步完成：

1. 使用 RFE 根据训练模型中的权重对预测变量进行排序，并提供可被视为预测变量相关性排序的结果；

2. 确定马尔可夫毯的大小，从而确定从 RFE 返回的列表中选择的变量数量。

我们没有理论保证 RFE/SVR 会返回马尔可夫毯变量。尽管 Nilsson et al. (2007) 表明 Guyon et al. (2002) 中描述的 RFE/SVM 是一致的（即在大样本极限下返回强相关变量），但在有限数据集上基于 SVM 的 w 权重对变量进行排序的局限性也已被强调（Hardin et al., 2004; Statnikov et al., 2006）。因此，目前我们将此特征选择步骤用作一种启发式方法。

为了确定从 RFE 返回的排序列表中选择的变量数量，我们使用以下标准：从列表中的第一个变量开始，如果 SVR 的交叉验证训练误差随新变量的加入而降低，则接受该新变量进入马尔可夫毯；如果加入下一个变量会增加误差，则停止并返回当前列表。

4.2 TC 算法

我们现在在过程 TCFEATURESELECTION（算法 6）中提出算法 3 通用方法第 3 行特征选择调用的另一个实例化。由特征选择、碰撞体识别和最大定向步骤确定的整个算法，等同于 Pellet and Elisseeff (2007) 中描述的 TC 算法。（因此我们写“TC”来指代整个算法，而不仅仅是特征选择过程，后者被称为 TCFEATURESELECTION。）

对于给定的目标变量 X ，TC 估计一个多元回归问题的系数，将所有其他变量 V ∖ X 视为预测变量。然后它根据对每个变量系数的 t t检验，返回显著的预测变量。其简短列表见算法 6。

4.2.1 显著性检验

独立于小样本量或多重共线性问题，线性回归方程权重的统计检验是 TC 中的一个微妙点。第一类错误率 α α的选择需要研究，因为它显著影响算法的结果。

4.3 TC_bw 算法

尽管 TC 是正确的，但在样本数 n n较低时，它无法有足够的证据来拒绝零回归权重的原假设，因此会遗漏链接（详见第 5 节的结果），即使 α α很高也是如此。我们现在试图通过逐步消除最不显著的预测变量并重新评估剩余的预测变量来解决这个特定问题。这实际上是一种后向逐步回归方法。这种启发式方法的伪代码列在算法 7 中。

5. 实验结果

在本节中，我们分别报告关于两点的实验和结果。首先，我们测试算法 2 中描述的、在给定所有马尔可夫毯的情况下恢复局部结构的过程，并将其与算法 1 中列出的 GS 算法的相关步骤进行比较，使用 5 种不同的网络拓扑。为了比较，我们还运行了参考 PC 算法（Spirtes et al., 2001），该算法用道德图而非完全连接图进行初始化。

其次，我们进行实验以研究整个结构学习算法的行为。我们首先使用基于 RFE 的方法。然后我们系统地比较 TC、TC_bw 和几个参考算法，改变数据集大小和网络大小。请注意，由于某些算法在某些数据集上运行时间过长，它们的结果可能会比较稀疏。

5.1 实验设置

为了测试各种算法的准确性，我们选择从贝叶斯网络库（Elidan, 2001）中的以下已知网络中采样数据：

• Alarm 网络（Beinlich et al., 1989）。该网络已成为结构学习算法事实上的标准基准：它包含 37 个节点，46 条弧，在等价类的 PDAG 中有 4 条无向边。它最初设计用于帮助解释监测数据，以提醒麻醉师手术室中的各种情况。其图示见图 4。

• Insurance（Binder et al., 1997），27 个节点，52 条弧，其 PDAG 中有 18 条无向边。它旨在评估汽车保险风险。该网络的节点比 Alarm 少，但更密集，见图 5。

• Hailfinder（Abramson et al., 1996），56 个节点，66 条弧，其 PDAG 中有 17 条无向边。它是一个预测科罗拉多州东北部夏季严重冰雹的规范系统。见图 6。

• Carpo，
  61 个节点，74 条弧，其 PDAG 中有 24 条无向边。它旨在帮助诊断腕管综合征。我们使用的版本有三个不连通的子图，其中一个是单变量，并且具有相对平坦的因果结构，如图 7 所示。

• Diabetes 的一个子集（Andreassen et al., 1991），有 104 个节点，149 条弧，其 PDAG 中有 8 条无向边，设计为胰岛素剂量调整的初步模型。该子集由 6 个重复模式（原始网络中有 24 个）组成，每个模式有 17 个节点，外加 2 个连接到每个模式的外部节点。其中前两个模式如图 8 所示。

我们进行了三个系列的实验。

1. 我们将解决马尔可夫毯的算法与第 3.2 节中描述的 Grow-Shrink 算法的相关步骤以及 PC 进行了比较；

2. 我们测试了基于 RFE 的方法，并将其与 PC 进行了比较；

3. 最后，我们将 TC 和 TC_bw 与三种参考算法进行了比较，并在改变网络结构、网络大小和样本大小的同时，检查了它们的准确性、运行时间和测试次数。

所选的参考算法是：

1. PC 算法。PC 与 TC 和 TC_bw 一样，在图不够稀疏的最坏情况下是指数级的：我们讨论了哪些结构元素会使 PC 或 TC 表现出指数级行为；

2. 完整的 Grow-Shrink 算法，如 Margaritis and Thrun (1999) 所述；

3. 一种处理连续数据集的最先进的贝叶斯结构学习算法，即 Bach-Jordan 评分算法（Bach and Jordan, 2003），并结合在 DAG 空间中的贪婪搜索。请注意，贝叶斯结构学习算法通常是基于评分的，并返回完全定向的 DAG。最大化所选评分函数可能不会像我们在这些结果中报告的那样最小化结构错误的数量。

对于所有模拟实验，我们通过使用这 5 个图作为线性结构方程模型的结构来生成数据集：无父节点的变量被采样为均值为零、标准差为单位一的高斯分布；其他变量被定义为其父变量的线性组合，系数在 0.2 到 1 之间均匀随机分布，类似于 Scheines et al. (1995) 中为评估 PC 所做的处理。扰动项也服从正态分布。我们比较了测试次数、条件集的大小，以及在人工数据运行情况下的结构误差。结构误差是指相对于原始图的弧添加、删除或反转。

5.2 利用马尔可夫毯信息进行局部结构恢复

在这个系列的实验中，我们将 RESOLVEMARKOVBLANKETS_COLLIDERSETS (CS) 与 RESOLVEMARKOVBLANKETS_GROWSHRINK 以及 PC 的一个修改版本进行比较，其中正在构建的图用道德图初始化（而不是原始 PC 版本中的完全图）。这正好代表了另外两种算法可用的马尔可夫毯信息，并允许直接比较。请注意，我们观察的是 PC 在约束传播步骤构建最大定向 PDAG 之前获得的 PDAG，这样在所有三种测试算法中，我们只期望 V 型结构被定向。

修改后的 PC 算法的结果仅为了比较而显示：PC 是一种通用算法，并不专门针对给定马尔可夫毯的这种局部结构识别。然而，比较表明，只要这种马尔可夫毯信息可用或获取成本低廉，就有更高效的方法。

GS(1) 和 GS(2) 在所有得分上都很接近，并且在测试次数上（高出几个数量级）以及在条件集的平均和最大大小上（显著地）优于 PC（除了用星号标记的人工结果外），因为它更好地利用了马尔可夫毯信息。然而，我们的方法在测试次数上比 GS(1) 和 GS(2) 好一个数量级，同时在所有测试网络中仍然使用更小的平均和最大条件集大小。尤其引人注目的是在 Carpo 网络上的结果：这是一个 CS 通过忽略大量不属于三角形的链接而节省大量时间的例子，而 GS(1) 和 GS(2) 也会检查那些链接，且马尔可夫毯通常很大（图 7）。

首先，我们看到在测试次数和条件集大小方面，我们得到了与表 1 相似的结果：CS 更快，并且始终执行更少的测试且条件集更小，这导致检验效力增加。然而，这有时被以下事实所抵消：CS 依赖单一系列的测试来同时移除配偶链接并定向（可能多个）V 型结构，因此如果测试结果相对于初始图是错误的，就会导致更大的惩罚。

我们看到 GS(1) 和 PC 在某些弧得分上可以击败 CS；特别是 PC，在这些实验中非常擅长避免弧定向错误。GS(1) 不仅检查三角形链接，还检查所有链接以尝试定向它们，这会犯更多的定向错误，尤其是在 Carpo 网络上。PC 往往比 CS 遗漏更多的弧，而 CS 又比 GS(1) 遗漏更多。但总的来说，CS 在 Insurance、Hailfinder 和 Carpo 上显著击败 GS(1)，同时在 Alarm 上表现略好，在 Diabetes 上表现略逊。基于这些结果，我们现在将使用我们的碰撞集搜索作为首选方法，在下一系列实验中分解马尔可夫毯。

5.3 基于 RFE 的方法

5.4 TC 和 TC_bw 与竞争方法的对比

对于这个系列的实验，我们对从 Alarm、Insurance、Hailfinder、Carpo 和 Diabetes 采样的数据集上，对 TC、TC_bw、PC、完整的 GS 以及 Bach-Jordan 方法进行了更系统的测试，并改变了样本量。Bach-Jordan 方法由基于 Mercer 核的评分函数加上在 DAG 空间中的贪婪搜索组成，旨在学习贝叶斯网络。它不保证在大样本极限下尊重因果图的形式语义，但为了比较起见，还是被纳入了实验。其他可能的竞争者，如 SCA (Friedman et al., 2000) 或 AlgorithmMB (Peña et al., 2005)，是不适用的，因为将它们推广到处理连续变量所需的技术在计算上过于昂贵，特别是因为基于评分的子程序难以推广。

与之前一样，结构误差是指返回的 CPDAG 中相对于生成图的缺失弧、额外弧和反转弧。对于 Bach-Jordan 方法，类似于 Fu (2005) 中所做的，我们在检查结构误差之前，首先将返回的 DAG 转换为其基本图（essential graph），以避免惩罚统计等价的结构。对于所有实验，我们还比较了 TC、TC_bw、GS 和 PC 的运行时间及执行的测试次数。

5.4.1 ALARM

第 1330 页的图展示了 Alarm 网络的结构误差、运行时间和统计检验次数与样本数量的关系。对于每个样本量，从模型中抽取了 5 个数据集；误差棒描绘了这 5 次运行的标准差。

随着样本数量的增加，所有算法的额外链接和缺失链接的数量平均而言似乎都明显减少，但 Bach-Jordan 除外，它有时在数据点更多时倾向于添加更多链接。请注意，Bach-Jordan 的 σ σ在最后两次运行之间发生了变化，这解释了额外弧的突然变化。反转弧的数量似乎不那么令人满意，特别是对于 TC。解释是 TC 在低样本量下遗漏了许多弧，因此实际上没有机会在这些情况下犯许多方向性错误。TC_bw 表现出相关的行为，尽管要弱得多。我们还看到 Bach-Jordan 犯的方向性错误最多（这实际上对所有网络都成立）。GS 在 n > 1000 时反复达到零额外弧得分，尽管它比其他算法遗漏得更多。

从大约 200 个样本开始，TC 等于或优于 PC、GS 和 Bach-Jordan。TC_bw 击败了 TC 和 PC，并且 TC 和 TC_bw 的收敛曲线表明，在大约 400 个样本时，逐步回归变得不必要。平均而言，TC 比我们使用的 PC 实现快约 20 倍，尽管这个倍数随着样本量的增加而趋于减小。TC_bw 自然比 TC 慢，但与 PC 的速度差异相比，这只是微不足道的。

总体而言，对于 n > 400 ，基于约束的方法表现大致相同，并且对于低样本量，TC_bw 和 GS 的表现略好于 PC。请注意，对于低样本量，TC 总是被 TC_bw、PC 和 GS 超越，但当样本量变大时，它通常表现最好。图 12 中的图表显示 TC 和 TC_bw 最快，尽管 GS 执行的测试次数少于 TC_bw。

5.4.2 INSURANCE

对于这个网络，我们发现了与 Alarm 相似的行为，如第 1331 页的图表所示。最显著的差异是，对于这个连接更密集的网络，Bach-Jordan 有明显的倾向在更多数据可用时添加更多弧。在第 5 和第 6 个样本量之间， σ σ再次发生了变化。比较缺失弧和额外弧的曲线，我们看到这改变了假阴性和假阳性之间的权衡。

5.4.6 讨论

当样本量超过一两千时（具体取决于网络），TC 和 TC_bw 都略微但持续地击败了其他竞争者。它们在低样本量下通常较弱，因为会遗漏弧。GS 在小数据集上击败了 TC，这是因为 PC 为统计检验遍历条件集的方式（Tsamardinos et al., 2006 在离散变量的检验案例中详细讨论了这一特定问题）。基于评分的 Bach-Jordan 方法被发现在调整参数 σ σ方面很困难。对于这种多变量高斯情况，其性能通常比测试的其他算法更差。这也反映了 PC、GS、TC 和 TC_bw 配合 z z检验都是针对多变量高斯数据“调优”过的事实。Bach-Jordan 所犯的额外错误反映了为了更具通用性而付出的代价。

研究哪种高度数结构更可能出现是很有趣的。如果它是一个有许多子节点的节点（如 Hailfinder 中的节点 27），我们称之为爆炸模式（explosion pattern），TC 可以高效地处理它。如果它是一个有许多父节点的节点，即内爆模式（implosion pattern），那么这些算法都无法在多项式时间内识别它。爆炸模式对应于一个有许多效应的单一原因；内爆模式对应于导致同一效应的许多原因。关于哪一种更可能出现在现实生活数据集中，仍有待讨论。

GS 在小样本量下无法被击败。对于 TC 和 TC_bw 来说，处理变量数量超过样本数量的问题（如基因表达网络）仍然是一个未解决的挑战，这导致试图求逆一个不满秩的矩阵。正则化协方差矩阵可能有助于使 TC_bw 在这种情况下更稳健。在计算上，TC_bw 确实比 TC 增加了一个复杂度阶数，并且 TC_bw 执行的测试次数通常与 GS 相当。

TC_bw 有助于解决 TC 和小数据集的问题，但仍无法在 n = d 阈值以下运行。TC_bw 停止优于 TC 的确切样本量似乎不是 n n或 d d的简单函数，而是取决于网络的结构。研究 TC_bw 的特征选择添加何时变得无关紧要将是有用的。由于 GS 在小样本量下更准确，找到一个类似的可测试条件来预测 TC 比 GS 更准确的阈值，将允许将这些方法合并为一个单一算法，该算法知道使用哪种马尔可夫毯方法以获得更好的结果。

6. 结论

因果发现和特征选择密切相关：最优特征选择发现马尔可夫毯作为强相关特征的集合，而因果发现发现马尔可夫毯作为直接原因、直接结果以及直接结果的共同原因。通过对每个变量执行完美的特征选择，我们得到无向道德图作为因果图的近似。需要一个额外的步骤，即碰撞集识别，以便将马尔可夫毯转换为父节点、子节点和配偶节点。这一步在最坏情况下是指数级的，但只要图足够稀疏——这是许多算法的常见假设——实际上是高效的。我们提出了一种算法来完成这项任务，并将其与 Grow-Shrink 算法的类似步骤进行了有利的比较。

使用现有的后向特征消除（如 RFE）来确定马尔可夫毯，在大样本极限下消除了不相关变量，但仍然过于包容。必须进行全局校正，例如确保目标的所选马尔可夫毯中的变量在其自己选择的马尔可夫毯中也包含该目标。我们进行的实验证实，这种调整丢弃了大多数假阳性，从而暗示该方法在大样本极限下是一致的。主要的挑战是以高效的方式对所有变量执行特征选择。在多变量高斯假设下，这项任务是可处理的。我们提出了 TC 和 TC_bw 算法，它们符合所描述的框架，并将它们与 PC、GS 以及一种贝叶斯结构学习方法进行了比较。对于小样本量，GS 通常犯更少的结构错误，而 TC/TC_bw 更适合较大的样本量。

我们确信本文所述的马尔可夫毯方法具有优越性。我们援引 PC 的高运行时间，以及 GS 和 TC/TC_bw 分别在低样本量和高样本量下的良好准确性，作为这一主张的支持。马尔可夫毯技术不仅更具可扩展性，而且可以更准确；它们也更容易修改，以仅构建被某种标准认为相关的网络部分。

我们现在在因果结构学习方面面临的最大挑战包括：针对连续且可能高度非线性的数据，进行稳健且一致的无分布结构学习。未来，我们打算利用这个框架来开发此类技术，从而试图摆脱高斯假设——该假设在现实生活数据集中通常不切实际。

原文链接：https://jmlr.org/papers/volume9/pellet08a/pellet08a.pdf