Bayesian structure discovery in Bayesian networks with less space

Pekka Parviainen, Mikko Koivisto
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:589-596, 2010.

Abstract

Current exact algorithms for score-based structure discovery in Bayesian networks on $n$ nodes run in time and space within a polynomial factor of $2^n$. For practical use, the space requirement is the bottleneck, which motivates trading space against time. Here, previous results on finding an optimal network structure in less space are extended in two directions. First, we consider the problem of computing the posterior probability of a given arc set. Second, we operate with the general partial order framework and its specialization to bucket orders, introduced recently for related permutation problems. The main technical contribution is the development of a fast algorithm for a novel zeta transform variant, which may be of independent interest.

Cite this Paper

BibTeX
@InProceedings{pmlr-v9-parviainen10a, title = {Bayesian structure discovery in Bayesian networks with less space}, author = {Parviainen, Pekka and Koivisto, Mikko}, booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics}, pages = {589--596}, year = {2010}, editor = {Teh, Yee Whye and Titterington, Mike}, volume = {9}, series = {Proceedings of Machine Learning Research}, address = {Chia Laguna Resort, Sardinia, Italy}, month = {13--15 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v9/parviainen10a/parviainen10a.pdf}, url = {https://proceedings.mlr.press/v9/parviainen10a.html}, abstract = {Current exact algorithms for score-based structure discovery in Bayesian networks on $n$ nodes run in time and space within a polynomial factor of $2^n$. For practical use, the space requirement is the bottleneck, which motivates trading space against time. Here, previous results on finding an optimal network structure in less space are extended in two directions. First, we consider the problem of computing the posterior probability of a given arc set. Second, we operate with the general partial order framework and its specialization to bucket orders, introduced recently for related permutation problems. The main technical contribution is the development of a fast algorithm for a novel zeta transform variant, which may be of independent interest.} }
Endnote
%0 Conference Paper %T Bayesian structure discovery in Bayesian networks with less space %A Pekka Parviainen %A Mikko Koivisto %B Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2010 %E Yee Whye Teh %E Mike Titterington %F pmlr-v9-parviainen10a %I PMLR %P 589--596 %U https://proceedings.mlr.press/v9/parviainen10a.html %V 9 %X Current exact algorithms for score-based structure discovery in Bayesian networks on $n$ nodes run in time and space within a polynomial factor of $2^n$. For practical use, the space requirement is the bottleneck, which motivates trading space against time. Here, previous results on finding an optimal network structure in less space are extended in two directions. First, we consider the problem of computing the posterior probability of a given arc set. Second, we operate with the general partial order framework and its specialization to bucket orders, introduced recently for related permutation problems. The main technical contribution is the development of a fast algorithm for a novel zeta transform variant, which may be of independent interest.
RIS
TY - CPAPER TI - Bayesian structure discovery in Bayesian networks with less space AU - Pekka Parviainen AU - Mikko Koivisto BT - Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics DA - 2010/03/31 ED - Yee Whye Teh ED - Mike Titterington ID - pmlr-v9-parviainen10a PB - PMLR DP - Proceedings of Machine Learning Research VL - 9 SP - 589 EP - 596 L1 - http://proceedings.mlr.press/v9/parviainen10a/parviainen10a.pdf UR - https://proceedings.mlr.press/v9/parviainen10a.html AB - Current exact algorithms for score-based structure discovery in Bayesian networks on $n$ nodes run in time and space within a polynomial factor of $2^n$. For practical use, the space requirement is the bottleneck, which motivates trading space against time. Here, previous results on finding an optimal network structure in less space are extended in two directions. First, we consider the problem of computing the posterior probability of a given arc set. Second, we operate with the general partial order framework and its specialization to bucket orders, introduced recently for related permutation problems. The main technical contribution is the development of a fast algorithm for a novel zeta transform variant, which may be of independent interest. ER -
APA
Parviainen, P. & Koivisto, M.. (2010). Bayesian structure discovery in Bayesian networks with less space. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 9:589-596 Available from https://proceedings.mlr.press/v9/parviainen10a.html.

Related Material