Optimal Search on Clustered Structural Constraint for Learning Bayesian Network Structure
Optimal Search on Clustered Structural Constraint for Learning Bayesian Network Structure
复制标题
DOI：
10.5555/1756006.1756015
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Kaname Kojima;Eric Perrier;S. Imoto;S. Miyano
中科院分区：
文献类型：
--
作者：
Kaname Kojima;Eric Perrier;S. Imoto;S. Miyano
我们研究了在受限搜索空间中学习最优贝叶斯网络的问题；骨架必须是给定的称为超结构的无向图的子图。即使对于稀疏的超结构，以前的约束最优搜索(COS)仍然是有限的。为了扩展其可行性，我们提出将超结构分成几个簇，并对每个簇进行优化搜索。此外，为了保证无循环性，我们引入了祖先约束的概念，并推导出满足给定的祖先约束集的最优算法。最后，从理论上给出了寻找最优约束图所要考虑的最优约束图的充要集合。实验结果表明，对于一些包含数百个顶点的图，甚至对于具有较高平均度(最高可达4个)的超结构，我们的算法都能学习到最优的贝叶斯网络，这在可行性上比以前的优化算法有了很大的提高。学习的网络在得分和结构汉明距离方面都大大优于最先进的启发式算法。
We study the problem of learning an optimal Bayesian network in a constrained search space; skeletons are compelled to be subgraphs of a given undirected graph called the super-structure. The previously derived constrained optimal search (COS) remains limited even for sparse super-structures. To extend its feasibility, we propose to divide the super-structure into several clusters and perform an optimal search on each of them. Further, to ensure acyclicity, we introduce the concept of ancestral constraints (ACs) and derive an optimal algorithm satisfying a given set of ACs. Finally, we theoretically derive the necessary and sufficient sets of ACs to be considered for finding an optimal constrained graph. Empirical evaluations demonstrate that our algorithm can learn optimal Bayesian networks for some graphs containing several hundreds of vertices, and even for super-structures having a high average degree (up to four), which is a drastic improvement in feasibility over the previous optimal algorithm. Learnt networks are shown to largely outperform state-of-the-art heuristic algorithms both in terms of score and structural hamming distance.