马尔科夫毯学习算法综述

1、 马尔科夫毯学习算法研究和进展*傅顺开，Sein Minn (华侨大学 计算机科学与技术学院,省市 361021） 摘 要:马尔科夫毯（MB）在贝叶斯网络（BN）研究中较早被认识和定义，它是BN拓扑结构的重要组成部分。在1996年被证明是预测目标变量的最优特征子集。给定全局BN可以很容易推导出特定变量的MB，但BN结构的学习已知是NP问题。回顾了从1996年至今关于MB学习算法的17个典型工作，包括 (1) 基于MB的全局条件独立特征的KS、IAMB等8个算法，(2) 利用MB的局部条件独立特征的PCMB、IPC-MB等6个算法, （3）基于逻辑回归分析+局部条件独体特征的RA-MMMB算法，

2、和 (4) 基于评分-搜索方法的DMB和RPDMB两个算法。讨论时兼顾理论和实用性容，并统一/扩展了相关算法的伪代码（描述），对学术界和工业界研究人员都具参考价值。关键词:马尔科夫毯; 贝叶斯网络；约束学习； 特征选择中图分类号:TP391 文献标志码: A 文章编号：（作者可不填）doi:10.3969/j.issn.1001-3695 (作者可不填)A Review of Markov Blanket Induction AlgorithmsFUShun-kai, SEIN Minn(College of Computer Science and Technology, Huaqiao U

3、niversity, Xiamen Fujian 361021, China)Abstract: Markov blanket (MB) has been realized and defined during the research of Bayesian network, and it is an important component of the BN. In 1996, it was proved the optimal feature subset for prediction. Given the global BN, it is trivial to read off the

4、 MB of specific variable, but the structure learning of BN is known as NP-hard problem. From 1996 on, there are many published works on the induction of MB, and our review covers 17 typical works, including (1) those based on the global conditional independence (CI) probability feature of MB, like K

5、S, IAMB etc., (2) those based on the local CI probability feature, such as PCMB, IPC-MB etc., (3) one work with the combination of logistic regression and constraint learning, called RA-MMMB, and (4) non-constraint learning works based on score-and-search, DMB and RPDMB. Our discussion covers theore

6、tical as well as practical aspect, and we revise the pseudo codes of related algorithms to easier the understanding. It is believed a useful reference for both academic and industrial colleagues.Key words: Markov blanket;Bayesian network; constraint learning;dimension reduction; feature selection9 /

7、 91 引言贝叶斯网络（Bayesian Network, BN）是一种有向无环图（DAG）模型，其中节点代表了随机变量，而边代表了随机变量之间的概率关系。基于条件独立性，BN的图模型能够有效紧凑表达目标问题的联合概率关系，并可以通过贝叶斯链式法则来快速实现从图表征语言到公式的相互转换。BN是人工智能领域的一种重要工具，被成功运用到机器学习和数据挖掘领域。早在1988年，Peal就在他的关于贝叶斯网络研究的专著1里定义和讨论了马尔科夫毯（Markov Blanket，MB）。给定一个节点，它的MB是唯一的，包括的所有父、子和配偶（和有共同孩子的）节点（见图1）。当MB的（所有）节点的值确定后，

8、的值可以被确定。虽然该性质被较早认识到，但直到1996年才由Koller和Sahami（简称K&S）两位斯坦福大学的学者将MB和特征选择（feature selection）关联起来2，而特征选择是机器学习和数据挖掘领域重要的预处理步骤之一。K&S从信息论角度首次证明了MB是预测目标变量的最优子集 - 不包含无关（irrelevant）和冗余（redundant）变量。特征选择通过降低输入维度而让随后的学习器所面临的求解搜索空间的复杂度大大降低，这既提高了求解效率，也减小出现过拟合现象的可能性。同时，降维还能为数据采集、存储、传输和预处理带来可观的（时间和经济）成本节约。当然，理想的特征选择是

9、在保证以上收益的同时不牺牲模型的预测能力。当已知BN（的结构），我们可以很容易“读出”目标节点（变量）的MB。然而，推导BN的结构被公认是NP问题3，已知的需要自动推导BN的应用一般只包含数十个变量4。王双成等的工作显示了基于马尔科夫毯的预测由于TAN、朴素贝叶斯和BN，但仍然需要先学习完整的BN5。K&S在1996年发表的著作里除了证明MB的重要性质，也讨论了MB的推导策略。为了保证搜索效率，他们提出了一个近似的学习算法。作者并没有为其命名，为了引用方便本文简称其为K&S算法。K&S算法无法保证一定输出正确的马尔科夫毯2。图 1 贝叶斯网络和T的马尔科夫毯（灰色节点）示例。X1，X2为T的父

10、节点，X3，X4 为T的子节点，X5，X6为T的配偶节点。X3，X4，Y3 为T的后代节点，剩下的为T的非后代节点基于Google Scholar的统计数据和我们对搜索结果的人工整理，在19962013期间至少有超过100篇的比较重要的关于马尔科夫毯推导和应用的学术论文，其中不乏发表在包括JMLR（Journal of Machine Learning Research）、DMKD（Data Mining and Knowledge Discovery）、ICML、KDD、ECMLPKDD、AAAI、PAKDD等顶级期刊和学术会议上。K&S的1996年的开创性论文2更是获得了超过1260次的引

11、用（截止准备本文时）。以上事实和数字直接反映了该研究方向的重要性，但国相关的研究成果甚少（查新过程中只发现两篇相关的工作），这推动我们撰写本文将相关研究进展向国同行介绍。在文中，我们将拣选出已发表的工作有代表性的算法进行分类，并从理论和实用维度分别给予介绍和讨论，相信这将有助于同行研究人员和工业界应用者的参考。2 符号、概念、算法分类和讨论维度2.1 符号表示采用粗体罗马字母表示变量集合（比如），非粗体的斜体罗马字母表示单个变量（比如），对应的小写罗马字母表示变量值（比如，）。对于一个分布，采用表示给定条件集时，与是相互独立的。若条件集（为空），使用表示。为了简化表示，在考虑单个变量时，都忽略

12、标准的集合表示。比如，采用表示。类似地，使用来表示在图模型中节点之间的条件独立关系。2.2 贝叶斯网络和理论基础给定变量集合，对应的贝叶斯网络是个二元组，。其中，是一个有向无环图：节点集合对应，边集合蕴含了拓扑关系。任意节点的父、子和配偶节点集合分别记为、和，而父子节点又常合并表示为。参数包含诸如这样的条件概率分布（当变量取连续值时对应条件概率分布函数，而变量取离散值时对应条件概率表），它“定量地”给出当父节点集合取值为时，他们共同的子节点取值的条件概率。没有父节点的用先验概率进行信息表达。本文中，“变量”和“节点”将混合使用。给定贝叶斯网络，其所表示的联合概率分布可以根据所包含的信息因式分解

13、为: (1)贝叶斯网络中任意相连的三个节点，和存在三种可能的连接场景，（1）（简称“顺序接接”），（2）（简称“尾部连接”），（3）（简称“头部连接”或“结构”）。图中任意存在路径（即连接两个节点的边集合）的两个节点之间的边都可以分解为这三种结构。例如图1中的是连接和的路径，但不是唯一的路径，因为还存在路径。能够割断两个节点之间所有路径的最小节点集合称作最小“割集”（seperator），例如图1中和的最小割集是空集。割集对应到中的。为了讨论方便，在此简要介绍一些基础概念和定理。定义1忠实性（Faithfulness）。一个贝叶斯网络和一个联合分布是相互忠实的，当且仅当蕴含在的结构里的每一个条

14、件独立性关系也同样存在于中，即。1定义2马尔科夫毯。一个变量的马尔科夫毯记为，它是满足以下条件的变量集合：，（2）而其中最小的马尔科夫毯称为马尔科夫边界（Markov boundary）。定理1 假定忠实性满足，对应于联合分布的贝叶斯网络的结构，（1）任意节点的马尔科夫毯是唯一的，包含其父、子和配偶节点（参考图1），（2），。引理1假定忠实性满足，（1）一个变量的马尔科夫毯和其马尔科夫边界是一致的，（2）的父、子和配偶节点组成了最优特征子集。（根据定义2和定理1容易证明）定理2 两个有向无环图是等价的，当且仅当他们有一样的无向图和一样的结构。定义3 后代（Descendant）。贝叶斯网络中，

15、如果存在一条从到的有向边，但不存在从到的有限边，那么就说是的后代。的后代节点集记为。定义4 非后代（Non-Descendant）。贝叶斯网络中，的除了后代节点的其他节点集称作非后代节点集，记为。定理3如果一个贝叶斯网络忠实于联合概率分布，那么和在中是直接相连接的，当且仅当对于任何不包含和的集合，恒不成立。定义4 马尔科夫条件（Markov condition）。在一个贝叶斯网络中，当已知，任意的除外的非后代节点条件独立于，(3)当忠实性满足，我们容易得：，(4)2.3 算法特征和分类参考贝叶斯网络结构学习算法分类方法，我们将已发表的推导算法分为约束和非约束学习。所谓约束学习（Constrai

16、nt Learning，CL），属于求解经典的约束满足问题（Constraint Satisfaction Problems, CSP）。CL类算法普遍基于条件独立（简称CI）测试，而在实际应用中用于训练的数据样本数目相对于问题特征所构成的高维度空间十分稀疏有限。例如一个应用包含16个二值特征变量，可能的值组合是。如果把每个组合看成一个单元格，当我们拥有1024（）个样本，意味着至多1.56%的单元格能分配到一个观测值；即便观测样本数提高一个量级，也只是覆盖了不超过15.6%的区域。当面对更多的特征变量，并且每个变量可能的取值不止两个，问题空间的复杂度将呈指数级增长。目前通用的统计测试可靠性判

17、断标准是要求每个单元格至少具备5个观测值6，这意味着面对16个二值特征变量时，即使我们有51200个样本也只是覆盖不超过16%的组合。当样本数不够时，统计测试的结果变得不可靠。如果“强行”信任测试结果，将引入错误的决策；而任何早期引入的错误将导致更多的“级联”错误，最终输出不佳甚至极差的结果。实际应用里，一般会预先进行类似每单元格至少5个样本的检查（简称“可靠性测试”），如果该条件不满足，该统计测试将被放弃。这个措施的后果是当没有更多可靠的测试可以被进行时，CL算法不得不提前结束搜索。非约束学习的典型策略是基于打分+搜索（Scoring +Search-based，S&S） - 基于一个预定义

18、的打分规则（很多选择，比如MDL、BDeu等4），以与一个启发式技术（比如爬山、退火等），迭代修改当前状态直至某个搜索停止条件（比如新的状态得分比上一个装填得分差）满足并输出结果。到目前为止，关于推导马尔科夫毯的工作普遍属于约束学习，这可以归结为两个缘由：n 我们能够清晰定义出目标 - 马尔科夫毯的概率和拓扑特征信息，这两部分信息的联合有助于定义有效学习的约束条件。具体来说，这两个信息让我们能够识别出马尔科夫真元素或/和假正（false positive）元素；n 然而，这两个信息并不会帮助到我们建立局部和全局得分之间的关联。具体来说，我们在不了解局部结构（这恰是我们希望推导的）的前提下，无法

19、准确推导局部得分，只有从全局得分入手。而全局得分的提高无法保证所关注的特定变量的局部得分也提高。即使我们能找到这个关联，学习全局结构的代价也将让我们望而却步。因此，虽然基于S&S的学习策略在BN的推导上获得了更大成功，在MB推导上目前尚没有有效的实施手段，鲜有相关研究的发表。在回顾已知的工作时，我们将按约束和非约束区分，而前者相关的工作更多，故篇幅占用也更多。已知基于约束学习的算法可进一步分成两大类：n 基于马尔科夫毯的条件独立（CI）特性设计的算法。该类算法直接寻找目标和非集合的“割集”，即依据公式（2）。此类算法的搜索策略简单、时间效率高，但实际应用时学习效果不佳。K&S算法可以算是此类算

20、法最早的一个工作，而引用频次相当高的IAMB也是属于该类。n 基于拓扑信息设计的算法。此类算法检查单独的和之间的条件独立关系，所需要的条件集合（或割集）通常比要小许多，因此条件独立测试的可信度提高，学习效果相对更高。该类算法的第突破性工作出现在2003年左右7。2.4 挑选标准和讨论维度我们将从约束和非约束类别里分别挑选出开创性和/或里程碑的工作，尽量做到不遗漏典型贡献。针对每个算法，将从几个维度进行讨论：n 提出背景和假设n 核心学习/搜索策略n 理论正确与否n 学习效率n 学习效果（又称数据效率、样本效率）n 实用性n 输出的信息n 可提高方向考虑到讨论方便、自包含以与实用参考价值，将整理

21、并附上重要的算法伪代码（片段）。伪代码描述将忠实反映原工作，但统一相关变量符号，并做必要扩展细化。3 约束学习I：基于全局条件独立信息的搜索3.1 K&S算法算法K&S2在1996发表在ICML年会上。作者K&S认为我们不可能拥有能完全预测目标的所有特征（实际情况是我们也不知道全集是什么，这导致我们不但不可能拥有所有特征，甚至很有可能包含错误的特征），因此预测问题演变为特征变量集合和目标变量的条件概率分布建模，。当给定一组观测值，预测变成了选择能最大化的。如果我们希望找一个能“代表”的子集，理想的选择是基于的条件分布接近于，即。信息熵衡量一个分布的不确定性，信息互熵（cross-entropy

22、）则衡量两个分布和的“距离”，。作者K&S从信息熵和互熵角度证明了是最理想的子集，即比任何其他的都更接近。K&S的工作和Singh和Provan发表在1996年ICML的另一个工作8类似，后者尝试基于选择的特征子集来训练贝叶斯网络分类器，而在选择标准上也利用了信息熵。在理论的实践上，作者K&S也讨论了前向（forward）和后向选择（backward selection）哪种搜索策略更适合马尔科夫毯的推导。文献8提出的算法是基于前向选择，从空集合开始，每次选择一个能带来最大信息增益的变量直到没有更多增益能获得。K&S认为该选择策略过于贪婪，很可能将搜寻导向错误的方向。因此，算法K&S选择了基于

23、后向选择的搜索策略 - 从特征全集开始，每次挑选并删除满足的变量，直到没有更多变量可挑选。K&S算法需要两个参数，（1）要保留多少个变量，即预测，（2）条件独立测试里的允许的最大。两条件中任一个满足时，搜索即停止，而此时所得的即认为是目标马尔科夫毯。显然，我们事先并无法预知目标马尔科夫毯的大小，如果将参数设置过大，时间效率将因为搜索可尽早结束而提高，但输出的不准确。关于第二个参数，如果设置较小，算法将从两个方面受益：（1）条件独立测试的可靠性更高，（2）时间复杂度降低。但随之而来的代价是无法“删除”所有非元素，从而无法输出准确的。所以，K&S算法是近似的，无法保证一定输出准确的马尔科夫毯。即便

24、该算法只能实现近似推导，K&S的工作仍被视为该研究方向的开山之作。K&S算法的搜索策略也被后继同类算法所参考，而其自身的缺陷也被加以重视和避免。3.2 GSMB算法GS算法9首次发表于1999年的NIPS会议上，作者希望借助“经济”的局部（邻居）推导，之后“整合”这些局部结构信息以获得完整的贝叶斯网络。这里的“局部结构信息”即指马尔科夫毯，而该推导策略在当时相比于传统的全局推导是一个创新。我们在这里只关心该工作里的核心部分 算法GSMB（Grow-Shrink based Markov Blanket induction），它负责推导具体变量的马尔科夫毯。其推导过程由两个步骤组成：先增长（Gr

25、ow），后裁剪（Shrink），因此得名。增长阶段执行的是贪婪的启发策略，基于发现的候选马尔科夫毯集合做条件独立测试，只要发现一个变量和目标变量关于条件独立，则认为为新的马尔科夫毯候选元素并添加中。该策略导致增长阶段结束时会包含一些假正（False positive）元素，因此需要随后的裁剪阶段里检查每个的元素，找出并删除假正变量。而这一步骤所基于的条件也直接明了 任何一个中的元素如果和目标变量关于条件独立，则可以将删除；迭代执行这个过程，直到中没有这样的存在 输出的即我们所要找的。GSMB算法属于约束学习，将受到CI测试（即）准确性的影响。在假设CI测试准确的前提下，GSMB算法可被证明为正

26、确的。该算法简单易实现，学习效率高，时间复杂度属于层级。但是，该算法在实际应用中的推导准确率表现可能很差。在增长阶段，由于配偶节点较晚进入导致可能引入错误的节点。而一旦有错误节点被引入（算法1的第6行），将持续误导随后迭代里的判断并引入更多的假正进。直接的后果是大大降低后面的测试的可靠性，当再无可靠的CI测试可参考，搜索将不得不停止，而此时很可能不但包含假正，还仅只有部分的马尔科夫毯元素；即使在裁剪步骤里能够删除全部的假正，最终输出的依旧是不完整的马尔科夫毯。这个由于CI测试里所涉与的变量（或自由度freedom）太多而导致每个取值组合的可用观测值数目可能很少，甚至为0，引发测试不可靠甚至（严

27、重）影响统计学习的现象称为数据/样本效率（Data/Sample efficiency）问题。给定同样的训练样本，如果算法A输出的准确率高于算法B，我们称算法A的数据效率更高。这是统计学习算法除了时间、空间效率之外，很重要的一个衡量指标。GS、IAMB以与他们的衍生算法由于固有的搜索策略局限，普遍数据效率不高10, 11。算法1：GS。输入： - 目标变量 - 数据集/训练集 - 显著性门限值输出：的马尔科夫毯01. ；/增长(Grow)阶段02. DO03. ;04. FOR() DO05. IF() THEN06. ;07. ; / 跳转到第3行08. BREAK;09. WHILE;/

28、裁剪(Shrink)阶段10. DO11. ;12. FOR() DO13. IF() THEN14. ;15. ; 16. BREAK; / 跳转到第11行17. WHILE;18. RETURN ;3.3 IAMB与其派生算法IAMB算法12首次发表于2003年，全名为Incremental Association Markov Blanket。它继承了GSMB算法的两步骤策略：先（贪婪）增长，后裁剪（假正元素）。裁剪阶段两者完全一致，增长阶段存在一个区别：IAMB会对通过CI测试的候选元素（参考GSMB算法第5行）进行排序，挑选出“最可能”的候选马尔科夫毯元素，即和目标变量条件依赖度最高

29、的。虽然这个选择过程依旧是贪婪决策，相比于GS更充分利用了当下的信息，因此降低了往添加假正元素的可能性。由于GSMB算法发表时是以学习贝叶斯网络为目标，而IAMB是专门针对推导马尔科夫毯提出的，所以后者在该方向的引用频次和知名度更高。IAMB继承了GSMB算法低数据效率的问题，例如，给定经典的Alarm问题，当给定一样的训练集大小（例如5000），IAMB算法输出的马尔科夫毯的平均准确率为49%，而IPC-MB算法为99%13。IAMB的作者也意识到这个问题，提出了三个“改良”版本：InterIAMB、IAMBnPC和InterIAMBnPC。InterIAMB将增长-裁剪两个阶段交替执行，而

30、原来的IAMB里，完全执行完增长阶段才开始执行裁剪阶段。IAMBnPC算法是将经典的PC算法应用于裁剪阶段，但它忽视了增长阶段所获得的有可能并不包含所有的元素，这将导致输出仍然不完整。当将这两个算法的思路合并后即为InterIAMBnPC，它的时间复杂度在这三个算法中最高。相比于IAMB，这三个算法的数据效率都有不同程度的提高，因此实际应用的准确率能得到提升，但是时间复杂度也有不同幅度的增加。3.4 Fast-IAMBFast-IAMB算法14发表于2005年的ICDM年会，它实际上是InterIAMB的升级版本。相比于InterIAMB，该算法有两个不同：n 条件独立性检查选择了统计；n 增

31、长阶段里每个迭代选择一个或多个变量添加到中。作者认为第二个策略的采用将提高时间效率，但这个更贪婪的策略将导致更多的假正元素被添加到，从而导致IAMB增长步骤已知的问题恶化 该步骤更早终止，且终止时包含更多的假正变量（自然包含更少的真元素）。3.5 K-IAMBK-IAMB和PCMB（在下章节里介绍）在2007被同时发表在文献15。其作者认为PCMB等（约束学习II类）算法所要求的忠实性假设过于严格，而IAMB算法的数据效率太低。K-IAMB实质是IAMB的一种随机版本，它允许算法使用者指定一个参数，该参数反映了对搜索贪婪度和随机性所能接受的一个“度”。当时，K-IAMB等价于IAMB，即在增长

32、阶段的每个迭代里总是选择当下和条件相关性最强的元素。当数据样本不充足时，这样的决策显然是有风险的。因此时，算法会从随机选择一个子集再执行类似算法1第5行的CI测试，并基于测试结果决策。3.6 -IAMB等算法-IAMB发表于2010年16，跟IAMB算法对比存在两个差异点。其一是作者通过使用信息熵，而非条件互信息，来降低衡量两个变量的条件独立性计算量。其二是算法希望一次选取多个候选变量进入，例如和目标变量相关性最高的两个变量，这和Fast-IAMB如出一辙。然而，为了降低风险，作者提出了参数（其实是门限值），当次相关变量和目标变量的相关性和最相关变量的相关性超过一定值时，方可同时被添加到。这个

33、二次检查的策略和K-IAMB类似。尽管较IAMB有一定的改善，Fast-IAMB、K-IAMB和-IAMB并没有在根本上解决此类算法的数据效率低的缺陷。4 约束学习II：基于局部条件独立信息的搜索在IAMB算法的追随者继续沿着那条路径前进的时候，有些人开始另辟蹊径来解决IAMB类算法的低数据效率的问题。他们的工作基础是贝叶斯网络DAG的拓扑信息，特别是“截断”两个节点的割集（的信息）。虽然是和之间的最小割集，但对于单独的和之间的割集往往远比小，例如图1的和的最小割集是空集，而包含六个元素。除了推导策略迥然不同，II类算法的输出相比I类算法存在一个巨大的优势：能推导出更多的拓扑信息。I类算法仅仅

34、告诉我们一个元素是否属于，而II类算法能(1)区分目标变量的父子和配偶集合,(2)从父子集合里分离出部分孩子（节点）,(3)一部分结构。4.1 MMPC/MB和HITON-PC/MB算法MMPC/MB算法17发表于2003年的ACM KDD年会，其第一作者和IAMB的一致，这间接反映了该作者也意思到IAMB算法的局限。MMPC全称是Max-Min Parents and Children，它的任务是推导特定变量的父子节点；MMMB的全称是Max-Min Markov Blanket，即推导一个变量的马尔科夫毯。MMMB依赖MMPC来完成马尔科夫毯的推导，这也是第一次将马尔科夫毯的推导分解成分别

35、推导父子节点和配偶节点。这个拆分策略将避免或出现在CI测试里，有助于提高CI测试的可靠性，继而让基于CI测试的结果所做的决策（比IAMB等）更准确。HITON-PC/MB算法7同样发表于2003年，它的总体策略和MMPC/MB如出一辙，为了节省篇幅不再单独熬述。MMPC/MB和HITON-PC/MB都是针对马尔科夫毯推导的重要尝试和突破，但更复杂的启发式策略也带来了高的多的计算代价。然而，在2007年这两个算法都被证明都无法恒保证输出正确的马尔科夫毯，有兴趣的读者可以参考文献15里提供的一个反例。鉴于此，我们在此为了节约篇幅都没有单独给出两个算法的伪代码，但他们的主要流程被PCMB和IPC-M

36、B所继承，读者可以参考算法3（IPC-MB）。4.2 PCMB算法PCMB算法15最初发表在2007年的Journal of Approximate Reasoning上，它的全称是Parents and Children based Markov Boundary。其作者同样意识到IAMB与其衍生算法在实际应用中的局限，并充分认可MMPC/MB和HITON-PC/MB的作者所提出从拓扑角度出发进行搜索策略的设计。虽然这个新的方向有贝叶斯网络研究者所积累的大量理论依据，但MMPC/MB和HITON-PC/MB两个具体算法都存在设计缺陷，这无法保证它们恒输出正确的结果。PCMB的作者首次在文献1

37、5中给出了反例，因而他们提出的PCMB属于“约束学习II”类已知发表的工作中首个能进行正确推导马尔科夫毯的算法。PCMB算法类似MMPC/MB和HITON-PC/MB，采用了分而治之的策略 分别学习父子节点和配偶节点。由于PCMB算法和随后将介绍的IPC-MB算法的主体架构相似，因此读者可以参考算法3来了解其总体设计。PCMB算法和IPC-MB算法的主要差别是RecognizePC（见算法2），该过程在原文献中即GetPCD。RecognizePC负责推导一个变量的候选父子集合，有可能输出后代节点。PCMB算法的RecognizePC实际是在IAMB的增长-裁剪过程前增加一个在候选集合里进行“

38、裁剪”的步骤，故总体上是SGS（Shrink-Grow-Shrink）。本质上，这是一个混合了后向和前向选择的搜索策略。然而，过度“谨慎”的检查导致PCMB算法时间复杂度甚高10, 11。算法2：RecognizePC（对应原PCMB文献中的GetPCD）。输入： - 目标变量 - 候选邻居 - 数据集/训练集 - 显著性门限值输出：的候选父子集合01. ; 02. DO/ 删除中的假正03. FOR() DO04. ;05. FOR() DO06. IF()THEN07. ; /添加最佳候选到08. ; 09. ;10. ;/从中删除假正11. FOR() DO12. ;13. FOR()

39、DO14. IF()THEN15. ;16. WHILE在本轮循环有改变;17. RETURN ;4.3 IPC-MB算法IPC-MB算法18最初发表在2007年的澳大利亚AI年会上，而提供了更完善证明的版本发表在2008年的加拿大人工智能年会上10。IPC-MB全称是Iterative Parent-Child based search of Markov Blanket。它同PCMB一样，基于拓扑信息设计，选择了分而治之的策略，通过迭代的推导父子节点（这一更局部的信息）来完成马尔科夫毯的推导。然而，在如何推导直接相连接的节点（父子节点）这个核心子策略上，IPC-MB选择了和PCMB完全不同

40、的策略：PCMB采用的是前向选择，而IPC-MB采用的是后向选择。PCMB的策略在上一节已经有介绍，此处着重介绍IPC-MB的后向选择。而关于前向和后向选择的孰优孰劣可以参考章节2.1里的简单讨论，更详细的讨论可以参考K&S的工作2。IPC-MB（见算法3）是依赖RecognizePC过程（见算法4）来完成对父子节点的判断。它的基本思路是当给定一个节点时，先假设其他的节点和都相连（即都为真的父子节点），随后通过一系列的CI测试来删除邻居集合里的假正元素，直到没有更多的CI测试可被执行。与PCMB算法判断一个元素是否为真的父子节点不同，判断假正元素的条件更为简单 只要存在一个关于节点和节点的割集

41、，即可判断为假正，并从里删除。在判断假正元素时，IPC-MB的作者从空集合开始判断其是否是和之间的割集；在第二个迭代里，允许割集合包含一个元素，并寻找可“割断”的变量；以此类推，直到没有更多的CI测试能够被执行。这个策略使得用于判断假正的CI测试总是能够基于最小的割集，充分保障了CI测试的可靠性。算法3：IPC-MB。输入： - 目标变量 - 数据集/训练集 - 显著性门限值输出：的马尔科夫毯01. ； /候选邻居02. RecognizePC(); /候选父子03. ;04. FOR()DO05. ;06. RecognizePC()07. IF () THE /删除假正08. ;09. E

42、LSE /发现真父子，并进一步推导配偶10. FOR(AND )DO11. IF()THEN12. ; /发现一个配偶13. RETURN;算法4：RecognizePC（IPC-MB版本）。输入： - 目标变量 - 候选邻居 - 数据集/训练集 - 显著性门限值输出：的候选父子集合14. ;15. ; /初始化CutSet Size16. DO17. FOR() DO18. FOR( with ) DO19. IF()THEN20. ; /假正父子21. ; /缓存供算法2使用22. BREAK; /跳转到第4行23. IF() THEN /统一删除假正24. ;25. ;26. ;27.

43、WHILE;28. RETURN ;IPC-MB算法被证明是正确的，其数据效率和PCMB相当，但它的时间效率比PCMB要高许多。例如在一个实验里它比PCMB节省了95%左右的CI测试次数10。虽然相比于IAMB的时间效率还是要低不少，但该算法在“瘦”网络（即网络连接不太稠密）问题里表现出与IAMB匹敌的时间效率但高得多的准确率。4.4 MBOR算法MBOR算法19发表于2008年的ECML/PKDD年会上，也是其作者在观察到GS和IAMB分支的算法数据效率不高后设计的，并声称结合了PCMB和IAMB的优点，并同时规避了他们的缺点。MBOR的全称是Markov Boundary search u

44、sing the OR condition。MBOR沿用了PCMB和IPC-MB的搜索策略，核心差异在于判断两个变量和是否相连的条件。PCMB和IPC-MB在判断时要求且（AND）都满足（算法4第7行），而MBOR只要求其中一个条件满足，即或（OR）。策略OR是一把双刃剑：真元素容易进入，而假正元素也不例外。MBOR算法的总体思路是依赖基于OR条件的弱学习器来构成能输出正确的强学习器，这个思想类似集成学习（ensemble learning）。MBOR算法由三个阶段组成：n 学习的超集。这是通过分别学习以与合并和的超集获得。（1）学习超集，算法设计了一个“粗糙”过滤策略 将CI测试的条件集合限

45、制为空集或包含一个变量。这个过程的输出为，而当发现可被删除的变量时，同IPC-MB一样记录对应的。（2）学习的超集，针对每一个不属于的，嵌套执行一个先增长-后裁剪的检查。增长步骤里，算法检查每个不属于的，如果能通过类似算法3第11行的测试（测试里的条件集合为），则认为是候选配偶，并添加到集合。这个步骤里，由于可能为空或包含一个变量，所以将包含至多2个变量。随后的裁剪步骤将检查和删除当前能识别的里的假正元素（不保证全部删除）。n 基于推导。原算法里这个阶段同样包含两个子步骤。第一个子步骤是从第一阶段获得的的超集中删除假正，而这个步骤和IAMB的裁剪步骤如出一辙。不同的是IAMB的裁剪步骤里，条件

46、子集是，而此处（作者没有明讲，但按经验以与作者重点关注数据效率上判断）选择的是满足条件的最小子集。我们判断作者的实现应该同IPC-MB的RecognizePC（算法4）过程，从空集开始迭代搜寻。第二个子步骤是针对每一个执行第一个子步骤并输出，如果属于的则将添加到，这是OR条件的贯彻。n 推导配偶。这个步骤同IPC-MB的配偶推导，但计算复杂度要高不少。MBOR算法为了保证数据效率而设计了弱而快的学习器，但为了保证准确性又不得不增加了繁琐的检查机制。作者并没有给出可信服的证明，而时间复杂度将高于IPC-MB。4.5 DOS算法DOS算法20发表在2011年的PAKDD年会上，全称是Dynamic

47、 Ordering-based Search，它充分参考之前的MMPC/MB、PCMB和IPC-MB。DOS算法的两个步骤如下：n 推导。这步对应IPC-MB（算法3）的第2行，作者在IPC-MB的RecognizePC（算法4）基础之上添加了一个微创新的启发策略。一旦发现可以变量和的割集，除了执行算法4的第22和23行的动作，作者对每个进行计数更新，并根据计数对他们按从高到低在排序。计数是根据出现在里的频次，作者认为里的的频次将较高。这个启发是合理的，因为满足这样条件的和直接相连，更可能出现在和的通路上，即更可能出现在里。这个信息将被用在从产生里，算法将优先选择包含高频次的（如果有多个则对频

48、次求和再比较大小）。n 推导并删除里的假正。该步骤和IPC-MB（算法3）的第412行完全一致。n DOS算法较IPC-MB参考了更多的拓扑信息，使得时间效率有可能获得提升。5 约束学习III：基于逻辑回归分析的过滤HITON-PC/MB和MMPC/MB算法已知无法保证正确的输出，但它们比约束学习I类的算法样本效率要高许多，也开创了新的学习策略。郭坤等人在2012年发表了名为RA-MMMB的算法21，全名为Regress Analysis Max Min Markov Blanket。该算法期望利用MMMB算法的样本效率优的特征进行特征全集的预过滤，得到候选的马尔科夫毯。随后建立目标变量与候选

49、马尔科夫毯的逻辑回归方程，基于逐步后向回归分析结果删除错误的和弱相关的变量（即所谓的兄弟节点 和目标节点同父节点）。作者的实验显示该算法优于MMMB，说明在删除假正节点上确实有效。然而，作者并没有给出算法的正确性证明。6 非约束学习前面两节介绍的算法都属于约束学习畴。虽然非约束学习算法在贝叶斯网络的结构学习研究领域有很多工作，但直到最近才由Acid等研究人员在2013年的DMKD杂志发表了一篇关于马尔科夫毯的非约束学习的文章22。作者在该文章里提出了两个算法，分别叫DMB和RPDMB。DMB和RPDMB算法使用常见的评分机制（例如BDeu等，关于他们的简短比较可以参考22），但通过将搜索局限在

50、一个特殊的图空间里来降低复杂度。由于作者的重心是应用贝叶斯网络于分类问题，这个图空间包含了所有和目标DAG分类等价（Classification equivalence）的DAGs，作者将其命名为C-DAG（Class-focused DAG）23。虽然这个空间相对于全局空间缩小很多，但仍然是一个指数增长的空间，故作者进一步应用了启发式搜索策略来加速学习。文献22中报告的实验结果显示RPDMB（配合BDeu和MIT两种评分机制）相比PCMB能够输出有竞争力的准确率的结果，但耗时要多许多。考虑到PCMB的时间效率比IPC-MB低许多，可以预测IPC-MB算法在时间效率上将远比RPDMB更有优势。

51、即便如此，DMB和RPDMB仍不失为一个重要的尝试。7 研究前景7.1 约束学习从既往已发表的工作来看，约束学习一般通过利用马尔科夫毯的条件独立性信息（I类）或拓扑信息（II类）来“约束”或“裁剪”搜索空间。虽然II类算法能够输出更准确的结果和更多的拓扑信息，但需要消耗更多的计算资源。未来的目标在保持高数据效率的前提下降低时间效率，但存在以下制约进一步提升的客观事实：n 如果我们选择前向选择策略，努力的方向是用最小的代价识别出真正的马尔科夫毯元素。然而，根据定理3，判断是否和目标变量相连的条件是要求不存在能让他们条件独立的集合。这要求进行“遍历”测试，可能的尝试是复用已经确认的元素信息来推导更

52、多的元素，而不是每个元素的判断都是从0开始。同时，还要避免CI测试里的条件集合过大；n 如果我们选择反向选择策略，努力的方向则是用最小的代价识别出假正元素。IPC-MB是基于这个目标设计的，并同时兼顾了CI测试里条件集合尽量小的目标。有两个问题目前影响该类算法的时间效率：（1）推导的父子节点集合时，后代节点可能会无法被正确删除，因而需要用到AND的检查策略，（2）配偶节点需要做间接鉴定。K-IAMB所采取的当数据样本不充足时的折中策略其实是进行二次验证，可以考虑在其他算法里尝试，毕竟相对样本不足是常态。RA-MMMB所采用的基于回归分析的二次过滤也是一个有趣的方向。或许可以尝试基于回归分析进行

53、“粗糙”地前置过滤，再基于更精细的推导算法进行二次过滤。7.2 非约束学习目前非约束学习的算法还相当稀少，从发表的两个算法来看，侧重分类问题，理解起来也相对比较复杂。鉴于S&S策略在贝叶斯网络学习上所获得的成功，以与马尔科夫毯和贝叶斯网络的关系，有理由相信其在马尔科夫毯推导上还有很大的空间可供挖掘。从前面的讨论可知：约束学习算法目标时间效率优于非约束学习算法，但面临统计测试不可靠以与级联出错的风险。IPC-MB、MBOR和DOS算法都尝试去极力让CI测试里的条件集合尽可能小。MBOR在其第一阶段的做法启发我们可否先用条件集合很小的CI测试做一个快速的粗过滤，这有助于我们快速裁剪搜索空间，输出一

54、个接近的超集。在这之上，我们再应用S&S策略来规避大条件集合CI测试所可能带来的问题。7.3 应用文中着重围绕特征选择问题讨论了马尔科夫毯，这归因于特征选择在整个机器学习和数据挖掘研究和应用中的重要基础角色。由于马尔科夫毯是贝叶斯网络的重要局部结构，可以通过先推导出该信息而获得全局贝叶斯网络，例如9, 24。考虑到局部推导可以并行化，运行等待时间将有可能获得较大缩短。此外，相关的工作也可能应用于局部因果关系的推导25。结束语马尔科夫毯从1996年被证明是预测目标的最优子集后，至今有众多的关于推导马尔科夫毯的工作。文中综合分析了已发表工作的两大分支 约束和非约束分析，而在约束学习类里又进一步分成

55、了三个分支。本文累计覆盖了17个典型工作，据查新所知，这是截止撰写本文时关于马尔科夫毯推导研究的最综合性的综述。在介绍每个算法时，讨论兼顾了理论和实用性，故该讨论对研究和工程人员都有一定的参考价值。基于已有的工作特点，文中同时给出了约束和非约束学习的可能机会，以与关于马尔科夫毯的可能应用。参考文献:1Pearl, J., Probabilistic reasoning in expert systems M 1988,San Matego: Morgan Kaufmann.2Koller, D. and M. Sahami. Toward optimal feature selection.

56、in the 13th International Conference on Machine Learning (ICML) C. 1996. Bari, Italy: Morgan Kaufmann.3Chickering, D.M., D. Geiger, and D. Heckerman, Learning Bayesian Network is NP-Hard R, 1994, Microsoft. p. 22.4Campos, C.P.d., Z. Zeng, and Q. Ji, Efficient structure learning of Bayesian networks using constraints. Journal of Machine Learning Research (JMLR) J, 2011. 12(11): p. 663-689.5王双成, 苑森淼, and 王辉, 基于贝叶斯网络的马尔科夫毯预测学习 J. 模式识别与人工智能, 2004. 17(1).6Spirtes, P., C. Glymour, and R. Scheines, Causation, Prediction, and Search M 2001: A Bradford Boo