Change search
ReferencesLink to record
Permanent link

Direct link
Finding Optimal Bayesian Networks Using Precedence Constraints
KTH, School of Computer Science and Communication (CSC). KTH, Centres, Science for Life Laboratory, SciLifeLab.
2013 (English)In: Journal of machine learning research, ISSN 1532-4435, E-ISSN 1533-7928, Vol. 14, 1387-1415 p.Article in journal (Refereed) Published
Abstract [en]

We consider the problem of finding a directed acyclic graph (DAG) that optimizes a decomposable Bayesian network score. While in a favorable case an optimal DAG can be found in polynomial time, in the worst case the fastest known algorithms rely on dynamic programming across the node subsets, taking time and space 2(n), to within a factor polynomial in the number of nodes n. In practice, these algorithms are feasible to networks of at most around 30 nodes, mainly due to the large space requirement. Here, we generalize the dynamic programming approach to enhance its feasibility in three dimensions: first, the user may trade space against time; second, the proposed algorithms easily and efficiently parallelize onto thousands of processors; third, the algorithms can exploit any prior knowledge about the precedence relation on the nodes. Underlying all these results is the key observation that, given a partial order P on the nodes, an optimal DAG compatible with P can be found in time and space roughly proportional to the number of ideals of P, which can be significantly less than 2(n). Considering sufficiently many carefully chosen partial orders guarantees that a globally optimal DAG will be found. Aside from the generic scheme, we present and analyze concrete tradeoff schemes based on parallel bucket orders.

Place, publisher, year, edition, pages
2013. Vol. 14, 1387-1415 p.
Keyword [en]
exact algorithm, parallelization, partial order, space-time tradeoff, structure learning
National Category
Control Engineering Computer Science
URN: urn:nbn:se:kth:diva-124731ISI: 000320709300006ScopusID: 2-s2.0-84878898521OAI: diva2:638230
Science for Life Laboratory - a national resource center for high-throughput molecular bioscience

QC 20130729

Available from: 2013-07-29 Created: 2013-07-29 Last updated: 2013-07-29Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Parviainen, Pekka
By organisation
School of Computer Science and Communication (CSC)Science for Life Laboratory, SciLifeLab
In the same journal
Journal of machine learning research
Control EngineeringComputer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 16 hits
ReferencesLink to record
Permanent link

Direct link