Record Details

Parallel globally optimal structure learning of Bayesian networks

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Parallel globally optimal structure learning of Bayesian networks
 
Creator NIKOLOVA, O
ZOLA, J
ALURU, S
 
Subject Bayesian networks
Graphical models
Machine learning
Structure learning
Parallel algorithm
STRUCTURE DISCOVERY
 
Description Given n random variables and a set of m observations of each of the n variables, the Bayesian network structure learning problem is to learn a directed acyclic graph (DAG) on the n 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 O(n(2).2(n)) time plus the cost of O(n.2(n)) evaluations of an application-specific scoring function whose run-time is at least linear in m. In this paper, we present a parallel algorithm for exact structure learning of a Bayesian network that is communication-efficient and workoptimal up to O(1/n.2(n)) 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. (C) 2013 Elsevier Inc. All rights reserved.
 
Publisher ACADEMIC PRESS INC ELSEVIER SCIENCE
 
Date 2014-10-15T14:07:21Z
2014-10-15T14:07:21Z
2013
 
Type Article
 
Identifier JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 73(8)1039-1048
0743-7315
1096-0848
http://dx.doi.org/10.1016/j.jpdc.2013.04.001
http://dspace.library.iitb.ac.in/jspui/handle/100/15062
 
Language en