The max-min hill-climbing Bayesian network structure learning algorithm
The max-min hill-climbing Bayesian network structure learning algorithm
复制标题
DOI：
10.1007/s10994-006-6889-7
复制
发表时间：
2006-10-01
期刊：
影响因子：
7.5
通讯作者：
Aliferis, Constantin F.
中科院分区：
文献类型：
--
作者：
Tsamardinos, Ioannis;Brown, Laura E.;Aliferis, Constantin F.
我们提出了一种新的贝叶斯网络结构学习算法，称为最大最小爬坡算法（MMHC）。该算法以一种有原则和有效的方式结合了局部学习、基于约束和搜索评分技术的思想。它首先重建贝叶斯网络的骨架，然后执行贝叶斯评分贪婪爬坡搜索来定位边缘。在我们广泛的实证评估中，MMHC在各种指标方面的平均表现优于几种原型和最先进的算法，即PC，稀疏候选，三相依赖分析，最优重新插入，贪婪等价搜索和贪婪搜索。这是第一个同时比较大多数主要贝叶斯网络算法的实证结果。MMHC提供了一定的理论优势，特别是优于稀疏候选算法，我们的实验证实了这一点。MMHC和我们研究的详细结果可在http://www.dsl-lab.org/supplements/mmhc_paper/mmhc_index.html上公开获取。
We present a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). The algorithm combines ideas from local learning, constraint-based, and search-and-score techniques in a principled and effective way. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. In our extensive empirical evaluation MMHC outperforms on average and in terms of various metrics several prototypical and state-of-the-art algorithms, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search. These are the first empirical results simultaneously comparing most of the major Bayesian network algorithms against each other. MMHC offers certain theoretical advantages, specifically over the Sparse Candidate algorithm, corroborated by our experiments. MMHC and detailed results of our study are publicly available at http://www.dsl-lab.org/supplements/mmhc_paper/mmhc_index.html.