Article

Parallelisation of the PC Algorithm

Authors:

Anders L. Madsen,

Antonio Salmerón,

Helge Langseth,

Thomas D. NielsenAuthors Info & Claims

Proceedings of the 16th Conference of the Spanish Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 9422

Pages 14 - 24

https://doi.org/10.1007/978-3-319-24598-0_2

Published: 09 November 2015 Publication History

Abstract

This paper describes a parallel version of the PC algorithm for learning the structure of a Bayesian network from data. The PC algorithm is a constraint-based algorithm consisting of five steps where the first step is to perform a set of conditional independence tests while the remaining four steps relate to identifying the structure of the Bayesian network using the results of the conditional independence tests. In this paper, we describe a new approach to parallelisation of the conditional independence testing as experiments illustrate that this is by far the most time consuming step. The proposed parallel PC algorithm is evaluated on data sets generated at random from five different real-world Bayesian networks. The results demonstrate that significant time performance improvements are possible using the proposed algorithm.

References

[1]

Andreassen, S., Jensen, F.V., Andersen, S.K., Falck, B., Kjærulff, U., Woldbye, M., SØrensen, A.R., Rosenfalck, A., Jensen, F.: MUNIN --- an expert EMG assistant. In: Computer-Aided Electromyography and Expert Systems, Chapter 21. Elsevier Science 1989

[2]

Andreassen, S., Hovorka, R., Benn, J., Olesen, K.G., Carson, E.R.: A model-based approach to insulin adjustment. In: Stefanelli, S., Hasman, A., Fieschi, M., Talmon, J. eds. Proceedings of the Third Conference on Artificial Intelligence in Medicine. Lecture Notes in Medical Informatics, pp. 239---248. Springer, Heidelberg 1991

[3]

Basak, A., Brinster, I., Ma, X., Mengshoel, O.J.: Accelerating Bayesian network parameter learning using hadoop and MapReduce. In: Proceedings of the 1st International Workshop on Big Data, Streams a nd Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications, pp. 101---108 2012

Digital Library

[4]

Chen, W., Zong, L., Huang, W., Ou, G., Wang, Y., Yang, D.: An empirical study of massively parallel Bayesian networks learning for sentiment extraction from unstructured text. In: Du, X., Fan, W., Wang, J., Peng, Z., Sharaf, M.A. eds. APWeb 2011. LNCS, vol. 6612, pp. 424---435. Springer, Heidelberg 2011

Digital Library

[5]

Chu, C.-T., Kim, S.K., Lin, Y.-A., Yu, Y., Bradski, G., Ng, A.Y., Olukotun, K.: Map-reduce for machine learning on multicore. In: NIPS, pp. 281---288 2006

Digital Library

[6]

de Jongh, M.: Algorithms for constraint-based learning of Bayesian network structures with large numbers of variables. Ph.D. thesis, Uni$$\dot{\rm o}$$f Pittsburgh 2014

[7]

Fang, Q., Yue, K., Fu, X., Wu, H., Liu, W.: A MapReduce-based method for learning Bayesian network from massive data. In: Ishikawa, Y., Li, J., Wang, W., Zhang, R., Zhang, W. eds. APWeb 2013. LNCS, vol. 7808, pp. 697---708. Springer, Heidelberg 2013

[8]

Jensen, F.V., Skaanning, C., Kjærulff, U.: The SACSO system for troubleshooting of printing systems. In: Proceedings of the Seventh Scandinavian Conference on Artificial Intelligence 2001

Digital Library

[9]

Jensen, F.V., Nielsen, T.D.: Bayesian Networks and Decision Graphs, 2nd edn. Springer, New York 2007

Digital Library

[10]

Kalisch, M., Buhlmann, P.: Estimating high-dimensional directed acyclic graphs with the PC-algorithm. J. Mach. Learn. Res. 8, 613---636 2008

Digital Library

[11]

Kjærulff, U.B., Madsen, A.L.: Bayesian Networks and Influence Diagrams: A Guide to Construction and Analysis, 2nd edn. Springer, New York 2013

[12]

