# Entropy and the Kullback-Leibler Divergence for Bayesian Networks: Computational Complexity and Efficient Implementation

arXiv: https://arxiv.org/abs/2312.01520 · HTML: https://mlsanity.com/paper/2312.01520/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 53 references that are in the map.
- First posted on arXiv 29 Nov 2023.

## Builds on (most cited first, 6 of 6)

- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Learning Gaussian Networks](https://mlsanity.com/paper/1302.6808/) (2013)
- [Model-Preserving Sensitivity Analysis for Families of Gaussian Distributions](https://mlsanity.com/paper/1809.10794/) (2018)
- [Logarithmic Time Parallel Bayesian Inference](https://mlsanity.com/paper/1301.7406/) (2013)

## Abstract (arXiv)

Bayesian networks (BNs) are a foundational model in machine learning and causal inference. Their graphical structure can handle high-dimensional problems, divide them into a sparse collection of smaller ones, underlies Judea Pearl's causality, and determines their explainability and interpretability. Despite their popularity, there are almost no resources in the literature on how to compute Shannon's entropy and the Kullback-Leibler (KL) divergence for BNs under their most common distributional assumptions. In this paper, we provide computationally efficient algorithms for both by leveraging BNs' graphical structure, and we illustrate them with a complete set of numerical examples. In the process, we show it is possible to reduce the computational complexity of KL from cubic to quadratic for Gaussian BNs.