Computation of Kullback–Leibler Divergence in Bayesian Networks
Kullback–Leibler divergence <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>K</mi><mi>L</mi><mo stretchy="false">(</mo><mi>p</mi><mo>,<...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/23/9/1122 |
| _version_ | 1797519431467794432 |
|---|---|
| author | Serafín Moral Andrés Cano Manuel Gómez-Olmedo |
| author_facet | Serafín Moral Andrés Cano Manuel Gómez-Olmedo |
| author_sort | Serafín Moral |
| collection | DOAJ |
| description | Kullback–Leibler divergence <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>K</mi><mi>L</mi><mo stretchy="false">(</mo><mi>p</mi><mo>,</mo><mi>q</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> is the standard measure of error when we have a true probability distribution <i>p</i> which is approximate with probability distribution <i>q</i>. 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–Leibler 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 <i>bnlearn</i> repository. Computer code in <i>Python</i> is provided taking as basis <i>pgmpy</i>, a library for working with probabilistic graphical models. |
| first_indexed | 2024-03-10T07:42:42Z |
| format | Article |
| id | doaj.art-89e744a3a43d492794bed22f93cd0d72 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T07:42:42Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-89e744a3a43d492794bed22f93cd0d722023-11-22T12:56:54ZengMDPI AGEntropy1099-43002021-08-01239112210.3390/e23091122Computation of Kullback–Leibler Divergence in Bayesian NetworksSerafín Moral0Andrés Cano1Manuel Gómez-Olmedo2Computer Science and Artificial Intelligent Department, University of Granada, 18071 Granada, SpainComputer Science and Artificial Intelligent Department, University of Granada, 18071 Granada, SpainComputer Science and Artificial Intelligent Department, University of Granada, 18071 Granada, SpainKullback–Leibler divergence <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>K</mi><mi>L</mi><mo stretchy="false">(</mo><mi>p</mi><mo>,</mo><mi>q</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> is the standard measure of error when we have a true probability distribution <i>p</i> which is approximate with probability distribution <i>q</i>. 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–Leibler 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 <i>bnlearn</i> repository. Computer code in <i>Python</i> is provided taking as basis <i>pgmpy</i>, a library for working with probabilistic graphical models.https://www.mdpi.com/1099-4300/23/9/1122probabilistic graphical modelslearning algorithmsKullback–Leibler divergence |
| spellingShingle | Serafín Moral Andrés Cano Manuel Gómez-Olmedo Computation of Kullback–Leibler Divergence in Bayesian Networks Entropy probabilistic graphical models learning algorithms Kullback–Leibler divergence |
| title | Computation of Kullback–Leibler Divergence in Bayesian Networks |
| title_full | Computation of Kullback–Leibler Divergence in Bayesian Networks |
| title_fullStr | Computation of Kullback–Leibler Divergence in Bayesian Networks |
| title_full_unstemmed | Computation of Kullback–Leibler Divergence in Bayesian Networks |
| title_short | Computation of Kullback–Leibler Divergence in Bayesian Networks |
| title_sort | computation of kullback leibler divergence in bayesian networks |
| topic | probabilistic graphical models learning algorithms Kullback–Leibler divergence |
| url | https://www.mdpi.com/1099-4300/23/9/1122 |
| work_keys_str_mv | AT serafinmoral computationofkullbackleiblerdivergenceinbayesiannetworks AT andrescano computationofkullbackleiblerdivergenceinbayesiannetworks AT manuelgomezolmedo computationofkullbackleiblerdivergenceinbayesiannetworks |