Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:kth:diva-124731ISI: 000320709300006Scopus ID: 2-s2.0-84878898521OAI: oai:DiVA.org:kth-124731DiVA: diva2:638230
Funder
Science for Life Laboratory - a national resource center for high-throughput molecular bioscience
Note

QC 20130729

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

Open Access in DiVA

No full text

Scopus

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

urn-nbn

Altmetric score

urn-nbn
Total: 27 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf