{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T03:39:51Z","timestamp":1784345991565,"version":"3.55.0"},"reference-count":19,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2021,8,28]],"date-time":"2021-08-28T00:00:00Z","timestamp":1630108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100006393","name":"Universidad de Granada","doi-asserted-by":"publisher","award":["CBUA"],"award-info":[{"award-number":["CBUA"]}],"id":[{"id":"10.13039\/501100006393","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Kullback\u2013Leibler divergence KL(p,q) is the standard measure of error when we have a true probability distribution p which is approximate with probability distribution q. Its efficient computation is essential in many tasks, as in approximate computation or as a measure of error when learning a probability. In high dimensional probabilities, as the ones associated with Bayesian networks, a direct computation can be unfeasible. This paper considers the case of efficiently computing the Kullback\u2013Leibler divergence of two probability distributions, each one of them coming from a different Bayesian network, which might have different structures. The paper is based on an auxiliary deletion algorithm to compute the necessary marginal distributions, but using a cache of operations with potentials in order to reuse past computations whenever they are necessary. The algorithms are tested with Bayesian networks from the bnlearn repository. Computer code in Python is provided taking as basis pgmpy, a library for working with probabilistic graphical models.<\/jats:p>","DOI":"10.3390\/e23091122","type":"journal-article","created":{"date-parts":[[2021,8,29]],"date-time":"2021-08-29T21:45:16Z","timestamp":1630273516000},"page":"1122","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Computation of Kullback\u2013Leibler Divergence in Bayesian Networks"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5555-0857","authenticated-orcid":false,"given":"Seraf\u00edn","family":"Moral","sequence":"first","affiliation":[{"name":"Computer Science and Artificial Intelligent Department, University of Granada, 18071 Granada, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7650-1221","authenticated-orcid":false,"given":"Andr\u00e9s","family":"Cano","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligent Department, University of Granada, 18071 Granada, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3817-8723","authenticated-orcid":false,"given":"Manuel","family":"G\u00f3mez-Olmedo","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligent Department, University of Granada, 18071 Granada, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,8,28]]},"reference":[{"key":"ref_1","unstructured":"de Jongh, M., and Druzdzel, M.J. (2009). A comparison of structural distance measures for causal Bayesian network models. Recent Advances in Intelligent Information Systems, Challenging Problems of Science, Computer Science Series, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1007\/s11222-019-09857-1","article-title":"Learning Bayesian networks from big data with greedy search: Computational complexity and efficient implementation","volume":"29","author":"Scutari","year":"2019","journal-title":"Stat. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.ijar.2019.09.002","article-title":"Learning Bayesian networks with local structure, mixed variables, and exact algorithms","volume":"115","author":"Talvitie","year":"2019","journal-title":"Int. J. Approx. Reason."},{"key":"ref_4","unstructured":"Natori, K., Uto, M., and Ueno, M. (2017). Consistent learning Bayesian networks with thousands of variables. Advanced Methodologies for Bayesian Networks, Available online: https:\/\/proceedings.mlr.press\/v73\/natori17a."},{"key":"ref_5","unstructured":"Kullback, S. (1968). Information Theory and Statistics, Dover Publication."},{"key":"ref_6","first-page":"2149","article-title":"A scoring function for learning Bayesian networks based on mutual information and conditional independence tests","volume":"7","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.knosys.2017.01.029","article-title":"A new hybrid method for learning Bayesian networks: Separation and reunion","volume":"121","author":"Liu","year":"2017","journal-title":"Knowl.-Based Syst."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Cano, A., G\u00f3mez-Olmedo, M., and Moral, S. (2020, January 15\u201319). Learning Sets of Bayesian Networks. Proceedings of the International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, Lisbon, Portugal.","DOI":"10.1007\/978-3-030-50143-3_12"},{"key":"ref_9","unstructured":"Koller, D., and Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques, MIT Press."},{"key":"ref_10","unstructured":"Elvira Consortium (2002, January 6\u20138). Elvira: An Environment for Probabilistic Graphical Models. Proceedings of the 1st European Workshop on Probabilistic Graphical Models, Cuenca, Spain."},{"key":"ref_11","unstructured":"Kj\u00e6rulff, U. (1993). Approximation of Bayesian Networks through Edge Removals, Department of Mathematics and Computer Science, Aalborg University. Technical Report IR-93-2007."},{"key":"ref_12","unstructured":"Choi, A., Chan, H., and Darwiche, A. (2012). On Bayesian Network Approximation by Edge Deletion. arXiv."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Kj\u00e6rulff, U. (1994). Reduction of computational complexity in Bayesian networks through removal of weak dependences. Uncertainty Proceedings 1994, Elsevier.","DOI":"10.1016\/B978-1-55860-332-5.50052-3"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Ankan, A., and Panda, A. (2015, January 6\u201312). pgmpy: Probabilistic graphical models using Python. Proceedings of the 14th Python in Science Conference (SCIPY 2015), Austin, TX, USA.","DOI":"10.25080\/Majora-7b98e3ed-001"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF01531015","article-title":"Probability propagation","volume":"2","author":"Shafer","year":"1990","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0004-3702(99)00059-4","article-title":"Bucket elimination: A unifying framework for reasoning","volume":"113","author":"Dechter","year":"1999","journal-title":"Artif. Intell."},{"key":"ref_17","unstructured":"Shachter, R. (1998, January 24\u201326). Bayes-Ball: The Rational Pasttime (for Determining Irrelevance and Requisite Information in Belief Networks and Influence Diagrams). Proceedings of the Fourteenth Annual Conference on Uncertainty in Artificial Intelligence (UAI\u201398), Madison, WI, USA."},{"key":"ref_18","unstructured":"Cano, A., and Moral, S. (1994, January 4\u20138). Heuristic algorithms for the triangulation of graphs. Proceedings of the International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, Paris, France."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v035.i03","article-title":"Learning Bayesian networks with the bnlearn R package","volume":"35","author":"Scutari","year":"2010","journal-title":"J. Stat. Softw."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/9\/1122\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:54:41Z","timestamp":1760165681000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/9\/1122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,28]]},"references-count":19,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2021,9]]}},"alternative-id":["e23091122"],"URL":"https:\/\/doi.org\/10.3390\/e23091122","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,28]]}}}