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

Accelerating Structure Learning of Bayesian Network

结构学习是应用贝叶斯网络(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.