马尔科夫毯学习算法综述

第29卷第1期计算机应用研究Vol.29No.12012年1期ApplicationResearchofComputersJan.2011———————————————收稿日期：2006-08-20；修回日期：基金项目：国家自然科学基金资助项目（61305058，61300139）；厦门科技计划基金资助项目（3505Z20133027）；华侨大学科研基金资助项目（11Y0274和12HJY18）；中央高校基本科研基金资助项目（11J0263）。作者简介:傅顺开(1978-)，男（汉），福建莆田市仙游县，讲师，博士，主要研究方向：数据挖掘、移动互联网（[e-mail]）；SeinMinn(1990-)，男，缅甸人，硕士研究生，主要研究方向：数据挖掘及其应用。本刊不特别标注通信作者，若必须标注，请在通信作者名后加“+”（横短竖长）上标，并在作者简介该作者性别后注明（通信作者）马尔科夫毯学习算法研究和进展*傅顺开，SeinMinn(华侨大学计算机科学与技术学院,福建省厦门市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算法，和(4)基于评分-搜索方法的DMB和RPDMB两个算法。讨论时兼顾理论和实用性内容，并统一/扩展了相关算法的伪代码（描述），对学术界和工业界研究人员都具参考价值。关键词:马尔科夫毯;贝叶斯网络；约束学习；特征选择中图分类号:TP391文献标志码:A文章编号：（作者可不填）doi:10.3969/j.issn.1001-3695(作者可不填)AReviewofMarkovBlanketInductionAlgorithmsFUShun-kai,SEINMinn(CollegeofComputerScienceandTechnology,HuaqiaoUniversity,XiamenFujian361021,China)Abstract:Markovblanket(MB)hasbeenrealizedanddefinedduringtheresearchofBayesiannetwork,anditisanimportantcomponentoftheBN.In1996,itwasprovedtheoptimalfeaturesubsetforprediction.GiventheglobalBN,itistrivialtoreadofftheMBofspecificvariable,butthestructurelearningofBNisknownasNP-hardproblem.From1996on,therearemanypublishedworksontheinductionofMB,andourreviewcovers17typicalworks,including(1)thosebasedontheglobalconditionalindependence(CI)probabilityfeatureofMB,likeKS,IAMBetc.,(2)thosebasedonthelocalCIprobabilityfeature,suchasPCMB,IPC-MBetc.,(3)oneworkwiththecombinationoflogisticregressionandconstraintlearning,calledRA-MMMB,and(4)non-constraintlearningworksbasedonscore-and-search,DMBandRPDMB.Ourdiscussioncoverstheoreticalaswellaspracticalaspect,andwerevisethepseudocodesofrelatedalgorithmstoeasiertheunderstanding.Itisbelievedausefulreferenceforbothacademicandindustrialcolleagues.Keywords:Markovblanket;Bayesiannetwork;constraintlearning;dimensionreduction;featureselection1引言贝叶斯网络（BayesianNetwork,BN）是一种有向无环图（DAG）模型，其中节点代表了随机变量，而边代表了随机变量之间的概率关系。基于条件独立性，BN的图模型能够有效紧凑表达目标问题的联合概率关系，并可以通过贝叶斯链式法则来快速实现从图表征语言到公式的相互转换。BN是人工智能领域的一种重要工具，被成功运用到机器学习和数据挖掘领域。早在1988年，Peal就在他的关于贝叶斯网络研究的专著[1]里定义和讨论了马尔科夫毯（MarkovBlanket，MB）。给定一个节点T，它的MB是唯一的，包括T的所有父、子和配偶（和T有共同孩子的）节点（见图1）。当MB内的（所有）节点的值确定后，T的值可以被确定。虽然该性质被较早认识到，但直到1996年才由Koller和Sahami（简称K&S）两位斯坦福大学的学者将MB和特征选择（featureselection）关联起来[2]，而特征选择是机器学习和数据挖掘领域重要的预处理步骤之一。K&S从信息论角度首次证明了MB是预测目标变量T的最优子集-不包含无关（irrelevant）和冗余（redundant）变量。特征选择通过降低输入维度而让随后的学习器所面临的求解搜索空间的复杂度大大降低，这既提高了求解效率，也减小出现过拟合现象的可能性。同时，降维还能为数据采集、存储、传输和预处理带来可观的（时间和经济）成本节约。当然，理想的特征选择是在保证以上收益的同时不牺牲模型的预测能力。当已知BN（的结构），我们可以很容易“读出”目标节点（变量）T的MB。然而，推导BN的结构被公认是NP问题[3]，已知的需要自动推导BN的应用一般只包含数十个变量[4]。王双成等的工作显示了基于马尔科夫毯的预测由于TAN、朴素贝叶斯和BN，但仍然需要先学习完整的BN[5]。K&S在1996年发表的著作里除了证明MB的重要性质，也讨论了MB的推导策略。为了保证搜索效率，他们提出了一个近似的学习算法。作者并没有为其命名，为了引用方便本文简称其为K&S算法。K&S算法无法保证一定输出正确的马尔科夫毯[2]。页码计算机应用研究第28卷TX1X2X3X4X5Y5Y3Y1X6Z1Y4Y2图1贝叶斯网络和T的马尔科夫毯（灰色节点）示例。{X1，X2}为T的父节点，{X3，X4}为T的子节点，{X5，X6}为T的配偶节点。{X3，X4，Y3}为T的后代节点，剩下的为T的非后代节点基于GoogleScholar的统计数据和我们对搜索结果的人工整理，在1996~2013期间至少有超过100篇的比较重要的关于马尔科夫毯推导和应用的学术论文，其中不乏发表在包括JMLR（JournalofMachineLearningResearch）、DMKD（DataMiningandKnowledgeDiscovery）、ICML、KDD、ECML\PKDD、AAAI、PAKDD等顶级期刊和学术会议上。K&S的1996年的开创性论文[2]更是获得了超过1260次的引用（截止准备本文时）。以上事实和数字直接反映了该研究方向的重要性，但国内相关的研究成果甚少（查新过程中只发现两篇相关的工作），这推动我们撰写本文将相关研究进展向国内同行介绍。在文中，我们将拣选出已发表的工作有代表性的算法进行分类，并从理论和实用维度分别给予介绍和讨论，相信这将有助于同行研究人员和工业界应用者的参考。2符号、概念、算法分类和讨论维度2.1符号表示采用粗体罗马字母表示变量集合（比如X），非粗体的斜体罗马字母表示单个变量（比如X），对应的小写罗马字母表示变量值（比如Xx，Xx）。对于一个分布P，采用(,|)IPXYZ表示给定条件集Z时，X与Y是相互独立的。若条件集Z（为空），使用(,)IPXY表示。为了简化表示，在考虑单个变量时，都忽略标准的集合表示。比如，采用(,|)IXYPZ表示({},{}|)IXYPZ。类似地，使用(,|)IXYGZ来表示在图模型中节点之间的条件独立关系。2.2贝叶斯网络和理论基础给定变量集合1{,...,}nXXU，1n，对应的贝叶斯网络是个二元组，,BNGΘ。其中，,GVA是一个有向无环图：节点集合V对应U，边集合蕴含了拓扑关系。任意节点iX的父、子和配偶节点集合分别记为()iXPa、()iXCh和()iXSp，而父子节点又常合并表示为()iXPC。参数Θ包含诸如|()(|())iixxiiPxxPaPa这样的条件概率分布（当变量取连续值时对应条件概率分布函数，而变量取离散值时对应条件概率表），它“定量地”给出当父节点集合取值为()ixPa时，他们共同的子节点取值的条件概率。没有父节点的用先验概率进行信息表达。本文中，“变量”和“节点”将混合使用。给定贝叶斯网络G，其所表示的联合概率分布可以根据G=V,A所包含的信息因式分解为:11()(|())n2niiipXX,...,XpXXPa,(1)贝叶斯网络中任意相连的三个节点X，Y和Z存在三种可能的连接场景，（1）XZY（简称“顺序接接”），（2）XZY（简称“尾部连接”），（3）XZY（简称“头部连接”或“v结构”）。图G中任意存在路径（即连接两个节点的边集合）的两个节点之间的边都可以分解为这三种结构。例如图1中的145XTXX是连接1X和5X的路径，但不是唯一的路径，因为还存在路径14345XTXYYX。能够割断两个节点之间所有路径的最小节点集合称作最小“割集”（seperator），例如图1中1X和5X的最小割集是空集。割集对应到()IX,YPZ|中的Z。为了讨论方便，在此简要介绍一些基础概念和定理。定义1忠实性（Faithfulness）。一个贝叶斯网络BN和一个联合分布P是相互忠实的，当且仅当蕴含在BN的结构G里的每一个条件独立性关系也同样存在于P中，即(,|)(,|)IXYIXYGPZZ。[1]定义2马尔科夫毯。一个变量TU的马尔科夫毯记为()TMB，它是满足以下条件的变量集合：\()\{}XTTUMB，(,|())IXYTPMB（2）而其中最小的马尔科夫毯称为马尔科夫边界（Markovboundary）。定理1假定忠实性满足，对应于联合分布P的贝叶斯网络BN的结构G，（1）任意节点XV的马尔科夫毯是唯一的，包含其父、子和配偶节点（参考图1），（2）\()\{}YTTUMB，(,|())IXYTDMB。引理1假定忠实性满足，（1）一个变量XU的马尔科夫毯和其马尔科夫边界是一致的，（2）X的父、子和配偶节点组成了最优特征子集。（根据定义2和定理1容易证明）定理2两个有向无环图是等价的，当且仅当他们有相同的无向图和相同的v结构。定义3后代（Descendant）。贝叶斯网络BN中，如果存在一条从X到Y的有向边，但不存在从Y到X的有限边，那么就说Y是X的后代。X的后代节点集记为()XDes。定义4非后代（Non-Descendant）。贝叶斯网络BN中，X的除了后代节点的其他节点集称作非后代节点集，记为()XNonDes。定理3如果一个贝叶斯网络BN忠实于联合概率分布P，那么X和Y在BN中是直接相连接的，当且仅当页码计算机应用研究第28卷对于任何不包含X和Y的集合Z，(,|())IXYTPMB恒不成立。定