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

Autor:	Scutari, Marco
Rok vydání:	2023
Předmět:	Computer Science - Artificial Intelligence Computer Science - Machine Learning Statistics - Computation Statistics - Machine Learning
Zdroj:	Algorithms (2024), 17(1), 24
Druh dokumentu:	Working Paper
Popis:	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. Comment: 32 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2312.01520 Zobrazit plný text záznamu View this record from Arxiv