Finding Optimal Bayesian Network Given a Super-Structure
Finding Optimal Bayesian Network Given a Super-Structure
复制标题
DOI：
--
复制
发表时间：
2008
影响因子：
6
通讯作者：
Eric Perrier;S. Imoto;S. Miyano
中科院分区：
文献类型：
--
作者：
Eric Perrier;S. Imoto;S. Miyano
传统的贝叶斯网络结构学习方法存在计算复杂度高、精度低等缺点。然而，最近的一项实证研究表明，混合算法提高了灵敏的准确性和速度：它学习的骨架与独立性测试（IT）的方法和约束的有向无环图（DAG）考虑在搜索和评分阶段。随后，我们通过引入超结构S的概念来理论化结构约束，超结构S是一个无向图，它将搜索限制在骨架是S的子图的网络上。提出了一种超结构约束最优搜索（COS），其时间复杂度为O（γm n），其中γm < 2依赖于S的最大度m.从经验上讲，复杂度取决于平均度，稀疏结构允许计算更大的图。我们的算法比最优搜索快几个订单，甚至发现更准确的结果时，给出了一个健全的超结构。实际上，S可以通过IT方法近似;测试的显著性水平控制其稀疏性，从而能够控制速度和准确性之间的权衡。对于不完整的超结构，一个greatest后处理版本（COS+）仍然能够显着优于其他启发式搜索。
Classical approaches used to learn Bayesian network structure from data have disadvantages in terms of complexity and lower accuracy of their results. However, a recent empirical study has shown that a hybrid algorithm improves sensitively accuracy and speed: it learns a skeleton with an independency test (IT) approach and constrains on the directed acyclic graphs (DAG) considered during the search-and-score phase. Subsequently, we theorize the structural constraint by introducing the concept of super-structure S, which is an undirected graph that restricts the search to networks whose skeleton is a subgraph of S. We develop a super-structure constrained optimal search (COS): its time complexity is upper bounded by O(γm n ), where γm < 2 depends on the maximal degree m of S. Empirically, complexity depends on the average degree ˜ m and sparse structures allow larger graphs to be calculated. Our algorithm is faster than an optimal search by several orders and even finds more accurate results when given a sound super-structure. Practically, S can be approximated by IT approaches; significance level of the tests controls its sparseness, enabling to control the trade-off between speed and accuracy. For incomplete super-structures, a greedily post-processed version (COS+) still enables to significantly outperform other heuristic searches.