{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:58:09Z","timestamp":1760241489085,"version":"build-2065373602"},"reference-count":27,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,4,12]],"date-time":"2018-04-12T00:00:00Z","timestamp":1523491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Dynamic Bayesian networks (DBN) are powerful probabilistic representations that model stochastic processes. They consist of a prior network, representing the distribution over the initial variables, and a set of transition networks, representing the transition distribution between variables over time. It was shown that learning complex transition networks, considering both intra- and inter-slice connections, is NP-hard. Therefore, the community has searched for the largest subclass of DBNs for which there is an efficient learning algorithm. We introduce a new polynomial-time algorithm for learning optimal DBNs consistent with a breadth-first search (BFS) order, named bcDBN. The proposed algorithm considers the set of networks such that each transition network has a bounded in-degree, allowing for p edges from past time slices (inter-slice connections) and k edges from the current time slice (intra-slice connections) consistent with the BFS order induced by the optimal tree-augmented network (tDBN). This approach increases exponentially, in the number of variables, the search space of the state-of-the-art tDBN algorithm. Concerning worst-case time complexity, given a Markov lag m, a set of n random variables ranging over r values, and a set of observations of N individuals over T time steps, the bcDBN algorithm is linear in N, T and m; polynomial in n and r; and exponential in p and k. We assess the bcDBN algorithm on simulated data against tDBN, revealing that it performs well throughout different experiments.<\/jats:p>","DOI":"10.3390\/e20040274","type":"journal-article","created":{"date-parts":[[2018,4,12]],"date-time":"2018-04-12T12:19:27Z","timestamp":1523535567000},"page":"274","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Polynomial-Time Algorithm for Learning Optimal BFS-Consistent Dynamic Bayesian Networks"],"prefix":"10.3390","volume":"20","author":[{"given":"Margarida","family":"Sousa","sequence":"first","affiliation":[{"name":"Instituto de Telecomunica\u00e7\u00f5es, Instituto Superior T\u00e9cnico, Universidade de Lisboa, 1049-001 Lisboa, Portugal"}]},{"given":"Alexandra","family":"Carvalho","sequence":"additional","affiliation":[{"name":"Instituto de Telecomunica\u00e7\u00f5es, Instituto Superior T\u00e9cnico, Universidade de Lisboa, 1049-001 Lisboa, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2018,4,12]]},"reference":[{"key":"ref_1","unstructured":"Pearl, J. (2014). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann."},{"key":"ref_2","unstructured":"Murphy, K.P., and Russell, S. (2002). Dynamic Bayesian Networks: Representation, Inference and Learning, University of California."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Yao, X.Q., Zhu, H., and She, Z.S. (2008). A dynamic Bayesian network approach to protein secondary structure prediction. BMC Bioinform., 9.","DOI":"10.1186\/1471-2105-9-49"},{"key":"ref_4","unstructured":"Zweig, G., and Russell, S. (1998). Speech Recognition with Dynamic Bayesian Networks. [Ph.D. Thesis, University of California]."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1016\/j.jbi.2008.01.006","article-title":"Dynamic Bayesian networks as prognostic models for clinical patient management","volume":"41","author":"Taal","year":"2008","journal-title":"J. Biomed. Inform."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1023\/A:1007465528199","article-title":"Bayesian Network Classifiers","volume":"29","author":"Friedman","year":"1997","journal-title":"Mach. Learn."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Grossman, D., and Domingos, P. (2004, January 4\u20138). Learning Bayesian network classifiers by maximizing conditional likelihood. Proceedings of the Twenty-First International Conference on Machine Learning, Banff, AB, Canada.","DOI":"10.1145\/1015330.1015339"},{"key":"ref_8","first-page":"2181","article-title":"Discriminative Learning of Bayesian Networks via Factorized Conditional Log-Likelihood","volume":"12","author":"Carvalho","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2716","DOI":"10.3390\/e15072716","article-title":"Efficient Approximation of the Conditional Relative Entropy with Applications to Discriminative Learning of Bayesian Network Classifiers","volume":"15","author":"Carvalho","year":"2013","journal-title":"Entropy"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"3438","DOI":"10.1016\/j.patcog.2014.03.019","article-title":"Hybrid learning of Bayesian multinets for binary classification","volume":"47","author":"Carvalho","year":"2014","journal-title":"Pattern Recognit."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Dojer, N. (2006). Learning Bayesian networks does not have to be NP-hard. International Symposium on Mathematical Foundations of Computer Science, Springer.","DOI":"10.1007\/11821069_27"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Vinh, N.X., Chetty, M., Coppel, R., and Wangikar, P.P. (2011, January 14\u201317). Polynomial time algorithm for learning globally optimal dynamic Bayesian network. Proceedings of the International Conference on Neural Information Processing, Shanghai, China.","DOI":"10.1007\/978-3-642-24965-5_81"},{"key":"ref_13","unstructured":"Monteiro, J.L., Vinga, S., and Carvalho, A.M. (2015, January 12\u201316). Polynomial-time algorithm for learning optimal tree-augmented dynamic Bayesian networks. Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), Amsterdam, The Netherlands."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1109\/TIT.1968.1054142","article-title":"Approximating discrete probability distributions with dependence trees","volume":"14","author":"Chow","year":"1968","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","unstructured":"Dasgupta, S. (August, January 30). Learning Polytrees. Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, Stockholm, Sweden."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Carvalho, A.M., and Oliveira, A.L. (2007, January 13\u201315). Learning Bayesian networks consistent with the optimal branching. Proceedings of the Sixth International Conference on Machine Learning and Applications, Cincinnati, OH, USA.","DOI":"10.1109\/ICMLA.2007.74"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Carvalho, A.M., Oliveira, A.L., and Sagot, M.F. (2007, January 2\u20136). Efficient learning of Bayesian network classifiers. Proceedings of the Australasian Joint Conference on Artificial Intelligence, Gold Coast, Australia.","DOI":"10.1007\/978-3-540-76928-6_4"},{"key":"ref_18","unstructured":"Koller, D., and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques, MIT Press."},{"key":"ref_19","unstructured":"Rissanen, J. (1985). Minimum Description Length Principle, Wiley Online Library."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/0004-3702(90)90060-D","article-title":"The computational complexity of probabilistic inference using Bayesian belief networks","volume":"42","author":"Cooper","year":"1990","journal-title":"Artif. Intell."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-1-4612-2404-4_12","article-title":"Learning Bayesian networks is NP-complete","volume":"Volume 112","author":"Chickering","year":"1996","journal-title":"Learning from Data"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0004-3702(93)90036-B","article-title":"Approximating probabilistic inference in Bayesian belief networks is NP-hard","volume":"60","author":"Dagum","year":"1993","journal-title":"Artif. Intell."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF00994016","article-title":"Learning Bayesian networks: The combination of knowledge and statistical data","volume":"20","author":"Heckerman","year":"1995","journal-title":"Mach. Learn."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/BF00994110","article-title":"A Bayesian method for the induction of probabilistic networks from data","volume":"9","author":"Cooper","year":"1992","journal-title":"Mach. Learn."},{"key":"ref_25","unstructured":"Friedman, N., Murphy, K., and Russell, S. (1998, January 24\u201326). Learning the structure of dynamic probabilistic networks. Proceedings of the Fourteenth Conference on UAI, Madison, WI, USA."},{"key":"ref_26","first-page":"2001","article-title":"The Bayes Net Toolbox for MATLAB","volume":"33","author":"Murphy","year":"2001","journal-title":"Comput. Sci. Stat."},{"key":"ref_27","first-page":"233","article-title":"Optimum branchings","volume":"71B","author":"Edmonds","year":"1968","journal-title":"Math. Decis. Sci."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/4\/274\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:00:26Z","timestamp":1760194826000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/4\/274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,12]]},"references-count":27,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,4]]}},"alternative-id":["e20040274"],"URL":"https:\/\/doi.org\/10.3390\/e20040274","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2018,4,12]]}}}