Polynomial-time algorithm for learning optimal tree-augmented dynamic Bayesian networks

Alexandra Carvalho Instituto de Telecomunicações, José Monteiro IST, Susana Vinga IDMEC
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:969-978, 2015.

Abstract

The identification of conditional dependences in longitudinal data is provided through structure learning of dynamic Bayesian networks (DBN). Several methods for DBN learning are concerned with identifying inter-slice dependences, but often disregard the intra-slice connectivity. We propose an algorithm that jointly finds the optimal inter and intra time-slice connectivity in a transition network. The search space is constrained to a class of networks designated by tree–augmented DBN, leading to polynomial time complexity. We assess the effectiveness of the algorithm on simulated data and compare the results to those obtained by a state of the art DBN learning implementation, showing that the proposed algorithm performs very well throughout the different experiments. Further experimental validation is made on real data, by identify- ing non-stationary gene regulatory networks of Drosophila melanogaster.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-telecomunicacoes15a, title = {Polynomial-time algorithm for learning optimal tree-augmented dynamic {B}ayesian networks}, author = {de Telecomunica{\c{c}}{\~o}es, Alexandra Carvalho Instituto and IST, Jos{\'e} Monteiro and IDMEC, Susana Vinga}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {969--978}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/telecomunicacoes15a/telecomunicacoes15a.pdf}, url = {https://proceedings.mlr.press/r13/telecomunicacoes15a.html}, abstract = {The identification of conditional dependences in longitudinal data is provided through structure learning of dynamic Bayesian networks (DBN). Several methods for DBN learning are concerned with identifying inter-slice dependences, but often disregard the intra-slice connectivity. We propose an algorithm that jointly finds the optimal inter and intra time-slice connectivity in a transition network. The search space is constrained to a class of networks designated by tree–augmented DBN, leading to polynomial time complexity. We assess the effectiveness of the algorithm on simulated data and compare the results to those obtained by a state of the art DBN learning implementation, showing that the proposed algorithm performs very well throughout the different experiments. Further experimental validation is made on real data, by identify- ing non-stationary gene regulatory networks of Drosophila melanogaster.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Polynomial-time algorithm for learning optimal tree-augmented dynamic Bayesian networks %A Alexandra Carvalho Instituto de Telecomunicações %A José Monteiro IST %A Susana Vinga IDMEC %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-telecomunicacoes15a %I PMLR %P 969--978 %U https://proceedings.mlr.press/r13/telecomunicacoes15a.html %V R13 %X The identification of conditional dependences in longitudinal data is provided through structure learning of dynamic Bayesian networks (DBN). Several methods for DBN learning are concerned with identifying inter-slice dependences, but often disregard the intra-slice connectivity. We propose an algorithm that jointly finds the optimal inter and intra time-slice connectivity in a transition network. The search space is constrained to a class of networks designated by tree–augmented DBN, leading to polynomial time complexity. We assess the effectiveness of the algorithm on simulated data and compare the results to those obtained by a state of the art DBN learning implementation, showing that the proposed algorithm performs very well throughout the different experiments. Further experimental validation is made on real data, by identify- ing non-stationary gene regulatory networks of Drosophila melanogaster. %Z Reissued by PMLR on 04 October 2026.
APA
de Telecomunicações, A.C.I., IST, J.M. & IDMEC, S.V.. (2015). Polynomial-time algorithm for learning optimal tree-augmented dynamic Bayesian networks. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:969-978 Available from https://proceedings.mlr.press/r13/telecomunicacoes15a.html. Reissued by PMLR on 04 October 2026.

Related Material