A Fast Clique Maintenance Algorithm for Optimal Triangulation of Bayesian Networks
A Fast Clique Maintenance Algorithm for Optimal Triangulation of Bayesian Networks
复制标题
贝叶斯网络最优三角剖分的快速团维护算法
DOI：
10.1007/978-3-319-28379-1_11
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Ueno
中科院分区：
文献类型：
--
作者：
Chao Li;M. Ueno
联合树算法是目前最流行的贝叶斯网络精确推理算法。为了提高联合树算法的时间和空间复杂度，必须找到一个最优的总表大小的三角剖分。为此，Ottosen和Vomlel提出了一种深度优先搜索的DFS最优三角剖分算法。他们还介绍了几种改进DFS算法的技术，包括动态团维护和合并映射修剪。然而，它们的动态团维护可能会计算一些重复的团。在本文中，我们提出了一个新的动态团维护，只计算包含一个新的边缘的团。新方法探索更少的搜索空间，运行速度比Ottosen和Vomlel方法更快。仿真实验表明，新的动态团维护算法提高了最优三角剖分算法的运行时间。
The junction tree algorithm is currently the most popular algorithm for exact inference on Bayesian networks. To improve the time and space complexity of the junction tree algorithm, we must find an optimal total table size triangulations. For this purpose, Ottosen and Vomlel proposed a depth-first search DFS algorithm for optimal triangulation. They also introduced several techniques for improvement of the DFS algorithm, including dynamic clique maintenance and coalescing map pruning. However, their dynamic clique maintenance might compute some duplicate cliques. In this paper, we propose a new dynamic clique maintenance that only computes the cliques that contain a new edge. The new approach explores less search space and runs faster than the Ottosen and Vomlel method does. Some simulation experiments show that the new dynamic clique maintenance improved the running time of the optimal triangulation algorithm.
贝叶斯网络最优三角剖分的深度优先搜索算法，
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Chao Li and; Maomi Ueno
通讯作者：
Maomi Ueno
影响因子：
1.1
作者：
Tomita, Etsuji;Tanaka, Akira;Takahashi, Haruhisa
通讯作者：
Takahashi, Haruhisa