面向最优特征选择的推测性马尔可夫毯发现

Speculative Markov Blanket Discovery for Optimal Feature Selection

面向最优特征选择的推测性马尔可夫毯发现

https://www.cs.cmu.edu/~dmarg/Papers/Yaramakala-Margaritis-ICDM05-with-header.pdf

摘要

在本文中，我们探讨了如何以高效的方式从数据中学习某个量的马尔可夫毯这一问题。马尔可夫毯发现可用于特征选择问题，以找到分类任务的最优特征集，并且是数据挖掘中常用的预处理阶段，尤其是在高维领域。我们的贡献是一种用于从数据中归纳马尔可夫毯的新颖算法，称为 Fast-IAMB，它采用了一种启发式方法来快速恢复马尔可夫毯。实证结果表明，在许多情况下，Fast-IAMB 比现有算法更快、更可靠，且不会对恢复的马尔可夫毯的准确性产生不利影响。

1. 引言

工程师或研究人员经常对一组观测数据中的某一个特定属性感兴趣。为了分析并可能预测该属性的值，他或她需要首先确定该领域中哪些其他属性会影响它。这项任务通常被称为特征选择问题。该问题的解决方案通常并非微不足道，并且当领域由大量属性定义时，可能会变得不可行。

特征选择问题的一个有原则的解决方案是确定一个属性子集，该子集能够“屏蔽”（使独立）感兴趣的属性，使其免受领域中其余属性的影响。Koller 和 Sahami [4] 首次表明，给定目标属性的马尔可夫毯是预测其值的理论上最优的属性集。

因为目标属性 T 的马尔可夫毯使其在统计上独立于所有其余属性（见下文马尔可夫毯的定义），所以所有可能影响其值的信息都存储在马尔可夫毯属性的值中。特征集中任何位于其马尔可夫毯之外的属性都可以从特征集中被有效忽略，而不会对预测 T 值的任何分类器的性能产生不利影响。

在本文中，我们假设数据是由一个单一的忠诚有向图模型（即贝叶斯网络）生成的，该模型对领域进行建模。贝叶斯网络是一种统计模型，能够以图形方式表示领域中成立的独立性 [6]。忠诚贝叶斯网络的存在（见下文忠诚性的定义）意味着领域中任何属性的马尔可夫毯都是唯一的，并且可以很容易地从网络结构中“读出”：一个属性的马尔可夫毯是由贝叶斯网络的图结构所编码的父节点、子节点和配偶（即共同子节点的父节点）的集合。例如，本段开头的图展示了一个由五个属性组成的贝叶斯网络。属性 Cancer（癌症）的马尔可夫毯是集合 {Exposure to Toxics（接触有毒物质），Smoking（吸烟），Serum Calcium（血清钙），Lung Tumor（肺部肿瘤）}（图中灰色的节点）。这个集合使 Cancer免受其外部属性的影响。

定义 2（忠诚性）。贝叶斯网络 B 和联合分布 P 相互忠诚，当且仅当由 B B的图所蕴含的每一个条件独立性也存在于 P 中，即，

本文的目标是开发一种从数据中发现马尔可夫毯的快速算法。我们强调，我们在此并不处理贝叶斯网络结构发现问题——马尔可夫毯的发现是在不确定底层贝叶斯网络结构的情况下进行的。

2. 相关工作

Margaritis 和 Thrun [5] 提出了第一个可证明正确的算法，该算法在特定假设下（见下文）从数据中发现属性的马尔可夫毯。Grow-Shrink 马尔可夫毯算法（GSBN）是一种贝叶斯网络结构归纳算法，它作为第一步，为领域中的每个属性调用 Grow-Shrink 马尔可夫毯算法（称为 GSMB）。然后，它利用恢复出的马尔可夫毯的知识，使实际的贝叶斯网络结构发现更加高效。正如其名称所暗示的，GS 马尔可夫毯算法包含两个阶段：增长阶段和收缩阶段。

GSMB 算法具有一个理想的特性：在特定假设下，它是可证明可靠的，即它可以恢复领域中任何给定属性的精确马尔可夫毯。所做的假设是：(i) 所考虑的领域存在一个忠诚贝叶斯网络（这意味着毯的存在性和唯一性，见上文定理 1）；以及 (ii) 条件独立性检验是正确的。

