贝叶斯网络结构加速学习算法  

Accelerating Structure Learning of Bayesian Network

作　　者：SEIN Minn 傅顺开[1] 

机构地区：[1]华侨大学计算机科学与技术学院,厦门361021

出　　处：《计算机科学》2016年第2期263-268,272,共7页Computer Science

基　　金：国家自然科学基金资助项目(61305058;61300139);厦门科技计划基金资助项目(3505Z20133027);华侨大学科研基金资助项目(11Y0274;12HJY18);中央高校基本科研基金资助项目(11J0263)资助

摘　　要：结构学习是应用贝叶斯网络(BN)的基础。提出一种新的基于约束的学习类算法APC(Accelerated PC),它基于一系列局部结构的推导获得BN。APC不但继承了经典的PC(Peter&Clark)算法优先执行低阶条件独立(CI)测试的优点,而且能够从已执行的CI测试中推导相关拓扑信息,并利用其来挑选并优先执行更可能d-分割节点X和Y的候选CI测试。该策略可有效避免在搜索过程中执行无效的CI测试,例如APC算法在实验中较PC算法节省高达50%的计算量,同时实现了质量相同的学习效果。Structure learning is the basis for the application of Bayesian networks（BN）.A novel algorithm called APC was proposed to recovery the whole structure via sequential induction of local structures.APC inherits the most feature of PC algorithm,i.e.effectively avoiding high-dimensional conditional independence（CI）tests.Besides,it constructs and sorts candidate sets which possibly d-separate any pair of nodes,Xand Y,based on information implied in early conducted CI tests and known features of BN topology.Then,CI tests involving highly ranked candidate set are performed with priority.This strategy is expected to avoid fruitless CI tests,and up to 50% saving is observed on APC over PC in our experimental study.

关 键 词：贝叶斯网络 结构学习 基于约束的学习 条件独立性测试 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]