马尔科夫毯学习算法综述

《马尔科夫毯学习算法综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、马尔科夫毯学习算法研究和进展*傅顺开，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）基于

2、评分-搜索方法的DMB和RPDMB两个算法。讨论时兼顾理论和实用性内容，并统一/扩展了相关算法的伪代码（描述），对学术界和工业界研究人负都具参考价值。关键词：马尔科夫毯；贝叶斯网络；约束学习；特征选择中图分类号：TP391文献标志码：A文章编号：（作者可不填）doi:l0.3969/j.issn.1001-3695（作者可不填）AReviewofMarkovBlanketInductionAlgorithmsFUShun-kai，SEINMinn(CollegeofComputerScienceandTechnology，HuaqiaoUniversity,XiamenFujian36102

3、1，China)Abstract:Markovblanket(MB)hasbeenrealizedanddefinedduringtheresearchofBayesiannetwork，anditisanimportantcomponentoftheBN.In1996,itwasprovedtheoptimalfeaturesubsetforprediction.GiventheglobalBN，itistrivialtoreadofftheMBofspecificvariable,butthestructurelearningofBNisknownasNP-hardproblem.Fro

4、m1996on,therearemanypublishedworksontheinductionofMB，andourreviewcovers17typicalworks，including(1)thosebasedontheglobalconditionalindependence(CI)probabilityfeatureofMB，likeKS，IAMBetc”(2)thosebasedonthelocalCIprobabilityfeature,suchasPCMB,IPC-MBetc.，(3)oneworkwiththecombinationoflogisticregressiona

5、ndconstraintlearning，calledRA-MMMB,and(4)non-constraintlearningworksbasedonscore-and-search,DMBandRPDMB.Ourdiscussioncoverstheoreticalaswellaspracticalaspect,andwerevisethepseudocodesofrelatedalgorithmstoeasiertheunderstanding.Itisbelievedausefulreferenceforbothacademicandindustrialcolleagues.Keywo

6、rds:MarkovbIanket;Bayesiannetwork;constraintlearning;dimensionreduction;featureselection1引言贝叶斯网络（BayesianNetwork,BN）是一种有向无环图（DAG）模型,其中节点代表了随机变量,而边代表了随机变觉之叫的概率关系。基于条件独立性，BN的图模型能够宥效紧凑衣达11标问题的联合概率关系，丼可以通过W叶斯链式法则来快速实现从图农征语言到公式的相互转换。BN是人工智能领域的一种重要工具，被成功运川到机器学4和数裾挖掘领域。¥在1988年，Peal就在他的关于贝叶斯网络研究的专著［1］里定义和讨

7、论了马尔科夫毯（MarkovBlanket,MB）。给定一个节点r，它的mb是唯一的,包括r的所有父、子和配偶（和r有共同孩子的）节点（见图1）。当mb内的（所有）节点的值确定后，r的值uj以被确定。瓜然该性质被较早认识到，但直到1996年才由Koller和Sahami（简称K&S）两位斯坦福人学的学者将MB和特征选择（featureselection）关联起來［2］,而特征选择足机器学》和数据挖掘领域重耍的