检索结果-内蒙古大学图书馆

Parallel Algorithm for Learning optimal bayesian network structure

JOURNAL OF MACHINE LEARNING RESEARCH 2011年第7期12卷 2437-2459页

作者： Tamada, Yoshinori Imoto, Seiya Miyano, Satoru Univ Tokyo Ctr Human Genome Inst Med Sci Minato Ku Tokyo 1088639 Japan RIKEN Computat Sci Res Program Wako Saitama 3510198 Japan

We present a parallel algorithm for the score-based optimal structure search of bayesian networks. This algorithm is based on a dynamic programming (DP) algorithm having O(n . 2(n)) time and space complexity, which is known to be the fastest algorithm for the optimal structure search of networks with n nodes. The bottleneck of the problem is the memory requirement, and therefore, the algorithm is currently applicable for up to a few tens of nodes. While the recently proposed algorithm overcomes this limitation by a space-time trade-off, our proposed algorithm realizes direct parallelization of the original DP algorithm with O(n(sigma)) time and space overhead calculations, where sigma > 0 controls the communication-space trade-off. The overall time and space complexity is O(n(sigma+1)2(n)). This algorithm splits the search space so that the required communication between independent calculations is minimal. Because of this advantage, our algorithm can run on distributed memory supercomputers. Through computational experiments, we confirmed that our algorithm can run in parallel using up to 256 processors with a parallelization efficiency of 0.74, compared to the original DP algorithm with a single processor. We also demonstrate optimal structure search for a 32-node network without any constraints, which is the largest network search presented in literature.

关键词： optimal bayesian network structure parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Parallel Algorithm for optimal DAG structure Search on Parallel Computer with Torus network 16th

Efficient Parallel Algorithm for Optimal DAG Structure Searc...

引用

16th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP)

作者： Honda, Hirokazu Tamada, Yoshinori Suda, Reiji Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan

ISBN: (纸本)9783319495835;9783319495828

The optimal directed acyclic graph search problem constitutes searching for a DAG with a minimum score, where the score of a DAG is defined on its structure. This problem is known to be NP-hard, and the state-of-the-art algorithm requires exponential time and space. It is thus not feasible to solve large instances using a single processor. Some parallel algorithms have therefore been developed to solve larger instances. A recently proposed parallel algorithm can solve an instance of 33 vertices, and this is the largest solved size reported thus far. In the study presented in this paper, we developed a novel parallel algorithm designed specifically to operate on a parallel computer with a torus network. Our algorithm crucially exploits the torus network structure, thereby obtaining good scalability. Through computational experiments, we confirmed that a run of our proposed method using up to 20,736 cores showed a parallelization efficiency of 0.94 as compared to a 1296-core run. Finally, we successfully computed an optimal DAG structure for an instance of 36 vertices, which is the largest solved size reported in the literature.

关键词： optimal DAG structure optimal bayesian network structure Parallel algorithm Distributed algorithm Torus network

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：