Knuth, D.E.: The Art of Computer Programming, Volume 4, Fascicle 3. Addison-Wesley, Reading 2005

Digital Library

[13]

Madsen, A.L., Jensen, F., Salmeron, A., Karlsen, M., Langseth, H., Nielsen, T.D.: A new method for vertical parallelisation of tan learning based on balanced incomplete block designs. In: Proceedings of PGM, pp. 302---317 2014

[14]

Nikolova, O., Aluru, S.: Parallel discovery of direct causal relations and Markov boundaries with applications to gene networks. In: 2011 International Conference IEEE Parallel Processing ICPP, pp. 512---521 2011

Digital Library

[15]

Papanikolaou, A.: Presents Modern Risk-based Methods and Applications to Ship Design, Operation, and Regulations. Springer, Heidelberg 2009

[16]

Scutari, M.: Learning Bayesian Networks with the bnlearn R Package. J. Stat. Softw. 353, 1---22 2010

[17]

Spirtes, P., Glymour, C., Scheines, R.: Causation, Prediction, and Search. Adaptive Computation and Machine Learning, 2nd edn. MIT Press, Cambridge 2000

[18]

Stinson, D.: Combinatorial Designs - Constructions and Analysis. Springer, New York 2003

Digital Library

Cited By

Schmidt CHuegle JUflacker MSacharidis DGamper JBöhlen M(2018)Order-independent constraint-based causal structure learning for gaussian distribution models using GPUsProceedings of the 30th International Conference on Scientific and Statistical Database Management10.1145/3221269.3221292(1-10)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.1145/3221269.3221292
Salmerón AMadsen AJensen FLangseth HNielsen TRamos-López DMartínez AMasegosa A(2016)Parallel filter-based feature selection based on balanced incomplete block designsProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-743(743-750)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.3233/978-1-61499-672-9-743

Recommendations

A parallel algorithm for Bayesian network structure learning from large data sets

This paper considers a parallel algorithm for Bayesian network structure learning from large data sets. The parallel algorithm is a variant of the well known PC algorithm. The PC algorithm is a constraint-based algorithm consisting of five steps where ...
A new PC-PSO algorithm for Bayesian network structure learning with structure priors
Highlights
- A new Bayesian network structure learning algorithm has been proposed.
- This ...
Abstract
Bayesian network structure learning is the basis of parameter learning and Bayesian inference. However, it is a NP-hard problem to find the optimal structure of Bayesian networks because the computational complexity increases ...
The dual PC algorithm and the role of Gaussianity for structure learning of Bayesian networks
Abstract
Learning the graphical structure of Bayesian networks is key to describing data-generating mechanisms in many complex applications but poses considerable computational challenges. Observational data can only identify the equivalence ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings of the 16th Conference of the Spanish Association for Artificial Intelligence on Advances in Artificial Intelligence - Volume 9422

November 2015

337 pages

ISBN:9783319245973

Editors:
José M. Puerta
University of Castilla-La Mancha, Albacete, Spain
,
José A. Gámez
University of Castilla-La Mancha, Albacete, Spain
,
Bernabe Dorronsoro
University of Cadiz, Cadiz, Spain
,
Edurne Barrenechea
Public University of Navarre, Pamplona, Spain
,
Alicia Troncoso
Pablo de Olavide University, Sevilla, Spain
,
Bruno Baruque
Department of Civil Engineering, University of Burgos, Burgos, Spain
,
Mikel Galar
Public University of Navarre, Pamplona, Spain

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 09 November 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Schmidt CHuegle JUflacker MSacharidis DGamper JBöhlen M(2018)Order-independent constraint-based causal structure learning for gaussian distribution models using GPUsProceedings of the 30th International Conference on Scientific and Statistical Database Management10.1145/3221269.3221292(1-10)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.1145/3221269.3221292
Salmerón AMadsen AJensen FLangseth HNielsen TRamos-López DMartínez AMasegosa A(2016)Parallel filter-based feature selection based on balanced incomplete block designsProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-743(743-750)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.3233/978-1-61499-672-9-743

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents