## 4 Shannon Entropy and Kullback-Leibler Divergence
### Gaussian BNs  
\(\mathrm{H}(\mathcal{B})\) decomposes along with the local distributions \(X_{i}\mid\Pi_{X_{i}}\) in the case of GBNs: from (3), each \(X_{i}\mid\Pi_{X_{i}}\) is a univariate normal with variance \(\sigma_{X_{i}}^{2}(\mathcal{B})\) and therefore  
\[\mathrm{H}\Big{(}X_{i}\mid\Pi_{X_{i}}^{\mathcal{B}}\Big{)}=\frac{1}{2}\log \Bigl{(}2\pi\sigma_{X_{i}}^{2}(\mathcal{B})\Bigr{)}+\frac{1}{2} \tag{12}\]  
which has a computational complexity of \(O(1)\) for each node, \(O(N)\) overall. Equivalently, we can start from the global distribution of \(\mathcal{B}\) from Section 3.2 and consider that  
\[\det(\Sigma)=\det(C_{\mathcal{B}^{\prime}}C_{\mathcal{B}^{\prime}}^{\mathsf{T }})=\det(C_{\mathcal{B}})^{2}=\Bigl{(}\prod_{i=1}^{N}C_{\mathcal{B}}[i;i] \Bigr{)}^{2}=\prod_{i=1}^{N}\sigma_{X_{i}}^{2}(\mathcal{B}) \tag{13}\]  
because \(C_{\mathcal{B}}\) is lower triangular. The (multivariate normal) entropy of \(\mathbf{X}\) then becomes  
\[\mathrm{H}(\mathcal{B})=\frac{N}{2}+\frac{N}{2}\log 2\pi+ \frac{1}{2}\log\det(\Sigma)=\frac{N}{2}+\frac{N}{2}\log 2\pi+\frac{1}{2}\sum_{i=1}^{N} \log\sigma_{X_{i}}^{2}(\mathcal{B})\] \[=\sum_{i=1}^{N}\frac{1}{2}+\frac{1}{2}\log\Bigl{(}2\pi\sigma_{X_ {i}}^{2}(\mathcal{B})\Bigr{)}=\sum_{i=1}^{N}\mathrm{H}\Big{(}X_{i}\mid\Pi_{X_ {i}}^{\mathcal{B}}\Big{)}\]  
in agreement with (12). **Example 6** (Entropy of a GBN). : _For reasons of space, this example is presented as Example A4 in Appendix B._  
In the literature, the Kullback-Leibler divergence between two GBNs \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\) is usually computed using the respective global distributions \(N(\mu_{\mathcal{B}^{\prime}},\Sigma_{\mathcal{B}})\) and \(N(\mu_{\mathcal{B}^{\prime}},\Sigma_{\mathcal{B}^{\prime}})\)[50; 51; 52]. The general expression is  
\[\mathrm{KL}\bigl{(}\mathcal{B}\parallel\mathcal{B}^{\prime}\bigr{)}=\frac{1} {2}\biggl{[}\mathrm{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B} })+(\mu_{\mathcal{B}^{\prime}}-\mu_{\mathcal{B}})^{\mathsf{T}}\Sigma_{ \mathcal{B}^{\prime}}^{-1}(\mu_{\mathcal{B}^{\prime}}-\mu_{\mathcal{B}})-N+ \log\frac{\det(\Sigma_{\mathcal{B}^{\prime}})}{\det(\Sigma_{\mathcal{B}})} \biggr{]}, \tag{14}\]  
Figure 2: DAGs and local distributions for the discrete BNs \(\mathcal{B}\) (**top**) and \(\mathcal{B}^{\prime}\) (**bottom**) used in Examples 1, 4 and 5.  
for use in both the quadratic form and in the trace._  
However, computing \(\operatorname{KL}(\mathcal{B}\,\|\,\mathcal{B}^{\prime})\) from the global distributions \(N(\mu_{\mathcal{B}},\Sigma_{\mathcal{B}})\) and \(N(\mu_{\mathcal{B}^{\prime}},\Sigma_{\mathcal{B}^{\prime}})\) disregards the fact that BNs are sparse models that can be characterised more compactly by \((\mu_{\mathcal{B}},C_{\mathcal{B}})\) and \((\mu_{\mathcal{B}^{\prime}},C_{\mathcal{B}^{\prime}})\) as shown in Section 3.2. In particular, we can revisit several operations that are in the high-order terms of (15):  
* _Composing the global distribution from the local ones._ We avoid computing \(\Sigma_{\mathcal{B}}\) and \(\Sigma_{\mathcal{B}^{\prime}}\), thus reducing this step to \(O(2N)\) complexity. * _Computing the trace_\(\operatorname{tr}(\Sigma_{\mathcal{B}}^{-1}\Sigma_{\mathcal{B}})\). We can reduce the computation of the trace as follows. 1. We can replace \(\Sigma_{\mathcal{B}}\) and \(\Sigma_{\mathcal{B}^{\prime}}\) in the trace with any reordered matrix [53] (Result 8.17): we choose to use \(\widetilde{\Sigma}_{\mathcal{B}^{\prime}}\) and \(\widetilde{\Sigma}_{\mathcal{B}}^{*}\) where \(\widetilde{\Sigma}_{\mathcal{B}^{\prime}}\) is defined as before and \(\widetilde{\Sigma}_{\mathcal{B}}^{*}\) is \(\Sigma_{\mathcal{B}}\) with the rows and columns reordered to match \(\widetilde{\Sigma}_{\mathcal{B}^{\prime}}\).