Tsamardinos、Aliferis 和 Statnikov [7] 描述了 GSMB 的若干变体，旨在提高速度和可靠性。我们在此评估增量关联马尔可夫毯（IAMB）和交错 IAMB（Inter-IAMB）算法。与 GSMB 一样，IAMB 和 Inter-IAMB 算法也使用两阶段方法来发现马尔可夫毯。然而，在增长阶段，每当一个新属性进入毯时，它们会重新排列属性集。这种重新排列是使用信息论启发式函数 h （条件互信息）来完成的。其动机是，IAMB 及其变体可能会有更好的表现，因为（有望）在增长阶段添加的假阳性会更少（而这些假阳性原本必须在收缩阶段被移除）。

3. Fast-IAMB 算法

在本节中，我们提出了一种用于马尔可夫毯发现的新算法，称为 Fast-IAMB。Fast-IAMB 算法如图 1 所示。

剩下的一个实际问题是：如果每个剩余属性的平均每单元格实例数都小于 k k，该怎么办？Tsamardinos 和 Aliferis [7] 在描述 IAMB 和 Inter-IAMB 时没有提及这个重要的实际问题。有两种选择：假设依赖或假设独立。虽然假设依赖似乎可能是“安全”的选择，但在实践中，这会导致产生难以证明且几乎没有实际用途的大型马尔可夫毯。因此，当等式 (2) 中的条件不满足时，我们假设独立并停止（第 22 行），返回当前的马尔可夫毯。正如我们的实验所证实的那样，与 IAMB 和 Inter-IAMB 相比，这不会对 Fast-IAMB 的性能产生不利影响。

4. 实验结果

为了从经验上比较 Fast-IAMB 与其他马尔可夫毯发现算法的性能，我们在合成数据集和真实世界数据集上进行了一系列实验，列举如下。

HAILFINDER20K 是一个合成数据集，而 ADULT [3] 和 CENSUS-INCOME [2] 都是著名的真实世界数据集，包含人口统计信息。

图 2（顶行）显示，在几乎所有情况下，Fast-IAMB 所需的条件独立性检验次数都少于 IAMB 或 Inter-IAMB。检验次数直接影响每个算法的执行时间（如预期的那样），如图 3 所示。从该图中可以验证，Fast-IAMB 在所有数据集上都比 IAMB 和 Inter-IAMB 执行得更快：Fast-IAMB 的运行时间是 IAMB 执行时间的 68% 到 82%，是 Inter-IAMB 的 52% 到 72%。

图 2（中间行）显示，通过 T T与马尔可夫毯外所有属性之间的期望条件 KL 散度来衡量，Fast-IAMB 发现的马尔可夫毯与 IAMB 和 Inter-IAMB 发现的马尔可夫毯大致一样好。这使得 Fast-IAMB 发现的马尔可夫毯可以在与 IAMB 和 Inter-IAMB 相当的场景中使用。

图 2（底行）显示了条件集大小的分布，其中大小以条件集中属性的数量来衡量。一般来说，条件化是不理想的，因为它通常会导致独立性检验的可靠性降低。从图中可以看出，虽然所有三种算法的无条件检验次数相当，但 Fast-IAMB 执行的条件检验次数显著少于 IAMB 和 Inter-IAMB，这表明检验可靠性有所提高。

5. 结论与未来研究

本文的主要贡献是一种从数据中归纳马尔可夫毯的新颖算法，称为 Fast-IAMB，它采用推测来更快地恢复马尔可夫毯。我们的实证结果表明，Fast-IAMB 通常比现有算法更快、更可靠，且不会对恢复的马尔可夫毯的准确性产生不利影响。未来潜在研究的一个方向是放宽对忠诚底层贝叶斯网络存在性的要求（这在实践中可能难以确定），同时保持所恢复的马尔可夫毯在特征选择方面的理论最优性。

原文链接：https://www.cs.cmu.edu/~dmarg/Papers/Yaramakala-Margaritis-ICDM05-with-header.pdf