Parallel globally optimal structure learning of Bayesian networks

详细信息    查看全文

• 作者：Olga Nikolova^a ; ^{olga.nikolova@sagebase.org}Author Vitae ; Jaroslaw Zola^b ; ^{jaroslaw.zola@rutgers.edu}Author Vitae ; Srinivas Aluru^c ; ^d ; ^{aluru@iastate.edu}Author Vitae
• 关键词：Bayesian networks ; Graphical models ; Machine learning ; Structure learning ; Parallel algorithm
• 刊名：Journal of Parallel and Distributed Computing
• 出版年：2013
• 出版时间：August, 2013
• 年：2013
• 卷：73
• 期：8
• 页码：1039-1048
• 全文大小：601 K

文摘

Given random variables and a set of observations of each of the variables, the Bayesian network structure learning problem is to learn a directed acyclic graph (DAG) on the variables such that the implied joint probability distribution best explains the set of observations. Bayesian networks are widely used in many fields including data mining and computational biology. Globally optimal (exact) structure learning of Bayesian networks takes time plus the cost of evaluations of an application-specific scoring function whose run-time is at least linear in . In this paper, we present a parallel algorithm for exact structure learning of a Bayesian network that is communication-efficient and work-optimal up to processors. We further extend this algorithm to the important restricted case of structure learning with bounded node in-degree and investigate the performance gains achievable because of limiting node in-degree. We demonstrate the applicability of our method by implementation on an IBM Blue Gene/P system and an AMD Opteron InfiniBand cluster and present experimental results that characterize run-time behavior with respect to the number of variables, number of observations, and the bound on in-degree.