Parallelisation of the PC Algorithm

Anders Læsø Madsen; Frank Jensen; Antonio Salmerón; Helge Langseth; Thomas Dyhre Nielsen

doi:10.1007/978-3-319-24598-0_2

Parallelisation of the PC Algorithm

Anders Læsø Madsen^*, Frank Jensen, Antonio Salmerón, Helge Langseth, Thomas Dyhre Nielsen

^*Kontaktforfatter

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

8 Citationer (Scopus)

322 Downloads (Pure)

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 parallelization 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.

Originalsprog	Engelsk
Titel	Advances in Artificial Intelligence : 16th Conference of the Spanish Association for Artiﬁcial Intelligence, CAEPIA 2015 Albacete, Spain, November 9–12, 2015 Proceedings
Antal sider	11
Forlag	Springer
Publikationsdato	2015
Sider	14-24
ISBN (Trykt)	978-3-319-24597-3
ISBN (Elektronisk)	978-3-319-24598-0
DOI	https://doi.org/10.1007/978-3-319-24598-0_2
Status	Udgivet - 2015
Begivenhed	16th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2015 - Albacete, Spanien Varighed: 9 nov. 2015 → 12 nov. 2015

Konference

Konference	16th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2015
Land/Område	Spanien
By	Albacete
Periode	09/11/2015 → 12/11/2015
Sponsor	DSI, ESII, I3A, University of Castilla-La Mancha

Navn	Lecture Notes in Computer Science
Vol/bind	9422
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-319-24598-0_2

madsen_amidst_caepiaIndsendt manuskript, 310 KB

http://www.idi.ntnu.no/~helgel/papers/MadsenJensenSalmeronLangsethNielsenCAEPIA15.pdf

AUB Link

Søg efter materialet i Aalborg Universitetsbiblioteks søgemaskine

AMIDST: Analysis of MassIve Data STreams - AMIDST
Madsen, A. L., Rommerdahl Bock, A., Nielsen, T. D. & Martinez, A. M.
European Union’s Seventh Framework Programme for research, technological development and demonstration
01/01/2014 → 31/12/2016
Projekter: Projekt › Forskning

Citationsformater

@inproceedings{05cf6c00d86d4122bcb216eec6f22e59,

title = "Parallelisation of the PC Algorithm",

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 parallelization 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.",

author = "Madsen, {Anders L{\ae}s{\o}} and Frank Jensen and Antonio Salmer{\'o}n and Helge Langseth and Nielsen, {Thomas Dyhre}",

year = "2015",

doi = "10.1007/978-3-319-24598-0_2",

language = "English",

isbn = "978-3-319-24597-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "14--24",

booktitle = "Advances in Artificial Intelligence",

address = "Germany",

note = "16th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2015 ; Conference date: 09-11-2015 Through 12-11-2015",

}

Madsen, AL, Jensen, F, Salmerón, A, Langseth, H & Nielsen, TD 2015, Parallelisation of the PC Algorithm. i Advances in Artificial Intelligence: 16th Conference of the Spanish Association for Artiﬁcial Intelligence, CAEPIA 2015 Albacete, Spain, November 9–12, 2015 Proceedings. Springer, Lecture Notes in Computer Science, bind 9422, s. 14-24, 16th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2015, Albacete, Spanien, 09/11/2015. https://doi.org/10.1007/978-3-319-24598-0_2

Parallelisation of the PC Algorithm. / Madsen, Anders Læsø; Jensen, Frank; Salmerón, Antonio et al.
Advances in Artificial Intelligence: 16th Conference of the Spanish Association for Artiﬁcial Intelligence, CAEPIA 2015 Albacete, Spain, November 9–12, 2015 Proceedings. Springer, 2015. s. 14-24 (Lecture Notes in Computer Science, Bind 9422).

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

TY - GEN

T1 - Parallelisation of the PC Algorithm

AU - Madsen, Anders Læsø

AU - Jensen, Frank

AU - Salmerón, Antonio

AU - Langseth, Helge

AU - Nielsen, Thomas Dyhre

PY - 2015

Y1 - 2015

N2 - 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 parallelization 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.

AB - 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 parallelization 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.

U2 - 10.1007/978-3-319-24598-0_2

DO - 10.1007/978-3-319-24598-0_2

M3 - Article in proceeding

AN - SCOPUS:84952654135

SN - 978-3-319-24597-3

T3 - Lecture Notes in Computer Science

SP - 14

EP - 24

BT - Advances in Artificial Intelligence

PB - Springer

T2 - 16th Conference of the Spanish Association for Artificial Intelligence, CAEPIA 2015

Y2 - 9 November 2015 through 12 November 2015

ER -

Madsen AL, Jensen F, Salmerón A, Langseth H, Nielsen TD. Parallelisation of the PC Algorithm. I Advances in Artificial Intelligence: 16th Conference of the Spanish Association for Artiﬁcial Intelligence, CAEPIA 2015 Albacete, Spain, November 9–12, 2015 Proceedings. Springer. 2015. s. 14-24. (Lecture Notes in Computer Science, Bind 9422). doi: 10.1007/978-3-319-24598-0_2

Parallelisation of the PC Algorithm

Abstract

Konference

Adgang til dokumentet

AUB Link

Fingeraftryk

Projekter

AMIDST: Analysis of MassIve Data STreams - AMIDST

Citationsformater